Building a Work-Stealing Queue

The Problem: Idle Cores and The Need for Dynamic Load Balancing

Imagine you have a large computational task that can be broken down into many smaller sub-tasks. You have a pool of worker threads running on multiple CPU cores. How do you distribute the work?

A simple approach is static scheduling: divide the work evenly at the beginning and assign a fixed chunk to each thread. This works well only if every sub-task takes the same amount of time. If some tasks are quick and others are long, some threads will finish early and sit idle while others are still chugging away. This is inefficient.

A better approach is dynamic scheduling, where work is distributed as threads become available. A common way to do this is with a central, shared queue. When a thread is free, it pulls the next task from the queue. This is better, but this central queue now becomes a major bottleneck. Every thread must acquire a lock to access it, leading to high contention and poor scalability.

Work-stealing is a clever form of dynamic scheduling that solves this problem by giving each worker thread its own local queue of tasks. This dramatically reduces contention.

To get a comprehensive overview of these concepts, including a great analogy to explain work stealing, please watch the following presentation from CppCon.

The Work-Stealing Deque: A Specialized Data Structure

As the video explained, the work-stealing pattern relies on each worker thread having its own double-ended queue, or deque. This is not a general-purpose deque; it's highly specialized for three operations with specific concurrency rules:

1. push: A worker adds a new task to its own deque. This is often called push_bottom.
2. pop: A worker takes a task to execute from its own deque. This is pop_bottom.
3. steal: An idle worker (the "thief") takes a task from another worker's (the "victim") deque. This is pop_top.

This LIFO/FIFO asymmetry is a key design feature:

• LIFO for the owner (pop): The worker operates on the most recently added task. This often leads to excellent cache performance, as the data related to this task is likely still in the CPU's L1/L2 cache (temporal locality).
• FIFO for the thief (steal): The thief steals the oldest task. In divide-and-conquer algorithms, the oldest tasks often represent larger chunks of the total work. Stealing a larger chunk means the thief can stay busy for longer, reducing the need for frequent (and more expensive) stealing operations.

Designing the Deque: From Locked to Lock-Free

Now, let's focus on the implementation. The most efficient work-stealing deques are lock-free, but it's easier to understand the logic by starting with a version that uses a lock. The core idea is to use a circular array and two indices: top and bottom.

Lock-Based C Implementation Sketch

Based on that reading, we can sketch out a C structure. We'll use a simple mutex to protect access.

#include <pthread.h>

#define DEQUE_CAPACITY 2048

// A simplified task structure
typedef struct {
    void (*function)(void*);
    void* arg;
} task_t;

typedef struct {
    task_t* tasks;          // A circular array of tasks
    long bottom;            // Index for push and pop
    long top;               // Index for steal
    pthread_mutex_t mutex;
} work_stealing_deque_t;

// Initialization
void deque_init(work_stealing_deque_t* deque) {
    deque->tasks = malloc(sizeof(task_t) * DEQUE_CAPACITY);
    deque->bottom = 0;
    deque->top = 0;
    pthread_mutex_init(&deque->mutex, NULL);
}

// Push a task onto the deque (owner only)
void deque_push(work_stealing_deque_t* deque, task_t task) {
    pthread_mutex_lock(&deque->mutex);
    deque->tasks[deque->bottom % DEQUE_CAPACITY] = task;
    deque->bottom++;
    pthread_mutex_unlock(&deque->mutex);
}

// Steal a task from the deque (thief only)
bool deque_steal(work_stealing_deque_t* deque, task_t* task) {
    pthread_mutex_lock(&deque->mutex);
    if (deque->top < deque->bottom) {
        *task = deque->tasks[deque->top % DEQUE_CAPACITY];
        deque->top++;
        pthread_mutex_unlock(&deque->mutex);
        return true;
    }
    pthread_mutex_unlock(&deque->mutex);
    return false;
}

// Pop a task from the deque (owner only)
bool deque_pop(work_stealing_deque_t* deque, task_t* task) {
    pthread_mutex_lock(&deque->mutex);
    deque->bottom--;
    if (deque->top <= deque->bottom) {
        *task = deque->tasks[deque->bottom % DEQUE_CAPACITY];
        pthread_mutex_unlock(&deque->mutex);
        return true;
    }
    // Deque was empty or became empty after a concurrent steal
    deque->bottom++; // Roll back
    pthread_mutex_unlock(&deque->mutex);
    return false;
}

This locked version works, but it serializes all access. The goal is to allow the owner to push/pop without conflict from a steal operation. This requires going lock-free.

Lock-Free Implementation

A high-performance implementation avoids locks by using atomic operations, specifically compare-and-swap (CAS). The key insight is that push and pop only modify bottom, while steal only modifies top. This separation allows for mostly independent operation.

The only point of contention is when the deque contains exactly one item. In this case, a pop by the owner and a steal by a thief might race to grab the last item. This race is resolved using a CAS operation.

Let's see how this is done in detail.

Let's translate the logic from the blog post into C, using GCC/Clang's atomic built-ins (C11 _Atomic types provide a standardized way to do this as well).

push (Owner):
The owner is the only thread that writes to bottom. No other thread modifies it. So, we just need to make sure the task is written to the array before bottom is incremented and made visible to other threads. A memory barrier ensures this ordering.

// Owner pushes to the bottom
void deque_push(work_stealing_deque_t* deque, task_t task) {
    long b = deque->bottom;
    deque->tasks[b % DEQUE_CAPACITY] = task;
    // Ensure the task write is visible before the bottom update
    __sync_synchronize(); 
    deque->bottom = b + 1;
}

steal (Thief):
A thief reads top, then bottom. If top < bottom, there might be work. It tries to steal by atomically incrementing top with a CAS. If the CAS succeeds, it won the race and can take the task at the old top index.

// Thief steals from the top
bool deque_steal(work_stealing_deque_t* deque, task_t* task) {
    long t = deque->top;
    // Ensure top is read before bottom
    __sync_synchronize();
    long b = deque->bottom;

    if (t < b) {
        *task = deque->tasks[t % DEQUE_CAPACITY];
        // Attempt to claim this task
        if (__sync_bool_compare_and_swap(&deque->top, t, t + 1)) {
            // Success!
            return true;
        }
    }
    return false; // Deque is empty or another thief won the race
}

pop (Owner):
This is the most subtle. The owner decrements bottom. If the deque is now empty (top > bottom), it resets bottom and fails. If it's not empty, there's still a race with a potential thief if there was only one item. The owner tries to "win" the race by atomically moving top up. If it succeeds, it got the last item. If not, a thief got it.

Integrating the Deque into a Thread Pool

This deque is the heart of a work-stealing thread pool. In a complete system, you would have:

• A pool of worker threads.
• An array of work-stealing deques, one for each worker.
• A mechanism for threads to find a "victim" to steal from (e.g., picking a random index).
• A way for idle threads to sleep when no work is available anywhere, and be woken up when new work is submitted.

The following resource describes how such a system is structured as a university project, which provides excellent context for a real-world implementation.

Conclusion

In this lesson, we designed a highly concurrent, high-performance work-stealing queue. This is a significant step in building practical parallel systems.

Key Takeaways:

• Work-stealing provides dynamic load balancing with low overhead by giving each worker a local deque, minimizing contention.
• The deque is a specialized data structure with push/pop (owner, LIFO) and steal (thief, FIFO) operations. This asymmetry improves cache performance and reduces stealing frequency.
• A lock-free implementation using atomic operations (like CAS) and memory barriers is essential for performance. It relies on top and bottom indices being modified by different threads, with a CAS to resolve the race for the last item.
• This deque is a core component of a larger thread pool or job system.

Preview of the Next Lesson:
We've successfully designed a key data structure for task-based parallelism. For our next capstone project, we will switch gears from managing ephemeral tasks to managing persistent, expensive resources. We will build a thread-safe connection pool to manage a finite number of resources, such as database connections or network sockets—another essential pattern in concurrent server-side software.