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

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

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

Постановка задачи

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

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

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

Прием пищи не ограничивается оставшимся количеством спагетти или объемом желудка; предполагается бесконечное предложение и бесконечный спрос.

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

Проблемы

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

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

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

Ресурсное голодание может также возникнуть независимо от тупика, если конкретный философ не может получить обе вилки из-за проблемы с синхронизацией. Например, может существовать правило, согласно которому философы кладут вилку после десяти минут ожидания, пока другая вилка станет доступной, и ждут еще десять минут перед следующей попыткой. Эта схема исключает возможность тупиковой ситуации (система всегда может перейти в другое состояние), но по-прежнему страдает проблемой лайвлок. Если все пять философов появятся в столовой в одно и то же время и каждый поднимет левую вилку одновременно, философы будут ждать десять минут, пока все они сложат вилки, а затем ждут еще десять минут, прежде чем все их возьмут снова вверх.

Взаимное исключение это основная идея проблемы; философы-обедающие создают общий и абстрактный сценарий, полезный для объяснения вопросов этого типа. Неудачи, с которыми могут столкнуться эти философы, аналогичны трудностям, возникающим в реальном компьютерном программировании, когда нескольким программам требуется монопольный доступ к общим ресурсам. Эти вопросы изучаются в параллельное программирование. Первоначальные проблемы Дейкстры были связаны с внешними устройствами, такими как ленточные накопители. Однако трудности, иллюстрируемые проблемой обедающих философов, возникают гораздо чаще, когда несколько процессов обращаются к наборам данных, которые обновляются. Сложные системы, такие как Операционная система ядра использовать тысячи замки и синхронизации которые требуют строгого соблюдения методов и протоколов, чтобы избежать таких проблем, как тупик, голодание и повреждение данных.

Решения

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

Это решение проблемы было первоначально предложено Dijkstra. Он присваивает частичный заказ к ресурсам (в данном случае вилкам), и устанавливает соглашение, согласно которому все ресурсы будут запрашиваться по порядку, и что никакие два ресурса, не связанных по порядку, никогда не будут использоваться одной единицей работы одновременно. Здесь ресурсы (вилки) будут пронумерованы от 1 до 5, и каждая единица работы (философ) всегда будет сначала выбирать вилку с меньшим номером, а затем вилку с большим номером из двух вилок, которые они планируют использовать. Порядок, в котором каждый философ кладет вилки, не имеет значения. В этом случае, если четыре из пяти философов одновременно возьмут вилку с меньшим номером, на столе останется только вилка с самым высоким номером, поэтому пятый философ не сможет взять вилку. Более того, только один философ будет иметь доступ к вилке с наибольшим номером, поэтому он сможет есть, используя две вилки.

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

Решение арбитра

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

Решение Chandy / Misra

В 1984 г. К. Мани Чанди и Дж. Мисра[5] предложил другое решение проблемы обедающих философов, позволяющее использовать произвольных агентов (пронумерованных п1, ..., пп), чтобы бороться за произвольное количество ресурсов, в отличие от решения Дейкстры. Он также полностью распределен и не требует центральной власти после инициализации. Однако это нарушает требование, согласно которому «философы не разговаривают друг с другом» (из-за сообщений-запросов).

  1. Для каждой пары философов, соревнующихся за ресурс, создайте вилку и отдайте ее философу с меньшим идентификатором (п для агента пп). Каждая вилка может быть грязный или же чистый. Изначально все вилки грязные.
  2. Когда философ хочет использовать набор ресурсов (т.е. есть), сказал философ должен получить вилки у своих соперничающих соседей. Для всех таких вилок, которых нет у философа, они отправляют сообщение-запрос.
  3. Когда философ с вилкой получает сообщение с запросом, они оставляют вилку, если она чистая, но отказываются от нее, если она грязная. Если философ посылает вилку, он перед этим чистит вилку.
  4. После того, как философ закончил есть, все его вилки становятся грязными. Если другой философ ранее запросил одну из вилок, философ, который только что закончил есть, чистит вилку и отправляет ее.

Это решение также обеспечивает высокую степень параллелизма и решает сколь угодно большие проблемы.

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

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

Смотрите также

Рекомендации

  1. ^ Дейкстра, Эдсгер В. EWD-1000 (PDF). Архив Э.В. Дейкстры. Центр американской истории, Техасский университет в Остине. (транскрипция )
  2. ^ а б Х. Диас; Рамос И. (1981). Формализация концепций программирования: Международный коллоквиум, Пенискола, Испания, 19–25 апреля 1981 г. Труды. Birkhäuser. стр.323 , 326. ISBN  978-3-540-10699-9.
  3. ^ Хоар, К. А. Р. (2004) [первоначально опубликовано в 1985 году издательством Prentice Hall International]. «Связь последовательных процессов» (PDF). usingcsp.com.
  4. ^ Дейкстра, Эдсгер В. EWD-310 (PDF). Архив Э.В. Дейкстры. Центр американской истории, Техасский университет в Остине. (транскрипция )
  5. ^ Chandy, K.M .; Мисра, Дж. (1984). Проблема пьющих философов. Транзакции ACM по языкам и системам программирования.

Библиография

  • Зильбершац, Авраам; Петерсон, Джеймс Л. (1988). Концепции операционных систем. Эддисон-Уэсли. ISBN  0-201-18760-4.
  • Дийкстра, Э. У. (1971, июнь). Иерархическое упорядочение последовательных процессов. Acta Informatica 1 (2): 115–138.
  • Леманн Д. Дж., Рабин М. О. (1981). О преимуществах свободного выбора: симметричное и полностью распределенное решение проблемы обедающих философов. Принципы языков программирования 1981 (POPL '81), стр. 133–138.

внешняя ссылка