2

Recently I read this Wikipedia article regarding the Dining Philosophers problem but I am not clear with Chandy / Misra solution.

According to the article, "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." In the context of this question, he passes it if he is eating and keeps it if he has not started eating yet.

According to the scenario, What is the meaning of Dirty? Thread is running or it has yeilded?

Chathuranga Chandrasekara
  • 20,548
  • 30
  • 97
  • 138
  • I guess it means it is finished running. OR the philosopher has finished eating for his part and hence the fork is dirty. – shahkalpesh May 14 '09 at 03:12

2 Answers2

2

Dirty means that processing has started so it can be interrupted.

And you can only process if you have two forks.

GordyII
  • 7,067
  • 16
  • 51
  • 69
  • Dirty also means "processing hasn't started yet (or has already finished), so it's immediately available without needing to interrupt someone else for it." – ChrisW May 14 '09 at 04:00
  • Which is why all of the forks start and finish Dirty. If they started clean, the no one would use them. – GordyII May 14 '09 at 04:33
  • The only time a fork is clean is during the instant that it's being passed from one philosopher to another. The important thing isn't whether it is clean (because it virtually never is clean) but whether it *was* clean when you received it: i.e. whether it was idle/available and you were able to just pick it up (dirty), or wheher it was busy and you had to request it and received it (cleaned). – ChrisW May 14 '09 at 04:43
0

Dirty seems to mean 'idle' or 'was available', and clean means 'had to request it' or 'preempted it'.

It says that a fork is 'dirty' if he picked it up (the fork wasn't contended when he wanted it), and 'clean' if he had to request it, and that its initial state is dirty.

  • Pick up an available fork => fork is dirty => clean it and give it up when asked.

  • No available fork => have to ask for it => will receive it cleaned.

It reminds me of the Organizational Pattern called Don't Interrupt an Interrupt.

ChrisW
  • 54,973
  • 13
  • 116
  • 224