A lock-free data structure lets threads access shared data without acquiring a mutex. It must permit concurrent access, though not necessarily concurrent use of every operation. Its key progress guarantee is that if one thread is suspended midway through an operation, other threads can still complete theirs. section 7.0 section 7.1.2
Many lock-free operations use compare/exchange in a retry loop. If another thread changed the data, the operation retries with the new state. A retry loop can still be lock-free: if competing threads stopped, the compare/exchange could succeed. A loop that merely waits for another thread is instead a spin lock. Lock-free progress does not guarantee that every thread finishes; repeated interference can starve one thread. Wait-free structures avoid that starvation. section 7.1.2
A queue with one producer and one consumer
An initial queue uses atomic head and tail pointers and a dummy node. pop() returns empty when head equals tail; otherwise, it advances head to the next node. Its single-producer, single-consumer restriction matters: this version does not establish that two producers can safely push at once. section 7.2.6 section 7.1.2
Listing 7.14. A single-producer, single-consumer lock-free queue
template<typename T>
class lock_free_queue
{
private:
struct node
{
std::shared_ptr<T> data;
node* next;
node():
next(nullptr)
{}
};
std::atomic<node*> head;
std::atomic<node*> tail;
node* pop_head()
{
node* const old_head=head.load();
if(old_head==tail.load()) #1
{
return nullptr;
}
head.store(old_head->next);
return old_head;
}
public:
lock_free_queue():
head(new node),tail(head.load())
{}
lock_free_queue(const lock_free_queue& other)=delete;
lock_free_queue& operator=(const lock_free_queue& other)=delete;
~lock_free_queue()
{
while(node* const old_head=head.load())
{
head.store(old_head->next);
delete old_head;
}
}
std::shared_ptr<T> pop()
{
node* old_head=pop_head();
if(!old_head)
{
return std::shared_ptr<T>();
}
std::shared_ptr<T> const res(old_head->data); #2
delete old_head;
return res;
}
void push(T new_value)
{
std::shared_ptr<T> new_data(std::make_shared<T>(new_value));
node* p=new node; #3
node* const old_tail=tail.load(); #4
old_tail->data.swap(new_data); #5
old_tail->next=p; #6
tail.store(p); #7
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":17,\"ch\":55},{\"line\":17,\"ch\":57}],[{\"line\":45,\"ch\":56},{\"line\":45,\"ch\":58}],[{\"line\":52,\"ch\":56},{\"line\":52,\"ch\":58}],[{\"line\":53,\"ch\":56},{\"line\":53,\"ch\":58}],[{\"line\":54,\"ch\":56},{\"line\":54,\"ch\":58}],[{\"line\":55,\"ch\":56},{\"line\":55,\"ch\":58}],[{\"line\":56,\"ch\":56},{\"line\":56,\"ch\":58}]]"}
!@%STYLE%@!
Inspect the head–tail empty check and the head update in the single-producer, single-consumer queue. section 7.2.6
Atomic operations also control visibility. A thread must publish changes in an order that lets other threads see a coherent data structure without data races. Sequentially consistent ordering is a straightforward starting point; later designs may use acquire, release, or relaxed ordering where justified. Removing mutex calls from C++ code is not, by itself, proof that its atomics use no internal locks: only std::atomic_flag is guaranteed not to do so. section 7.2 section 7.4
Check more than the atomic update when designing or selecting a structure:
- Account for node lifetime. Lock-free memory management is harder than in lock-based structures; a reference-counted queue tracks references before reclaiming nodes. section 7.2.6 section 7.4
- Watch for an operation that waits on unfinished work. Helping another thread complete that work can avoid a wait loop. section 7.2.6 section 7.4
- Measure the whole implementation. Allocator behavior can destroy scalability, and a simple lock-based structure may be preferable on some platforms. section 7.2.6 section 7.2
