CAS principle [concurrent programming]

1.CAS

CAS It's considered an optimistic lock , There are optimistic locks , The opposite is pessimistic lock .

In the example above , We used synchronized, If there is a high pressure of thread competition ,synchronized The interior will be upgraded to a heavyweight lock , At this time, only one thread can enter the code block to execute , If this lock never releases , Other threads will keep blocking and waiting . here , It can be thought of as a pessimistic lock .

Pessimistic lock will cause system context switching due to thread blocking , The performance of the system is expensive .

that , We can use optimistic lock to solve , The so-called optimistic lock , In fact, it's a kind of thought .

Optimism lock , Will treat things with a more optimistic attitude , Think you can operate successfully . When multiple threads operate on the same shared resource , Only one thread can get lock success at the same time , In the optimistic lock , Other threads find themselves unable to successfully acquire locks , It doesn't block threads like pessimistic locks , I'm going straight back , You can choose to try again to get the lock , You can also exit directly .

CAS It is the core algorithm of optimistic lock .
java.util.concurrent.atomic And all the atomic classes under the contract are based on CAS To achieve .

AtomicInteger Part of the code

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;

/**
     * Atomically increments by one the current value.
     *
     * @return the previous value
     */
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }


/**
     * Atomically sets the value to the given updated value
     * if the current value {@code ==} the expected value.
     *
     * @param expect the expected value
     * @param update the new value
     * @return {@code true} if successful. False return indicates that
     * the actual value was not equal to the expected value.
     */
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

We see that AtomicInteger Internal methods are based on Unsafe Class implements the ,Unsafe Class is the same as the underlying hardware CPU Command communication replication tool class .

From this code, we can see ：unsafe.compareAndSwapInt(this, valueOffset, expect, update)

So-called CAS, In fact, it's an abbreviation , The full name is Compare And Swap, Exchange data after comparison . The above method , There are several important parameters ：

（1）this,Unsafe Object itself , You need this class to get value The memory offset address of .

（2）valueOffset,value Memory offset address of variable .

（3）expect, Expected updated value .

（4）update, Latest value to update .

If... In the atomic variable value The value is equal to expect, Then use update Value updates the value and returns true, Otherwise return to false.

Let's see how to get valueOffset Of ：

// Unsafe example 
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;

static {
        try {
              //  get value stay AtomicInteger Offset in 
                valueOffset = unsafe.objectFieldOffset
                        (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
}
//  The value of the actual variable 
private volatile int value;

I see it here value The actual variable , By volatile Keyword modifier , To ensure memory visibility under multithreading .

Why can we get through Unsafe.getUnsafe() Methods can get Unsafe Class ？ In fact, because AtomicInteger Class is also in rt.jar Under the bag , therefore AtomicInteger Class is through Bootstrap Loaded by the root class loader .

The source code is shown below ：

@CallerSensitive
public static Unsafe getUnsafe() {
        Class var0 = Reflection.getCallerClass();
        // Bootstrap  The class loader is C++ Of , Normal return null, Otherwise, it will throw the exception .
        if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
                throw new SecurityException("Unsafe");
        } else {
                return theUnsafe;
        }
}

Class loader delegation ：

2. CPU How to implement atomic operation

CPU The processor speed is much faster than in main memory , To solve the speed difference , There's a multi-level cache between them , Such as L1、L2、L3 Level cache , These caches are away from CPU The closer you get, the faster , Cache frequently operated data here , Speed up access , As shown in the figure below ：

Now it's all multi-core CPU processor , Every CPU A block of memory is maintained in the processor , Each kernel maintains a byte cache inside , When multiple threads read and write concurrently , There will be cache data inconsistency .

here , The processor provides ：

Bus lock
When a processor wants to operate on shared variables , stay BUS Send a... On the bus Lock The signal , Other processes cannot operate this shared variable .

The disadvantages are obvious , The bus is locked when blocking the operation request of other processors to obtain the shared variable , It can also cause a lot of congestion , This increases the performance overhead of the system .

Cache lock
Later processors provided cache locking mechanism , In other words, when a processor operates on shared variables in the cache , Other processors have a sniffer mechanism , Invalidate the cache of this shared variable of other processors , When other threads read, they will read the latest data from main memory again , be based on MESI Cache consistency protocol to achieve .

Modern processors basically support and use the cache locking mechanism .

Be careful ：

There are two situations in which the processor will not use cache locking ：

（1） When the data of the operation spans multiple cache lines , Or not cached inside the processor , Then the processor will use the bus lock .

（2） Some processors do not support cache locking , such as ：Intel 486 and Pentium The processor will also call bus lock .

Decrypt CAS The underlying instructions
Actually , Master the above , about CAS The understanding of mechanism is relatively clear .

Of course , If you are interested , You can also continue to learn in-depth what hardware is used CPU Instructions .

The underlying hardware passes through CAS Multiple operations in the hardware level semantic implementation , Atomic operation is guaranteed by a processor instruction . These instructions are as follows ：

（1） Test and set up （Tetst-and-Set）

（2） Get and add （Fetch-and-Increment）

（3） In exchange for （Swap）

（4） Compare and exchange （Compare-and-Swap）

（5） Load link / Conditional storage （Load-Linked/Store-Conditional）

Most of the first three processors have been implemented , The latter two are new to modern processors . And depending on the architecture , There are significant differences in instructions .

stay IA64,x86 What is in the instruction set cmpxchg Command complete CAS function , stay sparc-TSO Also have casa Instructions implement , And in the ARM and PowerPC Under the architecture , You need to use a pair of ldrex/strex Order to complete LL/SC The function of . In a reduced instruction set architecture , It's usually a pair of instructions , Such as ：load and reserve and store conditional Realized , On most processors CAS It's a very lightweight operation , That's the advantage of it .

3. summary

Any technology needs to find the right scene , Not everything ,CAS The same mechanism , There are also side effects .

3.1 problem 1：

As an implementation of optimistic lock , When multiple threads are competing for resources , And the processing time of locked resources , Then other threads should consider the number of spins , Avoid excessive consumption CPU.

in addition , Consider the... Mentioned in the sample code above LongAdder To solve ,LongAdder In the way of space for time , To solve CAS Take up a lot of time after a lot of failures CPU resources , Increased system performance overhead .

3.2 problem 2：

A–>B—>A problem , Suppose there is a variable A , It is amended as follows B, Then it's revised to A, It has been revised , but CAS It may not be perceptible , Caused unreasonable value modification operation .

The integer type is OK , If it's an object reference type , Contains multiple variables , What to do with that ？ Add a version number or timestamp , That's all right. ！

JDK in java.util.concurrent.atomic And under the contract , Provides AtomicStampedReference, By creating a... For the reference Stamp Similar to version number , Make sure CAS The correctness of the operation .

I hope you can collect and digest this article ,CAS stay JDK The underlying implementation of concurrent package is a very important algorithm .