Задача планировщика — распределять CPU-время между потоками/процессами, соблюдая целевые критерии: отзывчивость, пропускную способность и/или предсказуемость. Кратко о трёх моделях, их механике, плюсах/минусах и сценариях применения.
1) Планирование по приоритету (приоритетная очередь)
- Механика: каждому потоку присвоен приоритет; планировщик выбирает задачу с наивысшим приоритетом. При равных — обычно FIFO/round‑robin внутри уровня.
- Особенности: простая структура (очереди для каждого уровня приоритета), возможна немедленная преэмпция более приоритетной задачей.
- Проблемы: риск голодания низкоприоритетных задач (starvation), приоритетная инверсия (решается приоритетным наследованием).
- Когда предпочтительно: системы с явным и жёстким иерархическим приоритетом — простые встраиваемые ОС, драйверы, части реального времени с фиксированными приоритетами.
2) Справедливое планирование (например, Linux CFS)
- Механика: каждому задаче даётся виртуальное время vruntime; задача с минимальным vruntime получает CPU. vruntime растёт пропорционально фактическому времени выполнения, скорректированному по весу:
$\Delta vruntime\approx \frac{\Delta t}{w}$.
CPU‑доля задачи примерно пропорциональна её весу:
${\text{share}}_i\approx \frac{w_i}{{\sum }_j{w}_j}$.
В Linux CFS задачи хранятся в сбалансированном дереве (red‑black tree), операции вставки/удаления/поиска — $\mathrm{O}(\log N)$.
- Особенности: цель — равноправное разделение CPU (timesharing) с учётом «nice»/веса; хорошая интерактивность.
- Проблемы: нет жёстких гарантий задержки; более сложен, чем простая приоритетная очередь.
- Когда предпочтительно: десктопы, серверы и многопользовательские системы, где важна общая справедливость и отзывчивость.
3) Реальное время (SCHED_FIFO, SCHED_RR, SCHED_DEADLINE и т.п.)
- Механика:
- Фиксированные приоритеты: SCHED_FIFO — не вытесняемая в пределах приоритета, SCHED_RR — круговая с квантами.
- Deadline/EDF (SCHED_DEADLINE): задания имеют исполнение, дедлайн и период; планировщик обеспечивает выполнении в рамках ограничений (правила EDF/ресурсных резервов).
- Особенности: даёт детерминированные гарантии по задержке и завершению; часто требует статического анализа WCET/периодов.
- Проблемы: снижают общую пропускную способность для фоновых задач; требуют управления приоритетной инверсией и аккуратной настройки.
- Когда предпочтительно: управление роботами, аудио/видео в реальном времени с низкой латентностью, авиация, промышленное управление.
Краткое сравнение по свойствам
- Предсказуемость/детерминированность: реальное время > приоритетное > справедливое.
- Справедливость: справедливое >> приоритетное/реальное.
- Риск голодания: приоритетное (высок) > реальное (высок для низкого приоритета) > справедливое (низкий).
- Применимость: интерактив/мультизадачность — CFS; жёсткие требования латентности — RT; простая политика и иерархия важнее — приоритетная.
Вывод: выбор модели зависит от требований: если нужны детерминированные гарантии — RT, если нужна общая отзывчивость и справедливость — CFS (fair), если приоритеты и простота критичны — приоритетная модель.