这需要无锁，因为它必须在 SMP 系统的中断处理程序中运行。我不能拿锁。
我有一个包含一些值的连续数组。此数组中的某些条目是“空闲的”，它们未被占用。我想列出这些条目，以便我可以快速分配一个。但是，我有时不得不分配一个任意条目。
因此，我认为以下是一种不错的处理方式：连续数组不仅保存值，还保存左右指针，从而形成双端队列。只有自由值具有有效的左/右指针。我可以快速访问任意节点，因为它只是对双端队列的索引访问。
现在，问题的关键是：是否有一个不错的无锁双端队列算法，它相对有效并且可以支持删除任意节点？
连续数组不仅保存值，还保存左右指针，从而形成双端队列。
[剪辑]
现在，问题的关键是：是否有一个不错的无锁双端队列算法，它相对有效并且可以支持删除任意节点？
能够删除任意元素的双端队列实际上是一个双向链表；您唯一放弃的是插入任意元素的能力，而删除是困难的部分-如果您可以删除，则当然可以添加。
存在无锁双向链表，但它需要垃圾回收。
这个怎么样; 有一个freelist。这表示可用节点。节点实际上是一个数组，因此您可以对它们进行索引。当您必须使用任意节点时，索引到数组，然后在该元素中 CAS 标志，但将其保留在 freelist 中（当然，您必须这样做，因为它不在 freelist 的顶部）。当您将来要弹出时，发现您弹出了一个已经使用过的元素，请继续弹出，直到找到一个免费的元素。
在垃圾收集系统中，如果您不关心项目的内存何时被物理释放，并且无法添加项目，则可以让单链表支持项目的无锁逻辑删除紧跟在被删除的项目之后。给每个项目一个已删除标志，并有一个列表遍历例程，当它访问每个项目时，它会检查下一个节点是否已被删除；如果有，使用比较和交换来围绕它摆动当前节点的“下一个”指针。请注意，被删除节点的“下一个”指针可能会被更改，但只是跳过它后面的节点。摆动下一个指针可能会导致刚刚从列表中取消链接的节点重新链接（例如 A->B-> 如果同时移除 B 和 C，C->D 可能变为 A->B->D（摆动 B 的指针）然后 A->C->D（摆动 A 的指针指向 B 的“下一个”的锁存值指针）。但是，如果节点 C 曾经并且继续被标记为“已删除”，那不应该造成问题，因为下次迭代列表时，A 的指针将摆动到 D。
两个警告： -1- 在非垃圾收集系统中，可能很难知道何时可以真正释放节点；释放一个节点，然后将一个指针摆回它可能会导致未定义的行为；-2- 如果在删除节点之后立即添加节点，则指针可能摆动以断开新节点的连接。如果总是将节点添加到队列的末尾，则可以通过使用虚拟节点结束队列来避免后一个问题，直到后面有另一个节点才能删除该虚拟节点。