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. One can feel this by drawing diagram.

---

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

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.