Планирование процессов

Задача планировщика

Готовых к выполнению потоков обычно больше, чем процессоров. Планировщик решает, кто будет выполняться и как долго.

Цели (часто противоречат друг другу):

Когда вызывается планировщик

• процесс блокируется (ввод-вывод, wait, sleep);
• процесс завершается;
• прерывание таймера — истёк квант времени;
• проснулся процесс с более высоким приоритетом.

Невытесняющее планирование: процесс работает, пока сам не отдаст процессор. Вытесняющее: ядро может отобрать процессор по таймеру. Все современные ОС общего назначения — вытесняющие.

Классические алгоритмы

FCFS (First Come, First Served)

Очередь в порядке прихода. Просто, но один длинный процесс задерживает всех («эффект конвоя»).

SJF (Shortest Job First)

Первым — самый короткий. Минимальное среднее время ожидания, но длительность заранее неизвестна (её прогнозируют по прошлым запускам).

Round Robin (карусель)

Каждый получает квант (например, 10 мс), затем уходит в конец очереди.

Слишком маленький квант — много переключений контекста; слишком большой — превращается в FCFS.

Приоритеты

Каждому процессу — приоритет, выбирается самый приоритетный. Проблема голодания низкоприоритетных решают старением: приоритет растёт со временем ожидания.

Многоуровневые очереди с обратной связью

Несколько очередей с разными приоритетами и квантами. Процесс, израсходовавший квант целиком (счётный), опускается ниже; часто блокирующийся (интерактивный) остаётся наверху. Так работал планировщик классического Unix.

Планирование в Linux

CFS (Completely Fair Scheduler, ядра 2.6.23–6.5) и пришедший ему на смену EEVDF (с 6.6) стремятся дать каждому потоку справедливую долю процессора:

• для каждого потока считается виртуальное время выполнения (vruntime) — сколько он проработал, взвешенно по приоритету;
• выбирается поток с наименьшим vruntime (CFS хранит их в красно-чёрном дереве);
• вес зависит от значения nice (−20…19): разница в 1 по nice ≈ 10% процессорного времени.

nice -n 10 ./long_job        # запустить «уступчиво»
renice -n 5 -p 4242          # изменить для работающего
top / htop                   # столбцы PR и NI

Политики реального времени

Потоки реального времени (приоритет 1–99) всегда вытесняют обычные.

Итог

• Планировщик выбирает следующий поток; вытесняющее планирование использует прерывания таймера.
• FCFS — просто, SJF — минимум ожидания, Round Robin — справедливо и отзывчиво, приоритеты требуют защиты от голодания.
• Linux: справедливое планирование по vruntime с весами по nice; отдельные политики реального времени.