✖


Jump to content

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

Иллюстрация проблемы обедающих философов. У каждого философа есть миска спагетти, и он может достать две вилки.

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

Первоначально он был сформулирован в 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 state

std::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 forks
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) 
// 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 философам сесть за стол в любое время. Последнему философу пришлось бы ждать (например, с помощью семафора), пока кто-нибудь закончит обедать, прежде чем он «сядет» и запросит доступ к любой вилке. Это гарантирует, что хотя бы один философ всегда сможет приобрести обе вилки, что позволит системе развиваться.

Решение Chandy/Misra [ править ]

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Дейкстра, Эдсгер В. EWD-1000 (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция )
  2. ↑ Перейти обратно: Перейти обратно: а б Х. Диас; И. Рамос (1981). Формализация концепций программирования: Международный коллоквиум, Пенискола, Испания, 19–25 апреля 1981 г. Труды . Биркхойзер. стр. 323 , 326 . ISBN  978-3-540-10699-9 .
  3. ^ Хоар, ЦАР (2004) [первоначально опубликовано в 1985 году издательством Prentice Hall International]. «Обмен последовательными процессами» (PDF) . используя csp.com.
  4. ↑ Перейти обратно: Перейти обратно: а б Таненбаум, Эндрю С. (2006), Операционные системы – проектирование и внедрение, 3-е издание [Глава: 2.3.1 Проблема обедающих философов] , Pearson Education, Inc.
  5. ^ Дейкстра, Эдсгер В. EWD-310 (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция )
  6. ^ Таненбаум, Эндрю С. (2006), Операционные системы – проектирование и внедрение, 3-е издание [Глава: 3.3.5 Предотвращение тупиковых ситуаций] , Pearson Education, Inc.
  7. ^ Столлингс, Уильям (2018). Операционные системы: внутреннее устройство и принципы проектирования (9-е изд.). Харлоу, Эссекс, Англия: Пирсон . п. 310. ИСБН  978-1-292-21429-0 . OCLC   1009868379 .
  8. ^ Чанди, КМ; Мисра, Дж. (1984). Проблема пьющих философов . Транзакции ACM в языках и системах программирования.

Библиография [ править ]

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

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dining_philosophers_problem&oldid=1225930123"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e41b6bf170fd700d92f75f0834e16ddc__1716814380
URL1:https://arc.ask3.ru/arc/aa/e4/dc/e41b6bf170fd700d92f75f0834e16ddc.html
Заголовок, (Title) документа по адресу, URL1:
Dining philosophers problem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)