CAS source code analysis and ABA solution

CAS (compare and exchange) a small demo

import java.util.concurrent.atomic.AtomicInteger;

public class CasDemo {
    public static void main(String[] args) {
    	//The default initial value is 5, which means the value in main memory is 5
        AtomicInteger atomicInteger = new AtomicInteger(5);

        //compareAndSet expects to exchange and exchange. It is expected to be the first parameter. It is expected that the actual memory value is the same when the memory is taken away and when it is put back. What is the update value
        System.out.println(atomicInteger.compareAndSet(5, 2048));
        System.out.println("cas number:"+atomicInteger.get());

        System.out.println(atomicInteger.compareAndSet(5, 2222));
        System.out.println("cas number:"+atomicInteger.get());

    }
}


The first CAS is because the initialization AtomicInteger is 5, so the exchange is successful (the volatile keyword ensures the real-time synchronization of memory values is visible)
The second time the value of memory in CAS has been modified to 2048, so it cannot be modified and return false

Here is the source code of the atomic CAS class

    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

The first parameter is the expected value, that is, the expected value in memory. The second parameter is the updated value
compareAndSwapInt method source code, in the Unsafe class

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

It is a native local method, not implemented by Java
The function of the method is that Object var1 is the current object, long var2 is the memory offset of the current object, var4 is the operation to be performed, and var5 is the value of the current main memory address

CAS bottom principle
The address is operated directly, so the security can be guaranteed without adding sync lock. What can CAS guarantee atomicity depends on the underlying unsafe class, which is the operating system level operation, and directly calls the underlying resources of the operating system to perform corresponding tasks
Determined by the primitive, the primitive defaults to be continuous without interruption, that is to say, CAS is a CPU atomic instruction, which will not cause so-called data inconsistency

CAS spin lock
The same time period with sync can only be accessed by one thread
Consistency is guaranteed but concurrency is reduced

cas always circulates, which not only improves the consistency but also ensures the concurrency
Here is the application of CAS:
Autoincrement operation getAndIncrement() in AtomicInteger, where
this is the current object
ValueOffset is the current object memory offset
i is the operation of adding one

    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

CAS spin lock in getAndAddInt() method of Unsafe class

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

The first var5 is to save the value under the current address (that is, the value in the main physical memory) var5=this.getIntVolatile(var1,var2); (equivalent to first getting the value in auto increment 1 (the value of auto increment 1 is var4))

whlie means
Compare and exchange. First, check whether the value of the memory offset of var1 and var2 is the same as that of var5 just obtained. If they are the same, add var4, that is, add 1
var5 is expected
If the memory address of var1 and var2 is different from the expected value of var5, then this.compareAndSwapIntI(var1,var2,var5,var5 + var4) in the while loop is false and then! Take the reverse sign and continue to do the inner loop, then find the value on this memory address, and then make a comparison until the success (that is, when the value of var5 is the same as that of var1var2, this is also the spin of the spin lock). Will this continue to loop as long as it is not successful??? Doubt)

Doubt analysis!!!
Var5 in do will be updated. Because the address value VAR1 var2 of this object has been modified by volatile, we will continue this.compareAndSwapIntI(var1,var2,var5,var5 + var4) according to jmm memory, and it will succeed until now, because there may be many threads executing first when suspending

However, it will still cause cyclic operations that cannot match the value all the time, which is also a disadvantage of CAS

The second disadvantage is that only one object can be atomically operated, not one piece of code

The third disadvantage is the ABA problem
Generation of ABA problems:
The ABA problem is that the value added to main memory is A
(1) Both threads will go to main memory and get A value A
(2) Because t1 thread has a short execution time of two seconds, it performs the operation of a - > b - > a again
(3) Because of the JMM principle, the same operation is performed in main memory
(4) Thread t2 will exchange when it sees whether the value in main memory is A after execution, but it has been modified and changed back

Solve:
Add a time stamp. Every time you change it, it will increase automatically, which is equivalent to the version number
Using the atomic reference class AtomicStampedReference

    public AtomicStampedReference(V initialRef, int initialStamp) {
        pair = Pair.of(initialRef, initialStamp);
    }

Parameter 1 or object, parameter 2 is an initial version number
Then every time the value in main memory is changed, the version number will be changed, which effectively avoids the occurrence of ABA problems
To solve the ABA problem, demo is as follows

package com.wsx.aba;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicStampedReference;

public class SloveAba {
    static AtomicReference<Integer> atomicReference = new AtomicReference<>(100);
    static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(100,1);

    public static void main(String[] args) {
        System.out.println("ABA Problem generation");
        new Thread(()->{
            atomicReference.compareAndSet(100,101);
            atomicReference.compareAndSet(101,100);
            System.out.println(Thread.currentThread().getName()+"\t"+atomicReference.get());
        },"t1").start();

        new Thread(()->{
            try {
                //In order for t1 to complete an ABA operation
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            atomicReference.compareAndSet(100,2019);

            System.out.println(Thread.currentThread().getName()+"\t"+atomicReference.get());
        },"t2").start();

        //Main thread sleep waiting for upper limit operation to complete
        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("ABA Problem solving");


        new Thread(()->{
            int stamp = atomicStampedReference.getStamp();
            //Here, sleeping for a second is for the same starting point of t3 thread and t4 thread. The version number is 1
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println(Thread.currentThread().getName()+"\t Latest version number"+atomicStampedReference.getStamp());
            //ABA operation with version number
            atomicStampedReference.compareAndSet(100,101,atomicStampedReference.getStamp(),atomicStampedReference.getStamp()+1);
            System.out.println(Thread.currentThread().getName()+"\t Latest version number"+atomicStampedReference.getStamp());
            atomicStampedReference.compareAndSet(101,100,atomicStampedReference.getStamp(),atomicStampedReference.getStamp()+1);
            System.out.println(Thread.currentThread().getName()+"\t Latest version number"+atomicStampedReference.getStamp());

        },"t3").start();

        new Thread(()->{
            int stamp = atomicStampedReference.getStamp();
            //The purpose of sleeping for two seconds here is to let t3 thread complete ABA operation
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //The stamp here is the version number that has not been modified by default. If it has been modified by other threads, the version number here will start to lag behind, and then the modification fails
            boolean result = atomicStampedReference.compareAndSet(100, 2019, stamp, stamp + 1);

            System.out.println(Thread.currentThread().getName()+"\t Latest version number"+atomicStampedReference.getStamp());
            System.out.println(Thread.currentThread().getName()+"\t Whether the change is successful"+result);
            System.out.println(Thread.currentThread().getName()+"\t Latest value"+atomicStampedReference.getReference());
        },"t4").start();
    }

}



Published 18 original articles, won praise 19, visited 1418
Private letter follow

Tags: Java

Posted on Sat, 14 Mar 2020 04:38:33 -0700 by sayedsohail