The concept of the CAS

The full name of CAS: CompareAndSet, which literally means CompareAndSet.

CAS is actually an instruction supported by A common processor that implements atomicity by comparing and setting the new value by determining whether the current memory value V, the old expected value A, and the value B to be updated are equal.

As mentioned in the previous article, “The Three features of threads”, atomicity can be achieved by Synchronized, but Synchronized blocks the thread when performing a heavyweight lock, which increases the resource cost in the case of many threads. The emergence of CAS is to let the thread do not block, by the way of spinning and waiting.

Synchronized blocks threads called pessimistic locks, while CAS does not block threads called optimistic locks. A pessimistic lock allows multiple threads to access the code at the same time, but determines if there is an update and then reexecutes the code.

Implementation principles of CAS

The principle of CAS: Through three parameters, the current memory variable value V, the old expected value A, and the value B to be updated. Check whether the value of the current variable has been changed by other threads by judging whether V and A are equal. If they are equal, the value of the variable has not been changed by other threads, and then assign the value of B to V. If they are not, spin them.

For example, if the initial value of I is 0 and the two threads execute I ++ respectively, let’s see how CAS executes:

1 thread: A = 0,B = 1

2 thread: A = 0,B = 1

In this case, the old expected value A and the updated value B of both threads are the same. Suppose thread 1 executes first, thread 1 gets the value V of I from memory, and V is equal to 0, which is exactly the same as the old expected value A, and assigns the updated value B to the memory value V of I. When thread 2 executes, the value of V in memory is 1 and does not wait with the old expected value 0, then the assignment operation of updating B is not done, and the old expected value A=V is spun, and the CAS instruction is determined again.

The atomic operation class provided by JDK is based on CAS to achieve atomicity, such as AtomicInteger, AtomicIntegerArray, AtomicDouble, AtomicBoolean and so on

So take a look at the AtomicInteger code to see how it implements the i++ operation.

public class AtomicInteger extends Number implements java.io.Serializable { private static final long serialVersionUID =  6214790243416807050L; private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); private static final long VALUE; static { try { VALUE = U.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (ReflectiveOperationException e) { throw new Error(e); } } private volatile int value; Public final int getAndIncrement() {return u.getAndAddInt (this, VALUE, 1); }Copy the code

The sun.misc.unsafe class is used here. This class performs spin operations and calls the local CAS method. Value is used to store variables; VALUE is the offset of the VALUE variable in memory, valueOffset. The getAndIncrement() method is equivalent to executing VALUE ++, which guarantees atomicity. This method calls unsafe.getAndAddint (this, VALUE, 1), indicating that the implementation is in the Unsafe class.

public final class Unsafe { public native int getIntVolatile(Object var1, long var2); public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5); 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 code

In the getAndAddInt method, there are three method parameters: VAR1 is the AtomicInteger, VAR2 is the memory offset of the value of the AtomicInteger, and VAR4 is the incremental value to be updated.

Var5 is obtained by getIntVolatile(VAR1, VAR2). It is a native method to obtain the value of VAR1 at the offset of VAR2.

Through the while (! CAS()) determines that the value of VAR1 is equal to that of VAR5, then assigns var5 + VAR4 to value, and CAS() returns true to end the loop. Otherwise, the operation continues by spin.

Problems arising from CAS

ABA problem

When one thread changes the variable from A->B to A, the other thread will assume that the variable has not been modified and is still A, which is causing the ABA problem.

To solve ABA problems, the JDK also provides an AtomicStampedReference and an AtomicMarkableReference to mark the version number and identifier. An AtomicStampedReference uses a built-in static class Pair to mark the version number

private static class Pair<T> { final T reference; final int stamp; private Pair(T var1, int var2) { this.reference = var1; this.stamp = var2; } static <T> AtomicStampedReference.Pair<T> of(T var0, int var1) { return new AtomicStampedReference.Pair(var0, var1); }}Copy the code

Reference is the variable of the atomic operation, and stamp records the version number. Change the version number after changing the variable, so that you can determine whether the ABA problem has been changed, and AtomicMarkableReference is similarly marked with Boolean. Common methods of AtomicStampedReference:

Public AtomicStampedReference(V initialRef, Public int getStamp() public int getStamp() public int getStamp() public int getStamp() Public Boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, Int newStamp) // update the new version to memory if the current reference equals the expectedReference public Boolean attemptStamp(V expectedReference,) Public void set(V newReference, int newStamp) public void set(V newReference, int newStamp)Copy the code

Spin problem

If there are many threads, the while loop of the CAS () method will continue to execute, and it will waste resources if it executes for a long time.

conclusion

To address atomicity of threads, you can use Synchronized if you are synchronizing a block of code, or AtomicInteger if you are synchronizing only one variable. The CAS determines whether the variable has been changed by another thread through the memory value, expected value, and new value. Threads that fail to update spin until the update is complete. There are two problems with CAS: the ABA problem and the spin time problem.