Взаимоблокировки: теория и борьба

Что такое взаимоблокировка

Узкий мост на одну машину. С двух сторон одновременно въезжают две машины и встречаются посередине. Каждой нужно, чтобы другая сдала назад, и ни одна не сдаёт. Стоять так они будут вечно.

Взаимоблокировка (deadlock, дедлок) — ситуация, когда несколько потоков навсегда застряли, потому что каждый ждёт ресурс, который держит другой из этой же группы. Ресурсом может быть мьютекс, семафор, строка в таблице базы, файл с блокировкой — всё, что захватывается монопольно.

От обычного ожидания дедлок отличается тем, что отпустить ресурс некому: все участники стоят и ждут друг друга. Долгое ожидание лока, который держит занятый, но работающий поток, — не дедлок, это рано или поздно пройдёт.

Классика: два лока в разном порядке

Самый частый дедлок в реальном коде — два лока, которые разные потоки берут в разном порядке. Перевод денег: поток 1 переводит с A на B и блокирует сначала A, потом B. Поток 2 переводит с B на A и блокирует сначала B, потом A.

   Поток 1 (A → B)                Поток 2 (B → A)
   ────────────────────           ────────────────────
   lock(A)   взял                 lock(B)   взял
   lock(B)   занят, ждёт П2       lock(A)   занят, ждёт П1
 
   П1 держит A и ждёт B; П2 держит B и ждёт A. Оба ждут вечно.

Коварство в том, что код каждого потока выглядит правильным, и дедлок случается только при определённом переплетении: оба должны успеть взять первый лок до того, как кто-то возьмёт второй. На тестах это может не случиться ни разу, а под нагрузкой в проде — раз в неделю.

Воспроизведём на Go. Чтобы не ждать удачного переплетения, заставим обе горутины взять первый лок прежде, чем кто-то возьмёт второй:

package main
 
import (
	"fmt"
	"sync"
)
 
func main() {
	var a, b sync.Mutex
	var wg, bothLocked sync.WaitGroup
	wg.Add(2)
	bothLocked.Add(2)
 
	go func() { // перевод A→B
		defer wg.Done()
		a.Lock()
		fmt.Println("горутина 1 держит A, хочет B")
		bothLocked.Done()
		bothLocked.Wait() // ждём, пока вторая возьмёт B
		b.Lock()
	}()
	go func() { // перевод B→A
		defer wg.Done()
		b.Lock()
		fmt.Println("горутина 2 держит B, хочет A")
		bothLocked.Done()
		bothLocked.Wait()
		a.Lock()
	}()
	wg.Wait()
}

горутина 2 держит B, хочет A
горутина 1 держит A, хочет B
fatal error: all goroutines are asleep - deadlock!
 
goroutine 1 [sync.WaitGroup.Wait]:
...

Рантайм Go заметил, что не осталось ни одной горутины, которая может продолжить работу, и аварийно завершил программу. Не рассчитывайте на это в сервисе: детектор срабатывает, только если заблокированы абсолютно все горутины. В HTTP-сервере всегда есть горутины, которые ждут сеть или таймеры, поэтому два зависших обработчика рантайм не заметит, просто запросы начнут висеть. Найти их помогает дамп всех горутин: kill -QUIT <pid> (рантайм напечатает стеки и завершится) или /debug/pprof/goroutine?debug=2, если подключён net/http/pprof. Ищите пары горутин в состоянии [sync.Mutex.Lock] с перекрёстными локами.

Четыре условия Коффмана

В 1971 году Эдвард Коффман с соавторами сформулировали четыре условия, которые выполняются в любой взаимоблокировке:

1. Взаимное исключение (mutual exclusion). Ресурс в каждый момент держит максимум один поток.
2. Удержание и ожидание (hold and wait). Поток держит уже захваченные ресурсы и при этом ждёт следующий.
3. Отсутствие вытеснения (no preemption). Ресурс нельзя отнять силой, только сам владелец может его отпустить.
4. Круговое ожидание (circular wait). Есть цикл: П1 ждёт П2, П2 ждёт П3, …, Пn ждёт П1.

На мосту: мост вмещает одну машину (1), стоящая машина держит свою половину моста и ждёт вторую (2), никто не может убрать чужую машину (3), две машины лоб в лоб — цикл из двух звеньев (4).

Важно, как эти условия связаны с дедлоком. Они необходимые: если дедлок случился, все четыре выполняются. Значит, если сломать хоть одно, дедлок невозможен — на этом построены все методы предотвращения. Но они не достаточные: все четыре могут быть выполнены в коде, а дедлок так и не случиться, если не сложится неудачное переплетение.

Граф ожидания

Чтобы увидеть дедлок формально, рисуют граф ожидания (wait-for graph): вершины — потоки, стрелка П1 → П2 означает «П1 ждёт ресурс, который держит П2».

   Нет цикла:                     Цикл:
 
   П1 ──→ П2                      П1 ──→ П2
           │                      ▲       │
           ▼                      │       ▼
          П3                      П4 ←── П3
 
   П3 никого не ждёт, доработает,  П1→П2→П3→П4→П1, выхода нет
   отпустит ресурс, за ним П2, П1

Если каждый ресурс существует в одном экземпляре (как мьютекс), правило простое: дедлок есть тогда и только тогда, когда в графе ожидания есть цикл. Поиском цикла в таком графе и занимаются детекторы дедлоков в базах данных. Детектор на Go вы напишете в задаче «Детект дедлока: цикл в графе ожидания».

Способ 1. Предотвращение: сломать одно условие

Самый практичный подход — устроить код так, чтобы дедлок был невозможен.

Про TryLock в разных источниках пишут по-разному, и это нормально. Поток, который при неудаче сам отпускает всё взятое, не держит ресурсы во время ожидания (ломается hold and wait). В OSTEP этот же приём описан как обход отсутствия вытеснения: поток как бы вытесняет сам себя. Смысл один.

Главный приём — упорядочивание локов (lock ordering). Договариваемся, что локи всегда берутся в одном порядке, например по возрастанию ID счёта. Тогда перевод A → B и перевод B → A оба берут сначала A, потом B. Кто первым взял A, тот и пройдёт; второй ждёт на A, ничего не держа, и цикла не получится.

package main
 
import (
	"fmt"
	"sync"
)
 
type Account struct {
	ID      int
	mu      sync.Mutex
	Balance int
}
 
// Transfer всегда берёт локи в порядке возрастания ID,
// независимо от направления перевода.
func Transfer(from, to *Account, amount int) {
	first, second := from, to
	if second.ID < first.ID {
		first, second = second, first
	}
	first.mu.Lock()
	defer first.mu.Unlock()
	second.mu.Lock()
	defer second.mu.Unlock()
 
	from.Balance -= amount
	to.Balance += amount
}
 
func main() {
	a := &Account{ID: 1, Balance: 1000}
	b := &Account{ID: 2, Balance: 1000}
 
	var wg sync.WaitGroup
	for i := 0; i < 500; i++ {
		wg.Add(2)
		go func() { defer wg.Done(); Transfer(a, b, 1) }() // A → B
		go func() { defer wg.Done(); Transfer(b, a, 1) }() // B → A
	}
	wg.Wait()
	fmt.Println("A:", a.Balance, "B:", b.Balance, "всего:", a.Balance+b.Balance)
}

A: 1000 B: 1000 всего: 2000

Тысяча переводов в обе стороны, деньги сошлись, никто не завис. Если в Transfer убрать перестановку first/second, этот же код на многоядерной машине рано или поздно зависнет.

Частая ошибка: перевод самому себе (Transfer(a, a, 1)). Оба лока — один и тот же мьютекс, второй Lock будет ждать первый вечно. Мьютексы в Go не реентерабельны (не позволяют захватить себя повторно), поэтому такой случай проверяют отдельно.

Классическая учебная иллюстрация того же — обедающие философы: пять философов за круглым столом, между соседями по одной вилке, есть можно только двумя. Если каждый возьмёт левую вилку и потянется за правой, получится цикл из пяти. Лечится тем же упорядочиванием: пронумеровать вилки, брать сначала меньшую. Тогда последний философ берёт вилки в обратном порядке, и цикл разрывается.

Способ 2. Избегание: алгоритм банкира

Избегание (avoidance) — система заранее знает, сколько ресурсов максимум понадобится каждому потоку, и перед каждой выдачей проверяет, останется ли она в безопасном состоянии: таком, из которого есть порядок, в котором все потоки смогут завершиться. Если выдача ведёт в небезопасное состояние, заявку откладывают. Это алгоритм банкира Дейкстры: банк выдаёт кредит, только если уверен, что сможет обслужить всех клиентов до конца.

В бэкенде он почти не встречается: максимальные потребности заранее неизвестны. На собеседовании его спрашивают как «третий путь» между предотвращением и обнаружением.

Способ 3. Обнаружение и восстановление: как в базах данных

Иногда дешевле позволить дедлоку случиться, а потом его найти и разорвать. Так поступают реляционные СУБД. Транзакция A обновила строку 1 и хочет строку 2, транзакция B обновила строку 2 и хочет строку 1:

   T1 держит row(1), ждёт row(2)
   T2 держит row(2), ждёт row(1)
   граф ожидания: T1 → T2 → T1   (цикл)
 
   база выбирает жертву, откатывает её транзакцию,
   локи жертвы освобождаются, вторая транзакция продолжает

Как это выглядит в конкретных базах:

• PostgreSQL не ищет циклы постоянно. Транзакция, которая прождала лок дольше deadlock_timeout (по умолчанию 1 с), запускает проверку графа. Найдя цикл, база отменяет одну из транзакций (документация предупреждает, что какую именно — предсказать трудно; обычно ту, что проверку и запустила). Клиент получает ERROR: deadlock detected с кодом SQLSTATE 40P01.
• MySQL/InnoDB проверяет граф сразу при постановке в ожидание и откатывает «меньшую» транзакцию — ту, что изменила меньше строк. Ошибка 1213: Deadlock found when trying to get lock; try restarting transaction.

С точки зрения ОС база добавляет вытеснение, которого не хватало: отнимает локи у жертвы силой. Для приложения из этого два вывода. Код, работающий с базой, должен уметь повторить транзакцию при ошибке дедлока (в Go с pgx — проверить pgErr.Code == "40P01" и повторить с небольшой случайной паузой). И даже при наличии детектора лучше не создавать дедлоки: обновлять строки в одном порядке (... WHERE id IN (...) ORDER BY id FOR UPDATE), держать транзакции короткими.

Livelock: все заняты, никто не продвигается

Livelock — потоки не спят, они активно что-то делают, но прогресса нет. Два человека в коридоре одновременно шагают влево, чтобы уступить, потом одновременно вправо, и так до бесконечности.

   П1: lock(A) ok, TryLock(B) неудача → unlock(A), повторить
   П2: lock(B) ok, TryLock(A) неудача → unlock(B), повторить
   ... и оба синхронно повторяют это снова и снова

Внешне дедлок и livelock различаются нагрузкой. Дедлок висит тихо: потоки спят, CPU свободен. Livelock висит шумно: CPU занят на 100%, а работа не идёт. Лечится случайной паузой перед повтором (randomized backoff): участники рассинхронизируются, и кто-то один проскакивает. Тот же приём используют сетевые протоколы и ретраи HTTP-клиентов (backoff с jitter).

Сводка подходов

Частые ошибки

• Считать, что рантайм Go поймает любую взаимоблокировку. Он ловит только случай, когда спят все горутины.
• Брать локи в порядке аргументов функции (from, to), а не в глобальном порядке.
• Забывать о переводе самому себе: два Lock одного мьютекса в Go — гарантированное зависание.
• Не повторять транзакцию при ошибке 40P01 в PostgreSQL или 1213 в MySQL.
• Повторять TryLock без случайной паузы — получается livelock.

Проверьте себя

1. Почему условия Коффмана называют необходимыми, но не достаточными?
2. Чем отличается картина в top при дедлоке и при livelock?
3. Что делает PostgreSQL, обнаружив цикл ожидания, и что должно сделать приложение?
4. Три горутины переводят деньги по кругу: A → B, B → C, C → A, каждая берёт сначала лок отправителя. Нарисуйте граф ожидания для худшего переплетения. Почему Transfer из главы, с упорядочиванием по ID, такой цикл не допускает при любом числе счетов?

Что спрашивают на собесе

• Назовите условия Коффмана и какое проще всего сломать. Взаимное исключение, удержание и ожидание, отсутствие вытеснения, круговое ожидание. Они необходимы для дедлока. Проще всего сломать круговое ожидание единым порядком захвата локов.
• Как получить дедлок на двух мьютексах? Два потока берут локи в противоположном порядке; при неудачном переплетении каждый держит первый и ждёт второй.
• Чем дедлок отличается от livelock? Дедлок: потоки спят, CPU свободен. Livelock: потоки активны, CPU занят, прогресса нет. Livelock лечат случайным backoff.
• Как СУБД борется с дедлоками? Граф ожидания, поиск цикла, откат жертвы. Приложение повторяет транзакцию; профилактика — единый порядок обновления строк и короткие транзакции.
• Как найти дедлок в Go-сервисе? Встроенный детектор ловит только случай, когда спят все горутины. В сервисе — дамп горутин (SIGQUIT или pprof) и поиск взаимно ждущих на Mutex.Lock.
• Минусы TryLock-подхода? Лишние откаты и риск livelock.