并发编程网 - ifeve.com

原文地址  作者：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就职。

https://labs.oracle.com/pls/apex/f?p=labs:bio:0:296

阅读全文

原文链接，译文链接，译者：huavben，校对：周可人

考虑支持插入，删除和查找操作的并发数据结构实现。如果这些操作只处理键值（译者注：而不处理具体值），这样的数据结构会是一个集合。如果一个数据值与每一个键关联起来，我们就得到了一部数据字典。由于他们都是密切相关的数据结构，一个并发的集合通常能够经过适当修改来实现一部字典。在接下来的三个小节中，我们将专注于利用linked lists，hash tables，和trees这三种不同的数据结构来实现集合。

阅读全文

原文链接，译文链接，译者：huavben，校对：周可人

实现高效并发栈和队列的大部分挑战来自于一个被插入的元素可以被删除这一需求。并发池是一种支持插入和删除操作的数据结构，它允许删除操作移除任何一个已经被插入的，并且没有在随后被删除的元素。这样的弱需求提供了提高并发性能的机会。

一个高效的并发池可以使用任意静态一致的计数器来构建。在这样的并发池中，元素被置于数组当中，fetch-and-inc操作决定插入操作在哪个位置存储元素，同样的，fetch-and-inc操作决定删除操作在哪个位置获得元素。每一个数组元素都包含了一个表示满/空的比特位或者等效的机制，来表明在相应的位置，将要删除的元素已经存在。在这种策略下，使用combining tree，combining funnel，counting network，diffracting tree中的任何一个技术都可以并行化共享技术器，解决这一主要的瓶颈来创建出一个高吞吐量的共享并发池。此外，一个类似栈的池可以使用一个允许增加和减少操作的计数器来实现，然后利用以上技术中的一种来并行化.
阅读全文

原文链接，译文链接，译者：iDestiny，校对：周可人

任何查找树的并发实现都可以通过用一个独占锁保护来完成。通过使用读写锁对并发性能有一定提升，读写锁允许所有只读（查找）操作并发地执行，因为读操作是以共享模式持有锁，然而更新（插入或删除）操作持有独占模式的锁，从而排斥其他所有操作。如果更新操作比较少，这还能接受，但是只要有适量的更新操作，那么更新操作所持有的独占锁将产生线性的瓶颈，从而大大降低性能。通过使用细粒度的锁策略——比如每个节点一个锁，而不是整棵树使用同一个锁——这样我们进一步地提升了并发性能。
阅读全文

原文链接，译文链接，译者：iDestiny，校对：周可人

典型可扩展的哈希表即一个可调整大小的桶数组(buckets), 每一个桶存放预期数量的元素，因此哈希表平均在常量时间内进行插入，删除，查询操作。哈希表调整大小的主要成本—–在于新旧桶(buckets)之间进行重新分配操作，该操作被分摊到所有表操作上，所以平均操作时间也是常量的。哈希表调整大小就是扩容，在实践中，哈希表仅需要增加数组大小即可。

Michael实现了一个可并发，不可扩展的哈希表(通过对哈希表中每个桶进行读写锁约束)。然而，为了保证元素数量增长时的性能，哈希表必须可扩展。
阅读全文

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

1.8 优先队列

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

基于堆的优先队列

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

原文链接，译文链接，译者：张军，校对：周可人

1.1.4 复杂度测量

一个被广泛研究的方向是在理想化模型，如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135]。然而，很少有将这些数据结构放在一个真实的多处理器上进行建模的。这里有多种原因，大部分原因跟系统硬件架构与线程异步执行的相互作用有关。想想组合树(combining tree)的例子，虽然我们能通过计算（指令数）得到O(P/logP)的加速比，但这无法反映在实证研究中[52, 129]。真实世界的行为是被上述其他因素支配的，如竞争开销，缓存行为，同步操作(例如CAS)开销，请求到达率，退避延时，数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。 阅读全文

原文链接，译文链接，译者：Noodles，校对：周可人

1.1.3 非阻塞技术

正如前面讨论的那样，非阻塞实现主要目的是为了消除由锁带来的相关问题，为了形式化研究这一概念，多种非阻塞演进条件已经在相关文献有所研究了，如wait-freedom演进条件，lock-freedom演进条件，和obstruction-freedom演进条件。满足wait-free演进条件的操作是指在执行自身包含的有限步骤之后，保证操作必须完成，而不用考虑其他操作发生的时序，满足lock-free演进条件的操作是指在执行自身包含的有限步骤之后，保证某些操作完成。满足obstruction-free演进条件的操作是指在不受其他操作干扰的情况下，执行它包含的有限步骤之后，保证其完成。

阅读全文

原文链接，译文链接，译者：周可人，校对：梁海舰

1.1.2 阻塞技术

在很多数据结构中，内存竞争所带来的不良现象和前文所说的顺序瓶颈带来的影响都可以通过使用细粒度锁机制来减小。在细粒度锁机制中，我们用多个粒度较小的锁来保护数据结构中的不同部分。这样做的目的是允许并发操作在它们不访问数据结构的相同部分时并行执行。这种方法也可以用于避免独立内存位置访问的额外竞争。在一些数据结构中，这种现象经常发生；举个例子，在哈希表中，对那些被哈希到不同哈希桶中的值的操作自然访问的是数据结构中的一部分。 阅读全文

原文链接，译文链接，译者：俞升兵，校对：周可人

1.1.1 性能

一个运行在P个处理上的应用程序的加速度是它在单个处理器上的执行时间和在P个处理器的执行时间的比值。这是一种评价应用程序对于机器资源利用程度的衡量。理想情况下，我们想要的结果是线性加速度：当我们使用P个处理器的时候,我们希望可以获得P的加速度(译者注:例如一个应用程序在单处理器的执行时间是10秒,那么在双处理的执行时间理想情况下是5秒)。加速度随着P一起增加的数据结构我们称之为可扩展的数据结构。在设计可扩展的数据结构的时候,我们必须注意：为了同步使用简单的方法会严重破坏扩展性。
阅读全文

原文链接，译文链接，译者：董明鑫，校对：周可人

随着多个处理器共享同一内存的机器在商业上的广泛使用，并发编程的艺术也产生了巨大的变化。当前的趋势向着低功耗芯片级多线程（CMT）发展，所以这样的机器一定会更加广泛的被使用。

共享内存多处理器是指并发的执行多个线程的系统，这些线程在共享的内存中通过数据结构通讯和同步。这些数据结构的效率对于性能是很关键的，而目前熟练掌握为多处理器机器设计高效数据结构这一技术的人并不多。对大多数人来说，设计并发的数据结构比设计单线程的难多了，因为并发执行的线程可能会多种方式地交错运行他们的指令，每一种方式会带来不同的，甚至不符合预期的输出。这就要求设计者改变他们对运算的认识，理解新的设计方法，采用新的编程工具集。此外，设计可扩展的并发数据结构，使得当机器执行越来越多的并发线程时依旧表现良好也是新的挑战。本文主要介绍设计并发数据结构的相关挑战，和一些重要的数据结构相关内容的总结。我们的总结绝不是全面的；相反，我们特意选取了一些能说明设计的关键问题的流行的数据结构，希望我们提供了足够的背景和知识，让有兴趣的读者接触那些我们没有提到的内容。
阅读全文

什么是并发数据结构? 引用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.

简而言之，并发数据结构即允许多线程同时访问（读和写）的数据结构。

阅读全文