#информатика #задачапрофилософов #задачасинхронизации #синхронизация

💻 Одна из самых известных, можно даже сказать легендарных, задач информатики — задача об обедающих философах. Ее в 1965 году придумал Edsger W. Dijkstra в качестве упражнения для студентов.

Первоначально она описывала не философов, а процессы, конкурирующие за доступ к магнитным накопителям (ленточным устройствам). Целью было показать трудности синхронизации в многозадачных системах. В современном наглядном и запоминающемся виде ее сформулировал Tony Hoare:

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

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

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

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

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

🤯 Однако именно такая естественная стратегия приводит к серьёзной проблеме.

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

⛔️ В информатике такое состояние называется взаимной блокировкой (deadlock). Оно представляет одну из фундаментальных проблем параллельных вычислений, поскольку процессы могут оказаться навсегда заблокированными, несмотря на то что все необходимые ресурсы существуют и находятся внутри системы.

С момента появления задачи предложено много способов избежать взаимной блокировки.
✔️Одно из самых простых решений заключается в том, чтобы установить строгий порядок получения ресурсов. Например, если все вилки пронумеровать и обязать философов всегда брать сначала вилку с меньшим номером, а затем с большим, циклическое ожидание станет невозможным.
✔️Другой подход предполагает введение своеобразного арбитра или «официанта», который контролирует доступ к вилкам. Прежде чем начать есть, философ должен получить разрешение от такого управляющего процесса, который следит за тем, чтобы система не зашла в тупик.

🥣 Существует и более простая стратегия: разрешать одновременно пытаться поесть не всем пяти философам, а только четырём. В этом случае хотя бы один участник всегда сможет получить обе вилки, завершить трапезу и освободить ресурсы для остальных.

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

Задача взята из канала Мат.салат