Atomic Operations

Wednesday, May 17, 2006

Greek philosophers Leucippos and Democritus were among the first to postulate that all matter is composed of indivisible units they called atomos. Thus arose atomistic philosophy and the concept of an atom. (Note that the Hindu Vaisesika Sutra appears to pre-date the Greek thinking by 100 years or more). Curious humans continued to tinker over the next 2300 years until they got inside the atom. Nuclear technology is responsible for devices as useful as the x-ray machine, and devices as destructive as the television and atom bomb.

Somewhere along the line, computer science adopted the term “atomic operation” to describe an instruction that is indivisible and uninterruptible by other threads of execution. It appears the now 40-year-old IBM System/360 was the first architecture to include an atomic operation (TS – test and set).

Let’s look at an atomic operation from a different perspective: other threads and CPUs cannot observe an atomic operation “in progress”. If thread A is writing a 32-bit value to memory as an atomic operation, thread B will never be able to read the memory location and see only the first 16 of 32 bits written out. Thread B can only read the value that exists before the atomic operation began, or the value that exists sometime after the atomic operation completes, but can never read the value only partially written.

Why is important to know what operations are atomic? If you ever come across code like the following, you’ll be able to know there is a problem.

static int _counter = 0;
static void IncrementCounter()
{
   _counter++;
}

If multiple threads call IncrementCounter concurrently, we might not get an accurate counter reading. The ++ operator isn't atomic - it needs to read the value, then write back an updated value. Another thread can step in between those two operations and we will miss a hit if both threads read the same value or overwrite each other's results.

What is an atomic operation in the CLR? Partition I of the CLI specification states that:

"A conforming CLI shall guarantee that read and write access to properly aligned memory locations no larger than the native word size (the size of type native int) is atomic…”.

 Section 12.5 of the C# specification has the specifics for semicolon fans:

“Reads and writes of the following data types shall be atomic: bool, char, byte, sbyte, short, ushort, uint, int, float, and reference types.” Also: “…there is no guarantee of atomic read-modify-write, such as in the case of increment or decrement.”.

To make the increment operation atomic, use Interlocked.Increment, or a lock.


Comments
Milan Negovan Sunday, May 21, 2006
Why not mark it as volatile? (Section 17.4.3 "Volatile fields")
scott Sunday, May 21, 2006
Volatile wouldn't prevent two threads coming in to increment the counter, reading the same values, and writing out the same output value (missing a hit count). Volatile would, (per my understanding), just prevent reording, like someone reading an old hitcounter value even after one thread published a new value.
gravatar kim Sunday, April 18, 2010
Scott is correct.

From Essential C# 2.0:

Declaring Fields as volatile
On occasion, the compiler may optimize code in such a way that the instructions don't occur in the exact order they are coded, or some instructions are optimized out. Such optimizations are generally innocuous when code executes on one thread. However, with multiple threads, such optimizations may have unintended consequences because the optimizations may change the order of execution of a field's read or write operations relative to an alternate thread's access to the same field.

One way to stabilize this is to declare fields using the volatile keyword. This keyword forces all reads and writes to the volatile field to occur at the exact location the code identifies instead of at some other location that the optimization produces. The volatile modifier identifies that the field is susceptible to modification by the hardware, operating system, or another thread. As such, the data is "volatile," and the keyword instructs the compilers and runtime to handle it more exactly.


Also in the statement above:
"atomic - it needs to read the value, then write back an updated value."
There is actually more than 2 opperations to the increment/decrement operation...

1) The processor reads the data in _Count.

2) The processor calculates the new value.

3) _Count is assigned a new value (even this may not be atomic).
Comments are now closed.
by K. Scott Allen K.Scott Allen
My Pluralsight Courses
The Podcast!