Java中如何解決ABA問題

這篇文章主要為大家展示了“Java中如何解決ABA問題”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“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;
	}
}

這個(gè)例子并不會(huì)引發(fā)ABA問題，至于為什么不會(huì)，后面再講解，下面先講一下ABA問題

什么是ABA？

引用原書的話：如果在算法中的節(jié)點(diǎn)可以被循環(huán)使用，那么在使用“比較并交換”指令就可能出現(xiàn)這種問題，在CAS操作中將判斷“V的值是否仍然為A？”，并且如果是的話就繼續(xù)執(zhí)行更新操作，在某些算法中，如果V的值首先由A變?yōu)锽，再由B變?yōu)锳，那么CAS將會(huì)操作成功

ABA的例子

有時(shí)候，ABA造成的后果很嚴(yán)重，下面將并發(fā)棧的例子修改一下，看看ABA會(huì)造成什么問題：

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基本沒有變化

重點(diǎn)關(guān)注ConcurrentStack的變化

1、push方法：原來是使用內(nèi)容構(gòu)造Node，現(xiàn)在直接傳入Node，這樣就符合了“在算法中的節(jié)點(diǎn)可以被循環(huán)使用”這個(gè)要求

2、pop方法的sleep，這是模擬線程的執(zhí)行情況，以便觀察結(jié)果

我們先往stack中壓入兩個(gè)Node：

ConcurrentStack stack = new ConcurrentStack(); 
stack.push(new Node("A")); 
stack.push(new Node("B"));

然后創(chuàng)建兩個(gè)線程來執(zhí)行出入棧的操作

線程A先執(zhí)行出棧：讓NodeA出棧

stack.pop(3);

因?yàn)槟承┰颍€程A執(zhí)行出棧比較久，用了3s

線程B執(zhí)行出棧之后再入棧：先然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實(shí)現(xiàn)了節(jié)點(diǎn)的循環(huán)利用，它先將棧里面的內(nèi)容全部出棧，然后入棧，最后棧頂?shù)膬?nèi)容是之前出棧的Node

線程B執(zhí)行完這些動(dòng)作之后，線程A才執(zhí)行CAS，此時(shí)CAS是可以執(zhí)行成功的

按照原來的想法，線程A和B執(zhí)行之后，stack的內(nèi)容應(yīng)該是：C和D，C在棧頂，但這里的執(zhí)行結(jié)果卻是Stack中什么都沒有，這就是ABA問題

如何避免ABA問題

Java中提供了AtomicStampedReference和AtomicMarkableReference來解決ABA問題

AtomicStampedReference可以原子更新兩個(gè)值：引用和版本號(hào)，通過版本號(hào)來區(qū)別節(jié)點(diǎn)的循環(huán)使用，下面看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();
		}
	}
}

注意：不能使用注釋中的方式，否則就和單純使用原子變量沒有區(qū)別了

AtomicMarkableReference可以原子更新一個(gè)布爾類型的標(biāo)記位和引用類型，看下面的例子：

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問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！