Як ми бачимо, середній час очікування для алгоритму 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 - планування.