1, Principle of Atomic atomic class:

         Atomic atomic operation class is implemented based on lockless CAS + volatile, and all methods in the class are decorated with final to further ensure thread safety. The specific implementation of CAS algorithm lies in the Unsafe class. All methods of Unsafe class are modified native ly, that is, all methods directly call the underlying resources of the operating system to perform corresponding tasks. Atomic uses an optimistic strategy. It assumes that no conflict occurs during each operation, and uses volatile with CAS to modify variables in memory. If it fails, it will try again until it succeeds.

• Optimistic lock: optimistic lock believes that competition does not always occur, so it does not need to lock every time the shared resources are operated. The two actions of "compare replace" are used as an atomic operation to modify variables in memory. In case of conflict, it will retry until it succeeds. Lock free strategy is an optimistic strategy. volatile + CAS is used to ensure the safety of thread execution.

• Pessimistic lock: pessimistic lock believes that there will always be conflicts when accessing shared resources. Therefore, each time you operate on shared resources, you will apply for an exclusive lock in advance. For example, synchronized and ReentronLock are exclusive locks.

2, What is CAS: Compare And Swap:

1. The core idea of CAS algorithm:

Executing function: CAS(V,E,U), which contains three parameters: memory value V, old expected value E, and value u to be modified.

• ① If and only if the expected value E is the same as the memory value V, the memory value will be modified to U and return true;

• ② If the V value and E value are different, it indicates that other threads have made updates, and the current thread does not perform the update operation, but you can choose to read the variable again and try to modify the variable again, or you can give up the operation.

CAS must cooperate with volatile variables to ensure that the variable obtained each time is the latest value in main memory. Otherwise, the old expected value E will always be a constant value E for a thread. As long as a CAS operation fails, it will never succeed. Since there is no lock in CAS lockless operation, it is impossible to have deadlock, that is, innate immunity to deadlock.

2. Support of CPU instruction for CAS:

         Since CAS has many steps, will there be a situation: suppose a thread switches the thread and changes the value when it is about to assign a value after judging that V and E are the same, resulting in inconsistent data? The answer is no, because CAS is a system primitive, which belongs to the language category of the operating system. It is composed of several instructions. It is used to complete a process of a function, and the execution of the primitive must be continuous. It is not allowed to be interrupted in the execution process, that is to say, CAS is an atomic instruction of the CPU and will not cause the so-called data inconsistency problem.

3. ABA problem of CAS and its solution:

Suppose such a scenario, when the first thread performs CAS(V,E,U) operation, before obtaining the current variable V and preparing to modify it to the new value u, the other two threads have continuously modified the value of variable V twice, so that the value returns to the old value. In this case, we cannot correctly judge whether the variable has been modified.

Solution: use the flag with version or timestamp to solve the ABA problem. When updating data, only the data to be updated and the version ID meet the expected value can be replaced.

 

3, Unsafe class:

         The execution of CAS operations in Atomic depends on the methods of unsafe class. All methods in unsafe class are modified native ly, that is, all methods directly call the underlying resources of the operating system to perform corresponding tasks. Unsafe class provides many functions. Here we mainly introduce unsafe CAS. Readers interested in other functions can read this article: https://blog.csdn.net/javazejian/article/details/72772470

The Unsafe class exists in the sun.misc package. Its internal method operations can directly operate memory like C pointers. From the name alone, we can know that this class is Unsafe. Because Unsafe has pointer operations similar to C, it should not be used first. Java officials do not recommend using Unsafe classes directly

The lock free operation CAS is some instructions directly supported by the CPU. In Java, the lock free operation CAS is implemented based on the following three methods. Later, we will explain that the internal methods of Atomic series are implemented based on the following methods.

//The first parameter o is the given object, and offset is the offset of the object memory. Through this offset, you can quickly locate the field and set or obtain the value of the field,
//Expected indicates the expected value, and x indicates the value to be set. The following three methods all perform operations through CAS atomic instructions.
public final native boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);                               

public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);

public final native boolean compareAndSwapLong(Object o, long offset,long expected,long x);

At the same time, several new methods in JDK8 in Unsafe class are implemented based on the above CAS methods, as follows:

 //1.8 add: for a given object o, add delta according to the field pointed to by the obtained memory offset,
 //This is a CAS operation process. You can exit the loop and return the old value until the setting is successful
 public final int getAndAddInt(Object o, long offset, int delta) {
     int v;
     do {
         //Get the latest value in memory
         v = getIntVolatile(o, offset);
       //Operation through CAS
     } while (!compareAndSwapInt(o, offset, v, v + delta));
     return v;
 }

//1.8 new. The function of the method is the same as above, except for the long type data operated here
 public final long getAndAddLong(Object o, long offset, long delta) {
     long v;
     do {
         v = getLongVolatile(o, offset);
     } while (!compareAndSwapLong(o, offset, v, v + delta));
     return v;
 }

 //1.8 add: given the object o, set the field to the new value newValue according to the obtained memory offset,
 //This is a CAS operation process. You can exit the loop and return the old value until the setting is successful
 public final int getAndSetInt(Object o, long offset, int newValue) {
     int v;
     do {
         v = getIntVolatile(o, offset);
     } while (!compareAndSwapInt(o, offset, v, newValue));
     return v;
 }

// 1.8 add, the same as above, and the operation is of long type
 public final long getAndSetLong(Object o, long offset, long newValue) {
     long v;
     do {
         v = getLongVolatile(o, offset);
     } while (!compareAndSwapLong(o, offset, v, newValue));
     return v;
 }

 //1.8 new, the same as above, operates on reference type data
 public final Object getAndSetObject(Object o, long offset, Object newValue) {
     Object v;
     do {
         v = getObjectVolatile(o, offset);
     } while (!compareAndSwapObject(o, offset, v, newValue));
     return v;
 }

4, Atomic operation class   Atomic:

The basic types of atomic update mainly include three classes:

• AtomicBoolean: atomic update boolean type

• AtomicInteger: atomic update integer

• AtomicLong: atomic update long

The implementation principles and usage methods of these three classes are almost the same. Here we take AtomicInteger as an example. AtomicInteger mainly performs atomic operations on int type data. It provides atomic self increasing method, atomic self decreasing method and atomic assignment method. Since AtomicInteger has few source codes, we can directly look at the source code:

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

    // Get pointer class Unsafe
    private static final Unsafe unsafe = Unsafe.getUnsafe();

    //The memory offset of the following variable value in the AtomicInteger instance object
    private static final long valueOffset;

    static {
        try {
           //Get the offset of the value variable in the object memory through the objectFieldOffset() method of the unsafe class
           //With this offset valueOffset, the internal method of the unsafe class can obtain the variable value and perform value or assignment operations on it
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
   //int variable value encapsulated by the current AtomicInteger
    private volatile int value;

    public AtomicInteger(int initialValue) {
        value = initialValue;
    }
    public AtomicInteger() {
    }
   //Get the current latest value,
    public final int get() {
        return value;
    }
    //Setting the current value has the volatile effect. The method is decorated with final to further ensure thread safety.
    public final void set(int newValue) {
        value = newValue;
    }
    //Finally, it will be set to newValue. After using this method, other threads may get the old value in a short period of time, which is similar to delayed loading
    public final void lazySet(int newValue) {
        unsafe.putOrderedInt(this, valueOffset, newValue);
    }
   //Set the new value and get the old value. The underlying call is the CAS operation, that is, the unsafe.compareAndSwapInt() method
    public final int getAndSet(int newValue) {
        return unsafe.getAndSetInt(this, valueOffset, newValue);
    }
   //If the current value is expect, it is set to update (the current value refers to the value variable)
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    //The current value plus 1 returns the old value, and the underlying CAS operation
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }
    //The current value minus 1 returns the old value and the underlying CAS operation
    public final int getAndDecrement() {
        return unsafe.getAndAddInt(this, valueOffset, -1);
    }
   //Increase the current value by delta, return the old value, and perform the underlying CAS operation
    public final int getAndAdd(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta);
    }
    //Add 1 to the current value, return a new value, and the underlying CAS operation
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }
    //The current value minus 1 returns a new value and the underlying CAS operation
    public final int decrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, -1) - 1;
    }
   //delta is added to the current value, a new value is returned, and the underlying CAS operation
    public final int addAndGet(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
    }
   //Omit some unusual methods
}

It can be found that the interior of AtomicInteger atomic class is almost implemented based on CAS related operations in Unsafe class, which also proves that AtomicInteger is implemented based on lock free. Here, the implementation process of auto increment operation is analyzed. The principle of auto increment implementation of other methods is the same.

//Add 1 to the current value, return a new value, and the underlying CAS operation
public final int incrementAndGet() {
     return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
 }

We found that all self increasing or self decreasing methods in AtomicInteger class indirectly call getAndAddInt() method in Unsafe class to realize CAS operation, so as to ensure thread safety. In fact, getAndAddInt() has been analyzed earlier. It is a new method in Unsafe class 1.8. The source code is as follows:

//getAndAddInt method in Unsafe class
public final int getAndAddInt(Object o, long offset, int delta) {
        int v;
        do {
            v = getIntVolatile(o, offset);
        } while (!compareAndSwapInt(o, offset, v, v + delta));
        return v;
    }

It can be seen that getAndAddInt() keeps trying to update the value to be set through a while loop until it succeeds. It calls the compareAndSwapInt() method in the Unsafe class, which is a CAS operation method. It should be noted that the above source code analysis is based on JDK1.8. If it is the method before 1.8, the implementation of AtomicInteger source code is different. It is based on the for loop, as follows:

//The source code of JDK 1.7 is implemented by the for loop, and the method is implemented directly in AtomicInteger. After JDK1.8, the method implementation has been moved to the Unsafe class, and the getAndAddInt method can be called directly
public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}