What are ABA problems

Anyone with a bit of familiarity with Java knows that CAS is compareAndSwap. The Unsafe class in Java provides native methods for manipulating memory directly, including an implementation of compareAndSwap.

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);Copy the code

Var1 here refers to the current object, var2 is the offset of a property of var1 in the current object, var4 is the expected value of the property of the offset var2, var5 is the value to be swapped, if the property of the object is the expected value, the exchange succeeds, otherwise the exchange fails, this is an atomic operation, Only one thread will succeed. So it’s also the premise of many Java thread-safe implementations.

For example, AtomicInteger Count starts with a value of 5 and two threads expect it to be set to 10; Both threads now call compareAndSet (also compareAndSwapObject)

public static void main(String[] args) {    final AtomicInteger count = new AtomicInteger(5);    for (int i = 0; i < 2; i++) {        Thread thread = new Thread(() -> {            try {                Thread.sleep(10);            } catch (Exception ignore) {            }            boolean re = count.compareAndSet(5, 10);            System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);        });        thread.start();    }}Copy the code

As we hoped, only one thread would succeed.

Now if you have another thread set 10 to 5

public static void main(String[] args) {    final AtomicInteger count = new AtomicInteger(5);    for (int i = 0; i < 2; i++) {        Thread thread = new Thread(() -> {            try {                Thread.sleep(10);            } catch (Exception ignore) {            }            boolean re = count.compareAndSet(5, 10);            System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);        });        thread.start();    }    Thread thread = new Thread(() -> {        try {            Thread.sleep(10);        } catch (Exception ignore) {        }        boolean re = count.compareAndSet(10, 5);        System.out.println(Thread.currentThread().getName() + " compareAndSet "+ re); }); thread.start(); }Copy the code

You might see something like this:

Normal? Normal and not normal. Normal as we understand it might look something like this, but do it a few times and you’ll see that it might look something like this:

We expect only a thread of 5 set to 10 successful results for two, like a cost to the user, the balance of 5 pieces, prepaid phone to 10 blocks, the load point for two times, at the same time also use this account to pay a sum of $5 orders, the desired cost is only a successful, payment can be successful, a result according to the equivalent of prepaid phone 2 times 5 dollars. This is the ABA problem in CAS.

How does AtomicStampedReference solve ABA problems

How to solve it? Each time after compareAndSwap, add 1 to the version number of the data. The next compareAndSwap compares both the data and the version number. If the value is the same, the execution fails even if the version number is different. An AtomicStampedReference is provided in Java to solve this problem

public static void main(String[] args) {    final AtomicStampedReference<Integer> count = new AtomicStampedReference<>(5, 1);    for (int i = 0; i < 2; i++) {        Thread thread = new Thread(() -> {            try {                Thread.sleep(10);            } catch (Exception ignore) {            }            boolean re = count.compareAndSet(5, 10, 1, 2);            System.out.println(Thread.currentThread().getName() + "[recharge] compareAndSet " + re);        });        thread.start();    }    Thread thread = new Thread(() -> {        try {            Thread.sleep(10);        } catch (Exception ignore) {        }        boolean re = count.compareAndSet(10, 5, count.getStamp(), count.getStamp() + 1);        System.out.println(Thread.currentThread().getName() + "[consume] compareAndSet "+ re); }); thread.start(); }Copy the code

This ensures that the recharge will only be successful once. So how does it get the version number updated every time?

AtomicStampedReference internally maintains a Pair data structure, which is volatile to ensure visibility and is used to package data objects and version numbers

private static class Pair<T> {    final T reference;    final int stamp;    private Pair(T reference, int stamp) {        this.reference = reference;        this.stamp = stamp;    }}Copy the code

Its compareAndSet method is as follows

public boolean compareAndSet(V   expectedReference,                             V   newReference,                             int expectedStamp,                             int newStamp) {    Pair<V> current = pair;    returnexpectedReference == current.reference && expectedStamp == current.stamp && ((newReference == current.reference && newStamp == current.stamp) || casPair(current, Pair.of(newReference, newStamp))); }Copy the code
  • First determine whether the parameters passed in match
    PairThe expected, from the data and version number of two aspects to judge, there is a do not meet the call back;
  • If the parameter is passed with
    PairAs in, return directly
    true, do not update;
  • use
    casPairTo compare and swap the current
    PairWith the passed parameter
    Pair;
  • casPairCall again
    compareAndSwapObjectTo interact
    PairProperties. 
private boolean casPair(Pair<V> cmp, Pair<V> val) {    returnUNSAFE.compareAndSwapObject(this, pairOffset, cmp, val); }Copy the code

To put it simply, atom Stampedreference adds the version number to solve the ABA problem of CAS. As for how to add a version number, since compareAndSwapObject can only compare and interact with one object, all you need to do is pack the data and version number into one object.

Java provides an AtomicMarkableReference, which is similar to an AtomicStampedReference except that your version number is replaced with a bool, You only care about whether the data is “modified”, whereas AtomicStampedReference cares about how many times the data is modified.