mojinhui33
0%

CopyOnWriteArrayList

发表于 分类于

CopyOnWriteArrayList

COW:写时复刻——来优化子进程的使用效率

维基百科

写入时复制（英语：Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被建立，因此多个调用者只是读取操作时可以共享同一份资源。

Linux、Redis、文件系统都有用到

线程安全的Vector和SynchronizedList

  • Vector是线程安全的容器。几乎每个方法声明处都加了synchronized关键字来使容器安全
  • Collections.synchronizedList(new ArrayList())来使ArrayList变成是线程安全的话，也几乎每个方法都加上synchronized关键字，只不过它不是加在方法的生命处，而是方法的内部

基本结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   final transient Object lock = new Object();

   private transient volatile Object[] array;

   final Object[] getArray() {
       return array;
   }

   final void setArray(Object[] a) {
       array = a;
   }
//初始化CopyOnWriterArrayList相当于初始化数组
   public CopyOnWriteArrayList() {
       setArray(new Object[0]);
   }

看起来很简单，ConpyOnWriterArrayList底层就是数组，加锁就交给ReentrantLock来完成

常用方法的实现

如果遍历Vercotr/SynchronizedList是需要自己手动加锁的

CopyOnWriterArrayList使用迭代器遍历时不需要显示枷锁

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;

        // 将volatile Object[] array 的指向替换成新数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

与后面版本可能有变化

我们可以知道：再添加的时候就上锁，并复制一个新数组，增加操作在新数组上完成，最后解锁

写加锁，读不加锁

总结

再用迭代器遍历时，操作的是原数组

缺点

  • 内存占用：如果CopyOnWriterArrayList经常要增删改里面的数据，比较耗费内存
  • CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性

CopyOnWriteArraySet的原理就是CopyOnWriteArrayList。