解释迈克尔

Question

我在研究Michael

但我在我的代码中产生了一个竞赛，并认为算法中可能存在竞赛。

我在这里阅读了论文：简单、快速和实用的非阻塞和阻塞并发队列算法，原始的取消排队伪代码如下：

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

在我看来，比赛是这样的：

< li >线程1前进到D3，然后停止。 < li >线程2前进到D3，读取与线程1相同的磁头。 < li >线程2幸运地一直前进到D20，在D19它释放了head.ptr < li >线程1继续前进到D4，尝试读取< code>head.ptr-

对于线程1，我的C代码总是在D4崩溃。

有人能指出我的错误并给出一些解释吗？

Answer 1

是的，问题可能在D19。

正如公认的答案所指出的，不是正常的免费（）。

这在导言§1中有所说明

仅当数据结构中没有指针或临时变量指向节点时，才会释放节点。

Answer 2

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

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

还有许多基于时代的填海变体，如RCU[2,3]，以及最近的基于间隔的填海（IBR）[4]。它们通过保留时代来避免免费使用，并且比危险指针更快。据我所知，基于时代的填海被广泛采用来处理这个问题。

你可以看看下面提到的这些论文，了解更多细节。基于区间的内存回收的论文有很多背景讨论。

这是非阻塞数据结构中的一个普遍问题，我们通常不认为它是数据结构本身的错误——毕竟它只发生在使用手动内存管理的语言中，比如C/C，而不是像Java（顺便说一句，迈克尔

参考：

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

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

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

[4]基于区间的内存回收，郝森文等，第23届ACM SIGPLAN并行编程原理与实践研讨会(PPoPP)论文集，2018。

Answer 3

谢谢你，非常有趣的主题！这看起来绝对像一个错误，但是这篇论文的一位作者断言，他们的Free（）不是我们都生活在一起的正常的Free（），而是一些神奇的Free（），所以没有错误。太棒了。

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

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