Ниже — краткий, но практический разбор ситуации с тремя потоками A, B, C и двумя взаимно исключающими ресурсами R1 и R2: какие наборы блокировок приводят к взаимной блокировке, как её предотвратить, и как обнаруживать и восстанавливать с минимальным прерыванием работы.

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

Классический «перекрёстный» deadlock между двумя потоками:
A взял R1 и затем пытается взять R2 (A: hold R1, wait R2).B взял R2 и затем пытается взять R1 (B: hold R2, wait R1).Получается цикл A → B → A — оба навсегда ждут друг друга.С третьим потоком C и двумя ресурсами:
При двух ресурсов цикл максимальной длины 2; поэтому с тремя потоками «полный» цикл из трёх вершин невозможен при условии, что каждый ресурс существует в единственном экземпляре. Возможные ситуации:Два потока (A и B) в deadlock, C просто блокируется или ждёт одного из них — C не создаёт трёхстороннего цикла.Если ресурсы имеют несколько экземпляров и/или процессы захватывают наборы ресурсов (например R1a, R1b и т.п.), возможны циклы длины >2. Но в простейшей модели (по одному экземпляру R1 и R2) единственная структураdeadlock — пара двух процессов, держащих по одному ресурсу в противоположном порядке.Пример пошагово (A и B):
A: lock(R1)B: lock(R2)A: try lock(R2) → блокируется (R2 занят B)B: try lock(R1) → блокируется (R1 занят A)Deadlock.

2) Превентивные стратегии (предотвращение deadlock)

Жёсткий глобальный порядок захвата ресурсов (рекомендуется)
Назначить каждому ресурсу число/уровень, например R1 < R2.Требование: все потоки захватывают ресурсы только в возрастании номера (никогда R2 перед R1). Это полностью устраняет цикл ожиданий.Простой, надёжен и малозатратен.Попытка атомарно захватить все требуемые ресурсы (try-acquire all-or-none)
try-lock для всех нужных ресурсов; если не удалось — отпустить все и повторить с backoff.Избегает частичных захватов и тем самым циркуляции ожиданий.Алгоритмы на основе временных ограничений (timeouts)
Если захват не удался за T, откатываем/освобождаем и повторяем.Протоколы типа wait-die / wound-wait (для распределённых/транзакционных систем)
Используют временной/приоритетный порядок, предотвращают циклы без глобального порядка.

3) Обнаружение deadlock (алгоритм)

Поддерживать граф ожиданий (wait-for graph, WFG):
Вершины = процессы (A,B,C).Ребро P -> Q, если P ждёт ресурс, который держит Q.В момент, когда запрос не может быть немедленно удовлетворён (процесс блокируется), добавлять соответствующее ребро и запускать проверку циклов.Поиск цикла: DFS или алгоритм обнаружения сильных компонент (Tarjan). При обнаружении цикла — deadlock подтверждён.Псевдокод (упрощённо):
при блокировке запроса P на ресурсе R:для каждого Q, держащего R, добавить ребро P->Q в WFGвыполнить DFS(cycles) из Pесли найден цикл → переход к восстановлению

4) Восстановление с минимальным прерыванием (стратегия выбора жертвы + действия)

Цель: минимизировать потери работы и избегать долгих простоев.Выбор «жертвы» (victim selection) — ключевой шаг. Эвристики (в порядке предпочтения для минимального нарушения):
Выбрать процесс, удерживающий наименьшее число ресурсов (освобождает больше для других).Если есть информация о стоимости отката — выбрать процесс с минимальной стоимости отката (меньше выполненной работы).Учитывать приоритеты/время работы — старые/высокоприоритетные процессы защищать (aging).Учитывать трудоёмкость восстановления (например, транзакции с чекпоинтом легче откатить).Действия по восстановлению:
Прекратить/откатить выбранный процесс (варианты):Аборт процесса (kill) — самый простой, немедленно освобождает ресурсы; потом можно перезапустить.Откат к чекпоинту (если есть) — дешевле по потерянной вычислительной работе.Принудительное освобождение локов (опасно, если ресурс в неконсистентном состоянии) — допустимо, только если возможна корректная коррекция.После освобождения ресурсов удалить соответствующие ребра в WFG и продолжить выполнение заблокированных потоков.Уведомить/перезапустить жертву после восстановления состояния.Псевдокод восстановления:
Найти цикл в WFG.Выбрать victim по эвристике cost = α num_resources_held + β estimated_restart_cost − γ * priority.Если есть checkpoint(victim): rollback(victim) → release_all_locks(victim).
Иначе if safe_to_kill(victim): kill(victim) → release locks.
Иначе (последняя мера) принудительно снять локи и пометить данные на реконструкцию/валидность.Уведомить жертву/перезапустить при необходимости.Удалить из WFG все ребра, связанные с жертвой; продолжить.

5) Практические рекомендации и компромиссы

Если возможно, используйте глобальное упорядочивание ресурсов — это самый дешёвый и надёжный способ.Если порядок затруднителен (динамические наборы ресурсов), используйте try-lock all-or-none или время ожидания + откат.Для минимального прерывания: внедрите чекпоинты для тяжёлых задач; при детекции deadlock откатывайте процессы до последнего чекпоинта, а не убивайте.Логирование и эвристики: собирайте статистику о том, какие процессы чаще становятся жертвами, чтобы корректировать α,β,γ в функции стоимости и избегать голодания.В распределённой системе используйте wound-wait (жёсткий приоритет: старший «рани» младшего, который откатывается) или wait-die — они предотвращают циклы с разумной политикой прерываний.

Короткая сводка (что делать в большинстве реалистичных систем)

Первичный выбор: везде, где возможно, фиксируйте порядок захвата ресурсов.Если порядок невозможен: используйте try-lock-all (all-or-none) или таймаут + backoff.Для уже возникшего deadlock: детектировать через wait-for graph; выбирать жертву по минимальной стоимости отката (количество захваченных ресурсов, оценка работы), откатывать её до чекпоинта или убивать как крайнюю меру; затем продолжать.

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

Привести конкретный пример кода (псевдокод на C/Java) для try-acquire-all или для построения WFG и обнаружения цикла.Предложить конкретную функцию стоимости для выбора жертвы с учётом метрик вашей системы.