(mobile phone horizontal screen source code is more convenient)
problem
(1) what is ABA?
(2) The harm of ABA?
(3) ABA solution?
(4) what is AtomicStampedReference?
(5) How does Atomic Stamped Reference solve ABA?
brief introduction
Atomic StampedReference is an atomic class provided under java Concurrent package. It can solve ABA problems that other atomic classes can not solve.
ABA
ABA problem occurs in a multithreaded environment. When a thread reads the same memory address twice in a row and gets the same value twice, it simply assumes that "the value of this memory address has not been modified". However, there may be another thread that modifies the value of this memory address from A to B and back to A between the two reads. At this time, it simply considers that "no". It's obviously wrong to have amended it.
For example, two threads execute in the following order:
(1) Thread 1 reads the value of memory location X as A;
(2) Thread 1 is blocked;
(3) Thread 2 reads the value of memory location X as A.
(4) Thread 2 modifies the value of memory location X to B.
(5) Thread 2 modifies the value of memory location X to A.
(6) Thread 1 resumes and continues to execute. Comparisons show that A sets the value of memory location X to C.
As you can see, for thread 1, the first A and the second A are not actually the same A.
ABA problems usually occur in unlocked structures, and the process of expressing them in code is probably like this:
public class ABATest { public static void main(String[] args) { AtomicInteger atomicInteger = new AtomicInteger(1); new Thread(()->{ int value = atomicInteger.get(); System.out.println("thread 1 read value: " + value); // Blocking 1s LockSupport.parkNanos(1000000000L); if (atomicInteger.compareAndSet(value, 3)) { System.out.println("thread 1 update from " + value + " to 3"); } else { System.out.println("thread 1 update fail!"); } }).start(); new Thread(()->{ int value = atomicInteger.get(); System.out.println("thread 2 read value: " + value); if (atomicInteger.compareAndSet(value, 2)) { System.out.println("thread 2 update from " + value + " to 2"); // do sth value = atomicInteger.get(); System.out.println("thread 2 read value: " + value); if (atomicInteger.compareAndSet(value, 1)) { System.out.println("thread 2 update from " + value + " to 1"); } } }).start(); } }
The printing results are as follows:
thread 1 read value: 1 thread 2 read value: 1 thread 2 update from 1 to 2 thread 2 read value: 2 thread 2 update from 2 to 1 thread 1 update from 1 to 3
Harm of ABA
To better understand the dangers of ABA, let's look at a practical example.
Suppose we have a lock-free stack structure, as follows:
public class ABATest { static class Stack { // Put top in the atomic class private AtomicReference<Node> top = new AtomicReference<>(); // Stack node information static class Node { int value; Node next; public Node(int value) { this.value = value; } } // Stack operation public Node pop() { for (;;) { // Get the top node of the stack Node t = top.get(); if (t == null) { return null; } // Next node on top of stack Node next = t.next; // CAS updates top to point to its next node if (top.compareAndSet(t, next)) { // To pop up the top element of the stack, the next should be emptied to prevent direct operation of the stack outside. t.next = null; return t; } } } // Stack operation [this article is written by the public number "Tong Ge read the source code" original). public void push(Node node) { for (;;) { // Get the top node of the stack Node next = top.get(); // Setting the top node of the stack as the next node of the new node node.next = next; // CAS updates top to point to new nodes if (top.compareAndSet(next, node)) { return; } } } } }
At first glance, there seems to be no problem with this procedure, but consider the following situation.
Suppose we initialize the stack structure as top - > 1 - > 2 - > 3, and then two threads do the following:
(1) Thread 1 executes pop() out of the stack, but it pauses before if (top. comparison AndSet (t, next){this line, so node 1 is not out of the stack at this time;
(2) Thread 2 executes pop() pop-up operation and pop-up node 1, when the stack becomes top - > 2 - > 3;
(3) Thread 2 executes pop() pop-up operation to pop up node 2, when the stack becomes top - > 3;
(4) Thread 2 performs push() to add node 1 to the stack, when the stack becomes top - > 1 - > 3;
(5) Thread 1 resumes execution, and the reference of Comparing Node 1 remains unchanged. CAS is successfully executed, when the stack becomes top - > 2.
What? The point solution becomes top - > 2? Shouldn't it be top - > 3?
That's because thread 1 saves next as node 2 in the first step, so when it executes CAS successfully, the top node points to node 2.
The test code is as follows:
private static void testStack() { // Initialization stack is top - > 1 - > 2 - > 3 Stack stack = new Stack(); stack.push(new Stack.Node(3)); stack.push(new Stack.Node(2)); stack.push(new Stack.Node(1)); new Thread(()->{ // Thread 1 stacks an element stack.pop(); }).start(); new Thread(()->{ // Thread 2 Out of Stack Two Elements Stack.Node A = stack.pop(); Stack.Node B = stack.pop(); // Thread 2 stacks A again stack.push(A); }).start(); } public static void main(String[] args) { testStack(); }
If (top. compareAndSet (t, next) of Stack's pop() method {break a breakpoint at which thread 1 blocks its execution and lets thread 2 finish executing and then execute thread 1. After executing this sentence, you can see that there are only two nodes in the top object of the stack.
Remember to hit the Thread breakpoint when interrupting. In IDEA, right-click and select Suspend as Thread.
Through this example, I think you must be very clear about the harm of ABA.
ABA Solution
We know the harm of ABA, so how to solve ABA?
The author summarizes the following ways:
(1) Version number
For example, the stack structure above adds a version number for control. Each CAS checks whether the version number has changed.
There are also some data structures that prefer to use a high level store with a postmark to ensure the security of CAS.
(2) References to non-reusable nodes
For example, the stack structure above creates a new node to pass in when thread 2 performs push() stacking operation, instead of multiplexing the reference of node 1.
(3) Direct manipulation of elements rather than nodes
For example, the stack structure push() method above should not pass in a node (Node), but an element value (value of int).
Okay, so much. Let's see how Atomic Stamped Reference in java solves ABA.^^
Source code analysis
Inner class
private static class Pair<T> { final T reference; final int stamp; private Pair(T reference, int stamp) { this.reference = reference; this.stamp = stamp; } static <T> Pair<T> of(T reference, int stamp) { return new Pair<T>(reference, stamp); } }
Bind element values and version numbers together and store them in Pair's reference and stamp.
attribute
private volatile Pair<V> pair; private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe(); private static final long pairOffset = objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);
Declare a Pair-type variable and use Unsfae to get its offset and store it in pairOffset.
Construction method
public AtomicStampedReference(V initialRef, int initialStamp) { pair = Pair.of(initialRef, initialStamp); }
The construction method needs to pass in the initial value and the initial version number.
compareAndSet() method
public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { // Get the current (element value, version number) pair Pair<V> current = pair; return // Citation unchanged expectedReference == current.reference && // The version number has not changed. expectedStamp == current.stamp && // New quotation is equal to old quotation ((newReference == current.reference && // The new version number equals the old version number. newStamp == current.stamp) || // Construct new Pair objects and update CAS casPair(current, Pair.of(newReference, newStamp))); } private boolean casPair(Pair<V> cmp, Pair<V> val) { // Call Unsafe's compareAndSwapObject() method CAS to update the pair's reference to a new reference return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val); }
(1) If the element value and version number do not change, and are the same as the new one, return true;
(2) If the element value and version number remain unchanged and are not exactly the same as the new one, a new Pair object is constructed and CAS update pair is executed.
As you can see, the implementation in java is consistent with the ABA solution we mentioned above.
First, version number control is used.
Secondly, instead of reusing the reference of Pair, a new Pair is created each time as the object of CAS comparison, instead of reusing the old one.
Finally, the value of the element and version number are passed in externally, rather than a reference to the node (Pair).
case
Let's use Atomic Stamped Reference to solve the ABA problem brought about by Atomic Integer at the beginning.
public class ABATest { public static void main(String[] args) { testStamp(); } private static void testStamp() { AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(1, 1); new Thread(()->{ int[] stampHolder = new int[1]; int value = atomicStampedReference.get(stampHolder); int stamp = stampHolder[0]; System.out.println("thread 1 read value: " + value + ", stamp: " + stamp); // Blocking 1s LockSupport.parkNanos(1000000000L); if (atomicStampedReference.compareAndSet(value, 3, stamp, stamp + 1)) { System.out.println("thread 1 update from " + value + " to 3"); } else { System.out.println("thread 1 update fail!"); } }).start(); new Thread(()->{ int[] stampHolder = new int[1]; int value = atomicStampedReference.get(stampHolder); int stamp = stampHolder[0]; System.out.println("thread 2 read value: " + value + ", stamp: " + stamp); if (atomicStampedReference.compareAndSet(value, 2, stamp, stamp + 1)) { System.out.println("thread 2 update from " + value + " to 2"); // do sth value = atomicStampedReference.get(stampHolder); stamp = stampHolder[0]; System.out.println("thread 2 read value: " + value + ", stamp: " + stamp); if (atomicStampedReference.compareAndSet(value, 1, stamp, stamp + 1)) { System.out.println("thread 2 update from " + value + " to 1"); } } }).start(); } }
The results are as follows:
thread 1 read value: 1, stamp: 1 thread 2 read value: 1, stamp: 1 thread 2 update from 1 to 2 thread 2 read value: 2, stamp: 2 thread 2 update from 2 to 1 thread 1 update fail!
You can see that thread 1 failed to update 1 to 3 at the last time, because the version number changed at that time, and the problem of ABA was successfully solved.
summary
(1) Attention should be paid to ABA when using lock-free structure in multi-threaded environment.
(2) The solution of ABA generally uses version number to control, and ensures that the data structure is transferred by element value, and every time the element is added, the new node bears element value.
(3) In Atomic Stamped Reference, Pair is used to store element values and their version numbers.
Egg
(1) What other classes in java can solve ABA's problems?
Atomic Markable Reference, it does not maintain a version number, but maintains a boolean type of markup, markup value has been modified, see.
(2) Have you ever encountered ABA problems in practical work?
The author also really encountered before, when playing chess game, ABCD four players, A player produced a card, and then his request has not arrived at the server, that is, overtime, the server will help him to automatically produce a card.
Then, turning around, it's the turn of the A players to play cards, saying that the coincidence is that the request came to the server before. The server detected that it was just A playing cards, and the request was also playing cards, so the card was played out.
Then, A players' cards are wrong.
Finally, we process each request by adding a sequence number, and detect that the expired sequence number request is discarded directly.
Have you ever encountered ABA problems?
Welcome to pay attention to my public number "Tong Ge read the source code", see more source series articles, and swim together with brother Tong's source ocean.
