Thinking In C++. Volume 2: Practical Programming

Because threads can become blocked and because objects can have mutexes that prevent threads from accessing that object until the mutex is released, it’s possible for one thread to get stuck waiting for another thread, which in turn waits for another thread, and so on, until the chain leads back to a thread waiting on the first one. You get a continuous loop of threads waiting on each other, and no one can move. This is called deadlock.

If you try running a program and it deadlocks right away, you immediately know you have a problem, and you can track it down. The real problem is when your program seems to be working fine but has the hidden potential to deadlock. In this case, you may get no indication that deadlocking is a possibility, so it will be latent in your program until it unexpectedly happens to a customer. (And you probably won’t be able to easily reproduce it.) Thus, preventing deadlock through careful program design is a critical part of developing concurrent programs.

Let’s look at the classic demonstration of deadlock, invented by Edsger Dijkstra: the dining philosophers problem. The basic description specifies five philosophers (but the example shown here will allow any number). These philosophers spend part of their time thinking and part of their time eating. While they are thinking, they don’t need any shared resources, but when they are eating, they sit at a table with a limited number of utensils. In the original problem description, the utensils are forks, and two forks are required to get spaghetti from a bowl in the middle of the table, but it seems to make more sense to say that the utensils are chopsticks. Clearly, each philosopher will require two chopsticks in order to eat.

A difficulty is introduced into the problem: as philosophers, they have very little money, so they can only afford five chopsticks. These are spaced around the table between them. When a philosopher wants to eat, they must pick up the chopstick to the left and the one to the right. If the philosopher on either side is using a desired chopstick, our philosopher must wait until the necessary chopsticks become available.

//: C11:DiningPhilosophers.h

// Classes for Dining Philosohophers

#ifndef DININGPHILOSOPHERS_H

#define DININGPHILOSOPHERS_H

#include "zthread/Condition.h"

#include "zthread/Guard.h"

#include "zthread/Mutex.h"

#include "zthread/Thread.h"

#include "Display.h"

#include

#include

class Chopstick {

  ZThread::Mutex lock;

  ZThread::Condition notTaken;

  bool taken;

public:

  Chopstick() : notTaken(lock), taken(false) {}

  void take() {

    ZThread::Guard g(lock);

    while(taken)

      notTaken.wait();

    taken = true;

  }

  void drop() {

    ZThread::Guard g(lock);

    taken = false;

    notTaken.signal();

  }

};

class Philosopher : public ZThread::Runnable {

  Chopstick& left;

  Chopstick& right;

  int id;

  int ponderFactor;

  ZThread::CountedPtr display;

  int randSleepTime() {

    if(ponderFactor == 0) return 0;

    return rand()/(RAND_MAX/ponderFactor) * 250;

  }

public:

  Philosopher(Chopstick& l, Chopstick& r,

  ZThread::CountedPtr& disp, int ident,int ponder)

  : left(l), right(r), display(disp),

    id(ident), ponderFactor(ponder) { srand(time(0)); }

  virtual void run() {

    try {

      while(!ZThread::Thread::interrupted()) {

        {

          std::ostringstream os;

          os << *this << " thinking" << std::endl;

          display->output(os);

        }

        ZThread::Thread::sleep(randSleepTime());

        // Hungry

        {

          std::ostringstream os;

          os << *this << " grabbing right" << std::endl;

          display->output(os);

        }

        right.take();

        {

          std::ostringstream os;

          os << *this << " grabbing left" << std::endl;

          display->output(os);

        }

        left.take();

        // Eating

        {

          std::ostringstream os;

          os << *this << " eating" << std::endl;

          display->output(os);

        }

        ZThread::Thread::sleep(randSleepTime());

        right.drop();

        left.drop();

      }

    } catch(ZThread::Synchronization_Exception& e) {

      std::ostringstream os;

      os << *this << " " << e.what() << std::endl;

      display->output(os);

    }

  }

  friend std::ostream&

  operator<<(std::ostream& os, const Philosopher& p) {

    return os << "Philosopher " << p.id;

  }

};

#endif // DININGPHILOSOPHERS_H ///:~

No two Philosophers can take( ) a Chopstick at the same time, since take( ) is synchronized with a Mutex. In addition, if the chopstick has already been taken by one Philosopher, another can wait( ) on the available Condition until the Chopstick becomes available when the current holder calls drop( ) (which must also be synchronized to prevent race conditions).