Ali Er Mian: what is CAS?

background

In a highly concurrent business scenario , Thread safety must be considered , stay JDK5 Before , Can pass synchronized or Lock To ensure synchronization , In order to achieve the purpose of thread safety . but synchronized or Lock The scheme belongs to the scheme of mutual exclusion , More heavyweight , Lock 、 Releasing the lock will cause performance loss .

And in some cases , We can pass JUC Provided CAS Mechanism to achieve a lock free solution , Or it is based on a scheme similar to optimistic locking , To achieve non blocking synchronization to ensure thread safety .

CAS The mechanism is not only the interview questions that will appear frequently in the interview , It is also a knowledge point that must be mastered in high concurrency practice . If you are right now CAS I don't know much about , Maybe there is only a vague impression , This article must be worth your time to study .

What is? CAS？

CAS yes Compare And Swap Abbreviation , Literal translation is

Compare and exchange

.CAS It's modern CPU A widely supported special instruction that operates on shared data in memory , This instruction will perform atomic read and write operations on the shared data in memory . Its function is to make CPU Compare whether a value in memory is the same as expected , If it is the same, update the value to the new value , Do not update if they are different .

In essence CAS It is a lock free solution , It is also an operation based on optimistic locking , It can guarantee the atomic operation of shared resources in multithreading concurrency , be relative to synchronized or Lock Come on , Is a lightweight implementation .

Java Used a lot of CAS Mechanism to realize the atomization operation of data update under multithreading , such as AtomicInteger、CurrentHashMap It's all about CAS Application . but Java There is no direct implementation CAS,CAS The relevant implementation is through C/C++ call CPU Instructions to achieve , It's very efficient , but Java The code needs to go through JNI To call . such as ,Unsafe Class provides the CAS Method （ Such as compareAndSwapXXX） The underlying implementation is CPU Instructions cmpxchg.

CAS Basic flow

Now let's use a picture to understand CAS The basic process of operation .

CAS Operation flow chart

The above figure involves the comparison and operation of three values ： Modify the previously obtained （ To be modified ） value A, New value calculated by business logic B, And the memory location corresponding to the value to be modified C.

In the whole process , Suppose there is a variable in memory i, Its corresponding value in memory is A（ First read ）, After business processing , Update it to B, Then I will read it again before updating i Now the value is C, If in the process of business processing i The value of has not changed , That is to say A and C identical , That's what makes i to update （ In exchange for ） For the new value B. If A and C inequality , That means in business calculation ,i The value of has changed , Do not update （ In exchange for ） become B. Last ,CPU Will return the old value to . The above series of operations are performed by CPU Instructions to ensure that it is atomic .

stay 《Java Concurrent programming practice 》 Chinese vs CAS A more popular description ： I think what the original value should be , If it is , The original value is updated to the new value , Otherwise, no changes will be made , And tell me what the original value was .

In the above journey , We can clearly see the idea of optimistic lock , And no lock was used during this period . therefore , be relative to synchronized Wait for the realization of pessimistic lock , Much more efficient .

be based on CAS Of AtomicInteger Use

About CAS The implementation of the , The most classic and commonly used is AtomicInteger 了 , Let's take a look at it right away AtomicInteger How to use CAS Realize atomic operation . In order to form a sharp contrast , First, let's see if you don't use CAS Mechanism , How do we usually deal with thread safety .

Before use CAS Mechanism , To ensure thread safety , be based on synchronized The implementation is as follows ：

public class ThreadSafeTest {

 public static volatile int i = 0;

 public synchronized void increase() {
 i++;
 }
}


As for the specific implementation of the above example , I'm not going to expand this , Many related articles are dedicated to explaining , We just need to know that in order to ensure i++ Atomic operation of , stay increase Method uses a heavyweight lock synchronized, This will lead to low performance of this method , All operations that call this method need to be synchronized and wait for processing .

that , If based on CAS Realized AtomicInteger class , The implementation of the above method becomes simple and lightweight ：

public class ThreadSafeTest {

 private final AtomicInteger counter = new AtomicInteger(0);

 public int increase(){
 return counter.addAndGet(1);
 }

}


The reason why it can be so safe 、 Convenient for safe operation , Is due to AtomicInteger Class uses CAS Mechanism . below , Let's get to know AtomicInteger Function and source code implementation .

CAS Of AtomicInteger class

AtomicInteger yes java.util.concurrent.atomic  An atomic class under the package , There are also under the bag AtomicBoolean, AtomicLong,AtomicLongArray, AtomicReference Equiatomic class , It is mainly used in high concurrency environment , Ensure thread safety .

AtomicInteger Commonly used API

AtomicInteger Class provides the following common API function ：

public final int get()： Get the current value
public final int getAndSet(int newValue)： Get the current value , And set the new value
public final int getAndIncrement()： Get the current value , And self increase
public final int getAndDecrement()： Get the current value , And reduce
public final int getAndAdd(int delta)： Get the current value , And add the expected value
void lazySet(int newValue):  Will eventually be set to newValue, Use lazySet After setting the value , It may cause other threads to be able to read the old values for a short period of time .


In the above methods ,getAndXXX Format methods all implement atomic operations . For specific usage, please refer to the above addAndGet Case can be .

AtomicInteger Core source code

So let's see AtomicInteger Core implementation code in code ：

public class AtomicInteger extends Number implements java.io.Serializable {
 private static final Unsafe unsafe = Unsafe.getUnsafe();
 private static final long valueOffset;
 static {
 try {
 //  Used to get value Field relative to the current object “ Initial address ” The offset
 valueOffset = unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));
 } catch (Exception ex) { throw new Error(ex); }
 }

 private volatile int value;

 // Returns the current value
 public final int get() {
 return value;
 }

 // Incremental detla
 public final int getAndAdd(int delta) {
 // 1、this： The current example  
 // 2、valueOffset：value The offset of the instance variable  
 // 3、delta： At present value The number to add (value+delta).
 return unsafe.getAndAddInt(this, valueOffset, delta);
 }

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


The above code uses AtomicInteger#incrementAndGet Method as an example shows AtomicInteger Basic implementation of . among , stay static Static block of code , be based on Unsafe Class gets value Field relative to the current object “ Initial address ” The offset , Used in subsequent Unsafe Class .

When dealing with self increasing atomic operations , It uses Unsafe Class getAndAddInt Method ,CAS Is realized by Unsafe This method of class provides , So as to ensure the atomicity of autoincrement operation .

meanwhile , stay AtomicInteger Class , You can see value Value through volatile To embellish , Ensure the thread visibility of the attribute value . In the case of multiple concurrency , Modification of a thread , It can ensure that other threads can immediately see the modified value .

You can see from the source code , AtomicInteger  The bottom is through

volatile

Variables and CAS The combination of the two ensures the atomicity of the updated data . It's about Unsafe Class to CAS The implementation of the , We will introduce in detail below .

CAS How it works

CAS The implementation principle of is simply by

Unsafe class

And one of them

spinlocks

To complete , Now let's take a look at the contents of these two blocks for the source code .

UnSafe class

stay AtomicInteger In the core source code , Already seen CAS Through Unsafe Class to do it , Let's first get to know Unsafe The role of classes . About Unsafe Class in previous articles 《 All major frameworks are in use Unsafe class , How amazing it is ？》 There is also a detailed introduction , You can refer to , Here we will briefly summarize .

sun.misc.Unsafe yes JDK Tools for internal use . It exposes some Java In a sense “ unsafe ” The function of Java Layer code , To make the JDK Can use more Java Code to implement some originally platform related 、 Need to use native Language （ for example C or C++） The function that can be realized . This class should not be in JDK Use... Outside the core class library , This is also named Unsafe（ unsafe ） Why .

JVM You are free to choose how to implement Java Object's “ Layout ”, That is, in memory Java Where are the parts of the object , Including instance fields of objects and some metadata .

Unsafe The method of object field access in abstracts the object layout , It provides objectFieldOffset() Method is used to get the relative value of a field Java Object's “ Initial address ” The offset , Also provided getInt、getLong、getObject Such methods can use the offset obtained earlier to access a Java Object . stay AtomicInteger Of static In the code block objectFieldOffset() Method .

Unsafe The function of class is mainly divided into memory operation 、CAS、Class relevant 、 The object operation 、 Array correlation 、 Memory barrier 、 System related 、 Thread scheduling and other functions . Here we only need to know its function , Easy to understand CAS The implementation of the , Note that it is not recommended to use in daily development .

Unsafe And CAS

AtomicInteger Called Unsafe#getAndAddInt Method ：

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


The above code is equal to AtomicInteger call UnSafe Class CAS Method ,JVM Help us realize assembly instructions , So as to realize atomic operation .

stay Unsafe in getAndAddInt The method is as follows ：

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


getAndAddInt The method has three arguments ：

• The first parameter represents the current object , That is to say new the AtomicInteger object ;

• The second represents the memory address ;

• The third represents the self increasing pace , stay AtomicInteger#incrementAndGet The default self increasing step in is 1.

getAndAddInt In the method , First, assign the value in the main memory of the current object to val5, Then enter while loop . Judge whether the value in the main memory of the current object is equal to val5, If it is , It's self increasing （ Exchange value ）, Otherwise continue the cycle , Recapture val5 Value .

The core method in the above logic is compareAndSwapInt Method , It's a native Method , After this method is compiled CPU Primitive instruction , Primitive instructions are executed continuously without interruption , So we can guarantee atomicity .

stay getAndAddInt Method also involves an implementation

spinlocks

. The so-called spin , In fact, it's the above getAndAddInt Methods do while Cyclic operation . When the expected value is different from the value in main memory , Just retrieve the value in main memory , This is spin .

Here we can see CAS A disadvantage of implementation ： For internal use

The spin

By

CAS

to update （while Cycle are CAS to update , If the update fails , Then the loop retries again ）. If it doesn't work for a long time , Will cause CPU A great expense .

in addition ,Unsafe Class also supports other CAS Method , such as compareAndSwapObject、 compareAndSwapInt、compareAndSwapLong. More about Unsafe The function of class is no longer expanded , You can go to see 《 All major frameworks are in use Unsafe class , How amazing it is ？》 This article .

CAS The shortcomings of

CAS Atomic operation is realized efficiently , But there are still some shortcomings in the following three aspects ：

• Long cycle time , Spending big ;

• Only one atomic operation of shared variables can be guaranteed ;

• ABA problem ;

Let's discuss these three issues in detail .

The cycle time is long and the cost is high

Based on the analysis of Unsafe We have already mentioned the source code , stay Unsafe The spin lock mechanism is used in the implementation of . In this link, if CAS operation failed , It needs to be recycled CAS operation (do while The loop also updates the expectations to the latest ), If it doesn't work for a long time , That would cause CPU A great expense . If JVM It can support pause The efficiency of instruction will be improved .

Only one atomic operation of shared variables can be guaranteed

In the initial example , It can be seen that... Is used for a shared variable CAS Mechanism , Atomic operation can be guaranteed . But if there are multiple shared variables , Or the logic of an entire code block needs to ensure thread safety ,CAS Atomic operation cannot be guaranteed , At this point, it is necessary to consider locking （ Pessimistic locking ） Guaranteed atomicity , Or there's a clever way , Merge multiple shared variables into a shared variable for CAS operation .

ABA problem

Although the use of CAS It can realize non blocking atomic operation , But it will ABA problem ,ABA The basic process of problems ：

• process P1 The value read in the shared variable is A;

• P1 It's taken , process P2 perform ;

• P2 Take the value in the shared variable from A Changed to B, And back to A, At this time P1 preemption ;

• P1 Come back and see that the values in the shared variables have not been changed , So it went on ;

although P1 Think the value of the variable has not changed , Go ahead , But this raises some potential problems .ABA Problems are most likely to occur in lock free In the algorithm of ,CAS Be the first to bear the brunt , because CAS It's the address of the pointer . What if the address is reused , It's a big problem （ It is very common for addresses to be reused , A memory allocation frees up , redistribution , It's probably the same address ）.

Wikipedia gives a vivid example ： You're at the airport with a suitcase full of money , At this time came a hot and sexy beauty , And then she teases you very gently , And take advantage of your inattention , Put a bag as like as two peas in a suitcase and your money filled box , Then I left , You see your suitcase is still there , So I went to catch the plane with my suitcase .

ABA The solution to the problem is to use version number ： Append the version number to the variable , Add the version number to each variable update 1, that A->B->A Will become 1A->2B->3A.

in addition , from Java 1.5 Start ,JDK Of Atomic A class is provided in the bag AtomicStampedReference To solve ABA problem . This class of compareAndSet Method first checks whether the current reference is equal to the expected reference , And check whether the current flag is equal to the expected flag , If all are equal , Then atomically set the reference and the value of the flag to the given update value .

Summary

This paper starts from CAS The basic use scenarios of 、 The basic flow 、 Implementation class AtomicInteger The source code parsing 、CAS Of Unsafe For the 、CAS We have a comprehensive understanding of the shortcomings and solutions of CAS. Through the study of this article, you must have a deeper understanding CAS Mechanism , If it helps you , Remember to pay attention , Continuous output of dry goods .

Link to the original text ：https://mp.weixin.qq.com/s/oGCGcqfq3shq9KSd1eLCTw