Учебники

27) Самая короткая работа сначала (SJF)

Декабрь 1, 2019

Существует два основных типа методов SJF:

  • Не вытесняющий SJF
  • Упреждающий SJF

Из этого руководства по операционной системе вы узнаете:

Характеристики SJF Scheduling

  • Это связано с каждой работой как единица времени для выполнения.
  • Этот метод алгоритма полезен для пакетной обработки, где ожидание выполнения заданий не является критическим.
  • Это может повысить пропускную способность процесса, поскольку вначале выполняется более короткое задание, что, возможно, требует короткого времени выполнения.
  • Это улучшает вывод заданий, предлагая более короткие задания, которые должны выполняться первыми, которые в основном имеют более короткое время выполнения.

Не вытесняющий SJF

В не вытесняющем планировании, когда цикл ЦП выделен для обработки, процесс удерживает его, пока не достигнет состояния ожидания или не завершится.

Рассмотрим следующие пять процессов, каждый из которых имеет свое уникальное время пакета и время прибытия.

Очередь процессов Время взрыва Время прибытия
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Шаг 0) Во время = 0, P4 прибывает и начинает выполнение.

Шаг 1) В момент времени = 1 приходит процесс P3. Но P4 по-прежнему нужно 2 исполнительных блока для завершения. Это продолжит исполнение.

Шаг 2) В момент времени = 2, процесс P1 прибывает и добавляется в очередь ожидания. P4 продолжит исполнение.

Шаг 3) В момент времени = 3 процесс P4 завершит свое выполнение. Время всплеска P3 и P1 сравнивается. Процесс P1 выполняется, потому что его время пакета меньше по сравнению с P3.

Шаг 4) В момент времени = 4, процесс P5 прибывает и добавляется в очередь ожидания. P1 продолжит выполнение.

Шаг 5) Во время = 5, процесс P2 прибывает и добавляется в очередь ожидания. P1 продолжит выполнение.

Шаг 6) В момент времени = 9 процесс P1 завершит свое выполнение. Время всплеска P3, P5 и P2 сравнивается. Процесс P2 выполняется, потому что его время пакета является самым низким.

Шаг 7) В момент времени = 10 выполняется P2, а P3 и P5 находятся в очереди ожидания.

Шаг 8) В момент времени = 11 процесс P2 завершит свое выполнение. Время всплеска P3 и P5 сравнивается. Процесс P5 выполняется, потому что его время пакета меньше.

Шаг 9) В момент времени 15 процесс P5 завершит свое выполнение.

Шаг 10) В момент времени 23 процесс P3 завершит свое выполнение.

Шаг 11) Давайте подсчитаем среднее время ожидания для приведенного выше примера.

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

Упреждающий SJF

В Preemptive SJF Scheduling задания помещаются в готовую очередь по мере их поступления. Процесс с самым коротким временем пакета начинает выполнение. Если приходит процесс с еще более коротким временем пакетной обработки, текущий процесс удаляется или освобождается от выполнения, а более короткому заданию назначается цикл ЦП.

Рассмотрим следующие пять процессов:

Очередь процессов Время взрыва Время прибытия
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Шаг 0) Во время = 0, P4 прибывает и начинает выполнение.

Очередь процессов Время взрыва Время прибытия
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Шаг 1) В момент времени = 1 приходит процесс P3. Но, у P4 есть более короткое время взрыва. Это продолжит исполнение.

Шаг 2) Во время = 2, процесс P1 прибывает с временем пакета = 6. Время пакета больше, чем у P4. Следовательно, P4 продолжит выполнение.

Шаг 3) В момент времени = 3 процесс P4 завершит свое выполнение. Время всплеска P3 и P1 сравнивается. Процесс P1 выполняется, потому что его время пакета меньше.

Шаг 4) В момент времени = 4, процесс P5 прибудет. Время взрыва P3, P5 и P1 сравнивается. Процесс P5 выполняется, потому что его время пакета является самым низким. Процесс P1 выгружен.

Очередь процессов Время взрыва Время прибытия
P1 5 из 6 осталось 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Шаг 5) Во время = 5, процесс P2 прибудет. Время посылки P1, P2, P3 и P5 сравнивается. Процесс P2 выполняется, потому что его время пакета меньше. Процесс P5 прерывается.

Очередь процессов Время взрыва Время прибытия
P1 5 из 6 осталось 2
P2 2 5
P3 8 1
P4 3 0
P5 3 из 4 осталось 4

Шаг 6) В момент времени = 6 выполняется P2.

Шаг 7) В момент времени = 7 P2 завершает свое выполнение. Время взрыва P1, P3 и P5 сравнивается. Процесс P5 выполняется, потому что его время пакета меньше.

Очередь процессов Время взрыва Время прибытия
P1 5 из 6 осталось 2
P2 2 5
P3 8 1
P4 3 0
P5 3 из 4 осталось 4

Шаг 8) В момент времени = 10, P5 завершит свое выполнение. Время взрыва P1 и P3 сравнивается. Процесс P1 выполняется, потому что его время пакета меньше.

Шаг 9) В момент времени = 15 P1 завершает свое выполнение. P3 — единственный оставшийся процесс. Это начнет выполнение.

Шаг 10) В момент времени = 23 P3 заканчивает свое выполнение.

Шаг 11) Давайте подсчитаем среднее время ожидания для приведенного выше примера.

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Преимущества SJF

Вот преимущества / преимущества использования метода SJF:

  • SJF часто используется для долгосрочного планирования.
  • Это сокращает среднее время ожидания по алгоритму FIFO (первый пришел — первый вышел).
  • Метод SJF дает наименьшее среднее время ожидания для определенного набора процессов.
  • Это подходит для заданий, запущенных в пакетном режиме, где время выполнения известно заранее.
  • Для пакетной системы долгосрочного планирования оценка времени пакета может быть получена из описания задания.
  • Для краткосрочного планирования нам нужно предсказать значение следующего пакета.
  • Вероятно, оптимально в отношении среднего времени выполнения заказа.

Недостатки / Минусы SJF

Вот некоторые недостатки / минусы алгоритма SJF:

  • Время завершения работы должно быть известно раньше, но это трудно предсказать.
  • Он часто используется в пакетной системе для долгосрочного планирования.
  • SJF не может быть реализован для планирования ЦП на короткий срок. Это связано с тем, что не существует конкретного метода для прогнозирования длины предстоящего пакета ЦП.
  • Этот алгоритм может вызвать очень длительные сроки выполнения работ или голодание.
  • Требуется знание того, как долго будет выполняться процесс или работа.
  • Это приводит к голоданию, которое не уменьшает среднее время выполнения заказа.
  • Трудно знать длину предстоящего запроса ЦП.
  • Прошедшее время должно быть записано, что приводит к увеличению нагрузки на процессор.

Резюме

  • SJF — это алгоритм, в котором процесс, имеющий наименьшее время выполнения, выбирается для следующего выполнения.
  • Планирование SJF связано с каждой задачей как единица времени для выполнения.
  • Этот метод алгоритма полезен для пакетной обработки, где ожидание выполнения заданий не является критическим.
  • Существуют в основном два типа методов SJF: 1) Непримитивный SJF и 2) Упреждающий SJF.
  • В не вытесняющем планировании, когда цикл ЦП выделен для обработки, процесс удерживает его, пока не достигнет состояния ожидания или не завершится.
  • В Preemptive SJF Scheduling задания помещаются в готовую очередь по мере их поступления.
  • Хотя процесс с коротким периодом запуска начинается, текущий процесс удаляется или освобождается от выполнения, а задание, которое короче, выполняется первым.
  • SJF часто используется для долгосрочного планирования.
  • Это сокращает среднее время ожидания по алгоритму FIFO (первый пришел — первый вышел).
  • В планировании SJF время завершения задания должно быть известно раньше, но его трудно предсказать.
  • SJF не может быть реализован для планирования ЦП на короткий срок. Это связано с тем, что не существует конкретного метода для прогнозирования длины предстоящего пакета ЦП.

 

414
Share: