非阻塞算法
原文地址 作者:Jakob Jenkov 译者:张坤
在并发上下文中,非阻塞算法是一种允许线程在阻塞其他线程的情况下访问共享状态的算法。在绝大多数项目中,在算法中如果一个线程的挂起没有导致其它的线程挂起,我们就说这个算法是非阻塞的。
为了更好的理解阻塞算法和非阻塞算法之间的区别,我会先讲解阻塞算法然后再讲解非阻塞算法。
原文地址 作者:Jakob Jenkov 译者:张坤
在并发上下文中,非阻塞算法是一种允许线程在阻塞其他线程的情况下访问共享状态的算法。在绝大多数项目中,在算法中如果一个线程的挂起没有导致其它的线程挂起,我们就说这个算法是非阻塞的。
为了更好的理解阻塞算法和非阻塞算法之间的区别,我会先讲解阻塞算法然后再讲解非阻塞算法。
原文地址 作者:Pedro Ramalhete,译者:叶磊,校对:周可人
在学术论文中Harris Linked List是使用最广泛的并发数据结构之一。
Harris Linked List是一个基于linked-list的并发有序set(或者是map),可进行无锁性质的插入,删除和查找操作。
http://research.microsoft.com/pubs/67089/2001-disc.pdf
这篇文章最早在2001年的DISC会议上发表,作者是Tim Harris,目前在Oracle就职。
实现高效并发栈和队列的大部分挑战来自于一个被插入的元素可以被删除这一需求。并发池是一种支持插入和删除操作的数据结构,它允许删除操作移除任何一个已经被插入的,并且没有在随后被删除的元素。这样的弱需求提供了提高并发性能的机会。
一个高效的并发池可以使用任意静态一致的计数器来构建。在这样的并发池中,元素被置于数组当中,fetch-and-inc操作决定插入操作在哪个位置存储元素,同样的,fetch-and-inc操作决定删除操作在哪个位置获得元素。每一个数组元素都包含了一个表示满/空的比特位或者等效的机制,来表明在相应的位置,将要删除的元素已经存在。在这种策略下,使用combining tree,combining funnel,counting network,diffracting tree中的任何一个技术都可以并行化共享技术器,解决这一主要的瓶颈来创建出一个高吞吐量的共享并发池。此外,一个类似栈的池可以使用一个允许增加和减少操作的计数器来实现,然后利用以上技术中的一种来并行化.
阅读全文
并发的优先队列是一个可线性化到顺序优先队列的数据结构,能够通过常用的优先队列语义提供insert和delete-min操作。
基于堆的优先队列
许多文献中提到的并发优先队列结构,其实是本书前面提到的可线性化堆结构。再一次的,这种结构的基本思想是在个别堆节点上使用细粒度锁,使线程在并行下也能够尽可能的访问数据结构的不同部分。设计这种并发堆的关键问题,在于传统自底向上的insert和自顶向下的delete-min操作有可能造成死锁。Biswas和Brown[17]提出基于锁的堆算法,通过专门的“清理”线程解决死锁。Rao和Kumar[116]建议通过一个将insert和delete-min操作都自顶向下处理的算法[17]来解决问题。Ayani[11]在他们算法基础上做了改善,即通过一种方式在堆两侧进行连续插入。Jones[68]提出一种基于类似斜堆的方案[116]。
阅读全文
一个被广泛研究的方向是在理想化模型,如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135]。然而,很少有将这些数据结构放在一个真实的多处理器上进行建模的。这里有多种原因,大部分原因跟系统硬件架构与线程异步执行的相互作用有关。想想组合树(combining tree)的例子,虽然我们能通过计算(指令数)得到O(P/logP)的加速比,但这无法反映在实证研究中[52, 129]。真实世界的行为是被上述其他因素支配的,如竞争开销,缓存行为,同步操作(例如CAS)开销,请求到达率,退避延时,数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。 阅读全文
正如前面讨论的那样,非阻塞实现主要目的是为了消除由锁带来的相关问题,为了形式化研究这一概念,多种非阻塞演进条件已经在相关文献有所研究了,如wait-freedom演进条件,lock-freedom演进条件,和obstruction-freedom演进条件。满足wait-free演进条件的操作是指在执行自身包含的有限步骤之后,保证操作必须完成,而不用考虑其他操作发生的时序,满足lock-free演进条件的操作是指在执行自身包含的有限步骤之后,保证某些操作完成。满足obstruction-free演进条件的操作是指在不受其他操作干扰的情况下,执行它包含的有限步骤之后,保证其完成。
随着多个处理器共享同一内存的机器在商业上的广泛使用,并发编程的艺术也产生了巨大的变化。当前的趋势向着低功耗芯片级多线程(CMT)发展,所以这样的机器一定会更加广泛的被使用。
共享内存多处理器是指并发的执行多个线程的系统,这些线程在共享的内存中通过数据结构通讯和同步。这些数据结构的效率对于性能是很关键的,而目前熟练掌握为多处理器机器设计高效数据结构这一技术的人并不多。对大多数人来说,设计并发的数据结构比设计单线程的难多了,因为并发执行的线程可能会多种方式地交错运行他们的指令,每一种方式会带来不同的,甚至不符合预期的输出。这就要求设计者改变他们对运算的认识,理解新的设计方法,采用新的编程工具集。此外,设计可扩展的并发数据结构,使得当机器执行越来越多的并发线程时依旧表现良好也是新的挑战。本文主要介绍设计并发数据结构的相关挑战,和一些重要的数据结构相关内容的总结。我们的总结绝不是全面的;相反,我们特意选取了一些能说明设计的关键问题的流行的数据结构,希望我们提供了足够的背景和知识,让有兴趣的读者接触那些我们没有提到的内容。
阅读全文