concept compare_exchange_strong() in category c++

This is an excerpt from Manning's book C++ Concurrency in Action, Second Edition. Login to get full access to this book.

This new operation is called compare-exchange, and it comes in the form of the compare_exchange_weak() and compare_exchange_strong() member functions. The compare-exchange operation is the cornerstone of programming with atomic types; it compares the value of the atomic variable with a supplied expected value and stores the supplied desired value if they’re equal. If the values aren’t equal, the expected value is updated with the value of the atomic variable. The return type of the compare-exchange functions is a bool, which is true if the store was performed and false otherwise. The operation is said to succeed if the store was done (because the values were equal), and fail otherwise; the return value is true for success, and false for failure.

First off, you’ve moved the loop that sets the hazard pointer inside the outer loop for reloading old_head if the compare/exchange fails 1. You’re using compare_exchange_strong() here because you’re doing work inside the while loop: a spurious failure on compare_exchange_weak() would result in resetting the hazard pointer unnecessarily. This ensures that the hazard pointer is correctly set before you dereference old_head. Once you’ve claimed the node as yours, you can clear your hazard pointer 2. If you did get a node, you need to check the hazard pointers belonging to other threads to see if they reference it 3. If so, you can’t delete it yet, so you must put it on a list to be reclaimed later 4; otherwise, you can delete it right away 5. Finally, you put in a call to check for any nodes for which you had to call reclaim_later(). If there are no longer any hazard pointers referencing those nodes, you can safely delete them 6. Any nodes for which there are still outstanding hazard pointers will be left for the next thread that calls pop().

What about the pop() code? In order to get the happens-before relationship you need, you must have an operation that’s std::memory_order_acquire or stronger before the access to next. The pointer you dereference to access the next field is the old value read by the compare_exchange_strong() in increase_head_count(), so you need the ordering on that if it succeeds. As with the call in push(), if the exchange fails, you just loop again, so you can use relaxed ordering on failure:

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,
        std::memory_order_acquire,std::memory_order_relaxed));
    old_counter.external_count=new_counter.external_count;
}

If the compare_exchange_strong() call succeeds, you know that the value read had the ptr field set to what’s now stored in old_counter. Because the store in push() was a release operation, and this compare_exchange_strong() is an acquire operation, the store synchronizes with the load and you have a happens-before relationship. Consequently, the store to the ptr field in the push() happens before the ptr->next access in pop(), and you’re safe.

A second option is to make the data pointer atomic and set that with a call to compare/exchange. If the call succeeds, this is your tail node, and you can safely set the next pointer to your new node and then update tail. If the compare/exchange fails because another thread has stored the data, you loop around, reread tail, and start again. If the atomic operations on std::shared_ptr<> are lock-free, you’re home free. If not, you need an alternative. One possibility is to have pop() return std::unique_ptr<> (after all, it’s the only reference to the object) and store the data as a plain pointer in the queue. This would allow you to store it as std::atomic<T*>, which would then support the necessary compare_exchange_strong() call. If you’re using the reference-counting scheme from listing 7.12 to handle multiple threads in pop(), push() now looks like this.