define

  • CAS (CompareAndSwap, CompareAndSet) and replace, core logic is to get the current value first, incoming expectations and to the value of the modified into if match the expectations and existing value, is the value to the incoming to change into value.
  • CAS is an instruction of the CPU (which requires JNI to call Native methods to call CPU instructions), so it ensures that atomic operations will not be modified by other threads during comparison and replacement
  • CAS is a non-blocking, lightweight optimistic lock

role

  • Because it is unlocked, non-blocking, lightweight optimistic locking, many underlying the use of CAS, for example, Java. Util. Concurrent. The atomic atomic classes, Unsafe, spin locks etc…

The principle of

  • You can understand how CAS is implemented by analyzing atomic classes.

1. AtomicInteger class

AtomicInteger count = new AtomicInteger(0); count.incrementAndGet(); Unsafe. private static final unsafe = unsafe. getUnsafe(); // unsafe. unsafe. getUnsafe(); public final int incrementAndGet() { return unsafe.getAndAddInt(this, valueOffset, 1) + 1; }Copy the code

2. The Unsafe class

@callersensitive // is deprecated in jdk11, and can only be called by developers Other without permission public static Unsafe getUnsafe () {Class var0 = Reflection. GetCallerClass (); if (! VM.isSystemDomainLoader(var0.getClassLoader())) { throw new SecurityException("Unsafe"); } else { return theUnsafe; } } 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; } /** * CAS * @param o contains the object where the field is to be modified * @param offset The offset of a field in the object * @param expected * @param update the update value * @return True | false * through object and offset for current values, then contrast and expectations, if update is replaced with the same value, */ Public final Native Boolean compareAndSwapInt(Object O, long offset, int expected, int update);Copy the code

ABA problem

  • Question: The core of CAS is to compare and replace. During the comparison, only the comparison value is the same. How can there be such a situation: A thread that set the value to A, another thread to get the current value of A and as expected, at the same time there is A thread to change the value from A to B to A, then we compare A as expectations of threads found is the same for the replacement, but did not know that in fact this is not the former that A. There are no problems with primitive data types, but exceptions can be caused by reference data types.

  • To mark a solution, use AtomicStampedReference

Private Final Static AtomicStampedReference<String> AR = new AtomicStampedReference<>("A", 1); // When investigating CAS, compare the expected value and version number,  boolean isCas = ar.compareAndSet(A, B, 1) /** * @param expectedReference The expected value of the reference * @param newReference the new value of the reference * @param expectStamp The expected value of the mark * @param newStamp Flag new value * @return {@code true} If successful */ 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))); } private boolean casPair(Pair<V> cmp, Pair<V> val) { return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val); }Copy the code