Fine-grained locking gives distinct parts of shared data separate mutexes. A queue wrapped in one mutex is simple, but only one thread can work on it at a time. To let a push at the tail overlap with a pop at the head, the implementation must expose those parts rather than treat a standard queue as one protected item. section 6.2.2 section 6.2.3
A singly linked queue appears to offer a natural split: protect its head pointer with one mutex and its tail pointer with another. The straightforward design has a catch. Removing the last item changes both pointers, and adding to an empty queue does too. Those operations would need both locks, undermining the intended separation. section 6.2.3
A permanent dummy node makes the split workable:
- Start with head and tail pointing to the dummy node. The queue is empty when those pointers are equal. section 6.2.3
- To push, prepare a value and a new node, lock the tail, put the value in the old dummy node, link the new dummy node, and advance tail. section 6.2.3
- To pop, lock the head, check it against the tail, then move head to the next node and return the old head’s value. A nonempty queue keeps a distinct dummy node at the tail. section 6.2.3
Listing 6.6. A thread-safe queue with fine-grained locking
template<typename T>
class threadsafe_queue
{
private:
struct node
{
std::shared_ptr<T> data;
std::unique_ptr<node> next;
};
std::mutex head_mutex;
std::unique_ptr<node> head;
std::mutex tail_mutex;
node* tail;
node* get_tail()
{
std::lock_guard<std::mutex> tail_lock(tail_mutex);
return tail;
}
std::unique_ptr<node> pop_head()
{
std::lock_guard<std::mutex> head_lock(head_mutex);
if(head.get()==get_tail())
{
return nullptr;
}
std::unique_ptr<node> old_head=std::move(head);
head=std::move(old_head->next);
return old_head;
}
public:
threadsafe_queue():
head(new node),tail(head.get())
{}
threadsafe_queue(const threadsafe_queue& other)=delete;
threadsafe_queue& operator=(const threadsafe_queue& other)=delete;
std::shared_ptr<T> try_pop()
{
std::unique_ptr<node> old_head=pop_head();
return old_head?old_head->data:std::shared_ptr<T>();
}
void push(T new_value)
{
std::shared_ptr<T> new_data(
std::make_shared<T>(std::move(new_value)));
std::unique_ptr<node> p(new node);
node* const new_tail=p.get();
std::lock_guard<std::mutex> tail_lock(tail_mutex);
tail->data=new_data;
tail->next=std::move(p);
tail=new_tail;
}
};
The two-mutex queue shows the key boundary: popping holds head_mutex and briefly obtains tail_mutex to check for emptiness, while pushing updates the tail side. section 6.2.3
Adding a blocking pop
A waiting consumer holds the head lock while checking whether head differs from tail. A condition-variable wait releases that lock until data is available; a producer finishes its tail update and notifies a waiter. The empty check still needs a synchronized read of tail. section 6.2.3
Smaller lock scopes can reduce contention, not eliminate synchronization costs. An operation that genuinely needs several protected items may still need several mutexes, bringing a deadlock risk. Choose lock boundaries around the data each operation actually changes, then check every operation that crosses them. section 3.2.3 section 6.2.3
