Кратко и по сути — для каждой модели: сценарии применения, плюсы и минусы (задержки, голодание, предсказуемость).
1) Round‑robin (RR)
- Сценарии: интерактивные time‑sharing системы, терминальные/GUI процессы, серверы общего назначения.
- Преимущества: простота реализации; справедливость для равноценных задач; ограниченная реактивность для интерактивных задач.
- Параметр: кванта времени $q$.
- Время ожидания в худшем случае при $n$ готовых задач ≈ $(n-1)q$.
- Потенциальные проблемы:
- Задержки зависят от $q$ и числа задач: малая кванта → хорошая отзывчивость, но много переключений → накладные расходы ($\propto 1/q$); большая кванта → высокий отклик.
- Голодание: практически отсутствует при равных приоритетах (каждая задача получает квант регулярно).
- Предсказуемость: низкая для реального времени — нельзя гарантировать строгие дедлайны без дополнительной политики/приоритетов.
2) Multilevel Feedback Queue (MLFQ)
- Сценарии: смешанные рабочие нагрузки с интерактивными (краткие) и фоновыми (длительными) задачами; ОС, стремящиеся адаптивно отдавать приоритет интерактивности.
- Преимущества: адаптивно приближает поведение к Shortest‑Job‑First для коротких задач; даёт лучшую среднюю отзывчивость для интерактивных процессов; можно настроить демоцияцию/понижение при длительном CPU‑использовании.
- Параметры: число уровней $L$, правила демоции/агинга, кванты на уровнях.
- Потенциальные проблемы:
- Задержки: долгие CPU‑борные задачи могут получить большие задержки при многократной понижательной политике.
- Голодание: возможно для низших приоритетов, если нет механизма старения (aging) или периодического повышения приоритета (priority boost).
- Предсказуемость: худшая среди перечисленных — поведение адаптивно и зависит от историй выполнения, поэтому трудно формально доказать ограничения задержек без дополнительных правил.
- Настройка сложная: параметры ($L$, кванты, пороги) сильно влияют на поведение; возможна манипуляция задачами, которые сознательно yield/блокируются.
3) Real‑time priority scheduling (фиксированные/динамические приоритеты)
- Сценарии: жесткое/мягкое реальное время: встроенные контроллеры, мультимедиа, управление, где важны дедлайны и предсказуемость. Типы: фиксированный приоритет (Rate Monotonic, RM) и динамический (Earliest Deadline First, EDF).
- Преимущества: высокая предсказуемость при известном WCET и контроле допуска задач; формальные тесты приложимости:
- EDF на однопроцессоре является оптимальным по загрузке: при суммарной загрузке $U=\sum C_i/T_i$ достаточно $U\le 1$ для планируемости (при независимых периодических задачах).
- RM имеет аналитическую границу: для $n$ задач гарантированно планируемо при $U\le n(2^{1/n}-1)$.
- Потенциальные проблемы:
- Задержки: высокоприоритетные задачи имеют малые и предсказуемые задержки; низкоприоритетные могут испытывать большие задержки или вовсе отсутствовать выполнение.
- Голодание: реально для низких приоритетов в отсутствии механизмов контроля/ограничений; требуется admission control (чтобы не допустить перегрузки).
- Предсказуемость: хорошая для задач, прошедших анализ (известны $C_i,T_i$ или дедлайны), но критична корректность WCET и учёт блокировок/инверсии приоритетов.
- Другие риски: приоритетная инверсия (решается priority inheritance/protocol), накладные расходы на прерывания/контр‑переключения, необходимость статического анализа и контроля загрузки.
Краткое сравнение по ключевым свойствам:
- Справедливость: RR — высокая, MLFQ — средняя (зависит от правил), Real‑time — низкая (предпочтение важным задачам).
- Отзывчивость интерактивных задач: RR и MLFQ хороши ($MLFQ$ лучше для коротких задач); real‑time — хороша для задач с приоритетом/назначенными дедлайнами.
- Предсказуемость/анализируемость: real‑time (EDF/RM) лучше всего при корректных WCET и admission control; RR прост, но не подходит для жёсткого реального времени; MLFQ трудно анализировать формально.
- Настройка и сложность: RR — прост; MLFQ — много параметров и тонкая настройка; real‑time — требует анализов, протоколов синхронизации и admission control.
Вывод: выбирать по цели — если нужна простая справедливость и интерактивность → RR; если нужна адаптивная отзывчивость для смешанных нагрузок → MLFQ (при наличии механизмов старения/бустов); если нужны гарантии дедлайнов и предсказуемость → real‑time scheduling (EDF/RM) с анализом и средствами против приоритетной инверсии.