synchronized
synchronized
volatile
volatile

Synchronized exclusive locks are pessimistic locks, which assume that there will be a conflict, so locking is useful, and optimistic locks, which means assuming that there is no conflict, so I can just do something, and if there is a conflict, I’ll try again until I succeed. The most common form of optimistic locking is CAS.

When we read the source code for the classes under the Concurrent package, we find that both the AQS inside ReenterLock and various Atomic classes have CAS applied internally. The most common case is i++, which we encounter in Concurrent programming. The traditional approach would certainly be to add the synchronized keyword to the method:

public class Test {

    public volatile int i;

    public synchronized void add() { i++; }}Copy the code

But this approach is probably a little bit worse, and we can also use AtomicInteger to guarantee that I atoms are ++.

public class Test {

    public AtomicInteger i;

    public void add() { i.getAndIncrement(); }}Copy the code

Let’s look inside getAndIncrement:

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}
Copy the code

Dig deeper into getAndAddInt():

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

Here we see the function compareAndSwapInt, which is where the abbreviation CAS comes from. So what does this function do?

First of all, we find this before compareAndSwapInt, so what class does it belong to? Let’s look at getAndAddInt, before unsafe. Here we go into the Unsafe class. Here’s an explanation for the Unsafe class. Using the definition of AtomicInteger:

public class AtomicInteger extends Number implements java.io.Serializable { private static final long serialVersionUID =  6214790243416807050L; // setup to use Unsafe.compareAndSwapIntfor updates
    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; .Copy the code

In the AtomicInteger data definition section, we can see that the actual stored value is in value, in addition to getting the unsafe instance and defining a valueOffset. Now, if you look at the static block, for those of you who know the class loading process, the static block is loaded when the class is loaded, it’s initialized first, and that’s when we call the objectFieldOffset for unsafe to get the offset of value from the Atomic class file, So valueOffset is just the offset of value.

Going back to that function getAndAddInt, let’s see what var5 is getting, by calling getIntVolatile(var1, var2), which is a native method, and I’m going to do it in the JDK source code, but it’s actually getting var1, Value at the offset of VAR2. Var1 is AtomicInteger, and var2 is the valueOffset we mentioned earlier, so we get the value from memory at the current valueOffset.

CompareAndSwapInt (obj, offset, expect, update) compareAndSwapInt (obj, offset, expect, update) If value in obj is equal to Expect, it proves that no other thread has changed the variable, update it to update, and if CAS doesn’t succeed, then spin the CAS operation, which at first looks like two steps. In JNI, this is actually done by means of a CPU instruction. So it’s still atomic.

Underlying CAS Principles

The underlying CAS implementation uses JNI to call C code. If you have Hotspot source code, you can find its implementation in unsafe.cpp:

Static JNINativeMethod methods_15[] = {// {CC"compareAndSwapInt",  CC"("OBJ"J""I""I"")Z",      FN_PTR(Unsafe_CompareAndSwapInt)},
    {CC"compareAndSwapLong", CC"("OBJ"J""J""J"")Z"FN_PTR(Unsafe_CompareAndSwapLong)}, // omit a bunch of code... };Copy the code

We can see that the compareAndSwapInt implementation is inside Unsafe_CompareAndSwapInt, and we can go further into Unsafe_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

Atomic:: CMPXCHG (x, addr, e) is called with x as the value to be updated and e as the value of the original memory. CMPXCHG can be seen in the code based on various platforms, here I choose the Linux X86 platform source analysis:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  int mp = os::is_MP();
  __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

This is a small assembly, __asm__ means ASM assembly, and __volatile__ disables compiler optimization

// Adding a lock prefix to an instruction on MP machine
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1:"
Copy the code

OS ::is_MP determines whether the current system is a multi-core system, and if so, locks the bus, so that other processors on the same chip cannot access memory through the bus temporarily, ensuring the atomicity of the instruction in a multi-processor environment.

Before formally interpreting the assembly, let’s look at the basic format of the embedded assembly:

asm ( assembler template
    : output operands                  /* optional */
    : input operands                   /* optional */
    : list of clobbered registers      /* optional */
    );
Copy the code

  • Template is CMPXCHGL %1, and (%3) represents the assembly template

  • Output operands indicates the output operands. = A corresponds to the EAX register

  • Input operand indicates the input parameter, %1 is exchange_value, %3 is dest, %4 is MP, r is any register, a or EAX

  • List of clobbered registers are additional arguments. Cc means that the compiler’s execution of CMPXCHGL will affect the flag register. Memory tells the compiler to re-read the latest value of a variable from memory, which implements a volatile feel.

CMPXCHGL exchange_value,dest, and compare_value are not used. The end l of CMPXCHGL means that the operand is of length 4, which we already know. By default, CMPXCHGL compares the values of the EAX registers, namely compare_value and exchange_value. If they are equal, it assigns dest to Exchange_value; otherwise, it assigns Exchange_value to eAX. For specific assembly instructions, see the Intel manual CMPXCHG

Finally, the JDK implements AtomicInteger’s CAS operation atomicness through the SUPPORT of the CPU’s CMPXCHGL directive.

The problem of the CAS

  1. ABA problem

CAS needs to check whether the value has changed when it operates on the value, and update it if it hasn’t changed, but if A value is A, then B, and then A, then the CAS check will find that the value has not changed, but it has changed. This is the ABA problem with CAS. A common solution is to use version numbers. Append the version number to the variable and add it by one each time the variable is updated, so that a-b-a becomes 1A-2B-3a. An AtomicStampedReference class is currently available in the JDK’s atomic package to address ABA issues. The compareAndSet method of this class first checks to see if the current reference equals the expected reference, and if the current flag equals the expected flag, and if all are equal, sets the reference and flag values atomically to the given update value.

  1. Long cycle time and high overhead

We said above that if the CAS is unsuccessful, it will spin in place, and if it spins for a long time, it will cause a significant execution overhead to the CPU.