Basic Concepts of CAS
CAS stands for Compare And Swap, which means Compare And Swap. It usually refers to a lock-free atomic algorithm that updates the value of a variable by first comparing its memory value to some expected value and, if so, assigning it a new value. The CAS operation directly reads and writes memory in user mode without switching between user mode and kernel mode. Therefore, the CAS operation does not block threads. CAS can be thought of as an optimistic lock, and incremental operations of Java atomic classes are implemented through CAS spin.
The following pseudocode describes a composite operation consisting of the comparison and assignment phases. CAS can be viewed as their combined whole, an indivisible atomic operation:
if(value == expectedValue){
value = newValue;
}
Copy the codeCAS implementation in Java
In Java, CAS operations are supported by the Unsafe class, which defines three CAS operations for different types of variables, as follows:
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 codeThese three methods are native methods whose specific implementation is provided by the Java VIRTUAL machine. Different Java virtual machines may implement them slightly differently. They accept four parameters: the object instance, the memory offset of the field being modified, the expected value of the field, and the new value of the field. These three methods perform CAS operations on fields in the specified object instance at the corresponding offset, as shown in the following code:
public class CASDemo {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
Entity entity = new Entity();
Field field = Unsafe.class.getDeclaredField("theUnsafe");// get the theUnsafe attribute in theUnsafe class via reflection, i.e., theUnsafe instance
field.setAccessible(true);
Unsafe unsafe = (Unsafe) field.get(null);
// Get the memory offset of the field
long offset = unsafe.objectFieldOffset(Entity.class.getDeclaredField("x"));
// 4 parameters are: object instance, memory offset of the field to be modified, expected value of the field, new value of the field;
// If the expected value of the field is equal to the memory value of the current field, it can be modified successfully and returns true
boolean successful = unsafe.compareAndSwapInt(entity, offset, 0.3);
System.out.println(successful + "\t" + entity.x);
successful = unsafe.compareAndSwapInt(entity, offset, 3.5);
System.out.println(successful + "\t" + entity.x);
successful = unsafe.compareAndSwapInt(entity, offset, 3.8);
System.out.println(successful + "\t"+ entity.x); }}class Entity{
int x;
}
Copy the codeCAS defects
Although CAS solves atomic operation efficiently, it still has some defects, mainly in three aspects:
- In Java, many concurrency frameworks use spin CAS to acquire locks, i.e. they loop until the lock is acquired and then perform the operation. CAS is always using up CPU resources while spinning. If CAS spins unsuccessfully for long periods of time, this can be very expensive for the CPU.
- Only one shared variable atomic operation can be guaranteed – for one shared variable, we can loop CAS to ensure atomic operation, but for multiple shared variables, the spin CAS cannot guarantee atomicity, which requires locking.
- ABA problem
ABA problem
An important prerequisite for the implementation of CAS algorithm is to extract the data in memory at one moment and compare and replace it at the next moment. Therefore, the data may change within this time difference.
What are ABA problems
The so-called ABA problem is that when multiple threads work on an atomic class, one thread changes the value of the atomic class from A to B in A short period of time, and then changes it immediately to A, the other threads still read the value of A, and do not perceive the process of A->B->A, and still modify it successfully.
How to solve THE ABA problem
The solution to the ABA problem is to use version numbers. Append the version number to the variable, increment the version number by 1 each time the variable is updated, and A->B->A becomes 1A->2B->3A. Java provides an atom class, AtomicStampedReference, 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) {
return newPair<T>(reference, stamp); }}private volatile Pair<V> pair;
/**
* Creates a new {@code AtomicStampedReference} with the given
* initial values.
*
* @param initialRef the initial reference
* @param initialStamp the initial stamp
*/
public AtomicStampedReference(V initialRef, int initialStamp) {
pair = Pair.of(initialRef, initialStamp);
}
// Other code omitted.....
}
Copy the codeThe constructor for AtomicStampedReference passes in two parameters, V initialRef, which is the initial variable we actually stored, and int initialStamp, which is the initial version number. Pair.reference is the actual stored variable, pair. stamp is the version number, and stamp+1 is used to ensure the uniqueness of the version for each modification. This ensures that each revision will be incremented upward.
The following code example shows that Thread1 cannot be modified successfully because the version numbers are inconsistent.
public class AtomicStampedReferenceDemo {
public static void main(String[] args) {
// Initialize AtomicStampedReferenct with an initial value of 1 and an initial version number of 1
AtomicStampedReference atomicStampedReference = new AtomicStampedReference(1.1);
new Thread(() -> {
int[] stampHolder = new int[1];
int value = (int) atomicStampedReference.get(stampHolder);
int stamp = stampHolder[0];
System.out.println("Thread1 read value:" + value + ", stamp:" + stamp);
// block for 1 second
LockSupport.parkNanos(1000000000L);
// Change the value to 3 through CAS
if (atomicStampedReference.compareAndSet(value, 3, stamp, stamp+1)){
System.out.println("Thread1 update value from " + value + " to 3");
}else {
System.out.println("Thread1 update fail."); }},"Thread1").start();
new Thread(() -> {
int[] stampHolder = new int[1];
int value = (int) atomicStampedReference.get(stampHolder);
int stamp = stampHolder[0];
System.out.println("Thread2 read value:" + value + ", stamp:" + stamp);
// Change value to 2 through CAS
if (atomicStampedReference.compareAndSet(value, 2, stamp, stamp+1)){
System.out.println("Thread2 update value from " + value + " to 2");
value = (int) atomicStampedReference.get(stampHolder);
stamp = stampHolder[0];
System.out.println("Thread2 read value:" + value + ", stamp:" + stamp);
// Change the value to 1 through the CAS
if (atomicStampedReference.compareAndSet(value, 1, stamp, stamp +1)){
System.out.println("Thread2 update value from " + value + " to 1"); }}else {
System.out.println("Thread2 update fail."); }},"Thread2").start(); }}Copy the codeJava also provides another class, AtomicMarkableReference, which can be interpreted as a simplified version of AtomicStampedReference, because it doesn’t care how many times it’s been modified, only whether it’s been modified. Use the Boolean variable mark to record whether the value has been changed.
public class AtomicMarkableReference<V> {
private static class Pair<T> {
final T reference;
final boolean mark;
private Pair(T reference, boolean mark) {
this.reference = reference;
this.mark = mark;
}
static <T> Pair<T> of(T reference, boolean mark) {
return newPair<T>(reference, mark); }}private volatile Pair<V> pair;
/**
* Creates a new {@code AtomicMarkableReference} with the given
* initial values.
*
* @param initialRef the initial reference
* @param initialMark the initial mark
*/
public AtomicMarkableReference(V initialRef, boolean initialMark) { pair = Pair.of(initialRef, initialMark); }... }Copy the code