Ниже — полный разбор: пример конкретной ситуации с тремя задачами и ресурсами, метод обнаружения и варианты восстановления, два практичных способа предотвращения (банкир и порядок захвата + приоритетная потолочная политика) и оценка последствий для систем с жёсткими (hard) временными ограничениями.

1) Конкретный пример взаимоблокировки (deadlock)

Условие системы:
Задачи: T1 (высокий приоритет), T2 (средний), T3 (низкий).Ресурсы: R1, R2, R3 — эксклюзивный доступ (mutex), каждый ресурс может быть занят только одной задачей.Начальное распределение и запросы:
T1 захватила R1, затем пытается захватить R2 (ждёт, пока R2 освободится).T2 захватила R2, затем пытается захватить R3 (ждёт).T3 захватила R3, затем пытается захватить R1 (ждёт).Наблюдение: каждое из трёх процессов ждёт ресурс, который занят следующим по кругу → круговая блокировка (T1 → T2 → T3 → T1). Это классический deadlock: удовлетворяются четыре необходимые условия (взаимное исключение, удержание и ожидание, отсутствие принудительного вытеснения, циклическое ожидание).

2) Обнаружение взаимоблокировки

Модели:
Граф распределения ресурсов (resource allocation graph): вершины — задачи и ресурсы; ребро task→resource — запрос; resource→task — выделение. Цикл в графе с эксклюзивными ресурсами означает deadlock.Wait-for graph (граф ожидания): только вершины — задачи; ребро Ti → Tj если Ti ждёт ресурс, который удерживает Tj. Наличие цикла в этом графе = deadlock.Алгоритм обнаружения:
При каждом запросе (или периодически) строим/обновляем wait-for граф и ищем цикл (DFS / Tarjan / поиск цикла). Сложность O(n + e) (n — число задач, e — число ожиданий).В системах с большим количеством задач/ресурсов можно ограничить проверку: триггер на появление «долго» ожидающих задач (> threshold) или при скоплении ожиданий.Практическая политика: запуск детектора при превышении порога ожидания или по таймеру. Для реального времени важно контролировать накладные расходы и частоту проверок.

3) Восстановление от взаимоблокировки (recovery)
Варианты, с минусами/рисками:

Убийство (terminate) одной или нескольких задач из цикла:
Плюсы: просто реализуется, быстро разрывает цикл.Минусы: потеря вычислений, нарушение требований — критично в hard-RT; требует отката/чистой остановки, освобождения ресурсов.Принудительное освобождение ресурса (preempt resources):
Вынудить задачу освободить ресурс и возобновить. Часто невозможно (ресурс в неконсистентном состоянии).Откат до контрольной точки (checkpoint & rollback):
Плюсы: безопаснее, можно восстановить корректное состояние.Минусы: требуется поддержка контрольных точек, дополнительная память/время — часто неприемлемо в RT.Репланирование/пересчёт приоритетов:
Может снять взаимоблокировку, но не всегда; требует сложной логики.Комбинированные подходы:
Детектор выбирает «жертву» по критериям (наименьший приоритет важности, минимальные потери), завершает/перезапускает её и освобождает ресурсы.Практическая рекомендация: восстановление неизбежно сопряжено с риском нарушения дедлайнов и консистентности; в hard-RT системах восстановление через убийство/откат обычно недопустимо, поэтому лучше предотвращать.

4) Стратегии предотвращения
A. Протокол банкира (Banker’s algorithm)

Идея: следить за максимально возможными требованиями задач и разрешать захват только если система остаётся "safe" (существует последовательность завершения).Требования: заранее известны максимальные потребности каждой задачи по каждому ресурсу, вычисления проверки безопасного состояния при каждом запросе.Плюсы: гарантирует отсутствие deadlock.Минусы для RT:
Нелегко применить при динамических/непредсказуемых требованиях.Вычислительная стоимость и задержки при каждой операции — плохо для жёсткого RT.Потребует значительной проектной дисциплины (максимумы должны быть корректными).Вывод: банкёр применим если ресурсы и максимумы статичны и можно допустить накладные расходы; в hard-RT почти всегда неудобен.

B. Порядок захвата ресурсов (global ordering)

Правило: каждому ресурсу присвоен уникальный номер; любая задача должна захватывать ресурсы строго в порядке возрастания номера (или наоборот). Это устраняет циклическое ожидание.Плюсы:
Простая реализация, низкие накладные расходы, не требует сложных проверок.Гарантирует отсутствие циклов.Минусы:
Требует аккуратного проектирования API; может приводить к повышенной блокировке (за счёт более частых удержаний ресурсов).Неохотно сочетается с динамическими требованиями захвата нескольких ресурсов.Применение: рекомендованная простая стратегия.

C. Протокол приоритетной потолочной блокировки (Priority Ceiling Protocol, PCP) / Immediate Ceiling Protocol (ICPP)

Идея: при захвате ресурса задача временно получает приоритет = потолок ресурса (максимальный приоритет любой задачи, которая может запросить этот ресурс). Это предотвращает как приоритетную инверсию, так и циклическое ожидание при правильной настройке.Свойства:
Устраняет взаимоблокировки (если реализован корректно) и обеспечивает верхнюю границу времени блокировки (bounded blocking).Часто предпочтителен для hard-RT систем.Практика:
Определите потолок каждого ресурса как максимум приоритета задач, которые могут его использовать.На попытку захвата ресурса проверяйте: можно ли захватить без нарушения потолка; иначе задача блокируется и получает приоритет потолка владельца.Плюсы: низкая накладная стоимость, формально выводимая оценка worst-case blocking time.Минусы: требует статического анализа того, какие задачи могут брать какие ресурсы; сложнее в динамических системах.

D. Альтернативы: неблокирующие/lock-free структуры, одноуровневые API, отказ от вложенных захватов.

Если возможно, избегайте многоресурсных критических секций: используйте атомарные операции, lock-free структуры, designs with message passing (actor), или передавайте ресурсы, а не захватывайте несколько одновременно.

5) Практические рекомендации для real-time (особенно hard-RT)

Для hard-RT систем:
Предпочтительны методы предотвращения с детерминированным временем блокировки: priority ceiling protocol (PCP / ICPP) или статический порядок захвата.Banker's algorithm обычно неприемлем из-за непредсказуемости и вычислительных накладных.Избегайте динамической аллокации множества ресурсов в критических задачах. Проектируйте API так, чтобы каждая задача захватывала не более одного ресурса за раз, если возможно.Предварительный статический анализ: определить максимум блокировок, оценить worst-case blocking time (WCB), выполнить верификацию расписания.Используйте приоритетную инверсию (priority inheritance) только для решения inversion, но помните: PI не устраняет циклическое ожидание; PCP предпочтительнее для deadlock-freedom.Если восстановление всё же требуется: заранее планируйте безопасные точки и механизмы rollback/redo, логирование и строгую обработку ошибок. В hard-RT системах часто "безопаснее" разработать поведение отказа (fail-safe), чем пытаться восстанавливать выполнение.Для soft-RT и non-critical:
Можно использовать таймауты при ожидании ресурса и попытки повторного захвата/перезапуска; это легче, но не гарантирует корректность.

6) Пример применения: детектор + восстановление в soft-RT (алгоритм)

При каждом запросе ресурса:
Добавить ребро Ti → resource в resource-allocation структуру.Обновить wait-for граф (ребро Ti → Tj если ресурс удерживает Tj).Выполнить DFS для поиска цикла, но только если задача ждёт дольше threshold.Если цикл найден, выбрать «жертву»:
критерий: наименьшая стоимость перезапуска / наименьший приоритет / или наименьший размер held-state.Освободить ресурсы жертвы (убить/перезапустить/откатить) и уведомить зависимые задачи.Замечание: шаг 5 может нарушить консистентность, поэтому нужен механизм восстановления данных.

7) Итоговые выводы

Deadlock в hard-RT системе — критическая ситуация: восстановление часто равносильно пропущенным дедлайнам или неправильной работе системы.Лучший путь для жёсткого RT — предотвращение deadlock на этапе проектирования: priority-ceiling / статический порядок ресурсных захватов / отказ от множества одновременно захватываемых ресурсов / возможность формальной верификации worst-case blocking times.Для систем с менее строгими временными ограничениями можно применять обнаружение и восстановление (детектор циклов + убийство/rollback), но это требует продуманной политики выбора жертвы и безопасных точек сохранения.

Если хотите, могу:

Привести псевдокод детектора циклов и выбора жертвы.Показать, как реализовать Priority Ceiling Protocol на примере API mutex.Рассчитать worst-case blocking time для простого набора задач с использованием PCP.