This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
What is the CAS
CAS, also known as comparison and exchange, is a lock-free algorithm. In daily development, CAS is not used directly, but is used by some concurrent tool classes packaged in JDK, under the JUC package.
CAS contains three values, memory address (V), expected value (A), and new value (B). The value of the memory address is compared to the expected value. If the value is equal, the new value is assigned to the memory address. Otherwise, no processing is done. The steps are as follows:
1. Obtain the expected value of the field.
2. Calculate the newValue to be replaced.
3. Place the newValue on the memory address of the field through CAS. If the CAS fails, steps 1 to 2 are repeated until the CAS succeeds.
When CAS compares the value of the memory address with the expected value, if the value is equal, it proves that the memory address value has not been modified, can be replaced with the new value, and then continue to run. If not, say that the value of the memory address has been changed, abandon the replacement operation, and then re-spin. When the number of concurrent modification threads is small and the chance of conflict is small, the number of spins will be small and CAS performance will be high. When the number of concurrent modification threads is large and the chance of conflict is high, the number of spins will also be large, and CAS performance will be greatly reduced. Therefore, the key to improve the efficiency of CAS lock-free programming is to reduce the chance of conflicts.
Analysis of CAS Principle
Take AtomicInteger as an example to see the underlying CAS implementation mechanism.
public class AtomicInteger extends Number implements java.io.Serializable { private static final long serialVersionUID = 6214790243416807050L; private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; // The AtomicInteger value field is the offset // address of the address field. The value field is volatile. Static {try {// Obtain the memory offset of value valueOffset = unsafe.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; Public AtomicInteger(int initialValue) {value = initialValue; }Copy the codePublic final int getAndAdd(int delta) {return unsafe. GetAndAddInt (this,); valueOffset, delta); Public final int incrementAndGet() {return unsafe. GetAndAddInt (this, valueOffset, 1) + 1; } public final Boolean compareAndSet(int expect, int update) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); } // Unsafe. Unsafe class; public final int getAndAddInt (Object o,long offset, int delta){int v; do { v = getIntVolatile(o, offset); } while (! weakCompareAndSetInt(o, offset, v, v + delta)); return v; }Copy the codeThe AtomicInteger internal methods are implemented based on the Unsafe class, which is a replication utility class that communicates with the underlying hardware CPU instructions. Unsafe. GetAndAddInt ()
//CAS spins, uses getIntVolatile to get the latest value of the object from the memory offset, and calls CAS. Public final int getAndAddInt(Object var1, Long var2, int var4) {int var5; Var5 = this.getIntVolatile(var1, var2); // The broadening object var1 // and var5, the offset var2 and the corresponding unsafe object var1 //, are taken into compareAndSwapInt to obtain the value referred to by the offset. // The broadening object var5 is the expected value. //var5 + var4; //var5 + var4; //var5 + var4; //var5 + var4 this.compareAndSwapInt(var1, var2, var5, var5 + var4)); return var5; }Copy the codeHow to obtain valueOffset:
// Unsafe instance private static final Unsafe = Unsafe. GetUnsafe (); private static final long valueOffset; ValueOffset = unsafe.objectFieldoffSet static {try {// Get value's offset in AtomicInteger (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); }} private volatile int value;Copy the codeValue The actual variable, which is specified by the volatile keyword, to ensure memory visibility across multiple threads.
The problem of the CAS
ABA problem
The CAS operation compares whether the expected value of A is the same as the value in the memory address. If the value is the same, no other thread changes the value of A at this time. However, if one thread reads the value of A, another thread changes the value of A to B, and then changes the value of B back to A, then the comparison between A and the expected value is the same, and the value of A is considered unchanged. In order to solve the ABA problem, you can use the version number, and each time you change the variable, add 1 to the version number of the variable, so that A->B->A, although the value of A has not changed, but its version number has changed, and then judge the version number will find that A has been changed by someone else.
AtomicReference AtomicReference
Performance issues
If the spin is not successful for a long period of time, it can be very expensive for the CPU to execute.
public final int getAndSet(int newValue) { for (;;) { int current = get(); if (compareAndSet(current, newValue)) return current; }}Copy the codeAs you can see in the source code, the spin only returns when the CAS succeeds. So the performance issues that CAS brings are also something to consider. Spin is also a feature of CAS. Spin is a non-blocking algorithm. Compared with other blocking algorithms, non-blocking algorithm does not require CPU to switch time slices to save context, saving a lot of performance consumption. Advantages of CAS over synchronous locking: If the concurrency is not very high, THE CAS mechanism can improve efficiency, but in the case of high competition and concurrency, the efficiency is very low, because the spin time is too long, and the number of failures leads to too many retries.
Atomic operations of only one shared variable are guaranteed
When performing operations on a shared variable, we can loop CAS to ensure atomic operations, but when performing operations on multiple shared variables, the loop CAS cannot guarantee atomic operations, so we can use locks. Another trick is to combine multiple shared variables into a single shared variable. For example, if you have two shared variables I =2, j=a, merge ij=2a, and then use CAS to manipulate ij. Since Java 1.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.
ABA problem solutions
Add the version number
Each time you modify A variable, add 1 to the version number of the variable, so that A->B->A has changed, although the value of A has not changed, but the version number has changed, and then judge the version number will find that A has been changed. Referring to the version number of the optimistic lock provides a validation of the data.
The compareAndSet method of AtomicStampReference first checks whether the current object reference value is equal to the expected reference and whether the current Stamp flag is equal to the expected flag, and if all are equal, atomically updates the reference value and Stamp flag value to the given update value.
Using AtomicMarkableReference
AtomicMarkableReference does not care how many times it has been modified, only whether it has been modified. The tag attribute mark is a Boolean type, not a number type, and only records whether the value has been changed. AtomicMarkableReference is suitable for situations where you only know if the object has been modified, but not for situations where the object has been modified repeatedly.
CAS application scenarios
CAS is used to implement important concurrent container classes such as atomic classes in JUC packages, AQS, and CurrentHashMap. Look again at the AQS example:
protected final boolean compareAndSetState(int expect, int update) {
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
Copy the codeThe CAS operation on the state variable is used by many synchronous classes to implement thread-safety, so in AQS, the first thing to do is to ensure that the assignment of state is thread-safe.
In Java. Util. Concurrent. Atomic atoms such as AtomicXXX package, use the CAS guarantee atomicity of digital members to operate. Most of JUC’s classes (including display locks and concurrent containers) are implemented based on AQS and AtomicXXX, while AQS guarantees atomicity of its internal bidirectional queue head and tail operations through CAS.
Draw that
1. This event is supported by the Nuggets official details can be found at juejin.cn/post/701221…
2. You can participate through comments and articles related content, and article content related oh!
3. This month’s articles will participate in the lucky draw, welcome more interaction!
4. In addition to the official lottery of nuggets, I will also give peripheral gifts (one mug and several nuggets badges, mugs will be given to fans, badges will be randomly selected, the number of badges will increase according to the number of comments).