Dining philosophers problem

Summary

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.

Illustration of the dining philosophers problem.

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 formulation.[1][2][3][4]

Problem statementEdit

Five philosophers, numbered from 0 through 4, live in a house where the table is laid for them; each philosopher has their own place at the table. Their only problem – besides those of philosophy – is that the dish served is a very difficult kind of spaghetti, that has to be eaten with two forks. There are two forks next to each plate, so that presents no difficulty: as a consequence, however, no two neighbours may be eating simultaneously.

A very naive solution associates with each fork a binary semaphore with the initial value = 1 (indicating that the fork is free) and, naming in each philosopher these semaphores in a local terminology[clarification needed], we could think the following solution for the philosopher's life adequate.

But this solution – although it guarantees that no two neighbours are eating simultaneously – must be rejected because it contains the danger of the deadly embrace (deadlock). When all five philosophers get hungry simultaneously, each will grab his left-hand fork and from that moment onwards the group is stuck.

In order to be able to give a formal description, we associate with each philosopher a state variable, "C" say, where C[i] = 0 means: philosopher i is thinking, C[i] = 1 means: philosopher i is hungry, C[i] = 2 means: philosopher i is eating.

Now each philosopher will go cyclically through the states 0, 1, 2, 0, ...[5]

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher at a time and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can only take the fork on their right or the one on their left as they become available, and they cannot start eating before getting both 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.

ProblemsEdit

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 until the left fork is available; when it is, pick it up;
  • think until the right fork is available; when it is, pick it up;
  • when both forks are held, eat for a fixed amount of time;
  • then, put the right fork down;
  • then, put the left fork down;
  • repeat from the beginning.

This attempted solution fails because it allows the system to reach a deadlock state, in which no progress is possible. This is a state in which each philosopher has picked up the fork to the left, and is waiting for the fork to the right to become available. With the given instructions, this state can be reached, and when it is reached, each philosopher will eternally wait for another (the one to the right) to release a fork.

Resource starvation might also occur independently of deadlock if a particular philosopher is unable to acquire both forks because of a timing problem. For example, there might be a rule that the philosophers put down a fork after waiting ten minutes for the other fork to become available and wait a further ten minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up the left fork at the same time the philosophers will wait ten minutes until they all put their forks down and then wait a further ten minutes before they all pick them up again.

Mutual exclusion is the basic idea of the problem; the dining philosophers create a generic and abstract scenario useful for explaining issues of this type. The failures these philosophers may experience are analogous to the difficulties that arise in real computer programming when multiple programs need exclusive access to shared resources. These issues are studied in concurrent programming. The original problems of Dijkstra were related to external devices like tape drives. However, the difficulties exemplified by the dining philosophers problem arise far more often when multiple processes access sets of data that are being updated. Complex systems such as operating system kernels use thousands of locks and synchronizations that require strict adherence to methods and protocols if such problems as deadlock, starvation, and data corruption are to be avoided.

SolutionsEdit

Dijkstra's solutionEdit

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.[6][7] This is a C++20 version of Dijkstra's solution with Tanenbaum's changes:

#include <iostream>
#include <chrono>
#include <thread>
#include <mutex>
#include <semaphore>
#include <random>

const int N = 5;          // number of philosophers
enum {
  THINKING=0,             // philosopher is thinking
  HUNGRY=1,               // philosopher is trying to get forks
  EATING=2,               // philosopher is eating
};  

#define LEFT (i+N-1)%N    // number of i's left neighbor
#define RIGHT (i+1)%N     // number of i's right neighbor

int state[N];             // array to keep track of everyone's state
std::mutex mutex_;        // mutual exclusion for critical regions
std::binary_semaphore s[N]{0, 0, 0, 0, 0}; 
                          // one semaphore per philosopher
std::mutex mo;            // for synchronized cout

int myrand(int min, int max) {
  static std::mt19937 rnd(std::time(nullptr));
  return std::uniform_int_distribution<>(min,max)(rnd);
}

void test(int i) {        // i: philosopher number, from 0 to N-1
  if (state[i] == HUNGRY 
   && state[LEFT] != EATING && state[RIGHT] != EATING) {
    state[i] = EATING;
    s[i].release();
  }
}

void think(int i) {
  int duration = myrand(400, 800);
  {
    std::lock_guard<std::mutex> gmo(mo);
    std::cout<<i<<" thinks "<<duration<<"ms\n";
  }
  std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}

void take_forks(int i) {  // i: philosopher number, from 0 to N-1
  mutex_.lock();          // enter critical region
  state[i] = HUNGRY;      // record fact that philosopher i is hungry
  {
    std::lock_guard<std::mutex> gmo(mo);
    std::cout<<"\t\t"<<i<<" is hungry\n";
  }
  test(i);                // try to acquire 2 forks
  mutex_.unlock();        // exit critical region
  s[i].acquire();         // block if forks were not acquired
} 

void eat(int i) {
  int duration = myrand(400, 800);
  {
    std::lock_guard<std::mutex> gmo(mo);
    std::cout<<"\t\t\t\t"<<i<<" eats "<<duration<<"ms\n";
  }
  std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}

void put_forks(int i) {   // i: philosopher number, from 0 to N-1
  mutex_.lock();          // enter critical region
  state[i] = THINKING;    // philosopher has finished eating
  test(LEFT);             // see if left neighbor can now eat
  test(RIGHT);            // see if right neighbor can now eat
  mutex_.unlock();        // exit critical region
}

void philosopher(int i) { // i: philosopher number, from 0 to N-1
  while (true) {          // repeat forever
    think(i);             // philosopher is thinking
    take_forks(i);        // acquire two forks or block
    eat(i);               // yum-yum, spaghetti
    put_forks(i);         // put both forks back on table
  }
}

int main() {
  std::cout<<"dp_14\n";

  std::thread t0([&] {philosopher(0);});
  std::thread t1([&] {philosopher(1);});
  std::thread t2([&] {philosopher(2);});
  std::thread t3([&] {philosopher(3);});
  std::thread t4([&] {philosopher(4);});
  t0.join();
  t1.join();
  t2.join();
  t3.join();
  t4.join();
}

The function test() and its use in take_forks() and put_forks() make the Dijkstra solution deadlock-free.

Resource hierarchy solutionEdit

This solution assigns a partial order to the resources (the forks, in this case), and establishes the convention that all resources will be requested in order, and that no two resources unrelated by order will ever be used by a single unit of work at the same time. Here, the resources (forks) will be numbered 1 through 5 and each unit of work (philosopher) will always pick up the lower-numbered fork first, and then the higher-numbered fork, from among the two forks they plan to use. The order in which each philosopher puts down the forks does not matter. In this case, if four of the five philosophers simultaneously pick up their lower-numbered fork, only the highest-numbered fork will remain on the table, so the fifth philosopher will not be able to pick up any fork. Moreover, only one philosopher will have access to that highest-numbered fork, so he will be able to eat using two forks.

While the resource hierarchy solution avoids deadlocks, it is not always practical, especially when the list of required resources is not completely known in advance. For example, if a unit of work holds resources 3 and 5 and then determines it needs resource 2, it must release 5, then 3 before acquiring 2, and then it must re-acquire 3 and 5 in that order. Computer programs that access large numbers of database records would not run efficiently if they were required to release all higher-numbered records before accessing a new record, making the method impractical for that purpose.[2]

The resource hierarchy solution is not fair. If philosopher 1 is slow to take a fork, and if philosopher 2 is quick to think and pick its forks back up, then philosopher 1 will never get to pick up both forks. A fair solution must guarantee that each philosopher will eventually eat, no matter how slowly that philosopher moves relative to the others.

The following source code is a C++11 implementation of the resource hierarchy solution for three philosophers. The sleep_for() function simulates the time normally spend with business logic.[8]

#include <iostream>
#include <chrono>
#include <mutex>
#include <thread>
#include <random>
#include <ctime>
using namespace std;
int myrand(int min, int max) {
  static mt19937 rnd(time(nullptr));
  return uniform_int_distribution<>(min,max)(rnd);
}
void phil(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);
    this_thread::sleep_for(chrono::milliseconds(400));
    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;   // 3 forks are 3 mutexes
  mutex mo;           // for proper output
  // 3 philosophers are 3 threads
  thread t1([&] {phil(1, m1, m2, mo);});
  thread t2([&] {phil(2, m2, m3, mo);});
  thread t3([&] {phil(3, m1, m3, mo);});  // Resource hierarchy
  t1.join();  // prevent threads from termination
  t2.join();
  t3.join();
}

Arbitrator solutionEdit

Another approach is to guarantee that a philosopher can only pick up both forks or none by introducing an arbitrator, 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 their 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.

Concurrent algorithm design

Limiting the number of diners in the tableEdit

A solution presented by William Stallings[9] 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 they "sit down" and request access to any fork. This guarantees at least one philosopher may always acquire both forks, allowing the system to make progress.

Chandy/Misra solutionEdit

In 1984, K. Mani Chandy and J. Misra[10] proposed a different solution to the dining philosophers problem to allow for arbitrary agents (numbered P1, ..., Pn) 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 Pn). 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), said philosopher must obtain the forks from their contending neighbors. For all such forks the philosopher does not have, they send a request message.
  3. When a philosopher with a fork receives a request message, they keep the fork if it is clean, but give it up when it is dirty. If the philosopher sends the fork over, they clean the fork before doing so.
  4. After a philosopher is done eating, all their forks become dirty. If another philosopher had previously requested one of the forks, the philosopher that 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. 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 alsoEdit

ReferencesEdit

  1. ^ Dijkstra, Edsger W. EWD-1000 (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)
  2. ^ a b J. Díaz; I. Ramos (1981). Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. Birkhäuser. pp. 323 , 326. ISBN 978-3-540-10699-9.
  3. ^ Hoare, C. A. R. (2004) [originally published in 1985 by Prentice Hall International]. "Communicating Sequential Processes" (PDF). usingcsp.com.
  4. ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 2.3.1 The Dining Philosophers Problem], Pearson Education, Inc.
  5. ^ Dijkstra, Edsger W. EWD-310 (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)
  6. ^ Dijkstra, Edsger W. EWD-310 (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)
  7. ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 2.3.1 The Dining Philosophers Problem], Pearson Education, Inc.
  8. ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 3.3.5 Deadlock Prevention], Pearson Education, Inc.
  9. ^ Stallings, William (2018). Operating systems : internals and design principles (9th ed.). Harlow, Essex, England: Pearson. p. 310. ISBN 1-292-21429-5. OCLC 1009868379.
  10. ^ Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.

BibliographyEdit

  • Silberschatz, Abraham; Peterson, James L. (1988). Operating Systems Concepts. Addison-Wesley. ISBN 0-201-18760-4.
  • Dijkstra, E. W. (1971, June). 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. 133–138.

External linksEdit

  • Dining Philosophers Problem I
  • Dining Philosophers Problem II
  • Dining Philosophers Problem III
  • Discussion of the problem with solution code for 2 or 4 philosophers
  • Discussion of various solutions at the Wayback Machine (archived December 8, 2013)
  • Discussion of a solution using continuation based threads (cbthreads) at the Wayback Machine (archived March 4, 2012)
  • Formal specification of the Chandy-Misra solution written in TLA+
  • Distributed symmetric solutions
  • Programming the Dining Philosophers with Simulation
  • Interactive example of the Philosophers problem (Java required)
  • Satan Comes to Dinner
  • 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.
  • ThreadMentor
  • Solving The Dining Philosophers Problem With Asynchronous Agents
  • Solution using Actors