Race Conditions
Threads bring us a higher likelihood of bugs because they can access shared data without explicit coordination, whereas IPC mechanisms required significant forethought to apply. In fact, the complexity of writing code that behaves properly in threads warrants its own term. Code is thread-safe if it guarantees correctness when running in multiple threads simultaneously.
Most threading bugs are race conditions. Generally speaking, race conditions occur when data writes are not properly coordinated. There are three types of race conditions based on the conflicting operation and its order: write-read, read-write, and write-write.
If asynchronous operations that have ordering dependencies are not properly coordinated, you have a write-read race condition. The value should be generated or written before it is consumed or read. Bugs in this case occur in the code that coordinates the computations. Listing 13-1 shows this kind of situation in JavaScript. The jQuery $.get()asynchronously fetches data from the given URL then runs the supplied callback. In this case, it is nearly certain that it will not finish before build_menu() is called, and menu will be passed to the menu builder without being initialized.
Listing 13-1: A write-read race condition in JavaScript
var menu;
$.get('/menu').done(function(response) {
menu = response;
});
build_menu(menu);
A read-write, also known as a test-then-set, race condition occurs when code uses a value to make a decision about how that value will be changed without ensuring the two operations happen atomically. Let’s look at a simple example, a dysfunctional resource initializer implementation (see Listing 13-2).
Listing 13-2: A simple dysfunctional resource initialization method
1 public Resource initializeResource() {
2 if (resource == null) {
3 resource = new Resource();
4 }
5 return resource;
6 }
The race condition occurs between lines 2 and 3. Consider the following sequence of events.
• Thread A executes line 2 and determines that resource is null.
• The operating system suspends Thread A and resumes Thread B.
• Thread B executes line 2 and determines that resource is null.
• Thread B executes lines 3–5, allocating an instance of Resource and returning it to the caller.
• The operating system suspends Thread B and resumes Thread A.
• Thread A executes lines 3–5, allocating a different instance of Resource and returning it to the caller.
• At some later point in time, Thread B calls initializeResource() again, resource is not null, and the method returns a different instance than on the previous invocation.
What happened to the first instance of Resource, the one allocated by Thread B? It depends on your language. In Java, it is garbage collected once Thread B’s use of it has finished. In C++, it is most likely a memory leak unless you are using some form of thread-safe smart pointers,2 since Thread B has no reason to know it should free it. Regardless of what happens to the memory, you have now created two resources when you meant to create one.
2. Note that not all smart pointer implementations are thread-safe. Be careful!
This demonstrates one of the simplest examples of a critical section, a section of code that must be accessed by only one thread at a time to behave correctly. In some machine architectures, this can even occur at the machine- or byte-code level when the low-level instructions generated by the compiler effectively modify a value separately from its final storage, as you might get during a self-assignment operation (e.g., m += n).
Write-write race conditions occur less frequently in higher-level languages. Instruction-level write-write races occur more frequently, but as a participant in one of the other races at a higher level. Listing 13-3 shows an example of a write-write race condition that may occur if executed in multiple threads. Suppose you have a queue of items waiting to be processed. Previously, you processed it serially but parallelized it for better throughput. Your code assumes that the last item in the queue should be the last processed. However, once you parallelize the item processing, the second to last item could take longer and finish after the last item, recording the wrong item as the last processed.
Listing 13-3: A write-write race condition under certain assumptions. If the threads are processing a queue, for example, and the intent is for the last in the queue to be recorded as the last processed, this may not behave as desired.
public void recordLastProcessed(Item item) {
lastProcessed = item;
}