Search code examples
c++multithreadingmutexsemaphoredining-philosopher

How is this solution for dining philosophers problem (dpp) working? Mutex and semaphores

I am trying to solve the dining philosophers problem (the problem: https://en.wikipedia.org/wiki/Dining_philosophers_problem) and I found the solution with code below. Solution uses semaphores and one mutex. I implemented busy waiting simple semaphores myself, cause C++ does not provide semaphores. I can't understand what's the purpose of mutex locking in take_forks and put_forks functions.

I tried to find the answer to my question, but I couldn't. So I am asking in stackoverflow.

My questions are:

  1. What's the purpose of mutex locking in take_forks and put_forks functions? (What can cause for race condition to occur?)
  2. What's the name of this solution? Is this the arbitration solution?

Here's my code

#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);
    }
}

I expected that mutex locking must be in test function, because that's the only cause for race condition that I found.

Any answers and suggestions are appreciated! Thanks!

Solution

  • I found answer to my question.

    This solution is introduced by A. Tanenbaum and is one of several solutions that are called arbitration. By this approach it is guaranteed that a philosopher can only pick up either forks or none by introducing an arbitrator, e.g., a waiter.In order to pick up the forks, a philosopher must ask permission of the waiter. The waiter gives permission to only one philosopher at a time until he has picked up both his forks. The waiter can be implemented as a mutex. Thus, the operation of checking and updating the array is atomic and exclusive access to forks is guaranteed. (That's the purpose of mutex)

    Several references