Dining Philosophers Problem in Operating System (OS)

Dining Philosophers in Operating System

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

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.

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.

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,

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 */ }

Code in C

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription