Lock using atomic operations

Question

Yes, I'm aware of that the following question could be answered with "Use the lock keyword instead" or something similar. But since this is just for "fun", I don't care about those.

I've made a simple lock using atomic operations:

public class LowLock 
{
    volatile int locked = 0;

    public void Enter(Action action)
    {
        var s = new SpinWait();

        while (true)
        {
            var inLock = locked; // release-fence (read)

            // If CompareExchange equals 1, we won the race.
            if (Interlocked.CompareExchange(ref locked, 1, inLock) == 1)
            {
                action();
                locked = 0; // acquire fence (write)
                break; // exit the while loop
            }
            else s.SpinOnce(); // lost the race. Spin and try again.
        } 
    }
}

I'm using the lock above in a simple for loop, that adds a string to a normal List<string>, with the purpose of making the add method thread-safe, when wrapped inside the Enter method from a LowLock.

The code looks like:

static void Main(string[] args)
{
    var numbers = new List<int>();

    var sw = Stopwatch.StartNew();
    var cd = new CountdownEvent(10000);

    for (int i = 0; i < 10000; i++)
    {
        ThreadPool.QueueUserWorkItem(o =>
        {
            low.Enter(() => numbers.Add(i));
            cd.Signal();
        });
    }

    cd.Wait();
    sw.Stop();

    Console.WriteLine("Time = {0} | results = {1}", sw.ElapsedMilliseconds, numbers.Count);

    Console.ReadKey();
}

Now the tricky part is that when the main thread hits the Console.WriteLine that prints time and number of elements in the list, the number of elements should be equal to the count given to the CountdownEvent (10000) - It works most of the time, but sometimes there's only 9983 elements in the list, other times 9993. What am I overlooking?

Answer 1

I suggest you take a look at the SpinLock structure as it appears to do exactly what you want.

---

That said, this all looks really dicey, but I'll have a stab at it.

You appear to be trying to use 0 to mean 'unlocked' and 1 to mean 'locked'.

In which case the line:

if (Interlocked.CompareExchange(ref locked, 1, inLock) == 1)

isn't correct at all. It's just replacing the locked variable with the value of 1 (locked) if its current value is the same as the last time you read it via inLock = locked (and acquiring the lock if so). Worse, it is entering the mutual exclusion section if the original value was 1 (locked), which is the exact opposite of what you want to be doing.

You should actually be atomically checking that the lock has not been taken (original value == 0) and take it if you can (new value == 1), by using 0 (unlocked) as both the comparand argument as well as the value to test the return value against:

if (Interlocked.CompareExchange(ref locked, 1, 0) == 0)

Now even if you fixed this, we also need to be certain that the List<T>.Add method will 'see' an up to date internal-state of the list to perform the append correctly. I think Interlocked.CompareExchange uses a full memory barrier, which should create this pleasant side-effect, but this does seem a little dangerous to rely on (I've never seen this documented anywhere).

I strongly recommend staying away from such low-lock patterns except in the most trivial (and obviously correct) of scenarios unless you are a genuine expert in low-lock programming. We mere mortals will get it wrong.

EDIT: Updated the compare value to 0.

Answer 2

Interlocked.CompareExchange returns the original value of the variable, so you want something like this:

public class LowLock
{
    int locked = 0;

    public void Enter( Action action )
    {
        var s = new SpinWait();

        while ( true )
        {
            // If CompareExchange equals 0, we won the race.
            if ( Interlocked.CompareExchange( ref locked, 1, 0 ) == 0 )
            {
                action();
                Interlocked.Exchange( ref locked, 0 );
                break; // exit the while loop
            }

            s.SpinOnce(); // lost the race. Spin and try again.
        }
    }
}

I've removed the volatile and used a full fence to reset the flag, because volatile is hard