В информатике проблема обедающих философов является примером проблемы, часто используемой при разработке параллельных алгоритмов для иллюстрации проблем синхронизации и методов их решения.
Первоначально он был сформулирован в 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 { THINKING = 0 , // философ ДУМАЕТ ГОЛОДНО = 1 , // философ пытается достать вилки EATING = 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 ; } Состояние штата [ N ]; // массив для отслеживания состояния Both_forks_available каждого std :: мьютекс критический_регион_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 голоден и оба соседа не едят, то едят { // i: номер философа от 0 до N-1 if ( state [ i ] == State :: HUNGRY && state [ left ( i )] != Состояние :: ЕДА && состояние [ right ( i )] != Состояние :: ЕДА ) { состояние [ i ] = Состояние :: ЕДА ; обе_вилки_доступны [ я ]. выпускать (); // вилки для этого сеанса еды больше не нужны } } void think ( size_t я ) { size_t продолжительность = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // критическая секция для непрерывной печати std :: cout << i << " думает " << длительность << "ms \n " ; } std :: this_thread :: sleep_for ( std :: хроно :: миллисекунды ( длительность )); } void take_forks ( size_t i ) { { std :: lock_guard < std :: mutex > lk { Critical_region_mtx }; // вход в критическое состояние региона [ i ] = State :: HUNGRY ; // записываем тот факт, что философ i — State::HUNGRY { std :: lock_guard < std :: mutex > lk ( output_mtx ); // критическая секция для непрерывной печати std :: cout << " \t\t " << i << " is State::HUNGRY \n " ; } Тест ( я ); // попытаемся получить (разрешение на) 2 форка } // выходим из критической области Both_forks_available [ i ]. приобретать (); // блокируем, если форки не были получены } void eat ( size_t я ) { size_t продолжительность = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // критическая секция для непрерывной печати std :: cout << " \t\t\t\t " << i << " съедает " << длительность << "ms \n " ; } std :: this_thread :: sleep_for ( std :: хроно :: миллисекунды ( длительность )); } void put_forks ( size_t i ) { std :: lock_guard < std :: mutex > lk { critical_region_mtx }; // вход в состояние критической области [ i ] = State :: THINKING ; // философ завершил тест State::EATING ( left ( i ) ); // проверяем, может ли левый сосед съесть test ( right ( i )); // проверяем, может ли правый сосед теперь есть // выходим из критической области, выйдя из функции } void философ ( 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 ([ & ] { философ ( 0 ); }); // [&] означает каждую переменную вне последующей лямбды std :: jthread t1 ([ & ] { философ ( 1 ); }); // захватывается по ссылке std :: jthread t2 ([ & ] { философ ( 2 ); }); std :: jthread t3 ([ & ] { философ ( 3 ); }); std :: jthread t4 ([ & ] { философ ( 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 = С++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 )); вернуть униформу_int_distribution <> ( мин , макс )( rnd ); } void философ ( int ph , mutex & ma , mutex & mb , mutex & mo ) { for (;;) { // предотвращаем завершение потока int period = myrand ( 200 , 800 ); { // Block { } ограничивает область действия блокировки lock_guard < mutex > gmo ( mo ); cout << ph << " думает " << длительность << "ms \n " ; } this_thread :: Sleep_for ( хроно :: миллисекунды ( длительность )); { lock_guard < мьютекс > gmo ( mo ); cout << " \t\t " << ph << " голоден \n " ; } lock_guard < мьютекс > gma ( ма ); // Sleep_for() Здесь можно добавить задержку перед поиском второй вилки, но это не обязательно. lock_guard < мьютекс > gmb ( mb ); продолжительность = миранд ( 200 , 800 ); { lock_guard < мьютекс > gmo ( mo ); cout << " \t\t\t\t " << ph << " ест " << длительность << "ms \n " ; } this_thread :: Sleep_for ( хроно :: миллисекунды ( длительность )); } } int main () { cout << "обед Философов C++11 с иерархией ресурсов \n " ; мьютекс m1 , m2 , m3 , m4 , m5 ; // 5 вилок — это 5 мьютексов mutex mo ; // для корректного вывода // 5 философов — это 5 потоков thread t1 ([ & ] { философ ( 1 , m1 , m2 , mo );}); нить t2 ([ & ] { философ ( 2 , m2 , m3 , mo );}); нить t3 ([ & ] { философ ( 3 , m3 , m4 , mo );}); нить t4 ([ & ] { философ ( 4 , m4 , m5 , mo );}); thread t5 ([ & ] { философ ( 5 , m1 , m5 , mo );}); // Форсируем иерархию ресурсов t1 . присоединиться (); // предотвращаем завершение потоков t2 . присоединиться (); т3 . присоединиться (); т4 . присоединиться (); т5 . присоединиться (); } Другой подход состоит в том, чтобы гарантировать, что философ может взять только обе вилки или не взять ни одной, введя арбитра вместо циклического ожидания, например, официанта. Чтобы взять вилки, философ должен спросить разрешения у официанта. Официант дает разрешение только одному философу за раз, пока тот не возьмет в руки обе вилки. Всегда можно положить вилку. Официант может быть реализован как мьютекс. Помимо введения новой центральной сущности (официанта), этот подход может привести к уменьшению параллелизма: если философ ест, а один из его соседей запрашивает вилки, все остальные философы должны ждать, пока этот запрос не будет выполнен, даже если вилки для них все еще доступны.
Решение, предложенное Уильямом Столлингсом [7], состоит в том, чтобы позволить максимум n-1 философам сесть за стол в любое время. Последнему философу пришлось бы ждать (например, с помощью семафора), пока кто-нибудь закончит обедать, прежде чем он «сядет» и запросит доступ к любой вилке. Это сводит на нет циклическое ожидание, гарантируя, что хотя бы один философ всегда может получить обе вилки, что позволяет системе развиваться.
В 1984 году К. Мани Чанди и Дж. Мисра [8] предложили другое решение проблемы обедающих философов, позволяющее произвольным агентам (с номерами P 1 , ..., P n ) бороться за произвольное количество ресурсов, в отличие от Решение Дейкстры. Он также полностью распределен и не требует никаких центральных полномочий после инициализации. Однако это нарушает требование, чтобы «философы не разговаривали друг с другом» (из-за сообщений-запросов).
Это решение также обеспечивает высокую степень параллелизма и решит сколь угодно большую проблему.
Это также решает проблему голодания. Этикетки «чистый/грязный» служат способом отдать предпочтение наиболее «голодным» процессам и поставить в невыгодное положение процессы, которые только что «съели». Их решение можно сравнить с решением, в котором философам не разрешается есть дважды подряд, не позволяя другим пользоваться вилками между ними. Решение Чанди и Мисры более гибкое, но в нем есть элемент, тяготеющий в этом направлении.
В своем анализе они выводят систему уровней предпочтений на основе распределения вилок и их чистых/грязных состояний. Они показывают, что эта система может описывать ориентированный ациклический граф , и если это так, то операции в их протоколе не могут превратить этот граф в циклический. Это гарантирует, что тупиковая ситуация не возникнет, поскольку исключает циклическое ожидание. Однако если система инициализирована в идеально симметричном состоянии, как все философы, держащие левую вилку, то граф с самого начала является циклическим, и их решение не может предотвратить тупик. Инициализация системы так, чтобы у философов с более низкими идентификаторами были грязные вилки, гарантирует, что граф изначально ацикличен.