Thinking In C++. Volume 2: Practical Programming

Each Philosopher holds references to their left and right Chopstick so they can attempt to pick those up. The goal of the Philosopher is to think part of the time and eat part of the time, and this is expressed in main( ). However, you will observe that if the Philosophers spend very little time thinking, they will all be competing for the Chopsticks while they try to eat, and deadlock will happen much more quickly. So you can experiment with this, the ponderFactor weights the length of time that a Philosopher tends to spend thinking and eating. A smaller ponderFactor will increase the probability of deadlock.

In Philosopher::run( ), each Philosopher just thinks and eats continuously. You see the Philosopher thinking for a randomized amount of time, then trying to take( ) the right and then the left Chopstick, eating for a randomized amount of time, and then doing it again. Output to the console is synchronized as seen earlier in this chapter.

This problem is interesting because it demonstrates that a program can appear to run correctly but actually be deadlock prone. To show this, the command-line argument allows you to adjust a factor to affect the amount of time each philosopher spends thinking. If you have lots of philosophers and/or they spend a lot of time thinking, you may never see the deadlock even though it remains a possibility. A command-line argument of zero tends to make it deadlock fairly quickly:[128]

//: C11:DeadlockingDiningPhilosophers.cpp

// Dining Philosophers with Deadlock

//{L} ZThread

#include "DiningPhilosophers.h"

#include "zthread/ThreadedExecutor.h"

#include

using namespace ZThread;

using namespace std;

int main(int argc, char* argv[]) {

  int ponder = argc > 1 ? atoi(argv[1]) : 5;

  cout << "Press to quit" << endl;

  static const int sz = 5;

  try {

    CountedPtr d(new Display);

    ThreadedExecutor executor;

    Chopstick c[sz];

    for(int i = 0; i < sz; i++) {

      int j = (i+1) > (sz-1) ? 0 : (i+1);

      executor.execute(

        new Philosopher(c[i], c[j], d, i, ponder));

    }

    cin.get();

    executor.interrupt();

    executor.wait();

  } catch(Synchronization_Exception& e) {

    cerr << e.what() << endl;

  }

} ///:~

Note that the Chopstick objects do not need internal identifiers; they are identified by their position in the array c. Each Philosopher is given a reference to a left and right Chopstick object when constructed; these are the utensils that must be picked up before that Philosopher can eat. Every Philosopher except the last one is initialized by situating that Philosopher between the next pair of Chopstick objects. The last Philosopher is given the zeroth Chopstick for its right Chopstick, so the round table is completed. That’s because the last Philosopher is sitting right next to the first one, and they both share that zeroth chopstick. With this arrangement, it’s possible at some point for all the philosophers to be trying to eat and waiting on the philosopher next to them to put down their chopstick, and the program will deadlock.

If the ponder value is nonzero, you can show that if your threads (philosophers) are spending more time on other tasks (thinking) than eating, then they have a much lower probability of requiring the shared resources (chopsticks), and thus you can convince yourself that the program is deadlock free, even though it isn’t.

To repair the problem, you must understand that deadlock can occur if four conditions are simultaneously met:

1.       Mutual exclusion. At least one resource used by the threads must not be shareable. In this case, a chopstick can be used by only one philosopher at a time.

2.      At least one process must be holding a resource and waiting to acquire a resource currently held by another process. That is, for deadlock to occur, a philosopher must be holding one chopstick and waiting for the other one.

3.      A resource cannot be preemptively taken away from a process. All processes must only release resources as a normal event. Our philosophers are polite, and they don’t grab chopsticks from other philosophers.

4.      A circular wait must happen, whereby a process waits on a resource held by another process, which in turn is waiting on a resource held by another process, and so on, until one of the processes is waiting on a resource held by the first process, thus gridlocking everything. In DeadlockingDiningPhilosophers.cpp, the circular wait happens because each philosopher tries to get the right chopstick first and then the left.