并发非阻塞无锁队列及其实施方法和装置

摘要

仅当有必要防止队列变空时才使虚节点入列到并发非阻塞无锁FIFO队列中。仅在出列操作过程中并且仅当在该出列操作过程中队列包含单个用户节点时，虚节点才入列。这相对于总是将虚节点保持于队列中的常规机制而言减少了开销。用户节点直接入列到队列中并且能够按照任何线程的要求立即出列。优选地，入列和出列操作包括使用加载链接/条件存储(LL/SC)同步原语。这解决了ABA问题而无需使用唯一编号如队列特有编号，并且与包括使用比较和交换(CAS)同步原语以及通过使用唯一编号来解决ABA问题的常规机制形成对比。此外，优选地插入存储排序防护以使得算法可以在弱一致性处理器上运行。

主权项

一种实施队列的方法，包括以下步骤：(a)使用户节点入列到队列的末尾，其中在所述入列步骤(a)之前，所述队列至少包括虚节点，所述虚节点具有指向下一节点的“next”指针，并且其中所述用户节点具有指向下一节点的“next”指针，并且其中所述步骤(a)包括将尾节点的“next”指针设置为指向所述用户节点而将所述用户节点链接到所述队列的末尾；(b)在所述入列步骤(a)之后，使所述虚节点从所述队列中出列；(c)在所述出列步骤(b)之后，有条件地使头节点从所述队列中出列；(d)在所述有条件的出列步骤(c)过程中，仅当所述队列包含仅一个用户节点时才使另一虚节点入列到所述队列的末尾；并且将所述队列的尾指针更新为指向所述用户节点；其中所述更新步骤在后续入列操作或者后续出列操作过程中完成。