3

对于 LRU 缓存，我需要一种用于无锁队列的算法，类似于简单、快速和实用的非阻塞和阻塞并发队列算法一文中描述的算法

但是为了维护一个 LRU 队列，我还需要删除队列中的节点（尾部节点除外）。

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

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

这是我目前使用的结构：

一般的

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

入队

  • 辅助队列保存未使用节点的列表，“新”节点通过从辅助队列中的出队获取，然后设置为默认值
  • node.prev 在新节点入队之前设置为当前尾部

出队

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

删除

  • 为了标记队列中的删除，状态被 CAS'ed 删除并在成功时传递给清理队列。失败时什么也不做，但函数返回。

清理线程

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

Node.prev 用于告诉：

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

1 回答 1

3

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

有问题的问题是双重的；首先，队列通常不是为支持游标而设计的。其次，了解访问您希望在逻辑上删除的元素是否仍然安全——例如，它是否已经出队和解除分配？

您引用的队列使用指针计数器对来解决 ABA，这意味着使用空闲列表。在这种情况下，您始终可以确定该元素尚未被释放。

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

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

你没有提到你使用的语言？

于 2012-09-11T12:39:41.267 回答