Відмінності між версіями «3. Shortest-Job-First (SJF)»
(Створена сторінка: Для алгоритмів FCFS і RR досить істотним є порядок розташування процесів в черзі процесів г...) |
|||
| Рядок 9: | Рядок 9: | ||
більше, то для вибору одного з них можна використовувати вже відомий нам | більше, то для вибору одного з них можна використовувати вже відомий нам | ||
алгоритм FCFS. Квантування часу при цьому не застосовується. Описаний | алгоритм FCFS. Квантування часу при цьому не застосовується. Описаний | ||
| − | алгоритм отримав назву “найкоротша робота першої” або Shortest Job First | + | алгоритм отримав назву “найкоротша робота першої” або ''Shortest Job First |
| − | (SJF). | + | (SJF). '' |
| − | + | ||
SJF алгоритм короткострокового планування може бути як таким що | SJF алгоритм короткострокового планування може бути як таким що | ||
витісняє, так і таким, що не витісняє. При SJF плануванні що не витісняє | витісняє, так і таким, що не витісняє. При SJF плануванні що не витісняє | ||
Версія за 19:04, 26 квітня 2011
Для алгоритмів FCFS і RR досить істотним є порядок розташування процесів в черзі процесів готових до виконання. Якщо короткі задачі розташовані в черзі ближче до її початку, то загальна продуктивність цих алгоритмів значно зростає.
Якби ми знали час наступних CPU burst для процесів, що знаходяться в стані готовність, то могли б вибрати для виконання не процес з початку черги, а процес з мінімальною тривалістю CPU burst. Якщо ж таких процесів два або більше, то для вибору одного з них можна використовувати вже відомий нам алгоритм FCFS. Квантування часу при цьому не застосовується. Описаний алгоритм отримав назву “найкоротша робота першої” або Shortest Job First (SJF). SJF алгоритм короткострокового планування може бути як таким що витісняє, так і таким, що не витісняє. При SJF плануванні що не витісняє процесор надається вибраному процесу на весь потрібний йому час, незалежно від подій які відбуваються в обчислювальній системі. При SJF плануванні що витісняє враховується поява нових процесів в черзі готових до виконання (з числа тих, що знов народилися або розблокованих) під час роботи вибраного процесу. Якщо CPU burst нового процесу менше, ніж залишок CPU burst у того, що виконується, то процес, що виконується, витісняється новим.
Можна показати, що для заданого набору процесів (якщо в черзі не з'являються нові процеси) алгоритм SJF є оптимальним з погляду мінімізації середнього часу очікування серед класу всіх невитісняючих алгоритмів. Основну складність при реалізації алгоритму SJF представляє неможливість точного знання часу чергового CPU burst для процесів, що виконуються. У пакетних системах кількість процесорного часу, потрібне завданню для виконання, вказує користувач при формуванні завдання.
Можемо брати цю величину для здійснення довгострокового SJF планування. Якщо користувач вкаже більше часу, ніж йому потрібно, він чекатиме отримання результату довше, ніж міг би, оскільки завдання буде завантажене в систему пізніше. Якщо ж він вкаже меншу кількість часу, задача може не долічитися до кінця. Таким чином, в пакетних системах рішення задачі оцінки часу використання процесора перекладається на плечі користувача.
