Invisible Races

By | 2013-06-26

When you’re writing multi-threaded applications, the problem you are working hardest to avoid is that of data races. Here’s an example (assume a 32-bit x86 system):

int global = 0;

void thread1() {
    global += 1;
}

void thread2() {
    global = 0x10000;
}

The race here is pretty obvious. Two threads are accessing the same bit of memory. I’ve discussed these sorts of races before when an interrupt handler acts just like another thread. You have no control of when each thread gets control of the CPU, or even if the two threads are running simultaneously on multiple cores.

The solution is to wrap the shared variable in a lock, as we’ll have seen and done plenty of times before.

Now consider this:

char c1 = 0;
char c2 = 0;

int x, y;

void thread1() {
    c1 = 1;
    x = c1;
}

void thread2() {
    c2 = 1;
    y = c2;
}

The question for the class is this:

What are x and y after these two threads have completed?

I’m sure you’ll realise that the very existence of the question means that the answer “1 and 1”, is not correct.

The answer is actually any of, with no ability to specify:

  • 0 and 0
  • 1 and 0
  • 0 and 1
  • 1 and 1

“What? How?” I hear you cry (it’s what I cried when it was explained to me). There is no shared variable between the two threads. c1 and x are isolated in thread1() and c2 and y are isolated in thread2(). Unfortunately, no, that isn’t true.

The key observation to make is that c1 and c2 are chars on a 32-bit system, and nothing stops the compiler and linker from allocating these two variables to adjacent bytes in memory. It’s not possible to access a single byte on a 32-bit system; you have to read all four bytes that make up the word, modify the 8 of them that you’re interested in and put 32 back. Even if the processor has nice instructions to hide that from you, that’s what it’s doing in the background. Read-modify-write is the hole through which all race conditions drive – another thread can be scheduled any time between the read and the write, and trample all over you.

Modern compilers are meant to prevent this, although short of only allocating 32-bits for every 8-bit value, I’m not entirely sure how they do that.

Terrified? Me too.

Leave a Reply