当前位置:网站首页>How does atomicstampedreference solve the ABA problem of CAS

How does atomicstampedreference solve the ABA problem of CAS

2021-09-15 04:24:55 roshilikang

This article has been included https://github.com/lkxiaolou/lkxiaolou welcome star.

What is? ABA problem

Every right Java If you go a little deeper, you'll know CAS, namely compareAndSwap. stay Java Use in Unsafe Class provides the native Method can operate memory directly , One of them is right compareAndSwap The implementation of the .

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

there var1 refer to The current object ,var2 It's in the current object var1 The offset of an attribute of ,var4 It's the offset var2 The expected value of the corresponding attribute ,var5 Is the value to exchange , When the properties of an object are expected values , The interaction was successful , Otherwise the exchange fails , This is an atomic operation , Only one thread will succeed . So it's also a lot Java The premise of thread safe implementation of .

for instance AtomicInteger count The initial value of 5, Two threads expect it to be set to 10; At this point, both threads call compareAndSet( So is the bottom floor 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(510);
            System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);
        });
        thread.start();
    }
}

It will be as we wish , Only one thread will succeed .

At this point, if there is another thread, it will 10 Set 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(510);
            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(105);
        System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);
    });
    thread.start();
}

You might see the result :

Is it normal ? normal , It's not normal . Normal is the result of our understanding , But if you do it a few more times, you will find that there may be such an outcome :

What we expect 5 Set to 10 Only one thread will succeed, and two , It's like recharging users , balance 5 block , Recharge to 10 block , The hand is fast twice , I also used this account to pay for 5 Dollar order , The expectation is that recharge is only a success , Payment can succeed , According to the latter result, it is equivalent to recharging 2 Time 5 Yuan . This is it. CAS Medium ABA problem .

AtomicStampedReference How to solve ABA problem

How to solve ? The idea is simple , Every time compareAndSwap Add... To the version number of the data 1, The next time compareAndSwap It's not just about comparing data , Also compare version numbers , Same value , Different version numbers cannot be executed successfully .Java Provided in AtomicStampedReference To solve the problem

public static void main(String[] args) {
    final AtomicStampedReference<Integer> count = new AtomicStampedReference<>(51);

    for (int i = 0; i < 2; i++) {
        Thread thread = new Thread(() -> {
            try {
                Thread.sleep(10);
            } catch (Exception ignore) {
            }

            boolean re = count.compareAndSet(51012);
            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(105, count.getStamp(), count.getStamp() + 1);
        System.out.println(Thread.currentThread().getName() + "[consume] compareAndSet " + re);
    });
    thread.start();
}

This will ensure that the recharge will be successful only once . So how does it update the version number every time ?

AtomicStampedReference One was maintained internally Pair Data structure of , use volatile modification , Guaranteed visibility , 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;
    }
}

its compareAndSet The method is as follows

public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp)
 
{
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}
  • First, judge whether the parameters passed in conform to Pair The expected , Judging from the data and version number , If one doesn't match, call back ;
  • If the parameter passed in is the same as Pair The same as in China , Go straight back to true, Don't need to update ;
  • Use casPair To compare and exchange the current Pair With the input parameter Pair;
  • casPair Call again compareAndSwapObject To interact Pair attribute .
private boolean casPair(Pair<V> cmp, Pair<V> val) {
    return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}

So to put it simply ,AtomicStampedReference It's solved by adding version number CAS Of ABA problem . As for how to add the version number , because compareAndSwapObject Only one object can be compared , So just package the data and version number into one object to solve the problem .

Again Java Provided in AtomicMarkableReference, And AtomicStampedReference Similar principle , It's just AtomicMarkableReference Changed the version number to a bool value , It's only about whether the data “ Has been modified ”, and AtomicStampedReference You can care how many times the data has been modified .


WeChat official account " Master bug catcher ", Back end technology sharing , Architecture design 、 performance optimization 、 Source code reading 、 Troubleshoot problems 、 Step on the pit practice .

版权声明
本文为[roshilikang]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/09/20210909112309704w.html

随机推荐