Why am I getting this result with my attempt to implement a basic spin-lock in C#?

Question

Attempt:

public interface ISemaphore
{
    void Aquire();

    void Release();
}

public class SpinlockSemaphore : ISemaphore
{
    private int _cur;
    private const int B = 1;
    private const int A = 0;

    public SpinlockSemaphore()
    {
        this._cur = A;
    }

    public void Aquire()
    {
        // Locally named variables for clarity. Could obviously be
        // condensed to something like:
        // while (Interlocked.CompareExchange(ref this._cur, B, A) != A);

        var flipped = false;
        do
        {
            // Flip to B only if it is A
            var prev = Interlocked.CompareExchange(ref this._cur, B, A);
            if (prev == A)
            {
                // If here, flipped from A to B
                flipped = true;
            }
            // If here, didn't flip because it was already B
        } while (!flipped);
    }

    public void Release()
    {
        // Set to A
        this._cur = A;
    }
}

Test (driver):

var r = new Random();
ISemaphore s = new SpinlockSemaphore();
var t_base = DateTime.Now;

var tasks = Enumerable.Range(0, 26)
    .Select(i => Task.Run(() =>
    {
        var task = (char)((int)'A' + i);
        s.Aquire();
        Console.WriteLine($"I acquired the semaphore! (Task {task} at {(DateTime.Now - t_base).TotalMilliseconds} ms)");
        Thread.Sleep(r.Next() % 1000); // Simulate work
        s.Release();
        Console.WriteLine($"I released the semaphore! (Task {task} at {(DateTime.Now - t_base).TotalMilliseconds} ms)");
    }))
    .ToArray();

Task.WaitAll(tasks); // Run all tasks (concurrently)

Console.ReadKey(); // Keep Console window from closing

Output: examples of acquisitions before releases

I acquired the semaphore! (Task B at 88.7629 ms)
I released the semaphore! (Task B at 635.2041 ms)
I acquired the semaphore! (Task C at 635.2041 ms)
I released the semaphore! (Task C at 906.7672 ms)
I acquired the semaphore! (Task D at 906.7672 ms)
I released the semaphore! (Task D at 1427.5738 ms)
I acquired the semaphore! (Task E at 1427.5738 ms)
I released the semaphore! (Task E at 1565.426 ms)
I acquired the semaphore! (Task A at 1565.426 ms)
I released the semaphore! (Task A at 2387.7001 ms)
I acquired the semaphore! (Task H at 2387.7001 ms)
I released the semaphore! (Task H at 3265.8058 ms)
I acquired the semaphore! (Task I at 3265.8058 ms)
I released the semaphore! (Task I at 3586.6978 ms)
I acquired the semaphore! (Task J at 3586.6978 ms)
I released the semaphore! (Task J at 3729.4946 ms)
I acquired the semaphore! (Task G at 3729.4946 ms)
I released the semaphore! (Task G at 4720.5139 ms)
I acquired the semaphore! (Task F at 4720.5139 ms)
I released the semaphore! (Task F at 5077.1144 ms)
I acquired the semaphore! (Task K at 5077.1144 ms)
I acquired the semaphore! (Task L at 5782.0138 ms)
I released the semaphore! (Task K at 5782.0138 ms)
I released the semaphore! (Task L at 6746.3076 ms)
I acquired the semaphore! (Task N at 6746.3076 ms)
I released the semaphore! (Task N at 7412.1375 ms)
I acquired the semaphore! (Task O at 7412.1375 ms)
I released the semaphore! (Task O at 8137.582 ms)
I acquired the semaphore! (Task M at 8137.582 ms)
I released the semaphore! (Task M at 8327.2192 ms)
I acquired the semaphore! (Task R at 8327.2192 ms)
I released the semaphore! (Task R at 8907.7793 ms)
I acquired the semaphore! (Task S at 8907.7793 ms)
I released the semaphore! (Task S at 9445.4624 ms)
I acquired the semaphore! (Task P at 9445.4624 ms)
I released the semaphore! (Task P at 10231.1811 ms)
I acquired the semaphore! (Task Q at 10231.1811 ms)
I released the semaphore! (Task Q at 10368.8125 ms)
I acquired the semaphore! (Task V at 10368.8125 ms)
I released the semaphore! (Task V at 10992.4072 ms)
I acquired the semaphore! (Task U at 10992.4072 ms)
I released the semaphore! (Task U at 12019.8456 ms)
I acquired the semaphore! (Task T at 12019.8456 ms)
I released the semaphore! (Task T at 12303.2822 ms)
I acquired the semaphore! (Task Y at 12303.2822 ms)
I released the semaphore! (Task Y at 12378.0044 ms)
I acquired the semaphore! (Task X at 12378.0044 ms)
I acquired the semaphore! (Task W at 12705.6469 ms)
I released the semaphore! (Task X at 12705.6469 ms)
I acquired the semaphore! (Task Z at 13671.7837 ms)
I released the semaphore! (Task W at 13671.7837 ms)
I released the semaphore! (Task Z at 14262.6353 ms)

So far I've been unable to figure out the issue through Debugging and re-thinking the interleavings to convince myself it should work.

Ways I've tried to solve it through brute force:

• Change _cur to have modifier volatile
• Litter the code with Thread.MemoryBarrier()s

I'm anxious to hear what obvious flaw I'm overlooking :)

Answer 1

Even if your spinlock is working perfectly (it looks right at first glance, but it's extremely easy to make a mistake with such kind of code), there is an obvious race condition in your driver code:

[...]
s.Release();
Console.WriteLine($"I released the semaphore! (Task {task} at {(DateTime.Now - t_base).TotalMilliseconds} ms)");

The Console.WriteLine is not locked, and so it could happen that the next task acquires the lock and prints the acquire message before the releasing task gets to print its releasing message.

Instead, you could put a "I'm releasing the lock..." message just before the s.Release(). If you still see intertwined messages then, your spinlock is broken. If not, it may be working correctly.