Найкоротше завдання спочатку (SJF): превентивний, невипереджувальний приклад

Що таке найкоротший графік роботи?

Найкоротша робота спочатку (SJF) це алгоритм, в якому для наступного виконання вибирається процес, який має найменший час виконання. Цей метод планування може бути випереджальним або невипереджальним. Це значно скорочує середній час очікування для інших процесів, які очікують на виконання. Повна форма SJF – це найкоротша робота.

В основному існує два типи методів 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 Scheduling пов’язано з кожною роботою як одиницею часу для виконання.
Цей метод алгоритму корисний для обробки пакетного типу, де очікування завершення завдань не є критичним.
В основному існує два типи методів SJF: 1) Non-Preemptive SJF і 2) Preemptive SJF.
У невипереджувальному плануванні, як тільки цикл ЦП виділено для процесу, процес утримує його, поки не досягне стану очікування або не завершиться.
У Preemptive SJF Scheduling завдання додаються до черги готовності, коли вони надходять.
Незважаючи на те, що починається процес із коротким часом пакету, поточний процес видаляється або виключається з виконання, а завдання, яке коротше, виконується першим.
SJF часто використовується для довгострокового планування.
Це зменшує середній час очікування за алгоритмом FIFO (першим прийшов, першим вийшов).
У плануванні SJF час завершення завдання має бути відомий раніше, але його важко передбачити.
SJF не можна реалізувати для планування ЦП на короткий термін. Це тому, що немає спеціального методу для прогнозування тривалості майбутнього вибуху ЦП.