0
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ This question could use some editing to make it more self-contained. I would guess that most people aren't familiar with the Chandy-Misra solution to the dining philosophers problem and I'm confident that pretty much nobody is familiar with the blog post you link. So I had to read two large sections of webpage before I could even figure out what you were asking about. $\endgroup$
    – David Richerby
    Commented May 13, 2015 at 10:01
  • $\begingroup$ I don't know what else I could add. The wikipedia article should be sufficient to understand how the solution works. The second link was essentially there to provide an illustration so that it's clearer. $\endgroup$
    – Omar Sharaki
    Commented May 13, 2015 at 10:05
  • $\begingroup$ The diagrams in the blog post are incorrect. The protocol requires one fork for each pair of philosophers contending for a resource. The blog has the food in the centre of the table, suggesting that every pair of philosophers is in contention for every resource. This means there should be $\tfrac12n(n+1)=10$ forks, not 5. $\endgroup$
    – David Richerby
    Commented May 13, 2015 at 10:06
  • $\begingroup$ You could add a brief description of the Chanda-Misra solution to the question, to make your question self-contained (and link directly to the relevant section of the Wikipedia article). I actually think the blog post is a very bad illustration, as you can see from the comment I posted a moment ago (but before I read your comment). $\endgroup$
    – David Richerby
    Commented May 13, 2015 at 10:07
  • $\begingroup$ I think the position of the food is irrelevant. The resource that they want to access is that they "want to eat" so they need 2 forks to do that, which means they are competing for the forks not the food. In other words the critical section is the forks. $\endgroup$
    – Omar Sharaki
    Commented May 13, 2015 at 10:29

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ If 3 has 2 forks doesn't that mean he can eat? $\endgroup$
    – Omar Sharaki
    Commented May 13, 2015 at 10:23
  • $\begingroup$ Also philosopher 5 should have no forks since he has the highest id, meaning philosophers 4 and 1 took the forks around him. I think the scenario after 3 requests a fork from 4 should be as follows: 1 has 2 forks(both dirty), 2 has 1 dirty fork, 3 has 2 forks(one dirty one clean), 4 has none, five has none. This means 2 philosphers, namely 1 and 3, have 2 forks and are thus ready to eat. Am I right? $\endgroup$
    – Omar Sharaki
    Commented May 13, 2015 at 10:36
  • $\begingroup$ Sorry, yes, I've completely messed this up. I'm sorry for taking a somewhat dismissive tone while being wrong myself. I'll rewrite the answer. (In the mean time, take this as a warning against the power of metaphor. To me, the clean/dirty fork thing implied that philosophers, being very civilized, would only eat with clean forks. I'd assumed that everyone starting with a dirty fork led to a starting transient where people have to swap forks for a bit until somebody has two clean ones, but this is not the case.) $\endgroup$
    – David Richerby
    Commented May 13, 2015 at 10:45
  • $\begingroup$ I've now fixed the answer. $\endgroup$
    – David Richerby
    Commented May 13, 2015 at 11:00
  • $\begingroup$ I don't want to make this an extended chat, but in reply to your last comment in the section above where you said "So, for example, if five philosophers want a single dish, there are ten forks just for that dish, plus other forks for other dishes. A phil. can only eat from a dish if he has all its forks." I'd like to point out that a philosopher can only communicate with his neighbors i.e only 2 phils. If he needs 10 forks as you say then what's he supposed to do? Also in reply to what you said about the shared resources being the food, regard this quote: $\endgroup$
    – Omar Sharaki
    Commented May 14, 2015 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.