解释Michael&Scott无锁队列alorigthm

Question

我正在研究迈克尔和斯科特的无锁队列算法,并尝试用C++实现它.

但我在我的代码中制作了一个竞赛,并认为算法中可能存在竞争.

我在这里阅读了论文: 简单,快速,实用的非阻塞和阻塞并发队列算法 和原始的Dequeue伪代码如下:

dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1:   loop                          // Keep trying until Dequeue is done
D2:      head = Q->Head             // Read Head
D3:      tail = Q->Tail             // Read Tail
D4:      next = head.ptr->next      // Read Head.ptr->next
D5:      if head == Q->Head         // Are head, tail, and next consistent?
D6:         if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
D7:            if next.ptr == NULL  // Is queue empty?
D8:               return FALSE      // Queue is empty, couldn't dequeue
D9:            endif
                // Tail is falling behind.  Try to advance it
D10:            CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11:         else                    // No need to deal with Tail
               // Read value before CAS
               // Otherwise, another dequeue might free the next node
D12:            *pvalue = next.ptr->value
               // Try to swing Head to the next node
D13:            if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14:               break             // Dequeue is done.  Exit loop
D15:            endif
D16:         endif
D17:      endif
D18:   endloop
D19:   free(head.ptr)                // It is safe now to free the old node
D20:   return TRUE                   // Queue was not empty, dequeue succeeded

在我看来,比赛是这样的:

1. 线程1前进到D3然后停止.
2. 线程2前进到D3,读取与线程1相同的头部.
3. 线程2幸运地一直推进到D20,在D19它释放了head.ptr
4. 线程1继续并前进到D4,尝试读取head.ptr->next,但是head.ptr已经被线程1释放,崩溃发生.

我的C++代码总是在D4上为Thread 1崩溃.

任何人都可以指出我的错误并给出一些解释吗？

Answer 1

谢谢,非常有趣的主题!它肯定看起来像一个bug,但是该论文的作者之一声称他们的free()不是正常的free()我们都生活在一起,但是有些魔法free(),所以没有bug.太棒了.

见http://blog.shealevy.com/2015/04/23/use-after-free-bug-in-maged-m-michael-and-michael-l-scotts-non-blocking-concurrent-queue-algorithm /

希望没有经过深入分析就没有人投入生产.

Answer 2

这实际上是自 MS 队列的作者之一 Maged Michael 引入危险指针 [1] 以来一直在探索的非阻塞内存回收问题。

危险指针允许线程保留块，以便其他线程在完成之前不会真正回收它们。然而，这种机制会导致不平凡的性能开销。

还有许多基于纪元的回收变体，例如 RCU [2,3]，以及最近的基于间隔的回收 (IBR) [4]。它们通过保留时代来避免使用后释放，并且比危险指针更快。据我所知，基于 epoch 的回收被广泛用于处理这个问题。

您可以查看下面提到的这些论文以了解更多详细信息。的纸为基础的区间内存回收具有所讨论的许多背景。

这是非阻塞数据结构中的一个普遍问题，我们通常不认为它是数据结构本身的错误——毕竟它只发生在使用手动内存管理的语言中，如 C/C++ 而不是那些Java（顺便说一句，Michael & Scott Queue 多年来一直被Java 并发采用）。

参考：

[1]危险指针：无锁对象的安全内存回收，Maged M. Michael，IEEE 并行和分布式系统交易，2004 年。

[2] 无 锁同步的内存回收性能，Thomas E. Hart 等人，并行和分布式计算杂志，2007 年。

[3] 阅读复制更新，Paul E. McKenney 等人，渥太华 Linux 研讨会，2002 年。

[4] Interval-Based Memory Reclamation，Haosen Wen 等，第 23 届 ACM SIGPLAN 并行编程原理与实践研讨会论文集 (PPoPP)，2018 年。