What is CAS and ABA in CAS

In multithreading concurrency , To ensure the atomicity of threads .

The atomicity of atomic class is through volatile + CAS To achieve atomic operation .

Concept

CAS（Compare And Swap） To compare and exchange .CAS Algorithm CAS(V,E,N) contains 3 Parameters ,V Represents the variable to update ,E Indicates the expected value ,N Represents the new value .

In and only in V The value is equal to E When the value of , Will be V Value to N, If V Values and E Values are different , Indicates that other threads have updated , The current thread does nothing . Last ,CAS Returns the current V True value of .

This method is more efficient than locking , When V and E When the judgment is different , So the value is not updated , No blocking is sent , Continue to get CPU The enforcement of , Continue to judge and execute .

CAS Characteristics of ： Optimism lock

CAS The idea of optimistic locking is adopted in the operation of , Always think that you can successfully complete the operation . When there are multiple threads that can be used at the same time CAS When you manipulate a variable , Only one will win and successfully update , The rest will fail .
The failed thread will not be suspended , Just being allowed to try again , Of course , It also allows the failed thread to abandon the operation . Based on this principle ,CAS Operation even without lock , You can also find the interference of other threads to the current thread , And deal with it properly .

CAS Spin waiting for

stay JDK The atomic package of java.util.concurrent.atomic A set of atomic classes is provided in , The basic feature of these atomic classes is in a multithreaded environment , When multiple threads execute the methods contained in the instances of these classes at the same time , There will be exclusivity . Its interior is based on CAS Algorithm to achieve , That is, when a thread enters the method and executes its instructions , Will not be interrupted by other thread locks ; And other threads are like spinlocks ,（ Is to try again and again in the endless rotation ） Wait until the execution of the method is completed JVM Select a thread from the waiting queue .

be relative to synchronized Blocking algorithm , CAS Is a common implementation of non blocking algorithm . because CPU Context switching ratio CPU The operation of instruction set is more time-consuming , therefore CAS The performance of spin operation has been greatly improved .

CAS The shortcomings of

CAS Using a spin lock , Because the lock will be judged repeatedly , So there is no type synchronize Thread blocking causes thread switching .
But in the process of constant spin , It can lead to CPU Consumption of , Especially in the case of large concurrency, it is easy to cause CPU Run full .

---

In the use of CAS There is an important premise for the implementation of the algorithm ： It is necessary to fetch the data in the memory at a certain time , Then the comparison was made immediately at one moment 、 Replace , Within this time difference, the data may have changed , It came into being. ABA problem .

ABA problem

ABA The problem is that the first thread from memory V Take out the position A , At this time, the second thread is also fetched from memory A And will V The data of the position is modified to B , And then V The data of the location is modified to A , This is the first time 1 Threads and then CAS In operation , What will happen in memory is still A , Then the first thread can operate successfully .

Although from the perspective of thread one ,CAS The operation of is successful , But in the process V The location data has changed , Just in the first thread , I didn't feel it , In some application scenarios, process data inconsistency may occur .

So to solve this ABA The problem of , In some optimistic locks , Yes by version number （version） To solve ABA The problem of .

Specific operation ： The optimistic lock will carry a version number every time it performs data modification , When the expected version number is consistent with the data version number, you can perform the modification operation , And add... To the version number 1 The operation of , Otherwise, the execution fails . Therefore, the version number will increase with each operation , So there won't be ABA problem . Because the version number will only increase or not decrease .

Code demonstration ：

Here in thread 2 , It should not be changed , This is where the ABA The problem of , So here we are going to solve this ABA The problem of .