Dining Philosophers Problem using Semaphores (with Solution)

Let's learn about an interesting problem of operating systems today. Dining Philosopher's Problem originated from the field of concurrent programming when multiple processes contend for limited resources while also avoiding deadlock.

Dining Philosopher's Problem Statement

This is a classic synchronization problem in computer science that demonstrates the challenges of resource allocation and concurrency.

We have been provided with a table where 5 philosophers are sitting for dining. In the middle of the table, noodles have been kept and we have 5 plates and 5 forks. It is given that either the philosophers will be in an eating state or a thinking state. To eat the noodles, each philosopher needs 2 forks and picks the forks one by one.

This implies we need 10 forks as per their need. So how do we synchronize their actions so that we are able to create a system where whichever philosopher is about to eat, gets the 2 forks and we get a deadlock-free system?

From the problem statement, we know it is a critical section problem. As 'fork' here can be treated as a shared variable between 2 philosophers or processes. And just like a classical critical section problem, here we need to synchronize in such a way that till a philosopher says, p1 is not done with eating, another philosopher says p2, does not disturb p1.

The Dining Philosophers Problem serves as an abstract representation of real-world challenges like highlighting the need for synchronization techniques to ensure the fair allocation of resources and prevent deadlock.

To solve this critical section problem, we use an integer value called semaphore.

Approach to Solution

Here is the simple approach to solving it:

1. We convert each fork as a binary semaphore. That implies there exists an array of semaphore data types of forks having size = 5. It initially contains 1 at all positions.
2. Now when a philosopher picks up a fork he calls wait() on fork[i] which means that i'th philosopher has acquired the fork.
3. If a philosopher has done eating he calls release(). That implies fork[i] is released and any other philosopher can pick up this fork and can start eating.

Here is the code for this approach:

do{
        wait(fork[i]);
        wait(fork[(i + 1) % 5]);
        //eat noodles
        
        signal(fork[i]);
        signal(fork[(i + 1) % 5]);
        //think
        
    }while(1);

How does this solution work?

The i-th philosopher will pick i-th fork and fork kept at (i + 1) % 5 positions. As the table is circular and if we take i = 5, the philosopher will pick the 5th fork but to pick the second correct fork, we used  (i + 1) % 5.

If i = 1, we call one by one wait function due to which the philosopher picks up the 1st and 2nd fork. After he has finished eating, he releases the fork and starts thinking, and this is how we are ensuring that no two adjacent philosophers eat simultaneously.

Now as we saw, this solution is ensuring that the neighbors say p1 and p2 are not eating simultaneously but this doesn't ensure that we will not witness a situation of deadlock.

Let's see how we can get the deadlock situation.

Assume all the philosophers have picked their leftmost fork. Now there arises a deadlock condition as here, each philosopher is waiting for their rightmost fork to be free. Only if p5 leaves its fork, p1 can have the food, and p5 will only leave its fork if p4 gives him the fork. So this creates an infinite loop and hence a deadlock situation.

Approach to solving this deadlock condition

Here is the approach to solving Dining Philosopher's Problem in this deadlock condition:

1. If we allow at most 4 philosophers to be sitting simultaneously. After doing so at least one of the philosophers can go to the eating stage and hence other philosophers can after he releases the fork.
2. Allow the philosopher to pick his fork only and only if both forks are available. So to implement this, we convert the wait() calls into a critical section and so we introduce a new lock. This lock will ensure that the philosopher gets both forks at once.
3. Odd-Even rule: We can identify the philosophers by their position if it is even or odd. All the philosophers at odd positions pick the fork kept at their left and then the fork at their right. The philosophers at even position can pick the fork at the right position and then the fork at their left.

Conclusion 

The dining philosophers is a classic problem related to synchronization. In the operating system, we assume the philosophers to be processed and forks as the resources. The same technique is used in operating systems too and this way we avoid the deadlock situation.