Here's a fine-grained locking queue introduced by Anthony Williams in chapter 6.2.3 C++ Concurrency in Action.
/*
pop only need lock head_mutex and a small section of tail_mutex,push only need
tail_mutex mutex.maximum container concurrency.
*/
template<typename T> class threadsafe_queue
{
private:
struct node
{
std::shared_ptr<T> data;
std::unique_ptr<node> next;
}
std::mutex head_mutex; //when change the head lock it.
std::unique_ptr<node> head;
std::mutex tail_mutex; //when change the tail lock it.
node* tail;
std::condition_variable data_cond;
node* get_tail()
{
std::lock_guard<std::mutex> tail_lock(tail_mutex);
return tail;
}
public:
/*
create a dummy node
*/
threadsafe_queue():
head(new node),tail(head.get())
{}
std::shared_ptr<T> wait_and_pop()
{
std::unique_lock<std::mutex> head_lock;
data_cond.wait(head_lock,[&]{return head.get()!=get_tail();}); //#1
std::unique_ptr<node> old_head=std::move(head);
head=std::move(old_head->next);
return old_head;
}
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);
{
std::lock_guard<std::mutex> tail_lock(tail_mutex);
tail->data=new_data;
node* const new_tail=p.get();
tail->next=std::move(p);
tail=new_tail;
}
data_cond.notify_one();
}
}
Here's the situation: There are two threads (thread1 and thread2). thread1 is doing a wait_and_pop and thread2 is doing a push. The queue is empty.
thread1 is in #2, had already checked head.get()!=get_tail() before data_cond.wait(). At this time its CPU period had run out. thread2 begins.
thread2 finished the push function and did data_cond.notify_one(). thread1 begins again.
Now thread1 begins data_cond.wait(), but it waits forever.
Would this situation possibly happen ?If so, how to get this container fixed ?