Lock-Free and Wait-Free Programming

This chapter covers lock-free and wait-free data structures and algorithms: what they guarantee, why they are hard, and how to build a few basic ones.

Why This Matters

Locks can cause deadlock, priority inversion, and contention. Lock-free structures avoid these but introduce the ABA problem, memory-ordering subtleties, and high complexity. Understanding the guarantees is essential before using them.

Prerequisites

• c.conc.6 — CAS and memory orders.

Core Concept

• Lock-free: some thread makes progress in a bounded number of steps, even

if others are delayed. No thread can block the whole structure.

• Wait-free: *every* thread makes progress in a bounded number of its own

steps, regardless of others.

Lock-free is weaker than wait-free. Both are built from atomic operations (especially CAS), not mutexes.

The ABA problem

A thread reads value A; another thread changes A → B → A; the first thread's CAS succeeds even though the object logically changed. This breaks lock-free stacks/queues. Solutions include tagged pointers (with a version counter) or hazard pointers.

Examples

Lock-free stack (push/pop)

#include <stdatomic.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

static atomic_intptr_t head = ATOMIC_VAR_INIT(0);

void push(Node *n)
{
    intptr_t old;
    do {
        old = atomic_load(&head);
        n->next = (Node *)old;
    } while (!atomic_compare_exchange_weak(&head, &old, (intptr_t)n));
}

Node *pop(void)
{
    intptr_t old;
    Node *n;
    do {
        old = atomic_load(&head);
        n = (Node *)old;
        if (n == NULL) return NULL;
    } while (!atomic_compare_exchange_weak(&head, &old, (intptr_t)n->next));
    return n;
}

This is lock-free (a failed CAS means another thread succeeded), but it has the ABA problem: a node could be freed and reused, and a stale head value could still pass CAS.

How It Works

CAS is used in a retry loop: read, compute, try to commit. If another thread changed the state, the CAS fails and the loop retries. Progress is guaranteed because some thread's CAS succeeds each round.

Variations

Wait-free counters

A simple atomic counter is wait-free: atomic_fetch_add completes in a bounded number of steps per thread, with no retry loop.

RCU, hazard pointers, epoch reclamation

Memory reclamation for lock-free structures is the hard part. These techniques defer freeing until no thread can be using a node.

Common Mistakes

• Ignoring the ABA problem.
• Freeing a node immediately after popping it (another thread may still hold a

pointer).

• Using non-atomic reads/writes inside a lock-free structure.
• Assuming lock-free means faster (it can be slower under contention).

Undefined Behavior

• A data race on the node pointers/values if they are not atomic or properly

ordered. VERIFIED

• Use-after-free from premature reclamation.

Portability

• C11 atomics are standard, but lock-free progress guarantees depend on the

implementation (check atomic_is_lock_free).

Under the Hood

atomic_compare_exchange_weak compiles to lock cmpxchg (x86) or a load-linked/store-conditional loop (ARM). The retry loop is the core idiom.

Practical Usage

• Use atomic counters and flags freely.
• Use lock-free queues/stacks only when you can solve reclamation safely.
• Prefer proven libraries (e.g., a published MPMC queue) over hand-rolled code.

Exercises

1. Implement the lock-free stack and stress-test it. 2. Demonstrate the ABA problem (with a tagged pointer counter). 3. Implement a wait-free atomic counter.

Deep Challenge

Implement a lock-free stack with tagged pointers to solve the ABA problem, and explain why the tag increment prevents the stale-read CAS from succeeding.

Related Concepts

• c.conc.6 — CAS.
• c.conc.7 — fences.
• c.conc.9 — deadlock.

References

• "The Art of Multiprocessor Programming" (Herlihy & Shavit); published

lock-free algorithms.

Verification

• Lock-free vs. wait-free definitions. VERIFIED
• ABA problem and solutions. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Lock-free definition
• [ ] Wait-free definition
• [ ] CAS retry loop
• [ ] ABA problem

Mastery levels