Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: May 23, 2024
Difficulty: Medium

Dining Philosophers Problem in OS

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

The Dining Philosophers Problem is a classic synchronization and concurrency problem in computer science and operating systems. It illustrates issues related to resource allocation and deadlock prevention in a multi-process environment. 

Dining Philosophers Problem in OS

There is a very famous problem named Dining Philosophers problem, which we will study dining philosophers problem in c with implementation in this article. 

What is the Dining Philosopher Problem?

The dining philosopher's problem is a version of the classical synchronization problem, in which five philosophers sit around a circular table and alternate between thinking and eating. A bowl of noodles and five forks for each philosopher are placed at the center of the table.

There are certain conditions a philosopher must follow: 

  1. A philosopher must use both their right and left forks to eat. 
  2. A philosopher can only eat if both of his or her immediate left and right forks are available. If the philosopher's immediate left and right forks are not available, the philosopher places their (either left or right) forks on the table and resumes thinking.


Note: There are many variations of this problem, such as that instead of a fork, a chopstick can be used, and instead of noodles, a rice bowl can be used, but the logic and solution of the problem will be the same.

The dining philosopher is a standard synchronization problem, which illustrates a vast class of concurrency control concerns.
 

Dining Philosopher's Problem

Let's look at the Dining Philosopher's Problem with the code below. The image above is a guide to help you completely comprehend the problem. P0, P1, P2, P3, and P4 symbolize the five Philosophers, whereas F0, F1, F2, F3, and F4 represent the five Forks.

void Philosopher  
{  
 while(1)  
  {  
  take_fork[i];  
  take_fork[ (i+1) % 5] ;  
    
  EATING THE NOODLE  
    
  put_fork[i];  
  put_fork[ (i+1) % 5] ;  
    
   THINKING  
  }  
}  

Let's discuss the above code:

If Philosopher P0 wants to eat, it will enter the Philosopher() function and perform take_fork[ i ]; this will hold F0 fork, and then it will execute take_fork[(i+1) % 5] this will hold F1 fork (because i = 0, therefore (0 + 1) % 5 = 1).

Similarly, if Philosopher P1 wishes to eat, it will enter the Philosopher() function and run take_fork[ i ]; this holds F1 fork, and then it will execute take_fork[(i+1) % 5] this holds F2 fork (because i = 1, thus (1 + 1) % 5 = 2).

But Practically, fork F1 is not available as it has already been taken by philosopher P0; hence the above code generates problems and produces race conditions. 

Logically, this problem does not exist in a real-life scenario. The philosophers could have requested a few extra pairs of chopsticks or eaten with their hands.😆

Jokes aside, the dining philosopher's problem is an excellent example of explaining the concept of deadlock while resource sharing in an Operating System.

Let's look at the Semaphore Solution to Dining Philosopher:

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Semaphore Solution to Dining Philosopher Problem

A solution to the Dining Philosopher's Problem is to use a semaphore to represent a fork. 

What is a semaphore? 

Semaphore is simply a non-negative variable that is shared between threads. A semaphore is a signaling mechanism, and another thread can signal a thread waiting on a semaphore. 

For process synchronization, it employs two atomic operations: 

1) Wait and 

2) Signal.

Depending on how it is configured, a semaphore either allows or denies access to the resource.

A fork can be picked up by performing a wait operation on the semaphore and released by performing a signal operation on the semaphore.

The structure of the fork is an array of a semaphore which is represented as shown below -

semaphore F[5];

Initially, the elements of the semaphore F0,F1,F2,F3, and F4 are set to 1 since the forks are on the table. 

Let us now modify the above code by adding wait and signal operations: 

Pseudo Code

void Philosopher  
{  
 while(true)  
  {  
  wait( F[i] );  
  wait( F[ (i+1) % 5]);  
    
  // EATING THE NOODLE  
    
  signal( F[i] );  
  signal( F[ (i+1) % 5] ) ;  
    
   // THINKING  
  }  
}

In the above code, at first, the wait operation is performed on F[i] and F[ (i+1) % 5], which means that the ith philosopher has picked up the forks on his sides and started eating. 

After that, the signal operation is performed on F[i] and F[ (i+1) % 5], which means that the ith philosopher has eaten and put down the forks on his sides and then started thinking. 

Implementation in C

The below code is written in C Language, with that Pthread and semaphore libraries are used. 

Note: Below code requires installing the prerequisites libraries. Using an online Coding Ninjas compiler with the language selected as C language is recommended.

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

#define N 5
#define THINKING 2
#define HUNGRY 1
#define EATING 0
#define LEFT (num_of_philosopher + 4) % N
#define RIGHT (num_of_philosopher + 1) % N

int state[N];
int phil[N] = {0,1,2,3,4};

// sem_t is a typedef defined in the header file as (apparently) some variety of integer.
sem_t mutex;
sem_t S[N];

void test(int num_of_philosopher)
{
		if (state[num_of_philosopher] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) 
		{
			// state that eating
			state[num_of_philosopher] = EATING;

			sleep(2);

			printf("Philosopher %d takes fork %d and %d\n", num_of_philosopher +1, LEFT +1, num_of_philosopher +1);

			printf("Philosopher %d is Eating\n", num_of_philosopher +1);

			/* sem_post(&S[num_of_philosopher]) has no effect
  			during takefork
  			used to wake up hungry philosophers
  			during putfork */
			sem_post(&S[num_of_philosopher]);
	}
}

// take up Forks
void take_fork(int num_of_philosopher)
{

	sem_wait(&mutex);

	// state that hungry
	state[num_of_philosopher] = HUNGRY;

	printf("Philosopher %d is Hungry\n", num_of_philosopher +1);

	// eat if neighbours are not eating
	test(num_of_philosopher);

	sem_post(&mutex);

	// if unable to eat wait to be signalled
	sem_wait(&S[num_of_philosopher]);

	sleep(1);
}

// put down Forks
void put_fork(int num_of_philosopher)
{

	sem_wait(&mutex);

	// state that thinking
	state[num_of_philosopher] = THINKING;

	printf("Philosopher %d putting fork %d and %d down\n",num_of_philosopher +1, LEFT +1, num_of_philosopher +1);
	printf("Philosopher %d is thinking\n", num_of_philosopher +1);

	test(LEFT);
	test(RIGHT);

	sem_post(&mutex);
}

void* philosopher(void* num)
{

	while (1) 
	{
		int* i = num;

		sleep(1);

		take_fork(*i);

		sleep(0);

		put_fork(*i);
	}
}

int main()
{
	int i;
	pthread_t thread_id[N];

	// initialize the semaphores
	sem_init(&mutex,0,1);

	for (i =0; i < N; i++)

	sem_init(&S[i],0,0);

	for (i =0; i < N; i++) {

	// create philosopher processes
	pthread_create(&thread_id[i],NULL,philosopher, &phil[i]);

	printf("Philosopher %d is thinking\n", i +1);
    }

	for (i =0; i < N; i++)
	{
		pthread_join(thread_id[i],NULL);
	}
}

 

Output:

Output for Dining Philosopher Problem

Steps for the Dining Philosopher Problem solution using semaphores are as follows:

  1. In this step, we need to initialize a semaphore for each fork on the table. Each semaphore will represent the availability of a fork. In the starting, we will set all semaphores to 1, it shows that all forks are available.
     
  2. Each philosopher will be represented by a separate thread or process. Each philosopher has to follow the same set of steps. These steps include activities such as thinking, attempting to pick forks, eating, releasing forks, and repeating the cycle.
     
  3. Then we will start by thinking or performing any other activity not involving forks.
     
  4. Whenever a philosopher wants to eat, they need to pick the two adjacent forks. To pick a fork, the philosopher attempts to decrement the corresponding semaphore value. If the value of the semaphore is greater than 0, this will show the fork is available. Then philosopher proceeds to pick that fork. Otherwise, if the value of the semaphore is 0, this will show the fork is currently being used by another philosopher. Then philosopher waits (blocks) until the fork becomes available.
     
  5. Once a philosopher has successfully picked both forks, they can eat for a certain amount of time.
     
  6. After finishing eating, the philosopher releases both forks by incrementing the corresponding semaphore values. Then make forks available for other philosophers to use.
     
  7. The philosopher then goes back to thinking or performing other non-fork-related activities.
    Also see, Components of Operating System

The Drawback of the Above Solution of the Dining Philosopher Problem

  • Deadlock Possibility: This solution may still suffer from deadlock if all philosophers simultaneously pick up their left chopstick and wait indefinitely for the right one, leading to a deadlock situation.
  • Starvation: There's a possibility of starvation where a philosopher might not get access to both chopsticks if other philosophers consistently prioritize one of the chopsticks, preventing fair access to resources.
  • Unequal Access: The solution doesn't ensure equal access to resources for all philosophers, as some may have better chances of acquiring both chopsticks compared to others.
  • Complexity: Implementing and managing the solution can be complex, especially in distributed or multi-threaded environments, potentially leading to synchronization issues and bugs.
  • Performance Overhead: The solution may introduce performance overhead due to the need for synchronization mechanisms like locks or semaphores, impacting the overall efficiency of the system.
  • Resource Waste: In cases where philosophers hold onto chopsticks for extended periods without eating, resources may be wasted unnecessarily, reducing overall system efficiency.

Problems with the Dining Philosopher

The Dining Philosophers Problem highlights several challenges in concurrent programming, including:

  • Deadlock: Philosophers can end up waiting indefinitely for forks, leading to a system standstill.
  • Resource Contention: Multiple philosophers may compete for the same forks, causing inefficiency and slow performance.
  • Starvation: Some philosophers may not get a fair chance to eat due to improper synchronization.
  • Complexity: Implementing a solution to ensure fairness, prevent deadlock, and avoid contention can be challenging.
  • Scalability: Scaling the problem to accommodate more philosophers or resources can make it even more complex.

Solving these issues requires careful synchronization and proper resource management techniques.

Frequently Asked Questions

What is the dining philosopher problem?

Dining Philosophers problem is to design a solution that allows each philosopher to successfully alternate between thinking and eating while preventing deadlocks and resource starvation.

What is the 5 dining philosophers problem?

Five philosophers at a table must alternate between thinking and eating, sharing forks without causing deadlock or contention in concurrent scenarios.

Who created the dining philosophers problem?

TThe Dining Philosophers Problem was created by E.W. Dijkstra, a renowned computer scientist, and was presented in his 1965 paper titled "Cooperating Sequential Processes."

Is Dining philosopher deadlock free?

The Dining Philosophers Problem is not inherently deadlock-free, but solutions are designed to prevent deadlocks through proper synchronization.

Conclusion

The above article discussed the popular Dining Philosopher's problem which is a classic synchronization and concurrency problem in computer science and operating systems. It illustrates issues related to resource allocation and deadlock prevention in a multi-process environment. 

Recommended Reading

 

To get hands-on and practice different types of questions on the Operating System, you can visit the Operating System Track, a FREE Guided path. If you want to learn OS from an industry expert, check out a fantastic course on Operating systems

Also, check out some amazing Problems, Interview Experiences, and Guided Paths to topics such as Data Structures and Algorithms on Code360.

Topics covered
1.
Introduction
2.
What is the Dining Philosopher Problem?
3.
Semaphore Solution to Dining Philosopher Problem
3.1.
What is a semaphore? 
3.2.
Pseudo Code
3.3.
Implementation in C
4.
The Drawback of the Above Solution of the Dining Philosopher Problem
5.
Problems with the Dining Philosopher
6.
Frequently Asked Questions
6.1.
What is the dining philosopher problem?
6.2.
What is the 5 dining philosophers problem?
6.3.
Who created the dining philosophers problem?
6.4.
Is Dining philosopher deadlock free?
7.
Conclusion
7.1.
Recommended Reading