(C) Dining Philosophers - How to make concurrent threads wait till a condition is satisfied?

Question

I am a beginner and I was implementing Dining Philosopher's problem. However, I ran across an issue. In my philosopher() function, I want my other threads to wait till the right and left chopsticks are available for them to use. How should I implement this? Currently, the program simply terminates after 2 philosophers are done eating without waiting for the others to eat

I've already tried :

• Using mutex to lock the shared variables in the philosopher() function and although it makes sure that no philosopher goes hungry, using this approach means giving up concurrency (only one philosopher can eat at a time even though there are chopsticks available for other philosophers to use)
• Using sleep() function in my while-loop but it doesn't work either

Any help is appreciated, thanks!

CODE

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h> 
#include <stdlib.h>

#define NUM 5  // Number of Philosophers
sem_t chopSticks[NUM]; // binary semaphore for each chopstick
sem_t mutex;
int philNo[NUM] = {0, 1, 2, 3, 4};

void* philosopher(void*);

int main()
{
    int semValue;
    pthread_t threadId[NUM]; // 5 concurrent threads for 5 philsophers
    sem_init(&mutex, 0, 1);
    for(int i=0; i< NUM; i++)
        sem_init(&chopSticks[i], 0, 1); 
    
    for(int i=0; i< NUM; i++)
    {
        pthread_create(&threadId[i], NULL, philosopher, (void*) &philNo[i]);
        printf("\nPhilosopher %d is thinking", i+1);
    }
    
    for(int i=0; i< NUM; i++)
        pthread_join(threadId[i], NULL);

return 0;
}

void* philosopher(void* philNo)
{
    int n = *(int*) philNo;
    int rightValue, leftValue;
    
    int left = (n+4) % NUM; 
    int right = (n+1) % NUM; 
    sem_getvalue(&chopSticks[left], &leftValue);
    sem_getvalue(&chopSticks[right], &rightValue);
    
    //sem_wait(&mutex);
    /* while(leftValue != 1 && rightValue != 1)
    {
        wait for the left and right chopsticks to be free
        How should I implement this?
    } */
        
    if(leftValue == 1 && rightValue == 1) // if both left and right chopSticks are free then start eating
    {
        sem_wait(&chopSticks[left]);
        sem_wait(&chopSticks[right]);
        printf("\nPhilosopher %d has taken Chopstick-%d and Chopstick-%d", n+1, left+1, right+1);
        printf("\nPhilosopher %d is Eating", n+1);
        sleep(1);
        sem_post(&chopSticks[left]);
        sem_post(&chopSticks[right]);
        printf("\nPhilosopher %d finished eating", n+1);
        printf("\nPhilosopher %d has put down chopstick-%d and chopstick-%d", n+1, left+1, right+1);
        
    }
    //sem_post(&mutex);
}

Answer 1

You can not have sempahore per fork on the dining table. This is the classic mistake that will lead you to the deadlock situation. Imagine all the philosophers simultaneously pick up the left fork your sempahore implementation will allow that, but after that point no one will be able to pick up the right fork, because none is available and all threads will indefinitely block.

The only solution that will work is a philosopher will not pickup any fork till both the left & right hand forks are available (i.e. neither neighbor is eating at the same time.)

The philosopher’s routine is: 0. Each philosopher will have state associated with her. The state is referred by the neighbours to find out what the philosopher is doing.

1. Spend time thinking. State of the philosopher is THINKING.
2. Philosopher becomes hungry, state of the philosopher is HUNGRY.
3. Check if you can pickup the left fork and right fork. (i.e. make sure left neighbour & right neighbour’s state is not EATING.) If either of fork is not available block till they become available.
4. When both forks are available change state to EATING, pickup the forks and start eating.
5. When your eating is done. Put down the left fork, check if your left neighbour is blocked for the fork you’re putting down, if she is wake her up to start eating. Then put down the right fork, check if your right neighbour is blocked for the fork you’re putting down, if she is wake her up to start eating.
6. Goto step 1.

Pseudo oop code is as below:

#define N 5
#define LEFT(i) (i-1)%N
#define RIGHT(i) (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
 
class DinningPhilosopher {
public:
    DinningPhilosopher();
    ~DinningPhilosopher();
    void
    philosopherRoutine(
        IN byte i
        );
 
private:
    byte m_state[N];
    Semaphore *m_sem[N];
    Mutex *m_mutex;
 
    void
    takeForks(
        IN byte i
        );
 
    void
    putForks(
        IN byte i
        );
 
    void
    testForkAvailability(
        IN byte i
        );
};
 
DinningPhilosopher::DinningPhilosopher()
{
    // All philosopher's are thinking initially.
    for (int i=0; i<N; i++) {
        m_state[i] = THINKING;
    }
    for (int i=0; i<N; i++) {
        m_sem[i] = new Semaphore(0);
    }
    m_mutex = new Mutex();
}
 
// N threads will be spawned, one for each philosopher.
// Argument i is philosopher id between (0,N)
void
DinningPhilosopher::philosopherRoutine(
    IN byte i
    )
{
    while(true) {
        continueThinking();
        takeForks(i);
        continueEating();
        putForks(i);
    }
}
 
void
DinningPhilosopher::takeForks(
    IN byte i
    )
{
    m_mutex->lock();
        // Announce to neighbours you're HUNGRY.
        m_state[i] = HUNGRY;
        // Test if left fork & right forks are available.
        // If available announce neighbours you're EATING.
        // so they don't pick up forks you already claimed.
        testForkAvailability(i);
    m_mutex->unlock();
    // If you are not yet EATING,
    // block till required forks are available.
    // Section A.
    m_sem[i]->wait();
}
 
void
DinningPhilosopher::testForkAvailability(
    IN byte i
    )
{
    // Note that m_mutex was locked before calling this function
    // Thread has exclusive access to execute this function.
    if (m_state[LEFT(i)] != EATING && // your left fork is available
        m_state[RIGHT(i)] != EATING && // your right fork is available
        m_state[i] == HUNGRY // and you want to start eating.
        ) {
        // Announce neighbours you started eating.
        m_state[i] = EATING;
        // Fork availability is passed.
        // Make sure you're not blocked at "Section A"
        // in function takeForks()
        m_sem[i]->post();
    }
}
 
void
DinningPhilosopher::putForks(
    IN byte i
    )
{
    m_mutex->lock();
        // Announce to neighbours you're done EATING.
        m_state[i] = THINKING;
        // Put down the left fork,
        // If your left neighbour is blocked at "Section A"
        // of function takeForks().
        // Allow him to unblock to start eating.
        testAvailability(LEFT(i));
        // Put down the right fork.
        testAvailability(RIGHT(i));
    m_mutex->unlock();
}

Check out link below: https://codeistry.wordpress.com/2018/04/06/dinning-philosophers-problem/

Answer 2

I am a beginner and I was implementing Dining Philosopher's problem. However, I ran across an issue. In my philosopher() function, I want my other threads to wait till the right and left chopsticks are available for them to use. How should I implement this?

I've already tried :

• Using mutex to lock the shared variables in the philosopher() function and although it makes sure that no philosopher goes hungry, using this approach means giving up concurrency (only one philosopher can eat at a time even though there are chopsticks available for other philosophers to use)

You absolutely do need at least one mutex or similar synchronization object, because your threads need to access shared data (the states of the chopsticks, or an equivalent). Shared data must be accessed only in a critical section protected by an appropriate synchronization object.

However, you don't necessarily need to hold the mutex locked between such accesses, and often you want to avoid doing so, in order that other threads will have the chance to run.

• Using sleep() function in my while-loop but it doesn't work either

As I wrote in comments, sleep() is not a synchronization function. It might have a role to play in a solution, but not in inter-thread activities.

The key thing to recognize for the dining philosophers problem is that if you want philosophers eating concurrently without having to orchestrate the whole meal in detail, then each philosopher must be able to try multiple times to pick up chopsticks until they succeed, without preventing any other philosophers from eating in the meantime.

Additionally, it is counterproductive for a thread to just try over and over when it has no reason to think that anything has changed since its last attempt.

When a thread needs to wait to proceed until some data-dependent condition is satisfied, you should immediately consider using a condition variable. Sometimes there are reasonable alternatives, but condition variables are the Swiss army knife for these situations.

Condition variables are used together with mutexes -- a mutex is used to protect the non-atomic variables by which each thread will determine whether it can proceed, and if the thread determines that it must wait, the CV assists it in both allowing other threads to lock the mutex while it waits, and in receiving notification that it should check again. This should always be performed in a loop because the thread might determine after waking that conditions still aren't right for it to move forward.

There are several ways to implement that in the Dining Philosophers problem. You could use a separate condition variable for each chopstick, all with the same mutex, but it would be simpler to use just one mutex and one CV:

• When one of the philosophers decides that he is ready to eat, he locks the mutex, and checks whether both the chopsticks he needs are available.

  • If so, he picks them up, releases the mutex, and proceeds to eat.

  • If not, then he waits for the condition variable to be signaled by another thread. The mutex is automatically released during this wait, and regained before the thread resumes from it. When the thread resumes, it loops back to check the chopsticks again.

  For example (error checking elided for clarity):

  pthread_mutex_lock(&mutex);
  while(chopsticks[left] || chopsticks[right]) {
      pthread_cond_wait(&cv, &mutex);
  }
  chopsticks[left] = 1;
  chopsticks[right] = 1;
  pthread_mutex_unlock(&mutex);
  

• When the philosopher is done eating, he locks the mutex, puts down the chopsticks, releases the mutex, and then signals all the threads waiting on the CV, so that they will check again whether they can proceed.

  For example:

  pthread_mutex_lock(&mutex);
  chopsticks[left] = 0;
  chopsticks[right] = 0;
  pthread_mutex_unlock(&mutex);
  pthread_cond_broadcast(&cv);
  

Note also that since the chopstick states are being protected via a mutex, there is no advantage to using semaphores to model them. The example code above assumes an ordinary array of _Bool or some other integer type, initialized with all zeroes.