JUC中的CopyOnWriteArrayList

时间：2021-03-14 00:04:44 阅读：23 评论：0 收藏：0 [点我收藏+]

CopyOnWriteArrayList

Java中多线程读写List，有两种选择：

Vector
CopyOnWriteArrayList

Vector 中几乎所有读写操作都增加了synchronized，意味着在多线程环境下，如果有多个线程同时想要操作这个 Vector，必须串行排队等着前面的操作完了才能下一个。这样的效率十分低下。

CopyOnWriteArrayList 是一个线程安全的随机访问列表，实现了 List接口：

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    //...
}

CopyOnWriteArrayList源码分析

CopyOnWriteArrayList 的特点是” CopyOnWrite (写时复制)“，即在写操作时不直接操作原容器，而是复制一个副本，在副本上进行写操作，最后将原容器的引用改为这个副本。

底层实现

private transient volatile Object[] elements;

CopyOnWriteArrayList 的底层实现是一个被 violatile 修饰的数组，violatile 无法保证原子性，但是保证了可见性，在访问 volatile 变量时不会执行加锁操作，因此也就不会使执行线程阻塞，当对非 volatile 变量进行读写的时候，每个线程先从内存拷贝变量到CPU缓存中。如果计算机有多个CPU，每个线程可能在不同的CPU上被处理，这意味着每个线程可以拷贝到不同的 CPU cache 中。

而声明变量是 volatile 的，JVM 保证了每次读变量都从内存中读，跳过 CPU cache 这一步。保证了每次读取的数据都是最新的

读操作

public E get(int index) {
    return (E) elements[index];
}

直接读取数组的内容，并不阻塞，效率完全远远高于 Vector 的读操作

写操作

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();
        }
    }

ReentrantLock，它和 synchronized 的区别大致如下：

synchronized 无法中断一个正在等候获得锁的线程，也无法通过投票得到锁
ReentrantLock 拥有与 synchronized 相同的并发性和内存语义，但是添加了类似锁投票、定时锁等候和可中断锁等候的一些特性

最重要的是：为什么要写时复制？

明明写操作已经加上了锁，保障了数据的原子性，为什么还要多此一举复制原始数组呢？

可以从 CopyOnWriteArrayList源码中的内部类可以看出来

迭代器

static class CowIterator<E> implements ListIterator<E> {
        private final Object[] snapshot;
        private final int from;
        private final int to;
        private int index = 0;

        CowIterator(Object[] snapshot, int from, int to) {
            this.snapshot = snapshot;
            this.from = from;
            this.to = to;
            this.index = from;
        }

        public void add(E object) {
            throw new UnsupportedOperationException();
        }
        //...

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public void set(E object) {
            throw new UnsupportedOperationException();
        }
        //...
}

CowSubList

private static class COWSubList<E>
        extends AbstractList<E>
        implements RandomAccess
    {
        private final CopyOnWriteArrayList<E> l;
        private final int offset;
        private int size;
        private Object[] expectedArray;

        // only call this holding l‘s lock
        COWSubList(CopyOnWriteArrayList<E> list,
                   int fromIndex, int toIndex) {
            l = list;
            expectedArray = l.getArray();
            offset = fromIndex;
            size = toIndex - fromIndex;
        }

        // only call this holding l‘s lock
        private void checkForComodification() {
            if (l.getArray() != expectedArray)
                throw new ConcurrentModificationException();
        }

        // only call this holding l‘s lock
        private void rangeCheck(int index) {
            if (index < 0 || index >= size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ",Size: "+size);
        }

        public E set(int index, E element) {
            final ReentrantLock lock = l.lock;
            lock.lock();
            try {
                rangeCheck(index);
                checkForComodification();
                E x = l.set(index+offset, element);
                expectedArray = l.getArray();
                return x;
            } finally {
                lock.unlock();
            }
        }
}

可以看到 CopyOnWriteArrayList 或者它的子列表返回的迭代器不能修改列表数据，要么直接不支持写操作，要么

在读写操作前都检查了原数组是否发生改变，如果发生改变就抛出 ConcurrentModificationException 异常

Arrays.copyOf拷贝的并不是原对象的引用，所以对copy后的数组进行写操作并不会影响原数组，也就不会抛出异常，写操作完成后再更新原数组的引用为新数组