Catalog

•  CAS ( Compare and swap)
•  1、 analysis CAS
•  2、CAS application
•  1. be based on CAS Can achieve “ Atomic classes ”
•   How to implement atomic classes
•  2. be based on CAS Can realize spin lock
•  CAS Medium ABA problem
•   How to solve ABA problem
•   Relevant interview questions
•  ① Explain what you understand CAS Mechanism
•  ② ABA How to solve the problem ？

CAS ( Compare and swap)

1、 analysis CAS

CAS： Full name Compare and swap, Literally ：” Compare and exchange “, One CAS The following operations are involved ：

Let's assume that the raw data in memory V, Old expectations A, New values that need to be modified B.

1. Compare A And V whether equal .（ Compare ）
2. If it's equal , take B write in V.（ In exchange for ）
3. Whether the return operation is successful

CAS Pseudo code ：

The code written below is not atomic , Actual CAS It is completed by an atomic hardware instruction . This pseudo code is just an aid to understanding
CAS workflow .

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

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
     

What's called here is CAS , refer to CPU Provides a separate CAS Instructions , Through this CPU Instructions , You can complete all the things that the pseudo code above needs to do .

What we are discussing here CAS, In fact, this is the one discussed CPU Instructions .
 
This The code is obviously thread unsafe

however If the above is “ An order ”,（CPU The above instructions are executed one by one ） At this point, the thread is safe

CAS The greatest significance , Let's write this kind of multithread safe code , It provides a new idea and direction ( It's different from a lock )

A lot of features , It can be implemented in hardware , It can also be realized by software

Just like the comparison and exchange logic just now , This is equivalent to the direct implementation of hardware , Through this instruction , Package it , Let's use it directly

2、CAS application

1. be based on CAS Can achieve “ Atomic classes ”

Java The standard library provides a set of atomic classes , More for the commonly used int, long, int array… It was packaged , Can be based on CAS The way to modify , And thread safety whole

java.util.concurrent.atomic package , The classes inside are implemented in this way

Typical is AtomicInteger class . Among them getAndIncrement amount to i++ operation .

import java.util.concurrent.atomic.AtomicInteger;

public class Demo27 {
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger num = new AtomicInteger(0);

        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 50000; i++) {
                //  This method is equivalent to  num++
                num.getAndIncrement();
            }
        });
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 50000; i++) {
                //  This method is equivalent to  num++
                num.getAndIncrement();
            }
        });

// // ++num
// num.incrementAndGet();
// // --num
// num.decrementAndGet();
// // num--
// num.getAndDecrement();
// // += 10
// num.getAndAdd(10);

        t1.start();
        t2.start();
        t1.join();
        t2.join();

        //  adopt  get  Method to get   Atomic classes   Internal values .
        System.out.println(num.get());
    }
}

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
      
11.
      
12.
      
13.
      
14.
      
15.
      
16.
      
17.
      
18.
      
19.
      
20.
      
21.
      
22.
      
23.
      
24.
      
25.
      
26.
      
27.
      
28.
      
29.
      
30.
      
31.
      
32.
      
33.
      
34.
      
35.
      
36.
      
37.
     

Running results ：

100000

     

      
1.
     

In this code There is no thread safety issue , be based on CAS Realized ++ operation

This can ensure that both Thread safety , And can compare with synchronized Efficient ,``synchronized` It will involve locks

competition , Two threads have to wait for each other CAS Thread blocking and waiting are not involved

Method ：

num.incrementAndGet(); // ++num
num.decrementAndGet(); // --num
num.getAndIncrement(); // num++;
num.getAndDecrement(); // num--;
num.getAndAdd(10); // += 10

     

      
1.
      
2.
      
3.
      
4.
      
5.
     

How to implement atomic classes

How to implement atomic classes ？

Pseudo code implementation :

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

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
      
11.
     

The illustration ：

The picture means ： Suppose two threads call getAndIncrement

1. Both threads read value Value to oldValue in . (oldValue Is a local variable , On the stack . Each thread has its own stack )
2. Threads 1 Execute first CAS operation . because oldValue and value The value of is the same , Direct to value assignment
3. Threads 2 Re execution CAS operation , for the first time CAS Found that oldValue and value It's not equal , Cannot assign . Therefore, it is necessary to enter the cycle .
   Reread in the loop value The value is assigned to oldValue
4. Threads 2 Next, execute... For the second time CAS, here oldValue and value identical , So the assignment operation is performed directly
5. Threads 1 and Threads 2 Go back to their own oldValue The value of the can

2. be based on CAS Can realize spin lock

be based on CAS Achieve more flexible locks , Gain more control

Spin lock pseudocode ：

public class SpinLock {
    private Thread owner = null; //  Record which thread holds the current lock , by  null  Indicates that there is no lock at present 
    
    public void lock(){
    //  adopt  CAS  See if the current lock is held by a thread .
    //  If the lock is already held by another thread ,  Then wait .
    //  If the lock is not held by another thread ,  Then put  owner  Set to the thread currently trying to lock .
        while(!CAS(this.owner, null, Thread.currentThread())){
        }
    }
    
    public void unlock (){
        this.owner = null;
    }
}

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
      
7.
      
8.
      
9.
      
10.
      
11.
      
12.
      
13.
      
14.
      
15.
     

The illustration ：

CAS Medium ABA problem

ABA problem ： Namely CAS The key to 【 Compare first , In exchange for 】

Here... And here , In fact Compare Current value and The old value Is it the same Of .

When these two values are the same , It is considered that there has been no change in the middle .

But the conclusion here has this loophole .

Current value and The old value identical , Maybe it hasn't changed in the middle .
It may also have changed , But it changed back .

【 Although the final value is the same as the old value , But it did change 】

And the current decision is very hasty , As long as the values are the same, there is no change .
Such loopholes , in the majority of cases , In fact, it doesn't affect .
however , In extreme cases, it can also cause bug.
This kind of problem , This is called ABA problem .

So-called ABA refer to ：

The old value A, The current value is also A.

result You don't know the current A, It has always been A, Or from the A Turned into B, Again from B It's back to A.

for — A typical example ,ABA Problems arise bug：

hypothesis Yes 100 deposit . Funny want to start from ATM take 50 Yuan . The ATM creates two threads , Execute concurrently -50 operation
We Expect a thread to execute -50 success , Another thread -50 Failure .
If you use CAS To complete There may be problems in this deduction process .

Normal process ：

1. deposit 100. Threads 1 The current deposit value obtained is 100, Expect to update to 50; Threads 2 The current deposit value obtained is 100, period
   Hope to update to 50.
2. Threads 1 Deduction successfully executed , The deposit was changed to 50. Threads 2 Blocking waiting .
3. It's the thread's turn 2 Yes , It is found that the current deposit is 50, And what I read before 100 inequality , Execution failure .

Abnormal process ：

1. deposit 100. Threads 1 The current deposit value obtained is 100, Expect to update to 50; Threads 2 The current deposit value obtained is 100, period
   Hope to update to 50.
2. Threads 1 Deduction successfully executed , The deposit was changed to 50. Threads 2 Blocking waiting .
3. In a thread 2 Perform before , Funny friends just give funny money 50, The account balance becomes 100 !
4. It's the thread's turn 2 Yes , It is found that the current deposit is 100, And what I read before 100 identical , Perform the deduction operation again

This is the time , The deduction operation was performed twice ! ! ! All are ABA problem Ghost

int oldValue = value; // Read old values 
CAS(&value, oldValue, oldValue - 50)

     

      
1.
      
2.
     

When you press the withdrawal operation , The machine jammed , Funny press more — Next withdrawal ~

This is equivalent to , One withdrawal operation , It was executed twice ,( Two threads , Perform the withdrawal operation concurrently ), Our expected effect should be to succeed only once ！( Hope to take away 50, There is... Left in the account 50)

Suppose at the moment of withdrawal , His funny friend transferred him 50 This will trigger ABA problem

The card was transferred 50, These two coincidences lead to an existence BUG Of ABA problem ( Extreme scenario problems )

Even so bug The probability of occurrence is 0.01%, We also need to deal with !!!

How to solve ABA problem

Give the value to be modified , introduce Version number . stay CAS Compare the current value of the data with the old value , Also compare whether the version number meets the expectation

This version number It can only grow , It can't be smaller , When changing variables , Comparison is not the comparison variable itself , But compare the version number

You don't have to use it here “ Version number ", It can also be used. “ Time stamp "

• CAS Operation in While reading the old value , Also read the version number
• When it's really revised
• If at present The version number is the same as the read version number , Then modify the data , And put Version number + 1.
• If The current version number is higher than the read version number , The operation failed ( Think the data has been modified

in addition , You don't have to “ Version number ”, You can also use “ Time stamp ”, The date and time must go straight ahead .

So use There is no problem with timestamp .

expand ：

such be based on Version number The way To control multithreaded data , It is also a kind of A typical implementation of optimistic locking .

1、 In the database

In the database , When accessing tables through transactions concurrently , This will also involve some multithreaded operations similar to locking
 
2、 Version management tools （SVN）

It is the collaboration of multi person development through version number .

If someone else changes , You need to pull data first , And resubmit .

Relevant interview questions

① Explain what you understand CAS Mechanism

CAS Full name Compare and swap, namely “ Compare and exchange ”.

amount to Through the operation of an atom , Simultaneous completion “ Read memory , Comparison is equal , Modify memory ” These three steps .

Essentially, we need CPU Support of instructions .

② ABA How to solve the problem ？

Give the data to be modified Introduce version number .

stay CAS Compare the current value of the data with the old value , Also compare whether the version number meets the expectation .

If the current version number is found to be consistent with the version number read before , Just really perform the modification operation , And let the version number increase ;

If It is found that the current version number is larger than the version number read before , It is considered that the operation failed