Dining Philosophers Problem in Operating System (OS)

Dining Philosophers in Operating System

Dining Philosophers essentially is a process synchronization example and helps understand how we can simultaneously utilise common resources of multiple processes together.

Dining

Entities –

  • Noodles/Rice
  • Chopsticks
  • Philosophers

At any given instance, a philosopher will do –

  • Thinking
  • Eating
  • Whenever the philosophers want to eat. He obviously will use two chopsticks together.
    • So to eat both chopsticks on his right and left must be free.
  • Whenever he is thinking
    • He must put down both the chopsticks back at the table.
Dining Philosophers Problem OS Operating System

Rules and Solution

If a philosopher decides to eat

  • He first will wait for the chopstick on his left to be free.
  • If the left chopstick is already free he will pick that up.
  • Then he will wait for the chopstick on his right
  • And once the right chopstick is also free he will pick that up too and do the eating.
Dining Philosopher Problem In OS

Algorithm

while(TRUE) 
{
// mod is used because if i=5,
// next chopstick is 1 (dining table is circular)
wait(stick[i]); wait(stick[(i+1) % 5]); /* eat */

signal(stick[i]); signal(stick[(i+1) % 5]);
/* think */ }

Some of the ways to avoid deadlock are as follows:

Four Philosopher

There should be at most four philosophers on the table. In this way one chopstick will be extra if all decide to eat together. This one chopstick then can be used by one of our philosopher and he will finish his eating and then two chopsticks are available then 1 more can eat and so on…

Even Odd

Solving with even and odd techniques, even philosopher must pick his right and off must pick his left.

Coordination

Only and only if both chopsticks are available at the same time for a philosopher then only he should pick them up,

Code in C

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define num_philopsophers 5
#define num_chopsticks 5

void dine(int n);
pthread_t philosopher[num_philopsophers];
pthread_mutex_t chopstick[num_chopsticks];

int main()
{
    // Define msg and status_message
    int status_message;
    void *msg;
    
    // Initialise the semaphore array
    for (int i = 1; i <= num_chopsticks; i++)
    {
        status_message = pthread_mutex_init(&chopstick[i], NULL);
        
        // Checking if the mutex was initialised successfully
        if (status_message == -1)
        {
            printf("\n Mutex initialization failed");
            exit(1);
        }
    }
    
    // Run the philosopher Threads using *dine() function
    for (int i = 1; i <= num_philopsophers; i++)
    {
        status_message = pthread_create(&philosopher[i], NULL, (void *)dine, (int *)i);
        if (status_message != 0)
        {
            printf("\n Thread creation error \n");
            exit(1);
        }
    }
    // Wait for all philosophers threads to complete executing 
    // (finish dining) before closing the program
    for (int i = 1; i <= num_philopsophers; i++)
    {
        status_message = pthread_join(philosopher[i], &msg);
        if (status_message != 0)
        {
            printf("\n Thread join failed \n");
            exit(1);
        }
    }
    
    // Destroy the chopstick Mutex array
    for (int i = 1; i <= num_chopsticks; i++)
    {
        status_message = pthread_mutex_destroy(&chopstick[i]);
        if (status_message != 0)
        {
            printf("\n Mutex Destroyed \n");
            exit(1);
        }
    }
    return 0;
}

// dine method
void dine(int n)
{
    printf("\nPhilosopher % d is thinking ", n);
    
    // picking up the left chopstick (wait)
    pthread_mutex_lock(&chopstick[n]);
    
    // picking up the right chopstick (wait)
    pthread_mutex_lock(&chopstick[(n + 1) % num_chopsticks]);
    
    // both chopstick picked now starts eating
    
    printf("\nPhilosopher % d is eating ", n);
    sleep(3);
    
    // places the left chopstick down (signal)
    pthread_mutex_unlock(&chopstick[n]);
    
    // places the  the right chopstick down (signal)
    pthread_mutex_unlock(&chopstick[(n + 1) % num_chopsticks]);
    
    //  eating finishes
    printf("\nPhilosopher % d Finished eating ", n);
}