• Five philosophers sit around a circular table, each in front of a big plate of spaghetti.
• A single fork is placed in between adjacently seated philosophers.
• Every day, each philosopher comes to the table to think, eat, think, eat, think, and eat.
  That's three square meals of spaghetti after three extended think sessions.
  • Each philosopher keeps to himself as he thinks. Sometime he thinks for a long time, and sometimes he thinks for only a short time.
  • After each philosopher has thought for a while, he proceeds to eat one of his three daily meals. In order to eat, he must grab hold of two forks—the one to his left, and the one to his right. Once that has happened, he chows down on spaghetti to nourish his big, philosophizing brain. When he's full, he puts down the forks in the same order he picked them up and returns to thinking for a while.

Here's the core of a C++ program simulating what we just described (click here for full program):

static const unsigned int kNumPhilosophers = 5; // must be 2 or greater
static const unsigned int kNumForks = kNumPhilosophers;
static const unsigned int kNumMeals = 3;

static mutex forks[kNumForks]; // forks modeled as mutexes

static void think(unsigned int id) {
  cout << oslock << id << " starts thinking." << endl << osunlock;
  sleep_for(getThinkTime());
  cout << oslock << id << " all done thinking. " << endl << osunlock;
}

static void eat(unsigned int id) {
  unsigned int left = id;
  unsigned int right = (id + 1) % kNumForks;
  forks[left].lock();
  forks[right].lock();
  cout << oslock << id << " starts eating om nom nom nom." << endl << osunlock;
  sleep_for(getEatTime());
  cout << oslock << id << " all done eating." << endl << osunlock;
  forks[left].unlock();
  forks[right].unlock();
}

static void philosopher(unsigned int id) {
  for (unsigned int i = 0; i < kNumMeals; i++) {
    think(id);
    eat(id);
  }
}

int main(int argc, const char *argv[]) {
  thread philosophers[kNumPhilosophers];
  for (unsigned int i = 0; i < kNumPhilosophers; i++) 
    philosophers[i] = thread(philosopher, i);
  for (thread& p: philosophers)
    p.join();
  return 0;
}

• The program models each of the forks as a mutex. Each philosopher either has the fork or doesn't, and we want the act of grabbing the fork to operate as atomic and transactional.
• The problem appears to work well (we'll run it several times in lecture), but it doesn't guard against this possibility: that each philosopher emerges from his deep thinking, successfully grabs the fork to his left, and then gets pulled off the processor because his time slice is over.
  • If this pathological scheduling pattern presents itself, eventually all each philosopher will be blocked from grabbing the fork on his right.
  • That will leave the program in a state where all five threads are entrenched in a state of deadlock, because each philosopher is stuck waiting for the philosopher to his right to let go of his left fork.
  • It's like one, big, intellectual silence contest, and the program is prevented from making progress.