I. CAS Introduction

1. What is CAS?

CAS fully stands for Compare and Swap, which is to realize the synchronization function of multiple threads through atomic instructions. It compares the original value stored in memory address with the specified memory address. Only when they are equal, the specified expected value and the value in memory are swapped. Retrieves the original value stored at the memory address.

2. CAS process

CAS is a lock-free algorithm that has three key operands: memory address, expected value in old memory, new value to update, and when the memory value is equal to the expected value in old memory, the value in memory is updated to the new value.

3. Optimistic and pessimistic locks

CAS is an optimistic lock. An optimistic lock is an operation performed without locking, assuming no conflicts. If the operation fails due to conflicts, the CAS is retried until it succeeds. Synchronized is a pessimistic lock. After a thread acquires the lock, other threads must wait for the thread to release the lock, resulting in poor performance

AtomicInteger code demonstration

In Java, a++ is not an atomic operation. A simple a++ operation involves three operations: fetch the memory value of variable A, add variable A +1, and write the new value to memory. This involves two memory accesses. AtomicInteger is an atomic operation class that internally uses the CAS lock-free algorithm. Let’s examine its internal implementation here.

AtomicInteger atomicInteger = new AtomicInteger(0);
atomicInteger.getAndSet(1);  
Copy the code

The static code block AtomicInteger executes before the AtomicInteger object is initialized to get the offset of the AtomicInteger object value field relative to the “start address” of the AtomicInteger object. The layout of the Java object stored in memory can be divided into three regions: Header, Instance Data, and Padding. The offset of the starting address is the offset of the object Header.

static {
    try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); }}Copy the code
public final int getAndSet(int newValue) {
    return unsafe.getAndSetInt(this, valueOffset, newValue);
}
Copy the code

Each time through the memory address (var2), the original value in memory (var5) is first obtained from the memory, and then the loop compares the original value in memory (var5) with the given memory address (var2). If the value is equal, the specified expected value (var4) is updated. If the value is not equal, the retry until success. Finally, the old memory value var5 is returned.

//var1 is the AtomicInteger object, var2 is the memory address value, Public final int getAndSetInt(Object var1, Long var2, int var4) {int var5;do{//unsafe.getIntVolatile calls the local method to obtain the memory value var5 = this.getIntVolatile(var1, var2); }while(! this.compareAndSwapInt(var1, var2, var5, var4));return var5;
}
Copy the code

Three disadvantages,

1. The problem of ABA

CAS checks to see if the value of the variable has been changed, and updates the value if it hasn’t, but there is A problem. The value is initially A, then B, and then A again. It is true that the value has not been changed since the final value is still A, but it has been changed. To solve this problem, add A version number to each operation. Each operation has two values, one version number and some value, and the problem becomes 1A — >2B — >3A. The JDK provides an AtomicStampedReference class to address ABA problems. The Pair class contains two attributes, one representing the version number and the reference number. In compareAndSet, the reference is checked first and then the version number flag is checked.

2. Atomic operations of only one shared variable can be guaranteed

When multiple shared variables operate, the loop CAS cannot guarantee atomicity, and locks can be used. Since java1.5, the JDK has provided the AtomicReference class to ensure atomicity between reference objects, allowing multiple variables to be placed in a single object for CAS operations.

3. Long cycle time and high CPU overhead

In the case of high concurrency, if many threads repeatedly try to update a variable, but fail to update, the cycle will put a lot of stress on the CPU.

Author: Tao Zhang Good link: juejin.cn/post/684490… The copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.