The problem
(1) What is ABA?
(2) Harm of ABA?
(3) ABA solution?
(4) What is AtomicStampedReference?
(5) How does AtomicStampedReference solve ABA?
Introduction to the
AtomicStampedReference is an atom class provided in a Java package that solves AN ABA problem that no other atom class can solve.
ABA
ABA problem occurred in A multithreaded environment, when A thread reads the same block of memory address two consecutive times, twice to get the value of the same, it simply assume that the value of “this memory address has not been modified”, however, at the same time there may be another thread between the two reads the memory address values from A modified into B and change back to A, It is clearly wrong to simply say “no changes” at this point.
For example, two threads execute in the following order:
(1) Thread 1 reads the value of memory location X as A;
Thread 1 is blocked;
(3) Thread 2 reads the value of memory location X as A;
(4) Thread 2 changes the value of memory location X to B;
(5) Thread 2 changes the value of the memory location X to A;
(6) Thread 1 resumes and continues execution. It is found that thread A has set 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 an unlocked structure, and code for the above process looks something 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);
/ / block 1 s
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(); }}Copy the codeThe printed result is:
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
Copy the codeThe harm of ABA
To better understand the dangers of ABA, let’s look at a more realistic example.
Suppose we have an unlocked stack structure as follows:
public class ABATest {
static class Stack {
// Put top in the atomic class
private AtomicReference<Node> top = new AtomicReference<>();
// Node information in the stack
static class Node {
int value;
Node next;
public Node(int value) {
this.value = value; }}// Unstack
public Node pop(a) {
for (;;) {
// Get the top node
Node t = top.get();
if (t == null) {
return null;
}
// The next node on the stack
Node next = t.next;
// CAS update top points to its next node
if (top.compareAndSet(t, next)) {
Next should be cleared to prevent direct manipulation of the stack outside
t.next = null;
returnt; }}}// Push operation
public void push(Node node) {
for (;;) {
// Get the top node
Node next = top.get();
// Set the top node to the next node of the new node
node.next = next;
// CAS update top points to the new node
if (top.compareAndSet(next, node)) {
return;
}
}
}
}
}
Copy the codeAt first glance, there seems to be nothing wrong with this program, but consider the following situation.
If we initialize the stack to top->1->2->3, then two threads do the following:
If (top.compareAndSet(t, next)) {if (top.compareAndSet(t, next)) {if (top.compareAndSet(t, next));
Thread 2 performs pop() to eject node 1, and the stack changes to top->2->3.
(3) Thread 2 performs pop() to eject node 2, and the stack changes to top->3;
(4) Thread 2 performs push() to add node 1, and the stack changes to top->1->3.
(5) Thread 1 resumes execution, the reference of node 1 does not change, CAS is successfully executed, and the stack changes to top->2.
What? The point solution becomes top->2, right? Shouldn’t it be top->3?
That’s because thread 1 saved next to node 2 in the first step, so the top node points to node 2 after it successfully executes CAS.
The test code is as follows:
private static void testStack(a) {
// Initialize stack 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 pushes out an element
stack.pop();
}).start();
new Thread(()->{
Thread 2 pushes two elements out of the stack
Stack.Node A = stack.pop();
Stack.Node B = stack.pop();
Thread 2 pushes A onto the stack again
stack.push(A);
}).start();
}
public static void main(String[] args) {
testStack();
}
Copy the codeIf (top.compareAndSet(t, next)) {if (top.compareAndSet(t, next)) {if (top.compareAndSet(t, next)) {if (top.compareAndSet(t, next)) {
Make sure to hit the Thread breakpoint when you break the point. In IDEA, right-click Suspend to select Thread.
From this example, I assume that you are well aware of the dangers of ABA.
ABA solution
The harm of ABA is clear, so how to deal with ABA?
The author summarizes, there are probably the following ways:
(1) Version number
For example, the stack structure above adds a version number for control, and checks whether the version number has changed each time the CAS is executed.
Other data structures like to store a postmark in high places to secure the CAS.
(2) Do not reuse references to nodes
For example, the stack structure above creates a new node when thread 2 pushes (), rather than multiplexing node 1’s reference.
(3) Operate directly on elements instead of nodes
For example, the stack structure push() method above should not pass in a Node, but an element value (int value).
So let’s see how your Atom ference addresses ABA
Source code analysis
The 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 newPair<T>(reference, stamp); }}Copy the codeBind the element value to the version number and store it in the 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);
Copy the codeDeclare a variable of type Pair and use Unsfae to get its offset and store it in pairOffset.
A constructor
public AtomicStampedReference(V initialRef, int initialStamp) {
pair = Pair.of(initialRef, initialStamp);
}
Copy the codeThe constructor needs to pass in an initial value and an 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
// The reference is unchanged
expectedReference == current.reference &&
// The version number has not changed
expectedStamp == current.stamp &&
// The new reference equals the old reference
((newReference == current.reference &&
// The new version number equals the old version number
newStamp == current.stamp) ||
// Construct a new Pair and CAS update
casPair(current, Pair.of(newReference, newStamp)));
}
private boolean casPair(Pair<V> cmp, Pair<V> val) {
// Calling the Unsafe compareAndSwapObject() method CAS updates the pair reference to a new reference
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}
Copy the code(1) Return true if the element value and version number have not changed and are the same as new;
(2) If the element value and version number have not changed and are not exactly the same as the new Pair, construct a new Pair and execute CAS update Pair.
As you can see, the implementation in Java is consistent with the ABA solution we described above.
First, use version number control;
Second, references to nodes (pairs) are not reused. Each time a new Pair is created as the object for CAS comparison, rather than reuse the old one.
Finally, the element value and version number are passed in externally instead of a reference to the node (Pair).
case
Let’s use an AtomicStampedReference to solve the ABA problem brought about by the initial AtomicInteger.
public class ABATest {
public static void main(String[] args) {
testStamp();
}
private static void testStamp(a) {
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);
/ / block 1 s
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(); }}Copy the codeThe running 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!
Copy the codeYou can see that thread 1 failed when it finally updated from 1 to 3, because the version number also changed, successfully resolving the ABA problem.
conclusion
(1) ABA should be paid attention to when using lock-free structure in multi-threaded environment;
(2) THE ABA solution is generally controlled by the version number, and ensures that the data structure is transmitted by the element value, and each time the element is added, a new node is created to bear the element value;
(3) Pairs are used to store element values and version numbers inside an AtomicStampedReference.
eggs
(1) What other classes in Java can solve the ABA problem?
AtomicMarkableReference, which maintains not a version number, but a Boolean tag with a modified value.
(2) Have you encountered ANY ABA problems in actual work?
The author also really encountered, before do chess and card game, ABCD four players, A player out of A card, and then he this request has not been to the server, that is, timeout, the server will help him automatically out of A card.
Then, turned A circle, and turn A player card, said coincidence, just at this time before the request to the server, the server detected that is now just A card, and the request is also A card, put this card out.
And then what happens? Player A has the wrong card.
Finally, we do this by adding a sequence number to each request, and discard requests that detect an expired sequence number.
Have you ever had ABA problems?
Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
