并发数据结构- 1.8 优先队列&1.9 总结

原文链接，译文链接，译者：郭振斌，校对：周可人

1.8 优先队列

并发的优先队列是一个可线性化到顺序优先队列的数据结构，能够通过常用的优先队列语义提供insert和delete-min操作。

基于堆的优先队列

许多文献中提到的并发优先队列结构，其实是本书前面提到的可线性化堆结构。再一次的，这种结构的基本思想是在个别堆节点上使用细粒度锁，使线程在并行下也能够尽可能的访问数据结构的不同部分。设计这种并发堆的关键问题，在于传统自底向上的insert和自顶向下的delete-min操作有可能造成死锁。Biswas和Brown[17]提出基于锁的堆算法，通过专门的“清理”线程解决死锁。Rao和Kumar[116]建议通过一个将insert和delete-min操作都自顶向下处理的算法[17]来解决问题。Ayani[11]在他们算法基础上做了改善，即通过一种方式在堆两侧进行连续插入。Jones[68]提出一种基于类似斜堆的方案[116]。

Hunt et al.[61]提出一种基于堆的算法，解决了上述方案的许多局限性，尤其是针对在堆遍历中需要获取多个锁的问题。此算法处理上是在一个标记堆大小的变量上加锁一小段时间和堆的第一个或者最后一个元素上加锁。为了提升并行性，插入自底向上遍历堆，而删除自顶向下，且不会产生死锁。插入也采用了自左向右技术，就像[11]允许访问堆两侧，从而最小化冲突。

此外，Huang和Weihl[60]提出了一种基于斐波那契堆[34]并行版本的并发优先队列。

Herlihy[50], Barnes [12], and Israeli and Rappoport [65]提出了非阻塞可线性化的基于堆的优先队列算法。Sundell 和 Tsigas[133]提出了一个基于无锁版Pugh 并发跳表的无锁优先队列。

基于树的队列池

Huang、Weihl[60]和Johnson[66]这样描述并发优先池：（并发优先池是）松散语义的优先队列，不保证delete-min操作的可线性化。他们的设计都是基于修正版的并发B+树实现。Johnson引入了一个集合待删除值的“删除容器”，从而降低在并发执行delete-min操作时的负载。Shavit和Zemach [130]提出了一个在Pugh并发跳表中引入“删除容器”机制的类似（队列）池。一般情况下，较弱的池语义可以提升并发。在[130]他们还提出，如果允许的键容量是有限的（操作系统中通常如此），那么一个基于结合漏斗节点的二叉树的优先池可以扩展到上百个（相比数十个）处理器。

1.9 结语

我们概述了在共享内存多处理器下设计并发数据结构的相关问题，还调研了此领域的一些重要贡献。概述中清楚的说明了设计并发数据结构的诸多显著挑战，在撰写本文时，并发数据结构的成熟度还远远落后于顺序结构。然而，在发现关键问题和开发新技术方面已经取得了显著进展，以促进设计有效的并发数据结构；学术界和工业界重新在通过增强硬件来支持同步上产生兴趣，我们感到倍受鼓舞。鉴于新认识，新技术和更强大的硬件支持，我们相信并发数据结构设计会在不久的将来出现重大的进步。