并发编程网 - ifeve.com

原文地址 作者：Pedro Ramalhete，译者：周可人，校对：梁海舰

Tick lock是mutual lock的一种简单实现：

http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf

它是由John Mellor-Crummey和Michael Scott在1991年提出的（pdf中2.2节），感谢C++11和C11中新的内存模型，我们可以对单个变量进行具有屏障或者不具有屏障的原子操作。当屏障没有使用，只有原子性保证时，我们称之为“relaxed atomic”：

http://en.cppreference.com/w/cpp/atomic/memory_order

注意在C11/C++11内存模型中，一个原子变量并不具有内在的“顺序一致性”或者“relaxed”性质，然而我们可以在每次访问的时选择它的行为。

原子修饰符只能保证原子性，即这个变量会被单步读或写。其他语言，如Java和Scala则不同，它们可以保证几乎所有的原生类型提供原子性保证，从而表现为“relaxed atomic”。并且，所有被声明为顺序一致性的变量可以在整个程序中保持性质（除非在Java中使用sun.misc.unsafe）。尽管这个细微的差异可能看起来并不重要，但是当我们的目标是从同步或是并发算法中挖掘最大性能时，就需要关注这个差异了。

阅读全文

《Concurrent Data Structures》（并发数据结构）一文是Mark Moir和Nir Shavit所撰写的一篇有关并发数据结构的综述性文章。这篇文章从多核处理器基础开始，理清了并发数据结构的基础设计理念和技巧，介绍了数据结构算法相关的正确性证明，并列举了栈，链表，队列，树等常用并发数据结构的设计思路。

为了促进大家对并发数据结构基础概念的了解，并发编程网组织译者翻译该论文。由于时间仓促，如有不到位的地方，还请各位指出。

感谢下列译者：董明鑫，俞升兵，Noodles，张军，huavben，iDestiny，郭振斌 阅读全文

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

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

阅读全文

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

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

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

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

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 阻塞技术

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

感谢人民邮电大学授权并发网发布此书样章，新书已上市，购买请进当当网

本章内容包含：

• 创建Fork/Join线程池
• 合并任务的结果
• 异步运行任务
• 在任务中抛出异常
• 取消任务

5.1　简介

通常，使用Java来开发一个简单的并发应用程序时，会创建一些Runnable对象，然后创建对应的Thread 对象来控制程序中这些线程的创建、执行以及线程的状态。自从Java 5开始引入了Executor和ExecutorService接口以及实现这两个接口的类（比如ThreadPoolExecutor）之后，使得Java在并发支持上得到了进一步的提升。 阅读全文

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

在查阅google之后，我发现没有一处对并发算法或是数据结构规定的演进条件（progress condition，注：参考[1]，译者认为翻译为演进状态更为合适）做合理的解释。甚至在”The Art of Multiprocessor Programming“中也只有围绕书本的一小段定义，大部分定义是单行的句子，因而造成了我们普通人含义模糊的理解，所以在这里我把我对这些概念的理解整理在一起，并且在每一种概念后面给出相应的例子。

我们先将演进条件分为四个主要类别，阻塞（blocking），无干扰（obstruction-free），无锁（lock-free），和无等待（wait-free）。详细列表如下：
阅读全文

感谢人民邮电大学授权并发网发布此书样章，新书购买传送门=》当当网

本章将介绍下列内容：

• 创建线程执行器
• 创建固定大小的线程执行器
• 在执行器中执行任务并返回结果
• 运行多个任务并处理第一个结果
• 运行多个任务并处理所有结果
• 在执行器中延时执行任务
• 在执行器中周期性执行任务
• 在执行器中取消任务
• 在执行器中控制任务的完成
• 在执行器中分离任务的启动与结果的处理
• 处理在执行器中被拒绝的任务

阅读全文

起源

在程晓明同学的文章“双重检查锁定与延迟初始化”中，提到了对于单例模式的“Initialization On Demand Holder idiom”实现方案。

这个方案的技术实质是利用Java类初始化的LC锁。相比其他实现方案（如double-checked locking等），该技术方案的实现代码较为简洁，并且在所有版本的编译器中都是可行的。该方案代码如下：
阅读全文

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

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

阅读全文