本文主要研究的是關於Java中ABA問題及避免的相關內容,具體如下。
在《Java並發實戰》一書的第15章中有一個用原子變量實現的並發棧,代碼如下:
public class Node {public final String item;public Node next;public Node(String item){this.item = item;}} public class ConcurrentStack {AtomicReference<Node> top = new AtomicReference<Node>();public void push(String item){Node newTop = new Node(item);Node oldTop;do{oldTop = top.get();newTop.next = oldTop;}while(!top.compareAndSet(oldTop, newTop));}public String pop(){Node newTop;Node oldTop;do{oldTop = top.get();if(oldTop == null){return null;}newTop = oldTop.next;}while(!top.compareAndSet(oldTop, newTop));return oldTop.item;}}這個例子並不會引發ABA問題,至於為什麼不會,後面再講解,下面先講一下ABA問題
什麼是ABA?
引用原書的話:如果在算法中的節點可以被循環使用,那麼在使用“比較並交換”指令就可能出現這種問題,在CAS操作中將判斷“V的值是否仍然為A?”,並且如果是的話就繼續執行更新操作,在某些算法中,如果V的值首先由A變為B,再由B變為A,那麼CAS將會操作成功
ABA的例子
有時候,ABA造成的後果很嚴重,下面將並發棧的例子修改一下,看看ABA會造成什麼問題:
public class Node {public final String item;public Node next;public Node(String item){this.item = item;}} public class ConcurrentStack {AtomicReference<Node> top = new AtomicReference<Node>();public void push(Node node){Node oldTop;do{oldTop = top.get();node.next = oldTop;}while(!top.compareAndSet(oldTop, node));}public Node pop(int time){Node newTop;Node oldTop;do{oldTop = top.get();if(oldTop == null){return null;}newTop = oldTop.next;TimeUnit.SECONDS.sleep(time);}while(!top.compareAndSet(oldTop, newTop));return oldTop;}}注意這裡的變化,Node基本沒有變化
重點關注ConcurrentStack的變化
1、push方法:原來是使用內容構造Node,現在直接傳入Node,這樣就符合了“在算法中的節點可以被循環使用”這個要求
2、pop方法的sleep,這是模擬線程的執行情況,以便觀察結果
我們先往stack中壓入兩個Node:
ConcurrentStack stack = new ConcurrentStack(); stack.push(new Node("A")); stack.push(new Node("B"));然後創建兩個線程來執行出入棧的操作
線程A先執行出棧:讓NodeA出棧
stack.pop(3);
因為某些原因,線程A執行出棧比較久,用了3s
線程B執行出棧之後再入棧:先然NodeA和NodeB出棧,然後讓NodeD,NodeC,NodeA入棧(NodeA在棧頂)
Node A = stack.pop(0); stack.pop(0); stack.push(new Node("D")); stack.push(new Node("C")); stack.push(A);注意:線程B實現了節點的循環利用,它先將棧裡面的內容全部出棧,然後入棧,最後棧頂的內容是之前出棧的Node
線程B執行完這些動作之後,線程A才執行CAS,此時CAS是可以執行成功的
按照原來的想法,線程A和B執行之後,stack的內容應該是:C和D,C在棧頂,但這裡的執行結果卻是Stack中什麼都沒有,這就是ABA問題
如何避免ABA問題
Java中提供了AtomicStampedReference和AtomicMarkableReference來解決ABA問題
AtomicStampedReference可以原子更新兩個值:引用和版本號,通過版本號來區別節點的循環使用,下面看AtomicStampedReference的例子:
public class ConcurrentStack {AtomicStampedReference<Node> top = new AtomicStampedReference<Node>(null,0);public void push(Node node){Node oldTop;int v;do{v=top.getStamp();oldTop = top.getReference();node.next = oldTop;}while(!top.compareAndSet(oldTop, node,v,v+1));// }while(!top.compareAndSet(oldTop, node,top.getStamp(),top.getStamp()+1));}public Node pop(int time){Node newTop;Node oldTop;int v;do{v=top.getStamp();oldTop = top.getReference();if(oldTop == null){return null;}newTop = oldTop.next;try {TimeUnit.SECONDS.sleep(time);}catch (InterruptedException e) {e.printStackTrace();}}while(!top.compareAndSet(oldTop, newTop,v,v+1));// }while(!top.compareAndSet(oldTop, newTop,top.getStamp(),top.getStamp())); return oldTop;}public void get(){Node node = top.getReference();while(node!=null){System.out.println(node.getItem());node = node.getNode();}}}注意:不能使用註釋中的方式,否則就和單純使用原子變量沒有區別了
AtomicMarkableReference可以原子更新一個布爾類型的標記位和引用類型,看下面的例子:
AtomicMarkableReference<Node> top = new AtomicMarkableReference<Node>(null,true);public void push(Node node){Node oldTop;Boolean v;do{v=top.isMarked();oldTop = top.getReference();node.next = oldTop;}while(!top.compareAndSet(oldTop, node,v,!v));}總結
以上就是本文關於淺談Java中ABA問題及避免的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題,如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!