CAS comparison and exchange

1. No, CAS Before

Multithreading environment does not use atomic classes to ensure thread safety （ Basic data type ）

public class T3
{
    
    volatile int number = 0;
    // Read 
    public int getNumber()
    {
    
        return number;
    }
    // Write locking ensures atomicity 
    public synchronized void setNumber()
    {
    
        number++;
    }
}

Multithreaded environment Use atomic classes to ensure thread safety （ Basic data type ）

public class T3
{
    
    volatile int number = 0;
    // Read 
    public int getNumber()
    {
    
        return number;
    }
    // Write locking ensures atomicity 
    public synchronized void setNumber()
    {
    
        number++;
    }
    //=================================
    //Atomic than synchronized Lightweight locks 、 concise , It can ensure atomic safety , No need synchronized Lock 
    AtomicInteger atomicInteger = new AtomicInteger();

    public int getAtomicInteger()
    {
    
        return atomicInteger.get();
    }

    public void setAtomicInteger()
    {
    
        atomicInteger.getAndIncrement(); // Get the value first , The value is being Increment ++
    }
}

2. CAS What is it?

compare and swap Abbreviation , Chinese translation into Compare and exchange , A technique commonly used in the implementation of concurrent algorithm . It contains three operands —— Memory location 、 Expected original value and updated value .
perform CAS During operation , Compare the value of the memory location with the expected original value ：
If Match , The processor will automatically update the location value to the new value ,
If Mismatch , The processor does nothing , Multiple threads executing at the same time CAS operation Only one will succeed .

CAS Yes 3 Operands , Location memory value V, Old expectations A, Update value to modify B.
If and only if the old expected value A And memory values V Phase at the same time , Put the memory value V It is amended as follows B, Otherwise, do nothing or start over
When it retries again, this behavior becomes ---- The spin ！！！

CAS yes JDK Provided Non blocking Atomic operation , It passes through Hardware assurance Compared - Updated atomicity .
It is non blocking and self atomic , That means it's more efficient and guaranteed by hardware , That means it's more reliable .

CAS It's a piece. CPU Atomic instructions for （cmpxchg Instructions ）, Will not cause so-called data inconsistency ,Unsafe Provided CAS Method （ Such as compareAndSwapXXX） The underlying implementation is CPU Instructions cmpxchg.
perform cmpxchg At the time of instruction , Will determine whether the current system is a multi-core system , Lock the bus if it is , Only one thread will lock the bus successfully , It will be executed after successful locking cas operation , in other words CAS The atomicity of CPU Realized , In fact, there are exclusive locks at this point , It's just a comparison synchronized, The exclusive time here is much shorter , So in the case of multithreading, the performance will be better

public class CASDemo
{
    
    public static void main(String[] args) throws InterruptedException
    {
    
        AtomicInteger atomicInteger = new AtomicInteger(5);
		//compareAndSet( Expected value , Update value )
        System.out.println(atomicInteger.compareAndSet(5, 2020)+"\t"+atomicInteger.get());//true 2020
        System.out.println(atomicInteger.compareAndSet(5, 1024)+"\t"+atomicInteger.get()); //false 2020
    }
}

Source code analysis compareAndSet(int expect,int update)

compareAndSet() Source code for method ：

The above three methods are similar , Mainly for 4 One parameter for explanation .
var1： Represents the object to operate on
var2： Represents the offset of the property address in the object to be manipulated
var4： Indicates the expected value of the data that needs to be modified
var5/var6： Indicates the new value to be modified to

3. CAS Underlying principle ？ Yes UnSafe The understanding of the

UnSafe

1. Unsafe yes CAS The core of the class , because Java Method cannot directly access the underlying system , Need to go through the local （native） Method to access ,Unsafe It's like a back door , Based on this class, you can directly operate the data of specific memory .Unsafe Class exists in sun.misc In bag (jdk route /jre/lib/rt.jar It's a bag ), Its internal method operation can be like C Of The pointer Operate memory directly , because Java in CAS Operation execution depends on Unsafe Class method .
   Be careful Unsafe All methods in the class are native Embellished , in other words Unsafe All methods in the class directly call the underlying resources of the operating system to perform the corresponding tasks

2. Variable valueOffset, Indicates the value of the variable in memory offset , because Unsafe Is to get the data according to the memory offset address .
   

3. Variable value use volatile modification , It ensures the communication between multiple threads Memory visibility .

i++ Thread unsafe , that atomicInteger.getAndIncrement()

CAS The full name is Compare-And-Swap( Compare and exchange ), It's a CPU Concurrent primitives .
Its function is to determine whether the value of a memory location is the expected value , If so, change to the new value , This process is atomic .
AtomicInteger Class mainly uses CAS (compare and swap) + volatile and native Method to ensure atomic operation , To avoid synchronized The high cost of , Greatly improved execution efficiency .

Source code analysis

new AtomicInteger().getAndIncrement();  // Execution process 

OpenJDK Check the source code Unsafe.java

Assuming that thread A And thread B Two threads execute at the same time getAndAddInt operation （ Run in different places CPU On ）：

1. AtomicInteger Inside value The original value is 3, In main memory AtomicInteger Of value by 3, according to JMM Model , Threads A And thread B Each holds a share with a value of 3 Of value Copies of are sent to Respective working memory .
2. Threads A adopt getIntVolatile(var1, var2) Get value value 3, When a thread A suspended .
3. Threads B Also through getIntVolatile(var1, var2) Method to get value value 3, This happens to be the thread B Not suspended And implement compareAndSwapInt Method comparison memory value is also 3, Successfully modified the memory value to 4, Threads B Finish off work , everything OK.
4. When a thread A recovery , perform compareAndSwapInt Methods to compare , Find the number in your hand 3 And main memory values 4 atypism , This indicates that the value has been modified by other threads first , that A Thread failed to modify this time , I can only read it again and do it again .
5. Threads A Recapture value value , Because of the variable value By volatile modification , So other threads modify it , Threads A Always be able to see , Threads A Carry on compareAndSwapInt Compare and replace , Until success .

Bottom assembly

native The decorated method represents the underlying method
Unsafe Class compareAndSwapInt, It's a local approach , The implementation of this method is located in unsafe.cpp in

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
//  First find a way to get the variable value Address in memory , According to the offset valueOffset, Calculation  value  The address of 
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
//  call  Atomic  The function in  cmpxchg To compare and exchange , The parameter x Is the value to be updated , Parameters e Is the value of the original memory 
//cas success , Return the expected value a, be equal to e, This method returns true
//cas Failure , Returns the... In memory value value , It's not equal to e, This method returns false
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

//JDK Provided CAS Mechanism , At the assembly level, Instruction Optimization on both sides of a variable is prohibited , And then use cmpxchg Instructions compare and exchange variable values ( Atomicity )

(Atomic::cmpxchg(x, addr, e)) == e;

---

cmpxchg Method

//  call  Atomic  The function in  cmpxchg To compare and exchange , The parameter x Is the value to be updated , Parameters e Is the value of the original memory 
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;

unsigned Atomic::cmpxchg(unsigned int exchange_value,volatile unsigned int* dest, unsigned int compare_value) {
    assert(sizeof(unsigned int) == sizeof(jint), "more work to do");
  /*
   *  Call overloaded functions on different platforms according to the type of operating system , During precompile, the compiler will decide which overloaded function to call */
    return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest, (jint)compare_value);
}

Different... Will be called under different operating systems cmpxchg overloaded function

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  // Judge if it's multi-core CPU
  int mp = os::is_MP();
  __asm {
    // Three move Instruction means to move the following value to the previous register 
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    //CPU Primitive level ,CPU Trigger 
    LOCK_IF_MP(mp)
    // Compare and exchange instructions 
    //cmpxchg:  namely “ Compare and exchange ” Instructions 
    //dword:  The full name is  double word  It means two words , Four bytes in all 
    //ptr:  The full name is  pointer, As in the previous  dword  Connect to use , Indicates that the memory unit being accessed is a doubleword unit  
    // take  eax  Value in register （compare_value） And  [edx]  Double word memory unit ,
    // If the same , Will  ecx  Value in register （exchange_value） Deposit in  [edx]  In the memory unit 
    cmpxchg dword ptr [edx], ecx
  }
}

It should be understood here CAS The real mechanism , It is finally completed by the assembly instructions of the operating system .

summary

Just remember ：CAS It is realized by hardware, so as to improve efficiency at the hardware level , At the bottom, it's up to the hardware to guarantee atomicity and visibility
The implementation is based on the assembly instructions of the hardware platform , stay intel Of CPU in (X86 On the machine ), Using assembly instructions cmpxchg Instructions .

The core idea is ： Compare the value of the variable to be updated V And the expected value E（compare）, Equality will make V Set the value of to the new value N（swap） If it's not equal The spin Come again .

4. Atomic reference AtomicReference

AtomicInteger Atomic integers , Can there be other atomic types ？ for example ：AtomicBook、AtomicOrder...

@Getter
@ToString
@AllArgsConstructor
class User
{
    
    String userName;
    int    age;
}


public class AtomicReferenceDemo
{
    
    public static void main(String[] args)
    {
    
        User z3 = new User("z3",22);
        User li4 = new User("li4",28);

        AtomicReference<User> atomicReferenceUser = new AtomicReference<>();

        atomicReferenceUser.set(z3);
        System.out.println(atomicReferenceUser.compareAndSet(z3,li4)+"\t"+atomicReferenceUser.get().toString());//true User(userName=li4, age=28)
        System.out.println(atomicReferenceUser.compareAndSet(z3,li4)+"\t"+atomicReferenceUser.get().toString());//false User(userName=li4, age=28)
    }
}

5. CAS With spinlocks , reference CAS thought

spinlocks （spinlock）

CAS It is the basis of realizing spin lock ,CAS utilize CPU Instructions ensure the atomicity of the operation , The lock effect has been achieved . Spin means that threads trying to acquire a lock do not immediately block , It is Try to acquire the lock in a circular way , When the thread finds that the lock is occupied , It loops to determine the status of the lock , Until you get it . In this way benefits Is to reduce the consumption of thread context switching , shortcoming It is a cycle that consumes CPU

---

OpenJDK Source code query Unsafe.java

CAS It is the basis of realizing spin lock , Spin locks are loops , It is usually realized by an infinite loop . thus , In an infinite loop , Execute one CAS operation

When the operation is successful, it returns true when , The loop ends ;
When to return to false when , Then execute the loop , Continue to try to CAS operation , Until return true

Manually implement a spin lock

/** *  requirement ： Implement a spin lock , review CAS thought  *  Spin lock benefits ： There is no such thing as circular comparison wait The block . * *  adopt CAS Operation complete spin lock ,A Thread first to call myLock Method own the lock 5 Second ,B Then came in and found  *  There are currently threads holding locks , So we can only wait through spin , until A After releasing the lock B And then grab . */
public class SpinLockDemo
{
    
    AtomicReference<Thread> atomicReference = new AtomicReference<>();

    public void lock()
    {
    
        Thread thread = Thread.currentThread();
        System.out.println(Thread.currentThread().getName()+"\t"+"----come in");
        while (!atomicReference.compareAndSet(null, thread)) {
    

        }
    }

    public void unLock()
    {
    
        Thread thread = Thread.currentThread();
        atomicReference.compareAndSet(thread,null);
        System.out.println(Thread.currentThread().getName()+"\t"+"----task over,unLock...");
    }

    public static void main(String[] args)
    {
    
        SpinLockDemo spinLockDemo = new SpinLockDemo();

        new Thread(() -> {
    
            spinLockDemo.lock();
            // Pause the thread for a few seconds 
            try {
     TimeUnit.SECONDS.sleep(5); } catch (InterruptedException e) {
     e.printStackTrace(); }
            spinLockDemo.unLock();
        },"A").start();

        // Pause 500 millisecond , Threads A Precede B start-up 
        try {
     TimeUnit.MILLISECONDS.sleep(500); } catch (InterruptedException e) {
     e.printStackTrace(); }

        new Thread(() -> {
    
            spinLockDemo.lock();

            spinLockDemo.unLock();
        },"B").start();
    }
}
// Execution results :
//A ----come in
//B ----come in
//A ----task over,unLock...
//B ----task over,unLock...

6. CAS shortcoming

1. The cycle time is long and the cost is high

You can see getAndAddInt Method execution , There is one do while

If CAS Failure , It's going to keep trying . If CAS It's been a long time without success , May give CPU High cost .

2. Lead out ABA problem ？？？

CAS It can lead to “ABA problem ”.

CAS An important premise of algorithm implementation is to extract the data in memory at a certain time and compare and replace it at the current time , So here Time difference Classes can cause data changes .

For example, a thread one From memory location V Remove from A, Now another thread two Also take it out of memory A, And threads two Some operations have been done to change the value to B,
Then the thread two And will be V The location data becomes A, At this point, the thread one Conduct CAS The operation found that the memory is still A, Then the thread one Successful operation .

Although thread one Of CAS Successful operation , But it doesn't mean that there is no problem in this process .

understand ： For example, you have a girlfriend , You went on a business trip . Your opponent is sharpening his knife , Old Wang next door is practicing waist , Someone came to help you care about your girlfriend . Lao Wang changed the value back after caring ( Clean up the scene ), But nothing has changed since you came back , The overall result is correct , however The process is not safe .

---

ABA Solution ： Version number 、 It is also called stamp flow

Version number timestamp atomic reference

1. CAS And AtomicStampedReference introduction

@NoArgsConstructor
@AllArgsConstructor
@Data
class Book
{
    
    private int id;
    private String bookName;
}


public class AtomicStampedDemo
{
    
    public static void main(String[] args)
    {
    
        Book javaBook = new Book(1,"javaBook");

        AtomicStampedReference<Book> stampedReference = new AtomicStampedReference<>(javaBook,1);

        System.out.println(stampedReference.getReference()+"\t"+stampedReference.getStamp());

        Book mysqlBook = new Book(2,"mysqlBook");

        boolean b;
        b = stampedReference.compareAndSet(javaBook, mysqlBook, stampedReference.getStamp(), stampedReference.getStamp() + 1);

        System.out.println(b+"\t"+stampedReference.getReference()+"\t"+stampedReference.getStamp());


        b = stampedReference.compareAndSet(mysqlBook, javaBook, stampedReference.getStamp(), stampedReference.getStamp() + 1);

        System.out.println(b+"\t"+stampedReference.getReference()+"\t"+stampedReference.getStamp());

    }
}
// Output results ：
//---------------------------
//Book(id=1, bookName=javaBook) 1
//true Book(id=2, bookName=mysqlBook) 2
//true Book(id=1, bookName=javaBook) 3
//----------------------------
// problem : You can see the contents of the first and third times ( Version number is not included ) It's consistent , But it has been modified once in the process , It is not safe to compare only by content 

CAS And ABA Problem solving ( Multithreading )

public class ABADemo
{
    
    static AtomicInteger atomicInteger = new AtomicInteger(100);
    static AtomicStampedReference<Integer> stampedReference = new AtomicStampedReference<>(100,1);
	
    // ABA Problem solving examples 
    public static void main(String[] args)
    {
    
        new Thread(() -> {
    
            int stamp = stampedReference.getStamp();
            System.out.println(Thread.currentThread().getName()+"\t"+" First version number ："+stamp);

            // Pause 500 millisecond , Guaranteed behind t4 The version number obtained by thread initialization is the same as mine 
            try {
     TimeUnit.MILLISECONDS.sleep(500); } catch (InterruptedException e) {
     e.printStackTrace(); }

            stampedReference.compareAndSet(100,101,stampedReference.getStamp(),stampedReference.getStamp()+1);
            System.out.println(Thread.currentThread().getName()+"\t"+"2 Sub Serial No ："+stampedReference.getStamp());

            stampedReference.compareAndSet(101,100,stampedReference.getStamp(),stampedReference.getStamp()+1);
            System.out.println(Thread.currentThread().getName()+"\t"+"3 Sub Serial No ："+stampedReference.getStamp());

        },"t3").start();

        new Thread(() -> {
    
            int stamp = stampedReference.getStamp();
            System.out.println(Thread.currentThread().getName()+"\t"+" First version number ："+stamp);

            // Pause 1 Second thread , Wait for the above t3 Threads , It happened. ABA problem 
            try {
     TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) {
     e.printStackTrace(); }

            boolean b = stampedReference.compareAndSet(100, 2022, stamp, stamp + 1);

            System.out.println(b+"\t"+stampedReference.getReference()+"\t"+stampedReference.getStamp());

        },"t4").start();
		/** *  Output results ： t3  First version number ：1 t4  First version number ：1 t3 2 Sub Serial No ：2 t3 3 Sub Serial No ：3 false 100 3 *  The final output false,t3 The thread changes the value from 100 Change to 101, And back to 100,t4 Threads pass through content + Version number ( Version number is different , Modification failed ) *  It can be seen that , Even if another thread in the middle has modified the value , Change back to the original value . Another thread passes through the content + The version number can solve the problem ABA problem  */
    }

    //ABA Problem recurrence 
    private static void abaHappen()
    {
    
        new Thread(() -> {
    
            atomicInteger.compareAndSet(100,101);
            try {
     TimeUnit.MILLISECONDS.sleep(10); } catch (InterruptedException e) {
     e.printStackTrace(); }
            atomicInteger.compareAndSet(101,100);
        },"t1").start();

        new Thread(() -> {
    
            try {
     TimeUnit.MILLISECONDS.sleep(200); } catch (InterruptedException e) {
     e.printStackTrace(); }
            System.out.println(atomicInteger.compareAndSet(100, 2022)+"\t"+atomicInteger.get());
        },"t2").start();
    }
}

summary ： Compare + Version number , Ensure thread safety