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 <iostream>
#include <cstdlib>
class Chopstick {
ZThread::Mutex lock;
ZThread::Condition notTaken;
bool taken;
public:
Chopstick() : notTaken(lock), taken(false) {}
void take() {
ZThread::Guard<ZThread::Mutex> g(lock);
while(taken)
notTaken.wait();
taken = true;
}
void drop() {
ZThread::Guard<ZThread::Mutex> g(lock);
taken = false;
notTaken.signal();
}
};
class Philosopher : public ZThread::Runnable {
Chopstick& left;
Chopstick& right;
int id;
int ponderFactor;
ZThread::CountedPtr<Display> display;
int randSleepTime() {
if(ponderFactor == 0) return 0;
return rand()/(RAND_MAX/ponderFactor) * 250;
}
public:
Philosopher(Chopstick& l, Chopstick& r,
ZThread::CountedPtr<Display>& 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).
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 <cstdlib>
using namespace ZThread;
using namespace std;
int main(int argc, char* argv[]) {
int ponder = argc > 1 ? atoi(argv[1]) : 5;
cout << "Press <ENTER> to quit" << endl;
static const int sz = 5;
try {
CountedPtr<Display> 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;
}
} ///:~
128
At the time of this writing, Cygwin (www.cygwin.com) was undergoing much-needed changes and improvements to its threading support, but we were still unable to observe deadlocking behavior with this program under the available version of Cygwin. The program deadlocked quickly under, for example, Linux.