Wait-Free Data Structure Design

In this lesson, you will learn how to design data structures that guarantee every thread makes progress within a finite number of steps, regardless of the behavior of other threads.

The Limitation of Lock-Free

Previously, we explored atomic operations and spinlocks. While these allow threads to bypass the OS scheduler, they are typically "lock-free" rather than "wait-free." In a lock-free structure, the system as a whole makes progress, but an individual thread might be repeatedly forced to retry its operation because other threads keep "winning" the race to update a shared atomic variable. This is often acceptable, but in real-time systems, we need a stronger guarantee: every thread must complete its task in a bounded number of steps.

The Wait-Free Architectural Pattern

To achieve wait-freedom, we must move away from the "try-update-retry" loop. The core strategy is Help-Others or State Pre-computation. Instead of a thread trying to force its own update, it announces its intent in a shared structure, and other threads help complete that intent before working on their own.

Consider a simple scenario where we want to increment a value without contention-based retries:

use std::sync::atomic::{AtomicUsize, Ordering};

struct WaitFreeCounter {
    // Each thread has a dedicated slot to announce its intent
    // This avoids contention on a single global atomic.
    slots: [AtomicUsize; 8], 
}

impl WaitFreeCounter {
    fn increment(&self, thread_id: usize) {
        // A thread only modifies its assigned slot.
        // It never waits for others or competes for a single location.
        self.slots[thread_id].fetch_add(1, Ordering::Relaxed);
    }
}

In this pattern, the "wait-free" nature is achieved by partitioning the state. By ensuring that no thread ever checks the state of another thread to decide its next move, we eliminate the retry loop entirely. If you have a task that requires global state coordination, you must structure the data so that operations can be performed as "passive snapshots" or through dedicated per-thread buffers that are later aggregated in a way that doesn't block the producers.

Designing these structures requires ensuring that memory reads and writes are strictly ordered to prevent partial updates from being observed, relying heavily on the memory ordering concepts we discussed previously.

Key Takeaway: Wait-free data structures eliminate the "retry loop" by partitioning state or employing cooperative algorithms where threads help each other complete work, ensuring every participant finishes in bounded time.