The preface

Due to the recent high concurrency problems encountered in the project, and my knowledge of high concurrency and multi-threading is relatively weak, especially the basic, so I want to systematically learn about it, and may publish a series of JUC articles and summaries in the future, as well as prepare for the enterprise high concurrency projects.

The summary of this series of articles can be roughly divided into three parts:

  1. Theory (concept);
  2. Practice (code proof);
  3. Summary (experience and application scenarios);

I’m going to say this in advance in case you get lost looking at it.

Outline of the CAS

First of all, the figure below is the outline of this paper. That is to say, before reading this paper, you need to understand what this paper is about, have a general view, and then subdivide it to the content level.

The CAS theory

See AtomicInteger. GetAndIncrement () method, found its not synchronized also implements the synchronization. Why is that?

What is CAS?

CAS stands for compace-and-swap, And it is a CPU concurrency primitive.

As the name suggests, compare and exchange, it’s an important idea of synchronization. If the main memory value is as expected, change it, otherwise retry until it is.

The execution of primitives must be continuous and cannot be interrupted in the execution process, that is to say, CAS is an atomic CPU instruction and will not cause the so-called data inconsistency problem.

Its function is to determine whether a value at a location in memory is the expected value and, if so, change it to the new value. This process is atomic.

Let’s look at a piece of code:

public class CasDemo {
  public static void main(String[] args) {
    / / initial value
    AtomicInteger integer = new AtomicInteger(5);
    // Compare and replace
    boolean flag = integer.compareAndSet(5.10);
    boolean flag2 = integer.compareAndSet(5.15);

    System.out.println("Optional and replace \t"+flag +"\t changed to:"+integer.get());
    System.out.println("Optional and replace \t"+flag2 +"\t changed to:"+integer.get()); }}Copy the code

Can you guess the answer?

Whether to select and replacetrueThe changed value is:10Whether to select and replacefalseThe changed value is:10
Copy the code

First change, expected value 5, main memory 5, successful change, 10.

The second change, expected value 5, main memory 10, failed to change.

The CAS theory

After reviewing the source code, two key points can be summarized:

  1. Spin;
  2. The unsafe class.

When the compareAndSet method is clicked:

// Inside the AtomicInteger class
public final boolean compareAndSet(int expect, int update) {
  return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
Copy the code

Volatile int Value and private static final Unsafe Unsafe are the two most important parameters that AtomicInteger maintains internally. (Note that value is volatile)

Also, the private static final Long valueOffset variable, which represents the address of the variable’s memory offset, is what an Unsafe variable looks for in memory.

The variable value is volatile, which ensures memory visibility across multiple threads.

// Inside the AtomicInteger class
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

We then find the broadening class core method via compareAndSwapInt:

/ / the unsafe inner classes
public final int getAndAddInt(Object var1, long var2, int var4) {
  intvar5; do { var5 = this.getIntVolatile(var1, var2); } while(! this.compareAndSwapInt(var1, var2, var5, var5 + var4));return var5;
}
Copy the code

AtomicInteger.com pareAndSwapInt () call the Unsafe.com pareAndSwapInt () method. Most of the methods of the Unsafe class are native, used to manipulate memory from the ground level, like the C language.

The method var1 and var2 are snapshots of the value var5 in main memory based on the object and offset. The compareAndSwapInt method then uses var1 and var2 to get the actual value of the current main memory. If the actual value is equal to the snapshot value, the main memory value is updated to var5+ VAR4. If not, the loop will keep taking snapshots and comparing until the actual value is equal to the snapshot value.

Let’s say I have thread A and thread B

  1. They all started off with a copy of 3 from main memory;
  2. Thread A is runningvar5=this.getIntVolatile, namely var5 = 3. Thread A is suspended;
  3. Thread B changes the value to 4. Thread B completes execution, and the change is immediately visible because it volatile.
  4. Thread A wakes up and executesthis.compareAndSwapInt()Method, the main memory value is not equal to snapshot value 3, so continue the loop,againFrom main memory.
  5. Thread A retrieves value, and since value is volatile, thread A always sees changes made to it by other threads, and thread A continues to compareAndSwapInt until it succeeds.

ABA problem

The so-called ABA problem, in fact, with the most easy-to-understand words to sum up is the leopard cat for prince

The cycle of comparison and exchange, there is a time difference, and this time difference can bring unexpected problems.

Let’s say we have two threads A and B:

  1. They all started off with a copy of 3 from main memory;
  2. Thread A is runningvar5=this.getIntVolatile, namely var5 = 3. Thread A is suspended;
  3. B changes the original value to 4, and thread B completes execution.
  4. And then B thinks it’s wrong, and then changes it back to 3;
  5. Thread A wakes up and executesthis.compareAndSwapInt()The main memory value is equal to snapshot value 3, (But they didn’t know that B had changed it), the modification is successful.

Although the CAS operation of thread A succeeds, it does not mean there is no problem. Some requirements, such as CAS, focus only on heads and tails and accept as long as they are consistent. But for some requirements, it’s also about the process, and nothing can change in the middle. This leads to the AtomicReference.

AtomicReference AtomicReference

AtomicInteger performs atomic operations on integers. What if it’s a POJO? This POJO can be wrapped with an AtomicReference to atomize its operations.

User user1 = new User("Jack".25);
User user2 = new User("Lucy".21);
AtomicReference<User> atomicReference = new AtomicReference<>();
atomicReference.set(user1);
System.out.println(atomicReference.compareAndSet(user1,user2)); // true
System.out.println(atomicReference.compareAndSet(user1,user2)); //false
Copy the code

The essence is to compare whether the addresses of two objects are equal.

Atom Stampedreference and ABA problem solving

The ABA problem can be solved using the AtomicStampedReference class. This class maintains a “version number” Stamp, which is similar to optimistic lock.

When the CAS operation is performed, not only the current value is compared, but also the version number. Update operations are performed only if both are equal.

AtomicStampedReference.compareAndSet(expectedReference,newReference,oldStamp,newStamp);
Copy the code

CAS summary

No technology is perfect, of course, CAS has its drawbacks:

CAS is actually a kind of spin lock,

  1. It’s going to be a lot of overhead.
  2. Atomic operations can only be guaranteed for one variable, and multiple variables are still locked.
  3. The ABA problem (atom stampedreference can be solved) is introduced.

And its use scenario is suitable for some concurrent volume is not high, the thread contention is less, the lock is too heavy. However, once the thread conflict is serious, the loop time is too long, which brings a lot of overhead to the CPU.