CODEWITHSUNDEEP
c++multithreadingconcurrencylockinglock-free
Kasun
Kasun

Reputation: 307

Implementation of lock free stack using split reference count in the concurrency in action book

In Anthony williams's Concurrency in action book, he implements lock free stack using split reference count. After the initial load of head node.Here he use method call increase_head_count which is listed in the below code.

counted_node_ptr old_head = head.load();
increase_head_count(old_head);

void increase_head_count(counted_node_ptr& old_counter)
{
    counted_node_ptr new_counter;

    do
    {
        new_counter = old_counter;
        ++new_counter.external_count;
    }
    while (!head.compare_exchange_strong(old_counter, new_counter));

    old_counter.external_count = new_counter.external_count;
}

full implementation can be found in this link https://github.com/subjam/concurrency-in-action/blob/master/ch7/stack_ref.cpp.

my question is,if a senario occures that more than one thread try to execute pop() concurrently and all threads read head node and then only one executed untill end and others start to execute this fuction afterwards how this implementation works.

I am stuck here for quite some time, I would be really glad if anyone can help me understanding this.

Upvotes: 0

Views: 403

Answers (1)

Paul Bentley
Paul Bentley

Reputation: 343

If in the while clause, the old_counter still equals new_counter, then head is set to new_counter. This is the case for the single thread that succeeds at any one time.

For other threads accessing this method simultaneously, compare_exchange_strong() returns false causing a loop iteration. However, it will also copy head over the contents of old_counter.

This means in the next loop for these other (unsuccessful) threads, old_counter has been updated with the current contents of head.

Upvotes: 1

Related Questions