c++ - C++中的细粒度锁定队列

Question

这是 Anthony Williams 在 6.2.3 C++ 并发实战一章中介绍的细粒度锁定队列。

/*
    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();
    }
}

情况如下:有两个线程(thread1 和thread2)。 thread1 正在执行 wait_and_pop 而 thread2 正在执行 push。队列为空。

thread1 在#2 中，在data_cond.wait() 之前已经检查了head.get()!=get_tail()。这时它的CPU周期已经用完了。 线程 2 开始。

thread2 完成了push 函数并做了data_cond.notify_one()。 thread1 再次开始。

现在 thread1 开始 data_cond.wait()，但它会永远等待。

这种情况会不会发生？如果会，如何修复这个容器？<​​/p>

Answer 1

是的，OP 中描述的情况是可能的，并且会导致通知丢失。在谓词函数中注入(inject)一个很好的大时间延迟可以很容易地触发。 Here's a demonstration at Coliru .请注意程序是如何用 10 秒来完成的(wait_for 的超时长度)而不是 100 毫秒(生产者将一个项目插入队列的时间)。通知丢失。

在条件变量的设计中有一个隐含的假设，即条件状态(谓词的返回值)在关联的互斥体被锁定时不能改变。对于此队列实现而言，情况并非如此，因为 push 可以在不持有 head_mutex 的情况下更改队列的“空”。

§30.5p3 指定 wait 具有三个原子部分:

1. the release of the mutex, and entry into the waiting state;
2. the unblocking of the wait; and
3. the reacquisition of the lock.

请注意，如果有任何传递给 wait，这些都没有提到检查谓词。 §30.5.1p15 中描述了带有谓词的 wait 的行为:

Effects:

while (!pred())      wait(lock);

请注意，这里不能保证谓词检查和 wait 是自动执行的。 有一个先决条件，即 lock 已被锁定，并且它是调用线程持有的关联互斥锁。

就修复容器以避免丢失通知而言，我会将其更改为单个互斥体实现并完成它。当 push 和 pop 最终都采用相同的互斥量 (tail_mutex) 时，将其称为细粒度锁定有点牵强.