“This is the 19th day of my participation in the November Gwen Challenge. Check out the event details: The Last Gwen Challenge 2021
CAS, Compare And Swap. Doug Lea uses CAS technology to implement concurrent Java multithreading in synchronous components. The entire AQS synchronization component, Atomic class operations, and so on are implemented in CAS, and even ConcurrentHashMap was adjusted to CAS+Synchronized in version 1.8. CAS is the cornerstone of JUC.
Analysis of the CAS
There are three parameters in CAS: the memory value V, the old expected value A, and the value to be updated B. The memory value V is changed to B if and only if the memory value V is equal to the old expected value A, otherwise nothing is done. Its pseudocode is as follows:
if(this.value == A){
this.value = B
return true;
}else{
return false;
}
Copy the codeAtomic classes under JUC are implemented through CAS. Here we take AtomicInteger as an example to illustrate the implementation of CAS. As follows:
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;
Copy the codeUnsafe is the core CAS class. Java does not access the underlying operating system directly, but rather through native methods. Even so, the JVM opens a backdoor: Unsafe, which offers hardware-level atomic operations.
ValueOffset is the offset address of a variable value in memory. Unsafe is used to obtain the original data value.
Value The current value, using the volatile modifier to ensure that the same values are seen in multithreaded environments.
AtomicInteger addAndGet() ¶
public final int addAndGet(int delta) { return unsafe.getAndAddInt(this, valueOffset, delta) + delta; } 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)); return var5; }Copy the codeUnsafe internally calls the getAndAddInt method, in which the focus is on the compareAndSwapInt method:
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Copy the codeThis method is a local method with four parameters, representing the object, the address of the object, the expected value, and the modified value. . The implementation of this method is not described in detail here, interested partners can take a look at the openJDK source code.
CAS ensures that a read-change-write operation is atomic, which is easy to implement on a single processor, but a bit more complicated on multiple processors.
The CPU provides two ways to implement atomic operations on multiple processors: bus locking or cache locking.
- Bus locking: bus locking is the use of a LOCK# signal provided by a processor. When one processor outputs this signal on the bus, requests from other processors will be blocked and the processor can exclusively use the shared memory. It locks up the communication between the CPU and memory. During the lock, no other processor can access the memory address, which is a bit expensive. So you have cache locking.
- Cache lock: in this case we only need to ensure that the operation on a memory address is atomic at the same time. Cache locking is when the data is cached in the memory region. If during the locking period, when it performs the lock operation and writes back to memory, the processor does not output the LOCK# signal, but changes the internal memory address, using the cache consistency protocol to ensure atomicity. The cache consistency mechanism ensures that data in a memory region can only be modified by one processor. This means that if CPU1 modifies the I in the cache row by using a cache lock, then CPU2 cannot also cache the I in the cache row.
CAS defects
Although CAS solves atomic operation efficiently, it still has some defects, mainly manifested in three methods: too long cycle time, only one shared variable atomic operation can be guaranteed, ABA problem.
The cycle time is too long
What if CAS is never successful? This is definitely possible, and if the spin CAS is unsuccessful for an extended period of time, it can be very expensive for the CPU. There are places in JUC that limit the number of CAS spins, such as the SynchronousQueue of BlockingQueue.
Only one shared variable atomic operation is guaranteed
If you have multiple shared variables, you can only use locks. Of course, if you have a way to consolidate multiple variables into a single variable, CAS is also good. For example, the high status of state in read/write locks
ABA problem
CAS needs to check whether the operation value has changed. If not, CAS updates the operation value. But there is A situation where if A value is A, changes to B, and then changes to A, CAS checks that it has not changed, but it has changed. This is called the ABA problem. The solution to the ABA problem is to add A version number, that is, add A version number to each variable and add 1 to each change, so that A — > B — > A becomes 1A — > 2B — > 3A.
Use an example to illustrate the impact of ABA problems.
There is the following linked list
Let’s say we want to replace B with A, so compareAndSet(this,A,B). Thread 1 replaces thread A with thread B. Thread 2 mainly performs the following actions: A and B are removed from the stack, and then C and A are added to the stack. Finally, the linked list is as follows:
If b.ext = null,compareAndSet(this,A,B) will cause C to be lost, and only one B element will be added to the stack. I lost the C for no reason.
CAS hidden ABA problem, the solution is version number, Java provides AtomicStampedReference to solve. AtomicStampedReference avoids THE ABA problem by packing a tuple of [E,Integer] to stamp the version of the object marker. In the above case thread 1 should fail.
The compareAndSet() method of AtomicStampedReference is defined as follows:
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
Copy the codeCompareAndSet takes four parameters: expected reference, updated reference, expected flag, and updated flag. Source code is well aware that expected references == current references, expected identifiers == current identifiers, return true if updated references and identifiers are equal to current references and identifiers, otherwise a new Pair object is generated to replace the current Pair CAS. Pair is an internal class of AtomicStampedReference, which records reference and version stamp information (id). The definitions are as follows:
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 new Pair<T>(reference, stamp);
}
}
private volatile Pair<V> pair;
Copy the codePair records the reference and version stamp of the object. The version stamp is int and keeps incrementing. A Pair is an immutable object with all properties defined as final and provides an of method that returns a newly created Pari object. The pair object is defined as volatile to ensure visibility in multithreaded environments. Most methods in an AtomicStampedReference generate a new Pair object by calling the of method of a Pair and assigning it to the Pair. For example, set method:
public void set(V newReference, int newStamp) { Pair<V> current = pair; if (newReference ! = current.reference || newStamp ! = current.stamp) this.pair = Pair.of(newReference, newStamp); }Copy the codeHere is an example to see the difference between AtomicStampedReference and AtomicInteger. Let’s define two threads, thread 1 is responsible for 100 – > 110 – > 100, thread 2 is responsible for 100 – >120, see the difference between the two.
public class Test { private static AtomicInteger atomicInteger = new AtomicInteger(100); Private static AtomicStampedReference AtomicStampedReference = new AtomicStampedReference(100,1); public static void main(String[] args) throws InterruptedException { //AtomicInteger Thread at1 = new Thread(new A Runnable () {@ Override public void the run () {atomicInteger.com pareAndSet (100110); AtomicInteger.com pareAndSet (110100); }}); Thread at2 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(2); // at1, complete} catch (InterruptedException e) {e.printStackTrace(); } System. Out. Println (" AtomicInteger: "+ atomicInteger.com pareAndSet (100120)); }}); at1.start(); at2.start(); at1.join(); at2.join(); Thread tsf1 = new Thread(new Runnable() {@override public void run() {try { Timeunit.seconds.sleep (2); } catch (InterruptedException e) { e.printStackTrace(); } // Expected reference: 100, updated reference: In 110, Expected identifier getStamp() Updated identifier getStamp() + 1 AtomicStampedReference.com pareAndSet (100110, atomicStampedReference getStamp (), atomicStampedReference. GetStamp () + 1); AtomicStampedReference.com pareAndSet (110100, atomicStampedReference getStamp (), atomicStampedReference. GetStamp () + 1); }}); Thread tsf2 = new Thread(new Runnable() { @Override public void run() { int stamp = atomicStampedReference.getStamp(); try { TimeUnit.SECONDS.sleep(2); Catch (InterruptedException e) {e.printStackTrace(); } System. Out. Println (" AtomicStampedReference: "+ atomicStampedReference.com pareAndSet (100120, stamp, stamp + 1)); }}); tsf1.start(); tsf2.start(); }}Copy the codeRunning results:
The results fully demonstrate the ABA problem of AtomicInteger and the ABA problem solved by AtomicStampedReference.