Що таке перше планування найкоротшої роботи?
Найкоротше завдання спочатку (SJF) - це алгоритм, у якому для наступного виконання вибирається процес, що має найменший час виконання. Цей метод планування може бути попереджувальним або непередбачувальним. Це значно зменшує середній час очікування для інших процесів, що очікують виконання. Повна форма SJF - це Найкоротша робота спочатку.
В основному існує два типи методів SJF:
- Неперевага SJF
- Попереджувальний SJF
У цьому посібнику з операційної системи ви дізнаєтесь:
- Що таке перше планування найкоротшої роботи?
- Характеристика планування SJF
- Неперевага 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 надходить і додається до черги очікування. Р4 продовжить виконання.
Крок 3) У момент = 3 процес P4 завершить своє виконання. Порівнюється час сплеску P3 та P1. Процес P1 виконується, оскільки час його спалаху менше, ніж у P3.
Крок 4) В момент = 4, процес P5 надходить і додається до черги очікування. Р1 продовжить виконання.
Крок 5) В момент = 5, процес P2 надходить і додається до черги очікування. Р1 продовжить виконання.
Крок 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 timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 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 Р2 завершує своє виконання. Порівнюється час сплеску 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 timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 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 не може бути застосований для планування процесора на короткий термін. Це тому, що не існує конкретного методу, щоб передбачити тривалість майбутнього сплеску процесора.
- Цей алгоритм може спричинити дуже тривалий час виконання або голодування.
- Потрібні знання про те, як довго триватиме процес чи робота.
- Це призводить до голоду, що не зменшує середній час обороту.
- Важко зрозуміти тривалість майбутнього запиту на процесор.
- Слід зафіксувати минулий час, що призводить до збільшення накладних витрат на процесор.
Резюме
- SJF - це алгоритм, у якому для наступного виконання вибирається процес, що має найменший час виконання.
- Планування SJF пов'язане з кожним завданням як одиниця часу, яку потрібно виконати.
- Цей метод алгоритму корисний для пакетної обробки, коли очікування завершення завдань не є критичним.
- В основному існує два типи методів SJF 1) Неперевага SJF та 2) Попередження SJF.
- При непередбачуваному плануванні, як тільки цикл процесора виділяється для обробки, процес утримує його до досягнення стану очікування або завершення.
- У превентивному плануванні SJF завдання розміщуються в черзі готових у міру надходження.
- Незважаючи на те, що розпочинається процес із коротким часом сплеску, поточний процес видаляється або виключається з виконання, а завдання, яке коротше, виконується 1-м.
- SJF часто використовується для довгострокового планування.
- Це зменшує середній час очікування за алгоритмом FIFO (First in First Out).
- При плануванні SJF час завершення роботи повинен бути відомий раніше, але важко передбачити.
- SJF не може бути застосований для планування процесора на короткий термін. Це тому, що не існує конкретного методу, щоб передбачити тривалість майбутнього сплеску процесора.