Lock-Free and Wait-Free: CAS Loops, the ABA Problem and Linearizability

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

Guess First

In Bookstore, the online bookstore used as the shared example across this site's series, you want to write the sales counter without a lock: read the value, add one, write the new value if the value is still what you read, otherwise start over. When eight threads record 8 million sales in total, how many times does "the value changed, start over" happen? And is this lock-free counter faster or slower than an ordinary counter protected by a lock?

Second question: you wrote a lock-free stack and, to cut allocations, you put popped nodes into a pool and reuse them. The algorithm is the same, only the nodes are reused. When eight threads push and pop 8 million ids, how many ids get lost? In the previous post we derived from the memory model why locks and Interlocked work correctly. In this post we drop the lock entirely.

Progress Guarantees: From Blocking to Wait-Free

The basic weakness of code with locks is this: if the thread holding the lock is suspended by the OS, hits a page fault or gets stuck in an exception, everyone waiting for that lock stops too. One slow thread can stop the whole system. Algorithms like this are called blocking. Lock-free algorithms give different levels of guarantee for progress, and these levels have established names in the literature:

• Obstruction-free: if the other threads stop, a thread running alone finishes its work in a finite number of steps. Under contention everyone can block each other forever.
• Lock-free: even under contention, at any moment at least one thread in the system makes progress. Individual threads can starve, but the system as a whole never gets stuck.
• Wait-free: every thread finishes its own work in a bounded number of steps, whatever the others do. This is the strongest guarantee.

Behind this classification is Maurice Herlihy's 1991 paper "Wait-Free Synchronization". Herlihy showed that memory that only supports reads and writes cannot provide even wait-free consensus between two threads, while compare-and-swap can provide it for any number of threads. Here is the link with Peterson's algorithm from the third post: mutual exclusion can be built with reads and writes alone, but that solution is blocking. A wait-free or lock-free data structure needs the hardware's atomic instructions.

The CAS Loop: A Lock-Free Counter

CAS, or compare-and-swap, is the basic tool of lock-free algorithms: an atomic operation that writes a new value to an address if the current value is the expected one, and does nothing otherwise. Its .NET counterpart is Interlocked.CompareExchange. The pattern is always the same: read, compute the new value, publish it if nobody stepped in, otherwise start over. The new folder is LockFree/:

// The CAS loop: read, compute, publish only if nobody changed the value in between, otherwise retry
public sealed class LockFreeCounter
{
    private long _value;

    public long Value => Volatile.Read(ref _value);

    // Returns how many CAS attempts failed before ours succeeded (a measure of contention)
    public int Add(long amount)
    {
        int failed = 0;
        while (true)
        {
            long seen = Volatile.Read(ref _value);
            if (Interlocked.CompareExchange(ref _value, seen + amount, seen) == seen)
                return failed;
            failed++;
        }
    }
}

This counter is lock-free but not wait-free: if a thread's CAS failed, another thread's CAS succeeded, so the system made progress. But an unlucky thread could in theory lose every time. I split eight million increments over 1, 2, 4 and 8 threads and measured the number of failed CAS attempts:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- cas-counter

threads=1 value=8,000,000 failed CAS=         0 (27 ms)
threads=2 value=8,000,000 failed CAS= 2,268,002 (167 ms)
threads=4 value=8,000,000 failed CAS= 5,988,556 (325 ms)
threads=8 value=8,000,000 failed CAS=27,774,810 (1316 ms)

The result is always correct, but with 8 threads there are 27.7 million failed attempts for 8 million successful CAS operations; each increment took four and a half attempts on average. Work that takes 27 ms on one thread took 1.3 seconds on 8 threads. Looking at the code the JIT produced, the heart of the loop is ARM64's casal instruction; Interlocked.Increment, on the other hand, becomes a single ldaddal instruction (an atomic fetch-and-add) with no loop. The latter never "fails" in hardware, which is why simple counters use the ready-made atomic operation rather than a CAS loop. The CAS loop is for cases where the new value comes from a more complex computation on the old one; the TryUpdate loop in the second post was an example.

The Treiber Stack

The best-known teaching example of lock-free data structures is the stack R. Kent Treiber published in a 1986 research report. The idea is simple: the only shared thing is the _head reference, and every change is a single CAS on that reference.

// Treiber (1986): a lock-free stack whose only shared word is the head reference
public sealed class TreiberStack<T> : IConcurrentStack<T>
{
    private sealed record Node(T Value, Node? Next);

    private Node? _head;

    public void Push(T value)
    {
        while (true)
        {
            Node? head = Volatile.Read(ref _head);
            Node node = new(value, head);
            if (Interlocked.CompareExchange(ref _head, node, head) == head)
                return;
        }
    }

    public bool TryPop(out T value)
    {
        while (true)
        {
            Node? head = Volatile.Read(ref _head);
            if (head is null)
            {
                value = default!;
                return false;
            }
            if (Interlocked.CompareExchange(ref _head, head.Next, head) == head)
            {
                value = head.Value;
                return true;
            }
        }
    }
}

The correctness argument is short as well. Nodes are immutable; once a node is created, its Next never changes. Push publishes the new node only if _head is still the node it read; Pop moves _head to the next node only if _head is still the node it read. Any change in between makes the CAS fail and the operation starts over. Since CompareExchange is a full fence, the node's contents are visible to other threads by the time its reference is published.

Each of eight threads pushes its own unique id a million times, each followed by a pop; at the end what is left in the stack is drained and we count whether every id came out exactly once. For the Treiber stack the result is zero lost and zero repeated ids out of 8 million (the first line of the output below).

The ABA Problem and the GC's Silent Help

Now to the second opening question. The version that puts popped nodes into a pool and reuses them on the next push does not change the algorithm itself at all:

public bool TryPop(out int value)
{
    while (true)
    {
        Node? head = Volatile.Read(ref _head);
        if (head is null)
        {
            value = 0;
            return false;
        }
        Node? next = head.Next;
        // head may have been popped, recycled and pushed again since we read it: CAS still succeeds
        if (Interlocked.CompareExchange(ref _head, next, head) == head)
        {
            value = head.Value;
            _pool.Enqueue(head);
            return true;
        }
    }
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- stack-stress 1000000

Treiber (new nodes)     pushed=8,000,000 missing=      0 popped twice=      0
Treiber (pooled nodes)  pushed=8,000,000 missing=699,298 popped twice=570,668
racy read-then-write    pushed=8,000,000 missing= 72,802 popped twice=242,240

In the pooled version 699,298 ids were lost and 570,668 came out twice. In the first run these numbers were around 2.6 and 2 million. The third line is a stack that reads and then writes without any CAS; we will use it shortly for linearizability.

What breaks the pooled version is the ABA problem: a value goes from A to B and back to A, and CAS takes it as "never changed". The scenario: thread 1 reads N1 as the head and N2 as its Next, then gets suspended right before the CAS. Meanwhile thread 2 pops N1 and N2, and both go back to the pool. Then a new value is pushed and the node that comes out of the pool is N1 again; now its Next points to some other node. Thread 1 wakes up, sees that the head is still N1, and the CAS succeeds: the head now points to N2, which is sitting in the pool. The rest of the stack is lost and one pooled node ends up used in two places at once.

Why is the version that creates new nodes not affected? Because the GC does not give N1's memory to another node while thread 1 holds a reference to N1. Every push is a genuinely new object, so the reference equality CAS compares also means "same node, same contents". In other words, .NET solves memory reclamation for us, the biggest problem for people writing lock-free code in C and C++. In the native world this needs techniques such as putting a version counter next to the pointer and CAS-ing both together (tagged pointers), the hazard pointers Maged Michael published in 2004, or epoch-based reclamation. In .NET there is one rule: do not pool the nodes of a lock-free structure. What you gain in allocations with pooling does not compare with the correctness you lose in the table above.

Linearizability: The Correctness Criterion

We said the Treiber stack is "correct", but what exactly does correct mean? On a single thread the answer is easy: it is correct if it follows the sequential definition of a stack. In a concurrent object, operations overlap in time. In their 1990 paper "Linearizability: A Correctness Condition for Concurrent Objects", Maurice Herlihy and Jeannette Wing gave the answer accepted as standard today. In our own words: if you can assign each operation one instant between the moment it was called and the moment it returned, and the operations ordered by those instants form a valid run of an ordinary single-threaded stack, then the observed history is linearizable.

In the Treiber stack that instant is the successful CAS itself; it is called the linearization point. In the consistency models post of the Distributed Systems Fundamentals series we used the same definition for a distributed key-value store; here we apply the same criterion to a data structure inside a single process.

This definition can be tested. Each of three threads makes four calls (push, pop, push, pop); a shared counter stamps the start and end of every call. Then a small checker tries every possible ordering, looking for a sequential run that explains the history. This brute-force search idea goes back to the 1993 work of Wing and Gong:

private static bool Search(ImmutableList<StackCall> pending, ImmutableStack<int> stack)
{
    if (pending.IsEmpty)
        return true;
    // a call can go next only if no other pending call returned before it was invoked
    long firstReturn = pending.Min(c => c.Returned);
    foreach (StackCall call in pending.Where(c => c.Invoked < firstReturn))
    {
        ImmutableStack<int> next;
        if (call.IsPush)
            next = stack.Push(call.Value);
        else if (!call.Popped)
        {
            if (!stack.IsEmpty) continue;
            next = stack;
        }
        else
        {
            if (stack.IsEmpty || stack.Peek() != call.Value) continue;
            next = stack.Pop();
        }
        if (Search(pending.Remove(call), next))
            return true;
    }
    return false;
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- linearizability 20000

Treiber  histories=20,000 not linearizable=0
racy     histories=20,000 not linearizable=63
    [ 1.. 8] T2 Push(200)
    [ 2.. 6] T0 Push(0)
    [ 3.. 4] T1 Push(100)
    [ 5..14] T1 TryPop() -> 200
    [ 7..19] T0 TryPop() -> 200
    [ 9..10] T2 TryPop() -> empty
    [11..12] T2 Push(202)
    [13..24] T2 TryPop() -> 202
    [15..16] T1 Push(102)
    [17..18] T1 TryPop() -> 102
    [20..21] T0 Push(2)
    [22..23] T0 TryPop() -> 2

All 20,000 histories of the Treiber stack are linearizable. For the stack that reads and then writes, 63 histories could not be explained, and the checker printed the first one. Let's read it on paper: at instant 10, three pushes (200, 0, 100) have finished. By then at most two pops have started, and each pop can remove at most one element, so there must be at least one element in the stack. Yet T2's pop between 9 and 10 said "empty". On top of that, two threads popped the same 200. No sequential run explains both observations at once. What the checker found is a concrete counterexample that says "no correct stack can produce this output". In real systems tools such as Jepsen's Knossos or Porcupine, written in Go, apply the same idea with far more efficient search algorithms.

Is Lock-Free Always Faster?

A common assumption is that lock-free code is faster. I measured the same 10 million increments with lock, Interlocked.Increment and the CAS loop using BenchmarkDotNet; the table shows the time per increment (ARM64, a 10-core machine, environment lines removed):

dotnet run -c Release --project bench/Bookstore.ConcurrencyLab.Benchmarks -- --filter "*CounterBenchmarks*"

| Method               | Threads | Mean       | StdDev     | Ratio |
|--------------------- |-------- |-----------:|-----------:|------:|
| Locked               | 1       |   4.901 ns |  0.4104 ns |  1.01 |
| InterlockedIncrement | 1       |   1.678 ns |  0.0172 ns |  0.34 |
| CasLoop              | 1       |   1.970 ns |  0.1725 ns |  0.40 |
|                      |         |            |            |       |
| Locked               | 2       |   8.321 ns |  0.0368 ns |  1.00 |
| InterlockedIncrement | 2       |   5.220 ns |  0.2469 ns |  0.63 |
| CasLoop              | 2       |  21.704 ns |  3.2255 ns |  2.61 |
|                      |         |            |            |       |
| Locked               | 4       |   7.116 ns |  0.2942 ns |  1.00 |
| InterlockedIncrement | 4       |  11.631 ns |  0.7229 ns |  1.64 |
| CasLoop              | 4       |  86.109 ns | 20.2068 ns | 12.12 |
|                      |         |            |            |       |
| Locked               | 8       |  11.130 ns |  0.4049 ns |  1.00 |
| InterlockedIncrement | 8       |  22.508 ns |  4.7180 ns |  2.02 |
| CasLoop              | 8       | 179.745 ns | 51.9046 ns | 16.17 |

On one thread we get the expected order: the lock-free paths are three times faster than lock. As contention grows the table turns around. On 8 threads the CAS loop is 16 times slower than lock, with a very high standard deviation as well; this is called a CAS storm. Every failed CAS pulls the cache line to one core and gives it back for nothing, and all cores queue for the same line. On 4 and 8 threads lock even beats Interlocked.Increment. My interpretation: the lock makes waiting threads spin and then wait, and the thread that holds the lock can do several increments in a row while it owns the cache line; with Interlocked the line changes core on every increment. This result belongs to this machine and this workload. On x64 and with different core counts the ratios change; do not generalize without measuring on your own machine.

That is exactly why ConcurrentStack<T> in the BCL is not a plain Treiber stack. Looking at its source code in dotnet/runtime, I saw that it waits with SpinWait when a CAS fails and uses a randomly growing backoff. In the fourth post, random backoff was also what broke the livelock.

In Production

Do not write lock-free data structures yourself. ConcurrentStack<T>, ConcurrentQueue<T>, ConcurrentDictionary<TKey, TValue> and Channel<T> have been tested for years on different hardware and use the memory model correctly. We covered their use in the synchronization and Channels posts of the C# Asynchronous Programming series. The place where you really need your own CAS loop is usually updating a single field with a complex rule (keeping the highest price, moving a state only from one specific state to another), and even there the loop should not go beyond a few lines.

Count the cost of maintaining lock-free code in a team. The pooled stack in this post differs from the normal stack by only a few lines, and in code review it can easily pass as "a nice optimization that cuts allocations". To approve a lock-free change, ask in writing why each CAS is correct and where the linearization point is. For a team that cannot write that down, lock is the better choice.

Measure the performance argument. The real benefit of lock-free code is often not average speed but that a slow lock holder does not stop the others. If you are writing it for average speed, do not decide without a measurement like the table above.

Common Pitfalls

Assuming lock-free is always fast. In the experiment the CAS loop was 16 times slower than lock on 8 threads. Under high contention a single lock can scale better than a CAS storm.

Pooling nodes. The GC silently removes the most common cause of ABA; pooling removes that protection. The pooled stack lost hundreds of thousands of the 8 million ids.

Taking lock-free for wait-free. A CAS loop guarantees progress for the system, not for each individual thread. Where you need a bound on latency, this difference matters.

Believing a stress test proves correctness. The broken stack was caught in only 63 of 20,000 histories. A stress test can show a bug but cannot prove its absence; the correctness argument is built on linearization points.

A Small Experiment

★☆☆ Add a RecordPeak(long candidate) method to LockFreeCounter: it keeps the highest daily sales count so far, and the candidate is written only if it is greater than the current value. Explain why you cannot do this with a single atomic operation like Interlocked.Increment and how the CAS loop is built.

★★☆ Fix ABA in the pooled stack with the tagged pointer idea: make _head an immutable object holding a node reference and a long version counter, and bump the version on every successful CAS. Check with stack-stress that the losses drop to zero. Why does this solution still allocate on every operation?

★★★ Write the linearizability checker for a queue (with the FIFO rule) and run it on ConcurrentQueue<T> over 20,000 histories. Then write a version that breaks the queue on purpose and explain on paper the first counterexample the checker finds.

In this post we looked at the far end of the shared memory model, lock-free data structures, and how hard they are to verify. In the last post of the series we go in a different direction: actor and CSP models that communicate with messages instead of shared memory, building Bookstore's order processing flow with these models, and verifying concurrent code beyond testing with model checking in TLA+.