Wednesday, November 2, 2005

C# Interlocked

----------
Note: a more recent and revised version of this post could be found here: http://www.mangcut.vn/blog/2015-02-14-atomicity-interlocked-memory-operation-optimizations-csharp.html
----------

Multithread programming, together with unit testing and exception handling, is among the tough and hard-to-do-cleanly things a software developer has to do on virtually every project. When starting learning about threads, a developer usually spend a lot of time to figure out how to create, start, and stop threads, how to make use of the thread pool, how to programming with the asynchronous delegates, etc. However, as I see it, the hardest thing to master is thread synchronization, that is, when and where you need to lock a code block to ensure accuracy and consistency. However, locking is reputed as expensive as it is often used ineffectively and create performance bottlenecks in the application. Effective locking primarily refers to locking at the correct level and correct granularity. Quite often, low level locking becomes useless as higher level code has its own business rules and may requires to lock a chunk of methods-something like "integration locking". Sometimes, two blocks of code are wrongly guarded by the same object which results in unnecessary contention. I am not a fan of lock-free tricks as it is too difficult to understand and might even be proven incorrect some time. However, there are some circumstances in which avoiding locking is just simple and elegant. I guess some of you might have seen code like following:

lock (this)
{
    a++; // or a--, a = b, you name it
}

We all learned that even a simple operation like increment might include several steps: load the variable into a register, increment it, save its value back from the register. So the lock in the code snippet above is necessary to prevent some other thread from intervening those steps (for this to work, the two threads must be guarded by the same lock). The only comment you might make about that snippet is that: avoid locking on this (or any public object if it is not designed for that purpose) since it might be accidentally be locked on by other code for a different purpose, which usually leads to a deadlock or at least execution inefficiency.

However, the .NET does provide a brilliant class called System.Threading.Interlocked. This class contains a handful of useful methods such as assignment and increment/decrement, each one is performed as an atomic operation. So the above code could be better rewritten as simple as: Interlocked.Increment(ref a). How nice!

"Atomic operation" is sometimes incorrectly interpreted as volatility. Let's take a look at section 5.5 of the C# Language Specification which said: 5.5 Atomicity of variable references Reads and writes of the following data types are atomic: bool, char, byte, sbyte, short, ushort, uint, int, float, and reference types. In addition, reads and writes of enum types with an underlying type in the previous list are also atomic. Reads and writes of other types, including long, ulong, double, and decimal, as well as user-defined types, are not guaranteed to be atomic. Aside from the library functions designed for that purpose, there is no guarantee of atomic read-modify-write, such as in the case of increment or decrement. Hmm... atomic again. Does that means in C#, the two following snippets are identical? Variables a, b, c are declared at class level:

int a, b, c;

Snippet 1: 

a = 1;
b = c;

Snippet 2: 

Interlocked.Exchange(ref a, 1);
b = c;

The answer is no. An atomic operation is indivisible. For example, an atomic write guarantees that no other thread can read while the write operation not yet finished and end up reading a partially updated value. However, for performance reason, the JIT or the hardware may decide to apply some optimizations such as reordering or even eliminating instructions as long as they do not break the logic from a single thread's perspective. For instance, in snippet 1, the processor might decide to fetch the value of c before writing 1 to a. That is OK if the program is single-threaded. However, what if a second thread updates the value of c in the meantime? The first thread then uses a stale value of c.

The Interlocked class is just more than atomicity. In fact, each one of its methods uses a memory barrier which prevents any instruction being reordered crossing the barrier. The Interlocked.Exchanged method call in snippet 2 prevents the reading of c from happening before 1 is written to a. Interlocked class is also safe on multiprocessor systems, where, because of caching issues, the sequence of instructions executed on one processor can appear to be different from other processors' perspective. In addition, the specification says C# does not guarantee functions such as increment and decrement to be atomic. The Interlocked class provides two super-handy methods for those purposes: Interlocked.Increment and Interlocked.Decrement. It should be noted that there are overloaded versions of these two methods that accept a long argument. This surprised me at first since it guarantees increment and decrement of a 64-bit number as an atomic operation. However, I soon realized that there is no magic under the scene since MSDN remark section of this method says that "The 64-bit versions of Increment and Decrement are truly atomic only on systems where a System.IntPtr is 64 bits long. On other systems, these methods are atomic with respect to each other, but not with respect to other means of accessing the data.”. Aha, that means on 32-bit systems, they can only be considered atomic only if increment and decrement are the two only operations you ever want to perform on the variable. That behavior could be simulated by letting the two methods acquire a lock on the same static internal object.

Besides the methods above, Interlocked class also provides a less-used method: CompareExchange. This method, as its name suggests, carries out a comparison first, and then exchanges the values if that test succeeded. Note that compare and exchange operations are performed as a single atomic operation. The example MSDN provides for this method is very interesting. This method reminds me of the DB optimistic concurrency problem which I had to deal with recently: you should only update a value if it is not been updated by someone else since the last time you queried it. Otherwise, that updated value will be replaced by your value. This method can also be used to implement the Singleton pattern:

Interlocked.CompareExchange(ref singleton,
           new SingletonClass(), null);

However, this approach requires a new instance of SingletonClass to be created even if singleton is not null.

So now if you ever want to lock a block of code which performs only a simple operation on a variable, let’s first see if you can get the same effect with Interlocked class!

9 comments:

Bojan Komazec said...

Related to last sentence (using Interlocked.CompareExchange Method): I think that new SingletonClass object won't be created every time (even if "singleton" is not null). It will be created only in case when value of "singleton" equals null. In MSDN pages related to entire family of this method, "Remarks" section says: "If comparand and location1 are equal, then value is stored in the destination. Otherwise, no operation is performed." I hope that "not operation is performed" assumes and no creating a new instance of singleton class (which would be totally unnecessary).

At the end of this article http://msdn2.microsoft.com/en-us/library/f857xew0(VS.71).aspx there's code equivalent to Interlocked.CompareExchange Method.

Unknown said...

I think "no operation is performed" means value is not stored in the destination. A new instance is always created to pass to the CompareExchange Method, no matter what CompareExchange does.

David Turner said...

Arguments to method invocations are always evaluated before the method is invoked. So the new singleton will always be created. Late-bound evaluation of arguments is a whole topic in itself.

We're also discussing this subject over at http://www.janus-net.de/2008/01/10/double-checked-locking-in-c/.

Anonymous said...

How about using a delegate to create the Singleton instance? you could have the delegate executed only if the singleton reference is null, to ensure it is only instantiated once.

Unknown said...

Hi,

I am trying to get better understanding of threading and synchronization constructs. So I decided to implement some on the synchronization constructs myself. Can you review my implementations and validate if they are correct?

Ignore the spin-wait logic, I know it's not optimal. As I said, the purpose if to understand the construct implementation.

public sealed class MyManualRestEvent
{
private Boolean isGateOpen;

public MyManualRestEvent(Boolean initialState)
{
this.isGateOpen = initialState;
}

public void ReSet()
{
//It's not thread-safe
this.isGateOpen = false;
}

public void Set()
{
//It's not thread-safe
this.isGateOpen = true;
}

public void WaitOne()
{
//It's not thread-safe
while (!this.isGateOpen) Thread.Sleep(1000); // "Spin-Sleeping!"
}
}

public sealed class ThreadSafeManualResetEvent
{
// It can possibly have only two false, 0 and 1.
// 0 - Gate is closed. Thread can not enter critical section.
// 1.- Gate is open. Waiting threads can enter the critical section.
private Int32 isGateOpen;

public ThreadSafeManualResetEvent(Boolean initialState)
{
Interlocked.Exchange(ref this.isGateOpen, initialState ? 1 : 0);
}

public void ReSet()
{
Interlocked.Exchange(ref this.isGateOpen, 0);
}

public void Set()
{
Interlocked.Exchange(ref this.isGateOpen, 1);
}

public void WaitOne()
{
while (Interlocked.CompareExchange(ref this.isGateOpen, this.isGateOpen, this.isGateOpen) == 0)
Thread.Sleep(1000); // "Spin-Sleeping!"
}
}

Regards,
Jehanzeb

Unknown said...

Hi Jehanzeb,

Because all accesses to isGateOpen are already atomic, in order to make MyManualResetEvent thread-safe regardless of memory model, simply add "volatile" keyword to the declaration of MyManualResetEvent's isGateOpen.

private volatile Boolean isGateOpen;

The "volatile" keyword prevents optimizations such as reordering or caching, and it is optimal in this situation.

For the purpose of understanding the construct implementation, your second class, ThreadSafeManualResetEvent, is correct.
However, I suggest to change WaitOne like this:

public void WaitOne()
{
int gateState = 0;
while (Interlocked.Exchanged(ref gateState, this.isGateOpen) == 0)
Thread.Sleep(1000); // "Spin-Sleeping!"
}

Unknown said...

Thanks Truong for your reply.

sergeyt said...

thanks for a lot of good letters

Anonymous said...

Thanks for such an amazing article