浅谈Java中ABA问题及避免

时间:2022-11-09 15:24:00

本文主要研究的是关于Java中ABA问题及避免的相关内容,具体如下。

在《Java并发实战》一书的第15章中有一个用原子变量实现的并发栈,代码如下:

?
1
2
3
4
5
6
7
public class Node {
    public final String item;
    public Node next;
    public Node(String item){
        this.item = item;
    }
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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会造成什么问题:

?
1
2
3
4
5
6
7
public class Node {
    public final String item;
    public Node next;
    public Node(String item){
        this.item = item;
    }
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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:

?
1
2
3
ConcurrentStack stack = new ConcurrentStack();
stack.push(new Node("A"));
stack.push(new Node("B"));

然后创建两个线程来执行出入栈的操作

线程A先执行出栈:让NodeA出栈

?
1
stack.pop(3);

因为某些原因,线程A执行出栈比较久,用了3s

线程B执行出栈之后再入栈:先然NodeA和NodeB出栈,然后让NodeD,NodeC,NodeA入栈(NodeA在栈顶)

?
1
2
3
4
5
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的例子:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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可以原子更新一个布尔类型的标记位和引用类型,看下面的例子:

?
1
2
3
4
5
6
7
8
9
10
11
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问题及避免的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/li954644351/article/details/50511879