Java并發(fā)中的ABA問題學習與解決方案
1.簡介
我們將了解在并發(fā)編程中的ABA問題。同時學習引起該問題的根因及問題解決辦法。
2.Compare and swap
為了理解根本原因，首先回顧一下Compare and swap的概念。Compare and Swap (CAS)在無鎖算法中是一種常見的技術。能夠保證并發(fā)修改共享數(shù)據(jù)時，一個線程將共享內存修改后，另一線程嘗試對共享內存的修改會失敗。
我們每次更新時，通過兩種信息來實現(xiàn)：要更新的值及原始值。首先Compare and swap 會比較原始值和當前獲取到的值。如果相等，那么將值更新為要設置的值。
3. ABA問題
當執(zhí)行campare and swap會出現(xiàn)失敗的情況。例如，一個線程先讀取共享內存數(shù)據(jù)值A，隨后因某種原因，線程暫時掛起，同時另一個線程臨時將共享內存數(shù)據(jù)值先改為B，隨后又改回為A。隨后掛起線程恢復，并通過CAS比較，最終比較結果將會無變化。這樣會通過檢查，這就是ABA問題。 在CAS比較前會讀取原始數(shù)據(jù)，隨后進行原子CAS操作。這個間隙之間由于并發(fā)操作，最終可能會帶來問題。
3.1 ABA問題的實際場景：賬戶余額修改
為了通過實例演示ABA問題。我們創(chuàng)建一個銀行賬戶類，該類維護一個整型變量記錄賬戶余額。該類有兩個函數(shù)：一個用于存錢，一個用于取錢。這些操作使用CAS來修改賬戶余額。
3.2 賬戶余額修改時產生的問題
我們來考慮兩個線程操作同一個賬戶時的場景。當線程1取錢時，先讀取余額，隨后通過CAS操作進行比較。然后，可能由于某些原因，線程1可能發(fā)生阻塞。與此同時，線程2同樣通過CAS機制，在線程1掛起時，在同一個賬戶上執(zhí)行兩個操作。首先，改變原始值，這個值已經被線程1在剛才讀取。隨后線程2又將這個值改為原始值。
一旦線程1恢復后，在線程1看來，沒有發(fā)生任何變化。cas將會執(zhí)行成功。
4.銀行取款問題代碼演示
創(chuàng)建一個Account類，balance記錄賬戶余額。transactionCount記錄成功執(zhí)行的事務數(shù)。currentThreadCASFailureCount來記錄CAS操作失敗的次數(shù)。
接著我們實現(xiàn)一個存款的方法deposit，與取款方法withdraw。為了演示ABA問題，同時實現(xiàn)一個maybeWait方法進行延遲等待。
最終的代碼如下：
public class Account {
private AtomicInteger balance;
private AtomicInteger transactionCount;
private ThreadLocal<Integer> currentThreadCASFailureCount;
public Account() {
this.balance = new AtomicInteger(0);
this.transactionCount = new AtomicInteger(0);
this.currentThreadCASFailureCount = new ThreadLocal<>();
this.currentThreadCASFailureCount.set(0);
}
public int getBalance() {
return balance.get();
}
public int getTransactionCount() {
return transactionCount.get();
}
public int getCurrentThreadCASFailureCount() {
return Optional.ofNullable(currentThreadCASFailureCount.get()).orElse(0);
}
public boolean withdraw(int amount) {
int current = getBalance();
maybeWait();
boolean result = balance.compareAndSet(current, current - amount);
if (result) {
transactionCount.incrementAndGet();
} else {
int currentCASFailureCount = currentThreadCASFailureCount.get();
currentThreadCASFailureCount.set(currentCASFailureCount + 1);
}
return result;
}
private void maybeWait() {
if ("thread1".equals(Thread.currentThread().getName())) {
try {
TimeUnit.SECONDS.sleep(2);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
public boolean deposit(int amount) {
int current = balance.get();
boolean result = balance.compareAndSet(current, current + amount);
if (result) {
transactionCount.incrementAndGet();
} else {
int currentCASFailureCount = currentThreadCASFailureCount.get();
currentThreadCASFailureCount.set(currentCASFailureCount + 1);
}
return result;
}
}
接著我們對上述代碼進行測試。通過maybeWait方法，模擬出現(xiàn)ABA問題。
@Test
public void abaProblemTest() throws InterruptedException {
final int defaultBalance = 50;
final int amountToWithdrawByThread1 = 20;
final int amountToWithdrawByThread2 = 10;
final int amountToDepositByThread2 = 10;
Assert.assertEquals(0, account.getTransactionCount());
Assert.assertEquals(0, account.getCurrentThreadCASFailureCount());
account.deposit(defaultBalance);
Assert.assertEquals(1, account.getTransactionCount());
Thread thread1 = new Thread(() -> {
// this will take longer due to the name of the thread
Assert.assertTrue(account.withdraw(amountToWithdrawByThread1));
// thread 1 fails to capture ABA problem
Assert.assertNotEquals(1, account.getCurrentThreadCASFailureCount());
}, "thread1");
Thread thread2 = new Thread(() -> {
Assert.assertTrue(account.deposit(amountToDepositByThread2));
Assert.assertEquals(defaultBalance + amountToDepositByThread2, account.getBalance());
// this will be fast due to the name of the thread
Assert.assertTrue(account.withdraw(amountToWithdrawByThread2));
// thread 1 didn't finish yet, so the original value will be in place for it
Assert.assertEquals(defaultBalance, account.getBalance());
Assert.assertEquals(0, account.getCurrentThreadCASFailureCount());
}, "thread2");
thread1.start();
thread2.start();
thread1.join();
thread2.join();
// compareAndSet operation succeeds for thread 1
Assert.assertEquals(defaultBalance - amountToWithdrawByThread1, account.getBalance());
//but there are other transactions
Assert.assertNotEquals(2, account.getTransactionCount());
// thread 2 did two modifications as well
Assert.assertEquals(4, account.getTransactionCount());
}
5.值類型與引用類型的場景
上面的例子中使用了getBalance()方法獲取了一個值類型數(shù)據(jù)。由于使用的是值類型，雖然出現(xiàn)ABA問題，但未對結果造成影響。如果我們操作的是引用類型，那么最終會保存不同的引用對象，會帶來意外的結果。
對于引用類型，下面以鏈棧為例說明。
- 線程A希望將A結點出棧，此時讀取棧頂元素A，準備執(zhí)行CAS操作，此時由于某種原因阻塞。
- 線程B開始執(zhí)行，執(zhí)行出棧A、B。隨后將D、C、A結點壓入棧中。
- 線程A恢復執(zhí)行。接著執(zhí)行CAS，比較發(fā)現(xiàn)棧頂結點A沒有被修改。隨后將棧頂結點改為B。由于B線程在第二步時，已經將B結點移除，A線程修改后發(fā)生錯誤。棧的結構發(fā)生破壞。
接著我們通過下面的代碼進行演示：
static class Stack {
private AtomicReference<Node> top = new AtomicReference<>();
static class Node {
String value;
Node next;
public Node (String value) {
this.value = value;
}
}
//出棧
public Node pop(int time) {
Node newTop;
Node oldTop;
do {
oldTop = top.get();
if (oldTop == null) {
return null;
}
newTop = oldTop.next;
try {
//休眠一段時間，模擬ABA問題
TimeUnit.SECONDS.sleep(time);
} catch (InterruptedException e) {
e.printStackTrace();
}
} while (!top.compareAndSet(oldTop, newTop));
return oldTop;
}
public void push (Node node) {
Node oldTop;
do {
oldTop = top.get();
node.next = oldTop;
} while (!top.compareAndSet(oldTop, node));
}
public AtomicReference<Node> getTop() {
return top;
}
}
@Test
public void testStack() throws Exception{
Stack stack = new Stack();
Stack.Node a = new Stack.Node("A");
Stack.Node b = new Stack.Node("B");
// 初始化棧結構
stack.push(b);
stack.push(a);
// ABA 測試
Thread t1 = new Thread(() -> {
stack.pop(2);
});
Stack.Node c = new Stack.Node("C");
Stack.Node d = new Stack.Node("D");
Thread t2 = new Thread(() -> {
stack.pop(0);
stack.pop(0);
stack.push(d);
stack.push(c);
stack.push(a);
});
//
t1.start();
t2.start();
TimeUnit.SECONDS.sleep(5);
Stack.Node top = stack.getTop().get();
do {
System.out.println(top.value);
top = top.next;
} while (top != null);
}
6. 解決方法
- hazard pointer：首先出現(xiàn)問題是因為，多個線程操作共享數(shù)據(jù)，并未感知到別的線程正在對共享數(shù)據(jù)進行操作。通過hazard pointer介紹[1]，其基本思想就是每個線程維護一個操作列表，在操作一個結點時將其記錄。如果一個線程要做結點變更，先搜索線程操作列表，看是否有其它線程操作。如果有則此次操作執(zhí)行失敗。
- 不變性：從上述棧的例子中可以看到，在對結點A進行比較時，由于A依然是多個線程共享并復用，因此CAS會成功。如果每次操作時，新創(chuàng)建對象而不是復用。這樣CAS就會正常提示失敗。但這樣可能會創(chuàng)建大量對象。
7. Java中的解決方法
Java中提供了兩個類來解決這個問題。
AtomicStampedReferenceAtomicMarkableReference
在原有類的基礎上，除了比較與修改期待的值外，增加了一個時間戳。對時間戳也進行CAS操作。這也稱為雙重CAS。從上例中看到。每次修改一個結點，其時間戳都發(fā)生變化。這樣即使共享一個復用結點，最終CAS也能返回正常的結果。
8. 總結
本文介紹了CAS產生ABA問題的背景，通用解決辦法及Java中的解決辦法。對于值類型有時發(fā)生ABA問題可能并不會造成問題。但對于引用類型，就可能造成歧義，同時破壞數(shù)據(jù)結構。通過鏈棧的演示，我們可以有所了解ABA產生的問題。
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了Java多線程之原子類解析,Java原子類是一種多線程編程中常用的工具,用于實現(xiàn)線程安全的操作,它們提供了一種原子性操作的機制,確保多個線程同時訪問共享變量時的數(shù)據(jù)一致性,需要的朋友可以參考下2023-10-10
IntelliJ IDEA中程序包org.slf4j找不到的解決
這篇文章主要介紹了IntelliJ IDEA中程序包org.slf4j找不到的解決,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
@Value注入List、數(shù)組、Set、Map問題
這篇文章主要介紹了@Value注入List、數(shù)組、Set、Map問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-07-07
這篇文章主要介紹了SpringBoot部署在tomcat容器中運行的部署方法,需要的朋友可以參考下2018-10-10
SpringBoot下載Excel文件時,報錯文件損壞的解決方案
這篇文章主要介紹了SpringBoot下載Excel文件時,報錯文件損壞的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
詳解Java編寫算法時如何加快讀寫數(shù)據(jù)速度
這篇文章主要為大家詳細介紹了Java在編寫算法時如何加快讀寫數(shù)據(jù)速度,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-03-03
今天小編就為大家分享一篇關于JAVA JDK8 List分組的實現(xiàn)和用法，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
解決Springboot項目中很多頁面出現(xiàn)Whitelabel Error Page(404)的問題
最近在接手的前后端項目中發(fā)現(xiàn)其默認路徑不是主機+端口（如：http://localhost:3453/）的形式,很多頁面的訪問是加了一個層級,只要訪問頁面就會出現(xiàn)Whitelabel Error Page(404),所以本文給大家提供了解決方案,需要的朋友可以參考下2024-02-02
由于項目需要,需要對二進制文件進行讀取,所以這篇文章主要給大家介紹了關于JAVA讀取二進制文件以及畫圖的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-07-07
詳解Java利用ExecutorService實現(xiàn)同步執(zhí)行大量線程
這篇文章主要介紹了Java利用ExecutorService實現(xiàn)同步執(zhí)行大量線程,ExecutorService可以維護我們的大量線程在操作臨界資源時的穩(wěn)定性。2017-03-03