CAS (compare-and-swap)

CAS is contrast exchange, which reduces the use of locks as much as possible on the premise of ensuring atomicity of data. CAS is widely used in many programming languages or system implementations.

CAS implementation in JAVA

The Unsafe method is the main application of CAS in JAVA. The Unsafe CAS operation is based on hardware platform assembly instructions. Most processors support CAS, but different vendors implement cas differently.

Unsafe provides three methods for CAS operations, namely

public final native boolean compareAndSwapObject(Object value, long valueOffset, Object expect, Object update);

public final native boolean compareAndSwapInt(Object value, long valueOffset, int expect, int update);

public final native boolean compareAndSwapLong(Object value, long valueOffset, long expect, long update);
Copy the code
  • Value Indicates the object to be operated on
  • ValueOffset Indicates the offset of the address of the object (value)Unsafe.objectFieldOffset(Field valueField)Get)
  • Expect stands for the expected value of value when it is updated
  • Update indicates the value to be updated

When the CAS operation is performed, the thread retrieves the current value from the memory according to valueOffset and compares it with expect’s value. If the value is consistent, change it and return true. If the value is inconsistent, other threads are also modifying the value of this object, and return false

Unsafe class, compareAndSwapInt

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
Copy the code

ABA problem

Thread 1 tries to change the value of variable A with CAS. Before that, other threads replace the value of variable A with B and then B with A. Then thread 1 executes CAS and finds that the value of variable is still A, so the CAS succeeds. But the reality is that the scene is different now.




aba.png

example

public static AtomicInteger a = new AtomicInteger(1); Public static void main(String[] args){Thread main = new Thread(() -> {system.out.println (" Thread "+) Thread.currentthread () +"; Thread.sleep(1000); thread.sleep (1000); // Wait 1 second for the interfering thread to execute} catch (InterruptedException e) {e.printStackTrace(); } Boolean isCASSuccess = a.compareAndSet(1,2); Println (" Thread "+ thread.currentThread () +",CAS result:" + isCASSuccess); }," main operation thread "); Thread other = new Thread(() -> { a.incrementAndGet(); System.out.println(" thread.currentThread () +", [increment] = "+ a "); a.decrementAndGet(); System.out.println(" rement "+ thread.currentThread () +",【 retirement 】, value = "+ a "); }," thread interference "); main.start(); other.start(); }Copy the code
If (1, 2, 3, 3, 3, 3, 3, 3, 3) > increment () if (2, 3, 3) > increment () Rement (); rement (); rement (); rement ()Copy the code

ABA Solution

Train of thought

The simplest solution to ABA is to add a modified version number to the value. Each time the value changes, the version number is changed and the CAS operation is compared to this version number.


aba_2.png

ABA Solution in JAVA (Atomic Stampede Ference)

AtomicStampedReference maintains a pair containing an object reference and an integer “stamp” that can be automatically updated to solve ABA problems.

Public class AtomicStampedReference<V> {private static class Pair<T> {final T reference; // The maintenance object references 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; . /** * expectedReference: The original value is updated * newReference: the new value to be updated * expectedStamp: the flag version you expect to update * newStamp: */ public Boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { Pair<V> current = pair; // Get the current pair return expectedReference == current. Reference && // The original value is equal to the value reference of the current pair, The value is unchanged The original mark version is equal to the current mark version of the pair, Mark did not change ((newReference = = current. The reference && newStamp = = current. The stamp) | | / / no change to update values and tag casPair (current, Pair.of(newReference, newStamp))); // Cas update pair}}Copy the code

example

private static AtomicStampedReference<Integer> atomicStampedRef = new AtomicStampedReference<>(1, 0); Public static void main(String[] args){Thread main = new Thread(() -> {system.out.println (" Thread "+) Thread. CurrentThread () + ", the initial value a = "+ atomicStampedRef. GetReference ()); int stamp = atomicStampedRef.getStamp(); Thread.sleep(1000); thread.sleep (1000); // Wait 1 second for the interfering thread to execute} catch (InterruptedException e) {e.printStackTrace(); } Boolean isCASSuccess = atomicStampedRef.com pareAndSet (1, 2, stamp, stamp + 1); System.out.println(" operation Thread "+ thread.currentThread () +") CAS result " + isCASSuccess); }," main operation thread "); Thread other = new Thread(() -> { AtomicStampedRef.com pareAndSet (1, 2, atomicStampedRef getStamp (), atomicStampedRef. GetStamp () + 1); System. Out. Println (" Thread "+ Thread. CurrentThread () +", "increment" value = "+ atomicStampedRef. GetReference ()); AtomicStampedRef.com pareAndSet (2, 1, atomicStampedRef getStamp (), atomicStampedRef. GetStamp () + 1); System. The out. Println (" Thread "+ Thread. CurrentThread () +", "decrement" value = "+ atomicStampedRef. GetReference ()); }," thread interference "); main.start(); other.start(); }Copy the code
Rement (); rement (); rement (); rement (); rement (); Thread[primary Thread,5,main],CAS result: trueCopy the code