Кратко и по делу.
Когда возникает приоритетная инверсия
- Наличие разделяемого ресурса (мьютекс/лок) и критических секций.
- Существуют как минимум три задачи с приоритетами $P_H>P_M>P_L$.
- Низкоприоритетная задача $L$ удерживает ресурс, задача высшего приоритета $H$ блокируется, ожидая этот ресурс, и в этот момент задача среднего приоритета $M$ становится готовой и вытесняет $L$.
Итог: $H$ ждёт не только из‑за $L$, но и из‑за $M$ — приоритеты «инвертированы».
Конкретный пример с временной диаграммой
- Задачи: $L$ (низкий), $M$ (средний), $H$ (высокий). Приоритеты $P_H>P_M>P_L$.
- Параметры: $L$ входит в критическую секцию длительностью $C_L=6$, $M$ выполняется без блокировок $C_M=5$.
Сценарий:
- $t=0$: $L$ стартует и захватывает mutex, выполняет критическую секцию.
- $t=1$: $H$ становится готовым и пытается захватить mutex → блокируется (ждёт $L$).
- $t=2$: $M$ становится готовым; так как $P_M>P_L$, $M$ предшествует $L$ и выполняется с $t=2$ до $t=7$.
- $t=7$: $M$ завершил; $L$ возобновляется и завершает оставшиеся $4$ единицы работы (заканчивает в $t=11$).
- $t=11$: $L$ освобождает mutex, $H$ наконец получает ресурс и продолжает.
Таблично (интервалы времени указаны в единицах):
- $0-2$: выполняется $L$ (держит mutex)
- $2-7$: выполняется $M$ (прерывает $L$)
- $7-11$: выполняется $L$ (заканчивает CS)
- $11-...$: выполняется $H$
Без $M$ $H$ получил бы mutex в $t=6$; с $M$ — только в $t=11$. Это и есть приоритетная инверсия (задержка $H$ увеличилась).
Практические механизмы устранения
1) Priority Inheritance (наследование приоритета)
- Идея: когда $H$ блокируется на ресурсе, который держит $L$, временно поднять приоритет $L$ до $P_H$. Таким образом $L$ не будет вытеснен задачами со средним приоритетом и быстрее освободит ресурс.
- Поведение в примере: при появлении $H$ приоритет $L$ повышается до $P_H$, $M$ уже не сможет прервать $L$, $L$ завершает CS в $t=6$, $H$ получает ресурс — инверсия устранена.
- Преимущества:
- Простая и динамическая; обычно реализуется в ОС/RTOS; уменьшает время блокировки выше‑приоритетных задач.
- Поддерживает транзитивное наследование (цепочки блокировок).
- Недостатки:
- Не даёт жёсткой верхней границы блокировки в общем случае (в сложных цепочках блокировка может суммироваться), хотя практическая задержка часто существенно меньше.
- Требует отслеживания, когда и кому повышать/понижать приоритеты (сложность реализации, накладные переключения контекста).
- Не предотвращает взаимные блокировки (deadlocks) — только снижает инверсию.
2) Priority Ceiling Protocol (потолок приоритета) — две реализации: Original PCP и Immediate Ceiling Protocol (ICP)
- Идея: каждому ресурсу присваивается «потолок» — максимальный приоритет всех задач, которые могут его захватить: для ресурса $R$ потолок = $\max \{P_i\mid \text{задача}i\text{может захватить}R\}$.
- Правило (ICP, более часто используемое): задача не может войти в критическую секцию (захватить ресурс), если её приоритет ниже текущего системного потолка; при захвате её приоритет немедленно повышается до потолка ресурса.
- Эффект: предотвращается ситуация, в которой задача с приоритетом между владельцем ресурса и его пользователем может прервать владельца — тем самым приоритетная инверсия заранее исключается.
- Преимущества:
- Даёт жёсткие верхние границы блокировки (каждая задача может быть заблокирована не более чем на длину одной критической секции другой задачи в большинстве анализов RT).
- Предотвращает некоторые виды дедлоков (PCP).
- Подходит для жёсткого реального времени и статического анализа.
- Недостатки:
- Более консервативен: может ограничивать параллелизм (некоторые безопасные захваты блокируются заранее).
- Требует статического знания, какие задачи могут захватить какие ресурсы (анализ и установка потолков).
- Более строгая политика может привести к менее эффективному использованию CPU в динамических системах.
Краткое сравнение
- Priority inheritance: проще, динамическая, хорошо уменьшает инверсии в типичных сценариях; может не дать жёсткой гарантии времени блокировки в сложных системах.
- Priority ceiling: даёт формальные границы блокировки и предотвращает некоторые дедлоки; требует преданализa и может быть избыточно ограничивающим.
Рекомендация практического применения
- Для общих RTOS и систем со многими динамическими ресурсами часто используют priority inheritance как компромисс (простая реализация в мьютексах).
- Для жёсткого реального времени и приёмистых (safety‑critical) систем предпочитают priority ceiling (PCP/ICP) с предварительным анализом, чтобы иметь математически обоснованные задержки.