Найкоротше завдання спочатку (SJF): превентивний, невипереджувальний приклад
⚡ Розумний підсумок
Найкоротший час виконання (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
У випереджувальному плануванні 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 (First In First Out - перший прийшов, перший вийшов).
- Метод SJF дає найнижчий середній час очікування для певного набору процесів.
- Це підходить для завдань, що виконуються пакетно, коли час виконання відомий заздалегідь.
- Для пакетної системи довгострокового планування оцінку часу пакету можна отримати з посадової інструкції.
- Для короткострокового планування нам потрібно передбачити значення часу наступного пакету.
- Це, ймовірно, оптимально з точки зору середнього часу виконання.
Недоліки/мінуси SJF
Ось деякі недоліки/мінуси алгоритму SJF:
- Термін виконання роботи повинен бути відомий раніше, але його важко передбачити.
- Він часто використовується в пакетній системі для довгострокового планування.
- SJF не може бути реалізований для Планування ЦП на короткий термін. Це тому, що немає спеціального методу для прогнозування тривалості майбутнього вибуху ЦП.
- Цей алгоритм може спричинити дуже тривалий час виконання або голодування.
- Вимагає знання того, як довго триватиме процес або робота.
- Це призводить до голодування, яке не зменшує середній час виконання робіт.
- Важко дізнатися довжину майбутнього запиту ЦП.
- Слід записувати час, що минув, оскільки це призводить до збільшення навантаження на процесор.























