天天看點
傳回

java并發之CopyOnWriteArrayList

java并發之CopyOnWriteArrayList

目錄

概述

成員屬性

構造方法

添加元素

擷取元素

修改元素

删除元素

疊代器

總結

set方法細節

​ 我在前面總結了Java集合中ArrayList的源碼細節，其中也提到了ArrayList是線程不安全的(沒有做任何的同步保證)，也說到了fast-fail機制以及多線程下使用ArrayList的異常問題。當然也包括單線程下使用不當：這裡主要展現在使用增加for循環周遊的時候在循環體内進行add/remove操作導緻的modCount和ArrayList的疊代器中expectModCount值不一緻導緻異常抛出問題。

​ 那麼jdk中為我們提供的線程安全的List是什麼呢，就是下面要說的CopyOnWriteList這個并發安全的集合類，它主要采用的就是copy-on-write思想，個人了解的這個思想核心大概就是讀寫分離：讀時共享、寫時複制(原本的array)更新(且為獨占式的加鎖)，而我們下面分析的源碼具體實作也是這個思想的展現。

​ 那先看看CopyOnWriteList集合的特點：是線程安全的集合類、對其進行修改都是在底層的數組副本上進行的，更新之後利用volatile的可見性保證别的線程可以看到更新後的數組。

回到頂部

​ 還是先貼上CopyOnWriteList的繼承體系吧，可以看到其實作了Serializable、Cloneable和RandomAccess接口，具有随機通路的特點，實作了List接口，具備List的特性。

​ 我們單獨看一下CopyOnWriteList的主要屬性和下面要主要分析的方法有哪些。從圖中看出：

每個CopyOnWriteList對象裡面有一個array數組來存放具體元素

使用ReentrantLock獨占鎖來保證隻有寫線程對array副本進行更新。關于ReentrantLock可以參考我另一篇AQS的應用之ReentrantLock。

CopyOnWriteArrayList在周遊的使用不會抛出ConcurrentModificationException異常，并且周遊的時候就不用額外加鎖

下面還是主要看CopyOnWriteList的實作

//這個就是保證更新數組的時候隻有一個線程能夠擷取lock，然後更新

final transient ReentrantLock lock = new ReentrantLock();

//使用volatile修飾的array，保證寫線程更新array之後别的線程能夠看到更新後的array.

//但是并不能保證明時性：在數組副本上添加元素之後，還沒有更新array指向新位址之前，别的讀線程看到的還是舊的array

private transient volatile Object[] array;

//擷取數組，非private的，final修飾

final Object[] getArray() {

return array;

}

//設定數組

final void setArray(Object[] a) {

array = a;

(1)無參構造，預設建立的是一個長度為0的數組

//這裡就是構造方法，建立一個新的長度為0的Object數組

//然後調用setArray方法将其設定給CopyOnWriteList的成員變量array

public CopyOnWriteArrayList() {

setArray(new Object[0]);

(2)參數為Collection的構造方法

//按照集合的疊代器周遊傳回的順序，建立包含傳入的collection集合的元素的清單

//如果傳遞的參數為null，會抛出異常

public CopyOnWriteArrayList(Collection<? extends E> c) {

Object[] elements; //一個elements數組
//這裡是判斷傳遞的是否就是一個CopyOnWriteArrayList集合
if (c.getClass() == CopyOnWriteArrayList.class)
    //如果是，直接調用getArray方法，獲得傳入集合的array然後指派給elements
    elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
    //先将傳入的集合轉變為數組形式
    elements = c.toArray();
    //c.toArray()可能不會正确地傳回一個 Object[]數組，那麼使用Arrays.copyOf()方法
    if (elements.getClass() != Object[].class)
        elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
//直接調用setArray方法設定array屬性
setArray(elements);

(3)建立一個包含給定數組副本的list

public CopyOnWriteArrayList(E[] toCopyIn) {

setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));

上面介紹的是CopyOnWriteList的初始化，三個構造方法都比較易懂，後面還是主要看看幾個主要方法的實作

​ 下面是add(E e)方法的實作 ，以及詳細注釋

public boolean add(E e) {

//獲得獨占鎖
final ReentrantLock lock = this.lock;
//加鎖
lock.lock();
try {
    //獲得list底層的數組array
    Object[] elements = getArray();
    //獲得數組長度
    int len = elements.length;
    //拷貝到新數組，新數組長度為len+1
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    //給新數組末尾元素指派
    newElements[len] = e;
    //用新的數組替換掉原來的數組
    setArray(newElements);
    return true; 
} finally {
    lock.unlock();//釋放鎖
}

​ 總結一下add方法的執行流程

調用add方法的線程會首先擷取鎖，然後調用lock方法對list進行加鎖（了解ReentrantLock的知道這是個獨占鎖，是以多線程下隻有一個線程會擷取到鎖）

隻有線程會擷取到鎖，是以隻有一個線程會去更新這個數組，此過程中别的調用add方法的線程被阻塞等待

擷取到鎖的線程繼續執行

首先擷取原數組以及其長度，然後将其中的元素複制到一個新數組中(newArray的長度是原長度+1)

給定數組下标為len+1處指派

将新數組替換掉原有的數組

最後釋放鎖

​ 是以總結起來就是，多線程下隻有一個線程能夠擷取到鎖，然後使用複制原有數組的方式添加元素，之後再将新的數組替換原有的數組，最後釋放鎖（别的add線程去執行）。

​ 最後還有一點就是，數組長度不是固定的，每次寫之後數組長度會+1，是以CopyOnWriteList也沒有length或者size這類屬性，但是提供了size()方法，擷取集合的實際大小，size()方法如下

public int size() {

return getArray().length;

​ 使用get(i)可以擷取指定位置i的元素，當然如果元素不存在就會抛出數組越界異常。

public E get(int index) {

return get(getArray(), index);           
return array;

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

return (E) a[index];

​ 當然get方法這裡也展現了copy-on-write-list的弱一緻性問題。我們用下面的圖示簡略說明一下。圖中給的假設情況是：threadA通路index=1處的元素

①擷取array數組

②通路傳入參數下标的元素

​ 因為我們看到get過程是沒有加鎖的（假設array中有三個元素如圖所示）。假設threadA執行①之後②之前，threadB執行remove(1)操作，threadB或擷取獨占鎖，然後執行寫時複制操作，即複制一個新的數組neArray，然後在newArray中執行remove操作(1)，更新array。threadB執行完畢array中index=1的元素已經是item3了。

​ 然後threadA繼續執行，但是因為threadA操作的是原數組中的元素，這個時候的index=1還是item2。是以最終現象就是雖然threadB删除了位置為1處的元素，但是threadA還是通路的原數組的元素。這就是若一緻性問題

​ 修改也是屬于寫，是以需要擷取lock，下面就是set方法的實作

public E set(int index, E element) {

//擷取鎖
final ReentrantLock lock = this.lock;
//進行加鎖
lock.lock();
try {
    //擷取數組array
    Object[] elements = getArray();
    //擷取index位置的元素
    E oldValue = get(elements, index);
    // 要修改的值和原值不相等
    if (oldValue != element) {
        //擷取舊數組的長度
        int len = elements.length;
        //複制到一個新數組中
        Object[] newElements = Arrays.copyOf(elements, len);
        //在新數組中設定元素值
        newElements[index] = element;
        //用新數組替換掉原數組
        setArray(newElements);
    } else {
        // Not quite a no-op; ensures volatile write semantics
        //為了保證volatile 語義，即使沒有修改，也要替換成新的數組
        setArray(elements);
    }
    return oldValue; //傳回舊值
} finally {
    lock.unlock();//釋放鎖
}

​ 看了set方法之後，發現其實和add方法實作類似。

獲得獨占鎖，保證同一時刻隻有一個線程能夠修改數組

擷取目前數組，調用get方法擷取指定位置的數組元素

判斷get擷取的值和傳入的參數

相等，為了保證volatile語義，還是需要重新這隻array

不相等，将原數組元素複制到新數組中，然後在新數組的index處修改，修改完畢用新數組替換原數組

釋放鎖

​ 下面是remove方法的實作，總結就是

擷取獨占鎖，保證隻有一個線程能夠去删除元素

計算要移動的數組元素個數

如果删除的是最後一個元素，那麼上面的計算結果是0，就直接将原數組的前len-1個作為新數組替換掉原數組

删除的不是最後一個元素，那麼按照index分為前後兩部分，分别複制到新數組中，然後替換即可

public E remove(int index) {

//擷取鎖
final ReentrantLock lock = this.lock;
//加鎖
lock.lock();
try {
    //擷取原數組
    Object[] elements = getArray();
    //擷取原數組長度
    int len = elements.length;
    //擷取原數組index處的值
    E oldValue = get(elements, index);
    //因為數組删除元素需要移動，是以這裡就是計算需要移動的個數
    int numMoved = len - index - 1;
    //計算的numMoved=0，表示要删除的是最後一個元素，
    //那麼舊直接将原數組的前len-1個複制到新數組中，替換舊數組即可
    if (numMoved == 0)
        setArray(Arrays.copyOf(elements, len - 1));
    //要删除的不是最後一個元素
    else {
        //建立一個長度為len-1的數組
        Object[] newElements = new Object[len - 1];
        //将原數組中index之前的元素複制到新數組
        System.arraycopy(elements, 0, newElements, 0, index);
        //将原數組中index之後的元素複制到新數組
        System.arraycopy(elements, index + 1, newElements, index,
                         numMoved);
        //用新數組替換原數組
        setArray(newElements);
    }
    return oldValue;//傳回舊值
} finally {
    lock.unlock();//釋放鎖
}

​ 疊代器的基本使用方式如下，hashNext()方法用來判斷是否還有元素，next方法傳回具體的元素。

CopyOnWriteArrayList list = new CopyOnWriteArrayList();

Iterator<?> itr = list.iterator();

while(itr.hashNext()) {

//do sth
itr.next();

​ 那麼在CopyOnWriteArrayList中的疊代器是怎樣實作的呢，為什麼說是弱一緻性呢(先擷取疊代器的，但是如果在擷取疊代器之後别的線程對list進行了修改，這對于疊代器是不可見的)，下面就說一下CopyOnWriteArrayList中的實作

//Iterator<?> itr = list.iterator();

public Iterator iterator() {

//這裡可以看到，是先擷取到原數組getArray()，這裡記為oldArray
//然後調用COWIterator構造器将oldArray作為參數，建立一個疊代器對象
//從下面的COWIterator類中也能看到，其中有一個成員存儲的就是oldArray的副本
return new COWIterator<E>(getArray(), 0);

static final class COWIterator implements ListIterator {

//array的快照版本
private final Object[] snapshot;
//後續調用next傳回的元素索引(數組下标)
private int cursor;
//構造器
private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
}
//變量是否結束：下标小于數組長度
public boolean hasNext() {
    return cursor < snapshot.length;
}
//是否有前驅元素
public boolean hasPrevious() {
    return cursor > 0;
}
//擷取元素
//hasNext()傳回true，直接通過cursor記錄的下标擷取值
//hasNext()傳回false，抛出異常
public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}
//other method...

​ 在上面的代碼中我們能看處，list的iterator()方法實際上傳回的是一個COWIterator對象，COWIterator對象的snapshot成員變量儲存了目前list中array存儲的内容，但是snapshot可以說是這個array的一個快照，為什麼這樣說呢

我們傳遞的是雖然是目前的array，但是可能有别的線程對array進行了修改然後将原本的array替換掉了，那麼這個時候list中的array和snapshot引用的array就不是一個了，作為原array的快照存在，那麼疊代器通路的也就不是更新後的數組了。這就是弱一緻性的展現

​ 我們看下面的例子

public class TestCOW {

private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList();

public static void main(String[] args) throws InterruptedException {
    list.add("item1");
    list.add("item2");
    list.add("item3");

    Thread thread = new Thread() {
        @Override
        public void run() {
            list.set(1, "modify-item1");
            list.remove("item2");
        }
    };
    //main線程先獲得疊代器
    Iterator<String> itr = list.iterator();
    thread.start();//啟動thread線程
    thread.join();//這裡讓main線程等待thread線程執行完，然後再周遊看看輸出的結果是不是修改後的結果
    while (itr.hasNext()) {
        System.out.println(Thread.currentThread().getName() + "線程中的list的元素:" + itr.next());
    }
}

運作結果如下。實際上再上面的程式中我們先向list中添加了幾個元素，然後再thread中修改list，同時讓main線程先獲得list的疊代器，并等待thread執行完然後列印list中的元素，發現 main線程并沒有發現list中的array的變化，輸出的還是原來的list，這就是弱一緻性的展現。

main線程中的list的元素:item1

main線程中的list的元素:item2

main線程中的list的元素:item3

CopyOnWriteArrayList是如何保證寫時線程安全的：使用ReentrantLock獨占鎖，保證同時隻有一個線程對集合進行寫操作

資料是存儲在CopyOnWriteArrayList中的array數組中的，并且array長度是動态變化的（寫操作會更新array）

在修改數組的時候，并不是直接操作array，而是複制出來了一個新的數組，修改完畢，再把舊的數組替換成新的數組

使用疊代器進行周遊的時候不用加鎖，不會抛出ConcurrentModificationException異常，因為使用疊代器周遊操作的是數組的副本（當然，這是在别的線程修改list的情況）

​ 注意到set方法中有一段代碼是這樣的

else { //oldValue = element（element是傳入的參數）

// Not quite a no-op; ensures volatile write semantics
//為了保證volatile 語義，即使沒有修改，也要替換成新的數組
setArray(elements);

​ 其實就是說要指定位置要修改的值和數組中那個位置的值是相同的，但是還是需要調用set方法更新array，這是為什麼呢，參考這個文章，總結就是為了維護happens-before原則。首先看一下這段話

java.util.concurrent 中所有類的方法及其子包擴充了這些對更進階别同步的保證。尤其是： 線程中将一個對象放入任何并發 collection 之前的操作 happen-before 從另一線程中的 collection 通路或移除該元素的後續操作。

​ 可以了解為這裡是為了保證set操作之前的系列操作happen-before與别的線程通路array（不加鎖）的後續操作，參照下面的例子

// 這是兩個線程的初始情況

int nonVolatileField = 0; //一個不被volatile修飾的變量

//僞代碼

CopyOnWriteArrayList list = {"x","y","z"}

// Thread 1

// (1)這裡更新了nonVolatileField

nonVolatileField = 1;

// (2)這裡是set()修改（寫）操作，注意這裡會對volatile修飾的array進行寫操作

list.set(0, "x");

// Thread 2

// (3)這裡是通路（讀）操作

String s = list.get(0);

// (4)使用nonVolatileField

if (s == "x") {

int localVar = nonVolatileField;

假設存在以上場景，如果能保證隻會存在這樣的軌迹：(1)->(2)->(3)->(4).根據上述java API文檔中的約定有

​ (2)happen-before與(3)，線上程内的操作有（1）happen-before與（2）,（3）happen-before與（4），根據happen-before的傳遞性讀寫nonVolatileField變量就有（1）happen-before與（4）

​ 是以Thread 1對nonVolatileField的寫操作對Thread 2中a的讀操作可見。如果CopyOnWriteArrayList的set的else裡沒有setArray(elements)對volatile變量的寫的話，(2)happen-before與(3)就不再有了，上述的可見性也就無法保證。

​ 是以就是為了保證set操作之前的系列操作happen-before與别的線程通路array（不加鎖）的後續操作，

原文位址

https://www.cnblogs.com/fsmly/p/11298782.html
存儲 安全 java api 索引 安全存儲java java雲存儲 java char存儲 java編碼安全存儲 使用java存儲
上一篇: 阿裡雲對象存儲OSS如何配置伺服器端加密？AES256加密OSSUtil工具上傳并加密資料
下一篇: 異步程式設計CompletableFuture實作高并發系統優化之請求合并

繼續閱讀