[Solved]: Chandy/Misra dining philosophers solution

Problem Detail: 

So based on the Chandy/Misra section in this Wikipedia article we've got 5 philosophers numbered P1-P5.

Based on this quote:

For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty

When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.

So with the knowledge that all forks are initially dirty, regard the following quote and the image underneath it.

For every pair of Swansons, give the fork to the guy with the smaller id.

My question is if P3 now requests a second fork from his neighbor P4, will P4 give up his single fork beacause it was dirty, even though he just picked it up?

Asked By : Omar Sharaki

Answered By : David Richerby

Yes. Whenever a philosopher asks for a fork that is dirty, the philosopher who currently has that fork cleans it and gives it to the person who asked for it.

So, in the initial position, 1 has two dirty forks and can eat, 2, 3 and 4 have one dirty fork each and 5 has no forks at all. If 3 requests a fork from 4, 4 cleans it and gives it to him. This leads to the state where 1 has two dirty forks and can eat, 2 has one dirty fork, 3 has one clean fork and one dirty fork and can eat, and 4 and 5 have no fork.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42503