CAS compares the knowledge exchanged, ABA problems, and the process of lock upgrading

Catalog

CAS : Compare and Swap More exchange

1. Use CAS Implements the atomic class  

Suppose two threads call getAndIncrement 

2. Use CAS To achieve spin lock  

3. CAS It caused ABA problem

synchronized The process of lock upgrading behind keywords  

---

CAS : Compare and Swap More exchange

CAS It's an implementation of optimistic lock , The program doesn't block , Try again and again .
application 1. Atomic classes , stay java.util.concurrent(juc package 、 Concurrent toolkit ),

Such as ： Atomic classes , Thread safe collection ,ConcurrentHashMap,CopyOnWriteArrayList, All in juc It's a bag .

int i = 0; i++,i-- It's all non atomic operations , Multithreading concurrency has thread safety problems .

Use atomic classes to ensure its thread safety
AtomicInteger i = new Atomiclnteger();// Nonparametric construction defaults to 0AtomicIntegeri = new Atomiclnteger(10);1/ The default is from 10 Start counting

It won't really block threads , Keep trying to update  
Suppose the current value in main memory is V, The value in the working memory is A, The value to be modified by the current thread is B

CAS The operation process is as follows :
1. Compare the values in memory V And the value of the current working memory A Whether it is equal or not
2. If equal , It can be considered that the current main memory value has not been modified , The current thread will set the value B Write back to main memory
If not equal , Indicates the value of the current thread A It's out of date ( The main memory has changed ), The latest value of the current main memory V Save to the current working memory , At this time, you cannot B Write back to main memory , Continue to cycle .

When multiple threads are working on a resource at the same time CAS operation , Only one thread can operate successfully , But it doesn't block other threads , Other lines
The process will only receive the signal of operation failure .
CAS It can be regarded as an optimistic lock . ( Or it can be understood as CAS It's an implementation of optimistic lock )

CAS How did it happen
For different operating systems ,JVM Different CAS Realization principle , simply ：
java Of CAS Take advantage of unsafe This class provides CAS operation ;
unsafe Of CAS Rely on jvm For different operating systems Atomic::cmpxchg;
Atomic::cmpxchg The implementation of using the assembly of CAS operation , And use cpu Hardware provided lock The mechanism guarantees its atomicity .
In short , Because the hardware supports it , Only at the software level can .

1. Use CAS Implements the atomic class  

java.util.concurrent.atomic All classes in the package are thread safe atomic classes

i++ Thread unsafe .

public class AtomicTest {
    class Counter {
        AtomicInteger count = new AtomicInteger();
    }

    public static void main(String[] args) {
        // 0
        AtomicInteger count = new AtomicInteger();
        //  Atomic classes based on integer 
        //  Equate to  ++i 1
        System.out.println(count.incrementAndGet());
        //  Equate to  i++ 1
        System.out.println(count.getAndIncrement());
        // -- i 1
        System.out.println(count.decrementAndGet());
        // i -- 1
        System.out.println(count.getAndDecrement());
        // 0
        System.out.println(count.get());
    }
}

---

count.incrementAndGet(); Use CAS The mechanism guarantees atomicity

public class AtomicTest {
    static class Counter {
        AtomicInteger count = new AtomicInteger();

        void increase() {
            // i++
            count.incrementAndGet();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Counter counter = new Counter();
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 5000; i++) {
                counter.increase();
            }
        });
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 5000; i++) {
                counter.increase();
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(counter.count.get());
    }
}

Suppose two threads call getAndIncrement 

  Atomic pseudocode

class AtomicInteger {
    private int value;
    public int getAndIncrement() {
        int oldValue = value;
        while ( CAS(value, oldValue, oldValue+1) != true) {
            oldValue = value;
       }
        return oldValue;
    }
}

CAS Workflow pseudocode

boolean CAS(address, expectValue, swapValue) {
 if (&address == expectedValue) {
   &address = swapValue;
        return true;
   }
    return false;
}

2. Use CAS To achieve spin lock  

An implementation of optimistic locking
Spin lock means that the thread that fails to acquire the lock does not enter the blocking state , But in CPU Turn over ( Thread does not yield CPU, But run some useless instructions ), Constantly query the status of the current lock .

for example ： Wait for the traffic light , Step on the brake but the car doesn't stop .

Parameter interpretation

3. CAS It caused ABA problem

There are two threads t1 and t2, At the same time, modify the shared variables num, initial num == A.
Under normal circumstances , Only one thread will num Change the value to the correct value , Another thread is modifying num != A, The value of the working memory of another thread has expired , So it's impossible to modify .

ABA problem

Example

solve ABA problem

Introduce version number
Only when CAS in ,V == A The version number will be used , To determine the current main memory V Whether it has been repeatedly modified by other threads .
With the version number , In a thread 1 notice V == A, Before preparing to modify the value , Determine whether other threads have operated on the main memory , If there is an operation, it will not be modified .

synchronized The process of lock upgrading behind keywords  

It seems to be used synchronized keyword , What kind of lock is behind it , yes JVM To handle it .

JVM The lock implementation will be dynamically selected according to the intensity of competition .