Проблема обедающих философов
В информатике проблема обедающих философов является примером проблемы, часто используемой при разработке параллельных алгоритмов для иллюстрации проблем синхронизации и методов их решения.
Первоначально он был сформулирован в 1965 году Эдсгером Дейкстрой как экзаменационное упражнение для студентов, представленное в виде конкуренции компьютеров за доступ к периферийным устройствам ленточных накопителей .Вскоре после этого Тони Хоар придал проблеме ее нынешнюю форму. [1] [2] [3] [4]
Постановка задачи
[ редактировать ]Пять философов обедают вместе за одним столом. У каждого философа на столе есть своя тарелка. Между каждой тарелкой есть вилка. Подаваемое блюдо представляет собой своего рода спагетти , которые нужно есть двумя вилками. Каждый философ может только попеременно думать и есть. Более того, философ может есть спагетти только тогда, когда у него есть и левая, и правая вилки. Таким образом, две вилки будут доступны только тогда, когда два их ближайших соседа думают, а не едят. После того, как отдельный философ заканчивает есть, он откладывает обе вилки.Проблема в том, как разработать режим ( параллельный алгоритм), при котором ни один философ не будет голодать; т.е. каждый может вечно продолжать чередовать еду и мышление, предполагая, что ни один философ не может знать, когда другие могут захотеть есть или думать (проблема неполной информации ).
Проблемы
[ редактировать ]Задача была разработана, чтобы проиллюстрировать, как избежать тупика — состояния системы, в котором прогресс невозможен. Чтобы увидеть, что правильное решение этой проблемы неочевидно, рассмотрим предложение, в котором каждому философу предлагается вести себя следующим образом:
- подумайте, если левая развилка недоступна; когда оно будет, поднимите его;
- думайте, пока не будет подходящей вилки; когда оно будет, поднимите его;
- удерживая обе вилки, ешьте определенное время;
- опустите левую вилку;
- опустите правую вилку;
- повторить с начала.
При наличии этих указаний может возникнуть ситуация, когда каждый философ держит вилку слева от себя; в этой ситуации все они застрянут навсегда, ожидая, пока освободится другая вилка: это тупик.
Нехватка ресурсов , взаимное исключение и блокировка в реальном времени — это другие типы проблем последовательности и доступа.
Решения
[ редактировать ]Этих четырех условий достаточно для возникновения тупика: взаимное исключение (ни одна вилка не может быть использована одновременно несколькими философами), удержание ресурса (философы держат вилку, ожидая второй), отсутствие вытеснения (ни один философ не может взять вилку). от другого) и круговое ожидание (каждый философ может ждать философа слева от него). Решение должно отрицать хотя бы одно из этих четырех условий. На практике отрицание взаимного исключения или невытеснения каким-то образом может дать действенное решение, но большинство теоретических подходов предполагают, что эти предположения не подлежат обсуждению, вместо этого они атакуют удержание ресурсов или циклическое ожидание (часто и то, и другое).
Решение Дейкстры
[ редактировать ]Решение Дейкстры сводит на нет удержание ресурсов; философы атомарно берут обе вилки или ждут, никогда не удерживая ровно одну вилку за пределами критической секции. Для этого решение Дейкстры использует один мьютекс , один семафор на каждого философа и одну переменную состояния на каждого философа. Это решение более сложное, чем решение с иерархией ресурсов. [5] [4] Это версия решения Дейкстры на C++20 с изменениями Таненбаума:
#include <chrono>#include <iostream>#include <mutex>#include <random>#include <semaphore>#include <thread>constexpr const size_t N = 5; // number of philosophers (and forks)enum class State { THINKING = 0, // philosopher is THINKING HUNGRY = 1, // philosopher is trying to get forks EATING = 2, // philosopher is EATING};size_t inline left(size_t i) { // number of the left neighbor of philosopher i, for whom both forks are available return (i - 1 + N) % N; // N is added for the case when i - 1 is negative}size_t inline right(size_t i) { // number of the right neighbour of the philosopher i, for whom both forks are available return (i + 1) % N;}State state[N]; // array to keep track of everyone's both_forks_available statestd::mutex critical_region_mtx; // mutual exclusion for critical regions for // (picking up and putting down the forks)std::mutex output_mtx; // for synchronized cout (printing THINKING/HUNGRY/EATING status)// array of binary semaphors, one semaphore per philosopher.// Acquired semaphore means philosopher i has acquired (blocked) two forksstd::binary_semaphore both_forks_available[N]{ std::binary_semaphore{0}, std::binary_semaphore{0}, std::binary_semaphore{0}, std::binary_semaphore{0}, std::binary_semaphore{0}};size_t my_rand(size_t min, size_t max) { static std::mt19937 rnd(std::time(nullptr)); return std::uniform_int_distribution<>(min, max)(rnd);}void test(size_t i) // if philosopher i is hungry and both neighbours are not eating then eat{ // i: philosopher number, from 0 to N-1 if (state[i] == State::HUNGRY && state[left(i)] != State::EATING && state[right(i)] != State::EATING) { state[i] = State::EATING; both_forks_available[i].release(); // forks are no longer needed for this eat session }}void think(size_t i) { size_t duration = my_rand(400, 800); { std::lock_guard<std::mutex> lk(output_mtx); // critical section for uninterrupted print std::cout << i << " is thinking " << duration << "ms\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration));}void take_forks(size_t i){ { std::lock_guard<std::mutex> lk{critical_region_mtx}; // enter critical region state[i] = State::HUNGRY; // record fact that philosopher i is State::HUNGRY { std::lock_guard<std::mutex> lk(output_mtx); // critical section for uninterrupted print std::cout << "\t\t" << i << " is State::HUNGRY\n"; } test(i); // try to acquire (a permit for) 2 forks } // exit critical region both_forks_available[i].acquire(); // block if forks were not acquired}void eat(size_t i){ size_t duration = my_rand(400, 800); { std::lock_guard<std::mutex> lk(output_mtx); // critical section for uninterrupted print std::cout << "\t\t\t\t" << i << " is eating " << duration << "ms\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration));}void put_forks(size_t i) { std::lock_guard<std::mutex> lk{critical_region_mtx}; // enter critical region state[i] = State::THINKING; // philosopher has finished State::EATING test(left(i)); // see if left neighbor can now eat test(right(i)); // see if right neighbor can now eat // exit critical region by exiting the function}void philosopher(size_t i){ while (true) { // repeat forever think(i); // philosopher is State::THINKING take_forks(i); // acquire two forks or block eat(i); // yum-yum, spaghetti put_forks(i); // put both forks back on table and check if neighbours can eat }}int main() { std::cout << "dp_14\n"; std::jthread t0([&] { philosopher(0); }); // [&] means every variable outside the ensuing lambda std::jthread t1([&] { philosopher(1); }); // is captured by reference std::jthread t2([&] { philosopher(2); }); std::jthread t3([&] { philosopher(3); }); std::jthread t4([&] { philosopher(4); });}Функция test() и ее использование в take_forks() и put_forks() делают решение Дейкстры свободным от взаимоблокировок.
Решение иерархии ресурсов
[ редактировать ]Это решение исключает циклическое ожидание, назначая частичный порядок ресурсам (в данном случае ветвям) и устанавливает соглашение, согласно которому все ресурсы будут запрашиваться по порядку и что никакие два ресурса, не связанные порядком, никогда не будут использоваться одним единица работы одновременно. Здесь ресурсы (вилки) будут пронумерованы от 1 до 5, и каждая единица работы (философ) всегда сначала выбирает вилку с меньшим номером, а затем вилку с большим номером из двух вилок, которые он планирует использовать. Порядок, в котором каждый философ кладет вилки, не имеет значения. В этом случае, если четыре из пяти философов одновременно возьмут вилки с меньшим номером, на столе останется только вилка с наибольшим номером, поэтому пятый философ не сможет взять вилку. Более того, только один философ будет иметь доступ к той вилке с наибольшим номером, поэтому он сможет есть, используя две вилки. Интуитивно это можно представить себе как наличие за столом одного философа-левши, который – в отличие от всех других философов – первым берет вилку слева.
Хотя решение иерархии ресурсов позволяет избежать взаимоблокировок, оно не всегда практично, особенно когда список необходимых ресурсов заранее не известен полностью. Например, если единица работы содержит ресурсы 3 и 5, а затем определяет, что ей нужен ресурс 2, она должна освободить 5, затем 3, прежде чем получить 2, а затем она должна повторно получить 3 и 5 в этом порядке. Компьютерные программы, которые обращаются к большому количеству записей базы данных, не будут работать эффективно, если от них потребуется освободить все записи с более высокими номерами перед доступом к новой записи, что делает этот метод непрактичным для этой цели. [2]
Решение с иерархией ресурсов несправедливо . Если философ 1 медленно берет вилку, а философ 2 быстро думает и снова поднимает вилки, то философ 1 никогда не сможет взять обе вилки. Справедливое решение должно гарантировать, что каждый философ в конечном итоге поест, независимо от того, насколько медленно этот философ движется относительно других.
Следующий исходный код представляет собой реализацию C++11 решения иерархии ресурсов для пяти философов. Функция Sleep_for() имитирует время, обычно затрачиваемое на бизнес-логику. [6]
Для GCC: скомпилировать с помощью
g++ src.cpp -std=c++11 -lpthread#include <iostream>#include <chrono>#include <mutex>#include <thread>#include <random>#include <ctime>using namespace std;int myrand(int min, int max) { static mt19937 rnd(time(nullptr)); return uniform_int_distribution<>(min,max)(rnd);}void philosopher(int ph, mutex& ma, mutex& mb, mutex& mo) { for (;;) { // prevent thread from termination int duration = myrand(200, 800); { // Block { } limits scope of lock lock_guard<mutex> gmo(mo); cout<<ph<<" thinks "<<duration<<"ms\n"; } this_thread::sleep_for(chrono::milliseconds(duration)); { lock_guard<mutex> gmo(mo); cout<<"\t\t"<<ph<<" is hungry\n"; } lock_guard<mutex> gma(ma); // sleep_for() Delay before seeking second fork can be added here but should not be required. lock_guard<mutex> gmb(mb); duration = myrand(200, 800); { lock_guard<mutex> gmo(mo); cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n"; } this_thread::sleep_for(chrono::milliseconds(duration)); }}int main() { cout<<"dining Philosophers C++11 with Resource hierarchy\n"; mutex m1, m2, m3, m4, m5; // 5 forks are 5 mutexes mutex mo; // for proper output // 5 philosophers are 5 threads thread t1([&] {philosopher(1, m1, m2, mo);}); thread t2([&] {philosopher(2, m2, m3, mo);}); thread t3([&] {philosopher(3, m3, m4, mo);}); thread t4([&] {philosopher(4, m4, m5, mo);}); thread t5([&] {philosopher(5, m1, m5, mo);}); // Force a resource hierarchy t1.join(); // prevent threads from termination t2.join(); t3.join(); t4.join(); t5.join();}Решение арбитра
[ редактировать ]Другой подход состоит в том, чтобы гарантировать, что философ может взять только обе вилки или не взять ни одной, введя арбитра вместо циклического ожидания, например, официанта. Чтобы взять вилки, философ должен спросить разрешения у официанта. Официант одновременно дает разрешение только одному философу, пока философ не возьмет в руки обе вилки. Всегда можно положить вилку. Официант может быть реализован как мьютекс.Помимо введения новой центральной сущности (официанта), этот подход может привести к уменьшению параллелизма: если философ ест, а один из его соседей запрашивает вилки, все остальные философы должны ждать, пока этот запрос не будет выполнен, даже если вилки для них все еще доступны.
Ограничение количества посетителей за столом
[ редактировать ]Решение, представленное Уильямом Столлингсом [7] состоит в том, чтобы позволить максимум n-1 философам сесть за стол в любое время. Последнему философу пришлось бы ждать (например, с помощью семафора), пока кто-нибудь закончит обедать, прежде чем он «сядет» и запросит доступ к любой вилке. Это сводит на нет циклическое ожидание, гарантируя, что хотя бы один философ всегда может получить обе вилки, что позволяет системе развиваться.
Решение Чанди/Мисра
[ редактировать ]В 1984 году К. Мани Чанди и Дж. Мисра. [8] предложил другое решение проблемы обедающих философов, позволяющее произвольным агентам (с номерами P 1 , ..., P n ) бороться за произвольное количество ресурсов, в отличие от решения Дейкстры. Он также полностью распределен и не требует никаких центральных полномочий после инициализации. Однако это нарушает требование, чтобы «философы не разговаривали друг с другом» (из-за сообщений-запросов).
- Для каждой пары философов, конкурирующих за ресурс, создайте форк и передайте его философу с меньшим идентификатором ( n для агента P n ). Каждая вилка может быть грязной или чистой. Изначально все вилки грязные.
- Когда философ хочет использовать набор ресурсов ( т. е . поесть), он должен получить вилки от своих конкурирующих соседей. На все такие развилки, которых у философа нет, он отправляет сообщение-запрос.
- Когда философ с вилкой получает сообщение с просьбой, он оставляет вилку чистой, но отдает ее, когда она грязная. Если философ посылает вилку, он перед этим очищает вилку.
- После того, как философ закончил есть, все его вилки становятся грязными. Если другой философ ранее запросил одну из вилок, философ, только что закончивший есть, чистит вилку и отправляет ее.
Это решение также обеспечивает высокую степень параллелизма и решит сколь угодно большую проблему.
Это также решает проблему голодания. Этикетки «чистый/грязный» служат способом отдать предпочтение наиболее «голодным» процессам и поставить в невыгодное положение процессы, которые только что «съели». Их решение можно сравнить с решением, в котором философам не разрешается есть дважды подряд, не позволяя другим пользоваться вилками между ними. Решение Чанди и Мисры более гибкое, но в нем есть элемент, тяготеющий в этом направлении.
В своем анализе они выводят систему уровней предпочтений на основе распределения вилок и их чистых/грязных состояний. Они показывают, что эта система может описывать ориентированный ациклический граф , и если это так, то операции в их протоколе не могут превратить этот граф в циклический. Это гарантирует, что тупиковая ситуация не возникнет, поскольку исключает циклическое ожидание. Однако если система инициализирована в идеально симметричном состоянии, как все философы, держащие левую вилку, то граф с самого начала является циклическим, и их решение не может предотвратить тупик. Инициализация системы так, чтобы у философов с более низкими идентификаторами были грязные вилки, гарантирует, что граф изначально ацикличен.
См. также
[ редактировать ]- Проблема курильщиков сигарет
- Проблема производителей-потребителей
- Проблема читателей-писателей
- Проблема со спящим парикмахером
Ссылки
[ редактировать ]- ^ Дейкстра, Эдсгер В. EWD-1000 (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция )
- ^ Перейти обратно: а б Х. Диас; И. Рамос (1981). Формализация концепций программирования: Международный коллоквиум, Пенискола, Испания, 19–25 апреля 1981 г. Труды . Биркхойзер. стр. 323 , 326 . ISBN 978-3-540-10699-9 .
- ^ Хоар, ЦАР (2004) [первоначально опубликовано в 1985 году издательством Prentice Hall International]. «Обмен последовательными процессами» (PDF) . используя csp.com.
- ^ Перейти обратно: а б Таненбаум, Эндрю С. (2006), Операционные системы – проектирование и внедрение, 3-е издание [Глава: 2.3.1 Проблема обедающих философов] , Pearson Education, Inc.
- ^ Дейкстра, Эдсгер В. EWD-310 (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция )
- ^ Таненбаум, Эндрю С. (2006), Операционные системы – проектирование и внедрение, 3-е издание [Глава: 3.3.5 Предотвращение тупиковых ситуаций] , Pearson Education, Inc.
- ^ Столлингс, Уильям (2018). Операционные системы: внутреннее устройство и принципы проектирования (9-е изд.). Харлоу, Эссекс, Англия: Пирсон . п. 310. ИСБН 978-1-292-21429-0 . OCLC 1009868379 .
- ^ Чанди, КМ; Мисра, Дж. (1984). Проблема пьющих философов . Транзакции ACM в языках и системах программирования.
Библиография
[ редактировать ]- Зильбершац, Авраам; Петерсон, Джеймс Л. (1988). Концепции операционных систем . Аддисон-Уэсли. ISBN 0-201-18760-4 .
- Дейкстра, EW (1971, июнь). Иерархическое упорядочение последовательных процессов . Акта Информатика 1 (2): 115–138.
- Леманн, ди-джей, Рабин М.О. (1981). О преимуществах свободного выбора: симметричное и полностью распределенное решение проблемы обедающих философов. Принципы языков программирования 1981 ( POPL '81), стр. 133–138.
Внешние ссылки
[ редактировать ]- Обсуждение проблемы с кодом решения для 2 или 4 философов. Архивировано 20 июля 2011 г. на Wayback Machine.
- Обсуждение различных решений на Wayback Machine (архив от 8 декабря 2013 г.)
- Обсуждение решения с использованием потоков на основе продолжения (cbthreads) на Wayback Machine (архивировано 4 марта 2012 г.)
- Формальная спецификация решения Чанди-Мисра, написанная на TLA+.
- Распределенные симметричные решения
- Программирование обедающих философов с помощью моделирования
- Интерактивный пример задачи «Философы» ( требуется Java )
- Сатана приходит на ужин
- Что, нет кур? - Питер Х. Уэлч предложил вариант «Голодные философы», который демонстрирует неудачное последствие поведения мониторов потоков Java, заключающееся в том, что голодание потоков становится более вероятным, чем это строго необходимо.
- ThreadMentor
- Решение проблемы обедающих философов с помощью асинхронных агентов
- Решение с использованием актеров
| Общий | |
|---|---|
| Процесс исчисления | |
| Классические задачи | |
