并发编程网 - ifeve.com

原文链接  作者: Jakob Jenkov 译者: 林威建[weakielin@gmail.com]

Java中的ThreadLocal类允许我们创建只能被同一个线程读写的变量。因此，如果一段代码含有一个ThreadLocal变量的引用，即使两个线程同时执行这段代码，它们也无法访问到对方的ThreadLocal变量。
阅读全文

原文地址  作者：Jakob Jenkov   译者：张坤

在并发上下文中，非阻塞算法是一种允许线程在阻塞其他线程的情况下访问共享状态的算法。在绝大多数项目中，在算法中如果一个线程的挂起没有导致其它的线程挂起，我们就说这个算法是非阻塞的。

为了更好的理解阻塞算法和非阻塞算法之间的区别，我会先讲解阻塞算法然后再讲解非阻塞算法。

阅读全文

原文地址：作者： Jakob Jenkov   译者：张坤

CAS（Compare and swap）比较和替换是设计并发算法时用到的一种技术。简单来说，比较和替换是使用一个期望值和一个变量的当前值进行比较，如果当前变量的值与我们期望的值相等，就使用一个新值替换当前变量的值。这听起来可能有一点复杂但是实际上你理解之后发现很简单，接下来，让我们跟深入的了解一下这项技术。

阅读全文

感谢网友【张超盟】的投稿

1. 前言

AQS(AbstractQueuedSynchronizer)是 java.util.concurrent的基础。J.U.C中宣传的封装良好的同步工具类Semaphore、CountDownLatch、ReentrantLock、ReentrantReadWriteLock、FutureTask等虽然各自都有不同特征，但是简单看一下源码，每个类内部都包含一个如下的内部类定义：

[code lang=”java”] abstract static class Sync extends AbstractQueuedSynchronizer [/code]

阅读全文

原文地址  译文地址   译者：姚志彬  校对：丁一，方腾飞

       这里我们只是关注了一些多线程之间共享变量的简单使用问题。这些是任何一个写多线程程序的人，都应该熟悉的最基础的问题。我们忽略了一些其他多线程实现提供的工具。它们虽然很少被用到，但是对于你的程序仍然很有必要。

阅读全文

原文链接  作者：Adrianos Dadis　译者：买蓉（sky.mairong@gmail.com）　校对：方腾飞

在高负载多线程应用中性能是非常重要的。为了达到更好的性能，开发者必须意识到并发的重要性。当我们需要使用并发时， 常常有一个资源必须被两个或多个线程共享。

在这种情况下，就存在一个竞争条件，也就是其中一个线程可以得到锁（锁与特定资源绑定），其他想要得到锁的线程会被阻塞。这个同步机制的实现是有代价的，为了向你提供一个好用的同步模型，JVM和操作系统都要消耗资源。有三个最重要的因素使并发的实现会消耗大量资源，它们是：

• 上下文切换
• 内存同步
• 阻塞

阅读全文

原文链接，译文链接，译者：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)开销，请求到达率，退避延时，数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。 阅读全文

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

1.1.2 阻塞技术

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

一个因中断或者超时的调用可能会引起数据丢失和CPU爆满。

前几天读LinkedTransferQueue（以下简称ltq)的源码，想加深下对松弛型双重队列的理解，无意中发现了这个问题:），经过仔细检查后确认了这是个bug，存在于JDK1.7.0_40和刚发布的JDK8中，去google和oracle官方似乎也没有搜索到这个问题。

重现bug：先来重现下这个bug，由于对并发线程的执行顺序预先不能做任何假设，所以很可能根本就不存在所谓的重现错误的“测试用例”，或者说这个测试用例应该是某种“执行顺序”。所以我一开始的做法是copy了一份ltq的源码，通过某个地方加自旋…但是这种方法毕竟要修改源码，后来我发现直接debug进源码就可以轻易重现bug了。 阅读全文