Сначала самое короткое задание (SJF): пример с вытеснением и без вытеснения

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

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

Характеристики планирования SJF

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

Невытесняющий 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

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

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

Очередь процесса	Время взрыва	Время прибытия
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.
• При невытесняющем планировании, как только цикл ЦП выделяется для процесса, процесс удерживает его до тех пор, пока не достигнет состояния ожидания или не завершится.
• При упреждающем планировании SJF задания помещаются в очередь готовности по мере их поступления.
• Хотя начинается процесс с коротким временем пакета, текущий процесс удаляется или прерывается из выполнения, а задание, которое короче, выполняется первым.
• SJF часто используется для долгосрочного планирования.
• Это сокращает среднее время ожидания по алгоритму FIFO (первым пришел – первым обслужен).
• При планировании SJF время завершения задания должно быть известно заранее, но его трудно предсказать.
• SJF не может быть реализован для планирования ЦП в краткосрочной перспективе. Это связано с тем, что не существует конкретного метода прогнозирования продолжительности предстоящего всплеска ЦП.