A wait-free data structure guarantees that every thread completes each operation in a finite number of steps, regardless of what other threads do. The guarantee applies to each operation, not merely to the system as a whole. A stalled or failed thread therefore cannot prevent another thread from making progress. section 8.5
This matters when shared data sits on a latency-sensitive path, such as a job queue. A thread acquiring a mutex can wait behind a long critical section, a stalled lock holder, or other contenders. Wait-free synchronization avoids that blocking dependency, though its implementation can be substantially harder than locking. section 8.5.1 section 8.0
Progress conditions differ in who is guaranteed to finish:
- Obstruction-free: an operation completes in finite time if it runs without contention. section 8.5
- Lock-free: some threads complete in finite time, but an individual thread may suffer heavy tail latency. section 8.5
- Wait-free: every thread completes in finite time. The bounded variant also specifies an upper bound on steps; the stronger population-oblivious variant specifies the same step count regardless of other threads’ actions. section 8.5 section 8.5.1
A bounded single-producer, single-consumer (SPSC) queue makes the guarantee concrete. Its fixed-size array holds items; front and back indexes track removals and insertions. Push returns an error when full, and pop returns no item when empty. Those outcomes let an attempted operation finish rather than wait for another thread to make space or supply data. section 8.6
The concurrent Rust version replaces ordinary indexes with atomic indexes. Each side reads its own index with relaxed ordering and the other side’s index with acquire ordering; after accessing an array slot, it publishes its updated index with release ordering. The producer writes through an unsafe pointer, making correct reasoning about slot access and publication essential. section 8.6
/// Pushes an item into the queue. Returns an error if the queue is full.
pub fn push(&self, value: T) -> Result<(), T> {
let back = self.back.load(Ordering::Relaxed);
let front = self.front.load(Ordering::Acquire);
if front + N - back == 0 {
return Err(value);
}
let ptr = self.data.as_ptr() as *mut T;
unsafe {
ptr.add(back % N).write(value);
}
self.back.store(back + 1, Ordering::Release);
Ok(())
}
The push implementation checks capacity, writes the selected slot, then publishes the new back index with a release store. section 8.6
/// Pops an item from the queue. Returns `None` if the queue is empty.
pub fn pop(&self) -> Option<T> {
let front = self.front.load(Ordering::Relaxed);
let back = self.back.load(Ordering::Acquire);
if back - front == 0 {
return None;
}
let value = self.data[front % N];
self.front.store(front + 1, Ordering::Release);
Some(value)
}
The matching pop implementation checks for an empty queue, reads the selected slot, then publishes the new front index. section 8.6
Do not treat the queue’s simple index updates as a recipe for every data structure. Linked-list insertion may require allocation and a pointer update that fails under contention; retrying a failed compare-and-swap can limit the wait-free guarantee. Deletion also needs safe memory reclamation because another thread may still see the removed node. Reference counting, hazard pointers, and epoch-based reclamation are approaches to that separate problem. section 8.5.5
The practical test is whether each operation has a finite completion path even when other threads contend, stall, or fail. Establish that guarantee alongside the synchronization logic, then measure the workload: wait-free progress offers a latency guarantee, not a promise that every implementation is faster. section 8.5 section 8.6
