Почему всё останавливается, когда каждый ждёт другого: Теория взаимных блокировок (Deadlock), графы распределения ресурсов, алгоритм банкира и Livelock

1. Введение: Задача об обедающих философах и четыре условия Коффмана (1971)

В 1965 году нидерландский информатик Эдсгер В. Дейкстра (Edsger W. Dijkstra) сформулировал знаменитую «задачу об обедающих философах» (Dining Philosophers Problem): пять философов \(P_0 \dots P_4\) сидят за круглым столом; между каждыми двумя тарелками спагетти лежит одна вилка (\(F_0 \dots F_4\)). Чтобы есть, каждому философу нужно одновременно держать левую вилку \(F_i\) и правую вилку \(F_{(i+1)\bmod 5}\). Если все пятеро проголодаются в одну и ту же микросекунду и одновременно возьмут левую вилку \(F_i\), каждый будет вечно ждать, пока сосед справа положит вторую вилку — вся система навсегда замрёт. Это явление называется взаимной блокировкой или тупиком (Deadlock).

Формально непустое подмножество процессов \(D \subseteq \mathcal{P}\) находится в состоянии дедлока тогда и только тогда, когда каждый процесс \(P_i \in D\) заблокирован в ожидании события (освобождения ресурса), которое может быть вызвано только другим процессом \(P_j \in D\) из того же самого множества ожидания.

В 1971 году Эдвард Коффман (Edward G. Coffman Jr.), М. Элфик и А. Шошани доказали, что ресурсный тупик возможен лишь при одновременном выполнении четырёх необходимых условий:

Взаимное исключение (Mutual Exclusion): Хотя бы один ресурс удерживается в монопольном (неразделяемом) режиме.
Удержание и ожидание (Hold and Wait): Процесс уже удерживает минимум один ресурс и одновременно блокируется, запрашивая дополнительные ресурсы, занятые другими процессами.
Отсутствие вытеснения (No Preemption): Выделенные ресурсы нельзя принудительно отобрать у процесса; он освобождает их только добровольно.
Циклическое ожидание (Circular Wait): Существует замкнутая цепь процессов \(\{P_0, P_1, \dots, P_{k-1}\}\), где каждый \(P_i\) ждёт ресурс, удерживаемый \(P_{(i+1)\bmod k}\).

Поскольку все четыре условия необходимы, логическое отрицание хотя бы одного из них делает дедлок математически невозможным (\(0\,\%\)).

2. Граф распределения ресурсов (RAG) и теоремы о циклах (Holt, 1972)

В 1972 году Ричард Холт представил состояние ресурсов в виде двудольного ориентированного графа распределения ресурсов (RAG) \(G = (V, E)\), где \(V = \mathcal{P} \cup \mathcal{R}\) (вершины процессов \(P_i\) и типов ресурсов \(R_j\) с \(W_j \ge 1\) идентичными экземплярами), а дуги делятся на дуги запросов \(P_i \to R_j\) и дуги назначений \(R_j \to P_i\).

Связь между ориентированными циклами в \(G\) и тупиками определяют три теоремы:

Теорема 1 (Ацикличность \(\implies\) Отсутствие тупика): Если в \(G\) нет ориентированных циклов (граф является DAG), ни один процесс не находится в тупике.
Теорема 2 (Критерий для единичных экземпляров): Если каждый ресурс имеет ровно один экземпляр (\(\forall j, W_j = 1\)), то ориентированный цикл в \(G \iff\) тупик (необходимое и достаточное условие).
Теорема 3 (Недостаточность цикла при кратных экземплярах): Если хотя бы один ресурс имеет несколько экземпляров (\(\exists j, W_j > 1\)), наличие цикла является необходимым, но НЕ достаточным условием тупика!

  flowchart TD
    subgraph RAG_Single["Случай А: Одноэкземплярный RAG (Цикл <==> Гарантированный тупик)"]
        PA1(("P1 (Блок)")) -->|"Запрос"| RA1["R1 (1 экз.: ●)"]
        RA1 -->|"Выдан"| PA2(("P2 (Блок)"))
        PA2 -->|"Запрос"| RA2["R2 (1 экз.: ●)"]
        RA2 -->|"Выдан"| PA1
    end

    subgraph RAG_Multi["Случай Б: Многоэкземплярный RAG (Цикл P1->R1->P3->R2->P1 есть, но тупика НЕТ!)"]
        PB1(("P1 (Блок)")) -->|"Запрос"| RB1["R1 (2 экз.: ●●)"]
        RB1 -->|"Экз. #1"| PB3(("P3 (Блок)"))
        PB3 -->|"Запрос"| RB2["R2 (2 экз.: ●●)"]
        RB2 -->|"Экз. #1"| PB1
        RB1 -->|"Экз. #2"| PB2(("P2 (РАБОТАЕТ: Нет запросов!)"))
        RB2 -->|"Экз. #2"| PB4(("P4 (РАБОТАЕТ: Нет запросов!)"))
    end

В Случае Б есть цикл \(P_1 \to R_1 \to P_3 \to R_2 \to P_1\), но процессы \(P_2\) и \(P_4\) имеют полустепень исхода \(0\) (активные стоки): завершив работу и вернув свои экземпляры \(R_1\) и \(R_2\), они разрушат цикл!

3. Стратегия 1 (Предотвращение): Доказательство полного упорядочения блокировок

В ядрах ОС (валидатор lockdep в Linux) и многопоточном коде условие 4 (циклическое ожидание) устраняется полным упорядочением блокировок (Total Lock Ordering): каждому мьютексу \(L \in \mathcal{L}\) присваивается уникальный ранг \(\phi(L) \in \mathbb{N}\), и поток, удерживающий множество \(\mathcal{H}\), имеет право запрашивать новый замок \(L_{\text{new}}\) только со строго большим рангом:

\[\forall L_{\text{held}} \in \mathcal{H}: \quad \phi(L_{\text{held}}) < \phi(L_{\text{new}})\]

【Доказательство от противного】: Допустим, возник цикл ожидания \(\{P_0, P_1, \dots, P_{k-1}\}\) (\(k \ge 2\)), где \(P_i\) удерживает \(L_i\) и ждёт \(L_{(i+1)\bmod k}\). Поскольку все потоки соблюдают правило строгого возрастания \(\phi\), вдоль цикла получаем:

\[\phi(L_0) < \phi(L_1) < \phi(L_2) < \cdots < \phi(L_{k-1}) < \phi(L_0) \implies \phi(L_0) < \phi(L_0)\]

Ни одно число не может быть строго меньше самого себя — противоречие (\(\bot\))! Будь то банковский перевод (всегда блокировать сначала счёт с меньшим ID) или обедающие философы (\(P_4\) берёт сначала правую вилку \(F_0\), а затем левую \(F_4\), так как \(0 < 4\)), циклическое ожидание становится невозможным. \(\blacksquare\)

4. Стратегия 2 (Избежание): Алгоритм банкира Дейкстры (Трассировка 5×3)

Когда порядок захвата динамичен, алгоритм банкира Дейкстры (1965 / Habermann, 1969) требует заранее заявить максимальную потребность \(\mathbf{Max}\) и перед каждой выдачей за время \(O(m \cdot n^2)\) проверяет, остаётся ли состояние безопасным (Safe State) с хотя бы одной безопасной последовательностью (Safe Sequence) (\(\text{Тупик} \subsetneq \text{Небезопасное состояние}\)).

Для \(n=5\) процессов \(\{P_0 \dots P_4\}\) и \(m=3\) ресурсов с \(\mathbf{Total} = (A=10, B=5, C=7)\) при сумме выданных \((7,2,5)\) начальный свободный вектор равен \(\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}\):

Процесс	Выдано \(\mathbf{Allocation}\) \((A,B,C)\)	Макс. \(\mathbf{Max}\) \((A,B,C)\)	Остаток \(\mathbf{Need} = \mathbf{Max} - \mathbf{Allocation}\)	Поиск безопасной последовательности (\(\mathbf{Work}_0 = (3,3,2)\))
\(P_0\)	\((0, 1, 0)\)	\((7, 5, 3)\)	\((7, 4, 3)\)	Шаг 4 выполнен: \((7,4,3) \le (7,4,5) \to \mathbf{Work}=(7,5,5)\)
\(P_1\)	\((2, 0, 0)\)	\((3, 2, 2)\)	\((1, 2, 2)\)	Шаг 1 выполнен: \((1,2,2) \le (3,3,2) \to \mathbf{Work}=(5,3,2)\)
\(P_2\)	\((3, 0, 2)\)	\((9, 0, 2)\)	\((6, 0, 0)\)	Шаг 5 выполнен: \((6,0,0) \le (7,5,5) \to \mathbf{Work}=(10,5,7)\)
\(P_3\)	\((2, 1, 1)\)	\((2, 2, 2)\)	\((0, 1, 1)\)	Шаг 2 выполнен: \((0,1,1) \le (5,3,2) \to \mathbf{Work}=(7,4,3)\)
\(P_4\)	\((0, 0, 2)\)	\((4, 3, 3)\)	\((4, 3, 1)\)	Шаг 3 выполнен: \((4,3,1) \le (7,4,3) \to \mathbf{Work}=(7,4,5)\)

Безопасная последовательность \(\langle P_1, P_3, P_4, P_0, P_2 \rangle\) доказывает безопасность \(t_0\). Если \(P_1\) запросит \((1,0,2)\), пробная выдача оставит \(\mathbf{Available}=(2,3,0) \ge \mathbf{Need}_1=(0,2,0)\) (одобрено мгновенно). Но если следом \(P_0\) запросит \((0,2,0)\), остаток упадёт до \((2,1,0)\), чего не хватит ни одному процессу (небезопасное состояние): банкир отклонит запрос и заблокирует \(P_0\)!

5. Стратегии 3 и 4 (WFG, Wait-Die/Wound-Wait, Страус) и Livelock против голодания

Реляционные СУБД (PostgreSQL, MySQL InnoDB) строят граф ожидания (Wait-For Graph, WFG) и ищут циклы обходом в глубину (DFS) за \(O(|V|+|E|)\), откатывая (rollback) транзакцию-жертву с наименьшим Undo-логом (MySQL проверяет мгновенно; PostgreSQL — через deadlock_timeout = 1s). Распределённые СУБД (Google Spanner) используют протоколы с временными метками \(\text{TS}(T_i)\) Розенкранца и др. (1978): Wait-Die (невытесняющий) и Wound-Wait (вытесняющий, меньше холостых перезапусков), обязательно сохраняя исходную метку \(\text{TS}(T_i)\) при перезапуске для защиты от голодания. Для редчайших переполнений системных таблиц ОС общего назначения применяют алгоритм страуса (Ostrich Algorithm), игнорируя проблему ради отсутствия ежедневных накладных расходов.

  flowchart TD
    Req["Распределённая транзакция Ti запрашивает замок, удерживаемый Tj"] --> Cmp{"Сравнение меток времени: TS(Ti) < TS(Tj) ?<br/>(Запрашивающая Ti СТАРШЕ удерживающей Tj?)"}
    Cmp -->|"Да: Ti СТАРШЕ (Older)"| WD1["[Wait-Die (невытесняющий)]: Старшая Ti ЖДЁТ младшую Tj (Старший -> Младший)<br/>[Wound-Wait (вытесняющий)]: Старшая Ti РАНИТ (откатывает) Tj и забирает замок!"]
    Cmp -->|"Нет: Ti МЛАДШЕ (Younger)"| WD2["[Wait-Die (невытесняющий)]: Младшая Ti УМИРАЕТ (откат и повтор со старым TS)<br/>[Wound-Wait (вытесняющий)]: Младшая Ti ТЕРПЕЛИВО ЖДЁТ старшую Tj (Младший -> Старший)"]

Наконец, сравним три вида отказов живучести (Liveness):

Критерий диагностики	Взаимная блокировка (Deadlock)	Активный тупик (Livelock)	Голодание (Starvation)
Механизм	Циклическое ожидание спящих потоков, удерживающих ресурсы	Симметричные циклы `trylock` и немедленного освобождения без продвижения («танец вежливости» в коридоре)	Система в целом работает, но низкоприоритетный поток вечно обходят в очереди
Статус ОС и загрузка CPU	`SLEEPING` / `BLOCKED` (\(0\,\%\) CPU)	`RUNNING` (\(\approx 100\,\%\) CPU вхолостую при нулевом прогрессе!)	Ожидание в очереди (\(0\,\%\) CPU у жертвы)
Инженерное решение	Полный порядок (\(\phi(L_1)<\phi(L_2)\)), алгоритм банкира, откат по WFG	Случайная экспоненциальная задержка с джиттером (Random Exponential Backoff + Jitter)	Старение приоритета (Aging), сохранение TS, честные FIFO-замки (MCS lock)