I. CAS Introduction
CAS is Compare And Swap, which is different from pessimistic lock. With the help of CAS, it can realize an optimistic lock that is different from synchronized exclusive lock, which is widely used in major programming languages. Java JUC underlayer makes heavy use of CAS, so java.util.Concurrent is built entirely on CAS. However, CAS also has its drawbacks, such as ABA and high CPU utilization.
CAS has three operands, the current memory value V, the old expected value A, and the new value N to be modified. Change V to N if and only if A and V are the same, otherwise do nothing.
2. CAS source code analysis
As we all know, Java provides a series of concurrency safe atomic operation classes, such as AtomicInteger and AtomicLong. Here we take AtomicInteger as an example to analyze its source code implementation.
Private static final UnSafe = UnSafe. GetUnsafe (); // 2, memory offset private static final long valueOffset; Static {try {/ / 3, initialize the address offset valueOffset = unsafe. ObjectFieldOffset (AtomicInteger. Class. GetDeclaredField ("value")); } catch (Exception ex) { throw new Error(ex); }} private volatile int value;Copy the codeAddressing Unsafe, AtomicInteger relies on an instance object called Unsafe. As we all know, the Java language blocks direct memory operations like C++. Programmers don’t have to manage memory manually. Java also opens up a class called Unsafe to directly manipulate memory. As its name implies, using Unsafe operations should be considered Unsafe.
ValueOffset is the memory offset address of an object. To initialize an object using an Unsafe object, a given field must have the same offset. Two fields in the same class never have the same offset. That is, the offset will never change as long as the object is immortal, and you can imagine that the first parameter that CAS depends on (the memory address value) is retrieved from this address offset.
Value is a shared resource. Volatile is used to ensure memory visibility. For a simple analysis of volatile, see
Java disassembly, decompilation, Volitale interpretation
Public final int getAndAdd(int delta) {public final int getAndAdd(int delta) {returnunsafe.getAndAddInt(this, valueOffset, delta); } // public final intincrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
Copy the codeThe above two methods rely on getAndAddInt in the Unsafe class below. Looking at the Unsafe source code provided by the OpenJDK, let’s look at its implementation:
public final int getAndAddInt(Object o, long offset, int delta) { int v; // 1. Repeat the loop until the CAS operation returns successfullydo {
v = getIntVolatile(o, offset);
} while(! compareAndSwapInt(o, offset, v, v + delta));return v;
}
Copy the codeAs you can see from the above, the CAS essentially spins with a spin lock until the CAS operation succeeds, and if it does not succeed for a long time, then it will keep spinning.
Disadvantages of CAS
As you can see from the first and second sections, CAS is essentially implemented in Java using the methods provided by the Unsafe class to get the memory address offset of an object, and then through spin. The advantage of CAS is obvious, that is, different from pessimistic strategy, optimistic strategy has better performance under high concurrency. Of course, CAS also has disadvantages, including three major problems like ABA, too long spin time, and only one shared variable atom operation, which will be analyzed in the following.
1, the ABA
What is ABA? To put it simply, there are two threads, thread A and thread B. For the same variable X=0, THREAD A intends to set X to 10. According to the steps of CAS, it first reads the old expected value 0 from memory, then compares it, and finally sets it to 10. At this point, thread B completes the three operations X=0 -> X=10 -> X=0. Then THREAD A continues to perform the comparison and finds that the memory value is still 0. Finally, CAS is successfully executed. Although there is no problem with the process and result, the 0 in the comparison of A is not the original 0, and it feels like being replaced.
The following code illustrates the ABA problem. Thread 1 simulates changing variables from 100->110->100, thread 2 executes 100->120, and finally look at the output:
import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicStampedReference; /** ** @author jiawei Huang * @since 2020 1月17日 * @version 1.0 */ public class ABATest {// Initial value is 100 private static AtomicInteger atomicInteger = new AtomicInteger(100); Public static void main(String[] args) throws InterruptedException {// AtomicInteger Implements 100->110->100 Thread T1 = new Thread(newRunnable() {
@Override
public void run() { atomicInteger.compareAndSet(100, 110); atomicInteger.compareAndSet(110, 100); }}); Thread t2 = new Thread(new)Runnable() {
@Override
public void runTimeunit.seconds.sleep (2); timeunit.seconds.sleep (2); timeunit.seconds. } catch (InterruptedException e) { e.printStackTrace(); } // return againtrue
System.out.println("AtomicInteger:"+ atomicInteger.compareAndSet(100, 120)); }}); t1.start(); t2.start(); }}Copy the codeThe output is:
AtomicInteger:true
Copy the codeVisible thread 2 also executed CAS successfully, so how to solve this problem? The solution is to use a version number, and Java provides an AtomicStampedReference. AtomicStampedReference avoids THE ABA problem by packing a tuple of [E,Integer] to stamp the version of the object marker.
/*
* Copyright (C) 2011-2019 DL
*
* All right reserved.
*
* This software is the confidential and proprietary information of DL of China.
* ("Confidential Information"). You shall not disclose such Confidential
* Information and shall use it only inaccordance with the argeements * reached into with DL himself. * */ package com.algorithm.leetcode.linkedlist; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicStampedReference; /** ** @author jiawei Huang * @since 2020年1月17日 * @version 1.0 */ public class ABATest {// Version 1 Private static AtomicStampedReference<Integer> AtomicStampedReference = New AtomicStampedReference<Integer>(100, 1); Public static void main(String[] args) throws InterruptedException {// AtomicStampedReference Implements Thread tsF1 = new Thread(newRunnable() {
@Override
public void runTimeunit.seconds.sleep (2); timeunit.seconds.sleep (2); timeunit.seconds.sleep (2); } catch (InterruptedException e) { e.printStackTrace(); } // Expected reference: 100, updated reference: In 110, Expected to identify getStamp () the updated logo getStamp (+ 1) atomicStampedReference.com pareAndSet (100, 110, atomicStampedReference. GetStamp (), atomicStampedReference.getStamp() + 1); atomicStampedReference.compareAndSet(110, 100, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1); }}); Thread tsf2 = new Thread(newRunnable() {
@Override
public void run() { int stamp = atomicStampedReference.getStamp(); try { TimeUnit.SECONDS.sleep(2); Catch (InterruptedException e) {e.printStackTrace(); } System.out.println("AtomicStampedReference:"+ atomicStampedReference.compareAndSet(100, 120, stamp, stamp + 1)); }}); tsf1.start(); tsf2.start(); }}Copy the codeOutput result:
AtomicStampedReference:false
Copy the codeYou can see that thread 1 failed.
2. Spin time is too long
As can be seen from the analysis in section 2, CAS is essentially determined by the spin. The problem is that if the old expected value is not equal to the memory value for many times, the spin will continue to spin, and too much spin will lead to high CPU utilization.
3. Only one shared variable atomic operation is guaranteed
It can be seen from the second section that CAS operation on a single shared object ensures atomicity of its update and acquisition, while atomic operation on multiple shared variables cannot be carried out simultaneously. This is a limitation of CAS, but the JDK also provides an AtomicReference class to ensure atomicity between reference objects, allowing multiple variables to be placed in one object for CAS operations.