Talk:Dining philosophers problem

Untitled

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

Yes, Chopsticks and rice makes more sense, and if my opinion were worth more than two cents, I would encourage every CS professor to teach it that way, But historically, spaghetti and forks actually is the traditional version. 74.111.96.172 (talk) 20:57, 7 March 2022 (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)? — Preceding unsigned comment added by Ollj (talk • contribs) 19:55, 6 April 2006 (UTC)

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)

Does Dijkstra's solution, which employs a global mutex, also count as communication? Charmoniumq (talk) 20:15, 5 July 2024 (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)

The problem is still ill-defined. The examples seem to assume that philosophers can only pick up one fork at a time, that they can see what their neighbors are doing, and that they cannot speak to each other. None of these is stated in the problem definition. Also, is time continuous or discrete? Do they have a common clock?--2003:C5:4F25:6E43:24BC:3621:1907:EF7D (talk) 18:03, 23 January 2019 (UTC)

True. The problem assumes that

• philosophers can only pick up one fork at a time;
• they can not communicate at all; all they can do is can inspect whether "their" forks are there (which won't help them as the neighbour may pick it up at any time) and attempt to pick one up;
• I'm not sure whether it makes any difference if time is discrete or continuous, if events take time or not, or if events may concur or overlap in time or not; I don't think it does;
• there is no clock.

Rp (talk) 22:12, 26 January 2019 (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)

It should be chopsticks - you can eat happily with one fork, especially spaghetti. The point of the problem is that you need two chopsticks to be able to eat anything! 213.105.181.114 (talk) 14:25, 26 September 2016 (UTC)

Agreed. I've heard this problem many times, and outside of Wikipedia apparently, it's always been explained the same way: rice and chopsticks. A person can, quite easily, eat spaghetti with one fork. Try eating rice with a single chopstick. You'll find that it's near impossible. R36 (talk) 23:53, 29 April 2017 (UTC)

The original problem statement from CAR Hoare was with forks. I understand that it seems to be quite strange (especially for Italians who do not use anything but a single fork for eating spaghetti) but it should be stressed that historically the original problem statement was that one. 158.110.27.203 (talk) 11:07, 2 October 2019 (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)

  Yes, I also think there should be a plain-text explanation to Dijkstra's solution in addition to or even replacing program code. Wikipedia is not stackit. Gpermant (talk) 11:20, 25 March 2024 (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.

The inconsistency is still there, 2013.11.05. Kdammers (talk) 08:01, 5 November 2013 (UTC)

There are no limitations on the spaghetti, so it doesn't really matter whether it is in one heap or in several; but the text and illustration should be consistent. I think it's best to change the picture - I'll ask the author. Rp (talk) 10:17, 5 November 2013 (UTC)

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)

Program output collapsed for convenience

1285281094258 0 00000 Philosopher 0 is thinking 1285281094258 0 00000 Philosopher 4 is thinking 1285281094258 0 00000 Philosopher 3 is thinking 1285281094258 0 00000 Philosopher 2 is thinking 1285281094258 0 00000 Philosopher 1 is thinking 1285281094519 5 00000 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281094531 6 00000 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281094615 7 00000 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281094798 8 00000 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281095214 9 00010 Philosopher 3 is eating 1285281095246 10 01010 Philosopher 1 is eating 1285281095296 11 01010 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281095302 12 01011 Philosopher 4 is eating 1285281095729 13 01111 Philosopher 2 is eating 1285281095751 14 11111 Philosopher 0 is eating 1285281095770 15 10111 Philosopher 1 finished eating, and puts away his chopsticks 1285281095770 16 10111 Philosopher 1 is thinking 1285281095862 17 00111 Philosopher 0 finished eating, and puts away his chopsticks 1285281095862 18 00111 Philosopher 0 is thinking 1285281095912 19 00101 Philosopher 3 finished eating, and puts away his chopsticks 1285281095912 20 00101 Philosopher 3 is thinking 1285281095914 21 00101 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281095961 22 00101 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281096096 23 00100 Philosopher 4 finished eating, and puts away his chopsticks 1285281096096 24 00100 Philosopher 4 is thinking 1285281096175 25 00100 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281096232 26 10100 Philosopher 0 is eating 1285281096434 27 10000 Philosopher 2 finished eating, and puts away his chopsticks 1285281096434 28 10000 Philosopher 2 is thinking 1285281096527 29 10010 Philosopher 3 is eating 1285281096594 30 11010 Philosopher 1 is eating 1285281096677 31 11010 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281096938 32 11011 Philosopher 4 is eating 1285281096952 33 11011 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281097079 34 01011 Philosopher 0 finished eating, and puts away his chopsticks 1285281097079 35 01011 Philosopher 0 is thinking 1285281097350 36 01001 Philosopher 3 finished eating, and puts away his chopsticks 1285281097350 37 01001 Philosopher 3 is thinking 1285281097351 38 00001 Philosopher 1 finished eating, and puts away his chopsticks 1285281097351 39 00001 Philosopher 1 is thinking 1285281097443 40 00001 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281097479 41 00101 Philosopher 2 is eating 1285281097520 42 00100 Philosopher 4 finished eating, and puts away his chopsticks 1285281097520 43 00100 Philosopher 4 is thinking 1285281097680 44 00100 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281097723 45 00000 Philosopher 2 finished eating, and puts away his chopsticks 1285281097723 46 00000 Philosopher 2 is thinking 1285281097725 47 00000 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281097792 48 10000 Philosopher 0 is eating 1285281098025 49 10000 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281098134 50 10001 Philosopher 4 is eating 1285281098299 51 10011 Philosopher 3 is eating 1285281098302 52 00011 Philosopher 0 finished eating, and puts away his chopsticks 1285281098302 53 00011 Philosopher 0 is thinking 1285281098321 54 00011 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281098352 55 00001 Philosopher 3 finished eating, and puts away his chopsticks 1285281098352 56 00001 Philosopher 3 is thinking 1285281098367 57 01001 Philosopher 1 is eating 1285281098478 58 00001 Philosopher 1 finished eating, and puts away his chopsticks 1285281098478 59 00001 Philosopher 1 is thinking 1285281098499 60 00001 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281098553 61 00101 Philosopher 2 is eating 1285281098859 62 00100 Philosopher 4 finished eating, and puts away his chopsticks 1285281098859 63 00100 Philosopher 4 is thinking 1285281098863 64 00100 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281099283 65 00100 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281099352 66 10100 Philosopher 0 is eating 1285281099378 67 10110 Philosopher 3 is eating 1285281099396 68 11110 Philosopher 1 is eating 1285281099439 69 11010 Philosopher 2 finished eating, and puts away his chopsticks 1285281099439 70 11010 Philosopher 2 is thinking 1285281099688 71 11010 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281099833 72 11010 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281099845 73 01010 Philosopher 0 finished eating, and puts away his chopsticks 1285281099845 74 01010 Philosopher 0 is thinking 1285281100038 75 01011 Philosopher 4 is eating 1285281100068 76 00011 Philosopher 1 finished eating, and puts away his chopsticks 1285281100068 77 00011 Philosopher 1 is thinking 1285281100074 78 00111 Philosopher 2 is eating 1285281100262 79 00101 Philosopher 3 finished eating, and puts away his chopsticks 1285281100262 80 00101 Philosopher 3 is thinking 1285281100411 81 00101 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281100425 82 00100 Philosopher 4 finished eating, and puts away his chopsticks 1285281100425 83 00100 Philosopher 4 is thinking 1285281100427 84 00100 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281100437 85 01100 Philosopher 1 is eating 1285281100790 86 00100 Philosopher 1 finished eating, and puts away his chopsticks 1285281100790 87 00100 Philosopher 1 is thinking 1285281100949 88 00000 Philosopher 2 finished eating, and puts away his chopsticks 1285281100949 89 00000 Philosopher 2 is thinking 1285281101013 90 00000 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281101198 91 00000 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281101235 92 00000 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281101236 93 00000 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281101252 94 10000 Philosopher 0 is eating 1285281101333 95 10100 Philosopher 2 is eating 1285281101341 96 10101 Philosopher 4 is eating 1285281101384 97 11101 Philosopher 1 is eating 1285281101669 98 11001 Philosopher 2 finished eating, and puts away his chopsticks 1285281101669 99 11001 Philosopher 2 is thinking 1285281102083 100 01001 Philosopher 0 finished eating, and puts away his chopsticks 1285281102083 101 01001 Philosopher 0 is thinking 1285281102133 102 01011 Philosopher 3 is eating 1285281102167 103 01011 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281102227 104 00011 Philosopher 1 finished eating, and puts away his chopsticks 1285281102227 105 00011 Philosopher 1 is thinking 1285281102245 106 00011 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281102292 107 00010 Philosopher 4 finished eating, and puts away his chopsticks 1285281102292 108 00010 Philosopher 4 is thinking 1285281102326 109 10010 Philosopher 0 is eating 1285281102676 110 10010 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281102883 111 00010 Philosopher 0 finished eating, and puts away his chopsticks 1285281102883 112 00010 Philosopher 0 is thinking 1285281103040 113 00110 Philosopher 2 is eating 1285281103045 114 00110 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281103069 115 01110 Philosopher 1 is eating 1285281103075 116 01100 Philosopher 3 finished eating, and puts away his chopsticks 1285281103075 117 01100 Philosopher 3 is thinking 1285281103196 118 01100 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281103356 119 01101 Philosopher 4 is eating 1285281103388 120 01001 Philosopher 2 finished eating, and puts away his chopsticks 1285281103388 121 01001 Philosopher 2 is thinking 1285281103408 122 01001 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281103415 123 11001 Philosopher 0 is eating 1285281103475 124 10001 Philosopher 1 finished eating, and puts away his chopsticks 1285281103475 125 10001 Philosopher 1 is thinking 1285281103535 126 10001 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281103645 127 10101 Philosopher 2 is eating 1285281103665 128 00101 Philosopher 0 finished eating, and puts away his chopsticks 1285281103665 129 00101 Philosopher 0 is thinking 1285281103717 130 00100 Philosopher 4 finished eating, and puts away his chopsticks 1285281103717 131 00100 Philosopher 4 is thinking 1285281103916 132 00100 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281104093 133 00110 Philosopher 3 is eating 1285281104182 134 00110 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281104256 135 00010 Philosopher 2 finished eating, and puts away his chopsticks 1285281104256 136 00010 Philosopher 2 is thinking 1285281104299 137 01010 Philosopher 1 is eating 1285281104302 138 01000 Philosopher 3 finished eating, and puts away his chopsticks 1285281104302 139 01000 Philosopher 3 is thinking 1285281104342 140 01000 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281104344 141 01000 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281104410 142 11000 Philosopher 0 is eating 1285281104614 143 10000 Philosopher 1 finished eating, and puts away his chopsticks 1285281104614 144 10000 Philosopher 1 is thinking 1285281104664 145 10000 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281104716 146 10100 Philosopher 2 is eating 1285281104773 147 10110 Philosopher 3 is eating 1285281104901 148 10111 Philosopher 4 is eating 1285281104944 149 10101 Philosopher 3 finished eating, and puts away his chopsticks 1285281104944 150 10101 Philosopher 3 is thinking 1285281105023 151 00101 Philosopher 0 finished eating, and puts away his chopsticks 1285281105023 152 00101 Philosopher 0 is thinking 1285281105028 153 00001 Philosopher 2 finished eating, and puts away his chopsticks 1285281105028 154 00001 Philosopher 2 is thinking 1285281105160 155 00001 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281105249 156 00001 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281105520 157 00001 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281105545 158 01001 Philosopher 1 is eating 1285281105564 159 01000 Philosopher 4 finished eating, and puts away his chopsticks 1285281105564 160 01000 Philosopher 4 is thinking 1285281105571 161 01000 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281105782 162 01100 Philosopher 2 is eating 1285281105795 163 00100 Philosopher 1 finished eating, and puts away his chopsticks 1285281105795 164 00100 Philosopher 1 is thinking 1285281105983 165 00100 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281106013 166 10100 Philosopher 0 is eating 1285281106015 167 10101 Philosopher 4 is eating 1285281106268 168 10111 Philosopher 3 is eating 1285281106334 169 10011 Philosopher 2 finished eating, and puts away his chopsticks 1285281106334 170 10011 Philosopher 2 is thinking 1285281106507 171 10011 Philosopher 1 is hungry and is trying to pick up his chopsticks 1285281106778 172 00011 Philosopher 0 finished eating, and puts away his chopsticks 1285281106778 173 00011 Philosopher 0 is thinking 1285281106818 174 00011 Philosopher 0 is hungry and is trying to pick up his chopsticks 1285281106993 175 00010 Philosopher 4 finished eating, and puts away his chopsticks 1285281106993 176 00010 Philosopher 4 is thinking 1285281107059 177 00010 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281107167 178 00000 Philosopher 3 finished eating, and puts away his chopsticks 1285281107167 179 00000 Philosopher 3 is thinking 1285281107220 180 00000 Philosopher 2 is hungry and is trying to pick up his chopsticks 1285281107329 181 00001 Philosopher 4 is eating 1285281107352 182 10001 Philosopher 0 is eating 1285281107386 183 11001 Philosopher 1 is eating 1285281107410 184 11101 Philosopher 2 is eating 1285281107552 185 11001 Philosopher 2 finished eating, and puts away his chopsticks 1285281107663 186 11000 Philosopher 4 finished eating, and puts away his chopsticks 1285281107663 187 11000 Philosopher 4 is thinking 1285281107885 188 11000 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281107965 189 10000 Philosopher 1 finished eating, and puts away his chopsticks 1285281107993 190 00000 Philosopher 0 finished eating, and puts away his chopsticks 1285281108077 191 00010 Philosopher 3 is eating 1285281108159 192 00010 Philosopher 4 is hungry and is trying to pick up his chopsticks 1285281108268 193 00000 Philosopher 3 finished eating, and puts away his chopsticks 1285281108268 194 00000 Philosopher 3 is thinking 1285281108815 195 00001 Philosopher 4 is eating 1285281109261 196 00001 Philosopher 3 is hungry and is trying to pick up his chopsticks 1285281109650 197 00000 Philosopher 4 finished eating, and puts away his chopsticks 1285281109668 198 00010 Philosopher 3 is eating 1285281110285 199 00000 Philosopher 3 finished eating, and puts away his chopsticks

— Preceding unsigned comment added by 134.117.251.6 (talk) 22:54, 23 September 2010 (UTC)

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)

Java implementation (II)

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)

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)

I think you're right. I implemented this using a straightforward semaphore in Java, and all of the philosophers starve. The waiter requires knowledge of how many forks each philosopher is holding. — Preceding unsigned comment added by 86.177.125.249 (talk) 12:36, 27 March 2012 (UTC)

I agree. I see not simple way to make it work. I have removed the solution and introduced another one using a somewhat similar theme. — Preceding unsigned comment added by 188.109.111.90 (talk) 02:22, 28 February 2014 (UTC)

Obvious solution?

Philosopher one picks up two forks and eats
philosopher one stops eating and puts down both forks
philosopher two picks up two forks and eats
etc.

Why isn't this allowed? 143.92.1.33 (talk) 02:18, 14 November 2012 (UTC)

Apparently, the problem still isn't being stated clearly enough. There are two problems with your proposal:

• It is essential that forks can only be picked up one by one.
• This is not a problem of sequential program design, but of concurrent program design. The problem is how to design behavior of communicating actors (the philosophers) such that their interaction will never produce deadlock or starvation. You implicitly introduce the notion of taking turns, without explaining how this is implemented: is there a supervisor who keeps track of whose turn it is and instructs the phlosophers what to do? Or is there a turn-keeping device that the philosophers read and write in addition to picking up forks? In any case, you introduce an additional element and additional actions without telling us the details of how it works. The correctness of your proposal very much depends on those details. Rp (talk) 00:09, 19 November 2012 (UTC)

Order of Solutions

I suggest to place the 'Resource hierarchy solution' first: 1) It is the solution originally proposed by Dijkstra. 2) As opposed to the solution currently placed first, it requires no external component. Lklundin (talk) 12:38, 13 February 2013 (UTC)

More Efficient Variant of 'Resource hierarchy solution'

This following variant of the 'Resource hierarchy solution' is also a solution, and a more efficient one at that: 1) When a philosopher sits next to a even-numbered fork, this fork is always the one he takes first. 2) In case of an odd number of forks, the philosopher sitting between forks number 1 and n always takes fork number 1 first. 3) As in the original solution, the fork first put down by the philosopher is the one picked up last, followed by the other.

While in the worst case of the 'Resource hierarchy solution' only one philosopher can eat, with the above scheme n/2 philosophers can always eat.

I.e. for n > 3, the above variant is more efficient.

This is surely not OR, it is either obvious or described in some source. Lklundin (talk)

BY Kaushal :-Dining philosophers problem Solution

The Dining philosophers problem has a solution but by a unique way that is.. First should be a condition that at a time a phiolospher have both fork from his left & right side by his neibhours and after a limit time he should put on the down for a limited few second and by this the other philosopher have a chance to put both forks if there are released from the both side at a time in this have vo caondition to clean the fork..and by this this should be continue...... — Preceding unsigned comment added by 119.226.42.242 (talk) 07:11, 7 August 2013 (UTC)

Problems with the Audience solution

I've never heard of the "audience solution" before. I'm completely unable to find any information about it; there's no link to the content of the source, and I can't find any reference to "M Ruen" except possibly a listing of dean's list students.

Analyzing the solution, I don't see how it's different from Dijkstra's solution. The fifth philosopher, who's sitting backwards, tries to grab his "left" and "right" forks, but because he's backwards these are actually the right and left forks, respectively. In other words, he tries to grab them in the reverse order as all the other philosophers, which is exactly what Dijkstra's solution entails. And if that's the case, then the conclusion as presented here is wrong, because up to 2 diners could be eating at the same time, depending on the concurrency. --Bigpeteb (talk) 19:04, 1 May 2014 (UTC)

I agree, this is just a strangely modified version of Dijkstra's version. It would also be very dangerous in practice, as the fifth philosopher could easily poke someone in the eye while bringing the forks from the table to their mouth :-) The explanation is also incomplete, as it is implicitly assuming the rule that the philosophers choose the left fork first without stating this. And the name doesn't make sense either - it just about works for five philosophers, but if you had a table with, say, 10 philosophers then more than one would have to turn around to see the 'event'.

I propose deleting this solution, as it serves no purpose. Unless there are any objections, I'll do this in a couple of days. Peturb (talk) 08:55, 29 May 2014 (UTC)

I have deleted this section as it violates WP:USI. I also suspect it violates WP:NOTMADEUP, as the only edits to this section come from an IP address which is based at an ISP close to the University of North Dakota (which is given as the affiliation of the originator). Finally, as mentioned above, it adds nothing to the article. Peturb (talk) 15:28, 1 June 2014 (UTC)

Feeding Philosophers

Is a bad idea. Let them starve.137.205.183.82 (talk) 13:33, 13 April 2015 (UTC)

Arbitrator solution is simplest

An arbitrator can handle the fork allocation by using a bit mask. Each fork is represented as a bit. When a philosopher attempts to acquire the forks, he asks the arbitrator to assign the 2 forks to him. The arbitrator can synchronously test both bits and refuse the request when either are already set. If the bits are zero, the arbitrator synchronously marks both bits and notifies the philosopher to start eating. The philosopher notifies the arbitrator that he is finished and the arbitrator synchronously turns off the bits.

This design can be implemented through a compare-and-swap machine instruction to fetch or store the bit mask. A simple loop for an unequal compare refreshes the local copy of the bit mask and a retry. This is guaranteed not to starve, suspend, or spin indefinitely, because each philosopher is not "holding" a lock, but merely synchronously inspecting bits and changing the bits with a concurrent update mechanism. A software spinlock (with proper memory barriers) can be used instead of a hardware compare-and-swap for the very short critical section that fetches, compares, and updates the bit mask.71.237.53.70 (talk) 03:47, 20 May 2015 (UTC)

sourceforge.net/projects/javamutex/ includes a sample solution using an efficient software spinlock mutex to compare-and-swap the bit mask.71.237.53.70 (talk) 21:28, 21 May 2015 (UTC)

That is interesting from a computer science perspective although I have to wonder what 'efficient' means in the combined context of 'bit mask' and 'java'. But I digress. Wikipedia has the limitation that we cannot accept so called original research, i.e. research (or other information) that has not been published via a so called reliable source. Is there such a reliable source that describes the software in question? Lklundin (talk) 22:23, 21 May 2015 (UTC)

That's why this is in the Talk section, rather than the Article section. The software mutex is a java implementation of the Peterson (1981) algorithm published in "Algorithms for Mutual Exclusion", M. Raynal, ISBN 0-262-18119-3..71.237.53.70 (talk) 22:35, 21 May 2015 (UTC)

I feel this confuses concept with implementation. This problem is conceptual; terms such as software shouldn't occur in descriptions of its solution. Besides, the given solution doesn't actually solve the problem: the magic spinlock mutex somehow needs guaranteed mutually exclusive access to those bits, while the point of the dining philosopher's problem is finding a solution that can work without such a guarantee. Rp (talk) 14:48, 18 March 2018 (UTC)

There are bigger problems. It might even be true that the arbitrator solution is the "simplest"; it uses simple logic, without restrictions like "each philosopher must obtain his forks in numerically ascending order" that are quite uncommon in most other software. But "simplest" is not the only useful metric to judge an algorithm by. The arbitrator solution doesn't scale. If you had 1000 philosophers, you would still have only one arbitrator, which would be a big source of resource contention. Whereas in solutions with a lock for each fork, up to half of the philosophers can obtains their forks and eat simultaneously. --Bigpeteb (talk) 15:54, 19 March 2018 (UTC)

They

Is it really necessary to use "they" to refer to individual philosophers? When reading the text, I was at first confused and then irritated. 37.99.61.154 (talk) 22:45, 26 January 2019 (UTC)

Forks + chopsticks = confusion

As currently written, the problem statement refers to chopsticks, and subsequent discussion discusses forks. I have seen discussion above about the relative pros and cons of using one or the other. The problem is changing from one to the other in the middle of the discussion just results in confusion. Editing has even resulted in the nonsense "Each of chopstick" in the problem statement.

On balance, and since the famous version of the problem as reworked by Tony Hoare refers to forks, we should use them. A sentence already exists explaining the cultural assumption that is being made. So, I propose:

"Five silent philosophers sit at a round table with bowls of spaghetti. A single fork is placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can eat spaghetti only when they have both the fork on their left and right. Each fork can be held by one and only one philosopher and so a philosopher can use them only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both the forks in their original positions so that the forks become available to the others at the table. A philosopher can only take the fork on their right and the one on their left as they become available and they cannot start eating before getting both the forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think." — Preceding unsigned comment added by Malpensilo (talk • contribs) 08:55, 27 October 2020 (UTC)

Why are forks used instead of chopsticks.

5 philosophers eating chow mein with chopsticks would make more sense than eating spaghetti with 2 forks as each person only has one chopstick. Superdoggo (talk) 03:53, 16 March 2022 (UTC)

Video stops in the middle

The video in the lemma stops in the middle. Heronils (talk) 12:28, 15 October 2023 (UTC)