Mutual Exclusion Theory: Critical Sections, Peterson's Algorithm, Semaphores and Monitors

Version note: The code in this post was built and run with .NET 10 (C# 14); tests use xUnit v3 4.0.3. The outputs were taken on ARM64; statements about x64 are based on the .NET memory model spec and Intel's documentation.

Guess First

In Bookstore, the online bookstore used as the shared example across this site's series, two threads increment the same counter. Without a lock, Interlocked or any ready-made synchronization type, only by reading and writing shared variables, can you prevent both threads from entering the critical section at the same time? Peterson's algorithm from the textbooks does exactly that, and it comes with a proof. If we make every access with Volatile.Read and Volatile.Write, how many times in 40 million entries does this algorithm let both threads in together on ARM64?

Second question: four consumer threads wait on the shipping preparation queue. If the queue is empty they wait with if (count == 0) Monitor.Wait(...), and when they wake up they take a parcel. In a run that processes 200,000 parcels, how many times do they try to take a parcel from an empty queue? In the previous post we saw that the common fix for races is "reduce the check and the action to a single step other threads cannot see". In this post we look at the theory that makes that step possible.

The Three Requirements of the Critical Section Problem

A critical section is a region of code that touches shared data and must be executed by only one thread at a time. Edsger Dijkstra first stated the problem in its modern form in his 1965 notes "Cooperating Sequential Processes" and in a short paper published the same year. In the classic formulation of operating system textbooks, a correct solution must meet three requirements:

• Mutual exclusion: while one thread is in the critical section, no other thread can be there.
• Progress: if the critical section is empty and some threads want to enter, the decision of who enters cannot be postponed forever; a thread that does not want to enter cannot block that decision.
• Bounded waiting: after a thread announces that it wants to enter, there is an upper bound on how many times other threads can go ahead of it; nobody waits forever.

The first requirement is about safety, the other two about progress. Meeting only the first is easy: a lock that lets nobody in provides perfect mutual exclusion but is useless. The hard part is meeting all three together without assuming any atomic hardware instruction.

With Only Reads and Writes: First Attempts

The first idea is for each thread to keep a "I want to enter" flag: if the other's flag is down, raise yours and go in.

// Attempt 1: check the other's flag, then raise our own (the check and the write are separate)
public sealed class FlagOnlyLock : ITwoThreadLock
{
    private readonly int[] _wants = new int[2];

    public void Enter(int me)
    {
        while (Volatile.Read(ref _wants[1 - me]) == 1) { }
        Volatile.Write(ref _wants[me], 1);
    }

    public void Exit(int me) => Volatile.Write(ref _wants[me], 0);
}

This is the check-then-act from the previous post: both threads can see the other's flag down and enter at the same time. To measure it, each thread does a plain counter++ inside the critical section; every lost increment proves that both threads were inside at the same time (the real number of violations can be higher still).

The second classic attempt is strict alternation: a shared turn variable says whose turn it is, and threads enter in alternation. It provides mutual exclusion but breaks progress: if it is your turn and you never want to enter, the other thread waits even though the critical section is empty. If the shipping service produces a parcel every second and the report thread enters once an hour, the shipping service waits for the report every time.

Peterson's Algorithm and the Reality on ARM64

In 1981 Gary Peterson published a short solution that combines both ideas: a flag and a turn. A thread first announces that it wants to enter, then politely gives the turn to the other side, and waits only while "the other side also wants in and it is their turn":

// Peterson (1981): raise the flag, give the turn away, wait while the other wants in and it is its turn
public sealed class PetersonLock(bool fullFence) : ITwoThreadLock
{
    private readonly int[] _wants = new int[2];
    private int _turn;

    public void Enter(int me)
    {
        int other = 1 - me;
        Volatile.Write(ref _wants[me], 1);
        Volatile.Write(ref _turn, other);
        if (fullFence)
            Interlocked.MemoryBarrier(); // the store-load order the algorithm assumes
        while (Volatile.Read(ref _wants[other]) == 1 && Volatile.Read(ref _turn) == other) { }
    }

    public void Exit(int me) => Volatile.Write(ref _wants[me], 0);
}

The proof on paper goes like this: if both threads are inside, both must have found the wait condition false. The thread that wrote _turn last will see that the other side raised its flag and that the turn is with the other side, and it will wait. All three requirements hold. The hidden assumption of the proof is this: a thread's writes become visible to the other thread before its own later reads. In other words, every operation happens in program order and in the same order for everyone. This is called sequential consistency, and modern processors do not provide it by default:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- mutex-attempts 20000000

flag only                lost updates:   281,354 of 40,000,000  (313 ms)
Peterson, volatile only  lost updates:        99 of 40,000,000  (4779 ms)
Peterson + full fence    lost updates:         0 of 40,000,000  (4654 ms)

The flag attempt is broken as expected. The really interesting line is the second: Peterson's algorithm, which has a proof, lost 99 increments in 40 million entries, so mutual exclusion was violated on ARM64. In a second run the number was 1,213. Looking at the JIT's output with DOTNET_JitDisasm, I saw that Volatile.Write becomes an stlr (release store) and Volatile.Read an ldapr (acquire load) instruction. A release write does not overtake the operations before it, and an acquire read does not fall behind the operations after it; but an acquire read that comes after a release write can run before that write is visible to the other core. That is exactly the order Peterson considers impossible: the read "the other's flag is down" happens before the write "I raised my flag" is visible.

Interlocked.MemoryBarrier() is a full fence: all writes before it complete before any reads after it. On ARM64 it became a dmb ish instruction, and the violations dropped to zero. This is not specific to ARM64: according to the memory ordering section of Intel's software developer's manual, x64 also allows a load to pass an earlier store to a different address. On x64, volatile reads and writes are ordinary instructions and do not prevent this reordering, so without a fence Peterson breaks on x64 too. We cover the hardware side of these differences in the fifth post, and .NET's volatile and fence rules in the sixth.

Peterson has no place in production. It works for only two threads, is slower than lock even with the fence, and its correctness depends on the memory model. Its value is educational: I know no clearer example of the lesson "even a proven algorithm has assumptions".

Hardware Support: Test-and-Set and Compare-and-Swap

Instead of struggling with plain reads and writes, hardware offers instructions that read and write in one atomic step. Test-and-set writes 1 to a location and returns the old value. Fetch-and-add atomically adds to a value and returns the old one. Compare-and-swap (CAS) says "if the value is still what I expect, write the new one", and it is powerful enough to emulate all the others. In .NET they appear as Interlocked.Exchange, Interlocked.Add and Interlocked.CompareExchange. A spinlock with test-and-set:

// Test-and-set built on an atomic exchange
public sealed class TasLock
{
    private int _held;

    public void Enter()
    {
        while (Interlocked.Exchange(ref _held, 1) == 1)
        {
            // test-and-test-and-set: wait with plain reads, retry the atomic op only when it looks free
            while (Volatile.Read(ref _held) == 1)
                Thread.SpinWait(20);
        }
    }

    public void Exit() => Volatile.Write(ref _held, 0);
}

The inner loop is an important engineering detail. An atomic instruction needs ownership of the cache line; if every waiting thread keeps calling Exchange, the line keeps changing hands between cores and even the thread holding the lock slows down. A plain read works on a shared copy of the line; the atomic operation is only retried when the lock looks free. We measured this cache line traffic between cores in the false sharing post of the How Computers Work series. Our test confirms that four threads do a million increments with this lock without losing any; but this lock does not provide bounded waiting, and an unlucky thread can keep losing the race.

A spinlock burns CPU while it waits; a blocking lock puts the thread to sleep, and the OS takes microseconds to wake it again. If the critical section is short, spinning is cheaper; if it is long, blocking is cheaper. The practical answer is a mix of both: spin briefly, then block. .NET's SpinWait type provides this mix, and according to its documentation it always yields instead of busy waiting on a single-processor machine. The SpinCount property of ManualResetEventSlim also tells how many spins happen before falling back to a kernel wait. Writing your own spinlock in application code is almost never right; we covered using lock and the Lock type in the synchronization post of the C# Asynchronous Programming series.

The Semaphore: Dijkstra's P and V

In the same 1965 work, Dijkstra defined the semaphore: a counter that cannot go negative and two atomic operations. P (named from Dutch; today called wait) waits if the counter is zero and otherwise decrements it. V (signal) increments the counter and wakes one waiter if there is any. A semaphore with an initial value of 1 behaves like a mutex; one with N allows at most N threads to use a resource at the same time. Sending at most 4 concurrent requests to the external shipping API in Bookstore is a typical example; the .NET counterpart is SemaphoreSlim.

The strength of the semaphore is that the counter carries "how many resources are free". Its weakness is that it needs discipline: wait and signal calls are scattered across the code, and forgetting one or mixing up their order produces bugs the compiler cannot catch. The monitor emerged to solve this.

Monitors and Condition Variables: Hoare, Brinch Hansen and Mesa

The monitor idea comes from the work of Per Brinch Hansen and Tony Hoare in the early 1970s; Hoare's 1974 paper "Monitors: An Operating System Structuring Concept" is the basis of today's definition. A monitor puts shared data and the operations that change it into a single structure; only one thread can be inside at a time. Because the lock is taken and released automatically, the scattering of the semaphore goes away.

The lock alone is not enough; sometimes a thread inside the monitor has to wait for a condition: "the queue is empty, wait until a parcel arrives". The condition variable provides this: wait releases the lock and puts the thread to sleep, and takes the lock again on wake-up; signal wakes one of the waiters. There are two different meanings here. In Hoare semantics, the signalling thread steps aside immediately and the woken thread takes the lock directly; when it wakes, the condition is guaranteed to still hold. In Mesa semantics, named after the 1980 paper in which Butler Lampson and David Redell described their experience with Xerox's Mesa language, a signal is only a hint: the woken thread moves to the ready queue, and before it gets the lock another thread can get in and break the condition again.

Almost all of today's systems use Mesa semantics. .NET's Monitor.Wait/Pulse pair works this way too: according to its documentation, Pulse moves a waiting thread to the ready queue, and the thread that takes the lock when it is released does not have to be the one that was pulsed. POSIX condition variables additionally allow waking up without any signal (spurious wakeup). The result is a single rule: wait for the condition with while, not if; check the condition again when you wake up.

Scenario: The Shipping Preparation Queue

In the warehouse, two producers prepare order parcels and four consumers hand them to the shipping company. The shelf for parcels holds 4: if the shelf is full the producer waits, if it is empty the consumer waits. This is the classic bounded buffer problem, built as a monitor with two conditions (shelf not full, shelf not empty):

// Bounded buffer as a monitor: one lock, two conditions (not full, not empty)
public sealed class ShippingQueue(int capacity, bool recheckWithWhile)
{
    private readonly Queue<Parcel> _parcels = new();
    private readonly object _monitor = new();

    public void Put(Parcel parcel)
    {
        lock (_monitor)
        {
            while (_parcels.Count == capacity)
                Monitor.Wait(_monitor);
            _parcels.Enqueue(parcel);
            Monitor.PulseAll(_monitor);
        }
    }

    public Parcel Take()
    {
        lock (_monitor)
        {
            if (recheckWithWhile)
            {
                while (_parcels.Count == 0)
                    Monitor.Wait(_monitor);
            }
            else if (_parcels.Count == 0)
            {
                Monitor.Wait(_monitor); // the condition may be false again when we wake up
            }
            Parcel parcel = _parcels.Dequeue();
            Monitor.PulseAll(_monitor);
            return parcel;
        }
    }
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- shipping-queue

if    delivered=200,000 Take() on empty queue=54,234
while delivered=200,000 Take() on empty queue=0

In the if version, consumers tried to take a parcel from an empty queue 54,234 times and got an InvalidOperationException (the experiment catches and counts it). The scenario: three consumers wait on an empty shelf, a parcel arrives and PulseAll wakes all three. The first takes the parcel; when the other two get the lock in turn, the shelf is empty again, but if does not look at the condition again. The while version has no errors in the same run. I use PulseAll here because two different conditions are waited on in a single monitor: Pulse wakes only one thread, and if that thread is waiting for the wrong condition (waking a producer when you meant to wake a consumer), the signal is lost and the system can stall.

In practice you do not write this class yourself: a bounded Channel<T> does the same job asynchronously and with backpressure, as we covered in the Channels post of the C# Asynchronous Programming series. But knowing what is inside Channels keeps you from making the same mistake wherever you write your own conditional wait (cache filling, a connection pool, a rate limiter).

In Production

Do not do I/O inside a lock. A database call or an HTTP request made while holding a lock stretches the critical section by milliseconds and serializes every waiting thread; in the Amdahl calculation of the first post this directly grows the serial part. Prepare the data first, take the lock only to change shared state, and do the I/O outside the lock.

Lock granularity is a trade-off. Protecting all stock with a single lock (coarse-grained) is simple and has no deadlock risk, but every reservation waits for the others. A lock per book (fine-grained) increases parallelism, but an operation that changes two books takes two locks and opens the door to deadlock, the subject of the next post. Do not move to fine-grained locking without measuring; move when the contention really is on the lock.

Watch lock contention. The dotnet.monitor.lock_contentions metric of the System.Runtime meter, added in .NET 9, counts how many times another thread held a monitor lock when a thread tried to take it since the process started; you can read the same value from code with Monitor.LockContentionCount. A number that grows fast with load is the first sign that the lock is a bottleneck.

Common Pitfalls

Waiting with if. In the experiment it produced 54,234 errors in a run of 200,000 parcels. Under Mesa semantics, waking up does not mean the condition holds; always use while.

Believing volatile preserves every order. The volatile version of Peterson broke on ARM64, and it breaks on x64 too. Volatile gives acquire/release; it does not give the order of a load that follows a store. A full fence gives that, and lock and Interlocked already include it.

Believing a pulse is remembered. According to the documentation, Monitor does not store a pulse; a Pulse called while nobody waits is lost. Keep the condition in a field and check that field before waiting; trust the state, not the signal.

Writing your own lock. All the locks in this post are educational. In production, lock/Lock, SemaphoreSlim and Channel<T> are tools tested for years that use the memory model correctly and balance fairness against spinning.

A Small Experiment

★☆☆ Run the mutex-attempts command a few times and note how many increments the volatile Peterson loses. Why does the number vary so much from run to run?

★★☆ Use Pulse instead of PulseAll in ShippingQueue and run the while version a few times. If the program hangs, explain which condition the threads are waiting for. Then explain a case where Pulse is safe: what changes if the queue has no capacity limit and only consumers wait?

★★★ Add bounded waiting to TasLock: write a ticket lock. Use two int counters; an entering thread takes a number with Interlocked.Increment and waits until "the number now being served" equals its own. With four threads, count how many times each thread enters and compare fairness with TasLock.

In this post we accepted that a thread cannot make progress while it waits for a lock. But what if two threads wait for the lock the other one holds? In the next post we define deadlock with Coffman's four conditions, actually deadlock a stock transfer between two Bookstore warehouses, fix it with lock ordering, and look at livelock, starvation and the priority inversion that stopped Mars Pathfinder.