Coin163

首页 > ABA问题及避免

ABA问题及避免

2020腾讯云8月秒杀活动,优惠非常大!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1040

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
入口地址https://www.aliyun.com/minisite/goods

在《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并发实战》一书的第15章中有一个用原子变量实现的并发栈,代码如下: public class Node { public final String item; public Node next; public Node(String item){ this.item

------分隔线----------------------------
相关推荐