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