Проблема Dining Philosophers - классическая задача, первоначально сформулированная Э. В. Дайкстрой, для демонстрации классических задач в информатике и программировании параллельных или параллельных процессов.
Четыре философа сидят за столом, проводя свою жизнь в бесконечном цикле мышления и еды. Философ должен забрать обе вилки, прежде чем съесть. Философов можно считать параллельными процессами, а развилки - общими ресурсами. Проблема в том, чтобы определить политику или алгоритм так, чтобы каждый философ получал пищу и не голодал. Например, один алгоритм для каждого философа, чтобы забрать сначала вилку справа, затем вилку слева, прежде чем он съест. Что это в конечном итоге приведет к тупиковой ситуации, когда все философы держат одну вилку, ожидая, пока друг друга опустят вилки.
В этом примере каждый философ моделируется как дискретная система событий, которая генерирует один объект в начале моделирования. Положение сущности в системе отражает состояние философа. Каждое состояние философа является сервером сущностей, который может содержать сущность в течение рандомизированного периода времени.
Проиллюстрированный здесь алгоритм представляет собой вариацию исходного алгоритма, описанного Дейкстрой. Каждая вилка пронумерована, и философы сначала подбирают меньшую пронумерованную вилку, а затем большую пронумерованную вилку. Этого алгоритма достаточно, чтобы избежать тупиковых ситуаций, потому что только один философ может когда-либо иметь самую высокую вилку и, следовательно, этот философ может продолжать есть.
На первом рисунке показана диаграмма Гантта всех четырех философов, которые вращаются между мышлением, голоданием и едой.
На втором рисунке показаны мгновенные состояния всех четырёх философов во время моделирования. Линия, проведенная от философа (заполненный круг) к вилке (скругленный прямоугольник), указывает на то, что философ взял эту вилку и, следовательно, вилка недоступна для своего соседа.
В этой модели взаимоблокировка может быть достигнута, если Философ 4 изменит свой порядок предпочтения вилки так, что он захватит вилку 4 перед вилкой 1. Это нарушает вышеуказанное ограничение иерархии ресурсов, и моделирование модели с этим изменением приведет к взаимоблокировке, как показано ниже.
Результат выше показывает, что каждый философ подобрал нужную вилку, и все ждут, когда другая вилка станет доступной, вызывая тупик.
[1] Проблема философов обедов - Википедия (https://en.wikipedia.org/wiki/Dining_philosophers_problem)
Генератор объектов | Приобретатель ресурсов | Пул ресурсов | Средство освобождения ресурсов