Basic Principles of CAS

concept

CAS stands for compace-and-swap, which is a CPU concurrency primitive

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

The CAS concurrency primitive is the various methods of the Sun.misc. Unsafe class in the Java language. Call the UnSafe methods of CAS of class, the JVM will help us realize the CAS assembly instruction, this is a completely dependent on the function of the hardware, through its atomic operation is achieved, again, because the CAS is a kind of system primitives, primitive belong to the category of operating system used, consists of a number of instructions, is used to accomplish a function of a process, In addition, the execution of the primitive must be continuous and cannot be interrupted during execution. In other words, CAS is an atomic CPU instruction and does not cause so-called data inconsistencies. In other words, CAS is thread safe.

Code using

An instance is first created by calling AtomicInteger and initialized to 5

// Create an atom class AtomicInteger AtomicInteger = new AtomicInteger(5);Copy the code

We then call the CAS method in an attempt to update it to 2019. There are two parameters, one is 5, which represents the expected value, and the second is the value we want to update

atomicInteger.compareAndSet(5, 2019)
Copy the code

Then a method is used again, again changing the value to 1024

atomicInteger.compareAndSet(5, 1024)
Copy the code

The complete code is as follows:

/** * CASDemo ** compareAndSet ** @author: @create: Public class CASDemo {public static void main(String[] args) {// Create an AtomicInteger class atomicInteger = new AtomicInteger(5); * if three seconds ago, I expect 5, so I expect 5, Then I need to update into 2019 * / System. Out. The println (atomicInteger.com pareAndSet (5, 2019) + "\ t current data:" + atomicInteger. The get ()); System.out.println(atomicInteger.compareAndSet(5, 1024) + "\t current data: " + atomicInteger.get()); }}Copy the code

The result of executing the above code is

This is because when we execute the first one, the expected value and the original value are met, so the change is successful, but after the second one, the main memory value has been changed to 2019, which does not meet the expected value, so the return false, this time write failed

This is similar to the SVN or Git version number. If no one has changed it, it can be submitted normally. Otherwise, you need to pull down the code first, merge the code, and then submit

Basic Principles of CAS

First of all, we first take a look at atomicInteger. GetAndIncrement () method of the source code

As you can see, the underlying layer calls the getAndAddInt method of the unsafe class

1, the unsafe

Unsafe is the core CAS class. Since Java methods cannot access the underlying system directly, they need to access it through Native methods. Unsafe is a backdoor for manipulating specific in-memory data. The Unsafe class exists in the Sun.misc package, and its internal method operations can manipulate memory directly like Pointers to C, because the execution of CAS operations in Java depends on the Unsafe class’s methods.

Note that all methods in the Unsafe class are native, meaning that methods in the Unsafe class call directly on the underlying operating system resources to perform their tasks

Why does an atomically modified wrapper class have to rely on the underlying unsafe class to ensure atomicity

2. Variable valueOffset

Represents the address offset in memory for the variable value, as Unsafe is the address for retrieving data.

From here we can see that by valueOffset, we get the value directly from the memory address, and then increment it by one

3. The variable value is volatile

Memory visibility between multiple threads is guaranteed

Var5: we copy the value from main memory to working memory (each time we get the latest value from main memory to our own local memory, and then execute compareAndSwapInt() to compare the value with main memory. Since threads cannot bypass the cache and operate directly on main memory, they need to perform a comparison before performing the increment operation.

So when you do that, you have to compare the values in the working memory with the values in the main memory

Assuming that compareAndSwapInt returns false, the while method is executed until the expected value is the same as the real value

  • Val1: AtomicInteger object itself

  • Var2: This object is worth referencing the address

  • Var4: Quantity to be changed

  • Var5: The true value in memory found with var1 and var2

    • Compare the current value of the object to VAR5
    • If the same, update var5 + var4 and return true
    • If it’s different, keep evaluating it and compare it again until the update is done

In this case, CAS is used instead of synchronized, which improves concurrency and achieves consistency. This is because each thread enters the do while loop, and then continuously obtains the value in memory to determine whether it is the latest, and then performs the update operation.

Suppose thread A and thread B perform getAndInt at the same time (running on different cpus)

  1. The original value of AtomicInteger is 3, that is, the value of AtomicInteger in the main memory is 3. According to the JMM model, thread A and thread B each hold A copy of value 3, which is stored in their respective working memory
  2. Thread A gets value 3 by getIntVolatile(var1, var2). Thread A is suspended.
  3. Thread B uses getIntVolatile(var1, var2) to obtain a value of 3. Thread B uses compareAndSwapInt (var1, var2) to obtain a value of 3
  4. Thread A performs the CAS method, and finds that the number 3 in its hand is inconsistent with the number 4 in its main memory, indicating that the value has been modified by another thread first. Therefore, thread A fails to modify this time, and can only read it again, that is, to execute the do while
  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.

Unsafe class + CAS idea: Spin, self-rotation

The underlying assembly

The compareAndSwapInt in the Unsafe class is a native method, the implementation of which is in the Unsafe. CPP

  • 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

CAS shortcomings

CAS is unlocked and guaranteed to be one-time, but requires multiple comparisons

  • The loop takes a long time and is expensive (because the do while is performed, if the loop is not successful, the worst case is that a thread keeps fetching different values than expected, so it will loop forever).

  • Atomic operations of only one shared variable are guaranteed

    • When performing operations on a shared variable, we can loop CAS to ensure atomic operations
    • However, in the case of multiple shared variable operations, the loop CAS cannot guarantee the atomicity of the operation, so only locks can be used to ensure atomicity

  • The ABA problem?

ABA problem

.

conclusion

CAS

CAS is a compareAndSwap. The CAS compares the value in the current working memory with the value in the main physical memory. If the value is the same, the CAS compares the value in the current working memory with the value in the main physical memory

The CAS application

CAS has three operands, the memory value V, the old expected value A, and the updated value B to be modified. Change the memory value V to B if and only if the expected value A is the same as the memory value V, or do nothing

\