Lock-Free Executor Queues

In this lesson, you will learn how to design a high-throughput, lock-free work-stealing queue to minimize contention in asynchronous task scheduling.

The Bottleneck of Mutexes

In a multi-threaded executor, every worker thread needs to pull tasks from a queue. If you use a standard Mutex<VecDeque<Task>>, every thread must acquire a lock before accessing the queue. Under heavy load, your threads spend more time waiting for the lock than executing tasks. This is the "thundering herd" problem of synchronization.

Designing the Lock-Free Queue

To solve this, we replace the Mutex with a circular buffer and atomic indices. Instead of locking the whole structure, we use AtomicUsize pointers for head (where tasks are popped) and tail (where tasks are pushed).

A common design is the "Chase-Lev" deque. Here, the local worker thread pushes and pops from the tail, while other threads "steal" tasks from the head. By using std::sync::atomic::AtomicUsize with Ordering::Relaxed or Ordering::AcqRel, we can ensure that threads only synchronize when absolutely necessary.

Simple Atomic Push Logic

A simplified push operation looks like this:

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

struct Queue {
    buffer: [Task; 1024],
    tail: AtomicUsize,
}

impl Queue {
    fn push(&self, task: Task) {
        let t = self.tail.load(Ordering::Relaxed);
        self.buffer[t % 1024] = task;
        // Ensure the task is written before updating the index
        self.tail.store(t + 1, Ordering::Release);
    }
}

By using Ordering::Release, we guarantee that any thread observing the updated tail will also see the task written into the buffer. Because the local worker owns the tail, it doesn't need a lock to add work. Similarly, when another thread tries to steal, it attempts to compare_exchange the head index. If the CAS (Compare-And-Swap) succeeds, it has successfully "claimed" that task without ever blocking the executor’s main loop.

This decentralized approach allows your executor to scale linearly with the number of CPU cores, as worker threads operate independently on their own local queues, only interacting with other threads during rare, non-blocking theft operations.

Key Takeaway: By replacing global mutexes with atomic index pointers and memory ordering primitives, you eliminate lock contention, allowing your executor to scale across multiple cores without performance-killing bottlenecks.