Наступна найкоротша робота
Наступне найкоротше завдання (ННЗ), також відоме як спочатку найкоротше завдання або наступний найкоротший процес, — це політика планування, яка вибирає для виконання процес з найменшим часом виконання.[1] ННЗ — це алгоритм без витискання, тобто без тимчасового переривання завдання, котре виконує система.
Наступне найкоротше завдання є корисним та практичним через його простоту. Алгоритм мінімізує середній проміжок часу, протягом якого кожен процес повинен чекати, поки його виконання завершиться. Однак це може призвести до ресурсного голоду. Існує не нульова імовірність, що процеси, для виконання котрих потрібен тривалий час, не будуть виконані, якщо короткі процеси будуть постійно надходити до черги. Ця проблема може бути вирішена за допомогою техніки, що називається старіння.[2] Кожному завданню система приписує коефіцієнт, що враховує час очікування в черзі та обчислений ймовірний середній час виконання. Планувальник вибирає завдання, враховуючи ці коефіцієнти.
Також недоліком використання наступного найкоротшого завдання є те, що перед виконанням потрібно знати загальний час виконання завдання. Хоча точно передбачити час виконання приктично неможливо, для його оцінки можна використати кілька різних методів, наприклад середнє зважене значення попереднього часу виконання.[3] Також можна вжити багаторівневу чергу зі зворотним зв'язком.[1]
Наступне найкоротше завдання можна ефективно використовувати з інтерактивними процесами. Як правило, такі процеси виконуються за шаблоном перемикання між станами чергування та очікуванням команди та її виконанням. Якщо час виконання процесу розглядати як окрему "роботу", то минула поведінка може вказувати, котрий процес вибрати із черги на основі оцінки його часу виконання.
Наступне найкоротше завдання також використовують в спеціалізованих середовищах, де можливо отримати точні оцінки часу виконання завдання.
Примітки[ред. | ред. код]
- ↑ а б Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter Scheduling Introduction] (PDF), Arpaci-Dusseau Books
- ↑ Tanenbaum, A. S. (2008). Modern Operating Systems (вид. 3rd). Pearson Education, Inc. с. 156. ISBN 978-0-13-600663-3.
- ↑ Silberschatz, A.; Galvin, P.B.; Gagne, G. (2005). Operating Systems Concepts (вид. 7th). Wiley. с. 161. ISBN 0-471-69466-5.