TimL on C#.NET: Interlocked Atomic Operations

Thursday, January 10, 2008

Interlocked Atomic Operations

Threads often scare novice programmers. But any experienced programmer will agree that nearly all "real" programs are threaded. If your program is constantly blocked waiting for something to finish, it is practically useless. As soon as a user sees a UI lockup for more than a few seconds, that user will undoubtably start clicking the mouse everywhere, trying to kill things in Task Manager (if they even know how to do that), or even yanking the power cord out of the wall while the computer is still on (thus corrupting the registry and possibly damaging the hard disk).

If your application is threaded, you must synchronize access to data that may potentially be accessed "simultaneously" by different threads. On a 32-bit system, even something as trivial as reading the value of a 64-bit long is not atomic because it takes two processor cycles, and may therefore be interrupted by a thread context-switch. Without some kind of synchronization, there could be a thread context-switch between reading the first 4-bytes and last 4-bytes, and another thread could change the value; the resulting number "read" by the first thread would be neither the old number or new number, but instead a composite of both.

Initial value is 00112233aabbccdd

Thread 1 reads upper four bytes: 00112233

Context switch to Thread 2

Thread 2 writes eight new bytes: 99887766ffeeddcc

Context switch back to Thread 1

Thread 1 reads lower four bytes: ffeeddcc

Thread 1 thinks the value is 00112233ffeeddcc

The Windows operating system povides the basic synchronization mechanisms in the form of semaphores, mutexes, critical sections, events (different from .NET events) and interlocked operations. .NET wraps all of these in one form or another. C#.NET programmers are probably most familiar with the lock(){...} which internally uses a System.Threading.Monitor, which is really not much more than a critical section. In my opinion, however, the simple interlocked atomic operations are sorely underused; I sometimes wonder if programmers even know they exist.

An operation is said to be atomic if the operating system cannot context-switch to another thread before the operation has completed. As stated earlier, even something like reading a 64-bit number on a 32-bit machine is not inherently atomic. Likewise, the x++, ++x, x--, --x we all know and love are also not atomic. .NET programmers should be happy to hear, however, that .NET does provide some primitive interlocked atomic operations in the System.Threading.Interlocked class. The following method calls are guaranteed to do atomic operations; Windows will not context-switch to another thread before the operations performed by these methods have completed.


// Interlocked.Read(ref a)
// Read and returns 64-bit value
long a = 100;
long z = Interlocked.Read(ref a); // Results: a == 100; z == 100

// Interlocked.Exchange(ref a, b)
// Sets a = b; Returns original value of a
int a = 100;
int b = 200;
int z = Interlocked.Exchange(ref a, b); // Results: a == 200; z == 100

// Interlocked.CompareExchange(ref a, b, c)
// Replace a with b if a == c; Returns original value of a
int a = 100;
int b = 200;
int c1 = 300;
int c2 = 100;
int z1 = Interlocked.CompareExchange(ref a, b, c1); // Results: a == 100; z == 100
int z2 = Interlocked.CompareExchange(ref a, b, c2); // Results: a == 200; z == 100

// Interlocked.Increment(ref a)
// Increments a; Returns new value of a; Wraps w/o exception
int a = 100;
int z = Interlocked.Increment(ref a); // Results: a = 101; z = 101;

// Interlocked.Decrement(ref a)
// Decrements a; Returns new value of a; Wraps w/o exception
int a = 100;
int z = Interlocked.Decrement(ref a); // Results: a = 99; z = 99;

// Interlocked.Add(ref a, b)
// Replace a with a + b; Returns new value of a; Wraps w/o exception
int a = 100;
int b = 200;
System.Threading.Interlocked.Add(ref a, b); // Results: a == 300; z = 300

From the comments in the code sample code above, it should be apparent that you need to keep in mind whether the first parameter does or does not change, and whether the new value or original value is returned by the function. This can be summarized in a few basic rules.

If the interlocked operation causes something to be updated, the first parameter will always have that new value after the operation has completed (Exchange, CompareExchange, Increment, Decrement and Add)

If the interlocked operation does math, the method always returns the new value of the first parameter(Increment, Decrement and Add)

If the interlocked operation does not do math, the method always returns the original value of the first parameter (Read, Exchange and CompareExchange)

Also, it should be noted that interlocked math operations do not throw exceptions! on underflows or overflows. Rather, they wrap instead. Because the operations are atomic, they need to be very fast and light-weight. They get in, do their thing, and get out. Throwing exceptions just does not fit that paradigm.

The interlocked operations are simple and useful. But, just because these operations are atomic does not mean you can't still run into problems if you're not careful. You really only get "protection" against other accesses to the same variable by interlocked functions. For example, you could still have problems if you attempt to protect access with a lock in one place but use an Interlocked.Increment in another.


// Variable accessible by both threads
int a = 100;

// Running on Thread 1
object obj = new object();
lock(obj)
{
     a++;
}

// Running on Thread 2
Interlocked.Increment(ref a);

In the example above, the interlock is atomic but the a++ is not. It is quite possible that the following scenario could occur.