Lecture Notes for Concurrent Programming

5 August 2003 - .NET Memory Consistency


The obvious thing to do is use Exchange() to implement the classic spin lock entry protocol. Assuming a global boolean lock initialized to false, the entry protocol is

bool locked = true
while Exchange(locked, lock)
  yield()

and the exit protocol is

lock = false

This is way overkill though, because we only want one-shot synchronization: the first thread gets to initialize and the rest can skip it.

We can implement one-shot initialization using Increment() (or, analogously, Decrement()) and a global integer lock initialized to n: the thread that adds 1 to lock and gets n + 1 wins:

if (Increment(lock) == initialLockValue + 1) 
  // initialize

On a 64-bit machine we needn't worry about overflow, but if we wanted to, we could add an else branch that calls Decrement() (but remember, atomic operations are expensive). Otherwise, no exit protocol is needed, because there's only ever going to be one entering thread.

One atomic operation left and we still have an assumption we can make. If BigExpensiveObject() is idempotent and side-effect free, then it creates the same instance every time it's called. Our path to using CompareExchange() should be clear:

CompareExchange(beo, null, new BigExpensiveObject)

This is a dumb solution because it forces every thread to spend time creating a big, expensive object, which all but the first will throw away, but at least we've used all the atomic operators available.


This page last modified on 4 August 2003.