计算机程序的思维逻辑 (73) - 并发容器 - 写时拷贝的List和Set

时间:2021-01-13 07:35:51

本系列文章经补充和完善,已修订整理成书《Java编程的逻辑》,由机械工业出版社华章分社出版,于2018年1月上市热销,读者好评如潮!各大网店和书店有售,欢迎购买,京东自营链接http://item.jd.com/12299018.html

计算机程序的思维逻辑 (73) - 并发容器 - 写时拷贝的List和Set


本节以及接下来的几节,我们探讨Java并发包中的容器类。本节先介绍两个简单的类CopyOnWriteArrayList和CopyOnWriteArraySet,讨论它们的用法和实现原理。它们的用法比较简单,我们需要理解的是它们的实现机制,Copy-On-Write,即写时拷贝或写时复制,这是解决并发问题的一种重要思路。

CopyOnWriteArrayList

基本用法

CopyOnWriteArrayList实现了List接口,它的用法与其他List如ArrayList基本是一样的,它的区别是:

  • 它是线程安全的,可以被多个线程并发访问
  • 它的迭代器不支持修改操作,但也不会抛出ConcurrentModificationException
  • 它以原子方式支持一些复合操作

我们在66节提到过基于synchronized的同步容器的几个问题。迭代时,需要对整个列表对象加锁,否则会抛出ConcurrentModificationException,CopyOnWriteArrayList没有这个问题,迭代时不需要加锁。在66节,示例部分代码为:

public static void main(String[] args) {
final List<String> list = Collections
.synchronizedList(new ArrayList<String>());
startIteratorThread(list);
startModifyThread(list);
}

将list替换为CopyOnWriteArrayList,就不会有异常,如:

public static void main(String[] args) {
final List<String> list = new CopyOnWriteArrayList<>();
startIteratorThread(list);
startModifyThread(list);
}

不过,需要说明的是,在Java 1.8之前的实现中,CopyOnWriteArrayList的迭代器不支持修改操作,也不支持一些依赖迭代器修改方法的操作,比如Collections的sort方法,看个例子:

public static void sort(){
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("c");
list.add("a");
list.add("b");
Collections.sort(list);
}

执行这段代码会抛出异常:

Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.concurrent.CopyOnWriteArrayList$COWIterator.set(CopyOnWriteArrayList.java:1049)
at java.util.Collections.sort(Collections.java:159)

为什么呢?因为Collections.sort方法依赖迭代器的set方法,其代码为:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}

基于synchronized的同步容器的另一个问题是复合操作,比如先检查再更新,也需要调用方加锁,而CopyOnWriteArrayList直接支持两个原子方法:

//不存在才添加,如果添加了,返回true,否则返回false
public boolean addIfAbsent(E e)
//批量添加c中的非重复元素,不存在才添加,返回实际添加的个数
public int addAllAbsent(Collection<? extends E> c)

基本原理

CopyOnWriteArrayList的内部也是一个数组,但这个数组是以原子方式被整体更新的。每次修改操作,都会新建一个数组,复制原数组的内容到新数组,在新数组上进行需要的修改,然后以原子方式设置内部的数组引用,这就是写时拷贝。

所有的读操作,都是先拿到当前引用的数组,然后直接访问该数组,在读的过程中,可能内部的数组引用已经被修改了,但不会影响读操作,它依旧访问原数组内容。

换句话说,数组内容是只读的,写操作都是通过新建数组,然后原子性的修改数组引用来实现的。我们通过代码具体来看下。

内部数组声明为:

private volatile transient Object[] array;

注意,它声明为了volatile,这是必需的,保证内存可见性,写操作更改了之后,读操作能看到。有两个方法用来访问/设置该数组:

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

在CopyOnWriteArrayList中,读不需要锁,可以并行,读和写也可以并行,但多个线程不能同时写,每个写操作都需要先获取锁,CopyOnWriteArrayList内部使用ReentrantLock,成员声明为:

transient final ReentrantLock lock = new ReentrantLock();

默认构造方法为:

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

就是设置了一个空数组。

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

代码也容易理解,add方法是修改操作,整个过程需要被锁保护,先拿到当前数组elements,然后复制了个长度加1的新数组newElements,在新数组中添加元素,最后调用setArray原子性的修改内部数组引用。

查找元素indexOf的代码为:

public int indexOf(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length);
}

也是先拿到当前数组elements,然后调用另一个indexOf进行查找,其代码为:

private static int indexOf(Object o, Object[] elements,
int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}

这个indexOf方法访问的所有数据都是通过参数传递进来的,数组内容也不会被修改,不存在并发问题。

迭代器方法为:

public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}

COWIterator是内部类,传递给它的是不变的数组,它也只是读该数组,不支持修改。

其他方法的实现思路是类似的,我们就不赘述了。

小结

每次修改都创建一个新数组,然后复制所有内容,这听上去是一个难以令人接受的方案,如果数组比较大,修改操作又比较频繁,可以想象,CopyOnWriteArrayList的性能是很低的。事实确实如此,CopyOnWriteArrayList不适用于数组很大,且修改频繁的场景。它是以优化读操作为目标的,读不需要同步,性能很高,但在优化读的同时就牺牲了写的性能。

之前我们介绍了保证线程安全的两种思路,一种是锁,使用synchronized或ReentrantLock,另外一种是循环CAS,写时拷贝体现了保证线程安全的另一种思路。对于绝大部分访问都是读,且有大量并发线程要求读,只有个别线程进行写,且只是偶尔写的场合,这种写时拷贝就是一种很好的解决方案。

写时拷贝是一种重要的思维,用于各种计算机程序中,比如经常用于操作系统内部的进程管理和内存管理。在进程管理中,子进程经常共享父进程的资源,只有在写时在复制。在内存管理中,当多个程序同时访问同一个文件时,操作系统在内存中可能只会加载一份,只有程序要写时才会拷贝,分配自己的内存,拷贝可能也不会全部拷贝,而只会拷贝写的位置所在的页,页是操作系统管理内存的一个单位,具体大小与系统有关,典型大小为4KB。

CopyOnWriteArraySet

CopyOnWriteArraySet实现了Set接口,不包含重复元素,使用比较简单,我们就不赘述了。内部,它是通过CopyOnWriteArrayList实现的,其成员声明为:

private final CopyOnWriteArrayList<E> al;

在构造方法中被初始化,如:

public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}

其add方法代码为:

public boolean add(E e) {
return al.addIfAbsent(e);
}

就是调用了CopyOnWriteArrayList的addIfAbsent方法。

contains方法代码为:

public boolean contains(Object o) {
return al.contains(o);
}

由于CopyOnWriteArraySet是基于CopyOnWriteArrayList实现的,所以与之前介绍过的Set的实现类如HashSet/TreeSet相比,它的性能比较低,不适用于元素个数特别多的集合。如果元素个数比较多,可以考虑ConcurrentHashMap或ConcurrentSkipListSet,这两个类,我们后续章节介绍。

ConcurrentHashMap与HashMap类似,适用于不要求排序的场景,ConcurrentSkipListSet与TreeSet类似,适用于要求排序的场景。Java并发包中没有与HashSet对应的并发容器,但可以很容易的基于ConcurrentHashMap构建一个,利用Collections.newSetFromMap方法即可。

小结

本节介绍了CopyOnWriteArrayList和CopyOnWriteArraySet,包括其用法和原理,它们适用于读远多于写、集合不太大的场合,它们采用了写时拷贝,这是计算机程序中一种重要的思维和技术。

下一节,我们讨论一种重要的并发容器 - ConcurrentHashMap。

(与其他章节一样,本节所有代码位于 https://github.com/swiftma/program-logic)

----------------

未完待续,查看最新文章,敬请关注微信公众号“老马说编程”(扫描下方二维码),从入门到高级,深入浅出,老马和你一起探索Java编程及计算机技术的本质。用心原创,保留所有版权。

计算机程序的思维逻辑 (73) - 并发容器 - 写时拷贝的List和Set