concept

• The full name of CAS is Compare And Swap, which means compare and exchange. It is the atomic operation of CPU
• CAS is an abstract idea, not a concrete implementation
• CAS operation has three parameters: memory address of the value to be modified, expected value and new value
• The main idea is to judge whether the value of a location in memory is equal to the expected value. If it is equal to, the new value will be used to exchange the old value, and if not, the modification will fail
• CAS non blocking synchronization realizes thread safety
• CAS operations are atomic, so when multiple threads use CAS to update data concurrently, they can not use locks.

CAS problem

CAS mode is optimistic lock and synchronized is pessimistic lock. Therefore, using CAS to solve concurrency problems usually has better performance.
However, there are also several problems in using CAS:

ABA problem

CAS needs to check whether the value has changed when operating the value. For example, if it has not changed, it will be updated. However, if A value turns out to be A, becomes B, and then becomes A, it will be found that its value has not changed when using CAS for inspection, but actually has changed.
The solution to ABA problem is to use version number. Add the version number in front of the variable. When the variable is updated, add 1 to the version number, and a - > b - > A will become 1A - > 2B - > 3a.
Starting from Java 1.5, the JDK's Atomic package provides a class AtomicStampedReference to solve the ABA problem. The compareAndSet method of this class is used to first check whether the current reference is equal to the expected reference and whether the current flag is equal to the expected flag. If they are all equal, set the value of the reference and the flag to the given update value in an Atomic manner.

ABA problem solving

The ABA problem can be solved by adding a version number to the data
​

AtomicStampedReference solves ABA problems
AtomicStampedReference mainly maintains a pair object containing an object reference and an integer "stamp" that can be automatically updated to solve the ABA problem.

Long cycle time and high overhead

If spin CAS fails for a long time, it will bring very large execution overhead to the CPU.

Only atomic operations of one shared variable can be guaranteed

When operating on a shared variable, we can use cyclic CAS to ensure atomic operation. However, when operating on multiple shared variables, cyclic CAS cannot ensure the atomicity of the operation. At this time, locks can be used.
Another trick is to combine multiple shared variables into a shared variable for operation. For example, there are two shared variables i = 2, j = a, merge ij = 2a, and then use CAS to operate ij.
Since Java 1.5, JDK has provided AtomicReference class to ensure the atomicity between reference objects. You can put multiple variables in one object for CAS operation.
​

Implementation of CAS in Java

java provides us with AtomicXXX atomic class (which updates data based on CAS at the bottom), and realizes data consistency in multi-threaded concurrent scenarios without locking.
​

public class CASDemo{
    public static void main(string[] args){
        AtomicInteger atomicInteger = new AtomicInteger(5);// mian do thing. . . . ..
        System.out.println(atomicInteger.compareAndSet(5, 2019)+"\t current data: "+atomicInteger.get());
        System.out.println(atomicInteger.compareAndset(5, 1024)+"\t current data: "+atomicInteger.get());
    }
}

true    2019
false   2019

Atomic class underlying principle atomicInteger as an example

atomicInteger.getAndIncrement() source code (this method implements atomic i + + operation)

    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);  //Current object, memory address, offset, operand
    }

It can be seen that this method calls the method in the unsafe class

Unsafe class

Because Java methods cannot directly access the underlying system, they need to be accessed through Native methods. Unsafe is equivalent to a back door. Based on this class, you can directly operate specific memory data.
Unsafe function

Unsafe and CAS

Methods about CAS in Unsafe class

public final int getAndAddInt(Object paramObject, long paramLong, int paramInt)
  {
    int i;
    do
      i = getIntVolatile(paramObject, paramLong);
    while (!compareAndSwapInt(paramObject, paramLong, i, i + paramInt));
    return i;
  }

  public final long getAndAddLong(Object paramObject, long paramLong1, long paramLong2)
  {
    long l;
    do
      l = getLongVolatile(paramObject, paramLong1);
    while (!compareAndSwapLong(paramObject, paramLong1, l, l + paramLong2));
    return l;
  }

  public final int getAndSetInt(Object paramObject, long paramLong, int paramInt)
  {
    int i;
    do
      i = getIntVolatile(paramObject, paramLong);
    while (!compareAndSwapInt(paramObject, paramLong, i, paramInt));
    return i;
  }

  public final long getAndSetLong(Object paramObject, long paramLong1, long paramLong2)
  {
    long l;
    do
      l = getLongVolatile(paramObject, paramLong1);
    while (!compareAndSwapLong(paramObject, paramLong1, l, paramLong2));
    return l;
  }

  public final Object getAndSetObject(Object paramObject1, long paramLong, Object paramObject2)
  {
    Object localObject;
    do
      localObject = getObjectVolatile(paramObject1, paramLong);
    while (!compareAndSwapObject(paramObject1, paramLong, localObject, paramObject2));
    return localObject;
  }
  

It is found from the source code that the CAS update is performed internally by using the spin method (the while loop updates the CAS. If the update fails, the loop retries again).
​

It is also found from the Unsafe class that atomic operations only support the following three methods.

public final native boolean compareAndSwapObject(Object paramObject1, long paramLong, Object paramObject2, Object paramObject3);

public final native boolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);

public final native boolean compareAndSwapLong(Object paramObject, long paramLong1, long paramLong2, long paramLong3);
  

All atomic classes

​

Atomic update basic type

Update basic types in an Atomic way. The Atomic package provides the following three classes.

• AtomicBoolean: atomic update boolean type.
• AtomicInteger: atomic update integer.
• AtomicLong: atomic update long.

Atomic update array

Update an element in the array in an Atomic way. The Atomic package provides the following four classes:

• AtomicIntegerArray: atom updates elements in an integer array.
• AtomicLongArray: atom updates the elements in a long array.
• AtomicReferenceArray: atomic updates the elements in the reference type array. The most common methods of these three classes are the following two methods:
• get(int index): get the element value with index.
• compareAndSet(int i,E expect,E update): if the current value is equal to the expected value, set the element at array position I as the update value in an atomic manner

Atomic update reference type

The Atomic package provides the following three classes:

• AtomicReference: atomic update reference type.
• AtomicStampedReference: the atomic update reference type uses Pair internally to store the element value and its version number.
• Atomicmarkablereference: atomic updates reference types with marker bits.

Atomic update field class

The Atomic package provides four classes to update Atomic fields:

• AtomicIntegerFieldUpdater: updater for fields of atomic integer type.
• AtomicLongFieldUpdater: an updater that updates long fields atomically.
• AtomicStampedFieldUpdater: atomic updates reference types with version numbers.
• AtomicReferenceFieldUpdater: as mentioned above, it will not be repeated here.