JUC高并发容器-CopyOnWriteArrayList

JUC高并发容器

线程安全的同步容器类

  Java同步容器类通过Synchronized(内置锁)来实现同步的容器，比如Vector、HashTable以及SynchronizedList等容器。线程安全的同步容器类主要有Vector、Stack、HashTable等。另外，Java还提供了一组包装方法，将一个普通的基础容器包装成一个线程安全的同步容器。

  例如通过Collections.synchronized包装方法能将一个普通的SortedSet容器包装成一个线程安全的SortedSet。

  1.通过synchronizedSortedSet静态方法包装出一个同步容器

public class CollectionsDemo {
    public static void main(String[] args) throws InterruptedException {
        //创建一个基础的有序集合
        SortedSet<String> elementSet=new TreeSet<>();
        //增加元素
        elementSet.add("element 1");
        elementSet.add("element 2");

        //将element包装成一个同步容器
        SortedSet<String> sortedSet = Collections.synchronizedSortedSet(elementSet);
        //输出容器中的元素
        System.out.println("SortedSet is :"+sortedSet);
        CountDownLatch latch = new CountDownLatch(5);
        ExecutorService pool = Executors.newFixedThreadPool(10);
        for (int i = 0; i < 5; i++) {
            int finalI=i;
            pool.submit(()->{
                //向同步容器中增加一个元素
                sortedSet.add("element "+(3+finalI));
                System.out.println("add element"+(3+finalI));
                latch.countDown();
            });
        }
        latch.await();
        //输出容器中的元素
        System.out.println("SortedSet is :"+sortedSet);
    }
}
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

  2.java.util.Collections所提供的同步包装方法

  java.util.Collections还提供了一系列对其他的基础容器进行同步包装的方法，如synchronizedList()方法将基础List包装成线程安全的列表容器，synchronizedMap()方法将基础Map容器包装成线程安全的容器,synchronizedCollection()方法将基础Collection容器包装成线程安全的Collection容器。

  同步包装方法如下：

  与同步包装方法相对应，java.util.Collections还提供了一系列同步包装类，这些包装类都是其内部类。这些同步包装类的实现逻辑很简单：实现了容器的操作接口，在操作接口上使用synchronized进行线程同步，然后在synchronized的临界区将实际的操作委托给被包装的基础容器。

  3.同步容器面临的问题

  可以通过查看Vector、HashTable、java.util.Collections同步包装类的源码，发现这些同步容器实现线程安全的方式是：在需要同步访问的方法上添加synchronized关键字。

  synchronized在线程没有发生争用的场景下处于偏向锁的状态，其性能非常高。但是，一旦发生了线程争用，synchronized会由偏向锁膨胀成重量级锁，在抢占和释放时发生CPU内核态与用户态切换，所以削弱了并发性，降低了吞吐量，而且会严重影响性能。

  因此，为了解决同步容器的性能问题，有了JUC高并发容器。

什么是高并发容器？

  JUC高并发容器是基于非阻塞算法(或者无锁编程算法)实现的容器类，无锁编程算法主要通过CAS(Compare And Swap)+volatile组合实现，通过CAS保障操作的原子性，通过volatile保障变量内存的可见性。无锁编程算法的主要优点如下：

• 开销较小：不需要在内核态和用户态之间切换进程。
• 读写不互斥：只有写操作需要使用基于CAS机制的乐观锁，读读操作之间可以不用互斥。

1.List

  JUC包中的高并发List主要有CopyOnWriteArrayList,对应的基础容器为ArrayList。

  CopyOnWriteArrayList相当于线程安全的ArrayList，它实现了List接口。在读多写少的场景中，其性能远远高于ArrayList的同步包装容器。

2.Set

  JUC包中的Set主要有CopyOnWriteArraySet和ConcurrentSkipListSet。

• CopyOnWriteArraySet继承自AbstractSet类，对应的基础容器为HashSet。其内部组合了一个CopyOnWriteArrayList对象，它的核心操作是基于CopyOnWriteArrayList实现的。
• ConcurrentSkipListSet是线程安全的有序集合，对应的基础容器为TreeSet。它继承自AbstractSet，并实现了NavigableSet接口。ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的。

3.Map

  JUC包中Map主要有ConcurrentHashMap和ConcurrentSkipListMap。

• ConcurrentHashMap对应的基础容器为HashMap。JDK6中的ConcurrentHashMap采用一种更加细粒度的分段锁加锁机制，JDK8基于Synchronized+CAS实现。
• ConcurrentSkipListMap对应的基础容器为TreeMap。其内部的Skip List(跳表)结构是一种可以代替平衡树的数据结构，默认是按照Key值升序的。

4.Queue

  JUC包中的Queue的实现类包括三类：单向队列、双向队列和阻塞队列。

• ConcurrentLinkedQueue是基于列表实现的单向队列，按照FIFO(先入先出)原则对元素进行排序。新元素从队列尾部插入，而获取队列元素则需要从队列头部获取。
• ConcurrentLinkedDeque是基于链表的双向队列，但是该队列不允许null元素。作为双向队列，ConcurrentLinkedDeque可以当作“栈”来使用，并且高效地支持并发环境。

  JUC还扩展了队列，增加了可阻塞地插入和获取等操作，提供了一组阻塞队列，具体如下：

• ArrayBlockingQueue:基于数组实现的可阻塞地FIFO队列。
• LinkedBlockingQueue:基于链表实现的可阻塞的FIFO队列。
• PriorityBlockingQueue:按优先级排序的队列。
• DelayQueue:按照元素的Delay时间进行排序的队列。
• SynchronousQueue:无缓冲等待队列。

CopyOnWriteArrayList

   前面讲到，Collections可以将基础容器包装为线程安全的同步容器，但是这些同步容器包装类在进行元素迭代时并不能进行元素添加操作。

  (1)CopyOnWriteArrayList原理：

  CopyOnWrite(写时复制)就是在修改器对一块内存进行修改时，不直接在原有内存块上进行写操作，而是将内存复制一份，在新的内存中进行写操作，写完之后，再将原来的指针(或者引用)指向新的内存，原来的内存被回收。

  CopyOnWriteArrayList是写时复制思想的一种典型实现，其含有一个指向操作内存的内部指针array，而可变操作(add、set等)是在array数组的副本上进行的。当元素需要被修改或者增加时，并不直接在array指向的原有数组上操作，而是首先对array进行一次复制，将修改的内容写入复制的副本中。写完之后，再将内部指针array指向新的副本，这样就可以确保修改操作不会影响访问器的读取操作。原理如下图所示：

  通俗地说：读操作不会被写操作阻塞，读操作返回的结果可能不是最新的，适合读多写少的场景。

  (2)CopyOnWriteArrayList读取操作：

  访问器的读取操作没有任何同步控制和锁操作，理由是内部数组array不会发生修改，只会被另一个array替换，因此可以保证数据安全。

//操作内存的引用 
private transient volatile Object[] array;
public E get(int index) {
        return get(getArray(), index);
}
//获取元素
private E get(Object[] a, int index) {
        return (E) a[index];
}
//返回操作内存
final Object[] getArray() {
        return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

  (3)CopyOnWriteArrayList写入操作

  CopyOnWriteArrayList的写入操作add()方法在执行时加了独占锁以确保只能有一个线程进行写入操作，避免多线程写的时候会复制出多个副本。

  这块给出的都是部分源代码，API中重载方法很多

 public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();	//加锁
        try {
            Object[] elements = getArray();
            int len = elements.length;
         	 //复制新数组
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();	//释放锁
        }
 }
 final void setArray(Object[] a) {
        array = a;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

  从add()操作可以看出，在每次进行添加操作时，CopyOnWriteArrayList底层都是重新复制一份数组，再往新的数组中添加新元素，待添加完了，再将新的array引用指向新的数组。当add()操作完成后，array的引用就已经指向另一个存储空间了。

   既然每次添加元素的时候都会重新复制一份，那就增加了内存的开销，如果容器的写操作比较频繁，那么其开销就比较大。所以，在实际应用中，CopyOnWriteArrayList并不适合进行添加操作。但是在并发场景下，迭代操作比较频繁，CopyOnWriteArrayList就是一个不错的选择。

  (4)CopyOnWriteArrayList迭代器实现

  CopyOnWriteArrayList有自己的迭代器，该迭代器不会检查修改状态，也无需检查状态。因为被迭代的array数组可以说是只读的，不会有其他线程能够修改它。

 static final class COWIterator<E> implements ListIterator<E> {
        //数组的快照(snapshot)
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
				//下一个元素
        public boolean hasNext() {
            return cursor < snapshot.length;
        }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  迭代器的快照成员会在构造迭代器的时候使用CopyOnWriteArrayList的array成员去初始化，具体如下：

//获取迭代器 
public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
 }
//返回操作内存
 final Object[] getArray() {
     return array;
 }
1
2
3
4
5
6
7
8

  总结：

  1.CopyOnWriteArrayList的优点：

  读取、遍历操作不需要同步，速度会非常快。所以CopyOnWriteArrayList适用于读操作多、写操作相对较少的场景(读多写少)，比如可以在进行“黑名单”拦截时使用CopyOnWriteArrayList。

  2.CopyOnWriteArrayList与ReentrantReadWriteLock的比较

  CopyOnWriteArrayList和ReentrantReadWriteLock读写锁的思想非常类似，即读读共享、写写互斥、读写互斥、写读互斥。但是前者相比后者更进一步：为了将读取的性能发挥到极致，CopyOnWriteArrayList读取是完全不用加锁的，而且写入也不会阻塞读取操作，只有写入和写入之间需要进行同步等待，读操作的性能得到大幅提升。