## Monday, November 10, 2014

### Relaxed atomics, out-of-thin-air results, and ConcurrentLinkedQueueRelaxed

On today's post we have a quiz on Relaxed Atomics.

Before you go any further, I recommend reading this paper by Hans Boehm and Brian Demsky entitled "Outlawing Ghosts: Avoiding Out-of-Thin-Air Results", if you haven't done so already. Without reading this paper, you may be missing some of the subtleties of relaxed atomics.

Ok, let's start.

Suppose we have three slightly different programs named Program A, Program B, and Program C, each with two threads. The code that each thread executes for each program is described below, and I'll use Java notation, but this is also true for C++1x, C11, D, and for Scala (not for Go, because it doesn't have relaxed atomics from what I could tell):

#### Program A

volatile int x = 0;
volatile int y = 0;

if (x == 1) y = 1;

if (y == 1) x = 1;

#### Program B

int x = 0;
int y = 0;

if (x == 1) y = 1;

if (y == 1) x = 1;

#### Program C

int x = 0;
int y = 0;

if (x == 42) y = 1;

if (y == 1) x = 1;

Question 1:
What are the possible outcomes of each of these programs?

Question 2:
Which (if any) of these three programs generate sequentially consistent results ?

I've taken the liberty of emphasizing the differences between the three programs in bold, so as to make it easier to analyze the code.
Program A is the only one where the variables x and y are sequentially consistent atomics. Programs B and C use relaxed atomics for all their operations (in the JVM, all loads and stores on an int are guaranteed atomicity). Program C compares x with 42 instead of comparing to 1.

If these programs seems somewhat familiar it is because Program B is one of the examples on the paper (see section 2) indicated as recommended reading at the beginning of this post.

So have you thought about it for a while?
What are the possible outcomes for each one of these three programs?
Scroll down to look at the solutions.

a little bit further....

For Program A, the only possible outcome is {x=0, y=0}.
There is no other possible outcome, and I hope this is obvious. If it is not, then I recommend watching Herb Sutter's presentation on atomics because I don't even know how to explain it. But basically, no re-ordering is possible due to implicit acquire barriers on the loads, and release barriers on the stores.
As for the consistency model, Program A provides at least sequential consistency because, well, it's constant/immutable, in the sense that there is only on possible state and it never changes.

For Program B, there are two possible outcomes {x=0, y=0} or {x=1,y=1}. To understand why the {1,1} state is possible, the best is to read the paper by Hans Boehm.
There is no sequentially consistent history for Program B that can result in {x=1,y=1}, so Program B is not sequentially consistent.

For Program C, there is only one possible outcome which is {x=0, y=0}, mainly because we check against a value that x can never take (a value of 42). Unlike for Program B, in Program C there is no way branch prediction can predict 42 and then it actually becomes 42 because there is no code path for which x is set to 42.
Program C has only one state and it's constant/immutable, so yes, it is sequentially consistent (if it even makes sense to say so).