An operation is wait-free if every thread completes it in a bounded number of steps, regardless of what other threads are doing. This is a per-thread progress guarantee. section 7.1.1
The progress guarantees differ in how much concurrent activity they tolerate:
- Obstruction-free guarantees completion when all other threads are paused. section 7.1.1
- Lock-free guarantees that some thread completes an operation within a bounded number of steps, but an individual thread may starve. section 7.1.1 section 7.1.2
- Wait-free guarantees bounded completion for every thread, even while other threads operate. section 7.1.1
A lock-free stack illustrates the distinction: its push() and pop() operations retry compare-and-exchange loops that could keep failing, so the stack is not wait-free. section 7.2.1
Listing 7.3. A lock-free stack that leaks nodes
template<typename T>
class lock_free_stack
{
private:
struct node
{
std::shared_ptr<T> data; #1
node* next;
node(T const& data_):
data(std::make_shared<T>(data_)) #2
{}
};
std::atomic<node*> head;
public:
void push(T const& data)
{
node* const new_node=new node(data);
new_node->next=head.load();
while(!head.compare_exchange_weak(new_node->next,new_node));
}
std::shared_ptr<T> pop()
{
node* old_head=head.load();
while(old_head && #3
!head.compare_exchange_weak(old_head,old_head->next));
return old_head ? old_head->data : std::shared_ptr<T>(); #4
}
};
Inspect the stack’s push() and pop() loops to see the retries behind its lock-free, but not wait-free, guarantee. section 7.2.1
