4.2 Lock-Free Queue

1. What LockFreeQueue Is

A Lock-Free Queue is a thread-safe queue implemented with lock-free techniques, usually relying on CAS and other atomic operations to coordinate concurrent updates.

“Lock-free” describes a system-wide progress guarantee. It does not mean there are no retries, and it does not mean it is always faster than a mutex under every workload.

2. Why LockFreeQueue Is Needed

The original note understood it from the perspective of “pessimistic locking vs optimistic concurrency”: when lock contention and thread-blocking costs become bottlenecks, atomic operations and retries can be considered to avoid holding one mutex that covers the entire queue.

Whether it is worth using still needs to be verified through the actual contention level, latency, and throughput.

3. How to Implement LockFreeQueue

The core idea recorded in the original note is:

infinite loop + CAS + singly linked list

The original enqueue/dequeue code shape is preserved below as a historical learning example. It does not fully show modern C/C++ atomic types, memory ordering, or safe memory reclamation, so it cannot be used directly as a production-grade MPMC queue implementation.

1. Enqueue

bool LockFreeQueue::enqueue(int val)
{
    QueueNode* cur_node;
    QueueNode* add_node = new QueueNode(val);
    while (1) {
        cur_node = tail;
        if (__sync_bool_compare_and_swap(&(cur_node->next), NULL, add_node)) {
            break;
        }
        else {
            __sync_bool_compare_and_swap(&tail, cur_node, cur_node->next);
        }
    }
    __sync_bool_compare_and_swap(&tail, cur_node, add_node);
    return 1;
}

2. Dequeue

int LockFreeQueue::dequeue()
{
    QueueNode* cur_node;
    int        val;
    while (1) {
        cur_node = head;
        if (cur_node->next == NULL) {
            return -1;
        }

        if (__sync_bool_compare_and_swap(&head, cur_node, cur_node->next)) {
            break;
        }
    }
    val = cur_node->next->val;

    // The historical example originally released the old head immediately here.
    // In a multithreaded lock-free structure, another thread may still hold a reference to this node,
    // so a safe memory reclamation scheme such as hazard pointers or epochs is required.
    return val;
}

This historical code also has two boundaries to note:

• GCC __sync_* is an older atomic builtin; modern C/C++ more commonly uses standard-language atomic APIs or newer __atomic_* builtins.
• Nodes cannot be released immediately after a successful dequeue as in an ordinary single-threaded linked list; it must be guaranteed that no other concurrent thread is still accessing the old node.

4. References

• Lock-free queue explanation - bilibili
• Lock-Free Queue - CoolShell
• Implementing-LockFree-Queues