聊聊高并發（十二）分析java.util.concurrent.atomic.AtomicStampedReference源碼來看如何解決CAS的ABA問題
來源：程序員人生 發布時間：2014-11-11 08:20:24 閱讀次數：3408次
在聊聊高并發（101）實現幾種自旋鎖（5）中使用了java.util.concurrent.atomic.AtomicStampedReference原子變量指向工作隊列的隊尾，為什么使用AtomicStampedReference原子變量而不是使用AtomicReference是由于這個實現中等待隊列的同1個節點具有不同的狀態，而同1個節點會屢次進出工作隊列，這就有可能出現出現ABA問題。
熟習并發編程的同學應當知道CAS操作存在ABA問題。我們先看下CAS操作。
CAS(Compare and Swap) 比較并交換操作是1個3元操作: 目標地址的值T(arget)，期望值E(xpected)，實際值R(eal)，
1. 只有當目標值T == 期望值E時，才會把目標值T設置為實際值R，否則不改變目標值
2. 不管目標值是不是改變，都返回之前的目標值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只比較期望值和目標值是不是相當，相當就設置新值。那末ABA問題就來了：
1. 由于CAS只是值比較，比如目標是A, 期望值也是A, 那末CAS操作會成功。但是這時候候目標A可能不是原來的那個A了，它多是A變成了B，再變成了A。所以叫ABA問題，很形象。ABA問題可能會使程序出錯，比如限時有界隊列鎖中的節點有幾個狀態，雖然援用值是A，但是可能對象的狀態已變了，這時候候的A實際已不是原來的A了
2. 需要注意的是ABA問題不是說CAS操作的進程中A變成了ABA，CAS操作是原子操作，不會被打斷。ABA問題場景以下：
先獲得了A的值，然后再CAS(A, R), 這時候候CAS中的A實際指向的對象的狀態可能和它剛取得的時候的狀態已發送了改變。
</pre><pre name="code" class="java">A a = ref.get();
// 根據a的狀態做1些操作
// do something
// CAS,這時候候會出現ABA問題，a指向的對象可能已變了
ref.compareAndSet(a, b)
解決ABA問題方法就是給狀態設置時間戳，這是并發中加樂觀鎖的常見做法，如果狀態的時間戳產生了改變，證明已不是原來的對象了，所以操作失敗
// 用int做時間戳
AtomicStampedReference<QNode> tail = new AtomicStampedReference<CompositeLock.QNode>(null, 0);
int[] currentStamp = new int[1];
// currentStamp中返回了時間戳信息
QNode tailNode = tail.get(currentStamp);
tail.compareAndSet(tailNode, null, currentStamp[0], currentStamp[0] + 1)
下面我們來看1下java.util.concurrent.atomic.AtomicStampedReference的源代碼是如何實現的。
下面代碼來自JDK1.7，條理很清晰，實現有幾個要點:
1. 創建1個Pair類來記錄對象援用和時間戳信息,采取int作為時間戳，實際使用的時候時間戳信息要做成自增的，否則時間戳如果重復，還會出現ABA的問題。這個Pair對象是不可變對象，所有的屬性都是final的， of方法每次返回1個新的不可變對象
2. 使用1個volatile類型的援用指向當前的Pair對象，1旦volatile援用產生變化，變化對所有線程可見
3. set方法時，當要設置的對象和當前Pair對象不1樣時，新建1個不可變的Pair對象
4. compareAndSet方法中，只有期望對象的援用和版本號和目標對象的援用和版本好都1樣時，才會新建1個Pair對象，然后用新建的Pair對象和原理的Pair對象做CAS操作
5. 實際的CAS操作比較的是當前的pair對象和新建的pair對象，pair對象封裝了援用和時間戳信息
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);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
