Concurrent programming (VI) ABA problems and solutions under CAS

List of articles

One ： A computer model &volatile Keyword details
Two ：java Lock system in
3、 ... and ：synchronized Keyword details
5、 ... and :Atomic Atomic class and Unsafe Detailed explanation of magic
6、 ... and :CAS Next ABA Problems and Solutions

---

---

One 、CAS Problem introduction

In concurrency problems , The first thought is undoubtedly mutually exclusive synchronization , But thread blocking and wakeup bring great performance problems , The core of synchronization lock is nothing more than preventing the problems caused by concurrent modification of shared variables , But there is not always such a competitive relationship .

Two 、CAS What is it?

CAS, Compare and exchange （Compare-and-Swap,CAS）, If the expected value is the same as the main memory value , Then exchange the values to be updated , Also known as optimistic lock , It's a common way to reduce read-write lock conflicts , Optimistic locking mechanism to ensure data consistency .

For example, thread a copies variables from main memory A by 1, Copy in your own thread A Change it to 10, When thread a is ready to update this variable to main memory , If the main memory A The value of does not change （ Expectations ）, still 1, Then thread a successfully updates the main memory A Value . But if the main memory A The value of has been changed by other threads first 1, Then thread a keeps trying again , Until we succeed （ The spin ）
CAS The idea is very simple ： Three parameters , A current memory value V、 Old expectations A、 Value to be updated B, If and only if expected A And memory values V Phase at the same time , Change the memory value to B And back to true, Otherwise, do nothing , And back to false

3、 ... and 、ABA Problem analysis

1、 The introduction of questions

• Bank deposit and withdrawal

• Thieves steal money

2、ABA Problem code

 static AtomicInteger atomicInteger = new AtomicInteger(1);
    public static void main(String[] args) {
    
       CompletableFuture.runAsync(()->{
    
           int a = atomicInteger.get();
           System.out.println(" Operation thread "+Thread.currentThread().getName()+"-- Operation value before modification :"+a);
           try {
    
               Thread.sleep(1000);
           } catch (InterruptedException e) {
    
               e.printStackTrace();
           }
           boolean isCasSuccess = atomicInteger.compareAndSet(a,2);
           if(isCasSuccess){
    
               System.out.println(" Operation thread "+Thread.currentThread().getName()+"--Cas Operation value after modification :"+atomicInteger.get());
           }else{
    
               System.out.println("CAS Modification failed ");
           }
       });

        CompletableFuture.runAsync(()->{
    
            atomicInteger.incrementAndGet();// 1+1 = 2;
            System.out.println(" Operation thread "+Thread.currentThread().getName()+"--increase After value :"+atomicInteger.get());
            atomicInteger.decrementAndGet();// atomic-1 = 2-1;
            System.out.println(" Operation thread "+Thread.currentThread().getName()+"--decrease After value :"+atomicInteger.get());
        });

    }

Execution results ： Threads 2 Get a value equal to 1, The thread 3 The value is also 1, here +1 be equal to 2, And then decrease 1 be equal to 1, The thread 1 update operation , The expectation is 1, The update value is 2, So it can be updated successfully , But threads already exist during this period 3 This value was manipulated twice .

3、 Concurrent business scenarios ABA The resulting problem has been solved

ABA The cause of the problem , yes CAS The process was simple “ value ” The check , In some cases ,“ value ” The same will not introduce wrong business logic （ For example, order inventory ）, In some cases ,“ value ” Although the same , But it's not the original data

3.1、 problem

In the system , The total inventory of a commodity is 5, user 1 And the user 2 Place an order at the same time
user 1 bought 3 Inventory , So the inventory should be set to 2
user 2 bought 2 Inventory , So the inventory should be set to 3
These two interfaces for setting inventory execute concurrently , Inventory will first become 2, And then become 3, Leading to data inconsistency （ Actually sold 5 Commodity , But the inventory is only deducted 2, The last inventory setting will overwrite and mask the previous concurrent operation ）

3.2、 reason

The root cause of data inconsistency , It is when the setting operation occurs , Did not check whether there is any change between the inventory and the queried inventory , Theoretically ：
Only inventory is 5 When , user 1 Inventory settings for 2 To succeed
Only inventory is 5 When , user 2 Inventory settings for 3 To succeed

In practice ：
Inventory is 5, user 1 Of set stock 2 It really should succeed

Inventory into 2 了 , user 2 Of set stock 3 Should fail

3.3、 solve

In the example above , When the update operation is performed , Just bring the version number

Four 、ABA Problem solving

To optimize the direction ：CAS We can't just compare “ value ”, It's also important to make sure that the original data , To modify it successfully .

1、AtomicStampReference

AtomicStampReference stay cas A mark is added on the basis of stamp, Using this tag can be used to detect whether the data has changed , It brings a kind of effectiveness test to the data . It has the following parameters ：

// The meanings of parameters are   Expectations , The new value written , Expected tag , New tag value 
public boolean compareAndSet(V expected,V newReference,int expectedStamp,int newStamp);
public V getRerference();
public int getStamp();
public void set(V newReference,int newStamp);

2、AtomicStampReference Use case of

    private static AtomicStampedReference<Integer> atomicStampedRef =
            new AtomicStampedReference<>(1, 0);
    public static void main(String[] args) throws InterruptedException {
    
        CountDownLatch countDownLatch = new CountDownLatch(2);
        CompletableFuture.runAsync(()->{
    
            int stamp = atomicStampedRef.getStamp(); // Get the current identifier 
            System.out.println(" Operation thread " + Thread.currentThread()+ "stamp="+stamp + ", Initial value  a = " + atomicStampedRef.getReference());
            try {
    
                Thread.sleep(1000); // wait for 1 second  , So that the interfering thread can execute 
            } catch (InterruptedException e) {
    
                e.printStackTrace();
            }
            boolean isCASSuccess = atomicStampedRef.compareAndSet(1,2,stamp,stamp +1);  // here expectedReference No change , however stamp It has been modified , therefore CAS Failure 
            System.out.println(" Operation thread " + Thread.currentThread() + "stamp="+stamp + ",CAS Operating results : " + isCASSuccess);
            countDownLatch.countDown();
        });
        CompletableFuture.runAsync(()->{
    
            int stamp = atomicStampedRef.getStamp();
            atomicStampedRef.compareAndSet(1,2,stamp,stamp+1);
            System.out.println(" Operation thread " + Thread.currentThread() + "stamp="+atomicStampedRef.getStamp() +",【increment】 , value  = "+ atomicStampedRef.getReference());
            stamp = atomicStampedRef.getStamp();
            atomicStampedRef.compareAndSet(2,1,stamp,stamp+1);
            System.out.println(" Operation thread " + Thread.currentThread() + "stamp="+atomicStampedRef.getStamp() +",【decrement】 , value  = "+ atomicStampedRef.getReference());
            countDownLatch.countDown();
        });
        countDownLatch.await();
    }

Execution results ： Threads 2 Get a value equal to 1, The tag value is also 0, The thread 3 The value is also 1, The tag value is also 0, here +1 be equal to 2, Marker value +1 yes 1; And then decrease 1 be equal to 1, Marker value +1 be equal to 2, The thread 1 update operation , The expectation is 1, Tag value is 0, The update value is 2, Therefore, it cannot be updated successfully

summary

Except AtomicStampedReference class , There is also an atomic class that can be solved , Namely AtomicMarkableReference, It's not about maintaining a version number , It's about maintaining a boolean Type of mark , There is no usage AtomicStampedReference flexible . Therefore, it is only used in specific scenarios