data-structures - 解释 Michael & Scott 无锁队列算法

Question

我正在研究 Michael & Scott 的无锁队列算法，并尝试用 C++ 实现它。

但是我在代码中产生了竞争，并且认为算法中可能存在竞争。

我在这里阅读了这篇论文: Simple, Fast, and Practical Non-Blocking and BlockingConcurrent Queue Algorithms原始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++ 代码确实总是在线程 1 的 D4 处崩溃。

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

Answer 1

谢谢，非常有趣的话题!这看起来确实像一个 bug，但该论文的一位作者断言，他们的 free() 不是我们所使用的普通 free()，而是一些神奇的 free()，所以不存在 bug。太棒了。

参见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/

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