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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Проблема была сформулирована в 1965 году Эдсгером Дейкстрой как экзаменационное упражнение для студентов. В качестве примера был взят конкурирующий доступ к ленточному накопителю. Вскоре проблема была сформулирована Ричардом Хоаром в том виде, в каком она известна сегодня[1][2][3].

Постановка задачи[править | править вики-текст]

Иллюстрация проблемы обедающих философов

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

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

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

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

Проблемы[править | править вики-текст]

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

Например, можно посоветовать каждому философу выполнять следующий алгоритм:

  • Размышлять, пока не освободится левая вилка. Когда вилка освободится — взять её.
  • Размышлять, пока не освободится правая вилка. Когда вилка освободится — взять её.
  • Есть
  • Положить левую вилку
  • Положить правую вилку
  • Повторить алгоритм сначала

Это решение задачи некорректно: оно позволяет системе достичь состояния взаимной блокировки, когда каждый философ взял вилку слева и ждёт, когда вилка справа освободится.[4]

Проблема ресурсного голодания (англ. resource starvation) может возникать независимо от взаимной блокировки, если один из философов не может завладеть левой и правой вилкой из-за проблем синхронизации. Например, может быть предложено правило, согласно которому философы должны класть вилку обратно на стол после пятиминутного ожидания доступности другой вилки, и ждать ещё пять минут перед следующей попыткой завладеть вилками. Эта схема устраняет возможность блокировки (так как система всегда может перейти в другое состояние), но по-прежнему существует возможность «зацикливания» системы (англ. livelock), при котором состояние системы меняется, но она не совершает никакой полезной работы. Например, если все пять философов появятся в столовой одновременно и каждый возьмёт левую вилку в одно и то же время, то философы будут ждать пять минут в надежде завладеть правой вилкой, потом положат левую вилку и будут ждать ещё пять минут прежде, чем попытаться завладеть вилками снова.

Взаимное исключение (англ. mutual exclusion) является основной идеей «Проблемы обедающих философов». Эта проблема представляет собой общий, абстрактный сценарий, позволяющий объяснить проблемы этого типа. Ошибки философов наглядно демонстрируют те трудности, которые возникают в реальном программировании, когда нескольким программам требуется исключительный доступ к разделяемым ресурсам. Эти вопросы изучаются в области параллельных вычислений.

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

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

Решение задачи[править | править вики-текст]

Официант[править | править вики-текст]

Относительно простое решение задачи достигается путём добавления официанта возле стола. Философы должны дожидаться разрешения официанта перед тем, как взять вилку. Поскольку официант знает, сколько вилок используется в данный момент, он может принимать решения относительно распределения вилок и тем самым предотвратить взаимную блокировку философов. Если четыре вилки из пяти уже используются, то следующий философ, запросивший вилку, вынужден будет ждать разрешения официанта — которое не будет получено, пока вилка не будет освобождена. Предполагается, что философ всегда пытается сначала взять левую вилку, а потом — правую (или наоборот), что упрощает логику. Официант работает, как семафор — понятие, введённое Дейкстрой в 1965 году.[5]

Чтобы показать, как это решение работает, предположим, что философы обозначены от А до Д по часовой стрелке. Если философы А и В едят, то заняты четыре вилки. Философ Б сидит между А и В, так что ему недоступна ни одна из вилок. В то же время, философы Г и Д имеют доступ к одной неиспользуемой вилке между ними. Предположим, что философ Г хочет есть. Если он тут же берёт свободную вилку, то становится возможна взаимная блокировка философов. Если вместо этого он спрашивает разрешения у официанта, то тот просит его подождать — и можно быть уверенным в том, что как только пара вилок освободится, то по крайней мере один философ сможет взять две вилки. Таким образом, взаимная блокировка становится невозможной.

Иерархия ресурсов[править | править вики-текст]

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

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

Данное решение было предложено Дейкстрой.

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

Решение на основе монитора[править | править вики-текст]

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

В отсутствии блокировок, связанных с вилками, философы должны обеспечивать то, что начало принятия пищи не основывается на старой информации о состоянии соседей. Например: Если философ B видит, что A не ест в данный момент времени, а потом поворачивается и смотрит на C, A мог начать есть, пока философ B смотрит на C. Используя одну взаимоисключающую блокировку, можно избежать этой проблемы. Эта блокировка не связана с вилками, но она связана с решением процедур, которые могут изменить состояние философов. Это обеспечивается монитором.

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

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

По окончании текущего приёма пищи философ оповещает монитора о том, что обе вилки свободны.

Стоит заметить, что этот алгоритм монитора не решает проблемы голодания. Например, философ B может бесконечно ждать своей очереди, если у философов A и C периоды приёма пищи всё время пересекаются. Чтобы гарантировать также, что ни один философ не будет голодать, можно отслеживать, сколько раз голодный философ не ел, когда его соседи положили вилки на стол. Если количество раз превысит некий предел, такой философ перейдёт в состояние Голодания и алгоритм монитора форсирует процедуру завладения вилками, выполняя условие недопущения голодания ни одного из соседей.

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

Проблема перекура[править | править вики-текст]

Еще одна из возможных проблем - одновременное обращение к вилкам. Если потоки будут выполняться одновременно, то 2 философа могут взять одну и ту же вилку.

На практике вероятность возникновения проблемы минимальна. Чтобы ее продемонстрировать, добавляется задержка между проверкой возможности взять вилку и ее взятием (перекур). Так как пока один философ курит, другой понимает, что может взять вилку и тоже начинает курить. После перекура они оба берут одну вилку (второму придется есть руками).

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 E.W. Dijkstra. EWD-1000 (англ.). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. Архивировано из первоисточника 15 сентября 2012.
  2. Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. — Birkhäuser, 1981. — P. [1], [2]. — ISBN 9783540106999.
  3. Hoare, C. A. R. Communicating Sequential Processes (англ.). [3] (originally published in 1985 by Prentice Hall International) (2004). Архивировано из первоисточника 15 сентября 2012.
  4. E.W. Dijkstra. EWD-310 (англ.). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.. Архивировано из первоисточника 15 сентября 2012.
  5. E.W. Dijkstra. EWD-123 (англ.). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.. Архивировано из первоисточника 15 сентября 2012.

Литература[править | править вики-текст]

  • Silberschatz, Abraham; Peterson, James L. Operating Systems Concepts. — Addison-Wesley, 1988. — ISBN 0-201-18760-4.
  • Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.
  • Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115—138.
  • Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pp. 133—138.
  • Э. Таненбаум Современные операционные системы = Modern Operating Systems. — 3-е изд. — Питер, 2010. — С. 203-207. — 1120 с. — (Классика computer science). — 2500 экз. — ISBN 978-5-49807-306-4.

Ссылки[править | править вики-текст]