Talk:Dining philosophers problem

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Mid rated as Mid-importance on the assessment scale

The link to Spontaneous Symmetry Breaking has no relevant content. It is all about examples from Physics, with continuous state spaces, and differential operators and equations. There is no section about computer science or discrete examples. To explain what symmetry breaking means in this context requires some explanation - an extension of the section about all philosophers acting at the same time, mentioning that if all philosophers don't behave exactly the same, the problem doesn't arise. Therefore, if philosophers are made to act differently, by giving one of them priority, or by randomized timeouts, the symmetric deadlock can be avoided. 128.153.22.208 15:28, 26 October 2006 (UTC)


It's not immediately obvious to me how this solution works. What if everyone is hungry and has one fork? Evercat 02:48, 11 Nov 2003 (UTC)

Good point. Honestly, I don't know. I think the key point for the solution is that someone needs to hesitate holding the last avaliable fork. In other words, if at least one fork is avaliable, eventually one more fork will be released. -- Taku 03:30, Nov 11, 2003 (UTC)
Evercat, Taku - See if this makes sense. The first four can pick up a fork (the one to their left), but the fifth one cannot, since he has to wait for the one to his right. So the guy to *his* left i.e. the fourth philosopher, can actually pick up *both* forks, and eat, and when he is done he puts down the forks so that the third guy can eat etc. The fifth one will eat last.
I didn't want to get into too much of a detailed explanations as it probably ceases to be encyclopedic. The forks must be taken at the same time. Having the external link to the solution is a good compromise. Dori 04:45, Nov 11, 2003 (UTC)
  • Huh? How is it unencyclopedic to explain with as much detail as possible? --SaulPerdomo 22:28, 26 September 2005 (UTC)
I think this is not a detail but very important point that we must cover. I mean can we just revise it so that the solution makes more sense? As Evercat pointed out, I am not sure how the solution works. It should not take too much space to explain. -- Taku 04:53, Nov 11, 2003 (UTC)
OK, I just wasn't sure what the level of detail should be. I can't believe how much attention this article got :) Here's one I just added Sleeping barber problem. Dori 05:03, Nov 11, 2003 (UTC)

Thanks. I am still trying to trace what is happening. What is important folks is the explantion makes sense not how to implement the solution. I am suspecting the solution posed in the article is the first solution of this below from an article of Britannica.

An operating system can handle this situation with various prevention or detection and recovery techniques. For example, resources might be numbered 1, 2, 3, and so on. If they must be requested by each process in this order, it is impossible for a circular chain of deadlocked processes to develop. Another approach is simply to allow deadlocks to occur, detect them by examining nonactive processes and the resources they are holding, and break any deadlockby aborting one of the processes in the chain and releasing its resources.

The point of solving this problem is how to prevent the circular chain. -- Taku 05:19, Nov 11, 2003 (UTC)

It's not just the circular chain (deadlock), it's also a problem of starvation (i.e. you could have no deadlock, and yet one or more of the philosophers never gets to eat). Dori 05:33, Nov 11, 2003 (UTC)
I know but at least you have to prevent the circular chain. -- Taku 05:35, Nov 11, 2003 (UTC)

I find this statement bit difficult to understand: A philosopher cannot eat unless he has declared his state as hungry and both of his neighboring philosophers are not eating. We need to split it up into a more understandable form. Phoe6

Contents

[edit] This makes no sense

"After the philosopher is done eating, he again obtains a mutex lock, changes his state to thinking and sees, one at a time, if either of his two neighbors are hungry. If at least one is hungry, that philosopher enters the eating state if his other neighbor is not eating, and the cycle continues."

When the philosopher is done eating, and one of his neighbors is hungry, he eats again?

I don't understand either--Chealer 02:58, 2005 Mar 27 (UTC)
No, the neighbor starts eating if his forks are available. It seems to be a Hoare-style condition variable approach. Gazpacho 03:23, 27 Mar 2005 (UTC)
  • I have rewritten the solution section using an alternate approach. Hopefully this solution is clearer in how it solves the problem. If not I am sure it will be reverted ;). --Allen3 talk 22:49, Apr 1, 2005 (UTC)

[edit] Inaccurate statement

"In most cases, the dining philosophers problem is explained using rice and chopsticks as opposed to spaghetti and forks, as it is obviously easier to understand that two chopsticks are required, whereas one could arguably eat spaghetti using a single fork, or using a fork and a spoon."

This statement is inaccurate as explanation would be dining philosophers eating rice with chopsticks and not forks. I would advise to delete this or better offer it as an alternate description. Pixeleditor (talk) 17:50, 17 April 2008 (UTC)

[edit] Starvation?

After further thought, I don't believe this protocol prevents starvation as claimed. Consider this sequence:

1 and 3 become hungry and start eating→2 gets hungry and waits→1 stops eating, but 2 keeps waiting→1 gets hungry and starts eating→3 stops eating, but 2 keeps waiting→3 gets hungry and starts eating, etc.

Philosopher 2 will never eat in this case, even though each fork is repeatedly available. The solutions 2 link, Solution #5, describes a similar protocol and a similar failure mode. Gazpacho 07:59, 28 Mar 2005 (UTC)

The way I read to solution (following your example) after P1 stops eating P2 will pick up fork F2, while still waiting for P3. So P1 can not start eating again before P3 has finished, letting P2 pick up F3 and eat and finish. The problem in your example is that you forget that a philosopher can still pick up a fork even though both his forks are not available at the same time. Aenar 00:48, 17 Apr 2005 (UTC)
It is true that in your example P1 will have to wait till P3 and P2 have both finished eating before he can get both forks. The point is that this will happen. If P1 is allowed to get the fork shared with P2, then it is possible to starve P2 by either P1 or P3 constently taking one of the forks needed by P2. --Allen3 talk 01:55, Apr 17, 2005 (UTC)

I removed the statement that starvation due to the use of plain spinlocks would be known as priority inversion. This is utterly wrong. Priority inversion is a problem in priority driven scheduling that occurs when a high priority thread enters an unbounded wait due to a low priority thread holding a mutex being preempted by a medium priority thread. It has absolutely nothing to do with the dining philosophers problem (unless you want to prioritize philosophers... I digress). [User talk:PixelEditor] Thursday, April 17 2008

[edit] prim factors

Just guessing that the number of philosophers is relatively irelevant to the basics, so.

  1. Do the prim factors of the phylosopher-count matter at all?
  2. Could there always be as much parallel circles as prim factors of the phylosopher-count no matter what algorythm is used?
  3. Could parallel circles mix depending on the used algorythm?
  4. Could parallel circles merge, or split if you add or substract a phylosopher, its table and fork (depending on the used algorythm)?

[edit] Misattribution

The problem is due to Dijkstra, the parable is due to Tony Hoare. Dijkstra's original was about tape drives. --Gorgonzilla 19:19, 10 April 2006 (UTC)

I put in a fix for the misattribution of the parable. There are a couple of remaining problems. First the current text does not bring out the real issue that made the story important. It was used by Dijkstra, Hoare and Binch-Hansen to illustrate their competing proposals for describing concurrency. There are two basic solutions to the problem. The first is to introduce an asymmetry such as a philosopher who always picks up their left fork first rather than their right. The other is to introduce a butler.

The point of Dijkstra's original exposition was not to show he could solve the problem, it was to show how the P/V flags made it easier to create a formal proof the solution works. This is not really possible with monitors. Even with the P/V flags you do not have a satisfactory formal description of the problem which is why Hoare used the problem to demonstrate the power of CSP. --Gorgonzilla 20:53, 10 April 2006 (UTC)

[edit] Communication or not!

The problem statement states that the philosophers never speak to each other. However, Chandy / Misra Solution uses requests and signals. Is it a valid solution? —The preceding unsigned comment was added by VinnieCool (talk • contribs) 19:40, 28 December 2006 (UTC).

[edit] Stating the problem to be solved

While the article as is does a good job of setting the stage, it fails to succinctly state the problem that is to be solved. Shouldn’t it have a statement such as: How can the philosophers behave so that they all get a fair share of spaghetti? --Lbeaumont 15:31, 7 April 2007 (UTC)

[edit] Even/Odd differentiation

If we name philosophers from P1 to P5 and forks from F1 to F5, and we make odd-numbered philosophers take the fork on their right first, and even-numbered ones take the forks on their left first, you can have two simultaneous philosophers eating at the same time on a worst case scenario (all philosophers become hungry at the same time). Does not solve starvation, though, when two processes are quick thinkers and eaters. -- Alx5000 02:26, 13 June 2007 (UTC)

[edit] Forks vs chopsticks

I have re-written the page to use rice and chopsticks instead of forks and spaghetti. The problem states that it is easier to understand, so why not write it that way in the first place? Additionally, the word 'fork' is used elsewhere in concurrent programming which may lead to confusion. I decided to remove the 'alternate way of explaining the problem' altogether to lead to less confusion. —Preceding unsigned comment added by 74.202.89.125 (talk) 15:37, 6 December 2007 (UTC)

[edit] Solutions --> Chaos

This is in regards to the "solution" where a philosopher will, in response to waiting 5 minutes for a second chopstick:

  • release the chopstick,
  • wait a random interval of time, and
  • attempt to acquire both chopsticks again.

I'm not sure that this is actually a solution. Waiting a random interval of time before another attempt to grab a chopstick is likely to prevent livelock, but there is no guarantee, at least not that I can see. Theoretically, the random number generator could produce the same number indefinitely. Can we either get a proof that "Chaos" is a solution to this problem or remove the "Chaos" section? It may even be beneficial to move this into a "non-solutions" section and explain why it isn't a solution.

Here's an example that may help. Let's say one were to decide which philosopher gets a chopstick by a contest using coin tosses. Each philosopher gets a coin, and both of them flip. If they both get heads or they both get tails, they flip again. If only one gets heads, that philosopher get the chopstick. Nothing forces the pair of philosophers to eventually get one heads and one tails. 167.136.242.30 (talk) 16:04, 25 February 2008 (UTC)

It's a randomized algorithm. Randomized algorithms are designed to reach a valid configuration with high probability in reasonable time, rather than to produce any result with certainty. I don't have sources on this particular algorithm though. Dcoetzee 22:42, 25 February 2008 (UTC)

[edit] Differentiate waiting time

I had this idea during the reading the article. I'm sure that somebody had this idea before. What if first phylospoher wait 2 minute and if he detect lock put the fork down for 2 minute, second waid/put down for 3 minutes, third for 5, forth for 7 and the fifth for 11? Uzytkownik (talk) 21:22, 9 May 2008 (UTC)