Helping lets a thread finish part of an operation started by another thread. In a lock-free queue, a push may place data in the tail node but stall before linking a new dummy node and advancing the tail. If other pushers merely wait for that work, they can burn CPU cycles while making no progress; the queue is effectively locked. section 7.2.6
A waiting pusher can complete the pending update:
- Use an atomic compare-and-exchange to set the tail node’s next pointer to a new dummy node. Dummy nodes are interchangeable, so the helper’s node can serve instead of the original pusher’s. section 7.2.6
- Try to advance tail with a compare-and-exchange loop, but only while it still refers to the original node. If another thread has advanced it, stop trying and repeat the queue operation. section 7.2.6
- Make next atomic and load it atomically in pop(), which must read the link that pushers can now establish concurrently. section 7.2.6
Helping replaces dependence on one stalled thread with work another thread can complete. It does not remove the need to manage node references: advancing tail or discovering that someone else advanced it leads to different reference-release paths. section 7.2.6
Listing 7.22. A sample push() with helping for a lock-free queue
template<typename T>
class lock_free_queue
{
private:
void set_new_tail(counted_node_ptr &old_tail, #1
counted_node_ptr const &new_tail)
{
node* const current_tail_ptr=old_tail.ptr;
while(!tail.compare_exchange_weak(old_tail,new_tail) && #2
old_tail.ptr==current_tail_ptr);
if(old_tail.ptr==current_tail_ptr) #3
free_external_counter(old_tail); #4
else
current_tail_ptr->release_ref(); #5
}
public:
void push(T new_value)
{
std::unique_ptr<T> new_data(new T(new_value));
counted_node_ptr new_next;
new_next.ptr=new node;
new_next.external_count=1;
counted_node_ptr old_tail=tail.load();
for(;;)
{
increase_external_count(tail,old_tail);
T* old_data=nullptr;
if(old_tail.ptr->data.compare_exchange_strong( #6
old_data,new_data.get()))
{
counted_node_ptr old_next={0};
if(!old_tail.ptr->next.compare_exchange_strong( #7
old_next,new_next))
{
delete new_next.ptr; #8
new_next=old_next; #9
}
set_new_tail(old_tail, new_next);
new_data.release();
break;
}
else #10
{
counted_node_ptr old_next={0};
if(old_tail.ptr->next.compare_exchange_strong( #11
old_next,new_next))
{
old_next=new_next; #12
new_next.ptr=new node; #13
}
set_new_tail(old_tail, old_next); #14
}
}
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":4,\"ch\":68},{\"line\":4,\"ch\":70}],[{\"line\":41,\"ch\":68},{\"line\":41,\"ch\":70}],[{\"line\":44,\"ch\":68},{\"line\":44,\"ch\":70}],[{\"line\":47,\"ch\":68},{\"line\":47,\"ch\":70}],[{\"line\":48,\"ch\":68},{\"line\":48,\"ch\":70}],[{\"line\":50,\"ch\":68},{\"line\":50,\"ch\":70}],[{\"line\":8,\"ch\":68},{\"line\":8,\"ch\":70}],[{\"line\":10,\"ch\":68},{\"line\":10,\"ch\":70}],[{\"line\":11,\"ch\":68},{\"line\":11,\"ch\":70}],[{\"line\":13,\"ch\":68},{\"line\":13,\"ch\":70}],[{\"line\":27,\"ch\":68},{\"line\":27,\"ch\":70}],[{\"line\":31,\"ch\":68},{\"line\":31,\"ch\":70}],[{\"line\":34,\"ch\":68},{\"line\":34,\"ch\":70}],[{\"line\":35,\"ch\":68},{\"line\":35,\"ch\":70}],[{\"line\":41,\"ch\":68},{\"line\":41,\"ch\":71}],[{\"line\":44,\"ch\":68},{\"line\":44,\"ch\":71}],[{\"line\":47,\"ch\":68},{\"line\":47,\"ch\":71}],[{\"line\":48,\"ch\":68},{\"line\":48,\"ch\":71}],[{\"line\":50,\"ch\":68},{\"line\":50,\"ch\":71}]]"}
!@%STYLE%@!
The sample push() includes a set_new_tail() helper: it retries the tail update while the original node remains current, then handles the corresponding reference cleanup. section 7.2.6
