A thread-safe stack lets multiple threads push and pop values without accessing its stored data at the same time. Protecting each member function is not enough, however: the interface must also make common sequences of operations safe. section 6.2.1
Why separate top() and pop() are risky
Consider `if (!s.empty()) { value = s.top(); s.pop(); }`. Two threads can both pass the check and read the same top value before either pops it. Even if every call is individually synchronized, the calls do not form one indivisible operation. section 3.2.3
A safer interface combines retrieval and removal in `pop()`. The mutex-protected implementation locks the stack, checks whether it is empty, prepares the result, and removes the top item. An empty pop throws `empty_stack`. An earlier call to `empty()` is only a snapshot; `pop()` must check again while holding the lock. section 3.2.3 section 6.2.1
The return type matters as much as the lock:
- `pop(T&)` writes into a supplied result, but requires the stored type to support assignment. section 3.2.3
- Returning `T` by value is problematic if constructing the return value throws after the item has been removed; restricting the stack to no-throw copyable or movable types is possible but limiting. section 3.2.3
- Returning `std::shared_ptr<T>` avoids a throwing copy of the result, at the cost of managing an allocated object. section 3.2.3
Listing 6.1. A class definition for a thread-safe stack
#include <exception>
struct empty_stack: std::exception
{
const char* what() const throw();
};
template<typename T>
class threadsafe_stack
{
private:
std::stack<T> data;
mutable std::mutex m;
public:
threadsafe_stack(){}
threadsafe_stack(const threadsafe_stack& other)
{
std::lock_guard<std::mutex> lock(other.m);
data=other.data;
}
threadsafe_stack& operator=(const threadsafe_stack&) = delete;
void push(T new_value)
{
std::lock_guard<std::mutex> lock(m);
data.push(std::move(new_value)); #1
}
std::shared_ptr<T> pop()
{
std::lock_guard<std::mutex> lock(m);
if(data.empty()) throw empty_stack(); #2
std::shared_ptr<T> const res(
std::make_shared<T>(std::move(data.top()))); #3
data.pop(); #4
return res;
}
void pop(T& value)
{
std::lock_guard<std::mutex> lock(m);
if(data.empty()) throw empty_stack();
value=std::move(data.top()); #5
data.pop(); #6
}
bool empty() const
{
std::lock_guard<std::mutex> lock(m);
return data.empty();
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":22,\"ch\":58},{\"line\":22,\"ch\":60}],[{\"line\":27,\"ch\":58},{\"line\":27,\"ch\":60}],[{\"line\":29,\"ch\":58},{\"line\":29,\"ch\":60}],[{\"line\":30,\"ch\":58},{\"line\":30,\"ch\":60}],[{\"line\":37,\"ch\":58},{\"line\":37,\"ch\":60}],[{\"line\":38,\"ch\":58},{\"line\":38,\"ch\":60}]]"}
!@%STYLE%@!
Inspect the mutex-protected class: `std::lock_guard` scopes access to the underlying `std::stack`, while `pop()` checks for emptiness under that lock. section 6.2.1
The mutex also protects `push()` and copying the stack. Locking occurs before a member function changes the data, and `std::lock_guard` releases the mutex when the function exits, including when an exception occurs. section 6.2.1
A lock-free version uses an atomic head pointer and compare-and-exchange to push or remove nodes. It still needs an empty-stack check and a safe result representation. Allocating the value during `push()` allows `pop()` to return a `std::shared_ptr<T>` without allocating then; the initial version nevertheless leaks removed nodes, so safe return does not complete the implementation. 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
}
};
Compare the lock-free `pop()` with the locked version: it checks for a null head and returns a shared pointer, but does not reclaim the removed node. section 7.2.1
Neither version waits for an item to arrive. Throwing on an empty stack would force a consumer that needs to wait to retry, wasting processing time; waiting requires additional synchronization. section 3.4
