Optimistic lock CAS

One, foreword

So far in our Little White Series, we’ve covered the following topics:

Synchronized code block;
Volatile variables visible;
JOL (Java Object Layout) Object Layout;
JMM (Java Memory Model);
Happens-before rules;

The reason why we spent a lot of time and energy to popularize the above content, on the one hand, is to let everyone more comprehensive and detailed grasp of these basic knowledge, on the other hand, is to prepare for our next content, lay a good foundation.

Starting from this, although is still a popular small white know, however, we will involve the content of the “lock”, JDK1.5, joined the concurrent package, the package also provides several locks, through my explanation, hope everybody can faster to master them, can according to the different situation to choose the most reasonable “lock” to realize their needs, Achieve optimum performance.

So, we officially enter the “lock” series of the first content: optimistic lock CAS (CompareAndSwap).

Second, the CAS

Take it literally: Compare and swap! What does that mean? When we want to change the value of an object, WE want to compare whether the object is the expected value and, if so, swap our new value with the expected (existing) value, that is, change the value of the object.

Why do you need to compare? Let’s look at an example:

public class Demo { private int x = 10; public void increase() { try { Thread.sleep(10); } catch (InterruptedException e) { e.printStackTrace(); } x ++; System.out.println(Thread.currentThread() + ", x = " + x); } public static void main(String[] args) { Demo demo = new Demo(); new Thread(demo::increase).start(); new Thread(demo::increase).start(); }}Copy the code

We expect two threads to perform the “increase” method, for x +1, for two manipulators, for x to be 12, and let’s look at the possible results:

Thread[thread-1,5,main], x = 11 Thread[thread-1,5,main], x = 11 X = 11 Thread[thread-1,5,mainCopy the code

Obviously, we don’t want outcome 1, we want outcome 2. Since the two threads are executing concurrently, copies of X are modified in each worker thread, making the value of x invisible. The simplest and lightest way to make x invisible is to use the volatile modifier, followed by synchronized.

So is there another way?

Of course, the CAS comparison swap is the lightweight lock we want, and CAS requires two inputs: E and N, “Expect value” and “Update value.” Before we update an object, we expect the value of the current object to be our expected value. Only the expected value indicates that no other thread has modified it, so we can modify it. If the value of the current object is not what we expect, we cannot update it, otherwise the object’s data will become dirty.

JDK1.5 provides us with a set of atomically operated classes under the concurrent/atomic directory that begin with atomic:

A class that begins with Atomic and provides a method

public class AtomicXXXX { public final boolean compareAndSet(V expect, V update) { return unsafe.compareAndSwapObject(this, valueOffset, expect, update); }}Copy the code

This is CAS, which is provided by the Unsafe class.

We can take a look at AtomicInteger source code:

public class AtomicInteger extends Number implements java.io.Serializable { public final boolean compareAndSet(int expect, int update) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); } public final int getAndSet(int newValue) { return unsafe.getAndSetInt(this, valueOffset, newValue); }}Copy the code

public final class Unsafe {
    public final int getAndSetInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var4));
    
        return var5;
    }
}
Copy the code

Whether directly using AtomicInteger.com pareAndSet or AtomicInteger getAndSet, eventually will be called the Unsafe compareAndSwapInt method to complete our updates, just, The former direct call is the program given the expected conditions and meet the update, while the latter is mandatory update.

So, let’s modify our example:

public class CASDemo { private AtomicInteger x = new AtomicInteger(10); public void increase() { try { Thread.sleep(10); } catch (InterruptedException e) { e.printStackTrace(); } x.getAndIncrement(); System.out.println(Thread.currentThread() + ", x = " + x); } public static void main(String[] args) { CASDemo demo = new CASDemo(); new Thread(demo::increase).start(); new Thread(demo::increase).start(); }}Copy the code

Print the output again:

Thread[Thread-0,5,main], x = 11
Thread[Thread-1,5,main], x = 12
Copy the code

To achieve the desired effect.

Third, CAS underlying implementation

3.1, the Unsafe

The Unsafe class’s “objectFieldOffset” is a native method, implemented by underlying C++, to retrieve the memory location of a field in an object instance.

Broadening also provides CAS operations, the “compareAndSwap” optimistic lock method. Taking a look at the CAS method in AtomicInteger:

public class AtomicInteger extends Number implements java.io.Serializable { private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; static { try { 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) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); }}Copy the code

From this approach, we see several things:

ValueOffset is the memory address of the value member variable.
Expect is the value we expect value to be;
Update is the value we want to update (modify);

The unsafe.com parenAndSwapInt is a native method:

public final class Unsafe { public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5); Public final Native Boolean compareAndSwapLong(Object var1, Long var2, Long var4, Long var6); public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5); }Copy the code

3.2 Native implementation of Unsafe.compareAndXXX

JDK1.8 native source:

The corresponding definitions of three JNI methods are found. Let’s look at the implementation:

3.3, Unsafe_CompareAndSwapInt

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) UnsafeWrapper("Unsafe_CompareAndSwapInt"); // Get an object, such as AtomicInteger OOP p = JNIHandles::resolve(obj); Jint * addr = (jint *) index_oop_from_field_offset_long(p, offset); Atomic:: CMPXCHG (x, addr, e); Return (jint)(Atomic:: CMPXCHG (x, addr, e)) == e; UNSAFE_ENDCopy the code

The Atomic:: CMPXCHG method depends on the OS CPU. We can look at the hotspot/ os_CPU directory and use linux_x86/vm/atomic_linux_x86.inline. HPP as an example.

#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: " inline jint Atomic::cmpxchg(jint exchange_value, volatile jint* dest, jint compare_value) { int mp = os::is_MP(); // Number of cpus > 1, mp = 1, otherwise MP = 0 __asm__ volatile (LOCK_IF_MP(%4) "CMPXCHGL %1,(%3)" : "=a" (exchange_value) : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp) : "cc", "memory"); return exchange_value; }Copy the code

Here are the embedded assembly instructions (when C and C++ code are mixed together), and we see that CMPXCHG also locks on multiple cpus, the result of the expansion of the macro “LOCK_IF_MP”.

3.4 understanding of embedded assembly

Asm means that the following code is embedded assembly;
Volatile indicates that the compiler does not optimize the code and that subsequent instructions are left as they are. Volatile is an alias for volatile;
CMPXCHG is an assembly instruction that compares and swaps operands
CMPXCHGL adds l for 4 bytes;

Embedded assembly template

Asm (Assembler Template: Output Operands (optional) : list of clobbered registers (optional) );Copy the code

Input, i.e. input is: “R” (exchange_value), “A” (compare_value), “R” (dest), “r” (mp) indicates that compare_value is stored in the EAX register; The values of exchange_value, dest, mp can be stored in any general purpose register.

Embedded assembly specifies that the output and input registers are numbered in a uniform order: the order is from left to right from top to bottom starting with “%0”, denoted as %0, %1 ··· %9; That is, the output eax is %0 and the input exchange_value, compare_value, dest, and MP are %1, %2, %3, and %4 respectively.

Therefore, CMPXCHGL %1,(%3) actually represents CMPXCHGL exchange_value,(dest), where (dest) represents the value stored at the DEST address.

Note that CMPXCHGL has an implicit operand, eax. The actual process of CMPXCHGL is to compare the value of eAX (i.e. Compare_value) to whether the value stored in dest address is equal. If they are equal, the value of exchange_value is written to the address pointed to by dest. If not, store the dest address into eAX.

The output is “=a” (exchange_value), which writes the value stored in eAX to the exchange_value variable.

One, foreword

Second, the CAS

Third, CAS underlying implementation

3.1, the Unsafe

3.2 Native implementation of Unsafe.compareAndXXX

3.3, Unsafe_CompareAndSwapInt

3.4 understanding of embedded assembly

Related Posts

Webgo: A Web framework similar to Gin

Chapter 14: Handwritten RPC, in-depth understanding of the whole RPC communication

Number of real-time warehouse | Flink1.11 based SQL build a number of real-time warehouse exploration practice