Dining Philosophers Problem in OS

quiz
Challenge Inside! : Find out where you stand! Try quiz, solve problems & win rewards!

Overview

Dining Philosophers Problem in OS is a classical synchronization problem in the operating system. With the presence of more than one process and limited resources in the system the synchronization problem arises. If one resource is shared between more than one process at the same time then it can lead to data inconsistency.

Scope

  • The article discusses the need of synchronisation in operating system, the use of semaphores and critical section.
  • We also discuss the Dining Philosophers in OS Problem and approach to solve it, algorithm and code explanation.
  • We also consider drawbacks of the solution of Dining Philosophers Problem, and how it can be improved.

Dining Philosophers Problem in OS

Consider two processes P1 and P2 executing simultaneously, while trying to access the same resource R1, this raises the question who will get the resource and when? This problem is solved using process synchronisation.

The act of synchronising process execution such that no two processes have access to the same associated data and resources is referred as process synchronisation in operating systems.

It's particularly critical in a multi-process system where multiple processes are executing at the same time and trying to access the very same shared resource or data.

This could lead to discrepancies in data sharing. As a result, modifications implemented by one process may or may not be reflected when the other processes access the same shared data. The processes must be synchronised with one another to avoid data inconsistency.

Dining Philosophers Problem

And the Dining Philosophers Problem is a typical example of limitations in process synchronisation in systems with multiple processes and limited resource. According to the Dining Philosopher Problem, assume there are K philosophers seated around a circular table, each with one chopstick between them. This means, that a philosopher can eat only if he/she can pick up both the chopsticks next to him/her. One of the adjacent followers may take up one of the chopsticks, but not both.

For example, let’s consider P0, P1, P2, P3, and P4 as the philosophers or processes and C0, C1, C2, C3, and C4 as the 5 chopsticks or resources between each philosopher. Now if P0 wants to eat, both resources/chopstick C0 and C1 must be free, which would leave in P1 and P4 void of the resource and the process wouldn't be executed, which indicates there are limited resources(C0,C1..) for multiple processes(P0, P1..), and this problem is known as the Dining Philosopher Problem.

Dining Philosophers Problem

:::

The Solution of the Dining Philosophers Problem

The solution to the process synchronization problem is Semaphores, A semaphore is an integer used in solving critical sections.

The critical section is a segment of the program that allows you to access the shared variables or resources. In a critical section, an atomic action (independently running process) is needed, which means that only single process can run in that section at a time.

Semaphore has 2 atomic operations: wait() and signal(). If the value of its input S is positive, the wait() operation decrements, it is used to acquire resource while entry. No operation is done if S is negative or zero. The value of the signal() operation's parameter S is increased, it used to release the reource once critical section is executed at exit.

Here's a simple explanation of the solution:

void Philosopher  
{
  while(1)  
  {
    //  Section where the philosopher is using chopstick
    wait(use_resource[x]);  
    wait(use_resource[(x + 1) % 5]);  
    //  Section where the philosopher is thinking
    signal(free_resource[x]);  
    signal(free_resource[(x + 1) % 5]);  
  }  
}  

Explanation:

  • The wait() operation is implemented when the philosopher is using the resources while the others are thinking. Here, the threads use_resource[x] and use_resource[(x + 1) % 5] are being executed.
  • After using the resource, the signal() operation signifies the philosopher using no resources and thinking. Here, the threads free_resource[x] and free_resource[(x + 1) % 5] are being executed.

To model the Dining Philosophers Problem in a C program we will create an array of philosophers (processes) and an array of chopsticks (resources). We will initialise the array of chopsticks with locks to ensure mutual exclusion is satisfied inside the critical section.

We will run the array of philosophers in parallel to execute the critical section (dine ()), the critical section consists of thinking, acquiring two chopsticks, eating and then releasing the chopsticks.

C program:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM_PHILOSOPHERS 5
#define NUM_CHOPSTICKS 5

void dine(int n);
pthread_t philosopher[NUM_PHILOSOPHERS];
pthread_mutex_t chopstick[NUM_CHOPSTICKS];

int main()
{
  // Define counter var i and status_message
  int i, status_message;
  void *msg;

  // Initialise the semaphore array
  for (i = 1; i <= NUM_CHOPSTICKS; i++)
  {
    status_message = pthread_mutex_init(&chopstick[i], NULL);
    // Check if the mutex is initialised successfully
    if (status_message == -1)
    {
      printf("\n Mutex initialization failed");
      exit(1);
    }
  }

  // Run the philosopher Threads using *dine() function
  for (i = 1; i <= NUM_PHILOSOPHERS; 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 (i = 1; i <= NUM_PHILOSOPHERS; 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 (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;
}
void dine(int n)
{
  printf("\nPhilosopher % d is thinking ", n);

  // Philosopher picks up the left chopstick (wait)
  pthread_mutex_lock(&chopstick[n]);

  // Philosopher picks up the right chopstick (wait)
  pthread_mutex_lock(&chopstick[(n + 1) % NUM_CHOPSTICKS]);

  // After picking up both the chopstick philosopher starts eating
  printf("\nPhilosopher % d is eating ", n);
  sleep(3);

  // Philosopher places down the left chopstick (signal)
  pthread_mutex_unlock(&chopstick[n]);

  // Philosopher places down the right chopstick (signal)
  pthread_mutex_unlock(&chopstick[(n + 1) % NUM_CHOPSTICKS]);

  // Philosopher finishes eating
  printf("\nPhilosopher % d Finished eating ", n);
} 

Output

Philosopher  2 is thinking 
Philosopher  2 is eating 
Philosopher  3 is thinking 
Philosopher  5 is thinking 
Philosopher  5 is eating 
Philosopher  1 is thinking 
Philosopher  4 is thinking 
Philosopher  4 is eating 
Philosopher  2 Finished eating 
Philosopher  5 Finished eating 
Philosopher  1 is eating 
Philosopher  4 Finished eating 
Philosopher  3 is eating 
Philosopher  1 Finished eating 
Philosopher  3 Finished eating

Let's Understand How the Above Code is Giving a Solution to the Dining Philosopher Problem?

We start by importing the libraries pthread for threads and semaphore for synchronization. And create an array of 5 p_threads representing the philosophers. Create an array of 5 mutexes representing the chopsticks.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM_PHILOSOPHERS 5
#define NUM_CHOPSTICKS 5

void dine(int n);
pthread_t philosopher[NUM_PHILOSOPHERS];
pthread_mutex_t chopstick[NUM_CHOPSTICKS];

The pthread library is used for multi-threaded programming which allows us to run parallel sub-routines using threads. The <semaphore.h> header is used to perform semaphore operations.

We initialise the counter i and status message variable as int and a pointer msg, and intialise the semaphore array.

int main()
{
  // Define counter var i and status_message
  int i, status_message;
  void *msg;

  // Initialise the semaphore array
  for (i = 1; i <= NUM_CHOPSTICKS; i++)
  {
    status_message = pthread_mutex_init(&chopstick[i], NULL);
    // Check if the mutex is initialised successfully
    if (status_message == -1)
    {
      printf("\n Mutex initialization failed");
      exit(1);
    }
  }

We create the philosopher threads using pthread_create and pass a pointer to the dine function as the subroutine and a pointer to the counter variable i.

  pthread_t philosopher[5];

  // Run the philosopher Threads using *dine() function
  for (i = 1; i <= NUM_PHILOSOPHERS; i++)
  {
    status_message = pthread_create(&philosopher[i], NULL, (void *)dine, (int *)i);
    if (status_message != 0)
    {
      printf("\n Thread creation error \n");
      exit(1);
    }
  }

All the philosophers start by thinking. We pass chopstick(n) (left) to pthread_mutex_lock to wait and acquire lock on it.

Then the thread waits on the right((n+1) % NUM_CHOPSTICKS) chopstick to acquire a lock on it (pick it up).

void dine(int n)
{
  printf("\nPhilosopher % d is thinking ", n);

  // Philosopher picks up the left chopstick (wait)
  pthread_mutex_lock(&chopstick[n]);

  // Philosopher picks up the right chopstick (wait)
  pthread_mutex_lock(&chopstick[(n + 1) % NUM_CHOPSTICKS]);

When the philosopher successfully acquires lock on both the chopsticks, the philosopher starts dining (sleep(3)).

 // After picking up both the chopstick philosopher starts eating
 printf("\nPhilosopher % d is eating ", n);
 sleep(3);

Once the philosopher finishes eating, we call pthread_mutex_unlock on the left chopstick (signal) thereby freeing the lock. Then proceed to do the same on the right chopstick.

  // Philosopher places down the left chopstick (signal)
  pthread_mutex_unlock(&chopstick[n]);

  // Philosopher places down the right chopstick (signal)
  pthread_mutex_unlock(&chopstick[(n + 1) % NUM_CHOPSTICKS]);

  // Philosopher finishes eating
  printf("\nPhilosopher % d Finished eating ", n);
}

We loop through all philosopher threads and call pthread_join to wait for the threads to finish executing before exiting the main thread.

for (i = 1; i <= NUM_PHILOSOPHERS; i++)
  {
    status_message = pthread_join(philosopher[i], &msg);
    if (status_message != 0)
    {
      printf("\n Thread join failed \n");
      exit(1);
    }
  }

We loop thorough the chopstick array and call pthread_mutex_destroy to destroy the semaphore array.

for (i = 1; i <= NUM_CHOPSTICKS; i++)
  {
    status_message = pthread_mutex_destroy(&chopstick[i]);
    if (status_message != 0)
    {
      printf("\n Mutex Destroyed \n");
      exit(1);
    }
  }

The Drawback of the Above Solution of the Dining Philosopher Problem

Through the above discussion we established that no two nearby philosophers can eat at the same time using the aforesaid solution to the dining philosopher problem. The disadvantage of the above technique is that it may result in a deadlock situation. This occurs when all of the philosophers choose their left chopstick at the same moment, resulting in a stalemate scenario in which none of the philosophers can eat, and hence deadlock will happen.

We can also avoid deadlock through the following methods in this scenario -

  1. The maximum number of philosophers at the table should not exceed four, let’s understand why four processes is important:

    • Chopstick C4 will be accessible for philosopher P3, therefore P3 will begin eating and then set down both chopsticks C3 and C4, indicating that semaphore C3 and C4 will now be increased to one.
    • Now that philosopher P2, who was holding chopstick C2, also has chopstick C3, he will place his chopstick down after eating to allow other philosophers to eat.
  2. The four starting philosophers (P0, P1, P2, and P3) must pick the left chopstick first, then maybe the right, even though the last philosopher (P4) should pick the right chopstick first, then the left. Let's have a look at what occurs in this scenario:

    • This will compel P4 to hold his right chopstick first since his right chopstick is C0, which is already held by philosopher P0 and whose value is set to 0, i.e. C0 is already 0, trapping P4 in an unending loop and leaving chopstick C4 empty.
    • As a result, because philosopher P3 has both left C3 and right C4 chopsticks, it will begin eating and then put down both chopsticks once finished, allowing others to eat, thereby ending the impasse.
  3. If the philosopher is at an even position, he/she should choose the right chopstick first, followed by the left, and in an odd position, the left chopstick should be chosen first, followed by the right.

  4. Only if both chopsticks (left and right) are accessible at the same time should a philosopher be permitted to choose his or her chopsticks.

Conclusion

  • Process synchronization is defined as no two processes have access to the same associated data and resources.
  • The Dining philosopher problem is an example of process synchronization problem.
  • Philosopher is an analogy for process and chopstick for resources, we can try to solve process synchronization problems using this.
  • The solution of Dining Philosopher problem focuses on the use of semaphores.
  • No two nearby philosophers can eat at the same time using the aforesaid solution to the dining philosopher problem, and this situation causes a deadlock, this is a drawback of the Dining philosopher problem.
Free Courses by top Scaler instructors
certificate icon
Certificates
Operating System Tutorial
This program includes modules that cover the basics to advance constructs of Operating System Tutorial. The highly interactive and curated modules are designed to help you become a master of this language.'
If you’re a learning enthusiast, this is for you.
Module Certificate
Criteria
Upon successful completion of all the modules in the hub, you will be eligible for a certificate.
You need to sign in, in the beginning, to track your progress and get your certificate.