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.
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 in which 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
// Dining Philosophers without 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);
if(i < (sz-1))
executor.execute(
new Philosopher(c[i], c[j], d, i, ponder));
else
executor.execute(
new Philosopher(c[j], 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.
Summary
The goal of this chapter was to give you the foundations of concurrent programming with threads:
1. You can (at least in appearance) run multiple independent tasks.
2. You must consider all the possible problems when these tasks shut down. Objects or other tasks may disappear before tasks are finished with them.
3. Tasks can collide with each other over shared resources. The mutex is the basic tool used to prevent these collisions.
4. Tasks can deadlock if they are not carefully designed.
However, there are multiple additional facets of threading and tools to help you solve threading problems. The ZThreads library contains a number of these tools, such as semaphores and special types of queues, similar to the one you saw in this chapter. Explore that library as well as other resources on threading to gain more in-depth knowledge.
It is vital to learn when to use concurrency and when to avoid it. The main reasons to use it are:
· To manage a number of tasks whose intermingling will make more efficient use of the computer (including the ability to transparently distribute the tasks across multiple CPUs).
· To allow better code organization.
· To be more convenient for the user.
The classic example of resource balancing is to use the CPU during I/O waits. The classic example of user convenience is to monitor a "stop" button during long downloads.
An additional advantage to threads is that they provide "light" execution context switches (on the order of 100 instructions) rather than "heavy" process context switches (thousands of instructions). Since all threads in a given process share the same memory space, a light context switch changes only program execution and local variables. A process change—the heavy context switch—must exchange the full memory space.
The main drawbacks to multithreading are:
· Slowdown occurs while waiting for shared resources.
· Additional CPU overhead is required to manage threads.
· Unrewarded complexity arises from poor design decisions.
· Opportunities are created for pathologies such as starving, racing, deadlock, and livelock.
· Inconsistencies occur across platforms. When developing the original material (in Java) for this chapter, we discovered race conditions that quickly appeared on some computers but that wouldn’t appear on others. The C++ examples in this chapter behaved differently (but usually acceptably) under different operating systems. If you develop a program on a computer and things seem to work right, you might get an unwelcome surprise when you distribute it.