《C++ Concurrency in Action》7.15节无锁队列push函数竞态疑问

问题核心 #

你疑惑的点在于：修改前的pop()会检查head和tail是否指向同一节点，清单7.15的push()仅在最后一步更新tail，似乎pop()不会操作未完成入队的节点。但实际竞态的根源在于多线程下，push()加载的old_tail可能在解引用前被pop()线程删除，具体原因如下：

竞态条件的触发时序 #

假设存在两个push线程（P1、P2）和一个pop线程（P3），结合代码逻辑看具体执行顺序：

1. 初始状态：队列的tail指向节点X（此时X是尾部占位节点）。
2. P1执行push()：执行标记1，通过tail.load()加载得到节点X的指针。
3. P2抢先完成push()：
   • 同样加载tail得到X；
   • 成功通过compare_exchange_strong将X的data设置为新值；
   • 更新X的next为新的占位节点Y；
   • 执行标记3，将tail更新为Y。此时X不再是尾部节点，而是队列中带有有效数据的普通节点。
4. P3执行pop()：
   • pop_head()加载head发现指向X，加载tail指向Y，X≠Y；
   • 将head更新为X->next（即Y）；
   • 返回X并在pop()中delete X，释放X的内存。
5. P1继续执行push()：此时P1仍持有已被释放的X的指针，尝试解引用X->data执行CAS操作——这一步会触发未定义行为，因为X的内存已经被回收。

关键原因总结 #

• push()中加载old_tail（标记1）和后续解引用操作（标记2）不是原子操作，两者之间存在可被其他线程利用的时间窗口；
• 其他push线程可以先完成对old_tail的修改并更新tail，使old_tail从尾部占位节点变为队列中的普通数据节点；
• 此时pop()线程会将该节点视为可弹出的有效节点，将其移除并释放内存，而持有该节点指针的push线程后续的解引用操作就会访问已释放的内存空间。

内容的提问来源于stack exchange，提问作者RuiXin Lin