Talk:Dining philosophers problem

I believe the Java Implementation is not a true solution to the problem at hand, as it has a semaphore allowing for 5 of them to be eating at once... this doesn't take into account the 'resources' which are the 5 forks that each philosopher needs two of to go ahead and eat. 24.116.42.202 (talk) 03:57, 21 October 2010 (UTC)

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 rewrote much of the article yesterday because the problem wasn't being explained correctly. For instance, it is essential that forks must be taken one by one, not at the same time - e.g. this can be shown by drawing Petri nets - and this was not being mentioned. I hope the present text answers all the remarks above. Rp (talk) 21:32, 29 July 2011 (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

It has disappeared: declarations of hunger aren't part of the problem as usually stated, but of course variations are possible. Rp (talk)

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)

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)

It's been rewritten - is it clear now? Rp (talk) 10:44, 27 January 2012 (UTC)

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 P₁ will have to wait till P₃ and P₂ have both finished eating before he can get both forks. The point is that this will happen. If P₁ is allowed to get the fork shared with P₂, then it is possible to starve P₂ by either P₁ or P₃ constently taking one of the forks needed by P₂. --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

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)?

If your question still applies to the present state of the article, please rephrase. Rp (talk) 10:46, 27 January 2012 (UTC)

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)

OK, but there should be links to the sources. Right now this page mentions Dijkstra and Hoare without any pointers to their original work. —Preceding unsigned comment added by 201.81.182.224 (talk) 13:21, 12 July 2010 (UTC)

I believe this has been fixed now. Rp (talk) 21:25, 29 July 2011 (UTC)

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

Indeed, I consider the Chandy / Misra Solution a cheat too. If the philosophers are allowed to communicate request they could ask politely: "could I have you fork please?" and no deadlock would occur. —Preceding unsigned comment added by 93.125.226.71 (talk) 21:09, 7 October 2008 (UTC)

I'm surprised nobody ever put a comment on the Chandy / Misra Solution section to indicate that it's indeed violating one of the rules given in the original. I've added a statement for that. --69.28.149.29 (talk) 16:58, 13 July 2011 (UTC)

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)

Fixed (but focusing on deadlock, not starvation or fairness). Rp (talk) 10:48, 27 January 2012 (UTC)

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)

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)

Wikipedia must document the problem statement as it is best known, because people may want to look that up; hence, the rice and chopsticks have been relegated to a side remark. Rp (talk) 10:50, 27 January 2012 (UTC)

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)

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)

Yes, using timing can work, and I don't know if it is somehow explicitly precluded in the original problem statement. However in realistic cases of this type of problem it may not always be possible to use timing with sufficient precision. Rp (talk) 10:53, 27 January 2012 (UTC)

Dijkstra's solution?

• Unlike in Dijkstra's solution, these labelings can be arbitrary.
  • What is Dijkstra's solution? The article currently doesn't state it. --Abdull (talk) 09:04, 8 August 2008 (UTC)

Chandy / Misra Solution

The Chandy / Misra solution proposal with "dirty" and "clean" forks can be simplified no? In the situation with "dirty" and "clean" forks, a fork that is dirty represents a resource that has been used, and a fork that is clean represents a resource that has yet to be used. In the context of the original Dining Philosopher's problem, each of the philosophers must acquire access to both resources before it can use either one of them. The general solution seems to state that a philosopher should use one resource (pick up one fork), use the resource (do as much as you can with that fork), put the fork down (the philosopher sticks his finger into the pasta and makes it act like a fork?), and then request for the next resource. It represents a fundamentally different situation from the Dining Philosophers problem, where you have to acquire both resources. So why is this the general solution in the first place? —Preceding unsigned comment added by 130.126.63.60 (talk) 22:40, 12 October 2008 (UTC)

Chandy / Misra do require that the philosophers acquire both forks. Their text is geared toward a wider class of problems with an arbitrary number of resources needed for each task. They include an analysis of the Dining Philosopher's problem and reuse concepts and terminology from that analysis in their more general treatment. However, their treatment does also solve the problem as stated here with five philosophers and five forks.

The more general problem includes questions about amount of knowledge required to find an optimal or good solution. They describe the interactions as messages because that is more general, it applies also when the competing processes run on widely separated computers. However, it is possible to implement their algorithm using just a few bits of shared memory, not unlike the solution included in the article. That solution uses an array called "state", which is accessed by all processes. Cacadril (talk) 23:16, 13 November 2009 (UTC)

The comment

This solution may be contestable though, as its 'requests' may be considered communication; which the philosophers cannot do.

- is not to the point. If I set the air in motion with my vocal cords and your ears detect this motion, it's communication. If a computer process changes the value of a variable, and another process acquires this value, it's communication. No solution whatsoever is possible without communication.

I suppose Hoare made his philosophers silent so that the problem could arise. I suppose he wanted his students to think of the philosophers more like machines. Machines do not solve problems on their own. They solve problems when that problem-solving behavior has been designed into them. Hoare's requirement should be taken to mean that the philosophers do not communicate outside the protocol, and his students had to specify a protocol that was sufficient to avoid deadlock and starvation. Cacadril (talk) 23:16, 13 November 2009 (UTC)

I disagree. The original problem clearly states that the philosophers do not speak to each other. Passing requests is a violation of this rule, as would be a more obfuscated solution such as "if the philosopher to your left picks up a fork, puts it down, and picks it up again, put down your left fork". To quote:

"Note that the alphabets of the philosophers are mutually disjoint. There is no event in which they participate jointly, so there is no way whatsoever in which they can interact or communicate with each other—a realistic reflection of the behaviour of philosophers in those days." (http://www.usingcsp.com/cspbook.pdf)

The concept of communicating only within a protocol is definitively not implied by the phrase "...there is no way whatsoever in which they can interact or communicate with each other...". --69.28.149.29 (talk) 17:29, 13 July 2011 (UTC)

Diagram / Text inconsistency

The text says there is a single plate of spaghetti in the centre of the table but the illustration shows multiple plates. This is significant because the text explains that the serving and eating is the reason that two forks are required.

DEADLOCK

THIS IS CONFUSING —Preceding unsigned comment added by 117.241.218.126 (talk) 08:05, 7 May 2010 (UTC)

Pascal implementation

Won't compile on FreePascal:

philos.pas(5,12) Fatal: Syntax error, "=" expected but "identifier DINING_PHILOSOPHERS" found
philos.pas(0) Fatal: Compilation aborted

--HTMLCODER.exe (talk) 11:24, 25 August 2010 (UTC)

Java Implementation

How is it possible to have all 5 eating at the same time???

Here is the result I got when I ran the program: (marked bold)

Looks like that code has a bug. I'm not sure which of the two Java implementations it was, but I removed all the code examples since they were cluttering up the article. 75.57.242.120 (talk) 19:39, 20 March 2011 (UTC)

Erlang implementation

Good article guys. I thought I'd contribute some solutions based on Erlang: https://github.com/TTimo/Dining-Philosophers---Erlang/blob/master/conductor.erl — Preceding unsigned comment added by TTimo (talk • contribs) 17:31, 30 December 2010 (UTC)

Conductor Solution

"The logic is kept simple by specifying that philosophers always seek to pick up their left hand fork before their right hand fork (or vice versa)."

This is quite unclear why that is. Is it to ensure that e.g. philosopher D will not take the fork left of E if A is the first to stop eating ? As far as I know this is already a requirement of the problem , that a philosopher cannot take any forks than the ones next to him.

Conductor Solution

"The logic is kept simple by specifying that philosophers always seek to pick up their left hand fork before their right hand fork (or vice versa)."

This is quite unclear why that is. Is it to ensure that e.g. philosopher D will not take the fork left of E if A is the first to stop eating ? As far as I know this is already a requirement of the problem , that a philosopher cannot take any forks than the ones next to him. — Preceding unsigned comment added by MadsBogeskov (talk • contribs) 11:32, 13 February 2011 (UTC)

implementations

There's an awful lot of space taken up by code, and at least one of the implementations seems to be wrong (see the post above with a log showing all 5 philosophers eating simultaneously). How about if we get rid of them and link here. There also seems to be a fair amount of extlink cruft and maybe some cleanup is appropriate. 75.57.242.120 (talk) 06:27, 16 March 2011 (UTC)

I made this change after a big battle against the edit filter. I think Rosetta Code is ok to use like this, as it's a GFDL wiki with no advertising. It doesn't seem perfect though; having some kind of code sample seems reasonable. Feel free to discuss. 75.57.242.120 (talk) 12:19, 16 March 2011 (UTC)

Good move! —Ruud 15:49, 17 March 2011 (UTC)

FYI, RC is not guaranteed to remain advert-free (heck, it's not even a non-profit), so be careful of using that as a predicate for outsourcing code hosting examples. Otherwise, feel free to use RC as a code-based demonstration ground for any WP articles that need it. I've intentionally set RC up as a place where language advocates can compete, and that should reduce the pressure on WP from "hey, you need to show examples using this langauge or paradigm!" (Full disclosure: I own RC) --Michael Mol (talk) 02:31, 30 June 2011 (UTC)

[1] restored all the material with "undo". I don't think that's good, but am open to intermediate solutions. I'll leave the reverter a usertalk message asking him/her to discuss the edit here. 75.57.242.120 (talk) 11:26, 22 March 2011 (UTC)

Having gotten no response to the talk message[2] I'm going to unrevert. 75.57.242.120 (talk) 22:17, 23 March 2011 (UTC)

Conductor Solution error

Is it me, or is the Conductor solution not quite right? If 4 of the philosophers request their left fork, they would get it. According to the wiki page, "When four of the forks are in use, the next philosopher to request one has to wait for the waiter's permission, which is not given until a fork has been released." That's not accurate, because in the scenario i just described, no one would ever release a fork. I think that that SHOULD say:

"When four of the forks are in use, the next philosopher to request one will receive it if it is their right fork (ie it would allow them to eat). If not, they will be forced to wait until a fork has been released." — Preceding unsigned comment added by 71.201.26.202 (talk) 18:05, 14 December 2011 (UTC)