Задача обедающих философов: дедлок и его решения

Задача обедающих философов - учебная модель, на которой Эдсгер Дейкстра в 1965 году показал, как несколько процессов, конкурирующих за общие ресурсы, способны намертво заблокировать друг друга. Пять философов сидят за круглым столом, между каждой парой лежит одна вилка, а чтобы поесть, философу нужны сразу две - левая и правая. Если все одновременно возьмут левую вилку и будут ждать правую, обед не начнётся никогда. За этой шуточной постановкой стоит настоящая инженерная проблема - взаимная блокировка (дедлок) в многопоточных системах. Ниже разберём условия её возникновения и канонические способы устранения; форма ниже соберёт точную постановку вашей задачи для разбора в чате.

Постановка задачи

Классическая формулировка такая. За круглым столом сидят пять философов. Жизнь каждого - бесконечный цикл из двух состояний: он либо размышляет, либо обедает. Между соседями лежит ровно одна вилка, всего вилок тоже пять. Чтобы поесть, философу нужны обе вилки - слева и справа от его тарелки.

Каждая вилка - общий ресурс, за который конкурируют два соседа. Философ - это поток (или процесс), вилка - разделяемый ресурс под взаимным исключением. Задача: придумать протокол поведения философов, при котором никто не останется голодным навсегда и стол не заблокируется целиком.

Наивное решение - «возьми левую вилку, потом правую, поешь, положи обе» - приводит к катастрофе. Стоит всем философам синхронно взять левую вилку, как каждый будет вечно ждать правую, которую держит сосед. Это и есть дедлок.

Рассчитать для своей задачи

Что такое дедлок

Дедлок (взаимная блокировка) - ситуация, в которой группа потоков навсегда остановлена, потому что каждый ждёт ресурс, удерживаемый другим потоком из этой же группы. Никто не двигается вперёд, и без внешнего вмешательства система из этого состояния не выйдет.

Формально состояние системы можно описать графом ожидания ресурсов: вершины - потоки и ресурсы, рёбра - отношения «удерживает» и «ждёт». Дедлок возникает тогда и только тогда, когда в этом графе появляется цикл. В задаче философов цикл очевиден: философ 1 ждёт вилку у философа 2, тот - у философа 3, и так по кругу до философа 1.

$$\text{Дедлок} \iff \exists \text{ цикл в графе ожидания}$$

Важно отличать дедлок от смежных патологий. При живоблокировке (livelock) потоки не стоят, но и не прогрессируют - бесконечно уступают друг другу. При голодании (starvation) один поток вечно проигрывает борьбу за ресурс, хотя система в целом работает. Дедлок - самый жёсткий случай: встаёт всё.

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

В 1971 году Эдвард Коффман сформулировал четыре необходимых условия дедлока. Взаимная блокировка возможна, только если выполнены все четыре одновременно - значит, чтобы её исключить, достаточно сломать любое одно.

1. Взаимное исключение (mutual exclusion): ресурс в каждый момент использует не более одного потока. Вилку нельзя делить.
2. Удержание и ожидание (hold and wait): поток, уже захвативший один ресурс, ждёт другой, не отпуская первый. Философ держит левую вилку и тянется за правой.
3. Отсутствие вытеснения (no preemption): ресурс нельзя насильно отобрать - поток сам должен его освободить. Вилку у философа не выхватить.
4. Циклическое ожидание (circular wait): существует кольцо потоков, каждый из которых ждёт ресурс, удерживаемый следующим в кольце.

Все классические решения задачи философов - это атака ровно на одно из четырёх условий. Понимание, какое именно условие ломает каждый метод, важнее, чем заучивание самого кода.

Рассчитать для своей задачи

Решение через иерархию ресурсов

Самый элегантный приём - нумерация ресурсов и захват строго в возрастающем порядке. Перенумеруем вилки от 1 до 5. Правило: философ всегда сначала берёт вилку с меньшим номером, потом с большим.

Для четырёх философов это работает как обычно, а пятый, сидящий «на стыке», между вилкой 5 и вилкой 1, по правилу возьмёт сначала вилку 1, а не 5. Тем самым он не замкнёт кольцо: всегда найдётся философ, который тянется за вилкой с меньшим номером раньше соседа, и кольцо ожидания рвётся.

Этот метод ломает условие циклического ожидания: в графе захвата по возрастанию номеров цикл невозможен в принципе. Стратегия настолько надёжна, что лежит в основе порядка захвата мьютексов во многих ядрах ОС и СУБД - везде, где блокировки берутся «по адресу» или «по идентификатору» в фиксированном порядке. Похожий приём упорядочивания состояний встречается и в динамическом программировании, где порядок обхода подзадач гарантирует корректность.

Решение через арбитра

Второй подход - ввести центрального посредника (официанта, арбитра). Прежде чем взять вилки, философ спрашивает разрешения у официанта; тот выдаёт обе вилки только если они обе свободны, иначе философ ждёт.

Поскольку решение о выдаче пары вилок принимается атомарно одним арбитром, ситуация «каждый взял по одной» становится невозможной. Это ломает условие удержания и ожидания: философ либо получает сразу оба ресурса, либо не получает ни одного.

Минус решения - официант становится узким местом. Все запросы проходят через него последовательно, и параллелизм падает: даже два философа на противоположных концах стола, которые могли бы есть одновременно, обслуживаются по очереди. На практике арбитр используется там, где простота важнее пропускной способности.

Решение через ограничение числа едоков

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

Реализуется это семафором-счётчиком с начальным значением 4. Каждый философ перед попыткой взять вилки делает $\text{wait}$ на семафоре, после еды - $\text{signal}$. Семафор гарантирует, что в зоне борьбы за вилки не окажется все пять.

$$\begin{aligned} &\text{semaphore room} = 4 \\ &\text{philosopher}(i): \\ &\quad \text{wait(room)} \\ &\quad \text{wait(fork}[i]) \\ &\quad \text{wait(fork}[(i+1) \bmod 5]) \\ &\quad \text{eat()} \\ &\quad \text{signal(fork}[i]),\ \text{signal(fork}[(i+1)\bmod 5]) \\ &\quad \text{signal(room)} \end{aligned}$$

Этот метод тоже ломает циклическое ожидание: пока за «активным» столом не более четырёх философов, замкнуть кольцо из пяти ожиданий физически некому. Решение даёт более высокий параллелизм, чем арбитр, и считается каноническим ответом на задачу.

Асимметрия как простейший трюк

Есть ещё более дешёвый приём, не требующий ни нумерации, ни семафоров: сделать поведение философов несимметричным. Пусть философы с чётными номерами берут сначала левую вилку, а с нечётными - сначала правую (или наоборот).

При такой расстановке как минимум для одной пары соседей порядок захвата совпадёт «навстречу», и кольцо одинаковых направлений ожидания не сложится. Это, по сути, частный случай иерархии ресурсов, но сформулированный через чётность, а не через глобальную нумерацию. Приём любят на собеседованиях за лаконичность.

Голодание: дедлок устранён, но не всё

Устранить дедлок мало - нужно ещё гарантировать, что ни один философ не останется голодным навсегда. Решение без дедлока всё ещё может страдать голоданием: например, два расторопных соседа могут так согласовать свои циклы, что философ между ними никогда не дождётся пары свободных вилок.

Сильное свойство, которого хотят добиться, - отсутствие голодания (freedom from starvation): каждый философ, захотевший есть, рано или поздно поест. Его обеспечивают честные (fair) очереди на ресурсы и арбитры, ведущие учёт, кто давно не ел. Простая иерархия ресурсов дедлок убирает, но честность не гарантирует автоматически - это отдельное требование к планировщику.

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

• Считать, что хватит сломать любое условие «примерно». Условий Коффмана ровно четыре, и каждое решение ломает конкретное. Размытая формулировка «добавим блокировку посильнее» обычно не ломает ни одного и дедлок не убирает.
• Путать дедлок и голодание. Решение может быть свободно от дедлока, но допускать голодание отдельного потока. Это разные свойства, доказывать их нужно отдельно.
• Захватывать вилки в произвольном порядке. Без фиксированной дисциплины захвата (иерархия, арбитр, асимметрия) кольцо ожидания возникнет рано или поздно под нагрузкой, даже если в тестах всё работало.
• Брать правую вилку, не проверив, отпущена ли левая при неудаче. Half-захват без отката («взял одну, не смог взять вторую, держу первую») - это и есть условие удержания и ожидания в чистом виде.
• Думать, что пять - магическое число. Задача обобщается на любое число философов; дедлок и его решения от конкретного N не зависят.

FAQ

Почему философов именно пять? Пять - минимальное наглядное число, при котором виден полный круг и нетривиальное кольцо ожидания. Логика решений не меняется для любого $N \ge 2$: при двух философах кольцо вырождается, при больших N картина та же, что и при пяти.

Чем дедлок отличается от гонки данных? Гонка данных (race condition) - это некорректный результат из-за неупорядоченного доступа к общим данным; программа продолжает работать, но выдаёт неверное значение. Дедлок - это остановка: программа не выдаёт вообще ничего, потоки висят. Это разные классы ошибок параллелизма.

Можно ли обнаружить дедлок, а не предотвращать? Да. Помимо предотвращения (ломать условия Коффмана заранее) существует обнаружение: периодически строить граф ожидания и искать в нём цикл, а найдя - снять один из потоков. Так работают, например, детекторы взаимоблокировок в СУБД, которые откатывают одну из транзакций.

Коротко

Задача обедающих философов - модельный пример взаимной блокировки в параллельном программировании. Дедлок возникает при одновременном выполнении четырёх условий Коффмана: взаимного исключения, удержания с ожиданием, отсутствия вытеснения и циклического ожидания. Чтобы его устранить, достаточно сломать любое одно условие. Канонические решения: иерархия ресурсов (захват вилок по возрастанию номеров рвёт цикл), центральный арбитр (выдаёт пару вилок атомарно), семафор-ограничитель Дейкстры (не более четырёх философов за столом) и асимметрия порядка захвата. Отдельно от дедлока стоит свойство отсутствия голодания - его обеспечивает честное планирование, а не сам факт устранения блокировки.