--- title: "Взаимоблокировки: теория и борьба" description: "Узкий мост на одну машину. С двух сторон одновременно въезжают две машины и встречаются посередине. Каждой нужно, чтобы другая сдала назад, и ни одна не сдаёт. Стоять так они…" canonical: https://graphlms.ru/os/book/deadlock course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Взаимоблокировки: теория и борьба > Источник: https://graphlms.ru/os/book/deadlock — курс «Операционные системы», GraphLMS. ## Что такое взаимоблокировка Узкий мост на одну машину. С двух сторон одновременно въезжают две машины и встречаются посередине. Каждой нужно, чтобы другая сдала назад, и ни одна не сдаёт. Стоять так они будут вечно. **Взаимоблокировка** (deadlock, дедлок) — ситуация, когда несколько потоков навсегда застряли, потому что каждый ждёт ресурс, который держит другой из этой же группы. Ресурсом может быть мьютекс, [семафор](/os/book/semaphores), строка в таблице базы, файл с блокировкой — всё, что захватывается монопольно. От обычного ожидания дедлок отличается тем, что отпустить ресурс некому: все участники стоят и ждут друг друга. Долгое ожидание лока, который держит занятый, но работающий поток, — не дедлок, это рано или поздно пройдёт. ## Классика: два лока в разном порядке Самый частый дедлок в реальном коде — два лока, которые разные потоки берут в разном порядке. Перевод денег: поток 1 переводит с A на B и блокирует сначала A, потом B. Поток 2 переводит с B на A и блокирует сначала B, потом A. ```text Поток 1 (A → B) Поток 2 (B → A) ──────────────────── ──────────────────── lock(A) взял lock(B) взял lock(B) занят, ждёт П2 lock(A) занят, ждёт П1 П1 держит A и ждёт B; П2 держит B и ждёт A. Оба ждут вечно. ``` Коварство в том, что код каждого потока выглядит правильным, и дедлок случается только при определённом переплетении: оба должны успеть взять первый лок до того, как кто-то возьмёт второй. На тестах это может не случиться ни разу, а под нагрузкой в проде — раз в неделю. Воспроизведём на Go. Чтобы не ждать удачного переплетения, заставим обе горутины взять первый лок прежде, чем кто-то возьмёт второй: ```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() } ``` ```text горутина 2 держит B, хочет A горутина 1 держит A, хочет B fatal error: all goroutines are asleep - deadlock! goroutine 1 [sync.WaitGroup.Wait]: ... ``` Рантайм Go заметил, что не осталось ни одной горутины, которая может продолжить работу, и аварийно завершил программу. Не рассчитывайте на это в сервисе: детектор срабатывает, только если заблокированы абсолютно все горутины. В HTTP-сервере всегда есть горутины, которые ждут сеть или таймеры, поэтому два зависших обработчика рантайм не заметит, просто запросы начнут висеть. Найти их помогает дамп всех горутин: `kill -QUIT ` (рантайм напечатает стеки и завершится) или `/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». ```text Нет цикла: Цикл: П1 ──→ П2 П1 ──→ П2 │ ▲ │ ▼ │ ▼ П3 П4 ←── П3 П3 никого не ждёт, доработает, П1→П2→П3→П4→П1, выхода нет отпустит ресурс, за ним П2, П1 ``` Если каждый ресурс существует в одном экземпляре (как мьютекс), правило простое: дедлок есть тогда и только тогда, когда в графе ожидания есть цикл. Поиском цикла в таком графе и занимаются детекторы дедлоков в базах данных. Детектор на Go вы напишете в задаче [«Детект дедлока: цикл в графе ожидания»](/os/tasks/deadlock-detect). ## Способ 1. Предотвращение: сломать одно условие Самый практичный подход — устроить код так, чтобы дедлок был невозможен. | Условие | Как сломать | Цена | |---|---|---| | Круговое ожидание | брать локи в одном глобальном порядке | дисциплина по всему коду | | Удержание и ожидание | брать все нужные локи разом или не держать ничего, пока ждёшь | меньше параллелизма, надо знать все локи заранее | | Отсутствие вытеснения | `TryLock`: не вышло — отпустить всё и начать заново | возможен livelock (ниже) | | Взаимное исключение | lock-free структуры на CAS | сложно написать правильно | Про `TryLock` в разных источниках пишут по-разному, и это нормально. Поток, который при неудаче сам отпускает всё взятое, не держит ресурсы во время ожидания (ломается hold and wait). В OSTEP этот же приём описан как обход отсутствия вытеснения: поток как бы вытесняет сам себя. Смысл один. Главный приём — **упорядочивание локов** (lock ordering). Договариваемся, что локи всегда берутся в одном порядке, например по возрастанию ID счёта. Тогда перевод A → B и перевод B → A оба берут сначала A, потом B. Кто первым взял A, тот и пройдёт; второй ждёт на A, ничего не держа, и цикла не получится. ```go play 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) } ``` ```text A: 1000 B: 1000 всего: 2000 ``` Тысяча переводов в обе стороны, деньги сошлись, никто не завис. Если в `Transfer` убрать перестановку `first`/`second`, этот же код на многоядерной машине рано или поздно зависнет. Частая ошибка: перевод самому себе (`Transfer(a, a, 1)`). Оба лока — один и тот же мьютекс, второй `Lock` будет ждать первый вечно. Мьютексы в Go не реентерабельны (не позволяют захватить себя повторно), поэтому такой случай проверяют отдельно. Классическая учебная иллюстрация того же — **обедающие философы**: пять философов за круглым столом, между соседями по одной вилке, есть можно только двумя. Если каждый возьмёт левую вилку и потянется за правой, получится цикл из пяти. Лечится тем же упорядочиванием: пронумеровать вилки, брать сначала меньшую. Тогда последний философ берёт вилки в обратном порядке, и цикл разрывается. ## Способ 2. Избегание: алгоритм банкира **Избегание** (avoidance) — система заранее знает, сколько ресурсов максимум понадобится каждому потоку, и перед каждой выдачей проверяет, останется ли она в **безопасном состоянии**: таком, из которого есть порядок, в котором все потоки смогут завершиться. Если выдача ведёт в небезопасное состояние, заявку откладывают. Это **алгоритм банкира** Дейкстры: банк выдаёт кредит, только если уверен, что сможет обслужить всех клиентов до конца. В бэкенде он почти не встречается: максимальные потребности заранее неизвестны. На собеседовании его спрашивают как «третий путь» между предотвращением и обнаружением. ## Способ 3. Обнаружение и восстановление: как в базах данных Иногда дешевле позволить дедлоку случиться, а потом его найти и разорвать. Так поступают реляционные СУБД. Транзакция A обновила строку 1 и хочет строку 2, транзакция B обновила строку 2 и хочет строку 1: ```text 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** — потоки не спят, они активно что-то делают, но прогресса нет. Два человека в коридоре одновременно шагают влево, чтобы уступить, потом одновременно вправо, и так до бесконечности. ```text П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). ## Сводка подходов | Подход | Идея | Где применяют | |---|---|---| | Предотвращение | сломать одно из условий, чаще всего порядком локов | прикладной код, ядро ОС | | Избегание | выдавать ресурс, только если состояние останется безопасным | редко, нужны максимумы заранее | | Обнаружение и восстановление | найти цикл, откатить жертву | СУБД, распределённые блокировки | | Игнорирование | дедлоки редки, при зависании перезапустить | так поступают большинство ОС с пользовательскими процессами | > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/deadlock ## Частые ошибки - Считать, что рантайм 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, такой цикл не допускает при любом числе счетов? Ответы. (1) При дедлоке все четыре выполнены, но их выполнение ещё не означает, что дедлок случится: нужно неудачное переплетение. (2) При дедлоке потоки спят, CPU свободен; при livelock CPU занят, а прогресса нет. (3) Отменяет одну из транзакций с ошибкой `deadlock detected` (40P01); приложение повторяет транзакцию. (4) Г1 держит A и ждёт B (у Г2), Г2 держит B и ждёт C (у Г3), Г3 держит C и ждёт A (у Г1) — цикл. С упорядочиванием каждая горутина, держа лок, ждёт только лок с большим ID. Вдоль цикла ID должны были бы строго расти и вернуться к началу, что невозможно. ## Что спрашивают на собесе - **Назовите условия Коффмана и какое проще всего сломать.** Взаимное исключение, удержание и ожидание, отсутствие вытеснения, круговое ожидание. Они необходимы для дедлока. Проще всего сломать круговое ожидание единым порядком захвата локов. - **Как получить дедлок на двух мьютексах?** Два потока берут локи в противоположном порядке; при неудачном переплетении каждый держит первый и ждёт второй. - **Чем дедлок отличается от livelock?** Дедлок: потоки спят, CPU свободен. Livelock: потоки активны, CPU занят, прогресса нет. Livelock лечат случайным backoff. - **Как СУБД борется с дедлоками?** Граф ожидания, поиск цикла, откат жертвы. Приложение повторяет транзакцию; профилактика — единый порядок обновления строк и короткие транзакции. - **Как найти дедлок в Go-сервисе?** Встроенный детектор ловит только случай, когда спят все горутины. В сервисе — дамп горутин (SIGQUIT или pprof) и поиск взаимно ждущих на `Mutex.Lock`. - **Минусы `TryLock`-подхода?** Лишние откаты и риск livelock. ## Вопросы для самопроверки **Квиз «Дедлоки»** 1. Сколько условий Коффмана должны выполняться одновременно, чтобы дедлок стал возможен? - Ответ: 4 - Пояснение: Mutual exclusion, hold and wait, no preemption, circular wait — нужны все 4 сразу. Сломав любое одно, мы делаем дедлок невозможным. 2. Какой приём чаще всего применяют для предотвращения дедлока на нескольких локах? - Lock ordering — всегда захватывать локи в одном глобальном порядке (верно) - Использовать как можно больше мьютексов - Увеличить таймаут ожидания лока - Брать каждый лок в отдельной горутине - Пояснение: Единый глобальный порядок захвата ломает условие circular wait: потоки идут 'в одну сторону', кольцо образоваться не может. 3. Чем livelock отличается от дедлока? - Ничем, это синонимы - Livelock — это когда поток упал с паникой - Livelock бывает только в БД - При дедлоке потоки спят/ждут, при livelock активно работают, но не прогрессируют (верно) - Пояснение: Дедлок 'висит тихо' (CPU простаивает, потоки ждут). Livelock 'висит шумно': потоки крутятся, уступают друг другу, жгут CPU, но прогресса нет. 4. Как наличие дедлока выражается в графе ожидания (wait-for graph)? - Граф теряет все рёбра - Граф становится деревом - В графе появляется цикл (верно) - Граф становится двудольным - Пояснение: Ребро 'П1 → П2' значит 'П1 ждёт ресурс, который держит П2'. Дедлок ⇔ в графе есть цикл (кольцо ожидания). 5. Что делает СУБД, обнаружив дедлок между транзакциями? - Выбирает жертву и откатывает её транзакцию, разрывая цикл (верно) - Зависает и ждёт администратора - Перезагружает сервер - Удаляет обе транзакции навсегда - Пояснение: База находит цикл в wait-for графе, выбирает жертву (обычно ту, что сделала меньше работы), делает ROLLBACK, освобождая локи. Приложение получает ошибку и повторяет транзакцию. 6. Какие условия Коффмана ломает стратегия trylock ('не получилось взять второй лок — отпусти всё и повтори')? - Hold and wait (удержание и ожидание) (верно) - Mutual exclusion (взаимное исключение) - Circular wait: порядок захвата при этом фиксируется - No preemption: отпуская взятый лок, поток добровольно отдаёт ресурс (верно) - Пояснение: Trylock убирает hold and wait: если второй лок взять не удалось, поток отпускает первый и не держит его, пока ждёт. По сути это и добровольное «вытеснение» (no preemption). Взаимное исключение остаётся: локи по-прежнему эксклюзивны. Порядок захвата trylock не задаёт. Цена приёма: два потока могут бесконечно уступать друг другу, это livelock.