pop()
函数。std::shared_ptr<T> pop() {
std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
node* old_head = head.load(); // #1
do {
node* temp;
do {
temp = old_head;
hp.store(old_head); // #2
old_head = head.load(); // #3
} while (old_head != temp); // #4
} while (old_head &&
!head.compare_exchange_strong(old_head, old_head->next));
hp.store(nullptr);
// ...
}
这本书解释了内部循环的作用:
为确保在读取旧的head指针#1和设置危险指针#2之间节点没有被删除,必须在while循环中执行此操作。在此期间,没有其他线程知道您正在访问此特定节点。幸运的是,如果旧的head节点将被删除,则head本身必须已更改,因此您可以检查并继续循环,直到知道head指针仍具有与您设置危险指针相同的值#4。
根据pop的实现,如果另一个线程在#1和#2之间通过pop删除头节点,则head将被修改为新节点。
我困惑的是,其他线程对
head
的修改能否及时被当前线程看到?例如,如果head
的新值尚未传播到当前线程,则#1
和#3
仍将读取相同的值(旧值),导致内部while
循环退出,进而外部while
循环访问old_head->next
,导致未定义行为。我在stackoverflow上搜索了一些答案。例如,this answer说:
默认的内存顺序
std::memory_order_seq_cst
为所有变量提供了一个单一的全局总序。这并不意味着您不能获得过期的值,但它确实意味着您获得的值取决于您的操作在该总序中的位置。
这篇评论 说:
每个原子变量都有自己的修改顺序,所有线程都可以达成一致,但是这只序列化了修改,而不是读取。涉及读取的一致性要求仅保证如果你在修改顺序中看到一个值,你就无法看到更早的值。
但是cppreference说:
从原子变量
M
加载的每个memory_order_seq_cst
操作B
都观察到以下之一:
M
的最后一个操作A
的结果,在单个完全顺序中出现在B
之前...
那么我的问题到底应该得到什么答案呢?
另外,如果使用较弱的顺序(如释放-获取或松散顺序),上述问题会出现吗?
这是
pop
的代码:std::shared_ptr<T> pop() {
std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
node* old_head = head.load(); // #1
do {
node* temp;
do {
temp = old_head;
hp.store(old_head); // #2
old_head = head.load(); // #3
} while (old_head != temp); // #4
} while (old_head &&
!head.compare_exchange_strong(old_head, old_head->next));
hp.store(nullptr); // Clear hazard pointer once you're finished
std::shared_ptr<T> res;
if (old_head) {
res.swap(old_head->data);
if (outstanding_hazard_pointers_for(old_head)) // Check for hazard pointers referencing a node before you delete it.
reclaim_later(old_head);
else
delete old_head;
delete_nodes_with_no_hazards();
}
return res;
}
pop()
函数弹出由head
指向的节点,并在没有风险指针指向它时释放它。通过compare_exchange_strong
实现修改head
。
hp
必须保证与它的值相同。”但是何时呢?我们实际上只能观察到某些hp
的加载和某些head
的加载是否返回相同的值。这两个负载不能同时进行,因此了解它们相对于彼此的排序方式至关重要。 - Nate Eldredgeold_head
时,我们必须确保hp
的值与它相同,而不是head
而是old_head
,因为old_head
是当前线程要删除的节点。但在我看来,这似乎偏离了我的问题。 - Plutohead
,则可能会出现#1和#3都返回相同值的情况。但如果是这样,则W必须在按顺序一致的总排序中后于#3,并因此也在#2之后。这将使我们能够推断出另一个线程不会释放我们在#1和#3处加载的指针。 - Nate Eldredge