Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
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 they eat using 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 Philosophers.
#ifndef DININGPHILOSOPHERS_H
#define DININGPHILOSOPHERS_H
#include <string>
#include <iostream>
#include <cstdlib>
#include "zthread/Condition.h"
#include "zthread/Guard.h"
#include "zthread/Mutex.h"
#include "zthread/Thread.h"
#include "Display.h"
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;
}
void output(std::string s) {
std::ostringstream os;
os << *this << " " << s
<< std::endl;
display->output(os);
}
public:
Philosopher(Chopstick& l, Chopstick& r,
ZThread::CountedPtr<Display>& disp, int
ident,int ponder)
: left(l), right(r), id(ident), ponderFactor(ponder),
display(disp) {}
virtual void run() {
try {
while(!ZThread::Thread::interrupted()) {
output("thinking");
ZThread::Thread::sleep(randSleepTime());
// Hungry
output("grabbing right");
right.take();
output("grabbing left");
left.take();
output("eating");
ZThread::Thread::sleep(randSleepTime());
right.drop();
left.drop();
}
} catch(ZThread::Synchronization_Exception& e)
{
output(e.what());
}
}
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 and ensure memory visibility in
multiprocessor systems).
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 adjusts a factor to affect the amount of time
each philosopher spends thinking. If you have lots of philosophers 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:
//: C11:DeadlockingDiningPhilosophers.cpp {RunByHand}
// Dining Philosophers with Deadlock.
//{L} ZThread
#include <ctime>
#include "DiningPhilosophers.h"
#include "zthread/ThreadedExecutor.h"
using namespace ZThread;
using namespace std;
int main(int argc, char* argv[]) {
srand(time(0)); // Seed the random number generator
int ponder = argc > 1 ? atoi(argv[1]) : 5;
cout << "Press <ENTER> to quit"
<< endl;
enum { SZ = 5 };
try {
CountedPtr<Display> d(new Display);
ThreadedExecutor executor;
Chopstick c[SZ];
for(int i = 0; i < SZ; i++) {
executor.execute(
new Philosopher(c[i], c[(i+1) % SZ], 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 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 (using a nonzero ponder value), 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 another one.
3. A resource cannot be preemptively taken away from a process. Processes
only release resources as a normal event. Our philosophers are polite and they
don t grab chopsticks from other philosophers.
4. A circular wait can 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.
Because all these conditions must be met to cause deadlock,
you need to stop only one of them from occurring to prevent deadlock. In this
program, the easiest way to prevent deadlock is to break condition four. This
condition happens because each philosopher is trying to pick up their
chopsticks in a particular sequence: first right, then left. Because of that,
it s possible to get into a situation where each of them is holding their right
chopstick and waiting to get the left, causing the circular wait condition.
However, if the last philosopher is initialized to try to get the left
chopstick first and then the right, that philosopher will never prevent the
philosopher on the immediate right from picking up their left chopstick. In
this case, the circular wait is prevented. This is only one solution to the
problem, but you could also solve it by preventing one of the other conditions
(see advanced threading books for more details):
//: C11:FixedDiningPhilosophers.cpp {RunByHand}
// Dining Philosophers without Deadlock.
//{L} ZThread
#include <ctime>
#include "DiningPhilosophers.h"
#include "zthread/ThreadedExecutor.h"
using namespace ZThread;
using namespace std;
int main(int argc, char* argv[]) {
srand(time(0)); // Seed the random number generator
int ponder = argc > 1 ? atoi(argv[1]) : 5;
cout << "Press <ENTER> to quit"
<< endl;
enum { SZ = 5 };
try {
CountedPtr<Display> d(new Display);
ThreadedExecutor executor;
Chopstick c[SZ];
for(int i = 0; i < SZ; i++) {
if(i < (SZ-1))
executor.execute(
new Philosopher(c[i], c[i + 1], d, i,
ponder));
else
executor.execute(
new Philosopher(c[0], c[i], d, i, ponder));
}
cin.get();
executor.interrupt();
executor.wait();
} catch(Synchronization_Exception& e) {
cerr << e.what() << endl;
}
} ///:~
By ensuring that the last philosopher picks up and puts down
their left chopstick before their right, the deadlock is removed, and the
program will run smoothly.
There is no language support to help prevent deadlock; it s
up to you to avoid it by careful design. These are not comforting words to the
person who s trying to debug a deadlocking program.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |