Кратко о проблеме: при приоритетной планировке низкоприоритетная задача, удерживающая мьютекс, может блокировать высокоприоритетную, при этом среднеприоритетная может прервать низкоприоритетную и удерживать процессор — получаем priority inversion и возможное нарушение временных ограничений.
Опишу протоколы, их свойства, пределы применимости и влияние на подтверждение временных ограничений.
1) Priority Inheritance Protocol (PIP)
- Идея: когда задача $H$ блокируется на ресурсе, которым владеет задача $L$ (ниже по приоритету), $L$ временно наследует приоритет $H$ (конкретно — наивысший блокирующий приоритет).
- Свойства:
- Устраняет классические случаи бесконечной инверсии и уменьшает влияние среднеприоритетных задач.
- Поддерживает динамическое распределение ресурсов (подходит при динамическом создании/использовании мьютексов).
- Возможна транзитивная наследственность (цепочки): высокоприоритетную задачу могут последовательно блокировать несколько низших задач через пересекающиеся ресурсы.
- Блокировка и анализ:
- Время блокировки задачи $i$ ограничено суммой длительностей критических секций тех более низкоприоритетных задач, которые действительно блокируют $i$ (в худшем случае может накопиться несколько таких секций).
- Для анализа отклика привычная формула:
$$R_i=C_i+B_i+\sum _{j\in hp(i)}\lceil \frac{R_i}{T_j}\rceil C_j,$$ где $B_i$ — вклад блокировок, зависящий от конкретных пересечений ресурсов при PIP.
- Ограничения:
- Не даёт строгого гарантированно малого верхнего предела блокировки в общем виде (хотя блокировка конечна).
- Реализация требует динамического изменения приоритетов (overhead, сложность отладки).
2) Priority Ceiling Protocol (PCP) — включая Immediate Ceiling Protocol (ICP) / Original Ceiling (варианты) и Stack Resource Policy (SRP)
- Идея: каждому ресурсу назначается потолок — наивысший приоритет задач, которые в перспективе могут его использовать. Правила блокировки не позволяют задаче войти в критическую секцию, если текущие захваченные ресурсы имеют потолок ≥ её приоритет (ICPP) либо используются другие критерии (оригинальный PCP). SRP — родственник PCP, применим для EDF.
- Свойства:
- Предотвращает дедлоки и ограничивает число блокировок: каждая задача может быть заблокирована не более одним критическим разделом задачи с более низким приоритетом.
- Даёт жёсткий и простой для анализа верхний предел блокировки.
- Блокировка и анализ:
- Для задачи $i$ верхняя граница блокировки:
$$B_i\le \max \{C{S}_k\mid \text{задача}k\text{с более низким приоритетом захватывает ресурс с потолком}\ge \text{приор}(i)\}.$$ - Ответное время рассчитывается той же формулой
$$R_i=C_i+B_i+\sum _{j\in hp(i)}\lceil \frac{R_i}{T_j}\rceil C_j,$$ но $B_i$ теперь легко и строго ограничено.
- Ограничения:
- Требует статической информации о том, какие задачи могут использовать какие ресурсы (чтобы задать потолки).
- Ограничивает параллелизм: ICPP может запрещать вход в критические секции даже если ресурс свободен, что иногда снижает пропускную способность.
- SRP необходим, если планирование по EDF; PCP обычно обсуждается для приоритетной (fixed-priority) системы.
3) Протоколы без учёта приоритетов (простые мьютексы, FIFO, отключение прерываний, non-preemptive sections)
- Описание: нет механизма изменения приоритета; блокировки происходят по очереди (FIFO) или критические секции выполняются неблокируемо (отключение прерываний).
- Свойства и риски:
- Простая реализация, но уязвимы к длительной или неограниченной priority inversion: высокая задача может быть заблокирована суммой многих критических секций или вообще ждать неопределённо.
- Отключение прерываний обеспечивает детерминизм на локальной CPU, но противопоказано в многопроцессорных/многозадачных системах и ухудшает реактивность.
- Влияние на анализ:
- Блокировка может быть большой: в худшем случае
$$B_i\le \sum _{k:priority(k)<priority(i)}C{S}_k,$$ что делает гарантию сроков трудной или невозможной для жёстких real-time требований.
Сравнение и влияние на подтверждение временных ограничений
- Предсказуемость: PCP/SRP > PIP > протоколы без приоритетов. PCP даёт самый строгий и простой для формального анализа верхний предел $B_i$ (обычно один критический раздел), что помогает доказать выполнение жёстких дедлайнов.
- Практичность: PIP проще в случаях динамического распределения ресурсов и когда сложно заранее определить все пересечения; даёт улучшение по сравнению с простыми мьютексами, но анализ сложнее (цепочки наследования).
- Производительность/параллелизм: PIP обычно даёт больше параллелизма, PCP может ограничивать конкурентный доступ ради предсказуемости.
- Реализация/накладные расходы: PIP — runtime-переназначение приоритетов (слегка дороже); PCP — проверки потолков при входе (статический анализ, меньше динамических изменений).
- Для жёсткого real-time (hard RT): рекомендуется PCP/ICPP или SRP (если используется EDF), т.к. они дают малые и формально выводимые блокировки. PIP приемлем, если ресурсы динамичны и когда можно учесть возможные цепочки в анализе. Протоколы без приоритетов непригодны для строгих временных гарантий.
Рекомендация кратко
- Если нужно жёсткое подтверждение временных ограничений и ресурсы известны статически — используйте priority ceiling / SRP.
- Если система динамична и вы не можете заранее построить потолки — используйте priority inheritance, но учитывайте усложнённый анализ и возможные цепочки блокировок.
- Избегайте простых немодифицированных мьютексов/FIFO в системах с жёсткими дедлайнами.
Если нужно, могу дать пример расчёта $B_i$ и $R_i$ для конкретного набора задач и ресурсов.