提问人:jdav22 提问时间:10/13/2023 更新时间:10/13/2023 访问量:64
具有虚拟节点的单线程队列如何促进并发?
How does a single-threaded queue with a dummy node facilitate concurrency?
问:
在 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() 现在只接触节点而不是节点(所以当我们去添加互斥锁时,我们只需要头节点的互斥锁)。tail
head
但是,如果队列是空的,并且发生了第一次推送,这是怎么回事呢?我的理解是,如果设置为 ,它们持有相同的指针,并且在第一次更新时,头部指针也会受到影响。tail
head.get()
tail->data
事实上,在我的打印语句中,当我们尝试两次推送到队列时,我们会看到以下内容:
0x55c37e5fa2701
0x55c37e5fa2701
0x55c37e5fa2b01
0x55c37e5fa2b02
显示头部和尾部在第一次推送时共享一个地址,但在第二次推送时不再共享地址。
我是否在某种程度上误解了这一点,或者实际上在推送到空队列时是一样的?head
tail
答:
0赞
jdav22
10/13/2023
#1
(找出了我自己问题的答案)
引入虚拟节点可以解决该问题,因为:
- 如果队列的元素为零,则将立即返回,并且从不尝试访问 。因此,当它们指向相同的值时,永远不会同时访问。
try_pop()
head -> next
head->next
tail->next
- 如果队列有一个元素,并且现在是单独的元素。 是队列中的第一个元素,并且是下一个元素,即虚拟节点。同样,当 和 指向相同的值时,不存在同时访问它们的情况。
head
tail
head
tail
head->next
tail->next
评论
tail->data
push
pop
tail