CAS (Compare And Swap) means Compare And Swap, CAS is an atomic operation. The CAS operation involves three values: V in current memory, E in overdue memory, and U to be updated. If V in the current memory is equal to the expected value E, the CAS operation succeeds by updating the value in the memory to U. Otherwise, the CAS fails to be updated. CAS is widely used in JUC. CAS is the basis of JUC. There is no JUC without CAS operation. CAS is often used to implement optimistic locks in Java. Compared with synchronized locks, which are pessimistic locks in Java, optimistic locks do not need to suspend and wake up threads. Under high concurrency, frequent suspension and wake up of threads will affect performance. In order to understand CAS operations, it is necessary to understand optimistic and pessimistic locks and the differences between them.

Pessimistic locks and optimistic locks

Pessimistic locking think other threads of each operation will be updating Shared variables, so all the operations must be mutually exclusive, through a pessimistic locking strategy for all operating serialization, all threads before operation Shared variables must get pessimistic locks, success is, get failure block the current thread pessimistic waiting for you. When the thread is blocked, the CPU will no longer schedule the thread. In the scenario of high concurrency, if the threads compete fiercely for a lock, it will cause the thread to hang and wake up frequently, which will undoubtedly bring a disastrous blow to our application. The flow chart for pessimistic locking is as follows:

Synchronized locks and Reentrantlocks in Java are pessimistic locks. In the previous article, we analyzed the differences between various locks in Java, and you can check them out if you are interested: multithreaded security and Locks in Java.

Optimistic locks, as opposed to pessimistic locks, assume that other threads may not modify the shared variable, so the thread does not have to block and wait. Update the shared variable through CAS. If the CAS update fails, other threads have modified the shared variable and retry until the update succeeds. Because CAS operations do not suspend threads, they reduce the overhead of thread suspension and awakening, which can be significant in high concurrency situations. Circular retries do not suspend threads but consume CPU because threads need to keep retrying in a loop, which is also a disadvantage of optimistic CAS locks. Java. Util. Concurrent. Atomic package the following atomic classes by CAS optimistic locking to ensure thread safety. Another disadvantage of CAS optimistic locking is that it does not solve the “ABA” problem. This will be analyzed in more detail later. The flow chart of optimistic lock based on CAS is as follows:

CAS operation and application in Java

CAS has many applications in Java, JUC and Java. Util. Concurrent. Under the atomic atomic classes are used to CAS.

Unsafe provides CAS operations

Unsafe provides much of the low-level functionality for Java, including CAS functionality in Java, through this class. For those interested, check out my previous article on the Unsafe class, Unsafe in Java.

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
Copy the code

Unsafe provides CAS operations of the Object, int, and Long types. Other types need to be implemented themselves. CAS is an atomic operation. In addition to atomicity, visibility and order are essential for thread safety. Both visibility and order can be implemented in Java with volatile.

Atomic classes in Java (java.util.concurrent.atomic)

Java. Util. Concurrent. Atomic package the classes by volatile + CAS retry ensure thread safety. Java. Util. Concurrent. Atomic package the following atomic classes can be divided into four types:

  1. Atomic scalars: AtomicBoolean, AtomicInteger, AtomicLong, AtomicReference
  2. Array classes: AtomicIntegerArray, AtomicLongArray, AtomicReferenceArray
  3. Update the class: AtomicLongFieldUpdater AtomicIntegerFieldUpdater, AtomicReferenceFieldUpdater
  4. Compound variable classes: AtomicMarkableReference, AtomicStampedReference

Atomic scalar class

Let’s focus on the AtomicInteger class to ensure thread-safety:

The value of AtomicInteger is volatile

public class AtomicInteger extends Number implements java.io.Seriablizable { ... private volatile int value; // Value is volatile, ensuring visibility and order... }Copy the code

The values in AtomicInteger are volatile, which guarantees visibility and order.

Get operation

public final int get() {
    return value;
}
Copy the code

As you can see, AtomicInteger’s GET operation is unlocked. For non-volatile shared variables, a reader thread may not immediately be able to read other threads’ changes to the shared variable. But the value is volatile, so you can immediately see changes made to the value by other threads.

IncrementAndGet operation

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

The incrementAndGet operation increments value by 1 and then returns the new value. The broadening method calls the getAndAddInt method internally:

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)); // CAS atomic update + loop retryreturn var5;
}
Copy the code

The Unsafe loop reads the value from memory, then the CAS is updated. If the CAS update is successful, the CAS is exited, and if the update fails, the loop is retried until the update is successful.

In the previous article (Unsafe in Java), we examined CAS operations in Unsafe that provide objects of three types: Object, int, and long. The AtomicLong is implemented using the CAS operation of type long, which Unsafe provides. The AtomicReference is implemented using the CAS operation of type Object, which Unsafe provides. The value in AtomicBoolean is also an int. AtomicBoolean does a conversion to int:

public AtomicBoolean(boolean initialValue) { value = initialValue ? 1:0; }Copy the code

1 means true and 0 means false. Therefore AtomicBoolean is also implemented through CAS operations of type int provided by Unsafe.

An array of class

Unsafe provides two main array-related capabilities:

public native int arrayBaseOffset(Class<? > var1); public native int arrayIndexScale(Class<? > var1);Copy the code

AtomicIntegerArray primarily uses these two methods to implement array CAS operations. Some of the main features in AtomicIntegerArray are as follows:

private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final int base = unsafe.arrayBaseOffset(int[].class); Private static final int scale = unsafe.arrayIndexScale(int[].class); Private final int[] array; public final int get(int i) {return unsafe.getIntVolatile(array, rawIndex(i));  
}  
public final void set(int i, int newValue) {  
    unsafe.putIntVolatile(array, rawIndex(i), newValue);  
}
Copy the code

AtomicLongArray and AtomicReferenceArray are implemented similarly to AtomicIntegerArray.

Update the class

The AtomicLongFieldUpdater is used to update an object’s volatile long property, which is an instance property, not a class property, meaning that it can only be used to update an instance of an object’s non-static property. Similar to AtomicLongFieldUpdater AtomicIntegerFieldUpdater used to update a volatile object of type int properties.

AtomicLongFieldUpdater and AtomicIntegerFieldUpdater are used to update a native object attributes (int long), and the AtomicReferenceFieldUpdater is used to update a package type attributes of objects.

Compound variable class

CAS based optimistic lock can not solve the “ABA” problem. The main idea to solve the ABA problem is to stamp a value. An AtomicStampedReference is to add a stamp to the value to solve the ABA problem.

public class AtomicStampedReference<V> { private static class Pair<T> { final T reference; // final int stamp; Private Pair(T reference, int stamp) {this.reference = reference; this.stamp = stamp; } static <T> Pair<T> of(T reference, int stamp) {returnnew Pair<T>(reference, stamp); } } private volatile Pair<V> pair; // Volatile ensures visibility and order... public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { Pair<V> current = pair;returnexpectedReference == current.reference && expectedStamp == current.stamp && ((newReference == current.reference && newStamp == current.stamp) || casPair(current, Pair.of(newReference, newStamp))); }... private boolean casPair(Pair<V> cmp, Pair<V> val) {returnUNSAFE.compareAndSwapObject(this, pairOffset, cmp, val); // Update via Unsafe compareAndSwapObject}... }Copy the code

conclusion

  1. java.util.concurrent.atomicThread safety is ensured through optimistic cas-based locks. Pessimistic locks perform better than synchronized and Reentrantlocks in overread and underwrite scenarios.
  2. Unsafe has a large number of CAS operations running in JUC, and its CAS is the foundation of JUC.
  3. CAS – based optimistic lock cannot solve THE ABA problem, but AtomicStampedReference adds stamps to solve the ABA problem.
  4. Optimistic locks based on CAS+ loops can consume a lot of CPU.