Other Bugs

Deadlock is, in some sense, a nicer kind of bug. When it happens, it's pretty obvious (as all the processes are stuck), and we can write algorithms to detect and even avoid deadlocks in the first place. But there are other bugs that can happen in concurrent programs that are much harder to detect and fix. We'll look at two of them here: atomicity violations and order violations.

Atomicity Violations

An atomicity violation is a bug that occurs when a program assumes that an operation is atomic (i.e., it happens all at once) when it's not. We talked about atomicity when we discussed the critical-section problem and introduced locks (a.k.a. mutexes) and semaphores as solutions, as well as atomic operations such as test-and-set.

Unfortunately, programmers often make mistakes in their assumptions about atomicity., such as thinking they can “get away with” not using a lock because they believe they understand all the cases that could occur. In fact, figuring out what can happen is extraordinarily difficult for two reasons:

• Humans are terrible at reasoning about concurrency.
• Modern computers don't work the way humans think they do.

Dekker's Example

Let's start with the following code:

int x = 0, y = 0;

Then we have two threads,

A1 | x = 1;
A2 | int r1 = y;

B1 | y = 1;
B2 | int r2 = x;

Carefully work out the possible final values for r1 and r2.

r1=NN, r2=NN — A1, A2, B1, B2
r1=MM, r2=MM — A1, B1, A2, B2

Here's a program you can run to see the possible valid interleavings:

• Try running the program in Online GDB

You'll see that there are six possible interleavings that can occur.

Possible outcomes:

r1 = 0, r2 = 1, x = 1, y = 1: 1 interleavings
  - [A1] x = 1; [A2] r1 = y; [B1] y = 1; [B2] r2 = x

r1 = 1, r2 = 1, x = 1, y = 1: 4 interleavings
  - [A1] x = 1; [B1] y = 1; [A2] r1 = y; [B2] r2 = x
  - [A1] x = 1; [B1] y = 1; [B2] r2 = x; [A2] r1 = y
  - [B1] y = 1; [A1] x = 1; [A2] r1 = y; [B2] r2 = x
  - [B1] y = 1; [A1] x = 1; [B2] r2 = x; [A2] r1 = y

r1 = 1, r2 = 0, x = 1, y = 1: 1 interleavings
  - [B1] y = 1; [B2] r2 = x; [A1] x = 1; [A2] r1 = y

Total interleavings: 6

In OnlineGDB, in the bottom pane, press enter to exit the console, and then add the command-line argument --allow-order-violation to see all 24 conceivable interleavings. Now you can see the six interleavings that would produce r1=0, r2=0.

r1 = 0, r2 = 0, x = 1, y = 1: 6 interleavings
  - [A2] r1 = y; [B1] y = 1; [B2] r2 = x; [A1] x = 1
  - [A2] r1 = y; [B2] r2 = x; [A1] x = 1; [B1] y = 1
  - [A2] r1 = y; [B2] r2 = x; [B1] y = 1; [A1] x = 1
  - [B2] r2 = x; [A1] x = 1; [A2] r1 = y; [B1] y = 1
  - [B2] r2 = x; [A2] r1 = y; [A1] x = 1; [B1] y = 1
  - [B2] r2 = x; [A2] r1 = y; [B1] y = 1; [A1] x = 1

Issue 1: Compiler Reordering

When a compiler sees code like

x = 1;
r1 = y;

it considers the two statements to be independent of each other—each accesses completely different, unrelated things. So the compiler can reorder them as it sees fit, and might generate code like

    movl    y, %eax         ; Read memory location y into register %eax
    movl    $1, x           ; Write 1 to memory location x
    movl    %eax, r1        ; Write the value in %eax to memory location r1

From the compiler's perspective, this code is fine. Finding an instruction to put between a memory load and a memory store can compensate for the delays in memory access. And for most programs, this kind of optimization is a good thing, because in most programs, accesses that look independent are independent.

But that's not the case for concurrent code where other threads can change the values of x and y. In that case, the reordering can lead to bugs.

Issue 2: Store Buffers

Hardware designers try to deal with the slowness of computer memory by using store buffers. When a store instruction is executed, the data is placed in a store buffer, and the store buffer is responsible for writing the data to memory. This method allows the CPU to continue executing instructions while the store buffer is writing to memory.

On a single core, special logic is put in place so that if the code tries to read something from memory that is actually in the store buffer, the CPU will read the value from the store buffer instead of memory. That's store-to-load forwarding.

And that all works great and improves performance—so long as we're not executing concurrent code. In that case, using the store buffer can lead to surprising results: because other cores can't see our store buffer, they'll just read the (stale) value from memory.

The Big Lesson

Programs don't execute the way you think they do. The optimizations made are designed for the common case—sequential programs—and they can lead to surprising results in concurrent programs. Unless you want to take a deep dive into the hardware and compiler, attempting to reason out why it's okay not to use a lock is almost always a bad idea.

Sequential Consistency

Modern systems make as few promises as possible about the order of operations. What programmers desire is sequential consistency, where final outcome is as if operations of all processors are executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. Sequential consistency still allows many possible interleavings, but at least it prohibits some of the more surprising ones.

You only get sequential consistency if you carefully follow the rules of synchronization. And the short version is that, in practice, you're only following the rules if you're using locks.

Order Violations

The second kind of bug we'll look at is order violations. These are bugs that occur when the order of operations is not what you expect. We've already seen an example of this issue in Dekker's example, where the compiler and hardware can reorder instructions in ways that are surprising.

Let's look at an example of a programmer-generated order violation in the cats and mice problem we saw in Homework 3. Let's suppose that in the main thread we had

lock_acquire(animal_lock);
while (active_animals > 0) {
    cv_wait(animal_cv, animal_lock);
}
lock_release(animal_lock);

and in each animal thread, at startup, we had

lock_acquire(animal_lock);
active_animals++;
cv_signal(animal_cv, animal_lock);  // Unnecessary, but it changed, so signal
lock_release(animal_lock);

and, on exit,

lock_acquire(animal_lock);
active_animals--;
cv_signal(animal_cv, animal_lock);  // We need this to signal the main thread
lock_release(animal_lock);

We could run this code and have it appear to work as we'd expect. But there is a bug here.

These kinds of bugs are subtle and hard to detect. They can be especially hard to detect because they can be timing dependent. On a multicore machine, it's far more likely that a child thread will have started before the main thread hits the while loop. But on a single-core machine, it's quite possible that the main thread will exit the loop before any of the child threads have been started.

Again, the lesson here is to use your synchronization primitives carefully. If something needs to wait for something else to have happened, you need to make that wait explicit in your code.

(When logged in, completion status appears here.)