具有虚拟节点的单线程队列如何促进并发?

How does a single-threaded queue with a dummy node facilitate concurrency?

提问人:jdav22 提问时间:10/13/2023 更新时间:10/13/2023 访问量:64

问:

在 Anthony Williams 的 C++ Concurrency in Action 一书中,显示了以下单线程队列:

template<typename T>
class queue {
public:
    queue() : 
        head{new node}, tail{head.get()} {}
    

    queue(const queue& other)=delete;
    queue& operator=(const queue& other)=delete;

    std::shared_ptr<T> try_pop() {
        if(head.get()==tail) {
            return std::shared_ptr<T>();
        }
        
        std::shared_ptr<T> const res(head->data);
        std::unique_ptr<node> old_head=std::move(head);
        head=std::move(old_head->next);
        return res;
    }

    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);

        tail->data=new_data;
        std::cout << tail << *(head->data) << '\n';
        std::cout << tail << *(tail->data) << '\n';

        node* const new_tail=p.get();
        tail->next=std::move(p);
        tail=new_tail;
    }

    struct node {
        std::shared_ptr<T> data;
        std::unique_ptr<node> next;
    };

    std::unique_ptr<node> head;
    node* tail;
};

这个队列使用一个虚拟节点作为头部和尾部,并说这样做的好处是 push() 现在只接触节点而不是节点(所以当我们去添加互斥锁时,我们只需要头节点的互斥锁)。tailhead

但是,如果队列是空的,并且发生了第一次推送,这是怎么回事呢?我的理解是,如果设置为 ,它们持有相同的指针,并且在第一次更新时,头部指针也会受到影响。tailhead.get()tail->data

事实上,在我的打印语句中,当我们尝试两次推送到队列时,我们会看到以下内容:

0x55c37e5fa2701
0x55c37e5fa2701
0x55c37e5fa2b01
0x55c37e5fa2b02

显示头部和尾部在第一次推送时共享一个地址,但在第二次推送时不再共享地址。

我是否在某种程度上误解了这一点,或者实际上在推送到空队列时是一样的?headtail

C++(英语:C++) 列表 多线程 并发 队列

评论

0赞 Solomon Slow 10/13/2023
回复,“在第一次更新时,头部指针也会受到影响。不。该操作从不更改头部指针。它更改头部指针指向的节点,但从不更改指针本身。同样,该操作从不更改指针。tail->datapushpoptail

答:

0赞 jdav22 10/13/2023 #1

(找出了我自己问题的答案)

引入虚拟节点可以解决该问题,因为:

  • 如果队列的元素为零,则将立即返回,并且从不尝试访问 。因此,当它们指向相同的值时,永远不会同时访问。try_pop()head -> nexthead->nexttail->next
  • 如果队列有一个元素,并且现在是单独的元素。 是队列中的第一个元素,并且是下一个元素,即虚拟节点。同样,当 和 指向相同的值时,不存在同时访问它们的情况。headtailheadtailhead->nexttail->next