thumb|In the problem, each philosopher has a bowl of spaghetti and can reach the two forks on either side of them.

In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.

It was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals.

Soon after, Tony Hoare gave the problem its present form.

Problem statement

Five philosophers dine together at the same table. Each philosopher has their own plate at the table. There is a fork between each pair of adjacent plates. The dish served is a kind of spaghetti which has to be eaten with two forks. Each philosopher can only alternately think and eat. Moreover, a philosopher can only eat their spaghetti when they have both a left and a right fork. Thus, two forks will only be available when their two nearest neighbors are thinking, not eating. After an individual philosopher finishes eating, they will put down both forks.

The problem is how to design a regimen (a concurrent algorithm) such that any philosopher will not 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 (an issue of incomplete information).

Problems

The problem was designed to illustrate the challenges of avoiding deadlock, a system state in which no progress is possible. To see that a proper solution to this problem is not obvious, consider a proposal in which each philosopher is instructed to behave as follows:

  • think unless the left fork is available; when it is, pick it up;
  • think unless the right fork is available; when it is, pick it up;
  • when both forks are held, eat for a fixed amount of time;
  • put the left fork down;
  • put the right fork down;
  • repeat from the beginning.

With these instructions, the situation may arise where each philosopher holds the fork to their left; in that situation, they will all be stuck forever, waiting for the other fork to be available: it is a deadlock.

Resource starvation, mutual exclusion, and livelock are other types of sequence and access problems.

Solutions

These four conditions are necessary for a deadlock to occur:

  • mutual exclusion (no fork can be simultaneously used by multiple philosophers)
  • resource holding (the philosophers hold a fork while waiting for the second)
  • non-preemption (no philosopher can take a fork from another), and
  • circular wait (each philosopher may be waiting on the philosopher to their left)

A solution must negate at least one of those four conditions. In practice, negating mutual exclusion or non-preemption somehow can give a valid solution, but most theoretical treatments assume that those assumptions are non-negotiable, instead attacking resource holding or circular waiting (often both).

Dijkstra's solution

Dijkstra's solution negates resource holding; the philosophers atomically pick up both forks or wait, never holding exactly one fork outside of a critical section. To accomplish this, Dijkstra's solution uses one mutex, one semaphore per philosopher, and one state variable per philosopher. This solution is more complex than the resource hierarchy solution.

For GCC: compile with <syntaxhighlight lang="bash">g++ src.cpp -std=c++11 -pthread</syntaxhighlight>

<syntaxhighlight lang="c++">

  1. include <iostream>
  2. include <chrono>
  3. include <mutex>
  4. include <thread>
  5. include <random>
  6. include <ctime>

using namespace std;

int myrand(int min, int max) {

static mt19937 rnd(time(nullptr));

return uniform_int_distribution<>(min,max)(rnd);

}

void philosopher(int ph, mutex& ma, mutex& mb, mutex& mo) {

for (;;) { // prevent thread from termination

int duration = myrand(200, 800);

{

// Block { } limits scope of lock

lock_guard<mutex> gmo(mo);

cout<<ph<<" thinks "<<duration<<"ms\n";

}

this_thread::sleep_for(chrono::milliseconds(duration));

{

lock_guard<mutex> gmo(mo);

cout<<"\t\t"<<ph<<" is hungry\n";

}

lock_guard<mutex> gma(ma);

// sleep_for() Delay before seeking second fork can be added here but should not be required.

lock_guard<mutex> gmb(mb);

duration = myrand(200, 800);

{

lock_guard<mutex> gmo(mo);

cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";

}

this_thread::sleep_for(chrono::milliseconds(duration));

}

}

int main() {

cout<<"dining Philosophers C++11 with Resource hierarchy\n";

mutex m1, m2, m3, m4, m5; // 5 forks are 5 mutexes

mutex mo; // for proper output

// 5 philosophers are 5 threads

thread t1([&] {philosopher(1, m1, m2, mo);});

thread t2([&] {philosopher(2, m2, m3, mo);});

thread t3([&] {philosopher(3, m3, m4, mo);});

thread t4([&] {philosopher(4, m4, m5, mo);});

thread t5([&] {philosopher(5, m1, m5, mo);}); // Force a resource hierarchy

t1.join(); // prevent threads from termination

t2.join();

t3.join();

t4.join();

t5.join();

}

</syntaxhighlight>

Arbitrator solution

Another approach is to guarantee that a philosopher can only pick up both forks or none by introducing an arbitrator to replace circular waiting, e.g., a waiter. In order to pick up the forks, a philosopher must ask permission of the waiter. The waiter gives permission to only one philosopher at a time until the philosopher has picked up both of his forks. Putting down a fork is always allowed. The waiter can be implemented as a mutex.

In addition to introducing a new central entity (the waiter), this approach can result in reduced parallelism: if a philosopher is eating and one of his neighbors is requesting the forks, all other philosophers must wait until this request has been fulfilled, even if forks for them are still available.

Limiting the number of diners in the table

A solution presented by William Stallings is to allow a maximum of n-1 philosophers to sit down at any time. The last philosopher would have to wait (for example, using a semaphore) for someone to finish dining before he "sits down" and requests access to any fork. This negates circular wait, guaranteeing that at least one philosopher may always acquire both forks, allowing the system to make progress.

Chandy/Misra solution

In 1984, K. Mani Chandy and J. Misra proposed a different solution to the dining philosophers problem to allow for arbitrary agents (numbered P<sub>1</sub>, ..., P<sub>n</sub>) to contend for an arbitrary number of resources, unlike Dijkstra's solution. It is also completely distributed and requires no central authority after initialization. However, it violates the requirement that "the philosophers do not speak to each other" (due to the request messages).

  1. 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 P<sub>n</sub>). Each fork can either be dirty or clean. Initially, all forks are dirty.
  2. When a philosopher wants to use a set of resources (i.e., eat), the said philosopher must obtain the forks from his contending neighbors. For all such forks that the philosopher does not have, he sends a request message.
  3. 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 the philosopher sends the fork over, he cleans the fork before doing so.
  4. After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, the philosopher who has just finished eating cleans the fork and sends it.

This solution also allows for a large degree of concurrency and will solve an arbitrarily large problem.

It also solves the starvation problem. The clean/dirty labels act as a way of giving preference to the most "starved" processes, and a disadvantage to processes that have just "eaten". One could compare their solution to one where philosophers are not allowed to eat twice in a row without letting others use the forks in between. Chandy and Misra's solution is more flexible than that, but has an element tending in that direction.

In their analysis, they derive a system of preference levels from the distribution of the forks and their clean/dirty states. They show that this system may describe a directed acyclic graph, and if so, the operations in their protocol cannot turn that graph into a cyclic one. This guarantees that deadlock cannot occur by negating circular waiting. However, if the system is initialized to a perfectly symmetric state, like all philosophers holding their left side forks, then the graph is cyclic at the outset, and their solution cannot prevent a deadlock. Initializing the system so that philosophers with lower IDs have dirty forks ensures the graph is initially acyclic.

See also

  • Cigarette smokers problem
  • Producers-consumers problem
  • Readers-writers problem
  • Sleeping barber problem

References

Bibliography

  • Dijkstra, E. W. (1971, June). [//www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF Hierarchical ordering of sequential processes]. Acta Informatica 1(2): 115–138.
  • Lehmann, D. J., Rabin, M. O. (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pp.&nbsp;133–138.
  • Discussion of the problem with solution code for 2 or 4 philosophers
  • Formal specification of the Chandy-Misra solution written in TLA+
  • Distributed symmetric solutions
  • Programming the Dining Philosophers with Simulation
  • [//www.doc.ic.ac.uk/~jnm/concurrency/classes/Diners/Diners.html Interactive example] of the Philosophers problem (Java required)
  • Satan Comes to Dinner
  • [//www.cs.kent.ac.uk/projects/ofa/java-threads/0.html Wot No Chickens?] – Peter H. Welch proposed the Starving Philosophers variant that demonstrates an unfortunate consequence of the behaviour of Java thread monitors is to make thread starvation more likely than strictly necessary.
  • [//www.cs.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html ThreadMentor]
  • Solving The Dining Philosophers Problem With Asynchronous Agents
  • Solution using Actors