基本原理

這里以Java集合為場景來解釋所謂的寫時復(fù)制COW(Copy-on-write)機(jī)制。當(dāng)向集合添加、移除元素時，并不是直接操作當(dāng)前集合，而是首先對原集合進(jìn)行拷貝、復(fù)制到一個新集合中。然后對該新集合進(jìn)行添加、移除元素的操作。最后，再將對原集合的引用指向新集合即可。該機(jī)制的好處就在于當(dāng)我們訪問、讀取集合是不需要加鎖的，即COW機(jī)制是讀寫分離思想的具體體現(xiàn)。當(dāng)然其弊端也是顯而易見的，一方面由于寫操作需要復(fù)制操作，所以對于較大規(guī)模的集合而言，其耗費的內(nèi)存也是較為可觀的；另一方面，由于讀操作訪問的是原集合，即使寫操作在此期間已經(jīng)完成。對于前者(讀操作)而言也是不可見的，即其保證的是最終一致性

應(yīng)用實踐

Java的ArrayList大家都很熟悉，其是線程不安全的。當(dāng)多個線程對其進(jìn)行操作時，由于fail-fast快速失敗機(jī)制的存在，其會盡可能拋出ConcurrentModificationException并發(fā)修改異常。為此針對數(shù)組列表，Java提供了一個線程安全的版本——Vector。其通過synchronized關(guān)鍵字實現(xiàn)了線程安全，故效率較低一般較少使用。為此Java還提供了一個基于COW機(jī)制的數(shù)組列表——CopyOnWriteArrayList。具體來說，該集合在進(jìn)行讀操作時是無鎖的。在進(jìn)行寫操作時，則通過ReentrantLock可重入鎖來保證當(dāng)前最多只有一個寫線程可以對其進(jìn)行復(fù)制、修改的操作

此外Java還提供了另外一個基于COW機(jī)制的并發(fā)容器——CopyOnWriteArraySet。具體來說，其首先是一個Set，元素的唯一性與HashSet類似，也是通過元素的equals方法來實現(xiàn)的。其次，其底層數(shù)據(jù)結(jié)構(gòu)使用的是CopyOnWriteArrayList，即通過數(shù)組來存儲元素

源碼分析

CopyOnWriteArrayList的源碼實現(xiàn)還是比較簡單的。其一方面，通過ReentrantLock可重入鎖來保證當(dāng)前最多只有一個寫線程可以對其進(jìn)行復(fù)制、修改的操作；另一方面，通過volatile保障可見性，使得在寫線程結(jié)束后，后續(xù)的讀線程可以立即讀取到最新的數(shù)據(jù)。但在set(int index, E element)方法中，如果發(fā)現(xiàn)指定索引處的原數(shù)據(jù)與新數(shù)據(jù)一樣時，其卻存在一行看似沒必要的代碼——setArray(elements)。原數(shù)組的內(nèi)容雖然沒有發(fā)生變化，但卻依然讓volatile變量array再次指向原數(shù)組。但本來array也是指向該數(shù)組的啊，為什么要多此一舉呢？

public?class?CopyOnWriteArrayList<E>?implements?List<E>,?RandomAccess,?Cloneable,?java.io.Serializable?{

????final?transient?ReentrantLock?lock?=?new?ReentrantLock();

????private?transient?volatile?Object[]?array;

????public?E?set(int?index,?E?element)?{
????????final?ReentrantLock?lock?=?this.lock;
????????lock.lock();
????????try?{
????????????Object[]?elements?=?getArray();
????????????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
????????????????setArray(elements);?????//?該行看似沒有必要，實則是?妙蛙種子在米奇妙妙屋吃妙脆角，妙到家了
????????????}
????????????return?oldValue;
????????}?finally?{
????????????lock.unlock();
????????}
????}

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

????private?E?get(Object[]?a,?int?index)?{
????????return?(E)?a[index];
????}

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

????...

}

在解答上述問題之前，我們需要先深刻理解下volatile關(guān)鍵字。在早期的Java內(nèi)存模型(JMM)中，雖然不允許volatile變量之間進(jìn)行重排序，但卻允許普通變量與volatile變量之間的重排序。由此導(dǎo)致程序發(fā)生讓人非常難以理解的現(xiàn)象及Bug，故在JSR 133中對volatile的內(nèi)存語義作了進(jìn)一步增強(qiáng)，限制了普通變量與volatile變量之間重排序的場景。下面是一個普通變量與volatile變量重排序的例子。假設(shè)線程A調(diào)用writer方法，線程B調(diào)用reader方法。當(dāng)線程B看到volatile變量v為true時，則后續(xù)訪問普通變量x一定可以保證其是42。換言之，在線程A執(zhí)行writer方法過程中，(1)處代碼一定先于(2)處代碼執(zhí)行。而在早期的JMM中由于允許普通變量與volatile變量之間的重排序，會導(dǎo)致(2)處代碼會被重排序到(1)處代碼前面進(jìn)而先執(zhí)行。進(jìn)一步會導(dǎo)致線程B雖然已經(jīng)看到volatile變量v為true了，但訪問變量x值卻為0

class?VolatileDemo?{
??
????int?x?=?0;
????
????volatile?boolean?v?=?false;
????
????//?寫操作
????public?void?writer()?{
????????x?=?42;?????//?(1)?普通變量寫
????????v?=?true;???//?(2)?valatile變量寫
????}

????//?讀操作
????public?void?reader()?{
????????if?(v?==?true)?{??//?(3)?valatile變量讀
????????????//?此時訪問變量x,?一定可以保證其值是?42
????????????...???//?(4)?普通變量讀
????????}
????}

}

現(xiàn)在回歸正題，我們看到在CopyOnWriteArrayList類上的注釋對Memory Consistency Effects內(nèi)存一致性影響所做出的保證：一個線程中放置一個元素到CopyOnWriteArrayList時其之前的動作 happen-before先行發(fā)生于另外一個線程從CopyOnWriteArrayList訪問、刪除該元素時其之后的動作

figure 1.jpg

假設(shè)現(xiàn)在有個普通變量nonVolatileField其初值為0，有一個CopyOnWriteArrayList實例，其在0位置的元素為x。如果線程1、2分別按如下代碼執(zhí)行。按CopyOnWriteArrayList類的Memory Consistency Effects說明進(jìn)行分析，則當(dāng)線程2執(zhí)行到(4)處代碼時，線程1的(1)處代碼必然要已經(jīng)執(zhí)行完成了，即線程2需要看到普通變量nonVolatileField已經(jīng)為1了。那如何保證(1)、(2)處的代碼不會發(fā)生重排序，以避免出現(xiàn)(2)先執(zhí)行、(1)后執(zhí)行的局面呢？答案自然是讓(2)處代碼執(zhí)行對volatile變量的寫。這也就是為什么在set(int index, E element)方法中，即使原數(shù)組的內(nèi)容雖然沒有發(fā)生變化，但卻依然讓volatile變量array再次指向原數(shù)組。其目的是用于保證volatile變量的寫語義

//?初始條件
int?nonVolatileField?=?0;
CopyOnWriteArrayList?list?=?new?CopyOnWriteArrayList<>();
list.add("x");

//?Thread?1
nonVolatileField?=?1;?????????????????//?(1)
list.set(0,?"x");?????????????????????//?(2)

//?Thread?2
String?s?=?list.get(0);???????????????//?(3)
if?(s?==?"x")?{
????int?localVar?=?nonVolatileField;??//?(4)
}

參考文獻(xiàn)

Java并發(fā)編程之美翟陸續(xù)、薛賓田著
深入理解Java虛擬機(jī)·第2版周志明著
JSR-133: Java Memory Model and Thread Specification

Java多線程之COW機(jī)制

基本原理

應(yīng)用實踐

源碼分析

參考文獻(xiàn)