GATE CSE 1996 | Question: 2.19

Question

A solution to the Dining Philosophers Problem which avoids deadlock is to

• A. ensure that all philosophers pick up the left fork before the right fork

• B. ensure that all philosophers pick up the right fork before the left fork

• C. ensure that one particular philosopher picks up the left fork before the right fork, and that all other philosophers pick up the right fork before the left fork

• D. None of the above

Comments

Good Read: https://www.cs.indiana.edu/classes/p415-sjoh/hw/project/dining-philosophers/index.htm

---

I had the confusion for option C but upon reading bikram sir’s comment i am convinced however i think the word “ensure” in option C asks us to make sure that one particular philosopher must do opposite of what everyone else is doing.

When we simulate this we effectively break any possibility of a circular wait and thus solving possibility of dead lock.

However if it was not for the word ensure, and all the philosopher picked up their right spoon then the one philosopher will be left with only a single spoon on his right.

If he picks it there is a circular wait, what will it do at that time and how the answer will change.

Please help @Bikram sir.

 

Answer 1

Acc. to me it should be (C) because: according to condition, out of all, one philosopher will get both the forks. So, deadlock should not be there.

Comments

@Bikram sir. Even if all Philosophers hold one of the chopstick (Here 1 holds left and other holds right) then also Deadlock will not happen. So even if all Philosophers are not satisfying the ‘’Dining-Philosophers imposes the restriction that a philosopher may pick up  chopsticks only if both of them are available’’ condition then also Deadlock will not occur because Circular wait doesn’t occur. So whether C option follows the mentioned condition or it doesn’t follow the mentioned condition, the deadlock will not happen. To add one more point, 1 picks left and others pick right. Here there would be 1 philosopher for sure who won’t be able to pick its right chopstick. 

---

A solution to the Dining Philosophers Problem which avoids deadlock is to ensure that all philosophers pick up the left fork before the right fork.

This approach helps prevent circular waiting, one of the necessary conditions for deadlock, as it enforces a consistent order in the way philosophers acquire resources (forks in this case). By having a protocol where all philosophers agree to pick up the left fork first and then the right fork, the potential for deadlock is reduced. If every philosopher follows the same order when picking up forks, it eliminates the possibility of a circular waiting scenario, thus avoiding deadlock.

---

Other than C another valid solution to dining philosophers can be like this :

All philosophers with even numbers take forks from Left to Right and odd numbered once take Right to Left.

Answer 2

option C explanation:-

let A,B,C are the three philosophers .....

let A pickup left before right and all other pickup right before left then...now B has picked up right fork and A has picked up left fork ....

and  C is waiting for A ....

now both left and right fork is available for A.(i.e A would finish)...after A ,B and then C......

no deadlock....

Comments

anyone verify this!

---

yes correct...i think

Answer 3

Another way to think is first two options forms a cycle that is a circular wait and all other necsessary conditions are satisfied for dining philosopher's problem. So those two are not possible and third one breaks this circular wait. So it is the correct answer.

Answer 4

In the Dining Philosophers Problem,

each philosopher needs exactly two chopsticks to eat food but the problem is: each philosopher is going to take one chopstick at a time, which is placed at its right-hand side or at its left-hand side, but remember all should choose in same the manner like it first one chooses in a clockwise manner then each one should choose in clockwise, this type of picking  causes a circular waiting loop because each one is depending on other. This is also called as circular waiting and it leads to deadlock.

To avoid this, at least one philosopher should choose its first chopstick in different way so that that circular loop is not formed.

Answer 5

There are multiple ways to break a deadlock, which are as follows:

1) You bring in more resources (not a good solution but still a possible way)

2)You choose one lesser No of Philosophers than given ie., create a room by using P() at start of each Philosophers turn and ensure that signal V()  is there at end of given philosophers only which ensures if 5 philophers are given and 5 forks then only 4 philophers are choosen first once one finishes eating fully another is allowed to come

3)You can also break the symmtery , there are many ways to do so one of them could be to ask one of them to pick right fork while all others pick the fork on their left.

4)All of Nothing, which means that a given person either picks both forks or does not pick anything, this also ensures that no deadlock occurs 

Here, option (c) matches with one of the methods hence it is correct.

Also, note that for n people you will need min of n+1 forks to avoid deadlock.

(source - goclasses slides)

Comments

Thanks for sharing!

Answer 6

Deadlock occurs when – The first choice fork of every philosopher is different. For example every philosopher just grabs the fork on their left first.

To avoid this scenario the first choice of atleast one philosopher must be different than the others.

So option (C) is correct.