Shortest-Job-First (SJF)
При розгляді алгоритмів FCFS і RR ми бачили, наскільки істотним для них є порядок розташування процесів в черзі процесів, готових до виконання. Якщо короткі завдання розташовані в черзі ближче до її початку, то загальна продуктивність цих алгоритмів значно зростає. Якби ми знали час наступних CPU burst для процесів, що знаходяться в стані готовність, то могли б вибрати для виконання не процес з початку черги, а процес з мінімальною тривалістю CPU burst. Якщо ж таких процесів два або більше, то для вибору одного з них можна використовувати вже відомий нам алгоритм FCFS. Квантування часу при цьому не застосовується. Описаний алгоритм отримав назву "найкоротша робота першої" або Shortest Job First (SJF).
SJF-алгоритм короткострокового планування може бути як витісняє. так і невитісняючі. При невитісняючі SJF - плануванні процесор надається обраному процесу на все необхідне йому час, незалежно від подій, що відбуваються в обчислювальній системі. При витісняє SJF - плануванні враховується поява нових процесів в черзі готових до виконання (з числа знову народилися або розблокованих) під час роботи обраного процесу. Якщо CPU burst нового процесу менше, ніж залишок CPU burst у що виконується, то що виконується процес витісняється новим.
Розглянемо приклад роботи невитісняючі алгоритму SJF. Нехай в стані готовність знаходяться чотири процесу, p0. p1. p2 і p3. для яких відомі часи їх чергових CPU burst. Ці часи наведені в таблиці 3.4. Як і раніше, будемо вважати, що вся діяльність процесів обмежується використанням лише одного проміжку CPU burst. що процеси не роблять операцій введення-виведення і що часом перемикання контексту можна знехтувати.
Як ми бачимо, середній час очікування для алгоритму SJF становить (4 + 1 + 9 + 0) / 4 = 3,5 одиниці часу. Легко порахувати, що для алгоритму FCFS при порядку процесів p0. p1. p2. p3 ця величина буде дорівнювати (0 + 5 + 8 + 15) / 4 = 7 одиницям часу, т. е. буде в два рази більше, ніж для алгоритму SJF. Можна показати, що для заданого набору процесів (якщо в черги не з'являються нові процеси) алгоритм SJF є оптимальним з точки зору мінімізації середнього часу очікування серед класу невитисняючих алгоритмів.
Для розгляду прикладу витісняє SJF планування ми візьмемо ряд процесів p0. p1. p2 і p3 з різними часом CPU burst і різними моментами їх появи в черзі процесів, готових до виконання (див. табл. 3.6.).
Час появи в черзі чергового CPU burst
У початковий момент часу в стані готовність знаходяться тільки два процеси, p0 і p3. Менший час чергового CPU burst виявляється у процесу p3. тому він і вибирається для виконання (див. таблицю 3.7.). Після 2 одиниць часу в систему надходить процес p1. Час його CPU burst менше, ніж залишок CPU burst у процесу p3. який витісняється зі стану виконання і переводиться в стан готовність. Після ще 2 одиниць часу процес p1 завершується, і для виконання знову вибирається процес p3. У момент часу t = 6 в черзі процесів, готових до виконання, з'являється процес p2. але оскільки йому для роботи потрібно 7 одиниць часу, а процесу p3 залишилося працювати всього 1 одиницю часу, то процес p3 залишається в стані виконання. Після його завершення в момент часу t = 7 в черзі знаходяться процеси p0 і p2. з яких вибирається процес p0. Нарешті, останнім отримає можливість виконуватися процес p2.
Основну складність при реалізації алгоритму SJF представляє неможливість точного знання тривалості чергового CPU burst для виконуються процесів. У пакетних системах кількість процесорного часу, необхідне завданням для виконання, вказує користувач при формуванні завдання. Ми можемо брати цю величину для здійснення довгострокового SJF - планування. Якщо користувач вкаже більше часу, ніж йому потрібно, він буде чекати результату довше, ніж міг би, так як завдання буде завантажено в систему пізніше. Якщо ж він вкаже меншу кількість часу, завдання може не дорахуватися до кінця. Таким чином, в пакетних системах рішення задачі оцінки часу використання процесора перекладається на плечі користувача. При короткостроковому плануванні ми можемо робити тільки прогноз тривалості наступного CPU burst. виходячи з передісторії роботи процесу. Нехай - величина n -го CPU burst. T (n + 1) - пророкує значення для n + 1 -го CPU burst. - деяка величина в діапазоні від 0 до 1.
Визначимо рекурентне співвідношення
T (0) покладемо довільній константою. Перший доданок враховує останнім поведінку процесу, тоді як другий доданок враховує його передісторію. При ми перестаємо стежити за останніми поведінкою процесу, фактично вважаючи
т. е. оцінюючи все CPU burst однаково, виходячи з деякого початкового припущення.
Поклавши, ми забуваємо про передісторію процесу. В цьому випадку ми вважаємо, що час чергового CPU burst буде збігатися з часом останнього CPU burst:
Зазвичай вибирають для рівноцінного обліку останнього поведінки і передісторії. Треба відзначити, що такий вибір зручний і для швидкої організації обчислення оцінки T (n + 1). Для підрахунку нової оцінки потрібно взяти стару оцінку, скласти з виміряним часом CPU burst і отриману суму розділити на 2. наприклад, зсунувши її на 1 біт вправо. Отримані оцінки T (n + 1) застосовуються як тривалості чергових проміжків часу безперервного використання процесора для короткострокового SJF - планування.