Как работает это решение для проблемы обедающих философов (dpp)?Мьютекс и семафоры - PullRequest
Новая
       65

Как работает это решение для проблемы обедающих философов (dpp)?Мьютекс и семафоры

0 голосов
/ 14 июня 2019

Я пытаюсь решить проблему столовых философов ( проблема: https://en.wikipedia.org/wiki/Dining_philosophers_problem), и я нашел решение с кодом ниже. Решениеиспользует семафоры и один мьютекс. Я сам реализовал простые семафоры ожидания ожидания, потому что C ++ не предоставляет семафоров. Я не могу понять, какова цель блокировки мьютекса в функциях take_forks и put_forks.

Я пыталсячтобы найти ответ на мой вопрос, но я не смог. Поэтому я спрашиваю в stackoverflow.

Мои вопросы:

  1. Какова цель блокировки мьютекса в take_forksи put_forks функции? (Что может вызвать возникновение состояния гонки?)
  2. Как называется это решение? Это арбитражное решение?

Вот мой код 

#include <mutex>
#include <thread>

#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2

typedef int sem_t;
void sem_up(sem_t* semaphore) {
    (*semaphore)++;
}
void sem_down(sem_t* semaphore) {
    while (*semaphore == 0) {}
    (*semaphore)--;
}

std::mutex mutualExclusion;
char philosopherState[N] = {THINKING};
sem_t philosopherSemaphore[N] = { 0 };

void test(short i) {
    if (philosopherState[i] == HUNGRY && philosopherState[(i + 1) % N] != EATING && philosopherState[(i + N - 1) % N] != EATING) {
        philosopherState[i] = EATING;
        sem_up(&philosopherSemaphore[i]);
    }
}

void think(short p) {
    //some code
}
void eat() {
        //some code
}

void take_forks(short i) {
    ::mutualExclusion.lock();
    philosopherState[i] = HUNGRY;
    test(i);
    ::mutualExclusion.unlock();
    sem_down(&philosopherSemaphore[i]);
}
void put_forks(short i) {
    ::mutualExclusion.lock();
    philosopherState[i] = THINKING;
    test((i + 1) % N);
    test((i + N - 1) % N);
    ::mutualExclusion.unlock();
}

void philosopher(short i) {
    while (1) {
        think();
        take_forks(i);
        eat();
        put_forks(i);
    }
}

Я ожидал, что блокировка мьютекса должна быть в функции test, потому что это единственная причина состояния гонки, которую я нашел.

Любые ответы и предложения приветствуются! Спасибо!

1 Ответ

0 голосов
/ 14 июня 2019

Я нашел ответ на свой вопрос.

Это решение введено А. Таненбаумом и является одним из нескольких решений, называемых арбитражем.При таком подходе гарантируется, что философ может подобрать либо вил, либо ни одного , введя арбитра, например, официанта . Чтобы забрать вилки, философ должен спросить разрешения у официанта.Официант дает разрешение только одному философу за раз, пока он не поднимет обе свои вилки.Официант может быть реализован как мьютекс.Таким образом, операция проверки и обновления массива является атомарной и эксклюзивный доступ к вилкам гарантирован.(Это цель мьютекса)

Несколько ссылок

...