This article mainly studies related content about ABA problems and avoidance in Java, as follows.
In Chapter 15 of the book "Java Concurrency Practical Practice", there is a concurrency stack implemented using atomic variables, and the code is as follows:
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;}}This example will not cause ABA problems. As for why it is not, I will explain it later. Let’s talk about the ABA problems first.
What is ABA?
Quote the original book: If the nodes in the algorithm can be used cyclically, this problem may occur when using the "Compare and Exchange" instruction. In the CAS operation, it will be judged that "Is the value of V still A?", and if so, the update operation will continue. In some algorithms, if the value of V first changes from A to B and then from B to A, then CAS will operate successfully.
Examples of ABA
Sometimes, the consequences caused by ABA are very serious. Let’s modify the example of concurrency stack to see what problems ABA will cause:
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;}}Pay attention to the changes here, Node has basically not changed
Focus on the changes in ConcurrentStack
1. Push method: Originally, using content to construct Node, but now directly pass in Node, which meets the requirement of "nodes in the algorithm can be recycled"
2. The sleep of the pop method, which simulates the execution of the thread in order to observe the results.
Let's first press two Nodes into the stack:
ConcurrentStack stack = new ConcurrentStack(); stack.push(new Node("A")); stack.push(new Node("B"));Then create two threads to perform operations entering and leaving the stack
Thread A first executes the stacking: Let NodeA out of the stack
stack.pop(3);
For some reason, thread A has been executed for a long time and has used 3 seconds
Thread B executes the stack and then enters the stack: First, NodeA and NodeB are released, and then let NodeD, NodeC, and NodeA be entered (NodeA is at the top of the stack)
Node A = stack.pop(0); stack.pop(0); stack.push(new Node("D")); stack.push(new Node("C")); stack.push(A);Note: Thread B implements the recycling of nodes. It first releases all the contents in the stack, and then puts them into the stack. Finally, the content on the top of the stack is the Node that was released before.
After thread B has performed these actions, thread A will execute CAS. At this time, CAS can execute successfully.
According to the original idea, after threads A and B execute, the content of stack should be: C and D, C is at the top of the stack, but the execution result here is that there is nothing in Stack, which is the ABA problem.
How to Avoid ABA Problems
AtomicStampedReference and AtomicMarkableReference are provided in Java to solve ABA problems
AtomicStampedReference can atomically update two values: reference and version number, and distinguish the node's cycle usage by version number. Let's see the example of 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();}}}Note: You cannot use the comment method, otherwise it will be no different from simply using atomic variables.
AtomicMarkableReference can atomically update a Boolean type marker bits and reference types, see the following example:
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));}Summarize
The above is all the content of this article about brief discussion on ABA problems and avoidance in Java. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!