Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com
Answertopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions
Privacy Policy

  




 

 

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Deadlock

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:[162]

//: 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

 
 
   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire