Saturday, May 15, 2010

Difference between Atomic and Volatile?

There seems to be a tendency for people to confuse an atomic action with a volatile memory access. This is quite natural, since they exhibit similar properties and makes it hard for people to distinguish between the two.

So what is the common property between an atomic action and a volatile memory? They both exhibit the property of total ordering. Let's assume for \forall a, b, c \in A where A is the set of possible actions a program can execute, and a \rightarrow b denotes that an action a precedes action b, then the property of total order means:

a \rightarrow b  \wedge b \rightarrow a \Rightarrow a = b

a \rightarrow b , b  \rightarrow c \Rightarrow a \rightarrow c

a \rightarrow b \vee b  \rightarrow a

Literally, the set of rules mean (1) that for any action a that precedes b and any action b that precedes a, then the action a must necessarily be the same action as b. (2) If a precedes b, and b precedes c, then a must precede c. (3) a must precede b or b must precede a. These are just some mathematical (or convoluted) formalisms of saying any action is guaranteed to be in sequential order.

But that's where the similarity ends.

An atomic action is literally what it means: an action that is indivisible. Volatile memory only provides a guarantee of sequential order, but offers no guarantee that an interleaving of actions cannot occur. For an illustration, lets take a look at the following code:

a = 0;
a++;

Assume that 'a' is a volatile variable. From the code, we naturally think that the increment operator (++) will atomically increment the value of 'a' to 1, but this assumption is slightly faulty:

[a] = 0;
r0 = [a];
r0 = r0 + 1;
[a] = r0;

The square brackets between [a] denotes a value gotten from memory, while r0 represents a register in which the addition operation actually occurs. An increment operation is actually a composite action, composed of a read, then a write action. (By the way, it is implied that register actions are atomic, despite being a composite action. This is because an operation within a register cannot be directly observed).

So increment is a composite action, compared to being an atomic action, what's the harm? Lets go through the same example, but with 2 concurrent processors executing simultaneously:

CPU1
CPU2
a++;
a++;

Lets assume that a is initially 0 to start. Given that iff the actions from CPU1 and CPU2 are both volatile and atomic, then the only possible transition value that can be seen after execution can only be 2.

However, if the actions from CPU1 and CPU2 are only volatile, then the actions can translate to this:

CPU1
CPU2
r0 = a;
r1 = a;
r0 = r0 + 1;
r1= r1 + 1
a = r0;
a = r1

For all the possible decompositions of C into uniprocessor-MT interleavings, one can see that it is possible that both registers r0 and r1 both read a as 0 simultaneously which causes the resultant possible values to be either 1 or 2. Clearly seeing 1 is wrong, since if the operation is atomic, then 1 cannot be a legal value at the end of the execution.

Conversely, a volatile variable can be deemed atomic. Consider the example below:

CPU1
CPU2
a=1;
a=2;

In this case, the only possible set of terminal values are 1 or 2, which is exactly the same as you would get for an atomic action. Therefore, a volatile memory access is atomic iff you perform only a read or write action, which are atomic in nature. But a volatile variable is no guarantee of atomicity if a composite action is executed.

Hence the label atomic actions is a slight misnomer, because it doesn't imply that the action is atomic, but rather it means that it guarantees a composite action is executed as a single atomic action. A well known example of such a composite action is the Compare-and-Swap instruction.

For simplicity, just remember that atomicity is not a property of memory, but a property its actions, to which a volatile memory access may or may not uphold.

3 comments:

Markus Dan said...

Hi Vincent...
Wow... interesting post. Maybe one day I´ll understand it... ;-)
Good work, keep on doing.

Greetings from Vienna, Markus

Rocky Liu said...

Thanks. Very helpful. Though the pictures cannot be displayed but can be "decoded" from the visible parts :)

Anonymous said...

Thanks man .. this is really interesting article and removed my confusion towards volatile variables. Keep writing such articles and make world a better place by reducing same mistake for other programmers.

Post a Comment