这需要无锁，因为它必须在 SMP 系统的中断处理程序中运行。我不能锁。
我有一个包含一些值的连续数组。这个数组中的一些条目是“空闲的”，它们没有被占用。我想列出这些条目，以便我可以快速分配一个。但是，我有时不得不分配一个任意条目。
因此，我认为以下是一种很好的做事方式: 连续数组不仅包含值，还包含左指针和右指针，因此构成了一个双端队列。只有自由值具有有效的左/右指针。我可以快速到达任意节点，因为它只是对双端队列的索引访问。
现在，问题的症结在于:是否有一种相对高效且可以支持删除任意节点的不错的无锁双端队列算法？
最佳答案
The contiguous array holds not just values but also left and right pointers, thus making a deque.
[剪断]
Now, to the crux of it: Is there a nice lock free deque algorithm that is relatively efficient and can support the removal of an arbitrary node?
具有删除任意元素能力的双端队列实际上是一个双向链表；您唯一放弃的是插入任意元素的能力，而删除是困难的部分 - 如果您可以删除，那么您当然可以添加。
存在无锁双向链表，但需要垃圾回收。
这个怎么样；有一个自由列表。这表示可用节点。节点实际上是一个数组，因此您可以对它们进行索引。当您必须使用任意节点时，索引到数组中，然后在该元素中 CAS 一个标志，但将其留在空闲列表中(当然您必须这样做，因为它不在空闲列表的顶部)。当你将来弹出时，发现你弹出了一个已经被使用过的元素，就继续弹出，直到找到一个空闲的元素。
关于performance - 支持删除任意节点的Lock Free Deque，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1814717/