## DEV Community 👩‍💻👨‍💻 Rahul Mishra

Posted on • Originally published at programmingport.hashnode.dev

# Dining Philosopher Problem | Operating System - M03 P08

This is a multipart blog article series, and in this series I am going to explain you the concepts of operating system. This article series is divided into multiple modules and this is the third module which consists of 10 articles.

In this article we will see about dining philosopher problem, various cases and there solutions in detail.

### Dining philosopher problem

• To understand this problem let’s take an example.
• There is a dining table on which `5` philosophers are stetted and in between every philosopher there is a fork to eat the rice from rice bowl placed in center of the table.
• Every philosopher has two state think and eat.
``````void philosopher(void) {
while(true) {
Thinking();
take_fork(i);
take_fork((i+1)%N);
EAT();
put_fork(i);
put_forl((i+1)%N);
}
}
``````

Case 1:

• P0 comes.
• This will first complete the `thinking()` function, and then it will pick the left fork, which is in this case will be `f0` (because i=0). And then it will take right fork which is `f1` (because i=1).
• Now after taking both fork it will start eating and `eat()` function will execute.
• When eating is done (means `eat()` is executed completely) it will put left fork first and then the right fork. • Now `P1` will come and do the same thing as done by `P0` • This is the normal case in it every philosopher comes one by one and this program is fine.

Case 2:

• Suppose `P0` comes first and take the left fork (f0), but before he could take the right fork (f1), `P1` came and take the left fork (f1), now `P0` is waiting for the right fork (f1). • `P0` can get `f1` fork only if `P1` get `f2` (right fork) and then execute `eat()` and put `f1` fork and `f1` become free.
• So, if more than one philosopher came at same time then it will cause race condition.
• Now to remove the race condition we use the concept of semaphore (binary semaphore)
• We will use array of semaphore, five semaphore as we have `5` philosophers and fork `S0`, `S1`, `S2`, `S3`, `S4`
• All semaphore initialize with `1` value.
``````void philosopher(void) {
while(true) {
Thinking();
wait(take_fork(Sci + 1)%N);
EAT();
signal(put_fork(i));
signal(out_fork(i+1)%N);
}
}
``````
• Now when `P0` come and if it want to take two fork then it requires two values of semaphore (`S0`, `S1`)
• Then if `P1` comes to get executed properly it also require two values of semaphore (`S1`, `S2`) • Now suppose `P0` want to eat so he executed the `wait()` operation and came into critical section and start eating (executing `eat()`) due to which the value of `S0` and `S1` become `0` from `1` while other semaphore values at this point is `1`.
• Suppose while `P0` is in critical section and `P1` arrives and it requires `S1` and `S2` but as we know the value of `S1` is `0` so `P1` get blocked.
• Now at the same time `P2` also arrives and it requires `S2` and `S3` value to be `1` to get into critical section, as the condition is true so `P2` will successfully enter the critical section and start eating (execute `eat()`)
• But as we know that first condition of process synchronization is mutual exclusion accordingly to which at a time only one process can enter critical section. But this Dining philosopher problem is a special case for that.
• `P0` and `P2` are independent and do not have dependency because `P0` need `f0` and `f1` while `P2` needs `f2` and `f3`, Due to which more than one process can enter critical section (because both process are independent.)

Case 3:

• Suppose value of all semaphore is initialized with `1`.
• `P0` arrives and it takes the left fork (f0) and get preempt. Then `P1` arrives and take left fork (f1) and also get preempt. Similarly `P2`, `P3` and `P4` take `f2`, `f3` and `f4` fork (left fork) respectively. And all the processes get preempt just before they were going to pick right fork.
• Now every philosopher had taken the left fork but no one have the right fork. Value of all semaphore is `0`
• Now every process is blocked and they cannot unblock if they try they get blocked again because value of all semaphore `0`. This is the Dead lock condition
• The only solution to this problem is that we can change the sequence of fork of `P4`. Which means `P4` will first will take the right fork instead of left fork (f0) and then left fork instead of right fork (f4) • So, when the P4 comes it cannot take any fork and get blocked due to which `P3` can take the right fork (f4) as `S4` is `1` already, and so on. By this we can overcome the deadlock state.
• For `P4` this will be the sequence of entry section code.
``````Wait(take fork(S(i+1)%N)
Wait(take fork(Si)
``````

So this was all about dining philosopher problem. Hope you liked it and learned something new from it.

If you have any doubt, question, quires related to this topic or just want to share something with me, then please feel free to contact me.

### 📧 Write a mail

rahulmishra102000@gmail.com