Lock-Free Programming

Lock free programming can be understood as a system which always makes progress when any thread is scheduled, regardless of any potential delays or suspensions. Importantly, the condition of making progress does not imply that every individual thread completes in a finite number of steps, as this stronger criterion is known as wait freedom, which is significantly less common in practice.

The majority of lock free codebases that are encountered rely on compare and exchange loops. These loops are considered lock free as long as a minimum of one thread can successfully execute its compare and exchange.

• Blocking: This is when a single thread has the potential to block all other threads; a clear example being a normal mutex.

• Obstruction free: Any thread, when allowed to proceed in isolation for a sufficient amount of time, will eventually terminate.

• Lock free: Some thread will always eventually terminate, regardless of whether other threads are running concurrently.

• Wait free: All threads, irrespective of their interaction with any others, will always terminate in a bounded number of their individual steps.

It is indeed possible to construct wait free data structures, however, they are generally difficult to implement and often have a slower throughput rate than a well written lock free structure or even a properly locked design in real world usage. Wait freedom is something that I almost never consider first when designing a data structure.

A commonly encountered example here is a linked list based stack which simply updates the head of the list using compare and exchange on its value:

#include <atomic>
#include <iostream>
#include <thread>
#include <vector>

struct Node
{
    int data;
    Node* next;
};

class LockFreeStack
{
    std::atomic<Node*> head{nullptr};

public:
    void push(int value)
    {
        Node* new_node = new Node{value, nullptr};
        Node* old_head = head.load(std::memory_order_relaxed);

        do
        {
            new_node->next = old_head;
        }
        while (!head.compare_exchange_weak(
            old_head,
            new_node,
            std::memory_order_release,
            std::memory_order_relaxed
        ));
    }

    bool pop(int& result)
    {
        Node* old_head = head.load(std::memory_order_relaxed);

        do
        {
            if (old_head == nullptr)
            {
                return false;
            }
        }
        while (!head.compare_exchange_weak(
            old_head,
            old_head->next,
            std::memory_order_acquire,
            std::memory_order_relaxed
        ));

        result = old_head->data;

        // The node is deliberately not deleted in this example.
        return true;
    }
};

LockFreeStack stack;

void producer()
{
    for (int i = 0; i < 1000; ++i)
    {
        stack.push(i);
    }
}

void consumer()
{
    int value;

    for (int i = 0; i < 1000; ++i)
    {
        while (!stack.pop(value))
        {
        }
    }
}

int main()
{
    std::jthread t1{producer};
    std::jthread t2{consumer};
    std::jthread t3{producer};
    std::jthread t4{consumer};
}

The push simply allocates a node, and then iteratively attempts to set the head value to the new node value. A compare_exchange_weak with release semantics ensures that the new node values are visible to any subsequent thread performing an acquire operation on that node.

Likewise, the pop operation loads the head value, checks if the list is empty, and then sets the head pointer to the value of the next pointer. Acquire semantics on this particular operation ensure that we are safe in viewing the data on the removed node.

This code is lock free. As long as some thread is able to continue running, either push or pop will eventually complete successfully.

However, it is not wait free, as a thread could technically starve if it were constantly interrupted and losing its attempt to update the head pointer.

Notice that all allocated nodes are lost as they have been successfully removed from the stack. This is an oversimplification.

In normal circumstances, if a node has been popped then there may still be some other thread with a pointer to it and waiting for its turn to perform a compare and exchange operation. This problem is a real world scenario related to the ABA problem.

Safely solving this reclamation problem is usually significantly more complex than the lock free algorithm itself. Hazard pointers, epoch based reclamation, or RCU style techniques are typical solutions to this issue and until one of these techniques is in place, the lock free data structure itself is incomplete.

Lock free algorithms and data structures are suitable for usage in scenarios such as:

• When the critical section required is exceptionally small, for example, only containing a few loads and a compare and exchange operation.

• When it is essential that the system continues making forward progress, even if a particular thread is descheduled.

• When creating a low level primitive that is expected to perform under high contention.

They are hardly ever the go to technique when designing the average application. A std::mutex controlling access to a std::deque or std::vector is far less complicated to work with and to reason about, and is often even quicker after accounting for the necessary logic to correctly perform safe memory reclamation.