Dining Philosophers Problem in OS

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 i^th 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 i^th 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);
	}
}

You can also try this code with Online C Compiler

Run Code

Output:

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

• Producer-Consumer Problem using Semaphores
• Readers-Writers Problem
• Sleeping Barber's Problem
• include stdio h
• fork() system call