cow思想和cowList

fraternityjava 2020-06-10

近来在学习Java多线程这一知识点,在分析线程安全集合时,提到了弱一致性的CopyOnWriteList集合。书上分析源码时候说这是借鉴了copy on wirte这一思想设计的相对线程安全的List。但是对于copy on wirte这一知识点却没有详细的介绍。这篇博客就copy on write还有 CopyOnWriteList做一个详细的介绍。

写时复制(cow)

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

通过定义我们看出,写时复制是一种对于数据修改持乐观的态度的一种策略。也就是认为数据不会被频繁的更改。试想如果数据非常庞大,而且调用者又修改的非常频繁。那么仅仅复制所带来的的时间和资源消耗就是非常巨大的。并且我们还可以得知这一策略只能给调用者提供弱一致性保证。因为当调用者修改了资源时,并不会对其他调用者立即可见。他们读到的仍然是原始副本。

CopyOnWriteArrayList源码分析

我们知道,java对我们提供的线程安全的List集合有VectorCopyOnWriteArrayList,其中Vector是通过在所有的方法加synchronized这一关键字来保证同步的。因为synchronized本质上是通过内部获取独占锁来进行同步的,所以显然,当多个线程同时读List的内容时,会造成阻塞,降低效率。

实际上通过名字我们可以看出,CopyOnWriteArrayList是通过copy on write这一思想,内部通过数组实现的List集合。下面我们逐一对其增删改查系列操作进行分析。

get方法是通过三个方法联合实现的,源代码如下:

public E get(int index) {
    return get(getArray(),index);
}
//method A
public Object[] getArray() {
    return array;
}
//method B
public E get(Object[] a,int index) {
    return (E) a[index];
}

可以看出get方法没有进行任何的同步措施,显然假设当get方法执行了method A以后发生了线程切换,并且此时数据发生了修改,那么再执行method B时,尽管内部的array已经指向了新的复制数组,但是由于在get线程中,仍然在访问array之前指向的数组,并且引用计数为1不是0,所以可以安全访问。这也就是为什么访问的数据仍然是老版本的数据的原因。

下面我们来分析remove方法。需要注意的是,不同版本的java在细节可能有些不同,但是思想都是一致的。

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(array,len-1));
        }
        else {
        	//分两次复制到原数组中去
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements,0,newElements,0,index);
            System.arraycoy(elements,index+1,newElements,index,numMoved);
            setArray(newElements);
        }
        return oldValue;
    }
    finally {
        lock.unlock();
    }
}

思路其实还是蛮简单的,获取独占锁使得其他线程不能对array进行修改,然后进行数据的复制,之后再把原数组引用指向复制后的数组,这样便完成了一次写时复制操作。

其他的增加和修改操作和删除操作是一样的逻辑,都是使用内部独占锁进行数据锁定,然后进行修改,修改完毕后进行锁的释放。

相关推荐