Описание задачи

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

Четыре философа сидят за таблицей, проводя свою жизнь в бесконечном круге мышления и еды. Философ должен забрать обе вилки, прежде чем он сможет поесть. Можно представить философов как параллельные процессы, а вилки как общие ресурсы. Задача состоит в том, чтобы определить политику или алгоритм, чтобы каждый философ мог поесть и не голодал. Например, один алгоритм для каждого философа, чтобы забрать сначала вилку справа, затем вилку налево, прежде чем он съедает. Что это в конечном счете приведет к тупиковой ситуации, когда все философы держат одну вилку, ожидая друг друга, чтобы положить свои вилки.

Философская модель

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

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

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

Результаты

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

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

Тупик

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

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

Ссылки

[1] Обеденная философская задача - Википедия (https://en.wikipedia.org/wiki/Dining_philosophers_problem)