Dining Philosophers Problem in OS

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 of who will get the resource and when. This problem is solved using process synchronization.

The act of synchronizing process execution such that no two processes have access to the same associated data and resources are referred to as process synchronization 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 synchronized with one another to avoid data inconsistency.

And the Dining Philosophers Problem is a typical example of limitations in process synchronization in systems with multiple processes and limited resources. 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 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/chopsticks C0 and C1 must be free, which would leave 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.

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 a 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 resources while entry. No operation is done if S is negative or zero. The value of the signal() operation's parameter S is increased, it is used to release the resource once the critical section is executed at exit.

Here's a simple explanation of the solution:

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 initialize 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:

Output

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.

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.

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.

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).

When the philosopher successfully acquires lock on both the chopsticks, the philosopher starts dining (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.

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

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

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 aforementioned 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 in 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.

Unlock the secrets of operating systems with our Operating System free course. Enroll now to get a comprehensive overview of their role and functionalities.