[THREADING 101] 07 – Lock-Free Algorithms

What Does “Lock-Free” Mean?

An algorithm is lock-free if at least one thread is guaranteed to make progress in a finite number of steps, regardless of what other threads are doing. If one thread crashes or gets paused by the OS, the remaining threads continue without being blocked.

Compare this to lock-based code: if the thread holding a lock is suspended, every other thread waiting for that lock is also stuck.

Hierarchy of Progress Guarantees

Guarantee	Description	Example
Wait-free	Every thread completes in bounded steps	AtomicLong.incrementAndGet() (hardware support)
Lock-free	System-wide progress guaranteed	CAS-loop algorithms
Obstruction-free	Progress if run in isolation	Transactional memory
Blocking	No progress guarantee if holder stalls	synchronized, ReentrantLock

The CAS Loop Pattern

Every lock-free algorithm follows the same structure:

while (true) {
    V current = atomicRef.get();          // 1. Read current state
    V desired = computeNewState(current); // 2. Compute desired state
    if (atomicRef.compareAndSet(current, desired)) { // 3. Attempt atomic update
        break; // Success!
    }
    // CAS failed — another thread modified the value. Retry.
}

This loop retries until it succeeds. Under contention, some iterations fail, but at least one thread succeeds per “round” — guaranteeing system-wide progress.

Example 1: Lock-Free Stack

A stack where push and pop are both lock-free using a CAS on the head pointer:

import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;

public class LockFreeStack<T> {

    private static class Node<T> {
        final T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    private final AtomicReference<Node<T>> head = new AtomicReference<>(null);

    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        while (true) {
            Node<T> currentHead = head.get();
            newNode.next = currentHead;
            if (head.compareAndSet(currentHead, newNode)) {
                return; // Successfully linked new node as head
            }
            // Another thread modified head — retry
            LockSupport.parkNanos(1); // Brief pause to reduce contention
        }
    }

    public T pop() {
        while (true) {
            Node<T> currentHead = head.get();
            if (currentHead == null) {
                return null; // Stack is empty
            }
            Node<T> nextNode = currentHead.next;
            if (head.compareAndSet(currentHead, nextNode)) {
                return currentHead.data; // Successfully removed head
            }
            // Another thread modified head — retry
            LockSupport.parkNanos(1);
        }
    }

    public boolean isEmpty() {
        return head.get() == null;
    }
}

How It Works

Example 2: Lock-Free Counter with Custom Logic

public class LockFreeMinMax {
    private final AtomicReference<long[]> minMax = 
        new AtomicReference<>(new long[]{Long.MAX_VALUE, Long.MIN_VALUE});

    public void observe(long value) {
        while (true) {
            long[] current = minMax.get();
            long newMin = Math.min(current[0], value);
            long newMax = Math.max(current[1], value);
            
            if (newMin == current[0] && newMax == current[1]) {
                return; // No change needed
            }
            
            long[] updated = new long[]{newMin, newMax};
            if (minMax.compareAndSet(current, updated)) {
                return; // Successfully updated
            }
            // Contention — retry
            LockSupport.parkNanos(1);
        }
    }

    public long getMin() { return minMax.get()[0]; }
    public long getMax() { return minMax.get()[1]; }
}

Example 3: Lock-Free Published Configuration

A common pattern where a configuration is atomically published and consumers always see a consistent snapshot:

public class ConfigPublisher {
    
    public record Config(String dbUrl, int maxConnections, boolean cacheEnabled) {}

    private final AtomicReference<Config> currentConfig = 
        new AtomicReference<>(new Config("localhost:5432", 10, true));

    // Called by admin thread — publishes new config atomically
    public void updateConfig(Config newConfig) {
        currentConfig.set(newConfig); // Single volatile write — always consistent
    }

    // Called by many worker threads — always sees a complete, consistent config
    public Config getConfig() {
        return currentConfig.get(); // Single volatile read
    }
}

Performance: Lock-Free vs Lock-Based

Aspect	Lock-Based	Lock-Free
Throughput (low contention)	Good	Good (slightly better)
Throughput (high contention)	Degrades (threads blocked)	Better (threads retry, not blocked)
Latency predictability	Variable (depends on lock holder)	More predictable
CPU usage under contention	Low (threads sleep)	Higher (spinning/retrying)
Complexity	Simple	Significantly harder
Debugging	Easier	Very difficult
Memory reclamation	Straightforward	Hard (concurrent reads)

When Lock-Free Wins

• Very short critical sections (counter increment, reference swap)
• High thread counts with contention
• Systems requiring predictable latency
• Scenarios where threads must never be blocked (real-time)

When Locks Win

• Long critical sections
• Complex multi-step operations
• Readability and maintainability matter
• Low-contention scenarios where simplicity wins

The ABA Problem in Practice

In the lock-free stack, pop is vulnerable to ABA:

Stack: A → B → C

Thread 1: reads head = A, next = B
  (Thread 1 is paused by OS)

Thread 2: pops A, pops B, pushes A back
Stack: A → C

Thread 1 resumes: CAS(expected=A, new=B) → SUCCEEDS!
  But B was already popped! Stack is now corrupted.

Solutions

1. AtomicStampedReference — version counter detects changes even if value returns to original.
2. Hazard pointers — threads publish which nodes they’re accessing, preventing premature reclamation.
3. Epoch-based reclamation — defer memory reuse until all readers from the old epoch are done.

// Using AtomicStampedReference to prevent ABA
private final AtomicStampedReference<Node<T>> head = 
    new AtomicStampedReference<>(null, 0);

public void push(T item) {
    Node<T> newNode = new Node<>(item);
    while (true) {
        int[] stampHolder = new int[1];
        Node<T> currentHead = head.get(stampHolder);
        int stamp = stampHolder[0];
        newNode.next = currentHead;
        if (head.compareAndSet(currentHead, newNode, stamp, stamp + 1)) {
            return;
        }
        
        LockSupport.parkNanos(1);
    }
}

Backoff Strategies

When CAS fails repeatedly under high contention, spinning wastes CPU. Backoff strategies help:

public void pushWithBackoff(T item) {
    Node<T> newNode = new Node<>(item);
    int backoffNanos = 1;
    
    while (true) {
        Node<T> currentHead = head.get();
        newNode.next = currentHead;
        if (head.compareAndSet(currentHead, newNode)) {
            return;
        }
        // Exponential backoff — reduce contention
        LockSupport.parkNanos(backoffNanos);
        backoffNanos = Math.min(backoffNanos * 2, 1000); // Cap at 1 microsecond
    }
}

Summary

• Lock-free algorithms guarantee system-wide progress even if threads are paused or crash.
• The CAS loop (read → compute → CAS → retry) is the universal pattern.
• Lock-free stacks are relatively simple; queues require cooperative “helping.”
• The ABA problem must be addressed in data structures where nodes are recycled.
• Lock-free code is harder to write, test, and debug — use it only where the performance benefit justifies the complexity.
• Java’s ConcurrentLinkedQueue, ConcurrentLinkedDeque, and ConcurrentSkipListMap use lock-free algorithms internally.

---

References

• Michael, M.M. & Scott, M.L. — Simple, Fast, and Practical Non-Blocking Concurrent Queue Algorithms (1996)
• Jenkov — Compare and Swap
• DZone — Demystifying Java’s Compare-and-Swap (CAS)
• AlgoMaster — Compare-And-Swap (CAS)
• Herlihy, M. — The Art of Multiprocessor Programming (Book)