In "C++: Concurrency in Action", why use reference counting/hazard variables instead of std::atomic<std::shared_ptr>?

Question

I'm learning about lock-free data structures from C++: Concurrency in Action, a textbook by Anthony Williams. The running example is a lock-free stack.

Williams uses the following pseudocode for pop (p. 186):

1 Read the current value of head.
2 Read head->next.
3 Set head to head->next.
4 Return the data from the retrieved node.
5 Delete the retrieved node.

The code for this WITHOUT step 5 is:

std::shared_ptr<T> pop() {
    node* old_head=head.load();
    while(old_head &&
        !head.compare_exchange_weak(old_head,old_head->next));
    return old_head ? old_head->data : std::shared_ptr<T>();
}

He says, "If one thread then proceeds all the way through to step 5 before the other gets to step 2, the second thread will be dereferencing a dangling pointer." This makes sense to me. He then goes on to propose several solutions for the issue, such as reference counting/garbage collection.

My question is: Why can't we just wrap the nodes in atomic smart pointers? Wouldn't they do all the resource cleanup for us?

Answer 1

You can't use an atomic smart pointer if you want to implement a lock-free stack. The atomic smart pointer uses locks.

Answer 2

Not read the book but definitely this code has the problem of dangling pointer and ABA problem. You are right about the usage of atomic<shared_ptr>, which should take care of ABA and resource management. You can refer this paper from Herb Sutter for detailed explanation. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4058.pdf