具有移尾功能的无锁队列算法

Question

对于 LRU 缓存，我需要一种类似于论文 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 中描述的无锁队列算法。

但是为了维护 LRU 队列，我还需要能够删除队列中的节点(尾部节点除外)。

我的想法是仅使用 CAS 操作将节点标记为已删除，然后使用单个清理线程稍后从队列中删除已删除的节点。

我发现创建无锁算法比我最初预想的要复杂。所以，我的问题是:
有没有这样的算法可用？

这是我目前使用的结构:

一般

• 节点具有以下结构:struct { e *entry, next pointer, prev pointer, state uint32}
• 为避免为每个新节点分配多个内存，分配了一个节点数组。
• 指向节点的指针由数组索引值和更新计数器组成，多路复用到单个 uint64
• 节点状态由一个高位组成，表示节点是否被删除。其余位用作更新计数器

排队

• 辅助队列保存未使用节点的列表，并通过从辅助队列中出队获取"new"节点，然后将其设置为默认值
• node.prev 设置为新节点入队前的当前尾

出列

• head.next.prev 在 head 出列之前被 CAS 为 NIL 值。如果 head.next.prev 设置为 CLEANUP(由清理线程处理)，则不允许出列，线程将让出 CPU 并重新开始。
• 在具有未删除状态的节点成功出列后，该状态将被 CAS'ed 删除，并且该节点将返回到辅助队列。失败时(或状态已设置为已删除)，出列的 node.prev 将从 NIL 更改为 CLEANUP，向清理线程发出信号，表明该节点已出列。出队将重新开始，直到未删除的节点成功出队并被 CAS 删除。

删除

• 为了标记队列中的删除，状态被 CAS'ed 删除并在成功时传递到清理队列。失败时不执行任何操作，但函数会返回。

清理线程

• 如果 node.prev 是 CLEANUP，则 Dequeue 已将其从队列中删除。节点传回辅助队列。
• 如果 node.prev 为 NIL，则该节点即将成为头节点、是头节点或即将出队。如果节点 == 头，清理线程尝试执行出列(状态更改为已删除)。失败时，清理过程从头开始。
• 如果节点被设置为另一个节点，node.prev 被 CAS'ed 为 CLEANUP。如果 head.next == node，这可以防止任何出队。成功后，使用双链表进行队列中删除。失败时，清理过程从头开始。

Node.prev 用来告诉:

• 队列中哪个节点在前
• 节点即将成为头/是头
• 清理线程正在处理节点
• 节点出队

Answer 1

队列中元素的逻辑删除实际上是有问题的，这就是为什么你找不到这方面的论文的原因。此外，它是添加到非常通用的数据结构中的非常具体的功能，这是您找不到论文的另一个原因；你只会找到一般数据结构的论文。

问题是双重的；首先，队列通常不支持游标。其次，知道访问您希望逻辑删除的元素是否仍然安全 - 例如它可能已经出队和解除分配了吗？

你引用的queue是用pointer-counter pairs来求解ABA的，也就是说使用了freelist。在这种情况下，您始终可以确定元素没有被释放。

对于游标，您需要在出队处输入，然后沿着队列向下进入入队指针。但是，如果您正在查看的元素在您移动到下一个元素之前已出队，会发生什么情况？然后，您将跟随已从队列中删除并位于空闲列表中的元素的下一个指针。事实上，一般来说，任何都可能发生在光标从一个元素移动到下一个元素之间的队列中 - 包括完全删除队列和使用不同的元素重新创建。

因此，您需要一个链表，它明确支持游标。

您没有提到您使用的语言吗？