浅谈Java中ABA问题及避免

本文主要研究的是关于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问题及避免的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！