【杂谈】对CopyOnWriteArrayList的认识

时间:2023-01-24 03:10:06

前言

  之前看《Java并发编程》这本书的时候,有看到这个,只记得"读多写少"、"写入时复制"。书中没有过多讲述,只是一笔带过(不过现在回头看,发现讲的都是精髓。老外的书大多重理论,喜欢花大篇幅讲概念,这点我非常喜欢)记得当时是觉得可能有点难,先跳过了,结果就忘记回头看了。今天突然想起来,就看了一下,整理一点东西。

非线程安全的ArrayList

我们知道原来util包中的ArrayList是不提供同步的,也就是说当多个线程读写ArrayList的时候可能出现线程安全问题。例如,就add操作而言

ArrayList的add方法:

【杂谈】对CopyOnWriteArrayList的认识

我们把elementData[size++] = e 分为两步:

  • elementData[size]=e
  • size++

如果调用两次add操作,期待结果应该是这样的:

【杂谈】对CopyOnWriteArrayList的认识

但是,如果存在两个线程A、B几乎同时操作add方法,由于无法保证add操作的原子性,实际操作时序可能如下。

【杂谈】对CopyOnWriteArrayList的认识

那么,对应的结果就会是这样:

【杂谈】对CopyOnWriteArrayList的认识

这里就发生大问题了,e1被后续添加的e2覆盖。e1丢失,而size却仍旧递增两位。

线程安全的ArrayList——SynchronizedList

Collections实用类(注意,不是Collection接口)提供同步容器包装,将普通的集合包装成线程安全的集合。

例如,通过Collections.synchronizedList(List<T>)方法,可以把一个非线程安全的List集合变为线程安全的集合。

这里其实是一个装饰器模式的应用,参数集合List将被装饰为SynchronizedList。

【杂谈】对CopyOnWriteArrayList的认识

其是Collections的内部类。

【杂谈】对CopyOnWriteArrayList的认识

通过对每个方法调用都进行同步加锁,使得多个线程读写ArrayList只能按序进行。这样的话,数据的安全性和一致性都得到了保证。

缺点也非常明显,每个线程读写ArrayList都需进行同步,开销大。

迭代过程中的异常 —— ConcurrentModificationException 

在ArrayList的实现中,其迭代器实现了一个方法checkForComodification 这个方法会检查迭代期间是否有其他线程修改了集合,如果有,则抛出ConcurrentModificationException

原理

主要跟两个字段有关:

  • expectedModCount(来自ArrayList的迭代器Itr)
  • modCount(来自ArrayList的父类AbstractList,初始为0)。

ArrayList实现中,每执行一次添加操作,都会让modCount+1

注意:addAll也是让modCount+1,与添加的元素个数无关。remove和set操作不算,其不会让modCount有所改变。

【杂谈】对CopyOnWriteArrayList的认识

【杂谈】对CopyOnWriteArrayList的认识

ArrayList的迭代器中,expectedModCount的初始值被设定为modCount

【杂谈】对CopyOnWriteArrayList的认识

迭代器在每次遍历时,会调用checkForComodification 检查状态,如果此过程中集合发生了改动,则直接抛出异常。

【杂谈】对CopyOnWriteArrayList的认识

【杂谈】对CopyOnWriteArrayList的认识

注:如果迭代期间需要修改集合,只能通过迭代器的方法修改集合,这些方法不会触发异常。因为其会重置expectedModCount的值为当前modCount。

如何防止迭代过程出现异常?

所以,在使用这样的ArrayList时,如果需要对其进行迭代,则需要对容器进行加锁(或者拷贝一份),使当前线程对其独占访问,以保证其迭代过程能够正常运行。如下:

public class SomeClass {
List<E> list; public SomeClass(List<E> list) {
this.list = list;
} //如果这个方法会被多线程访问,那么最好对list的访问进行加锁
public void function() {
synchronized(list) {
for(E e:list) {
....
}
}
}
}

线程安全的另一种实现类——CopyOnWriteArrayList

CopyOnWriteArrayList同样是线程安全的ArrayList,但是与SynchronizedList不同的是,它只对写操作加锁,对读操作不加锁。关键是,其在迭代期间不需要对容器进行加锁或复制。这一切都与"写入时复制"有关。

写入时复制的原理

【杂谈】对CopyOnWriteArrayList的认识

CopyOnWriteArrayList的字段:

  • lock => 锁,写操作时需要
  • array => 容器数组的引用。指向存储当前元素的数组。

与容器数组引用直接相关的两个方法:

【杂谈】对CopyOnWriteArrayList的认识

写入时复制相关代码:

public boolean add(E e) {
final ReentrantLock lock = this.lock;
//写操作还是要上锁的,此锁是全局锁
lock.lock();
try {
//获取容器数组
Object[] elements = getArray();
//获得容器长度
int len = elements.length;
//创建一个新的存储空间,容量+1
Object[] newElements = Arrays.copyOf(elements, len + 1);
//在新的存储空间内,加入新元素
newElements[len] = e;
//修改当前容器数组的引用
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}

当add操作完成后,array的引用就已经指向另一个存储空间了。 这里也暴露了一个缺点:如果此容器的写操作比较频繁,那么其开销就比较大。

迭代器实现

CopyOnWriteArray有自己的迭代器,该迭代器不会检查修改状态,也无需检查状态。因为迭代的数组是可以说是只读的,不会有其他线程能够修改它。

【杂谈】对CopyOnWriteArrayList的认识

迭代器,引用的数组变量名就叫snapshot(快照)。也从另一个角度说明,在迭代器迭代过程中,其使用的是容器的过去一个版本,一个快照。不能保证是当前容器的状态。

【杂谈】对CopyOnWriteArrayList的认识

这里也暴露了一个缺点:不能保证数据的瞬时一致性。

但是,其有一个显著的优点,那就是读操作,和遍历操作不需要同步。多线程访问的时候,速度较高。

CopyOnWriteArrayList应用场景

  由以上的优缺点可得,CopyOnWriteArrayList应用的场景,最好是读操作多,写操作相对较少的场景("读多写少")。也就是说,集合内容不会经常变动的。例如,网上常说的"黑名单"这类东西。