Кратко — из такого простого приоритетного планировщика возможны три типичных класса проблем: дедлок, голодание и инверсия приоритетов. Ниже по каждой проблеме: причина, проявление и практичные способы решения для интерактивных и реального времени систем.
1) Дедлок
- Причина: блокирующие ресурсы + круговая зависимость (Coffman‑условия: взаимное исключение, удержание и ожидание, отсутствие принудительной отмены, круговое ожидание).
- Пример: задачи берут ресурсы в разном порядке и ждут друг друга.
- Решения (интерактивные):
- запрещать круговое ожидание — единый глобальный порядок захвата ресурсов (тотальный порядок по id), или всегда захватывать все ресурсы атомарно;
- таймауты/trylock + откат и повтор;
- детекция + восстановление (снижение приоритетов/убийство задач).
- Решения (реального времени):
- избегать динамических/множественных блокировок; использовать неблокирующие/wait‑free алгоритмы;
- гарантировать отсутствие кругового ожидания проектированием ресурсообразования;
- если блокировки необходимы — использовать протоколы, обеспечивающие гарантированный и предсказуемый максимум времени блокировки (см. PCP/SRP ниже).
2) Голодание (starvation)
- Причина: низкоприоритетные задачи постоянно вытесняются более приоритетными и никогда не получают процессор.
- Проявление: долгий или бесконечный отклик низких приоритетов.
- Решения (интерактивные):
- старение приоритетов (priority aging) — постепенно повышать приоритет ожидания;
- справедливые очереди/квоты (round‑robin, multilevel feedback queue);
- приоритетные бустеры для задач I/O.
- Решения (реального времени):
- в RT нельзя произвольно менять приоритеты — вместо этого назначают расписуемость через анализ WCET и резервацию полосы (budgeting, sporadic server);
- гарантировать минимальную долю CPU для низкоприоритетных задач (серверы, квоты) и проводить анализ допустимости (schedulability) с учётом блокировок;
- проектировать систему так, чтобы важные операции не могли полностью монополизировать CPU на неограниченное время.
3) Инверсия приоритетов
- Причина: низкоприоритетная задача держит ресурс (критическую секцию), высокая задача блокируется, а средняя по приоритету прерывает низкую и не даёт ей завершить критическую секцию — высокая остаётся заблокированной (классический пример с $T_H,T_M,T_L$).
- Риск: неограниченное или долгое задерживание $T_H$.
- Решения (интерактивные):
- mutex с повышением приоритета (priority inheritance) — временно повышать приоритет владельца мьютекса до приоритета заблокированных задач;
- короткие критические секции, избегать долгих блокировок;
- использовать trylock/timeout, реорганизовать код.
- Решения (реального времени):
- применять формальные протоколы доступа к ресурсам, гарантирующие предсказуемые верхние границы блокировки:
- Priority Ceiling Protocol (PCP) или Immediate Ceiling Protocol (ICP) — предотвращают длительную инверсию и дают жёсткий верхний предел блокировок;
- Stack Resource Policy (SRP) для EDF‑планирования.
- использовать priority inheritance, если PCP/SRP неприменимы, но учитывать, что для анализа schedulability предпочтительнее PCP/SRP;
- избегать ненужных блокировок, использовать lock‑free/wait‑free структуры данных.
- Формализованное требование в RT: для каждого задания $i$ надо оценить время блокировки $B_i$ и включить его в проверку расписуемости, например для фиксированных приоритетов: $$R_i=C_i+B_i+\sum _{j:P_j>P_i}\lceil \frac{R_i}{T_j}\rceil C_j,$$ где $R_i$ — время ответа, $C_i$ — WCET, $T_j$ — период задач выше приоритета.
Короткие практические рекомендации при проектировании:
- Не блокируйтесь внутри run() дольше, чем нужно; минимизируйте критические секции.
- Для интерактивных систем — используйте старение, таймауты и разумные mutex‑механизмы (priority inheritance при необходимости).
- Для систем реального времени — применяйте формальные RT‑протоколы (PCP/SRP), резервируйте CPU (sporadic server) и проводите анализ допустимости с учётом максимального времени блокировки.
Если нужно, могу привести пример сценария с $T_H,T_M,T_L$ и показать, как priority inheritance и PCP изменяют порядок выполнения.