A lockless, or lock-free, technique lets concurrent threads make progress without waiting for one particular thread to finish. Its guarantee is collective: when threads keep taking steps, at least one operation completes within a bounded number of steps. A thread suspended midway through an operation must not prevent the others from completing theirs. section 7.1.1 section 7.1.2
Related guarantees answer different questions:
- Nonblocking means no blocking call is made; it does not establish lock-free progress. A spin lock loops on an atomic flag but still permits only one thread to hold its mutex. section 7.1.1
- Obstruction-free means a thread completes in bounded steps if every other thread is paused. section 7.1.1
- Wait-free means every thread completes in bounded steps despite other threads’ activity. Lock-free alone permits one thread to starve while others succeed. section 7.1.1 section 7.1.2
A common pattern reads shared state, prepares a change, then uses compare/exchange to publish it. If another thread changed the state first, the operation retries. Those retries can support lock-free progress because a failed attempt can reflect another thread’s successful change; merely looping on an atomic operation does not make an algorithm lock-free. Check the atomic type’s implementation too: `is_lock_free()` detects an internal lock, while C++17’s `is_always_lock_free` reports a compile-time guarantee across supported target hardware. `std::atomic_flag` is guaranteed lock-free, but building a spin-lock mutex from it does not make the protected data structure lock-free. section 7.1.2 section 5.2.1 section 5.2.2 section 7.1.1
Listing 7.2. Implementing push() without locks
template<typename T>
class lock_free_stack
{
private:
struct node
{
T data;
node* next;
node(T const& data_): #1
data(data_)
{}
};
std::atomic<node*> head;
public:
void push(T const& data)
{
node* const new_node=new node(data); #2
new_node->next=head.load(); #3
while(!head.compare_exchange_weak(new_node->next,new_node)); #4
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":8,\"ch\":71},{\"line\":8,\"ch\":73}],[{\"line\":16,\"ch\":71},{\"line\":16,\"ch\":73}],[{\"line\":17,\"ch\":71},{\"line\":17,\"ch\":73}],[{\"line\":18,\"ch\":71},{\"line\":18,\"ch\":73}]]"}
!@%STYLE%@!
In this stack push, `new_node->next` first records the observed head. `compare_exchange_weak` attempts to replace that head with the new node; on failure, it updates the expected head and the loop retries. The stack therefore need not hold a mutex while another thread pushes. section 7.2.1
Removing a node is harder. Two threads can read the same head; if one removes and deletes it before the other reads its `next` pointer, the second dereferences a dangling pointer. Compare/exchange prevents both threads from claiming the same node, but does not by itself solve reclamation. An initial stack version avoids deletion and consequently leaks nodes. Lockless design must preserve data-structure invariants through indivisible changes as well as satisfy its progress guarantee. section 7.2.1 section 3.1.2
