聊聊高并發(fā)（十二）分析java.util.concurrent.atomic.AtomicStampedReference源碼來看如何解決CAS的ABA問題
來源：程序員人生 發(fā)布時(shí)間：2014-11-11 08:20:24 閱讀次數(shù)：3403次
在聊聊高并發(fā)（101）實(shí)現(xiàn)幾種自旋鎖（5）中使用了java.util.concurrent.atomic.AtomicStampedReference原子變量指向工作隊(duì)列的隊(duì)尾，為什么使用AtomicStampedReference原子變量而不是使用AtomicReference是由于這個(gè)實(shí)現(xiàn)中等待隊(duì)列的同1個(gè)節(jié)點(diǎn)具有不同的狀態(tài)，而同1個(gè)節(jié)點(diǎn)會屢次進(jìn)出工作隊(duì)列，這就有可能出現(xiàn)出現(xiàn)ABA問題。
熟習(xí)并發(fā)編程的同學(xué)應(yīng)當(dāng)知道CAS操作存在ABA問題。我們先看下CAS操作。
CAS(Compare and Swap) 比較并交換操作是1個(gè)3元操作: 目標(biāo)地址的值T(arget)，期望值E(xpected)，實(shí)際值R(eal)，
1. 只有當(dāng)目標(biāo)值T == 期望值E時(shí)，才會把目標(biāo)值T設(shè)置為實(shí)際值R，否則不改變目標(biāo)值
2. 不管目標(biāo)值是不是改變，都返回之前的目標(biāo)值T
類似以下的邏輯:
package com.zc.lock;
public class CAS {
private int value;
public synchronized int get(){
return value;
}
public synchronized int compareAndSwap(int expected, int real){
int oldValue = value;
if(value == expected){
value = real;
}
return oldValue;
}
public synchronized boolean compareAndSet(int expected, int real){
return (expected == compareAndSwap(expected, real));
}
}
CAS只比較期望值和目標(biāo)值是不是相當(dāng)，相當(dāng)就設(shè)置新值。那末ABA問題就來了：
1. 由于CAS只是值比較，比如目標(biāo)是A, 期望值也是A, 那末CAS操作會成功。但是這時(shí)候候目標(biāo)A可能不是原來的那個(gè)A了，它多是A變成了B，再變成了A。所以叫ABA問題，很形象。ABA問題可能會使程序出錯(cuò)，比如限時(shí)有界隊(duì)列鎖中的節(jié)點(diǎn)有幾個(gè)狀態(tài)，雖然援用值是A，但是可能對象的狀態(tài)已變了，這時(shí)候候的A實(shí)際已不是原來的A了
2. 需要注意的是ABA問題不是說CAS操作的進(jìn)程中A變成了ABA，CAS操作是原子操作，不會被打斷。ABA問題場景以下：
先獲得了A的值，然后再CAS(A, R), 這時(shí)候候CAS中的A實(shí)際指向的對象的狀態(tài)可能和它剛?cè)〉玫臅r(shí)候的狀態(tài)已發(fā)送了改變。
</pre><pre name="code" class="java">A a = ref.get();
// 根據(jù)a的狀態(tài)做1些操作
// do something
// CAS,這時(shí)候候會出現(xiàn)ABA問題，a指向的對象可能已變了
ref.compareAndSet(a, b)
解決ABA問題方法就是給狀態(tài)設(shè)置時(shí)間戳，這是并發(fā)中加樂觀鎖的常見做法，如果狀態(tài)的時(shí)間戳產(chǎn)生了改變，證明已不是原來的對象了，所以操作失敗
// 用int做時(shí)間戳
AtomicStampedReference<QNode> tail = new AtomicStampedReference<CompositeLock.QNode>(null, 0);
int[] currentStamp = new int[1];
// currentStamp中返回了時(shí)間戳信息
QNode tailNode = tail.get(currentStamp);
tail.compareAndSet(tailNode, null, currentStamp[0], currentStamp[0] + 1)
下面我們來看1下java.util.concurrent.atomic.AtomicStampedReference的源代碼是如何實(shí)現(xiàn)的。
下面代碼來自JDK1.7，條理很清晰，實(shí)現(xiàn)有幾個(gè)要點(diǎn):
1. 創(chuàng)建1個(gè)Pair類來記錄對象援用和時(shí)間戳信息,采取int作為時(shí)間戳，實(shí)際使用的時(shí)候時(shí)間戳信息要做成自增的，否則時(shí)間戳如果重復(fù)，還會出現(xiàn)ABA的問題。這個(gè)Pair對象是不可變對象，所有的屬性都是final的， of方法每次返回1個(gè)新的不可變對象
2. 使用1個(gè)volatile類型的援用指向當(dāng)前的Pair對象，1旦volatile援用產(chǎn)生變化，變化對所有線程可見
3. set方法時(shí)，當(dāng)要設(shè)置的對象和當(dāng)前Pair對象不1樣時(shí)，新建1個(gè)不可變的Pair對象
4. compareAndSet方法中，只有期望對象的援用和版本號和目標(biāo)對象的援用和版本好都1樣時(shí)，才會新建1個(gè)Pair對象，然后用新建的Pair對象和原理的Pair對象做CAS操作
5. 實(shí)際的CAS操作比較的是當(dāng)前的pair對象和新建的pair對象，pair對象封裝了援用和時(shí)間戳信息
private static class Pair<T> {
final T reference;
final int stamp;
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
static <T> Pair<T> of(T reference, int stamp) {
return new Pair<T>(reference, stamp);
}
}
private volatile Pair<V> pair;
public AtomicStampedReference(V initialRef, int initialStamp) {
pair = Pair.of(initialRef, initialStamp);
}
public void set(V newReference, int newStamp) {
Pair<V> current = pair;
if (newReference != current.reference || newStamp != current.stamp)
this.pair = Pair.of(newReference, newStamp);
}
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
private static final long pairOffset =
objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);
private boolean casPair(Pair<V> cmp, Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
