CAS operation

What is? CAS

CAS（Compare And Swap, Compare and exchange ）, It usually refers to such an atomic operation ： For a variable , First compare its memory value with an expected value , If the same , Just give it a new value .CAS The logic of is described in pseudocode as follows ：

if (value == expectedValue) {
   value = newValue;
}

The above pseudo code describes a composite operation consisting of two phases of comparison and assignment ,CAS It can be seen as a whole of them

—— An indivisible atomic operation , And its atomicity is directly guaranteed at the hardware level .

CAS Can be seen as an optimistic lock （ Compare the pessimism of the database 、 Optimism lock ） An implementation of ,Java The incremental operation in the atomic class passes CAS Spin realized .

CAS It's a lock free algorithm , Without using locks （ No threads are blocked ） In the case of multithreading to achieve variable synchronization .

CAS application

stay Java in ,CAS The operation was carried out by Unsafe Class , This class defines three different types of variables CAS operation ,

public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object x);

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

public final native boolean compareAndSwapLong(Object o, long offset, long expected, long x);

They are all native Method , from Java Virtual machine provides specific implementation , It means different Java Virtual machines may implement them slightly differently .

With compareAndSwapInt For example ,Unsafe Of compareAndSwapInt Method reception 4 Parameters , Namely ： Object instances 、 Memory Offset 、 Field expectations 、 New value of field . This method is executed for the corresponding offset field in the specified object instance CAS operation .

public class UnsafeFactory {
    /**
     *  obtain  Unsafe  object  * @return
     */
    public static Unsafe getUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);

        } catch (Exception e) {
            e.printStackTrace();

        }
        return null;

    }

    /**
     *  Get the memory offset of the field   
     * @param unsafe  
     * @param clazz  
     * @param fieldName  
     * @return
     */
    public static long getFieldOffset(Unsafe unsafe, Class clazz, String fieldNam e) {
        try {
            return unsafe.objectFieldOffset(clazz.getDeclaredField(fieldName));

        } catch (NoSuchFieldException e) {
            throw new Error(e);

        }
    }
}

test

in the light of entity.x Of 3 Time CAS operation , Try to separate it from 0 Change to 3、 from 3 Change to 5、 from 3 Change to 8. The results are as follows ：

CAS The essence is one CPU Atomic instructions for , Guaranteed by operating system hardware . Different operating systems and different CPU It will be different Realization .

CAS stay Java Application in language

stay Java In programming, we usually don't directly use CAS, It's all through JDK Encapsulated concurrency tool classes for indirect use , These concurrency tool classes are java.util.concurrent In bag .

J.U.C yes java.util.concurrent For short , That's what people say Java Concurrent programming toolkit , Interviews often test , Very, very important .

stay java.util.concurrent.atomic The package provides a set of atomic operation classes ：

• Basic types ：AtomicInteger、AtomicLong、AtomicBoolean;
• Reference type ：AtomicReference、AtomicStampedRerence、AtomicMarkableReference;
• An array type ：AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray
• Object attribute atomic modifier ：AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater
• Atomic type accumulator （jdk1.8 Added class ）：DoubleAccumulator、DoubleAdder、 LongAccumulator、LongAdder、Striped64

Basic types of atomic renewal

With AtomicInteger Summarize common methods as an example

    // Add the original value in the instance by atom 1, It returns the old value before auto increment ;
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

    //getAndSet(int newValue)： Update the value in the instance to the new value , And return the old value ; 、
    public final boolean getAndSet(boolean newValue) {
        boolean prev;
        do {
            prev = get();
        } while (!compareAndSet(prev, newValue));
         return prev;

    }
    //incrementAndGet() ： Add the original value in the instance in the atomic way 1 operation , And return the result of the final addition ;
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;

    }

    //addAndGet(int delta) ： Add the input value to the original value in the example in atomic mode , And return to the last knot   fruit ;
    public final int addAndGet(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
    }

test

public class AtomicIntegerTest {
    static AtomicInteger sum = new AtomicInteger(0);

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            new Thread(() ->{
                for (int j = 0; j < 10000; j++) {
                    //  Atoms grow by themselves  CAS 
                    sum.incrementAndGet();
                }
            }).start();
        } 
        try {
            Thread.sleep(3000);

        } catch (InterruptedException e) {
            e.printStackTrace();

        }
        System.out.println(sum.get());
    }
}

incrementAndGet() Methods by CAS Self increasing realization , If CAS Failure , Spin until success +1.

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

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;
}

CAS defects

CAS Although the efficient solution to the atomic operation , But there are still some defects , Mainly in three aspects ：

• The spin CAS For a long time without success , Will give CPU It's very expensive
• Only one shared variable atomic operation can be guaranteed
• ABA problem

LongAdder/DoubleAdder

   CAS At high level , There will be a lot of failures and constant spin , At this point, spin will become a bottleneck . This is it. LongAdder The original intention of the introduction —— Solve the problem of high concurrency AtomicInteger,AtomicLong Spin bottleneck problem .

LongAdder The basic idea is to disperse hot spots , take value Values are spread into an array , Different threads will hit different slots in the array , Each thread only performs on that value in its own slot CAS operation , So the hot spots are scattered , The probability of conflict is much smaller . If you want to get real long value , Just add up the variable values in each slot and return to .

LongAccumulator

LongAccumulator yes LongAdder Enhanced Edition .LongAdder You can only add and subtract from numerical values , and LongAccumulator Provides custom function operations . The constructor is as follows ：

adopt LongBinaryOperator, You can customize any operation of the input parameter , And return the result （LongBinaryOperator

receive 2 individual long As a parameter , And back to 1 individual long）.LongAccumulator Internal principles and LongAdder Almost exactly , All use the parent class Striped64 Of longAccumulate Method .

public static void main(String[] args) throws InterruptedException {
    //  Add up  x+y
    LongAccumulator accumulator = new LongAccumulator((x, y) -> x + y, 0);
    ExecutorService executor = Executors.newFixedThreadPool(8); 
    // 1 To 9 Add up  
    IntStream.range(1, 10).forEach(i -> executor.submit(() -> accumulator.accumulate(i)));
    Thread.sleep(2000);
    System.out.println(accumulator.getThenReset());
}

ABA Solutions to problems

Java The corresponding atomic reference class is provided AtomicStampedReference<V>;reference That is, the variables we actually store ,stamp It's the version , Each modification can be made through +1 Ensure version uniqueness . In this way, you can ensure that the version after each modification will also increase upward .

Add ：AtomicMarkableReference It can be understood as the above AtomicStampedReference A simplified version of the , Just don't care how many times it has been modified , Just care about whether it has been modified . So the variable mark yes boolean type , Only record whether the value has been modified .