Проблема обедающих философов

Проблема обедающих философов — классическая задача синхронизации в информатике, иллюстрирующая сложности, возникающие при распределении общих ресурсов между несколькими параллельно выполняющимися процессами. Задача была сформулирована Эдсгером Дейкстрой в 1965 году как учебный пример взаимоблокировки (deadlock) и голодания (starvation) в многопоточных системах.

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

Формулировка задачи предполагает наличие пяти философов, сидящих за круглым столом. Перед каждым философом стоит тарелка со спагетти. Между каждой парой соседних тарелок лежит одна вилка. Таким образом, всего имеется пять вилок. Каждый философ попеременно либо обедает, либо размышляет. Для того чтобы поесть, философу необходимо взять две вилки — левую и правую (то есть обе вилки, находящиеся рядом с его тарелкой). После еды философ кладёт вилки обратно на стол и возвращается к размышлениям.

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

История возникновения

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

Основные проблемы, иллюстрируемые задачей

Взаимоблокировка (Deadlock)

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

1. Все пять философов одновременно берут левую вилку.
2. Каждый философ теперь держит одну вилку и ожидает, когда освободится правая вилка.
3. Правая вилка для каждого философа является левой вилкой для его соседа, которая также удерживается.
4. Ни один философ не может начать есть, и ни один не освободит свою вилку, так как для этого нужно закончить еду. Система оказывается в тупике.

Голодание (Starvation)

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

Состояние гонки (Race condition)

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

Решения задачи

Простейшее решение с семафорами

Наиболее прямолинейное решение предполагает использование бинарного семафора (мьютекса) для каждой вилки. Каждая вилка представлена отдельным семафором, инициализированным значением 1. Философ пытается захватить левый семафор, затем правый, ест, после чего освобождает оба. Это решение, однако, не предотвращает взаимоблокировку.

Решение с ограничением числа одновременно обедающих

Один из способов избежать взаимоблокировки — ограничить количество философов, которые могут одновременно пытаться взять вилки. Если за столом четыре философа вместо пяти, то по крайней мере один из них всегда сможет получить обе вилки. На практике это реализуется с помощью семафора, разрешающего не более четырём философам одновременно входить в «комнату» для еды.

Решение с использованием семафора-распорядителя

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

Решение с асимметричным захватом вилок

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

Решение с использованием монитора Хоара

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

Решение с использованием алгоритма Дейкстры

Эдсгер Дейкстра предложил решение, использующее массив семафоров и дополнительный семафор для взаимного исключения. Каждый философ представлен своим семафором. Перед попыткой взять вилки философ проверяет, могут ли оба его соседа есть. Если да, он начинает есть; если нет, он блокируется на своём семафоре. Это решение гарантирует отсутствие взаимоблокировки и голодания.

Применение в реальных системах

Хотя задача обедающих философов является учебной, она моделирует реальные проблемы, возникающие в операционных системах, базах данных и распределённых вычислениях:

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

Критика и альтернативные подходы

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

Альтернативные подходы к решению проблемы включают использование алгоритмов обнаружения взаимоблокировок (например, алгоритм банкира) и алгоритмов разрешения взаимоблокировок (например, принудительное завершение одного из процессов).

Интересные факты

• Задача обедающих философов часто используется на собеседованиях для проверки понимания принципов параллельного программирования.
• В оригинальной формулировке Дейкстры философы ели спагетти, а не рис или другую еду, что было связано с тем, что спагетти — это блюдо, которое удобно есть двумя вилками.
• Существует множество вариаций задачи, включая «обедающих философов с ножом и вилкой», «курящих философов» и «философов, играющих в карты».

Источники

• Дейкстра Э. W. «Co-operating sequential processes» (1965)
• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание)
• Сильбершац А., Гэлвин П., Гэгн Г. «Основы операционных систем»
• Хоар Ч. А. R. «Monitors: An Operating System Structuring Concept» (1974)
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»