Lock-Free Work-Stealing Thread Pool

A lock-free thread pool written in C11 using atomics and POSIX threads.

This project started as an exercise to understand C11 atomics and gradually evolved into a work-stealing thread pool with lock-free queues and epoch-based memory reclamation.

Features

• Lock-free Michael–Scott queue (CAS-based enqueue/dequeue)
• Multiple producers
• Multiple consumers
• Per-worker private queues
• Round-robin task submission
• Work stealing between workers
• Epoch-based memory reclamation
• Function pointer + parameter job representation
• POSIX threads (pthread)
• C11 atomics

---

Architecture

Each worker owns a private queue.

             submit_job()

                  |
                  v

       +-----+-----+-----+-----+
       | Q0  | Q1  | Q2  | Q3  |
       +-----+-----+-----+-----+
          |      |      |      |
          v      v      v      v
         W0     W1     W2     W3

Tasks are distributed in a round-robin fashion across worker queues.

Each worker always attempts to execute work from its own queue first.

If its queue becomes empty, it randomly selects another worker and attempts to steal work from that worker's queue.

---

Queue

Each worker queue is an implementation of the Michael–Scott lock-free queue.

The queue uses:

• Atomic head pointer
• Atomic tail pointer
• Compare-and-swap (CAS)
• Helping when the tail pointer falls behind

No mutexes are used for queue operations.

---

Memory Reclamation

Immediately freeing nodes after dequeue introduces the ABA problem.

Instead, every worker maintains a private retired list.

Queue
  |
  v

Retired List
  |
  v

grim_reaper()

Workers publish:

• Active status
• Local epoch

A global epoch advances only when every active worker has observed the current epoch.

Nodes are reclaimed only after they have survived enough epoch advances to guarantee that no worker can still reference them.

---

Job Representation

Each task consists of a function pointer and a parameter pointer.

struct Node {
    void (*function)(void *);
    void *params;
    _Atomic(struct Node *) next;
};

This allows arbitrary functions to be submitted to the thread pool.

Example:

void print_number(void *arg)
{
    printf("%d\n", *(int *)arg);
}

---

Current Design

• Lock-free Michael–Scott queues
• Per-worker private queues
• Round-robin scheduling
• Random work stealing
• Epoch-based memory reclamation
• Lock-free scheduling path

---

Building

gcc -std=c11 -O2 -pthread pool.c -o pool

---

What I Learned

This project was built primarily as a systems programming exercise covering:

• C11 atomics
• Compare-and-swap (CAS)
• Lock-free programming
• Michael–Scott queues
• Epoch-based memory reclamation
• Work-stealing schedulers
• POSIX threads
• Concurrent memory ownership
• ABA hazards

---

References

• Maged M. Michael and Michael L. Scott, Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms (1996)
• ISO C11 Atomics (stdatomic.h)
• POSIX Threads (pthread)