Псевдокод, вызывающий дедлок (два потока захватывают мьютексы в разном порядке):
Пусть мьютексы $m_1$, $m_2$; потоки $T_1$, $T_2$.
T1:
lock($m_1$)
// делает часть работы
lock($m_2$)
// критическая секция
unlock($m_2$)
unlock($m_1$)
T2:
lock($m_2$)
// делает часть работы
lock($m_1$)
// критическая секция
unlock($m_1$)
unlock($m_2$)
Причина дедлока (Coffman conditions):
- Взаимное исключение (mutual exclusion): каждый мьютекс эксклюзивен.
- Удержание и ожидание (hold-and-wait): $T_1$ держит $m_1$ и ждёт $m_2$; $T_2$ держит $m_2$ и ждёт $m_1$.
- Непрерываемость (no preemption): мьютексы не могут быть принудительно отобраны.
- Кольцевая блокировка (circular wait): $T_1\to m_2\to T_2\to m_1\to T_1$.
Стратегии предотвращения и примеры (плюсы/минусы коротко):
1) Упорядочивание захвата (static ordering)
- Правило: каждый поток должен захватывать мьютексы в согласованном порядке, например $m_1$ перед $m_2$.
Псевдокод:
Любой поток, нуждающийся в обоих:
lock($m_1$)
lock($m_2$)
...
unlock($m_2$)
unlock($m_1$)
- Плюсы: просто, эффективно; устраняет circular wait.
- Минусы: требует глобальной политики, не всегда применимо при динамическом наборе ресурсов.
2) trylock с откатом и экспоненциальным бэкоффом
Псевдокод (для двух мьютексов):
while true:
lock($m_1$)
if try_lock($m_2$):
break
else:
unlock($m_1$)
sleep(backoff())
// повторить
// критическая секция
unlock($m_2$)
unlock($m_1$)
- Плюсы: избегает блокировки навсегда; прост в реализации.
- Минусы: возможны лишние повторные попытки и живучесть (livelock) без правильного бэкоффа.
3) Таймаут при блокировке (timed lock)
Псевдокод:
if timed_lock($m_1$, $t$):
if timed_lock($m_2$, $t$):
// критическая секция
unlock($m_2$)
unlock($m_1$)
else:
unlock($m_1$)
// обработка неудачи (повторить/ошибка)
else:
// обработка неудачи
- Плюсы: даёт гарантию возврата в случае ожидания; гибче.
- Минусы: нужно выбирать $t$ и обрабатывать откаты; может усложнить логику.
4) Обнаружение и восстановление (deadlock detection & recovery)
- Идея: позволить ресурсы захватываться, периодически строить wait-for граф; при обнаружении цикла — выбрать жертву (roll back, принудительно прервать поток или отнять ресурсы) и освободить ресурсы.
Псевдокод мониторинга:
periodically:
build_wait_for_graph()
if cycle_detected(graph):
victim = select_victim(cycle) // критерии: минимальная стоимость отката
terminate_or_rollback(victim)
- Плюсы: применимо при динамичных ресурсах.
- Минусы: сложность детекции, стоимость восстановления, возможна потеря работы.
Короткие рекомендации:
- Если можно задать глобальный порядок — используйте его (самый простой и быстрый).
- Для динамики — trylock/timeout с бэкоффом.
- В системах с критичной надежностью — детекция и восстановление (или транзакции с откатом).
- Комбинируйте подходы: порядок для большинства случаев + таймаут/trylock для редких динамических ситуаций.