并发容器-CopyOnWriteArrayList juc并发容器

接上篇讲的并发中的list， 今天来聊聊CopyOnWriteArrayList。

概念

CopyOnWriteArrayList 类是JDK1.5引入的处理并发操作的容器类，他是Arraylist类的一种线程安全的变种，在并发环境下， 保证集合的读与写安全。

CopyOnWriteArrayList类是线程安全的容器，但它的安全是有一定的限制的。他的线程安全操作针对是并发环境下线程读与写安全。简单的讲, 它只能保证, 一边线程主读(遍历/获取), 一边线程主写(添加/删除/修改)操作上的安全。如果一边线程读写复合操作，另一边线程也读写复合操作，那它也无能为力啦。

案例1:CopyOnWriteArrayList 无法保证非读写模式线程安全

比如: 上篇测试例子

public class App {
 public static void main(String[] args) {
 CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
 list.add("1");
 list.add("2");
 new Thread(new Runnable() {
 public void run() {
 //集合大小
 int len = list.size();
 try {
 //睡5s
 Thread.sleep(5000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 //删除最后一个
 list.remove(len-1);
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 //清空集合
 list.clear();
 }
 }, "t2").start();
 }
}

将ArrayList换成CopyOnWriteArrayList, 依然存在数组越界问题, 原因就是上面说的CopyOnWriteArrayList仅保证一线程主读, 一线程主写, , 例子中t1线程复合操作,基友读又有写难于保证操作安全.

案例2:ConcurrentModificationException 异常解析

再看下面例子： 一个线程forEach遍历list集合， 另一线程删除list集合元素

public class App {
 public static void main(String[] args) {
 //CopyOnWriteArrayList
 final Vector<String> list = new Vector<>();
 //final ArrayList<String> list = new ArrayList<>();
 for(int i =0;i < 1000; i++){
 list.add(i+"");
 }
 new Thread(new Runnable() {
 public void run() {
 for(String s : list){
 System.out.println(s);
 }
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 for (int i = 0; i < list.size(); i++)
 {
 list.remove(i);
 }
 }
 }, "t2").start();
 }
}

使用普通的ArrayList 或者使用单操作线程安全的Vector, 多次执行,有很大概率抛出一个非常经典的线程异常:

Exception in thread "t1" java.util.ConcurrentModificationException
 at java.util.Vector$Itr.checkForComodification(Vector.java:1184)
 at java.util.Vector$Itr.next(Vector.java:1137)
 at cn.wolfcode.ch14.App$1.run(App.java:19)
 at java.lang.Thread.run(Thread.java:745)

分析:

ConcurrentModificationException 异常是Collection 集合定义一个用于限制多线程环境下集合并发修改的异常.比如: 某个线程在 Collection 上进行迭代时，另一个线程试图修改该 Collection。在这些情况下，第一线程迭代结果就不确定了。所以当检测到这种行为，迭代器选择抛出此异常。

来看下源码, 它是怎么折腾: 以ArrayList为例

ArrayList:

 public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
 //关键属性:继承自父类AbstractList
 protected transient int modCount = 0;
}

modCount 属性继承自AbstractList, 用于记录的是集合被修改(任意能导致集合结构发生变化的操作)次数, 每次修改+1.

 public boolean add(E e) {
 ensureCapacityInternal(size + 1); 
 elementData[size++] = e;
 return true;
 }
 private void ensureCapacityInternal(int minCapacity) {
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 ensureExplicitCapacity(minCapacity);
 }
private void ensureExplicitCapacity(int minCapacity) {
 modCount++;
 if (minCapacity - elementData.length > 0)
 grow(minCapacity);
 }

list集合的forEach迭代, 底层使用迭代器模式实现的, 在Arraylist内部维护了一个迭代器类

private class Itr implements Iterator<E> {
 int cursor; //迭代器游标, 指向下一个元素索引
 int lastRet = -1; // 最后一个元素索引
 int expectedModCount = modCount;
 public boolean hasNext() {
 return cursor != size;
 }
 @SuppressWarnings("unchecked")
 public E next() {
 checkForComodification();
 int i = cursor;
 if (i >= size)
 throw new NoSuchElementException();
 Object[] elementData = ArrayList.this.elementData;
 if (i >= elementData.length)
 throw new ConcurrentModificationException();
 cursor = i + 1;
 return (E) elementData[lastRet = i];
 }
 final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }
}

在list调用forEach操作时回调用iterator 方法获取迭代器对象,

public Iterator<E> iterator() {
 return new Itr();
 }

此时回将list持有的modCount赋值给itr类中的expectedModCount 属性,当使用迭代器迭代list元素时, iter.next( ) 方法会执行, 执行前调用checkForComodification 方法, 检查modCount 是否等于expectedModCount

 final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }

如果A线程在执行iter.next() 方法前, B线程对list集合做修改动作, 此时的modCount 就无法保证等于 expectedModCount , 故抛出ConcurrentModificationException异常.

回到案例, 线程t1做迭代操作, 线程t2做删除操作, 线程t2会对modCount进行修改, t1迭代器初始化的expectedModCount 属性, 肯定无法等于modCount, 所以抛出ConcurrentModificationException异常.

CopyOnWriteArrayList使用

案例中, list集合使用抛出ConcurrentModificationException阻止存在并发安全隐患的迭代. 那如果, 存在这么一场景, 线程t1只关心当前时刻持有的list集合的数据迭代. 不关心list的数据是否被修改呢?此时,可以使用CopyOnWriteArrayList作为操作的集合

public class App {
 public static void main(String[] args) {
 //final Vector<String> list = new Vector<>();
 final CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
 for(int i =0;i < 1000; i++){
 list.add(i+"");
 }
 new Thread(new Runnable() {
 public void run() {
 for(String s : list){
 System.out.println(s);
 }
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 for (int i = 0; i < list.size(); i++)
 {
 list.remove(i);
 }
 }
 }, "t2").start();
 }
}

上述案例如果使用CopyOnWriteArrayList作为迭代集合, 线程t1可以很愉快输出0~1000的数据, 它是怎么做到? 这得从CopyOnWriteArrayList原理说起.

CopyOnWriteArrayList类的设计理念，是基于一种叫Copy-On-Write(简称COW)设计思路，通俗的说就是读与写分离。具体可以看下图:

最初CopyOnWriteArrayList使用array数据存放list集合数据

当使用迭代器对CopyOnWriteArrayList进行遍历, 迭代器会给array弄一个快照,snapshot指向与array数组数据.具体代码:CopyOnWriteArrayList 源码

 public Iterator<E> iterator() {
 return new COWIterator<E>(getArray(), 0);
 }
 static final class COWIterator<E> implements ListIterator<E> {
 /** Snapshot of the array */
 private final Object[] snapshot;
 private int cursor;
 private COWIterator(Object[] elements, int initialCursor) {
 cursor = initialCursor;
 snapshot = elements;
 }
}

此时, 如果有其它线程对相同的list做写操作, 比如add元素

CopyOnWriteArrayList 将array复制一份赋值个newElments,然后在新的数组中做写操作, 操作结束后, 让array重新指向新数组.

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 Object[] getArray() {
 return array;
 }
 final void setArray(Object[] a) {
 array = a;
 }

注意观察, 在写操作时, 使用lock.lock();进行加锁, 保证写安全.

回到上面案例, 线程t1在迭代时一直使用的最初的array快照snapshot, 线程t2的写操作修改的都是新的array对snapshot没有任何影响, 所以可以从0打印到999

存在问题

最后说下CopyOnWriteArrayList 的局限性:

1>每次写操作都需要复制, 内存占用比重高, 不适宜操作大量数据

2>无法保证数据实时一致, 只能保证最终数据一致.

所以CopyOnWriteArrayList 在读远大于写的场合使用才有一定意义.

本文作者：叩丁狼教育王一飞老师。