说明

这个是李大狗在 juc 中提到的算法论文，找了半天网上也没有。

于是决定自己翻译一下。

论文作者：Maged M. Michael Michael L. Scott

翻译作者：老马啸西风

ps: 最近发现自己的文章被各种盗，别人的 SEO 还比自己的高，醉了醉了。

摘要

借鉴以前的作者的想法，我们提出了一种新的非阻塞并发队列算法和一种新的双锁队列算法，其中一个队列和一个出队列可以同时进行。

两种算法都很简单，快速且实用。我们很惊讶没有在文献中找到它们。

在12节点SGI Challenge多处理器上进行的实验表明，新的非阻塞队列始终胜过最著名的替代方案。对于提供通用原子原语的机器（例如比较和交换或加载链接/存储条件的），这是显而易见的选择算法。

当多个进程同时竞争访问权限时，双锁并发队列的性能优于单个锁。对于具有非通用原子基元（例如测试和设置）的机器上的繁忙队列，它似乎是首选的算法。

由于非阻塞算法的许多动机都源于它们对进程执行中较大的，不可预测的延迟的免疫力，因此对于具有专用处理器的系统以及在每个处理器上具有多个程序的多个进程的系统，我们都报告了实验结果。

介绍

并发FIFO队列广泛用于并行应用程序和操作系统。

为了确保正确性，必须同步访问共享队列。

通常，用于并发数据结构的算法（包括FIFO队列）分为两类：阻塞和非阻塞。

阻塞算法允许缓慢或延迟的进程，以防止更快的进程无限期地完成对共享数据结构的操作。

非阻塞算法可确保如果有一个或多个活动进程尝试对共享数据结构执行操作，则某些操作将在有限的时间步长内完成。

在异步（尤其是多程序）多处理器系统上，当进程在不适当的时机暂停或延迟时，阻塞算法会导致性能显着下降。

延迟的可能来源包括处理器调度抢占， 页面错误和高速缓存未命中。

面对这些事件，非阻塞算法更加健壮。

许多研究人员提出了用于并发FIFO队列的无锁算法。

Hwang和Briggs，Sites 和 Stone提出了基于比较和交换的无锁算法。

这些算法没有完全指定。他们忽略了细节，例如处理空队列或单项队列，或并发排队和出队。

Lamport 提出了一种免等待算法，该算法将并发限制为单个入队者和单个出队者。

Gottlieb等和Mellor-Crummey 提出了无锁但不是非阻塞的算法：

它们不使用锁定机制，但是它们允许缓慢的进程无限期地延迟较快的进程。

Treiber提出了一种非阻塞但效率低的算法：出队操作花费的时间与队列中元素的数量成正比。

莉莉; 普拉卡什，李和约翰逊； 图雷克，莎莎和普拉卡什； 和 Barnes提出了用于生成顺序或并发基于锁的算法的非阻塞版本的通用方法。

但是，与专用算法相比，结果实现通常效率低下。

Massalin和Pu提出了一种基于双比较和交换基元的无锁算法，该算法同时在两个任意内存位置上运行，并且似乎仅在Mo-torola 68000系列处理器的更高版本上可用。

Herlihy和Wing 提出了一种基于阵列的算法，需要无限的数组。

Valois提出了一种基于数组的算法，该算法需要未对齐的比较和交换（在任何体系结构上均不受支持）或类似于Motorola的双重比较和交换（double_compare_and_swap）。

Stone提出了一个无锁但不可线性化且非阻塞性的队列。

这是不可线性的，因为较慢的入队者可能导致较快的过程使项目入队，并随后观察到空队列，尽管从未使出队的项目出队。

它不是非阻塞的，因为缓慢的入队可能会无限期地延迟其他进程的出队。

我们的实验还揭示了一种竞争状况，其中，慢速出队与更快的入队之间的某些交错以及其他过程的出队会导致被入队的元素永久丢失。

Stone还基于循环单链接列表提供了一个非阻塞队列。

该算法使用一个锚指针（anchor pointer）而不是通常的头和尾来管理队列。

我们的实验揭示了一种竞赛条件，其中缓慢的出队可能导致入队元素永久丢失。

Prakash，Lee和Johnson提出了一种可线性化的非阻塞算法，该算法需要排队和出队流程对队列进行快照，以便在更新队列之前确定其“状态”。

该算法通过允许较快的进程完成较慢的进程的操作而不是等待它们来实现阻塞时的特性。

Valois提出了一种基于列表的非阻塞算法，该算法避免了由Prakashet等人的算法快照引起的争用，并且通过将虚拟节点保持在单链接列表的头部（出队端），从而实现了更高的并发性，从而简化了特殊情况与空队列和单项队列相关联（站点建议的一种技术）。

不幸的是，该算法使尾指针滞后于头指针，从而阻止了出队进程安全释放或重用出队节点。

如果尾指针落后，并且进程释放出队的节点，则链表可能会断开，因此随后入队的项目将丢失。

由于内存是一种有限的资源，因此禁止使用内存是不可接受的选择。

因此，瓦洛瓦提出了一种释放和分配记忆的特殊机制。该机制将参考计数器与每个节点相关联。每次进程创建指向节点的指针时，它都会自动增加该节点的引用计数器。当它不打算访问以前访问过的节点时，它会自动减少关联的参考计数器。除了来自流程局部变量的临时链接外，每个引用计数器还反映数据结构中指向所讨论节点的链接数。对于队列，这些是头和尾指针以及链接列表链接。当数据结构或临时变量中没有指针指向节点时，该节点是自由的。

我们在主题管理机制和相关的非阻塞队列算法中发现并纠正了竞争条件。

即使这样，内存管理机制和采用它的队列也是不切实际的：无限内存可以保证始终满足算法的内存需求。

如果进程读取指向节点的指针（增加引用计数器）然后延迟，则会出现问题。

虽然它不运行，但其他进程可以使任意数量的其他节点入队和出队。

由于延迟进程保留了指针，因此该指针所引用的节点或其任何后继节点都无法释放。

因此，即使队列中的项目数受常数限制，也可能用完内存。

在最大长度为12项的队列的实验中，我们使用了一个初始化为64,000个节点的空闲列表，在运行一千万个队列和出队的过程中，内存耗尽了好几次。

上面提到的大多数算法都是基于比较交换的，因此必须处理ABA问题：如果某个进程在共享位置读取了值A，计算了一个新值，然后尝试进行比较交换操作，则比较交换可能会成功（如果不应该）在读取和比较期间，在其他过程之间切换，将A更改为a频段，然后再次返回到a。

最常见的解决方案是将修改计数器与指针关联，以始终在任何读取-修改-比较-交换序列中使用指针访问计数器，并在每次成功的比较-交换中递增。

这种解决方案不能保证不会发生ABA问题，但是这使其极不可能发生。要实现此解决方案，必须使用双字比较和交换，或者使用数组索引而不是指针，以便它们可以与计数器共享单个字。

Valois的引用计数技术可确保避免ABA问题，而无需修改计数器或双字比较和交换。

Mellor-Crummey的无锁队列不需要采取特殊预防措施来避免ABA问题，因为它使用了比较掉期交换和存储-修改-比较掉期交换频率，而不是通常的读取-修改-比较掉期序列。但是，此功能也会使算法阻塞。

在第2节中，我们介绍了两个新的并发FIFO队列算法，这些算法受上述工作中的思想启发。

两种算法都很简单实用。

一种是非阻塞性的；另一个使用一对锁。这些算法的正确性将在第3节中讨论。

我们将在第4节中介绍实验结果。

使用12节点的SGI Challenge多处理器，我们将新算法与简单的单锁队列，Mellor-Crummey的阻塞算法以及Prakashet al。和Valois的非阻塞算法（具有专用和多程序负载）进行了比较。

结果证实了非阻塞算法的多程序系统的价值。

在新的无锁算法中，无论有无多程序编程，它们也始终显示出卓越的性能。新的两锁算法无法与多程序系统上的非阻塞替代方法竞争，但是当多个进程同时竞争访问权限时，其性能优于单个锁。

第五部分总结了我们的结论。

算法

非阻塞队列

图1给出了用于非阻塞队列数据结构和操作的注释伪代码。

非阻塞算法-伪代码-01.PNG

算法将队列作为带有HeadandTailpointers的单链接列表实现。

与Valois的算法一样，Headalways指向一个虚拟节点，该虚拟节点是列表中的第一个节点。尾点指向列表中的最后一个节点或倒数第二个节点。

该算法使用比较交换和修改计数器来避免ABA问题。

为了允许出队进程释放出队节点，出队操作可确保尾部既不指向出队节点，也不指向其前任节点。

这意味着可以安全地重新使用已出队的节点。

为了获得各种指针的一致值，我们依靠读取序列来重新检查较早的值，以确保它们没有改变。

这些读取序列与Prakashet等人的快照相似，但比快照更简单（希望仅检查一个共享变量，而不是两个）。

可以使用类似的技术来防止Stone的封锁算法中的竞争状况。

我们使用Treiber的简单高效的非阻塞堆栈算法来实现非阻塞空闲列表。

两锁队列

图2给出了用于两锁队列数据结构和操作的带注释的伪代码。

非阻塞队列-02.PNG

该算法采用单独的Head和Tail锁，以允许入队和出队之间的完全并发。

像在非阻塞队列中一样，我们在列表的开头保留一个虚拟节点。

由于有虚拟节点，排队者不必访问Head，而出队者也不必访问Tail，从而避免了潜在的死锁问题，这些死锁问题是由尝试以不同顺序获取锁的进程引起的。

正确性（Correctness）

安全性

提出的算法是安全的，因为它们满足以下属性：

  1. 链接列表始终处于连接状态。

  2. 节点仅插入到链表中的最后一个节点之后。

  3. 仅从链接列表的开头删除节点。

  4. Head 永远指向链接列表中的第一个节点。

  5. 总是指向链接列表中的一个节点，最初所有这些属性都成立。

通过归纳法，我们表明它们继续保持不变，假设ABA问题从未发生。

  1. 链表始终处于连接状态，因为一旦插入阳极，它的下一个指针在释放之前就不会设置为NULL，并且直到从列表的开头将其删除之前，节点都不会释放（属性3）。

  2. 在无锁算法中，节点仅插入到链表的末尾，因为它们是通过尾指针链接的，该指针始终指向链表中的节点（属性5），并且插入的节点仅链接到具有以下内容的节点： NULLnextpointer，并且链表中唯一的此类节点是最后一个（属性1）。在基于锁的算法中，节点仅插入链表的末尾，因为它们是插入到由Tail指向的节点之后，并且在该算法中始终指向到链表中的最后一个节点，除非它受尾锁保护。

  3. 从列表的开头删除节点，因为仅当 Headed 和 Head 永远指向列表中的第一个节点（属性4）时，才删除它们。

  4. Head 永远指向列表中的第一个节点，因为它仅自动地将其值更改为下一个节点（使用头锁或使用compareandswap）。发生这种情况时，将其原来指向的节点视为已从列表中删除。 Head的新值不能为NULL，因为如果链表中有一个节点，则出队操作将返回而不删除任何节点。

  5. 尾总是指向链表中的一个节点，因为它永远不会落后于Head，所以它永远也不会指向已完成的节点。 同样，当Tail更改时，其值将始终摆动到列表中的下一个节点，并且如果下一个指针为NULL，则它永远不会更改其值。

线性（Linearizability）

提出的算法是可线性化的，因为在每个操作过程中都有一个特定点被认为是“生效”的。

当分配的节点链接到链表中的最后一个节点时，入队生效。

当Head摆动到下一个节点时，出队生效

而且，如前面小节（属性1、4和5）所示，队列变量始终反映队列的状态。

它们永远不会进入可能会误认为队列状态的瞬态状态（例如，非空队列似乎为空）。

活性（Liveness）

无锁算法是无阻塞的。

无锁算法是无阻塞的，因为如果有不延迟的进程尝试对队列执行操作，则可以保证操作在有限时间内完成。

仅当E7行中的条件失败，E8行中的条件失败或比较掉线E9行失败时，排队操作才会循环。

仅当行D5中的条件失败，行D6中的条件成立（并且队列不为空）或比较交换行D13失败时，才出队操作循环。

通过显示一个进程仅在另一个进程完成队列上的操作时才循环超过无数次，从而证明该算法是非阻塞的。

（1）仅当在执行E5行之后通过中间过程写入Tailis时，E7行中的条件才会失败。

尾部始终指向链表的最后一个节点或倒数第二个节点，并且在修改后，尾部紧随其指向的节点的下一个指针。

因此，如果E7行中的条件多次失败，那么另一个过程必须成功完成了入队操作。

（2）如果Tail指向链表中的倒数第二个节点，则E8行中的条件失败。

在比较标记行E13之后，尾部必须指向列表中的最后一个节点，除非已成功地使新项目入队。

因此，如果条件内联E8不止一次失败，则另一个进程必须成功完成了入队操作。

（3）仅当另一个进程成功将新元素加入队列时，E9行中的compareandwap才会失败。

（4）仅当Head已由另一个进程写入时，D5行中的条件和D13行中的compareandwap才会失败。

仅当进程成功使项目出队时才写入头。

（5）仅当Tail指向链接列表中倒数第二个节点（在这种情况下，它也是第一个节点）时，D6行中的条件才会成功（队列不为空）。

在比较标记行D10之后，除非过程成功将新项目加入队列，否则尾部必须指向列表中的最后一个节点。

因此，如果D6行的条件不止一次成功，则另一个进程必须成功完成了入队操作（并且同一进程或另一个进程成功出队了）。

两锁（Two-Lock）算法是无活锁（Livelock-Free）

两锁算法不包含任何循环。

因此，如果用于锁定和解锁头锁和尾锁的互斥锁算法是无活锁的，那么提出的算法也是无活锁的。

有许多互斥算法是无活锁的]。

性能

我们使用12个处理器的Silicon Graphics Challenge多重处理器将新算法的性能与单锁算法（Prakashet等人的算法，Valois算法（具有更正） 到内存管理机制）和梅勒-克鲁姆美算法]。

我们将Prakashet等人的算法包括在内，因为它似乎是已知的非阻塞替代方法中最好的。

Mellor-Crummey的算法表示基于非锁定但具有阻塞性的替代方案； 它比Prakashet等人的代码更简单，并且在没有不可预测的过程延迟的情况下可以预期显示出较低的恒定开销，但是可能会在多程序系统上退化。

我们包含了Valois的算法，以证明在多程序系统上，即使是效率相对较低的非阻塞算法也能胜过阻塞算法。

对于这两种基于锁的算法，我们使用带有有限指数退避（back-off）的test-and-test 和 set locks.

在非基于锁的算法中，我们还会在适当情况下使用退避。

对于在队列操作之间至少进行少量工作的程序中，性能对精确选择退避参数并不敏感。

我们使用链接和存储条件指令MIPS R4000来模拟测试和设置以及其他算法所需的原子操作（比较交换，获取和递增，获取和递减等 compareandswap,fetchandincrement,fetchanddecrement）。

为了确保实验结果的准确性，我们专门使用了多处理器，并防止其他用户在实验过程中访问它。

为了评估不同编程水平下算法的性能，我们使用了挑战多处理器中的一项功能，该功能允许程序员将进程与某些处理器相关联。

例如，为了表示不允许多重编程的专用系统，我们创建了与要使用的处理器数量一样多的进程，并将每个进程锁定到不同的处理器。

为了表示一个多程序级别为2的系统，我们创建的进程数量是我们要使用的处理器数量的两倍，并将每对进程锁定为一个处理器。

可以从ftp://ftp.cs.rochester.edu/pub/packages/schedcioussynch/concurrent队列中获得用于测试算法的Ccode。

算法以最高优化级别进行编译，并经过仔细的手动优化。

我们在各种处理器上进行了长达数小时的长时间执行，以测试每种算法。

正是在这个过程中，我们发现了第1节中提到的竞态条件（race conditions）。

所有实验都使用一个初始为空的队列，进程对其执行一系列入队和出队操作。

每个过程使一个项目入队，执行“其他工作”，使项目出队，进行“其他工作”并重复。

对于进程，每个进程执行此循环10 ^ 6次。共计一百万个入队和出队。

“其他工作”大约包含一个空循环中的旋转；它可以通过防止同一进程长时间进行队列操作来使实验更加逼真（由于超低的缓存未命中率会导致性能过分乐观） 。

我们从图中报告的总时间中减去了一个处理器完成“其他工作”所需的时间。

从图中报告的总时间中完成“其他工作”。图3显示了一百万个入队/出队对的净经过时间（以秒为单位）。

粗略地说，这对应于一对入队/出队对的时间（以微秒为单位）。

确切地说，对于k个处理器，该图显示了一个处理器花费在执行10 ^ 6 入队/出队 上的时间，加上其他处理器执行的其他 10 ^ 6 *（k-1）* k 广播的关键路径所超过的时间。 第

一位处理器在“其他工作”中花费的时间和循环开销。 对于k = 1，第二项为零。

要求增加，第一项收缩到零，第二项接近整个计算的临界路径长度； 即一队/一队出局的串行部分的一百万倍。

究竟在不同的处理器上执行多少重叠，取决于算法的选择，处理器的数量k以及队列操作之间“其他工作”的时间长度。

performance

结论

队列在并行程序中无处不在，其性能是一个主要问题。

我们预选了一种简单，无阻塞，实用且快速的并发队列算法。我

们很惊讶没有在文献中找到合适的人。

对于具有通用原子基元（例如compareandswaporloadlinked / storeconditional）的多处理器上的任何基于队列的应用程序来说，这似乎是一种选择的算法。

它的结构类似于非阻塞队列的结构，但是它只允许一个入队和一个出队在给定时间进行。但是由于它是基于锁的，因此可以在具有简单原子原语（例如testandset）的计算机上运行。

建议将其用于此类计算机上大量使用的队列（对于通常仅由一个或两个处理器访问的队列，单个锁的运行速度会稍快一些。 ）这项工作是一个大型项目的一部分，该项目旨在评估常见数据结构的原子更新的替代机制之间的权衡。

考虑不足的结构包括堆栈，队列，堆，搜索树和哈希表。

机制包括单锁，特定于数据结构的多锁算法，通用和专用非阻塞算法以及到中央管理器的功能传递（这是一种有效的技术，其中远程访问等待时间主导着计算时间）。

在工作[8，25，26]中，我们一直在开发与调度程序配合使用的通用同步机制，以避免不合时宜的抢占。

鉴于对进程延迟的抵抗力是非阻塞并行算法的主要优势，我们计划将其进行比较多程序系统中的两种方法

小结

算法这个东西就是这样，都是经过一代一代人的不断改进摸索才能的道德的。

参考资料

paper