In a multi-threaded application, synchronization is key to protect data integrity. There are numerous ways to accomplish data synchronization in .NET and C#, such as the commonly used System.Threading.Monitor .NET Framework class and corresponding C# lock statement. But, when it comes to super-fast synchronization, nothing beats the interlocked operations for a few simple operations:

• Math Operations
  • Add 1 to a value (Increment)
  • Subtract 1 from a value (Decrement)
  • Add Two Values (Add)
• Get / Set Operations
  • Get a value (Read)
  • Get the current value and set a new value (Exchange)
  • Get the current value and set a new value if-and-only if the current value is a specific value (CompareExchange)

This article first looks at why atomic operations are needed, and then goes into the various interlocked operations accessible via the System.Threading.Interlocked class.

Why Interloced Operations Are Needed

Simply put, an interlocked operation is an operation that executes without interruption. An interlocked operation generally consists of a sequence of two or more steps that affect state information or rely on consistency in state information and need to be executed in order, without interruption, to ensure the integrity of that state information. If the execution sequence of the operation is interrupted, it is possible that the state information can be adversely affected, and interlocked operations ensure that that does not happen.

The Need for Interlocked Math Operations

Experienced programmers generally already know this fact, but novice programmers are often surprised to find out that something as simple as x++ is not atomic! For example, the simple x++ executes the following sequence of steps, but does not prevent interruption between the steps or manipulation of the value from another thread:

• Read the current value of the variable x
• Calculate the new value to be 1 + the current value
• Write the new value back into the variable x

Since x++ is non-atomic, if code running on another thread also tries to increment the variable x at the same time via x++, the variable x could end up with the wrong value as is indicated by one possible outcome execution outcome below:

Thus, as you can see from the example above, even though x++ was called twice, the final value residing in x is incorrect because it is 101 instead of 102.

But, if the ++ operator was atomic (which it is not!), then it would be guaranteed that calling x++ concurrently from two different threads would result in the correct value of 102 because the read, calculate, write sequences could not be interrupted on either thread:

From this example of x++, it should be pretty obvious that similar problems would exist for x-- or x + y.

Solutions to these problems are provided by

• Interlocked.Increment()
• Interlocked.Decrement()
• Interlocked.Add()

The Need for Interlocked Get and Set Operations

In addition to needing interlocked math operations as was mentioned above, there is also a need for interlocked get and set methods.

Get on 32-Bit vs 64-Bit Machines

In computer architecture, a "word" is always one "native width" worth of bits. On an 8-bit processor a word is 8-bits, on a 16-bit processor a word is 16-bits, on a 32-bit processor a word is 32-bits, and so on. To eliminate confusion for people that may be accustom to a word being exactly 2-bytes (16-bits) I will used the terminology "word8", "word16", "word32", "word64", etc. when referring to a word of a specific size, or "wordN" to refer to a word that is the native or natural size based on the processor's architecture.

.NET can run on 32-bit and 64-bit machines. And, in .NET, each value is at least one wordN wide. For example, even a bool value -- which technically needs only 1-bit in which to store its entire state information -- is stored in a word32 on a 32-bit machine or in a word64 on a 64-bit machine. In other words, .NET does not "pack" the data to optimize memory usage.

The .NET Framework supports a wide variety of numeric types. For example, consider what it means to have a System.Int32 ( int in C#) and System.Int64 (long in C#) on both 32-bit and 64-bit machines.

From that table, note that on a 64-bit machine a long is stored in only one wordN (where wordN = word64), but on a 32-bit machine a long is stored in two wordsN (where wordN = word32). This creates an interesting problem: In one CPU clock cycle, the CPU can typically only move one wordN from memory to CPU register, or from a CPU register to memory. Therefore, when a long is used on a 32-bit machine where it takes 2 wordsN to hold all 64-bits, it also takes 2 CPU clock cycles to move the value.

Moving one wordN from memory to register is atomic -- nothing is going to interrupt that. But, moving two wordsN from memory to register is not atomic! That means a thread context switch could occur between moving the lower 32-bits and upper 32-bits, which also means that another thread could change the value in between those two steps in that operation sequence. In multi-processor and muti-core environmets, it might not even take a thread context switch:

Doh! That table above shows that Thread 1 just got the lower 32-bits from the original value of x but the upper 32-bits from the new value of x that was just set by Thread 2. In other words, it did not get either the old value or the new value, but instead some hybrid value.

Thus, as you can see, even for value-types such as a long it becomes necessary to synchronize access when reading and writing across thread boundaries.

A solution to this problem is provided by

• Interlocked.Read()

Set a New Value, or Swap Two Values

For a similar 32-bit / 64-bit reason as was discussed in the previous section on getting a value, it is also necessary to synchronize when setting a 64-bit value on a 32-bit machine.

As you can set from that example, if the set is not atomic the final value in x could be the lower 32-bits set from Thread 2 but the upper 32-bits set from Thread 1. In that case, the final value is neither the value set by Thread 1 nor the value set but Thread 2, and instead a hybrid of the two.

In addition to setting a 64-bit value on a 32-bit processor, there is also a reason to need to synchronize a set even if the value is a 32-bit value on a 32-bit process where the entire value gets moved in a single CPU clock cycle: without synchronization, it would not be possible to set a new value and return the existing value with 100% certainty that the value that is returned is actually the value that was replaced:

• Get existing value and store it as original value
• Set new value
• Return original value

As an example, assume variable x is a bool and the code needs to turn the flag on and know that it is indeed the code that caused the flag to turn on. Without some kind of synchronization, the following situation could occur if two different threads try to set the flag at the same time.

bool y = x;
x = true;
return y;

As you can see from that example, both Thread 1 and Thread 2 now think they were the code that caused the flag to turn on because they were each told that the original value was false, and they each also know they just set the flag to true.

A solution to this problem is provided by

• Interlocked.Exchange()

Set New Value If Existing Value Is Something

It is often necessary to change the existing value to a new value if-and-only-if that exiting value is a specific value. Logically, that looks something like this:

// If x is 100, then set it to 200
if (x == 100)
{
   x = 200;
}

By now, if you're still reading this post, it's probably pretty obvious that threading can cause unintended side effects with that code. For example, it's easy to imagine that x was indeed 100 at the time it was checked in the conditional, but that another thread could have already changed x to a different value by the time x is set to 200.

Therefore, if x is something that can be changed by multiple threads, synchronization would be required.

A solution to this problem is provided by

• Interlocked.CompareExchange()

System.Threading.Interlocked Class

Fortunately, the .NET Framework provides high-speed, interlocked operations for the various situations described above as part of the System.Thread.Interlocked class. These methods follow a common set of rules:

• The first parameter of an Interlocked method is always the ref parameter that is the variable holding the value that is to be read and/or changed. Since it is a ref parameter, it must be a variable or class field, and cannot be a property.
• To make the implementation as fast as possible, the Interlocked methods do not throw exceptions.
• The Interlocked math operations (Increment(), Decrement(), Add()) return the new value (i.e. value after the math operation has completed).
• The Interlocked get and set operations (Read(), Exchange(), CompareExchange()) return the original value (i.e. before the new value was set, if applicable).
• The Interlocked methods are synchronized with each other, but are not synchronized with other .NET operators or synchronization classes. For example doing an Interlocked.Increment() on Thread 1 at the same time as a ++ on the same variable from Thread 2 is not safe. Likewise, doing an Interlocked.Exchange() to set a value from outside of a Monitor lock while another thread is using a = assignment operator from inside a Monitor lock is not safe.

Interlocked Math Operations

The three interlocked math methods have overloads for Int32 and Int64. They execute the math operation, and return the new value without throwing any exceptions. In order to increase execution speed, the Interlocked math operations do not check for overflows and underflows.

Two's-Complement Integer Overflows and Underflows

The Interlocked class is CLS (Common Language Specification) compliant, so it supports signed integer values but does not support unsigned integer values. Since the Interlocked math operations do not detect overflows and underflows, it is useful to understand how integer values are stored in two's-complement format so that you know what to expect when values are incremented or decremented, or when two signed integers are added.

The table below serves as a reminder about how signed integer values are stored in two's-complement format for both Int32 and Int64 types. The table shows the values form all bits off, to all bits on.

In two's-complement format, to convert a positive value to a negative value, or vice-versa, you simply

Invert and add one

In that phrase, "inverting" simply means flipping the state of all the bits, which is also known as taken the "one's-complement". The two tables below show that the technique works for both positive and negative numbers.

Knowing that the values simply wrap-around instead of checking for overflow and underflow, and referring to the tables above, you can see that the following will happen.

Additionally, when adding two signed integers...

• If you add a positive number and a negative number together, the answer cannot result in an overflow or underflow
• If you add two positive numbers together, the answer might result in an overflow
• If you add two negative number together, the answer might result in an underflow

Interlocked.Increment() and Interlocked.Decrement()

The Interlocked.Increment() and Interlocked.Decrement() are complementary operations. As their names imply, they simply increment of decrement value. Both have overloads for Int32 and Int64:

// Add 1 to the current value of an Int32, returning the new value
// Wrap around instead of throwing an OverflowException
public static int Increment(
    ref int value
)

// Add 1 to the current value of an Int64, returning the new value
// Wrap around instead of throwing an OverflowException
public static long Increment(
    ref long value
)

// Subtract 1 from the current value of an Int32, returning the new value
// Wrap around instead of throwing an UnderflowException
public static int Decrement(
    ref int value
)

// Subtract 1 from the current value of an Int64, returning the new value
// Wrap around instead of throwing an UnderflowException
public static long Decrement(
    ref long value
)

There are numerous reasons why someone might want to increment an integer. One of the common reasons ins reference counting.

Interlocked.Add()

The Interlocked.Add() function adds two Int32 or two Int64 numbers, store it in the specified variable, and return the resulting value. Each of the numbers may be positive or negative, and the the resulting is wrapped around instead of throwing an OverflowException or UnderflowException.

// Add two Int32 numbers (addend1 and addend2)
// Store the calculated result in value
// Return the calculated result
// Wrap around instead of throwing OverflowException or UnderflowException
public static int Add(
    ref int value,
    int addend1,
    int addedn2)

// Add two Int64 numbers (addend1 and addend2)
// Store the calculated result in value
// Return the calculated result
// Wrap around instead of throwing OverflowException or UnderflowException
public static Int64 Add(
    ref long value,
    long addend1,
    long addedn2)

Interlocked Get and Set Operations

The need for the interlocked read, exchange, and compare-exchange functionality was described a few sections above. This section describes the methods that .NET provides for accomplishing these tasks.

Interlocked.Read()

.NET runs on 32-bit and 64-bit machines. Neither 32-bit nor 64-bit machines would have an issue reading a 32-bit number in one CPU cycle. But, a 32-bit machine cannot read a 64-bit number in one CPU cycle. Therefore, there is no reason for a 32-bit interlocked read operation,but is a need for a 64-bit interlocked read operation.

You can use the same method below from both 32-bit machines and 64-bit machines, and the compiler is smart enough to know that it needs to do something for 32-bit machines, but does not need to do anything for 64-bit machines.

// Read 64-bit value in way that is "safe" from corruption by other Interlocked operations
// This provides no protection against non-Interlocked operations, such as x++
public static long Read(
    ref long value)

Interlocked.Exchange()

The Interlocked.Exchange() method writes a new value, returning the original value. There are a variety of different overloads of this for 32-bit and 64-bit data types, including:

• double (System.Double)
• int (System.Int32)
• long (System.Int64)
• IntPtr (System.IntPtr)
• object (System.Object)
• float
• double
• T

The Interlocked.Exchange always sets the new value, and always returns the original value.

Remember the simple example of turning a flag on and trying to determine which code actually turned it on?

bool y = x;
x = true;
return y;

That can easily be done with an Interlocked.Exchange:

var y = Interlocked.Exchange(ref  x, true);
return y;

Interlocked.CompareExchange()

This method is sets a new value if-and-only-if the current value is the specified value. As one would expect, it has the same kinds of overloads as the Interlocked.Excahnge disussed above.

Remember the simple example of trying to set the value to 200 if-and-only-if the current value is 100?

// If x is 100, then set it to 200
if (x == 100)
{
   x = 200;
}

That can easily be accomplished with Interlocked.CompareExchange:

// Set x to 200 if and only if the original value is 100, and return the original value
if (100 == Interlocked.CompareExchange(ref x, 200, 100))
{
    // If you make it here, the value of x was 100 and has just changed to 200
}