浅谈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问题及避免的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
您可能感兴趣的文章:
- java并发编程之cas详解
- 全面了解Java中的CAS机制
- Java编程cas操作全面解析
- Java语言中cas指令的无锁编程实现实例
- java中switch case语句需要加入break的原因解析
- java实现cassandra高级操作之分页实例(有项目具体需求)
- 解决cannot be cast to javax.servlet.Filter 报错的问题
- Java并发编程总结——慎用CAS详解