Java中如何解決ABA問題

這篇文章主要為大家展示了“Java中如何解決ABA問題”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“Java中如何解決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(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問題”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！