Проблема обедающих философов: иллюстрация и решения задач синхронизации.
Dining philosophers problem
Проблема "обедающих философов": классическая задача синхронизации в информатике, иллюстрирующая проблемы конкурентного доступа к ресурсам и методы их решения.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Проблема, используемая для иллюстрации проблем синхронизации и методов их решения
Problem used to illustrate synchronization issues and techniques for resolving them
В информатике проблема обедающих философов — это примерная задача, часто используемая при разработке параллельных алгоритмов для иллюстрации проблем синхронизации и способов их решения. Она была впервые сформулирована Эдсгером Дейкстрой в 1965 году в качестве студенческой экзаменационной работы, представленной в терминах компьютеров, конкурирующих за доступ к периферийным устройствам на магнитных лентах. Вскоре после этого Тони Хоар придал задаче её современную формулировку.
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them. It was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present form.
Заявление о проблеме
Пять философов обедают за одним столом. У каждого философа есть своя тарелка. Между каждой тарелкой лежит вилка. Подается блюдо – спагетти, которые нужно есть двумя вилками. Каждый философ может только попеременно думать и есть. Более того, философ может есть спагетти только тогда, когда у него есть и левая, и правая вилка. Таким образом, две вилки будут доступны только тогда, когда оба его ближайших соседа думают, а не едят. Когда философ заканчивает есть, он кладет обе вилки обратно. Задача состоит в том, чтобы разработать схему (параллельный алгоритм), гарантирующую, что ни один философ не останется голодным; то есть, каждый сможет бесконечно чередовать еду и размышления, при условии, что ни один философ не знает, когда другие захотят есть или думать (проблема неполной информации).
Five philosophers dine together at the same table. Each philosopher has his own plate at the table. There is a fork between each plate. The dish served is a kind of spaghetti which has to be eaten with two forks. Each philosopher can only alternately think and eat. Moreover, a philosopher can only eat his spaghetti when he has both a left and right fork. Thus two forks will only be available when his two nearest neighbors are thinking, not eating. After an individual philosopher finishes eating, he will put down both forks. The problem is how to design a regimen (a concurrent algorithm) such that any philosopher will not starve; i. e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think (an issue of incomplete information).
Решение арбитра
Другой подход заключается в том, чтобы гарантировать, что философ может взять либо обе вилки, либо ни одной, вводя арбитра, например, официанта. Чтобы взять вилки, философ должен запросить разрешение у официанта. Официант выдает разрешение только одному философу за раз, пока философ не возьмет обе свои вилки. Отложить вилку всегда разрешено. Официанта можно реализовать как мьютекс. Помимо введения нового центрального элемента (официанта), этот подход может привести к снижению параллелизма: если философ ест, а один из его соседей запрашивает вилки, все остальные философы должны ждать, пока этот запрос не будет обработан, даже если вилки для них все еще свободны.
Another approach is to guarantee that a philosopher can only pick up both forks or none by introducing an arbitrator, e. g., a waiter. In order to pick up the forks, a philosopher must ask permission of the waiter. The waiter gives permission to only one philosopher at a time until the philosopher has picked up both of his forks. Putting down a fork is always allowed. The waiter can be implemented as a mutex. In addition to introducing a new central entity (the waiter), this approach can result in reduced parallelism: if a philosopher is eating and one of his neighbors is requesting the forks, all other philosophers must wait until this request has been fulfilled even if forks for them are still available.
Ограничение количества гостей за столом
Решение, предложенное Уильямом Сталлингсом, состоит в том, чтобы допускать за стол не более чем n-1 философов одновременно. Последний философ должен будет ждать (например, используя семафор), пока кто-нибудь не закончит есть, прежде чем "садиться" и запрашивать доступ к вилке. Это гарантирует, что хотя бы один философ всегда сможет получить обе вилки, что позволит системе продвигаться вперед.
A solution presented by William Stallings is to allow a maximum of n 1 philosophers to sit down at any time. The last philosopher would have to wait (for example, using a semaphore) for someone to finish dining before he "sits down" and requests access to any fork. This guarantees at least one philosopher may always acquire both forks, allowing the system to make progress.
Раствор Чанди/Мисры
В 1984 году К. Мани Чанди и Дж. Мисра предложили иное решение проблемы обедающих философов, позволяющее произвольным агентам (с номерами P1, …, Pn) конкурировать за произвольное количество ресурсов, в отличие от решения Дайкстры. Оно также полностью распределено и не требует центрального органа после инициализации. Однако, оно нарушает требование, что "философы не общаются друг с другом" (из-за сообщений запроса). Для каждой пары философов, претендующих на ресурс, создается вилка и передается философу с меньшим идентификатором (n для агента Pn). Каждая вилка может быть чистой или грязной. Изначально все вилки грязные. Когда философ хочет использовать набор ресурсов (то есть, поесть), он должен получить вилки от своих соперничающих соседей. Для всех вилок, которых у философа нет, он отправляет запрос. Когда философ, владеющий вилкой, получает запрос, он оставляет вилку себе, если она чистая, но передает ее, если она грязная. Если философ передает вилку, он очищает ее перед этим. После того, как философ закончил есть, все его вилки становятся грязными. Если другой философ ранее запрашивал одну из вилок, философ, который только что закончил есть, очищает вилку и отправляет ее. Это решение также обеспечивает высокую степень параллелизма и может решить задачу произвольного размера. Оно также решает проблему "голодания". Метки "чистый/грязный" служат способом предоставления приоритета наиболее "голодным" процессам и снижения приоритета процессов, которые только что "поели". Их решение можно сравнить с ситуацией, когда философам не разрешается есть два раза подряд, не предоставляя другим возможность использовать вилки. Решение Чанди и Мисры более гибкое, но содержит элемент, направленный в этом же направлении. В своем анализе они выводят систему уровней приоритета на основе распределения вилок и их состояния (чистые/грязные). Они показывают, что эта система может быть представлена в виде ориентированного ациклического графа, и если это так, то операции в их протоколе не могут превратить этот граф в циклический. Это гарантирует отсутствие взаимоблокировки. Однако, если система инициализирована в полностью симметричное состояние, например, когда все философы держат вилки слева, то граф изначально цикличен, и их решение не может предотвратить взаимоблокировку. Инициализация системы таким образом, чтобы философы с меньшими идентификаторами имели грязные вилки, гарантирует, что граф изначально будет ациклическим.
In 1984, K. Mani Chandy and J. Misra proposed a different solution to the dining philosophers problem to allow for arbitrary agents (numbered P1, , Pn) to contend for an arbitrary number of resources, unlike Dijkstra's solution. It is also completely distributed and requires no central authority after initialization. However, it violates the requirement that "the philosophers do not speak to each other" (due to the request messages). For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty. When a philosopher wants to use a set of resources (i. e., eat), said philosopher must obtain the forks from his contending neighbors. For all such forks the philosopher does not have, he sends a request message. When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but give it up when it is dirty. If the philosopher sends the fork over, he cleans the fork before doing so. After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, the philosopher that has just finished eating cleans the fork and sends it. This solution also allows for a large degree of concurrency, and will solve an arbitrarily large problem. It also solves the starvation problem. The clean/dirty labels act as a way of giving preference to the most "starved" processes, and a disadvantage to processes that have just "eaten". One could compare their solution to one where philosophers are not allowed to eat twice in a row without letting others use the forks in between. Chandy and Misra's solution is more flexible than that, but has an element tending in that direction. In their analysis, they derive a system of preference levels from the distribution of the forks and their clean/dirty states. They show that this system may describe a directed acyclic graph, and if so, the operations in their protocol cannot turn that graph into a cyclic one. This guarantees that deadlock cannot occur. However, if the system is initialized to a perfectly symmetric state, like all philosophers holding their left side forks, then the graph is cyclic at the outset, and their solution cannot prevent a deadlock. Initializing the system so that philosophers with lower IDs have dirty forks ensures the graph is initially acyclic.