解释 Michael & Scott 无锁队列 alorigthm

Question

我正在学习Michael＆amp;Scott的无锁队列算法，并尝试在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上释放了头。ptr
4. 线程1继续前进到D4，试图读取head.ptr->next，但是由于head.ptr已经被线程1释放，因此发生了崩溃。

和我的C 代码确实总是在d4的线程1中崩溃。

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

Answer 1

谢谢，非常有趣的主题！它绝对看起来像是一个错误，但是本文的作者之一断言，他们的免费（）不是我们所有人都生活的正常（），而是一些魔术免费（），因此没有错误。很棒。

请参阅https://web.archive.org/web/2019090505090735/http://blog..shealevy.com/2015/2015/04/23/use-after-after-ferre-free-free-bug-in-mage-mage-mage-mage-maged-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael-michael---和Michael-l-Scotts-Non-Blocking-Concurrent-Queue-Algorithm/

希望没有人在没有彻底分析的情况下将其投入生产。

Answer 2

这实际上是自列格德·迈克尔（Maged Michael）（Queue女士的作者之一Maged Michael）引入危险指针[1]以来，它正在探索数年的非阻滞记忆填海问题[1]。

危险指针允许线程保留块，以便在完成之前不会真正收回它们。但是，这种机制会产生非平凡的性能开销。

也有许多基于时代的填充变体，例如RCU [2,3]，以及最近基于间隔的回收（IBR）[4]。他们避免通过预订时代的使用后避免使用，并且比危险指针更快。据我所知，基于时期的填海被广泛采用以解决这个问题。

您可以查看以下引用的这些论文以获取更多详细信息。基于间隔的记忆填海的论文有很多背景。

这是非阻止数据结构中的一个一般问题，我们通常不将其视为数据结构本身的错误 - 毕竟它仅在语言中使用手动内存管理，例如C/C ，但不在语言中在Java之类的人（顺便说一句，Michael＆amp; Scott Queue多年来一直在Java并发中采用）。

参考：

[1] 危险指针：无锁对象的安全记忆填海，MAGED M. MICHAEL，IEEE交易以及并行和分布式系统上的交易，2004年。

[2]无锁同步记忆填海的性能，托马斯·E·哈特等

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

[4]基于间隔的记忆填海，Haosen Wen等，第23届ACM Sigplan sigplan研讨会论文集（PPOPP）的原理和实践（PPOPP），2018年。

Answer 3

是的，问题可能在D19中。

正如所接受的答案指出不是正常的免费（）。

这在简介第1节

中说明了这一点

只有在数据结构或临时变量中没有指针指向的情况下，节点才被释放。