В информатике задача об обедающих философах — это пример задачи, часто используемой при проектировании параллельных алгоритмов для иллюстрации проблем синхронизации и методов их решения.
Первоначально она была сформулирована в 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 ; // количество философов (и вилок) enum class State { ДУМАЕТ = 0 , // философ ДУМАЕТ ГОЛОДНЫЙ = 1 , // философ пытается достать вилки ЕДИТ = 2 , // философ ЕДИТ }; size_t inline left ( size_t i ) { // номер левого соседа философа i, для которого доступны обе вилки return ( i - 1 + N ) % N ; // N добавляется для случая, когда i - 1 отрицательно } size_t inline right ( size_t i ) { // номер правого соседа философа i, для которого доступны обе вилки return ( i + 1 ) % N ; } State state [ N ]; // массив для отслеживания состояния both_forks_available каждого std :: mutex critical_region_mtx ; // взаимное исключение для критических регионов для // (поднятие и опускание вилок) std :: mutex output_mtx ; // для синхронизированного cout (вывод состояния ДУМАЮ/ГОЛОД/ЕДЮ) // массив двоичных семафоров, по одному семафору на философа. // Полученный семафор означает, что философ i получил (заблокировал) две вилки std :: 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 ) // если философ i голоден и оба соседа не едят, то eat { // i: номер философа, от 0 до 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 (); // вилки больше не нужны для этого сеанса еды } } void think ( size_t i ) { size_t duration = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // критическая секция для непрерывной печати 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 }; // войти в критическую область state [ i ] = State :: HUNGRY ; // записать факт, что философ i является State::HUNGRY { std :: lock_guard < std :: mutex > lk ( output_mtx ); // критическая секция для непрерывной печати std :: cout << " \t\t " << i << " is State::HUNGRY \n " ; } test ( i ); // попытаться получить (разрешение на) 2 вилки } // выйти из критической области both_forks_available [ i ]. acquire (); // блокировка, если вилки не были получены } void eat ( size_t i ) { size_t duration = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // критическая секция для непрерывной печати 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 }; // войти в критическую область state [ i ] = State :: THINKING ; // философ закончил State::EATING test ( left ( i )); // проверить, может ли теперь есть сосед слева test ( right ( i )); // проверить, может ли теперь есть сосед справа // выйти из критической области, выйдя из функции } void philosophy ( size_t i ) { while ( true ) { // повторять вечно think ( i ); // философ - State::THINKING take_forks ( i ); // получить две вилки или заблокировать eat ( i ); // ням-ням, спагетти put_forks ( i ); // положить обе вилки обратно на стол и проверить, могут ли соседи есть } } int main () { std :: cout << "dp_14 \n " ; std :: jthread t0 ([ & ] { philosophy ( 0 ); }); // [&] означает каждую переменную за пределами последующей лямбды std :: jthread t1 ([ & ] { philosophy ( 1 ); }); // захватывается ссылкой std :: jthread t2 ([ & ] { philosophy ( 2 ); }); std :: jthread t3 ([ & ] { philosophy ( 3 ); }); std :: jthread t4 ([ & ] { philosophy ( 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> с использованием пространства имен std ; int myrand ( int min , int max ) { static mt19937 rnd ( time ( nullptr )); return uniform_int_distribution <> ( min , max )( rnd ); } void philosophy ( int ph , mutex & ma , mutex & mb , mutex & mo ) { for (;;) { // предотвратить завершение потока int duration = myrand ( 200 , 800 ); { // Блок { } ограничивает область действия блокировки lock_guard < mutex > gmo ( mo ); cout << ph << " думает " << duration << " мс \n " ; } this_thread :: sleep_for ( chrono :: milliseconds ( duration )); { lock_guard < mutex > gmo ( mo ); cout << " \t\t " << ph << " голоден \n " ; } lock_guard < mutex > gma ( ma ); // sleep_for() Задержка перед поиском второй вилки может быть добавлена здесь, но не должна быть обязательной. 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 :: миллисекунды ( duration )); } } int main () { cout << "dining Philosophers C++11 с иерархией ресурсов \n " ; mutex m1 , m2 , m3 , m4 , m5 ; // 5 форков — это 5 мьютексов mutex mo ; // для правильного вывода // 5 философов — это 5 потоков thread t1 ([ & ] { philosophy ( 1 , m1 , m2 , mo );}); thread t2 ([ & ] { philosophy ( 2 , m2 , m3 , mo );}); thread t3 ([ & ] { philosophy ( 3 , m3 , m4 , mo );}); thread t4 ([ & ] { philosophy ( 4 , m4 , m5 , mo );}); thread t5 ([ & ] { philosophy ( 5 , m1 , m5 , mo );}); // Принудительно создаем иерархию ресурсов t1 . join (); // предотвратить завершение потоков t2 . join (); t3 . join (); t4 . join (); t5 . join (); } Другой подход заключается в том, чтобы гарантировать, что философ может взять только обе вилки или ни одной, путем введения арбитра для замены циклического ожидания, например, официанта. Чтобы взять вилки, философ должен спросить разрешения у официанта. Официант дает разрешение только одному философу за раз, пока философ не возьмет обе свои вилки. Положить вилку всегда разрешено. Официант может быть реализован как мьютекс. Помимо введения новой центральной сущности (официанта), этот подход может привести к уменьшению параллелизма: если философ ест, а один из его соседей запрашивает вилки, все остальные философы должны ждать, пока этот запрос не будет выполнен, даже если вилки для них все еще доступны.
Решение, представленное Уильямом Столлингсом [7], состоит в том, чтобы позволить максимум n-1 философам садиться в любое время. Последнему философу пришлось бы ждать (например, используя семафор), пока кто-то закончит обедать, прежде чем он «сядет» и запросит доступ к любой вилке. Это исключает циклическое ожидание, гарантируя, что по крайней мере один философ всегда может получить обе вилки, позволяя системе двигаться вперед.
В 1984 году К. Мани Чанди и Дж. Мисра [8] предложили другое решение проблемы обедающих философов, позволяющее произвольным агентам (пронумерованным P 1 , ..., P n ) бороться за произвольное количество ресурсов, в отличие от решения Дейкстры. Оно также полностью распределено и не требует центральной власти после инициализации. Однако оно нарушает требование, что «философы не разговаривают друг с другом» (из-за сообщений-запросов).
Это решение также обеспечивает высокую степень параллелизма и позволяет решить произвольно большую задачу.
Это также решает проблему голодания. Чистые/грязные этикетки действуют как способ отдать предпочтение наиболее «голодным» процессам и поставить в невыгодное положение процессы, которые только что «поели». Можно сравнить их решение с решением, в котором философам не разрешается есть дважды подряд, не позволяя другим пользоваться вилками между ними. Решение Чанди и Мисры более гибкое, но имеет элемент, тяготеющий к этому.
В своем анализе они выводят систему уровней предпочтений из распределения вилок и их чистых/грязных состояний. Они показывают, что эта система может описывать направленный ациклический граф , и если это так, то операции в их протоколе не могут превратить этот граф в циклический. Это гарантирует, что тупик не может возникнуть из-за отрицания циклического ожидания. Однако, если система инициализирована в идеально симметричном состоянии, как все философы, удерживающие свои левые вилки, то граф является циклическим с самого начала, и их решение не может предотвратить тупик. Инициализация системы таким образом, чтобы философы с более низкими идентификаторами имели грязные вилки, гарантирует, что граф изначально ацикличен.