Notes

Exploring note

0%

并发容器：都有哪些坑

发表于 更新于 分类于
本文字数： 2.9k 阅读时长 ≈ 5 分钟
同步容器与并发容器

Java1.5是synchronized分水岭

同步容器及其注意事项

Java中的容器主要可以分为四个大类，分别是List、Map、Set和Queue，但并不是所有的Java容器都是线程安全的。常用的ArrayList、HashMap就不是线程安全的。

把非线程安全的容器封装在对象内部，然后控制好访问路径，就可以将非线程安全的容器变成线程安全的容器。(面向对象思想) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SafeArrayList<T> {
    //封装ArrayList
    List<T> c = new ArrayList<>();
    //控制访问路径
    synchronized T get(int idx) {
        return c.get(idx);
    }

    synchronized void add(int idx, T t) {
        c.add(idx, t);
    }

    synchronized boolean addIfNotExist(T t) {
        if(!c.contains(t)) {
            c.add(t);
            return true;
        }
        return false;
    }
}

所有非线程安全的类都可以用这种包装的方式来实现线程安全。
Collections中提供了一套完备的包装类。 

1
2
3
List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());
Map map = Collections.synchronizedMap(new HashMap());

组合操作需要注意竞态条件问题。如addIfNotExit()方法就包含组合操作。组合操作往往隐藏着竞态条件问题，即便每个操作都能保证原子性，也并不能保证组合操作的原子性。

在容器领域一个容易被忽视的坑是用迭代器遍历容器。

在遍历的时候出现修改操作，直接抛快速失败(Fail-Fast)异常。 

1
2
3
4
List list = Collections.synchronizedList(new ArrayList());
Iterator i = list.iterator();
while(i.hasNext()) 
    foo(i.next());

通过迭代器遍历容器list，对每个元素调用foo()方法，存在并发问题。
正确的做法是，锁住list之后再执行遍历操作。Collections内部的包装类，公共方法锁的是对象的this，就是下面的list，锁住list绝对是线程安全的。 

1
2
3
4
5
6
List list = Collections.synchronizedList(new ArrayList());
synchronized (list) {
    Iterator i = list.iterator();
    while (i.hasNext())
    foo(i.next());
}

这些经过包装后线程安全的容器，都是基于synchronized这个同步关键字实现的，所以也被称为同步容器。
Java提供的同步容器还有Vector、Stack和Hashtable，这三个容器不是基于包装类实现的，但同样是基于synchronized实现的，对这三个容器的遍历，同样要加锁保证互斥。

并发容器及其注意事项

Java在1.5版本之前线程安全的容器，主要指的是同步容器，所有方法都用synchronized来保证互斥，串行度高、性能差。
Java在1.5及之后版本提供了性能更高的容器-并发容器。

依然是四大类：List、Set、Map、Queue

List

List里面只有一个实现类CopyOnWriteArrayList。
CopyOnWrite-写的时候会将共享变量新复制一份出来，读操作完全无锁。

CopyOnWriteArrayList内部维护了一个数组，成员变量array指向这个内部数组，所有的读操作都是基于array进行的。(迭代器Iterator遍历的就是array数组)。

如果在遍历array的同时，还有一个写操作(如增加元素)，CopyOnWriteArrayList会将array复制一份，然后在新复制的数组上执行增加元素的操作，执行完之后再将array指向这个新的数组。
读写是可以并行的，遍历操作一直都是基于原array执行，而写操作则是基于新array进行。

使用CopyOnWriteArrayList需要注意的坑有两个方面。

  • 应用场景，仅适用于写操作非常少的场景，而且能够容忍读写的短暂不一致。(写入的新元素并不能立刻被遍历到。)
  • 迭代器是只读的，不支持增删改。因为迭代器遍历的仅仅是一个快照，而对快照进行增删改是没有意义的。

Map

Map接口的两个实现是ConcurrentHashMap(key无序)和ConcurrentSkipListMap(key有序)。

SkipList-跳表。跳表插入、删除、查询操作平均的时间复杂度是O(logn)，性能好。

Set

Set接口的两个实现是CopyOnWriteArraySet和ConcurrentSkipListSet。

使用场景类似CopyOnWriteArrayList和ConcurrentSkipListMap。

Queue

Queue这类并发器是最复杂的，从两个维度来分类。

  • 阻塞与非阻塞。当队列已满时，入队操作阻塞；当队列已空时，出队操作阻塞。
  • 单端与双端。单端指的是只能队尾入队，队首出队；双端指的是队首队尾皆可入队出队。

Java并发包里阻塞队列队列都用Blocking关键字标识，单端队列使用Queue标识，双端队列使用Deque标识。

  • 单端阻塞队列
    ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、LinkedTransferQueue、PriorityBlockingQueue、DelayQueue。
    内部一般会持有一个队列，这个队列可以是数组(ArrayBlockingQueue)也可以是链表(LinkedBlockingQueue)；
    甚至还可以不持有队列(SynchronousQueue)，此时生产者线程的入队操作必须等待消费者线程的出队操作。
    LinkedTransferQueue融合LinkedBlockingQueue和SynchronousQueueQueue的功能，性能比LinkedBlockingQueue更好；
    PriorityBlockingQueue支持按照优先级出队；
    DelayQueue支持延时出队。

  • 双端阻塞队列
    LinkedBlockingDeque

  • 单端非阻塞队列
    ConcurrentLinkedQueue

  • 双端非阻塞队列
    ConcurrentLinkedDeque

使用队列时，需要格外注意队列是否支持有界(所谓有界指的是内部的队列是否有容量限制)。实际工作中，一般都不建议使用无界的队列，数据量大了之后很容易导致OOM。
上述Queue中，ArrayBlockingQueue和LinkedBlockedQueue是支持有界的。