Кратко и по делу.
1) Возможные состояния (для потоков $T_1$ и $T_2$, блокировок $A,B$):
- начальное: оба замка свободны.
- $T_1$ захватил $A$, $T_2$ свободен.
- $T_2$ захватил $B$, $T_1$ свободен.
- частичное ожидание: $T_1$ захватил $A$ и ждёт $B$; $T_2$ захватил $B$ и ждёт $A$.
- взаимная блокировка (deadlock): одновременно $T_1$ держит $A$ и ждёт $B$, $T_2$ держит $B$ и ждёт $A$. Это состояние устойчивое, никакой поток не продолжит.
2) Формальная причина (Coffman): выполняются все четыре условий — взаимное исключение, удержание и ожидание, отсутствие вытеснения, циклическое ожидание. В нашем примере циклическое ожидание очевидно:
$$T_1\to T_2\to T_1$$ (ребро $T_1\to T_2$ означает: $T_1$ ждёт ресурс, удерживаемый $T_2$).
3) Обнаружение взаимной блокировки (runtime):
- Построить wait-for-graph (вершины — потоки; ребро $X\to Y$ если $X$ ждёт ресурса, удерживаемого $Y$).
- Выполнять периодическую проверку графа на цикл (например DFS или алгоритм поиска сильных компонент). Сложность проверки — $O(N+E)$, где $N$ — число потоков, $E$ — число ожиданий.
- При обнаружении цикла — сигнал о deadlock; можно логировать состояние стеков/замков для диагностики.
4) Как устранить (минимум три варианта; с комментариями):
Вариант A — строгий порядок захвата (рекомендуемый)
- Ввести глобальный порядок ресурсов (например по идентификатору) и всегда брать замки в возрастающем порядке.
- Для двух замков: если $id(A)<id(B)$, оба потока делают lock(A); lock(B). Это исключает циклическое ожидание.
Вариант B — try-lock с откатом (optimistic backoff)
- Использовать неблокирующую попытку захвата: если не удалось захватить второй замок — отпустить первый, подождать (backoff) и повторить.
- Плюс: простая реализация; минус: возможен livelock/падение производительности при высокой конкуренции.
Вариант C — таймаут/откат
- При попытке захватить замок использовать таймаут. По истечении — освободить ранее захваченные и повторить или завершить транзакцию.
- Удобно при интеграции с логикой отката операций.
Вариант D — предотвращение через единую координационную блокировку
- Вместо двух мелких замков использовать один агрегированный mutex для обеих структур (или RW-lock).
- Простой, но хуже параллелизм.
Вариант E — детекция и восстановление
- Разрешать deadlock, но регулярно запускать детектор (см. п.3); при обнаружении цикла — принудительно прерывать/откатить/перезапустить один из потоков (victim selection).
- Подходит, если откат безопасен.
Вариант F — использовать высокоуровневые конструкции
- Транзакционная память или lock-free структуры, atomic операции, каналы/акторы — убрать явные блокировки.
5) Краткие рекомендации
- В большинстве случаев проще и безопаснее применять строгий порядок захвата (Вариант A).
- Для сложных динамических наборов ресурсов — сочетание try-lock с откатом и/или детекции+восстановления.
- Выбирать метод, учитывая требования к производительности, возможности отката и сложность реализации.
Если нужно, могу привести псевдокод для конкретного варианта (например, try-lock с откатом или порядок захвата).