Задача об обедающих философах

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

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

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

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

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

Задача была предложена Эдсгером Дейкстрой в 1965 году во время его работы в компании Burroughs Corporation. Первоначально она была сформулирована как проблема синхронизации для операционной системы THE (Technische Hogeschool Eindhoven). Дейкстра использовал метафору философов, чтобы наглядно продемонстрировать, как несколько процессов могут конкурировать за ограниченные ресурсы, и какие последствия это может иметь.

В 1971 году задача была популяризирована в книге «Операционные системы» (Operating Systems) под редакцией Энтони Хоара, где она получила название «обедающие философы». С тех пор она стала стандартным примером в учебных курсах по операционным системам, параллельному программированию и распределённым вычислениям.

Классификация проблем

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

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

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

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

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

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

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

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

Решение с семафорами

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

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

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

Решение с иерархией ресурсов (нумерация вилок)

В этом решении каждой вилке присваивается уникальный номер, и философы обязаны брать вилки в порядке возрастания номеров. Например, философ с номером i сначала берёт вилку с меньшим номером, затем с большим. Философ 0 берёт вилку 0, затем вилку 1; философ 4 берёт вилку 0, затем вилку 4. Это разрывает цикл ожидания, так как вилка 0 всегда захватывается первой, и ни один философ не может удерживать вилку с большим номером, ожидая вилку с меньшим.

Решение с мониторами

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

Решение с помощью алгоритма Дейкстры (использование состояния философа)

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

Применение в информатике

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

• Конкуренцию за общие ресурсы (например, доступ к файлам, принтерам, сетевым соединениям).
• Проблемы при работе с базами данных (блокировки транзакций, взаимные блокировки при параллельном доступе).
• Управление памятью и кэшем в многопроцессорных системах.
• Синхронизацию в распределённых системах (например, при использовании распределённых блокировок).

Критика и альтернативные формулировки

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

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

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

• Задача об обедающих философов вдохновила создание нескольких учебных симуляторов и игр, используемых в обучении параллельному программированию.
• В 2003 году задача была включена в список «великих задач информатики» по версии журнала Communications of the ACM.
• В некоторых учебных курсах задачу модифицируют, заменяя вилки на палочки для еды, что отражает культурные особенности.

Источники

• Дейкстра Э. W. «Cooperating Sequential Processes» (1965)
• Хоар Ч. А. R. «Operating Systems» (1971)
• Таненбаум Э. С. «Современные операционные системы» (4-е издание, 2015)
• Сильбершац А., Гэлвин П., Гэгн Г. «Основы операционных систем» (9-е издание, 2013)