小贺のBLOG

【Java并发编程】并发容器与框架

发表于 分类于
本文字数： 10k 阅读时长 ≈ 9 分钟

Java并发/多线程编程系列blog(五）并发容器与框架含ConcurrentHashMap/ConcurrentLinkedQueue/阻塞队列/Fork/Join框架

ConcurrentHashMap的实现原理与使用

线程不安全的HashMap：

HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表 形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry。

效率低下的HashTable:

为当一个线程访问HashTable的同步方法，其他线程也访问HashTable的同 步方法时，会进入阻塞或轮询状态。

ConcurrentHashMap的锁分段技术:

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的 线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

ConcurrentHashMap的结构

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重 入锁（ReentrantLock），在ConcurrentHashMap里扮演锁的角色；HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元 素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁，

类图如图所示：
Cck4h.png
结构如图所示：
Cc2Ha.png

ConcurrentHashMap的初始化

ConcurrentHashMap初始化方法是通过initialCapacity、loadFactor和concurrencyLevel等几个参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的 HashEntry数组来实现的。

初始化segments数组

源码：

1
2
3
4
5
6
7
8
9
10
11
if (concurrencyLevel > MAX_SEGMENTS) 
    concurrencyLevel = MAX_SEGMENTS; 
int sshift = 0; 
int ssize = 1; 
while (ssize < concurrencyLevel) {
    ++sshift; 
    size <<= 1; 
}
segmentShift = 32 - sshift; 
segmentMask = ssize - 1; 
this.segments = Segment.newArray(ssize);

由上面的代码可知，segments数组的长度ssize是通过concurrencyLevel计算得出的。为了能 通过按位与的散列算法来定位segments数组的索引，必须保证segments数组的长度是2的N次方），所以必须计算出一个大于或等于concurrencyLevel的最小的2的N次方值来作为segments数组的长度。假如concurrencyLevel等于14、15或16，ssize都会等于16，即容器里锁的个数也是16。concurrencyLevel的最大值是65535，这意味着segments数组的长度最大为65536， 对应的二进制是16位。

初始化segmentShift和segmentMask

这两个全局变量需要在定位segment时的散列算法里使用，sshift等于ssize从1向左移位的次数，在默认情况下concurrencyLevel等于16，1需要向左移位移动4次，所以sshift等于4。segmentShift用于定位参与散列运算的位数，segmentShift等于32减sshift，所以等于28，这里之所以用32是因为ConcurrentHashMap里的hash()方法输出的最大数是32位的，后面的测试中我们可以看到这点。segmentMask是散列运算的掩码，等于ssize减1，即15，掩码的二进制各个位的值都是1。因为ssize的最大长度是65536，所以segmentShift最大值是16，segmentMask最大值是65535，对应的二进制是16位，每个位都是1。

初始化每个segment

输入参数initialCapacity是ConcurrentHashMap的初始化容量，loadfactor是每个segment的负载因子，在构造方法里需要通过这两个参数来初始化数组中的每个segment。

1
2
3
4
5
6
7
8
9
10
if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY; 
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity) 
    ++c; 
int cap = 1; 
while (cap < c) 
    cap <<= 1; 
for (int i = 0; i < this.segments.length; ++i) 
    this.segments[i] = new Segment<K,V>(cap, loadFactor);

上面代码中的变量cap就是segment里HashEntry数组的长度，它等于initialCapacity除以ssize的倍数c，如果c大于1，就会取大于等于c的2的N次方值，所以cap不是1，就是2的N次方。segment的容量threshold＝（int）cap*loadFactor，默认情况下initialCapacity等于16，loadfactor等于0.75，通过运算cap等于1，threshold等于零。

定位Segment

既然ConcurrentHashMap使用分段锁Segment来保护不同段的数据，那么在插入和获取元素的时候，必须先通过散列算法定位到Segment。可以看到ConcurrentHashMap会首先使用Wang/Jenkins hash的变种算法对元素的hashCode进行一次再散列。

1
2
3
4
5
6
7
8
private static int hash(int h) { 
    h += (h << 15) ^ 0xffffcd7d; 
    h ^= (h >>> 10);
    h += (h << 3);
    h ^= (h >>> 6); 
    h += (h << 2) + (h << 14); 
    return h ^ (h >>> 16); 
}

之所以进行再散列，目的是减少散列冲突，使元素能够均匀地分布在不同的Segment上， 从而提高容器的存取效率 如果不进行再散列，散列冲突会非 常严重，因为只要低位一样，无论高位是什么数，其散列值总是一样。

ConcurrentHashMap通过以下散列算法定位segment:

1
2
3
final Segment<K,V> segmentFor(int hash) {
    return segments[(hash >>> segmentShift) & segmentMask]; 
}

默认情况下segmentShift为28，segmentMask为15，再散列后的数最大是32位二进制数据，向右无符号移动28位，意思是让高4位参与到散列运算中，（hash>>>segmentShift）&segmentMask的运算结果分别是4、15、7和8，可以看到散列值没有发生冲突。

ConcurrentHashMap的操作

get操作

Segment的get操作实现非常简单和高效。先经过一次再散列，然后使用这个散列值通过散列运算定位到Segment，再通过散列算法定位到元素，代码如下：

1
2
3
4
public V get(Object key) { 
    int hash = hash(key.hashCode()); 
    return segmentFor(hash).get(key, hash);
}

get操作的高效之处在于整个get过程不需要加锁，除非读到的值是空才会加锁重读。原因是它的get方法里将要使用的共享变量都定义成volatile类型

1
2
3
4
hash >>> segmentShift) & segmentMask 
// 定位Segment所使用的hash算法 
int index = hash & (tab.length - 1);
//定位HashEntry所使用的hash算法

在定位元素的代码里我们可以发现，定位HashEntry和定位Segment的散列算法虽然一样， 都与数组的长度减去1再相“与”，但是相“与”的值不一样，定位Segment使用的是元素的hashcode通过再散列后得到的值的高位，而定位HashEntry直接使用的是再散列后的值。其目的是避免两次散列后的值一样，虽然元素在Segment里散列开了，但是却没有在HashEntry里散列开。

put操作

由于put方法里需要对共享变量进行写入操作，所以为了线程安全，在操作共享变量时必 须加锁。put方法首先定位到Segment，然后在Segment里进行插入操作。插入操作需要经历两个步骤:

  • 第一步判断是否需要对Segment里的HashEntry数组进行扩容：在插入元素前会先判断Segment里的HashEntry数组是否超过容量（threshold），如果超过阈值，则对数组进行扩容。值得一提的是，Segment的扩容判断比HashMap更恰当，因为HashMap是在插入元素后判断元素是否已经到达容量的，如果到达了就进行扩容，但是很有可能扩容之后没有新元素插入，这时HashMap就进行了一次无效的扩容。在扩容的时候，首先会创建一个容量是原来容量两倍的数组，然后将原数组里的元素进行再散列后插入到新的数组里。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而只 对某个segment进行扩容。
  • 第二步定位添加元素的位置，然后将其放在HashEntry数组里

size操作

因为在累加count操作过程中，之前累加过的count发生变化的几率非常小，所以 ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小，如果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小。那么ConcurrentHashMap是如何判断在统计的时候容器是否发生了变化呢？使用modCount变量，在put、remove和clean方法里操作元素前都会将变量modCount进行加1，那么在统计size前后比较modCount是否发生变化，从而得知容器的大小是否发生变化。

ConcurrentLinkedQueue

在并发编程中，有时候需要使用线程安全的队列。如果要实现一个线程安全的队列有两种方式：

  • 一种是使用阻塞算法，
  • 另一种是使用非阻塞算法。

使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。非阻塞的实现方式则可以使用循环CAS了“wait-free”算法的方式来实现。

类图结构：
CdjwR.png

入队列

入队列过程

注意的：如果tail节点的next节点不为空，则将入队节点设置成tail节点，如果tail节点的next节点为空，则将入队节点设置成tail的next节点，所以tail节点不总是尾节点

多个线程同时进行入队的情况就变得更加复杂了，因为可能会出现其他线程插队的情况。如果有一个线程正在入队，那么它必须先获取尾节点，然后设置尾节点的下一个节点为入队节点，但这时可能有另外一个线程插队了，那么队列的尾节点就会发生变化，这时当前线程要暂停入队操作，然后重新获取尾节点。整个入队过程主要做两件事情：第一是定位出尾节点；第二是使用 CAS算法将入队节点设置成尾节点的next节点，如不成功则重试。

定位尾结点

tail节点并不总是尾节点，所以每次入队都必须先通过tail节点来找到尾节点。尾节点可能 是tail节点，也可能是tail节点的next节点。获取tail节点的next节点需要注意的是p节点等于p的next节点的情况，只有一种可能就是p节点和p的next节点都等于空，表示这个队列刚初始化，正准备添加节点，所以需要返回head节点。

设置入队节点为尾节点

p.casNext（null，n）方法用于将入队节点设置为当前队列尾节点的next节点，如果p是null，表示p是当前队列的尾节点，如果不为null，表示有其他线程更新了尾节点，则需要重新获取当 前队列的尾节点。

HOPS的设计意图

用hops变量来控制并减少tail节点的更新频率，并不是每次节点入队后都将tail节点更新成尾节点，而是当tail节点和尾节点的距离大于等于常量 HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距离越长，使用CAS更新tail节点的次数就会越少，但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长，因为循环体需要多循环一次来定位出尾节点，但是这样仍然能提高入队的效率，因为从本质上来看它通过增加对volatile变量的读操作来减少对volatile变量的写操作，而对volatile变量的写操作开销要远远大于读操作，所以入队效率会有所提升。入队方法永远返回true，所以不要通过返回值判断入队是否成功。

出队列

并不是每次出队时都更新head节点，当head节点里有元素时，直接弹出head节点里的元素，而不会更新head节点。只有当head节点里没有元素时，出队操作才会更新head节点。这种做法也是通过hops变量来减少使用CAS更新head节点的消耗，从而提高出队效率。

Java中的阻塞队列

什么是阻塞队列

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作支持阻塞的插入和移除方法：

  • 支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。
  • 支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空。

阻塞队列常用于生产者和消费者的场景，生产者是向队列里添加元素的线程，消费者是从队列里取元素的线程。阻塞队列就是生产者用来存放元素、消费者用来获取元素的容器。在阻塞队列不可用时，这两个附加操作提供了4种处理方式，如表所示:
ChQUj.png

  • 抛出异常：当队列满时，如果再往队列里插入元素，会抛出IllegalStateException（”Queue full”）异常。当队列空时，从队列里获取元素会抛出NoSuchElementException异常。
  • 返回特殊值：当往队列插入元素时，会返回元素是否插入成功，成功返回true。如果是移除方法，则是从队列里取出一个元素，如果没有则返回null。
  • 一直阻塞：当阻塞队列满时，如果生产者线程往队列里put元素，队列会一直阻塞生产者线程，直到队列可用或者响应中断退出。当队列空时，如果消费者线程从队列里take元素，队列会阻塞住消费者线程，直到队列不为空。
  • 超时退出：当阻塞队列满时，如果生产者线程往队列里插入元素，队列会阻塞生产者线程一段时间，如果超过了指定的时间，生产者线程就会退出。

这两个附加操作的4种处理方式不方便记忆，所以我找了一下这几个方法的规律。put和take分别尾首含有字母t，offer和poll都含有字母o。 注意如果是无界阻塞队列，队列不可能会出现满的情况，所以使用put或offer方法永远不会被阻塞，而且使用offer方法时，该方法永远返回true。

Java里的阻塞队列

JDK 7提供了7个阻塞队列，如下。

  • ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列:是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不保证线程公平的访问队列;
  • LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列:一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。
  • PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列:一个支持优先级的无界阻塞队列。默认情况下元素采取自然顺序升序排列。也可以自定义类实现compareTo()方法来指定元素排序规则，或者初始化 PriorityBlockingQueue时，指定构造参数Comparator来对元素进行排序。需要注意的是不能保证同优先级元素的顺序。
  • DelayQueue：一个使用优先级队列实现的无界阻塞队列:一个支持延时获取元素的无界阻塞队列。队列使用PriorityQueue来实现。队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。
  • SynchronousQueue：一个不存储元素的阻塞队列:一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作，否则不能继续添加元素。 它支持公平访问队列。默认情况下线程采用非公平性策略访问队列.
  • LinkedTransferQueue：一个由链表结构组成的无界阻塞队列:一个由链表结构组成的无界阻塞TransferQueue队列。相对于其他阻塞队列，LinkedTransferQueue多了tryTransfer和transfer方法。
  • LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列:一个由链表结构组成的双向阻塞队列。所谓双向队列指的是可以从队列的两端插入和移出元素。双向队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。相比其他的阻塞队列，LinkedBlockingDeque多了addFirst、 addLast、offerFirst、offerLast、peekFirst和peekLast等方法，以First单词结尾的方法，表示插入、获取（peek）或移除双端队列的第一个元素。以Last单词结尾的方法，表示插入、获取或移除双 端队列的最后一个元素。

Fork/Join框架

一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。

运行流程如图所示:
Ch1UT.png

工作窃取算法

工作窃取（work-stealing）算法是指某个线程从其他队列里窃取任务来执行

工作窃取的运行流程如图所示：
ChwKl.png

  • 工作窃取算法的优点：充分利用线程进行并行计算，减少了线程间的竞争。
  • 工作窃取算法的缺点：在某些情况下还是存在竞争，比如双端队列里只有一个任务时。并且该算法会消耗了更多的系统资源，比如创建多个线程和多个双端队列。

Fork/Join框架的设计

  • 步骤1 分割任务:首先我们需要有一个fork类来把大任务分割成子任务，有可能子任务还是很大，所以还需要不停地分割，直到分割出的子任务足够小。
  • 步骤2 执行任务并合并结果。分割的子任务分别放在双端队列里，然后几个启动线程分别从双端队列里获取任务执行。子任务执行完的结果都统一放在一个队列里，启动一个线程从队列里拿数据，然后合并这些数据。

Fork/Join使用两个类来完成以上两件事情:

  • ForkJoinTask：我们要使用ForkJoin框架，必须首先创建一个ForkJoin任务。它提供在任务中执行fork()和join()操作的机制。通常情况下，我们不需要直接继承ForkJoinTask类，只需要继承它的子类，Fork/Join框架提供了以下两个子类。 ·RecursiveAction：用于没有返回结果的任务。 ·RecursiveTask：用于有返回结果的任务。
  • ForkJoinPool：ForkJoinTask需要通过ForkJoinPool来执行。任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务。

使用Fork/Join框架

一个简单的需求来使用Fork/Join框架，需求是：计算1+2+3+4的结果。 使用Fork/Join框架首先要考虑到的是如何分割任务，如果希望每个子任务最多执行两个 数的相加，那么我们设置分割的阈值是2，由于是4个数字相加，所以Fork/Join框架会把这个任务fork成两个子任务，子任务一负责计算1+2，子任务二负责计算3+4，然后再join两个子任务的结果。因为是有结果的任务，所以必须继承RecursiveTask，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package Second; 
import java.util.concurrent.ExecutionException; 
import java.util.concurrent.ForkJoinPool; 
import java.util.concurrent.Future; 
import java.util.concurrent.RecursiveTask; 
public class CountTask extends RecursiveTask<Integer> { 
    private static final int THRESHOLD = 2; // 阈值 
    private int start; 
    private int end; 
    public CountTask(int start, int end) { 
        this.start = start; 
        this.end = end;
        }
    protected Integer compute() { 
        int sum = 0; // 如果任务足够小就计算任务 
        boolean canCompute = (end - start) <= THRESHOLD; 
        if (canCompute) { 
            for (int i = start; i <= end; i++) { 
                sum += i;
                } 
            
        } else {
        // 如果任务大于阈值，就分裂成两个子任务计算 
            int middle = (start + end) / 2;
            CountTask leftTask = new CountTask(start, middle); CountTask rightTask = new CountTask(middle + 1, end); // 执行子任务 
            leftTask.fork(); 
            rightTask.fork(); 
            // 等待子任务执行完，并得到其结果 int leftResult=leftTask.join(); 
            int rightResult=rightTask.join(); 
            // 合并子任务 
            sum = leftResult + rightResult;
        }
        return sum;
    }
public static void main(String[] args) { 
    ForkJoinPool forkJoinPool = new ForkJoinPool();
    // 生成一个计算任务，负责计算1+2+3+4 
    CountTask task = new CountTask(1, 4); 
    // 执行一个任务 Future<Integer> result = forkJoinPool.submit(task); 
    try { 
        System.out.println(result.get()); 
        
    } catch (InterruptedException e) { 
        
    } catch (ExecutionException e) { 
        
    } 
    
} 
}

Fork/Join框架的异常处理

ForkJoinTask在执行的时候可能会抛出异常，但是我们没办法在主线程里直接捕获异常，所以ForkJoinTask提供了isCompletedAbnormally()方法来检查任务是否已经抛出异常或已经被取消了，并且可以通过ForkJoinTask的getException方法获取异常。使用如下代码：

1
2
3
if(task.isCompletedAbnormally()) {
    System.out.println(task.getException());
}

getException方法返回Throwable对象，如果任务被取消了则返回CancellationException。如果任务没有完成或者没有抛出异常则返回null。

参考：
《Java并发编程的艺术》

如果觉得还不错的话，把它分享给朋友们吧(ง •̀_•́)ง