Fun programming problem: a simple lock-free algorithm
Can the program below ever print “oops?”
#include <stdio.h>
#include <process.h>
struct Globals {
volatile int start;
int a;
int b;
volatile int end;
};
Globals globals;
void WriterThread(void*) {
int i = 0;
while (true) {
globals.start = i;
globals.a = i;
globals.b = i;
globals.end = i;
i++;
}
}
void ReaderThread(void*) {
while (true) {
int end = globals.end;
int a = globals.a;
int b = globals.b;
int start = globals.start;
if (start == end)
if (a != b)
printf("oops! %d != %d\n", a, b);
}
}
void main() {
_beginthread(WriterThread, 0, NULL);
_beginthread(ReaderThread, 0, NULL);
getchar();
}
Answer below....
Keep going....
The code does indeed print “oops” fairly reliably.
So what exactly is going on with this code? First, let’s see what it’s trying to do. Here’s the code again – I’ve annotated some important lines with “statement numbers” to make them easier to discuss.
#include <stdio.h>
#include <process.h>
struct Globals {
volatile int start;
int a;
int b;
volatile int end;
};
Globals globals;
void WriterThread(void*) {
int i = 0;
while (true) {
globals.start = i; //S1
globals.a = i; //S2
globals.b = i; //S3
globals.end = i; //S4
i++;
}
}
void ReaderThread(void*) {
while (true) {
int end = globals.end; //S5
int a = globals.a; //S6
int b = globals.b; //S7
int start = globals.start; //S8
if (start == end)
if (a != b)
printf("oops! %d != %d\n", a, b);
}
}
void main() {
_beginthread(WriterThread, 0, NULL);
_beginthread(ReaderThread, 0, NULL);
getchar();
}
We have one thread that is writing values to globals.a and globals.b, and another thread that is reading these values. The reader expects to see the values in a consistent state – which here means that they satisfy the invariant that a == b, but in real life would probably be much more complex. The simple way to do this, of course, would be to protect these variables with a lock – but presumably the author decided that this would not perform adequately, and so chose to go with a hand-rolled synchronization mechanism.
The idea is that the writer will increment “start” just before updating “a” and “b”, and then after making the updates it will increment “end” to match “start.” The reader starts by reading “end”, then goes ahead and reads “a” and “b”. Having done that, it reads “start”. If start does not equal the previous value of end, then that means the writer might have written to a or b while we were reading them, so we might have read these variables in an inconsistent state – so we throw out the values and try again.
Assuming everything happens as described, this should avoid the race that would otherwise exist between the reader and the writer.
(Yes, this can be foiled by the extremely unlikely case where the reader thread is interrupted for exactly 3^32 iterations of the writer. Let’s ignore that problem for now.)
Our algorithm requires that statement S1 take place before S2, S3, and S4. S4 must take place after S1, S2, and S3. The order of S2 and S3 does not matter. Similarly, S5 must take place before S6, S7, and S8; and S8 must take place after S5, S6, and S7. These sorts of temporal relationships are sometimes notated as “A->B”, meaning that A must precede B. So we can state all of the required temporal relationships in our algorithm as:
S1->S2
S1->S3
S1->S4
S2->S4
S3->S4
S5->S6
S5->S7
S5->S8
S6->S8
S7->S8
C++ generally permits a program to be executed in any order that would produce the same results as if it was executed in “program order,” on a single thread. In fact, the C++ standard says absolutely nothing about threading, and this is one practical consequence of that fact. So without any special treatment, none of our temporal relationships will be enforced. We might get lucky, or we might not. Guess which one is more likely.
The only “escape hatch” that C++ provides for controlling the order of execution is this thing called “volatile,” which our program does use on the “start” and “end” variables. So what does “volatile” do?
The C++ standard has little to say about volatile. It was originally intended for the very specific application of writing device drivers that communicate with hardware via memory-mapped I/O. To make that work, compilers must follow these rules:
- A read or write to a volatile variable must not be eliminated by the compiler.
- Reads and writes to volatile variables must not be reordered by the compiler, relative to one-another.
Note that this does not place any restrictions on non-volatile accesses, nor does it say anything about what the hardware is allowed to do. It is assumed that if you’re reading and writing memory-mapped I/O ports, then the hardware will know better than to reorder things.
Visual C++ has an augmented definition of volatile. It adds the following rules:
- Reads and writes to any global memory (even if not volatile) must never be moved before a volatile read.
- Reads and writes to any global memory must never be moved after a volatile write.
- These rules will be enforced at the hardware level as well.
Back to the quiz problem: this code attempts to enforce its required temporal relationships by tagging the “start” and “end” variables with the “volatile” keyword. Given the VC++ rules for volatile variables, this enforces the following:
S1->S4
S2->S4
S3->S4
S5->S6
S5->S7
S5->S8
In other words, nothing may move after the volatile write in S4, and nothing may move before the volatile read in S5.
Notice that we are missing some of our required temporal relationships. This is because the volatile write in S1 does not affect anything occurring after it in program order, nor does the volatile read in S8 affect anything coming before it.
(Careful readers may notice that there are two additional temporal relationships that must be enforced for this algorithm to work. As we go around each loop, the last statement must come before the first one (i.e., a previous iteration of S4 must occur before a subsequent iteration of S1). I didn’t know how to notate this, so I left it out. :) Luckily, these relationships are satisfied by the original program, since S1, S4, S5, and S8 are all volatile accesses, which cannot be reordered relative to each other.)
So this program is not correct. But do we get lucky? Let’s look at how VC++ compiles this code for x86:
void WriterThread(void*) {
int i = 0;
00401000 xor eax,eax
00401002 jmp WriterThread+10h (401010h)
00401004 lea esp,[esp]
0040100B jmp WriterThread+10h (401010h)
0040100D lea ecx,[ecx]
while (true) {
globals.start = i; //S1
00401010 mov dword ptr [globals (403370h)],eax
globals.a = i; //S2
00401015 mov dword ptr [globals+4 (403374h)],eax
globals.b = i; //S3
0040101A mov dword ptr [globals+8 (403378h)],eax
globals.end = i; //S4
0040101F mov dword ptr [globals+0Ch (40337Ch)],eax
i++;
00401024 add eax,1
}
00401027 jmp WriterThread+10h (401010h)
void ReaderThread(void*) {
00401030 push esi
00401031 mov esi,dword ptr [__imp__printf (4020A0h)]
00401037 jmp ReaderThread+10h (401040h)
00401039 lea esp,[esp]
while (true) {
int end = globals.end; //S5
00401040 mov edx,dword ptr [globals+0Ch (40337Ch)]
int a = globals.a; //S6
int b = globals.b; //S7
int start = globals.start; //S8
if (start == end)
00401046 cmp dword ptr [globals (403370h)],edx
0040104C mov eax,dword ptr [globals+4 (403374h)]
00401051 mov ecx,dword ptr [globals+8 (403378h)]
00401057 jne ReaderThread+10h (401040h)
if (a != b)
00401059 cmp eax,ecx
0040105B je ReaderThread+10h (401040h)
printf("oops! %d != %d\n", a, b);
0040105D push ecx
0040105E push eax
0040105F push offset string "oops! %d != %d\n" (4020F4h)
00401064 call esi
00401066 add esp,0Ch
}
00401069 jmp ReaderThread+10h (401040h)
Notice that we did get lucky in WriterThread. The compiler did not reorder any of our global variable accesses. Another compiler, or a new version of this one, might decide to compile this code differently.
ReaderThread is a different story. S5 precedes S6, S7, and S8, as required by the semantics of volatile reads, but S8 has been moved to before S6 and S7!
When I run this program on my machine, it does in fact display “oops.”
Now here’s a surprise: on my machine it doesn’t print “oops” until approximately 5 million iterations have passed. Even though the code emitted by the compiler is clearly not a correct implementation of this synchronization algorithm, it still has only a 0.00002% chance of failing. Imagine this was just a small piece of a much larger system; what are the chances that anyone would find this bug in testing?
So how do we fix this? I know you all think I’m going to say, “use a lock.” And I am. Later. For now, let’s figure out how to make the original algorithm work.
Recall our required temporal relationships:
S1->S2
S1->S3
S1->S4
S2->S4
S3->S4
S5->S6
S5->S7
S5->S8
S6->S8
S7->S8
I’ve highlighted the ones that were not satisfied by our use of volatile. We need a mechanism to prevent S2 and S3 from moving before S1, and S6 and S7 from moving past S8. We can do this with explicit “memory barriers,” which are instructions to the compiler and the hardware to restrict reorderings in a specific way. There is nothing in the C++ standard that provides for memory barriers, but luckily most compilers do step outside of the standard and provide some sort of support for these.
In VC++, we have a function called MemoryBarrier() which implements a “full memory barrier,” meaning that nothing will be moved in either direction across a call to MemoryBarrier(). In our case, if we want to prevent S2 and S3 from moving before S1, we can insert a memory barrier after S1:
void WriterThread(void*) {
int i = 0;
while (true) {
globals.start = i; //S1
MemoryBarrier();
globals.a = i; //S2
globals.b = i; //S3
globals.end = i; //S4
i++;
}
}
Similarly, we need a memory barrier before S8:
void ReaderThread(void*) {
while (true) {
int end = globals.end; //S5
int a = globals.a; //S6
int b = globals.b; //S7
MemoryBarrier();
int start = globals.start; //S8
if (start == end)
if (a != b)
printf("oops! %d != %d\n", a, b);
}
}
Now all of our required temporal relationships are satisfied, and the program no longer prints “oops.”
Now to say the least that was an awful lot of mental effort to arrive at a working implementation of a very simple algorithm. You certainly wouldn’t want to have to do this kind of analysis for every line of your code! Hopefully the end product is worth it; it had better be much faster than it would have been with a lock, or we just wasted a lot of time (not to mention that in real-life code, we’d probably get it wrong even with all this analysis).
Attached you will find two versions of the original problem, one using the original custom synchronization mechanism, and the other implemented with a basic spin lock. I’ve added some simple timing code so we can see how fast each one goes.
(Please, please, please don’t take the spin lock implementation from the attached code and use it in production code. It is meant as an illustration only).
On my machine, with maximum contention (meaning each thread is running full-speed-ahead on its own CPU), the lock-free implementation does about 0.3 successful iterations of the reader per millisecond. The spin lock version does about 3500 iterations/ms. So in this scenario, all our hard work bought us a 12,000-fold decrease in performance.
Of course, this is unfair - the algorithm is clearly designed to perform best with little contention - i.e., the writer only writes every so often, while the reader reads very frequently.
We can simulate minimum contention by simply not running the writer thread. In this scenario, the lock-free reader does 38,000 iterations/ms, while the spin lock implementation does 33,000 iterations/ms. So the lock-free implementation is just 6% faster.
So was all this work worth a best-case perf improvement of 6%, with a risk of such horrible worst-case performance? And the very real risk that we might have gotten it wrong? Well, it depends on the situation. :) What I can say for sure is that this sort of code should not be entered into lightly. Getting it right requires the sort of rigorous, mind-numbing analysis we had to do here, but typically on a larger scale. And it usually has very little, if any, benefit.
Comments
Anonymous
September 01, 2011
I am a rookie and I did not understand how you used these end, a, b, start in S5,S6,S7,S8 ? I mean you haven't declared them as variables, I don't know the use of struct, but class view, an object is required to use those variables. Off-topic: How will I know if you have replied to this comment? However, leaving my email address cse.tanmay@gmail.comAnonymous
September 02, 2011
Tanmay, immediately after the declaration of the struct, there is a declaration for a single global instance of that struct named "globals" (all lower case).Anonymous
September 02, 2011
The comment has been removed