Compare and Swap (CAS) algorithm in detail

Introduction of the CAS

CAS means compare and swap. Cas was introduced to address performance issues caused by the Java locking mechanism. The locking mechanism has the following problems:

(1) In the multi-threaded competition, locking and releasing locks will lead to more context switching and scheduling delay, resulting in performance problems.

(2) A lock held by one thread causes all other threads requiring the lock to suspend.

(3) If a thread with a higher priority waits for a thread with a lower priority to release the lock, priority inversion will occur, causing performance risks.

Volatile is a good mechanism for addressing thread-safety issues, but volatile does not guarantee atomicity. So synchronization ultimately comes back to locking. An exclusive lock is a pessimistic lock, and synchronized is an exclusive lock that causes all other threads requiring the lock to suspend until the thread holding the lock releases it. An even more effective lock is the optimistic lock. Optimistic locking is when an operation is performed each time without locking, assuming no conflicts, and then retry until it succeeds if it fails because of conflicts.

CAS Principle Flow Chart

CAS has three operands, the memory value V, the old expected value A, and the new value B to modify. Change the memory value V to B if and only if the expected value A and memory value V are the same, otherwise nothing is done.

For example, A very simple operation, add 1 to the variable A = 2, and the result is 3.

Then, the current value E of A is read as 2 first, and the result V is calculated as 3 in memory. Compare the current value 2 of A read before with the latest value. If the latest value is 2, it means that the value has not been changed by others, so you can rest assured to update the final value to 3.

ABA problem

In one case, some other thread updates A to 5 and then back to 2 in the middle before you update the result. However, the current thread does not appear to have been modified.

JAVA CAS implementation principle

CAS in JAVA is implemented through code that calls JNI (JAVA Native Interface).

Take AtomicInteger’s compareAndSet in JAVA:

public class AtomicInteger extends Number implements java.io.Serializable { // setup to use Unsafe.compareAndSwapInt for  updates private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; Static {try {// Evaluates the offset valueOffset = unsafe.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; Public final Boolean compareAndSet(int expect, int update) {/* * compareAndSet The main logic is wrapped in the Unsafe * compareAndSwapInt method */ return unsafe.compareAndSwapInt(this, valueOffset, expect, update); } / /... } public final class Unsafe {// compareAndSwapInt is a native type of method, Public Final Native Boolean compareAndSwapInt(Object O, long offset, int expected, int X); / /... }Copy the code

The Unsafe compareAndSet is really just a shell, and the main logic is encapsulated in the Unsafe compareAndSwapInt method to parse it:

C + + source code

// unsafe. CPP /* * This doesn't look like a function, but don't worry, it's not the point. UNSAFE_ENTRY and UNSAFE_END are macros that * are replaced with real code during precompilation. The following jboolean, jlong, and jint are some type definitions (typedef) : * * jni.h * typedef unsigned char jboolean; * typedef unsigned short jchar; * typedef short jshort; * typedef float jfloat; * typedef double jdouble; * * jni_md.h * typedef int jint; * #ifdef _LP64 // 64-bit * typedef long jlong; * #else * typedef long long jlong; * #endif * typedef signed char jbyte; */ 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); // Calculate the address of value based on the offset. AtomaicInteger valueOffset jint* addr = (jint *) index_oop_from_field_offset_long(p, offset); Return (jint)(Atomic:: CMPXCHG (x, addr, e)) == e; // Call the CMPXCHG function declared in atomic.hpp. UNSAFE_END // atomic.cpp unsigned Atomic::cmpxchg(unsigned int exchange_value, volatile unsigned int* dest, unsigned int compare_value) { assert(sizeof(unsigned int) == sizeof(jint), "more work to do"); /* * Call overloaded functions on different platforms depending on the operating system type. During precompilation, the compiler decides which platform overloaded * functions to call. The associated precompilation logic is as follows: * * atomic.inline-hpp:  * #include "runtime/atomic.hpp" * * // Linux * #ifdef TARGET_OS_ARCH_linux_x86 * # include "Atomic_linux_x86.inline-hpp" * #endif * * // omit some code * * / Windows * #ifdef TARGET_OS_ARCH_windows_x86 * # include "atomic_windows_x86.inline.hpp" * #endif * * // BSD * #ifdef TARGET_OS_ARCH_bsd_x86 * # include "Atomic_bsd_x86.inline. HPP" * #endif * * Next analyze the CMPXCHG function implementation in atomic_windows_x86.inline. HPP */ return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest, (jint)compare_value); }Copy the code

Let’s try to get the address of the variable value in memory. Comparison substitution is implemented by Atomic:: CMPXCHG, where parameter x is the value to be updated and parameter e is the value of the original memory.

Implementation of a Concurrent package

Because Java CAS has memory semantics for both volatile reads and volatile writes, Java threads now communicate in the following four ways:

Thread A writes the volatile variable, and thread B reads the volatile variable. Thread A writes the volatile variable, and thread B updates the volatile variable with CAS. Thread A updates A volatile variable with CAS, and thread B updates the volatile variable with CAS. Thread A updates A volatile variable with CAS, which thread B then reads.

Java CAS will use modern processors provide efficient machine level atomic instructions, these atoms instruction atomically to memory read – to – write operations, this is the key to achieve synchronization in multiprocessor (in essence, can support atomic reading – to – writing instruction computing machines, calculate the Turing machine is order equivalent asynchronous machine, So any modern multiprocessor will support some kind of atomic instruction that can perform atomic read-modif-write operations on memory. Meanwhile, read/write of volatile variables and CAS enable communication between threads. Taken together, these features form the building blocks for the implementation of the concurrent package. If we look closely at the source code implementation of the Concurrent package, we will find a common implementation pattern:

First, declare the shared variable volatile; Then, atomic conditional update of CAS is used to achieve synchronization between threads. At the same time, the thread communication is realized with volatile read/write and CAS memory semantics.

AQS, non-blocking data structure and the atomic variable classes (Java. Util. Concurrent. Atomic package’s classes), the concurrent is the base class in the package using this model, and the top class in the concurrent bag is dependent on the base class. As a whole, the implementation of the Concurrent package looks like this:

This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.