专栏首页拭心的安卓进阶之路并发编程6:CopyOnWriteArrayList 的写时复制

并发编程6:CopyOnWriteArrayList 的写时复制

首先提个问题:

  • 线程安全的 List 集合有什么?
  • CopyOnWriteArrayList 的特点以及使用场景?

如果这个问题你答不上来,那这篇文章可能就对你有些价值。

CopyOnWriteArrayList 简介

在 Java 中多线程读写 List,有两种选择:

  1. Vector
  2. CopyOnWriteArrayList

Java 集合深入理解:古老的 Vector 中我们了解到 Vector 几乎所有的读写操作都加了 synchronized ,意味着在多线程环境下,如果有多个线程同时想要操作这个 Vector,必须串行排队等着前面的操作完了才能下一个。

就好比我和小肉一起写一个项目,每次得等她完全写完要写的,我才能接着写,这效率实在差了点。

好在有 Git,小肉想帮我修改程序员审美 UI 时,可以拷贝一份代码进行修改,修改完后再合并到远程。

Git 多人协作流程: 当有人要修改代码时,拉取服务端代码到本地,先修改本地的代码,然后再提交到服务器,这样可以避免直接修改远端代码对别人造成的影响。

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

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

它的思想和 Git 有些相似,即使在多个线程中被并发访问, CopyOnWriteArrayList 的读操作(比如 get())也不会阻塞其他操作;写操作则是通过复制一份,对复制版本进行操作,不会影响原来的数据。

Vector 相对效率提高不少。缺点就是可能读取的不是最新的值。

批量操作(比如 addAll(), clear())是原子的,也就是说不存在重排序导致的未赋值就访问等情况。

Java 集合源码解析:Iterator 中我们了解到:

在调用迭代器的 next,remove 方法时都会比较 expectedModCount 和 modCount 是否相等,如果不相等就会抛出 ConcurrentModificationException ,也就是成为了 fail-fast。

如果需要在遍历时操作列表,其中一种解决办法就是使用 CopyOnWriteArrayList ,它的迭代器永远不会抛出 ConcurrentModificationException异常。原因在于:在创建一个迭代器时,它会拷贝一份列表数据,这样即使操作列表也不会影响迭代器,缺点和前面一样,可能无法反映数据的最新状态。

CopyOnWriteArrayList 源码分析(Android SDK 25)

从名字就可以看出来 CopyOnWriteArrayList 的特点是 “CopyOnWrite”(写时复制),即在写入新元素时不直接操作原容器,而是先复制一个快照,对这个快照进行操作,在操作结束后再将原容器的引用指向新引用。

底部实现

private transient volatile Object[] elements;

CopyOnWriteArrayList 底层也是一个数组,不同之处在于它被 volatile 修饰,对它的修改、读取具有“可见性”、“有序性”(但不保证原子性),因此可以不加同步块,直接读取。

有三种构造函数:

public CopyOnWriteArrayList() {
    elements = EmptyArray.OBJECT;
}

@SuppressWarnings("unchecked")
public CopyOnWriteArrayList(Collection<? extends E> collection) {
    this((E[]) collection.toArray());
}

public CopyOnWriteArrayList(E[] array) {
    this.elements = Arrays.copyOf(array, array.length, Object[].class);
}

分别创建了空的数组、使用指定集合和数组来创建新数组。

读取操作

先看简单的几个读取操作:

public int size() {
    return elements.length;
}

@SuppressWarnings("unchecked")
public E get(int index) {
    return (E) elements[index];
}
public boolean isEmpty() {
    return elements.length == 0;
}

就是直接读取数组的内容,简单粗暴,快速高效。

修改操作

读取时轻松,但修改时就需要做同步操作了。先看添加元素 add()

public synchronized boolean add(E e) {
    Object[] newElements = new Object[elements.length + 1];
    System.arraycopy(elements, 0, newElements, 0, elements.length);
    newElements[elements.length] = e;
    //这步执行前,其他线程访问的就是旧数据
    elements = newElements;
    return true;
}

public synchronized void add(int index, E e) {
    Object[] newElements = new Object[elements.length + 1];
    System.arraycopy(elements, 0, newElements, 0, index);
    newElements[index] = e;
    System.arraycopy(elements, index, newElements, index + 1, elements.length - index);
    elements = newElements;
}

可以看到,在添加元素时调用 System.arraycopy() 拷贝了一个新数组,然后添加进去元素,最后将原数组的引用修改为拷贝数组。

如果其他线程在“原始数组引用更新”之前读取数据,那它访问到的就是旧数据。

方法被 synchronized 修饰,因此在这个过程中,其他调用这个方法的线程都会阻塞等待,只有这个方法结束后才有获得锁的机会。

set() 方法也是类似的:

public synchronized E set(int index, E e) {
    Object[] newElements = elements.clone();
    @SuppressWarnings("unchecked")
    E result = (E) newElements[index];
    newElements[index] = e;
    elements = newElements;
    return result;
}

删除操作 `remove() 也是类似:

public synchronized E remove(int index) {
    @SuppressWarnings("unchecked")
    E removed = (E) elements[index];
    removeRange(index, index + 1);
    return removed;
}

public synchronized boolean remove(Object o) {
    int index = indexOf(o);
    if (index == -1) {
        return false;
    }
    remove(index);
    return true;
}
private void removeRange(int from, int to) {
    Object[] newElements = new Object[elements.length - (to - from)];
    System.arraycopy(elements, 0, newElements, 0, from);
    System.arraycopy(elements, to, newElements, from, elements.length - to);
    elements = newElements;
}

迭代器

public Iterator<E> iterator() {
    Object[] snapshot = elements;    //读取的是快照
    return new CowIterator<E>(snapshot, 0, snapshot.length);
}

//读取的也是快照,并且不支持 remove() 
public ListIterator<E> listIterator(int index) {
    Object[] snapshot = elements;
    if (index < 0 || index > snapshot.length) {
        throw new IndexOutOfBoundsException("index=" + index + ", length=" + snapshot.length);
    }
    CowIterator<E> result = new CowIterator<E>(snapshot, 0, snapshot.length);
    result.index = index;
    return result;
}

/**
 * Equivalent to {@code listIterator(0)}.
 */
public ListIterator<E> listIterator() {
    Object[] snapshot = elements;
    return new CowIterator<E>(snapshot, 0, snapshot.length);
}

返回的迭代器是 CowIterator,实现了 ListIterator 接口:

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

可以看到 CopyOnWriteArrayList 或者它的子列表返回的迭代器不能修改列表数据,尤其是 Iterator.remove(), ListIterator.add(), ListIterator.set() 方法都会抛出 UnsupportedOperationException 异常。

CopyOnWriteArrayList 源码 JDK8 有什么不同

看完 android-25 的 CopyOnWriteArrayList 代码,再去看 JDK8 的,发现两者差别有点大啊,真是坑。

在知乎的一个问题下了解了 Android SDK 的 Java 源码为什么和 JDK 不一致,摘抄如下:

Android 使用的Java 库是Apache的Harmony, 与官方Java库接口相同,里面实现不一样。 就在06年的时候Sun公司宣布会将JDK开源,但是直到2009年4月才正式发布,而Android已经在2008年发布第一步部智能手机了。所以Google最早的时候使用了当时Apache的Java开源实现Harmony项目。 可惜Sun公司一直不承认Harmony,前不久Harmony那一帮人怒了,给Oracle放狠话说再不承认我我就抵制Java7,结果反倒把Google吓坏了,于是就出现了google宣布切换到openjdk上这条新闻。在Android N上,已经切换到OpenJDK了;基本可以认为Android SDK下的源码与JDK相同。 作者:weishu 链接:https://www.zhihu.com/question/40103672/answer/84730730 来源:知乎

JDK8 中的 CopyOnWriteArrayList 底层实现也是数组,不同之处在于使用 Lock 而不是 synchronized 进行同步:

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

    //锁住所有修改操作
    final transient ReentrantLock lock = new ReentrantLock();

    //只能被getArray/setArray 访问
    private transient volatile Object[] array;
    //...
}

构造函数也有些区别:

final void setArray(Object[] a) {
    array = a;
}

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

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

在使用集合作为参数构造时,做了一些优化:如果这个集合也是 CopyOnWriteArrayList,就直接指向该集合的数组;否则复制一下。

读取操作没什么变化,都是读的数组,不同之处在于通过 getter 方法包了一层:

public int size() {
    return getArray().length;
}

public boolean isEmpty() {
    return size() == 0;
}

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

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

添加操作 add()

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 相同的并发性和内存语义,但是添加了类似锁投票、定时锁等候和可中断锁等候的一些特性

摘自:http://blog.csdn.net/fw0124/article/details/6672522

删除操作也差不多:

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

总结

核心思想就两点:

  1. 底部实现(这里是数组) volatile 修饰,保证一致性
  2. 写时复制,写完更新引用

有了这两点,我们自己写个 CopyOnWriteHashMap 也是分分钟的事,有兴趣可以自己写一下。

优缺点

优点:

  • 可以在多线程环境下操作 List
  • 读的效率很高

缺点:

  • 读的可能不是最新值
  • 每次写需要创建个新数组,占用额外内存

可以看到,应该在并发读远大于并发写的情况下使用这个容器,比如保存缓存数据。

类似的思想还有个 CopyOnWriteArraySet

Thanks

http://ifeve.com/java-copy-on-write/ http://blog.csdn.net/fw0124/article/details/6672522 http://coolshell.cn/articles/11175.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 5分钟了解《代码整洁之道》精华

    版权声明:转载前请留言获得作者许可,转载后标明作者 张拭心 与 原文链接。大家都是成年人,创作不易,感谢您的支持! ...

    张拭心 shixinzhang
  • Java 集合深入理解(8):AbstractSequentialList

    今天有点无聊,来学学 AbstractSequentialList 解解闷 吧! AbstractSequentialList 没有什么特别的,这里介绍是为了...

    张拭心 shixinzhang
  • Java 集合深入理解(5):AbstractCollection

    今天好累,来学学 AbstractCollection 吧! ? 什么是 AbstractCollection AbstractCollection 是 Ja...

    张拭心 shixinzhang
  • go io.Writer 将os.Stdout 输出到控制台改为 string

    在使用模版的时候, 使用os.Stdout,只能输出到控制台,但是我又想将获得的输出模版变成字符串,在其他地方使用。

    solate
  • [译] 使用 microbundle 打包 TypeScript 组件库

    原文:https://codewithhugo.com/microbundle-typescript-npm-module/

    江米小枣
  • c# Marshal

    sofu456
  • TIOBE 6月编程语言排行榜:C语言仍为榜首,Rust首冲前20

    截止目前,Rust已经连续5年被Stackoverflow的用户评为“最受喜爱的编程语言”。

    老九君
  • 简谈快速排序

    Jacklin
  • Java 枚举7常见种用法

    Tanyboye
  • Java枚举(enum)七种常见的用法

    DK1.5引入了新的类型——枚举。在 Java 中它虽然算个“小”功能,却给我的开发带来了“大”方便。 用法一:常量 在JDK1.5 之前,我们定义常量都是:...

    Spark学习技巧

扫码关注云+社区

领取腾讯云代金券