对于LRU缓存，我需要一种无锁队列的算法，类似于论文《简单、快速和实用的非阻塞和阻塞并发队列算法》中描述的算法
但是，为了维护LRU队列，我还需要删除队列中的节点（尾部节点除外）的可能性。
我的想法是用CAS操作将节点标记为已删除，然后使用单个清理线程，稍后将从队列中删除已删除的节点。
我发现创建无锁算法比我最初预想的要复杂。所以，我的问题是：
是否已有此类算法可用
这是我目前使用的结构：
常规
- 节点具有以下结构：struct{e*entry，next pointer，prev pointer，state uint32}
- 为了避免为每个新节点分配多个内存，将分配一个节点阵列
- 指向节点的指针由数组索引值和更新计数器组成，复用到单个uint64中
- 节点状态由一个高位组成，该高位指示节点是否被删除。其余位用作更新计数器
排队
- 辅助队列包含未使用节点的列表，"新"节点通过辅助队列的出队列获取，然后设置为默认
- node.prev在新节点入队之前设置为当前尾部
退出队列
- head.next.prev在head出列之前被CAS'化为NIL值。如果head.next.prev设置为CLEANUP（由清理线程处理），则不允许出列，线程将产生CPU并重新启动
- 在具有未删除状态的节点成功出列时，状态将被CAS‘ed为已删除，节点将返回到辅助队列。一旦失败（或状态已设置为已删除），退出队列的node.prev将从NIL更改为CLEANUP，向清理线程发出节点已退出队列的信号。出队将重新开始，直到取消删除的节点成功出队并CAS被删除
删除
- 若要标记队列中的删除，状态为CAS‘ed To deleted，并在成功时传递到清理队列。失败时不执行任何操作，但函数返回
清理线程
- 若node.prev是CLEANUP，则Dequeue已将其从队列中删除。节点被传递回辅助队列
- 如果node.prev是NIL，则该节点即将成为head、是head或即将出列。若node==head，则清理线程尝试执行出列（状态更改为已删除）。一旦失败，清理过程将重新开始
- 若将node设置为另一个节点，则node.prev将CAS'ed设置为CLEANUP。这可以防止在head.next==node之后立即出列。成功后，将使用双链接列表进行队列中删除。一旦失败，清理过程将重新开始
Node.prev用于告知：
- 队列中的前一个节点是什么
- 节点即将成为头/是头
- 节点正在由清理线程处理
- 节点已退出队列
实际上，逻辑删除队列中的元素是有问题的，这就是为什么你找不到这方面的论文。此外，它是一个非常特殊的函数，添加到一个非常通用的数据结构中，这也是你找不到论文的另一个原因；你只能找到一般数据结构的论文。
问题有两个方面；首先，队列通常不是为支持游标而设计的。第二，知道访问您希望逻辑删除的元素是否仍然安全——例如，它是否已经出列和解除分配？
您引用的队列使用指针-计数器对来求解ABA，这意味着使用了自由列表。在这种情况下，您可以始终确保元素没有被解除分配。
对于游标，您需要在出队列处输入，然后沿着队列向下到达入队指针。但是，如果您正在查看的元素在转到下一个元素之前已退出队列，会发生什么呢？然后，您将跟踪从队列中删除并在自由列表中的元素的下一个指针。事实上，通常情况下，任何的事情都可能发生在光标从一个元素移动到下一个元素之间的队列上，包括完全删除队列和重新创建不同的元素。
因此，您需要一个链表，它明确支持游标。
你没有提到你使用的语言？