Professional C__ - Marc Gregoire [385]
A difficult part in multithreaded programming is to parallelize your algorithm, which is highly dependent on the type of your algorithm. Other difficult parts are preventing race conditions and deadlocks. These will be discussed in the following section.
Race Conditions and Deadlocks
Race conditions can occur when multiple threads want to read/write to a shared memory location. For example, suppose you have a shared variable and one thread increments this value while another thread decrements it. Incrementing and decrementing the value means that the current value needs to be retrieved from memory, incremented or decremented, and stored back in memory. On older architectures, for example PDP-11 and VAX, this used to be implemented with an INC processor instruction which was atomic. On multicore x86 processors, the INC instruction is not atomic anymore, meaning that the CPU could execute other instructions in the middle of this operation, which might cause the code to retrieve a wrong value.
The following table shows the result when the increment is finished executing before the decrement starts, and assumes that the initial value is 1:
THREAD 1 (INCREMENT) THREAD 2 (DECREMENT)
load value (value = 1)
increment value (value = 2)
store value (value = 2)
load value (value = 2)
decrement value (value = 1)
store value (value = 1)
The final value stored in memory is 1. When the decrement thread is finished before the increment thread starts, the final value is also 1, as seen in the following table:
THREAD 1 (INCREMENT) THREAD 2 (DECREMENT)
load value (value = 1)
decrement value (value = 0)
store value (value = 0)
load value (value = 0)
increment value (value = 1)
store value (value = 1)
However, when the instructions get interleaved on the CPU, the result is different:
THREAD 1 (INCREMENT) THREAD 2 (DECREMENT)
load value (value = 1)
increment value (value = 2)
load value (value = 1)
decrement value (value = 0)
store value (value = 2)
store value (value = 0)
The final result in this case is 0. In other words, the effect of the increment operation is lost. This is a race condition.
To prevent race conditions try to design your programs so that multiple threads do not need to read or write to shared memory locations. You can also use a synchronization method as described in the Mutual Exclusion section later in this chapter, or if possible, use atomic operations described in the next section.
If you opt to solve the race condition by using a synchronization method such as mutual exclusion, you might run into another common problem with multithreaded programming: deadlocks. Deadlocks are threads blocking indefinitely because they are waiting to acquire access to resources currently locked by other blocked threads.
For example, suppose you have two threads and two resources, A and B. Both threads require a lock on both resources, but they acquire the locks in different order. The following table shows this situation in pseudo code:
THREAD 1 THREAD 2
Lock A Lock B
Lock B Lock A
// ... compute // ... compute
Release B Release A
Release A Release B
Now, imagine that the code in the two threads is executed in the following order:
Thread 1: Lock A
Thread 2: Lock B
Thread 1: Lock B (waits, because lock held by Thread 2)
Thread 2: Lock A (waits, because lock held by Thread 1)
Both threads are now waiting indefinitely, a deadlock situation. Figure 22-2 shows a graphical representation of this deadlock situation. Thread 1 is holding a lock on resource A and is waiting to get a lock on resource B. Thread 2 is holding a lock on resource B and is waiting to get a lock on resource A.
FIGURE 22-2
In this graphical representation, you see a cycle that depicts the deadlock situation. Both threads will wait indefinitely, unless you include mechanisms in your program to break these kinds of deadlocks. One possible solution is to try for a certain time to acquire a lock on a resource. If the lock could not be obtained within