《Java并發(fā)編程之美》讀書筆記
第五章 Java并發(fā)包中并發(fā)List源碼剖析
介紹
并發(fā)包中的并發(fā)List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一個線程安全的ArrayList，對其進行修改操作都是在底層的一個復(fù)制的數(shù)組（快照）上進行的，也就是說采用了寫時復(fù)制的策略。CopyOnWriteArrayList的類圖結(jié)構(gòu)如下：
在CopyOnWriteArrayList的類圖中，每個CopyOnWriteArrayList對象里面有一個array數(shù)組用來存放具體元素，ReentrantLock獨占鎖對象用來保證同時只能有一個線程對array進行修改。ReentrantLock是獨占鎖，同時只能有一個線程獲取。
如果讓我們自己做一個寫時復(fù)制的線程安全的list我們怎么做，會怎樣考慮？
- 何時初始化list，初始化list的size是多少，list是有限大小的嗎？
- 如果保證線程安全，比如多個線程進行讀寫時是如何保證線程是安全的？
- 如何保證使用迭代器遍歷list時數(shù)據(jù)的一致性呢？
CopyOnWriteArrayList主要方法源碼解析
初始化
首先看下午無參的構(gòu)造函數(shù)，如下代碼在內(nèi)部創(chuàng)建了一個大小為0的Object數(shù)組作為array的初始值。
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
然后看下有參的構(gòu)造函數(shù)
//創(chuàng)建一個list，其內(nèi)部是入?yún)oCopyIn的副本
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
//入?yún)榧希瑢⒓侠锩娴脑貜?fù)制到副本list
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] es;
if (c.getClass() == CopyOnWriteArrayList.class)
es = ((CopyOnWriteArrayList<?>)c).getArray();
else {
es = c.toArray();
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (es.getClass() != Object[].class)
es = Arrays.copyOf(es, es.length, Object[].class);
}
setArray(es);
}
添加元素
CopyOnWriteArrayList中用來添加元素的函數(shù)有add(E e)、add(int index,E element)、addIfAbsent(E e)和addAllAbsent(Collection<?extends E> C)等，這里以add(E e)來講解
public boolean add(E e) {
//獲取鎖
synchronized (lock) {
//獲取es
Object[] es = getArray();
int len = es.length;
//復(fù)制array到新數(shù)組，添加元素到新數(shù)組
es = Arrays.copyOf(es, len + 1);
es[len] = e;
//使用新數(shù)組替換添加前的數(shù)組
setArray(es);
return true;
}
//釋放鎖
}
在如上的代碼中，調(diào)用add方法的線程會首先獲取獨占鎖，如果多個線程都調(diào)用add方法則只有一個線程會獲取到該鎖，其他線程會被阻塞掛起直到鎖被釋放。
所以一個線程獲取到鎖之后，就保證了該線程添加元素的過程中其他線程不會對array進行修改。
線程獲取鎖之后執(zhí)行代碼獲取array，然后執(zhí)行代碼復(fù)制array到一個新數(shù)組中（從這里可以直到新數(shù)組的大小是原來數(shù)組大小增加1，所以CopyOnWriteArrayList是無解的list）并把新增的元素添加到新數(shù)組，
然后執(zhí)行代碼使用新數(shù)組替換掉原數(shù)組，并在返回前釋放鎖。由于加了鎖整個add操作就是個原子性操作。需要注意的是，再添加元素時，首先復(fù)制了一個快照，然后再快照上進行添加，而不是直接在原來數(shù)組上進行
獲取指定位置元素
使用E get(int index)獲取下標(biāo)為index的元素，如果元素不存在則拋出IndexOutOfBoundsException異常；
public E get(int index) {
return elementAt(getArray(), index);
}
final Object[] getArray() {
return array;
}
static <E> E elementAt(Object[] a, int index) {
return (E) a[index];
}
在如上的代碼中，當(dāng)線程x調(diào)用get方法獲取指定位置的元素時，分兩步走，首先獲取array數(shù)組（步驟A），然后通過下標(biāo)訪問指定位置的元素（步驟B）這是兩步操作，但是整個過程中沒有進行加鎖同步.假設(shè)這時候List內(nèi)容如圖所示，里面有1，2，3三個元素。
由于執(zhí)行步驟A和步驟B都沒有加鎖，這就可能導(dǎo)致在線程x執(zhí)行步驟A的后在執(zhí)行步驟B之前，另外一個線程y進行了remove操作，假設(shè)要刪除元素1，remove操作首先會獲取獨占鎖，然后進行寫時復(fù)制的操作，也就是復(fù)制一份當(dāng)前的array數(shù)組，然后再復(fù)制的數(shù)組里面山城線程x通過get方法要訪問的元素1，之后讓array指向復(fù)制的數(shù)組，而這時候array之前指向的數(shù)組的引用計數(shù)為1而不是0，因為線程x還在使用它，這是線程x執(zhí)行步驟B，步驟B操作的數(shù)組還是線程y刪除元素之前的數(shù)組。
所以，雖然線程y已經(jīng)刪除了index處的元素，但是線程x的步驟B還是會返回index處的元素，這其實就是寫時復(fù)制策略產(chǎn)生的弱一致性的問題。
修改指定元素
使用E set(int index,E element)修改list中指定元素的值，如果指定位置的元素不存在則拋出IndexOutOfBoundsException異常
public E set(int index, E element) {
synchronized (lock) {
Object[] es = getArray();
E oldValue = elementAt(es, index);
if (oldValue != element) {
es = es.clone();
es[index] = element;
setArray(es);
}
return oldValue;
}
}
如上的代碼首先獲取了獨占鎖，從而阻止其他線程對array數(shù)組進行修改，然后獲取當(dāng)前數(shù)組，并調(diào)用get方法獲取指定位置的元素，如果指定位置的元素值和新的值不一樣，則創(chuàng)建新數(shù)組并復(fù)制元素，然后在新數(shù)組上修改指定位置的元素值并設(shè)置新數(shù)組到array。
刪除元素
刪除list里面指定的元素，可以使用E remove（int index) 、boolean remove(Object o) boolean remove(Object o,Object[] snapshot,int index)等方法
public E remove(int index) {
//獲取獨占鎖
synchronized (lock) {
//獲取數(shù)組
Object[] es = getArray();
int len = es.length;
//獲取指定元素
E oldValue = elementAt(es, index);
int numMoved = len - index - 1;
Object[] newElements;
//如果刪除的是最后一個元素
if (numMoved == 0)
newElements = Arrays.copyOf(es, len - 1);
else {
//分兩次復(fù)制刪除后剩余的元素到新數(shù)組
newElements = new Object[len - 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index + 1, newElements, index,
numMoved);
}
//使用新數(shù)組代替老數(shù)組
setArray(newElements);
return oldValue;
}
//釋放鎖
}
如上代碼其實和新增元素的代碼相似，首先獲取獨占鎖以保證刪除數(shù)據(jù)期間其他線程不能對array進行修改，然后獲取數(shù)組中要被刪除的元素，并把剩余的袁術(shù)復(fù)制到新數(shù)組中，之后使用新數(shù)組替換原來的數(shù)組，最后返回前釋放鎖。
弱一致性迭代器
遍歷列表元素可以使用迭代器，先舉一個例子說明如何使用迭代器
public static void main(String[] args) {
CopyOnWriteArrayList<String> arrayList=new CopyOnWriteArrayList<>();
arrayList.add("hello");
arrayList.add("CopyOnWriteArrayList");
Iterator<String> iterator = arrayList.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
迭代器的hasNext方法用于判斷列表中是否還有元素，next方法則返回具體元素。
什么時CopyOnWriteArrayList中迭代器的弱一致性？
所謂的弱一致性值得時返回迭代器后，其他線程對list的增刪改時對迭代器不可見的
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
//array的快照副本
private final Object[] snapshot;
//數(shù)組下標(biāo)
private int cursor;
//構(gòu)造函數(shù)
COWIterator(Object[] es, int initialCursor) {
cursor = initialCursor;
snapshot = es;
}
//是否遍歷結(jié)束
public boolean hasNext() {
return cursor < snapshot.length;
}
//獲取元素
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
}
在如上的代碼中，當(dāng)調(diào)用iterator()方法獲取迭代器時實際上會返回一個COWIterator對象，COWIterator對象的snapshot變量保留了當(dāng)前l(fā)ist的內(nèi)容，cursor是遍歷list時數(shù)據(jù)的下標(biāo)。
為什么說snapshot是list的快照呢？明明傳遞的是指針類型的引用啊，而不是副本。如果在該線程使用返回的迭代器遍歷元素的過程中，其他線程沒有對list進行增刪改，那么snapshot本身就是list的array，因為他們就是引用關(guān)系。然是如果在遍歷器件其他線程對list進行了增刪改，那么snapshot就是快照了，因為增刪改之后list里面的數(shù)組被新數(shù)組替換了，這時候老數(shù)組被snapshot引用，這也說明獲取迭代器后，使用該迭代器元素時，其他線程對該list進行的增刪改不可見，因為他們操作的是兩個不同類型的數(shù)組，這就是弱一致性。
public class CopyList {
//創(chuàng)建CopyOnWriteArrayList
private static volatile CopyOnWriteArrayList<String> arrayList=new
CopyOnWriteArrayList<>();
public static void main(String[] args) throws InterruptedException{
arrayList.add("hello");
arrayList.add("CopyList");
arrayList.add("welcome");
arrayList.add("to");
arrayList.add("heu");
//創(chuàng)建線程修改CopyOnWriteArrayList里面的值
Thread threadOne=new Thread(new Runnable() {
@Override
public void run() {
arrayList.set(1,"ali");
arrayList.remove(2);
arrayList.remove(3);
}
});
//在修改線程啟動前獲取list的迭代器
Iterator<String> iterator = arrayList.iterator();
//啟動線程
threadOne.start();
//等子線程執(zhí)行完畢
threadOne.join();
//迭代元素
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
在如上的代碼中，main函數(shù)首先初始化了arrayList，然后再啟動線程前獲取到了arrayList迭代器，子線程threadOne啟動后修改了arrayList里面的值。主線程子線程執(zhí)行完畢后使用獲取迭代器遍歷數(shù)組元素，從輸出結(jié)果我們知道，在子線程里面進行的操作都沒有生效，這就是迭代器弱一致性的體現(xiàn)。需要注意的是，獲取迭代器的操作必須在子線程操作之前進行。
參考資料：
《Java并發(fā)編程之美》
