Java并发基础(三)：等效不可变对象CopyOnWriteArrayList

转x33g5p2x  于2021-09-22 转载在 Java  
字(9.5k)|赞(0)|评价(0)|浏览(606)

写在前面

  •  不可变类：是指一个对象一经创建就不再改变。
  • 等效不可变对象：对象基本符合不可变对象的一些特征，但是某些情况下内部状态可能会改变

1、非线程安全List

Collecrtion 集合中的ArrayList、LinkedList

2、线程安全 List

  • Collecrtion 接口中的 **Vector和Stack，**位于java.util包
  • Collections 类中的 **SynchronizedList ，**位于java.util包
  • concurrent 包中的 **CopyOnWriteArrayList，**位于java.util.concurrent包

2.1、Vector和SynchronizedList的线程安全实现方式

比较简单粗暴的实现方式，直接方法上增加 synchronized 关键字实现的，而且不管增删改查，即使是 get 方法都加上。

Vector源码：synchronized修饰方法

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

    public boolean remove(Object o) {
        return removeElement(o);
    }
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }

    public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
    }

}

SynchronizedList源码：synchronized修饰代码块

static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {
    
        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }
    
}

**get()上加同步的好处：**在 get 方法上添加同步机制也是有原因的，虽然降低了效率，但是可以让写入的数据立即可以被查询到，这也保证了数据的强一致性。

2.2、CopyOnWriteArrayList

在 JDK 并发包中，目前关于 List 的并发集合，只有 CopyOnWriteArrayList 一个

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    private transient volatile Object[] array;
    final Object[] getArray() {
        return array;
    }
    final void setArray(Object[] a) {
        array = a;
    }


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

    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

    public E get(int index) {
        return get(getArray(), index);
    }

    static final class COWIterator<E> implements ListIterator<E> {
        /** 快照 */
        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 Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

}

CopyOnWriteArrayList 类的实现思路：Copy-On-Write, 也就是写时复制策略；末尾的 ArrayList 表示数据存放在一个数组里。在对元素进行增删改时，先把现有的数据数组拷贝一份，然后增删改都在这个拷贝数组上进行，操作完成后再把原有的数据数组替换成新数组。而原来数组不变，这样就完成了更新操作。

写时复制问题：因为每次更新都是用一个新数组替换掉老的数组，如果不巧在更新时有一个线程正在读取数据，那么读取到的就是老数组中的老数据。其实这也是读写分离的思想，放弃数据的强一致性来换取性能的提升。

3、CopyOnWriteArrayList源码解析

3.1、类的属性

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    final transient ReentrantLock lock = new ReentrantLock();

    private transient volatile Object[] array;
  
    final Object[] getArray() {
        return array;
    }
  
    final void setArray(Object[] a) {
        array = a;
    }

}

可以看到CopyOnWriteArrayList源码中维护一个array对象数组用于存储集合的每个元素，并且array数组只能通过getArray和setArray方法来访问。

3.2、构造函数

CopyOnWriteArrayList 的构造函数一共有三个，一个是无参构造，直接初始化数组长度为0；另外两个传入一个集合或者数组作为参数，然后会把集合或者数组中的元素直接提取出来赋值给 CopyOnWriteArrayList 内部维护的数组。

构造函数是实例创建时调用的，没有线程安全问题，所以构造方法都是简单的赋值操作，没有特殊的逻辑处理。

新增元素

3.2.1、无参构造

public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

3.2.2、集合参数构造

// 传入一个集合，提取集合中的元素赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] es;
    if (c.getClass() == CopyOnWriteArrayList.class)
        es = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        es = c.toArray();
        if (c.getClass() != java.util.ArrayList.class)
            es = Arrays.copyOf(es, es.length, Object[].class);
    }
    setArray(es);
}

3.2.3、数组参数构造

// 传入一个数组，数组元素提取后赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

3.3、主要方法

3.3.1、新增元素 add(E e) 

元素新增根据入参的不同有好几个，但是原理都是一样的

通过一个 ReentrantLock 锁保证线程安全的。

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); // 拷贝一个数据数组，长度+1
        newElements[len] = e; // 加入新元素
        setArray(newElements); // 用新数组替换掉老数组
        return true;
    } finally {
        lock.unlock();
    }
}

分析：

  • 加锁，获取目前的数据数组开始操作（加锁保证同一时刻只有一个线程进行增/删/修操作）。
  • 获取数组并拷贝出新的数组，且长度+1。
  • 放入新的元素。
  • 用新数组替换掉老的数组。
  • finally 释放锁。

由于每次 add 时容量只增加了1，所以每次增加时都要创建新的数组进行数据复制，操作完成后再替换掉老的数据，这必然会降低数据新增时候的性能。

3.3.2、修改元素

通过 ReentrantLock 锁保证线程安全性。

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //加锁
    try {
        Object[] elements = getArray(); // 获取老数组
        E oldValue = get(elements, index); // 获取指定位置元素

        if (oldValue != element) { // 新老元素是否相等，不相等
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len); // 复制老数组
            newElements[index] = element; // 指定位置赋新值
            setArray(newElements); // 替换掉老数组
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);  // 有意思的地方来了
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

通过源码可以看到在修改元素前会先比较修改前后的值是否相等，**而在相等的情况下，依旧 setArray(elements);**为什么呢？想了解其中的原因需要了解下 volatile 的特殊作用，通过下面这个代码例子说明。

// initial conditions
int nonVolatileField = 0;
CopyOnWriteArrayList<String> list = /* a single String */

// Thread 1
nonVolatileField = 1;                 // (1)
list.set(0, "x");                     // (2)

// Thread 2
String s = list.get(0);               // (3)
if (s == "x") {
    int localVar = nonVolatileField;  // (4)
}

首先要知道 volatile 可以防止指令重排，其次要了解 happens-before 机制。说简单点就是它们可以保证代码的执行前后顺序。

比如上面例子中的代码，1 会在 2 之前执行，3 会在 4 之前执行，这都没有疑问。还有一条是 volatile 修饰的属性写会在读之前执行，所以 2会在 3 之前执行。而执行顺序还存在传递性。所以最终 1 会在 4 之前执行。这样 4 获取到的值就是步骤 1 为 nonVolatileField 赋的值。如果 CopyOnWriteArrayList 中的 set 方法内没有为相同的值进行 setArray，那么上面说的这些就都不存在了。

**个人理解：**如果源码中没有setArray()，那么多线程并发执行时，线程1可能读不到线程2在执行setArrays()方法之前做的修改，而线程1在执行setArrays()方法之前的修改对线程2有影响。

3.3.3、删除元素 remove(index)

remove 删除元素方法一共有三个，这里只看public E remove(int index) 方法，原理类似。

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁
    try {
        Object[] elements = getArray(); // 获取数据数组
        int len = elements.length;
        E oldValue = get(elements, index); // 获取要删除的元素
        int numMoved = len - index - 1;
        if (numMoved == 0) // 是否末尾
            setArray(Arrays.copyOf(elements, len - 1)); // 数据数组减去末尾元素
        else {
            Object[] newElements = new Object[len - 1]; // 把要删除的数据的前后元素分别拷贝到新数组
            System.arraycopy(elements, 0, newElements, 0, index); 
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements); // 使用新数组替换老数组
        }
        return oldValue;
    } finally {
        lock.unlock(); // 解锁
    }
}

使用 ReentrantLock 独占锁保证操作的线程安全性，然后使用删除元素后的剩余数组元素拷贝到新数组，使用新数组替换老数组完成元素删除，最后释放锁返回。

 3.3.4、获取元素 get(index）

获取下标为 index 的元素，如果元素不存在，会抛出IndexOutOfBoundsException 异常。

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

这里是没有任何的加锁操作的，而获取指定位置的元素又分为了两个步骤：

  • getArray() 获取数据数组。
  • get(Object[] a, int index) 返回指定位置的元素。

很有可能在第一步执行完成之后，步骤二执行之前，有线程对数组进行了更新操作。通过上面的分析我们知道更新会生成一个新的数组，而我们第一步已经获取了老数组，所以我们在进行 get 时依旧在老数组上进行，也就是说另一个线程的更新结果没有对我们的本次 get 生效。这也是上面提到的弱一致性问题。

4、特性

4.1、迭代器的弱一致性

List<String> list = new CopyOnWriteArrayList<>();
list.add("aaaa");
list.add("bbbb");

Iterator<String> iterator = list.iterator();
list.add("cccc");
while (iterator.hasNext()) {
    String next = iterator.next();
    System.out.println(next);
}
  aaaa
  bbbb

现在 List 中添加了元素  aaaa 和 bbbb，在拿到迭代器对象后，又添加了新元素 cccc ,可以看到遍历的结果没有报错也没有输出 cccc 。也就是说拿到迭代器对象后，元素的更新不可见。       

两个线程并发读取CopyOnWriteArrayList的情况，其中线程1需要通过iterator()方法读取数据，其中集合中的元素为元素1、元素2，但是这个时候线程2需要往集合中添加一个元素：元素3，这个时候线程2的操作是直接基于集合当前的数据进行复制一份到新的一个数组，最后将array变量指向新的一个数组。

注意思考这样的一个场景：假设线程1在遍历元素的时候，读到了元素1，但是还没有读到元素2的时候，线程2添加了元素3，这个时候线程1是无法读取到元素3的。这是因为线程1和线程2操作的数组不是同一个数组。 这也是CopyOnWriteArrayList的一个特点：弱一致性。意思就是说线程1看到的是某一时刻的一份“快照数据”，无法保证能读取到最新的数据。

4.2、fail-safe特性

提到fail-safe，会先提到fail-fast（快速失败），它是集合快速检测失败机制，防止集合不正确操作！

一般情况下，如果线程通过iterator方式循环集合时，另外一个线程也修改了这个集合，会报出java.util.ConcurrentModificationException，集合并发修改错误，

CopyOnWriteArrayList执行正常，原因是CopyOnWriteArrayList删除数据时会有集合快照。

所以他是fail-safe，而Vector是fail-fast！

4.3、新版变化

上面的源码分析都是基于 JDK 8 进行的。新版本用了 synchronized 锁替换了老的 ReentrantLock 锁。

新增：

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

修改：

public E set(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);

        if (oldValue != element) {
            es = es.clone();
            es[index] = element;
        }
        // Ensure volatile write semantics even when oldvalue == element
        setArray(es);
        return oldValue;
    }
}

5、总结

  • CopyOnWriteArrayList 采用读写分离，写时复制方式实现线程安全，具有弱一致性。
  • CopyOnWriteArrayList 因为每次写入时都要扩容复制数组，写入性能不佳。
  • CopyOnWriteArrayList 在修改元素时，为了保证 volatile 语义，即使元素没有任何变化也会重新赋值。
  • 在高版 JDK 中，得益于 synchronized 锁升级策略， CopyOnWriteArrayList 的加锁方式采用了 synchronized。

参考：https://blog.csdn.net/u013735734/article/details/109153872

CopyOnWriteArrayList 读写分离，弱一致性_duyabc的博客-CSDN博客

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/mingyuli/article/details/120384838

内容来源于网络，如有侵权，请联系作者删除！

java并发编程java集合并发

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com