Політики планування процесора: FCFS, SJF, Пріоритет та Round Robin

Вибір процесора: компроміс

Планувальник операційної системи визначає, який із багатьох процесів, готових до виконання, отримує процесор наступним чином, протягом якого часу та що відбувається, коли з'являється процес вищого пріоритету. Кожна політика планування є компромісом між трьома показниками: часом очікування (час, який процес проводить у стані готовності, але не виконується), часом виконання (загальний час від моменту прибуття до завершення) та часом відповіді (час до моменту отримання першого байта виводу). Оптимізуючи будь-який з цих показників, зазвичай погіршуються інші, тому реальні системи використовують різні планувальники для серверів пакетної обробки, робочих станцій та систем реального часу.

FCFS та SJF: два екстреми

Першим прийденим, першим буде зроблено (FCFS) запускає процеси в порядку їх надходження до завершення, без переривань. Це легко реалізувати і справедливо у наївний сенсі, але страждає від ефекту «конвою»: один довгий процес на початку черги змушує всі короткі процеси позаду нього чекати, що знижує середній час очікування, незважаючи на те, що загальна виконана робота залишається незмінною.

Перший за часом виконання (SJF) замість цього завжди вибирає процес із найменшим залишковим часом виконання. Це доводиться оптимальним для мінімізації середнього часу очікування серед політик без переривань — класичний результат аргументу про обмін, але воно вимагає знати час виконання процесу заздалегідь, що планувальники оцінюють лише приблизно (зазвичай за допомогою експоненційно зваженого середнього минулих часів виконання). Його превентивна версія, Перший за залишковим часом виконання (SRTF), може безладно «виснажувати» довгі процеси назавжди, якщо короткі постійно надходять.

avg waiting time (non-preemptive) = (1/n) * sum(start_i - arrival_i)
SJF minimises this sum for a fixed, known set of burst times
— but a single misestimated burst can cascade delay onto everyone behind it

Round Robin та часові інтервали

Round Robin надає кожному готовому процесу фіксований часовий квант (наприклад, 10–100 мс), потім перериває його виконання та повертає назад у чергу, якщо він не завершено. Це обмежує найгірший випадок часу відповіді приблизно до (n − 1) × квант для n готових процесів, тому воно є стандартним для інтерактивних систем. Розмір кванту – це ключовий фактор: занадто великий – Round Robin поступово перетворюється на FCFS з ефектом «конвою»; занадто малий – система витрачає все більшу частку часу ЦП на контекстні переходи – збереження та відновлення регістрів, очищення конвеєрів і записів TLB – які не виконують жодної корисної роботи.

Приоритетне планування та виснаження ресурсів

Приоритетне планування запускає процес з найвищим пріоритетом із черги готових до виконання, незалежно чи динамічно. Це природно відповідає реальним потребам (наприклад, потік курсора миші може перебивати процес пакетної компіляції), але жорсткий порядок пріоритетів може призвести до того, що низькопріоритетні процеси будуть чекати нескінченно, якщо вища пріоритетна робота постійно надходить. Стандартним рішенням є «старіння»: поступово підвищується ефективний пріоритет процесу, який перебуває в черзі готових до виконання, протягом тривалого часу, гарантуючи його виконання незалежно від того, що відбувається.

effectivePriority(p) = basePriority(p) - k * waitingTime(p)
// lower number = higher priority; waitingTime grows every tick
// eventually even the lowest-priority process outranks new arrivals

Багаторівневі черги зворотного зв’язку

Ядерні ядра (наслідування CFS від Linux, Windows та класичний Unix) використовують варіації багаторівневої черги зворотного зв’язку: декілька черг на основі round-robin з різними рівнями пріоритетів і розмірами кванту, де процес, який використує весь свій квант (поведінка, пов'язана з обчисленнями), переводиться на нижчий рівень пріоритету з більшим часом виконання, а процес, який раніше віддає CPU (поведінка, пов’язана з I/O та взаємодією), залишається на тому ж рівні або переходить на вищий рівень пріоритету з меншим часом виконання. Схему планування не потрібно знати справньої природи процесу заздалегідь – вона визначає її, спостерігаючи за поведінкою та адаптуючись, поєднуючи гнучкість round-robin із ефективністю, близькою до SJF, для справді коротких спалахів.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте CPU Scheduling і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.