并发数据结构- 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 结语

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

时间: 2016-04-06

并发数据结构- 1.8 优先队列&1.9 总结的相关文章

招募译者翻译并发数据结构

什么是并发数据结构? 引用wiki上的定义 In computer science, a concurrent data structure is a particular way of storing and organizing data for access by multiple computing threads (or processes) on a computer. 简而言之,并发数据结构即允许多线程同时访问(读和写)的数据结构. 并发数据结构中的算法的设计原则主要分两大类,li

并发数据结构-1.1 并发的数据结构的设计

原文链接,译文链接,译者:董明鑫,校对:周可人 随着多个处理器共享同一内存的机器在商业上的广泛使用,并发编程的艺术也产生了巨大的变化.当前的趋势向着低功耗芯片级多线程(CMT)发展,所以这样的机器一定会更加广泛的被使用. 共享内存多处理器是指并发的执行多个线程的系统,这些线程在共享的内存中通过数据结构通讯和同步.这些数据结构的效率对于性能是很关键的,而目前熟练掌握为多处理器机器设计高效数据结构这一技术的人并不多.对大多数人来说,设计并发的数据结构比设计单线程的难多了,因为并发执行的线程可能会多种

并发数据结构-1.5 链表

原文链接,译文链接,译者:huavben,校对:周可人 考虑支持插入,删除和查找操作的并发数据结构实现.如果这些操作只处理键值(译者注:而不处理具体值),这样的数据结构会是一个集合.如果一个数据值与每一个键关联起来,我们就得到了一部数据字典.由于他们都是密切相关的数据结构,一个并发的集合通常能够经过适当修改来实现一部字典.在接下来的三个小节中,我们将专注于利用linked lists,hash tables,和trees这三种不同的数据结构来实现集合. 试想我们使用一个linked list去实

并发数据结构-1.1.4 复杂度测量&1.1.5 正确性

原文链接,译文链接,译者:张军,校对:周可人 1.1.4 复杂度测量 一个被广泛研究的方向是在理想化模型,如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135].然而,很少有将这些数据结构放在一个真实的多处理器上进行建模的.这里有多种原因,大部分原因跟系统硬件架构与线程异步执行的相互作用有关.想想组合树(combining tree)的例子,虽然我们能通过计算(指令数)得到O(P/logP)的加速比,但这无法反映在实证研究中[52, 129].真实世界的行为是被上述其他

并发数据结构-1.1.2 阻塞技术

原文链接,译文链接,译者:周可人,校对:梁海舰 1.1.2 阻塞技术 在很多数据结构中,内存竞争所带来的不良现象和前文所说的顺序瓶颈带来的影响都可以通过使用细粒度锁机制来减小.在细粒度锁机制中,我们用多个粒度较小的锁来保护数据结构中的不同部分.这样做的目的是允许并发操作在它们不访问数据结构的相同部分时并行执行.这种方法也可以用于避免独立内存位置访问的额外竞争.在一些数据结构中,这种现象经常发生:举个例子,在哈希表中,对那些被哈希到不同哈希桶中的值的操作自然访问的是数据结构中的一部分. 对其他的数

并发数据结构-1.1.3 非阻塞技术

原文链接,译文链接,译者:Noodles,校对:周可人 1.1.3 非阻塞技术 正如前面讨论的那样,非阻塞实现主要目的是为了消除由锁带来的相关问题,为了形式化研究这一概念,多种非阻塞演进条件已经在相关文献有所研究了,如wait-freedom演进条件,lock-freedom演进条件,和obstruction-freedom演进条件.满足wait-free演进条件的操作是指在执行自身包含的有限步骤之后,保证操作必须完成,而不用考虑其他操作发生的时序,满足lock-free演进条件的操作是指在执行

并发数据结构:迷人的原子

随着多核CPU成为主流,并行程序设计亦成为研究领域的热门. 要想利用多核/多路CPU带来的强大功能,通常使用多线程来开发应用程序.但是要想拥有良好的硬件 利用率,仅仅简单的在多个线程间分割工作是不够的.还必须确保线程大部分时间在工作,而不是在等待 工作或等待锁定共享数据结构. 在不止一个线程访问共享数据时,所有线程都必须使用同步.如果线程间不进行协调,则没有任务可 以真正并行,更糟糕的是这会给程序带来毁灭性的错误. 现在让我们来看一下在.NET和D语言中的标准同步手段-锁定..NET下我们使用l

并发数据结构:Stack

在叙述并发Stack前,我们先来了解下非线程安全的Stack. Stack是一种线性数据结构,只能访问它的一端来存储或读取数据.Stack很像餐厅中的一叠盘子:将 新盘子堆在最上面,并从最上面取走盘子.最后一个堆在上面的盘子第一个被取走.因此Stack也被称为 后进先出结构(LIFO). Stack有两种实现方式:数组和列表.下面我们分别用这两种方式来实现一个简单的Stack.采用数组 实现代码如下: using System; using System.Collections.Generic;

【转载】并发数据结构

本文转载自http://shift-alt-ctrl.iteye.com/blog/1841084   请首先参考:http://shift-alt-ctrl.iteye.com/blog/1839142 一.BlockingDeque阻塞双端队列(线程安全): 注意ArrayDeque和LinkedList仅仅扩展了Deque,是非阻塞类型的双端队列. BlockingQueue单向队列,其内部基于ReentrantLock + Condition来控制同步和"阻塞"/"唤