The best time for Monkey to plant trees was ten years ago, followed by now. Independently developed Java learning platform, PMP brush small program. Currently major in Java, Multi-threading, SpringBoot, SpringCloud, K8S. This public account is not limited to sharing technology, but also to share the use of tools, life perception, reading summary.

On a dark and windy night, a frustrated programmer was frantically typing on the keyboard when his wife glanced at the computer desktop with a pair of sleepy eyes. The following conversation ensued:

Wife: what is the meaning of this drawing, how there are triangles, quadrilateral?

Me: I’m drawing the principle of CAS, or shall I tell you again?

Wife: Good ah!

Case: A sees a triangle building block and thinks it is not good looking and wants to replace it with a pentagon, but B wants to replace it with a quadrilateral. (Prerequisite, can only be replaced once)

Comparing with the thief, A came up with an idea: “I will take the block to another room to replace it and lock it so that it won’t be disturbed by others.” (synchronized)

“The room is locked. I can’t get in. I can’t see what the blocks look like. (Locked, so not accessible)”

So a and B came up with another idea: whoever grabbed the blocks first would replace them first, and if the blocks changed shape, no one else would be allowed to replace them again. (Compare and replace CAS)

So they started grabbing triangles:

  • Scenario 1: A grabs and replaces it with a pentagon, but B cannot

    • If a gets it first and the block is still triangular, the triangle is replaced with a pentagon.

    • When the second player grabs the block, the building block has become a pentagon, and the second player has no chance to replace it (because a and B have a chance to replace each other).

  • Scenario 2: User B fails to replace the disk, and User A succeeds in replacing the disk

    • Suppose b grabs the triangle first, but suddenly feels that the triangle also looks good, does not replace, puts down the block and walks away.

    • Then a grabbed the building block, which was still triangular, and realized that B had not replaced the triangle, so he replaced the triangle with a pentagon.

  • Scenario 3: B grabs, replaced with triangle, A replaced with pentagon, ABA problem

    • If b gets it first and thinks the triangle is old, he replaces it with another one that looks exactly the same, but the block is newer.
    • Then a grabbed the building block, which was still triangular, and realized that B had not replaced the triangle, so he replaced the triangle with a pentagon.

Wife after hearing, feel these three kinds of scenes are too simple, the original computer is so simple, early know I also go to learn computer…

Was ruthlessly despised, fortunately wife incredibly understood, do not know everybody understood?

Back to the basics, let’s talk about Java CAS in computer terms

Introduction to Java CAS

** Full name of CAS: ** compare-and-swap. Compares whether the current value of a variable is consistent with its previous value, if so, replace it, otherwise not.

**CAS is used to atomically update variable values to ensure thread-safety.

**CAS instruction: ** requires three operands, the current value of the variable (V), the old expected value (A), and the new value (B) to be set.

** The CAS instruction execution condition: ** The processor sets V=B if and only if V=A, otherwise no update will be performed.

**CAS returns the previous value of **V.

**CAS processing: ** atomic operation, execution will not be interrupted by other threads, thread safety.

**CAS concurrency primitives: ** The various methods of the Sun.misc. Unsafe class in the Java language. Calling the CAS method in the UnSafe class, the JVM implements the CAS assembly instruction for us, a hardware-dependent feature that implements atomic operations. 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, and carry out must be continuous, primitive is not permitted to interrupt during execution, so the CAS is a CPU atomic instruction, not so-called data inconsistency problem, So CAS is thread-safe.

Two, can you write a few lines of code to explain?

In our previous article on volatile, we saw how to use the AtomicInteger class to solve the non-atomic problem of volatile by ensuring that multiple threads perform num++, resulting in the same result as a single thread, with an output of 20000.

Again, we’ll use AtomicInteger.

First define the atomicInteger variable to have an initial value equal to 10, and set the value in main memory to 10

AtomicInteger atomicInteger = new AtomicInteger(10);
Copy the code

The CAS method of atomicInteger is then called to compare whether the value of the current variable atomicInteger is 10 and, if so, set the value of the variable to 20

atomicInteger.compareAndSet(10.20);
Copy the code

AtomicInteger is updated to 20

When we call the CAS method of atomicInteger again, we first compare the value of the current variable atomicInteger to 10, and if so, set the value of the variable to 30

atomicInteger.compareAndSet(10.30);
Copy the code

Setting atomicInteger failed because the current value of atomicInteger is 20 and the comparison value is 10, so the comparison is not equal and therefore cannot be updated.

The complete code is as follows:

package com.jackson0714.passjava.threads;
import java.util.concurrent.atomic.AtomicInteger;
/** demo CAS compareAndSet comparison and exchange *@author: Wukong chat structure *@create: the 2020-08-17 * /
public class CASDemo {
    public static void  main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger(10);
        Boolean result1 = atomicInteger.compareAndSet(10.20);
        System.out.printf("Current atomicInteger variable value :%d comparison result %s\r\n", atomicInteger.get(), result1);
        Boolean result2 = atomicInteger.compareAndSet(10.30);
        System.out.printf("Current atomicInteger variable value :%d, compare result %s\n", atomicInteger.get(), result2); }}Copy the code

The result is as follows:

The current atomicInteger variable value:20Compare the resultstrueThe current atomicInteger variable value:20, comparison resultsfalse
Copy the code

So let’s look at the schematic and see how the code works

  • Step 1: Thread 1 and thread 2 both have copies of variables in main memory, with values equal to 10

  • Step 2: Thread 1 wants to update the value to 20 by comparing the value of the variable in working memory with the value of the variable in main memory, which is equal to 10, so it can replace the value in main memory with 20

  • Step 3: Thread 1 replaces the value in main memory with 20 and updates the copy in working memory in thread 1 to 20

  • Step 4: Thread 2 wants to update the variable to 30 by comparing the value in thread 2’s working memory with the main memory. 10 is not equal to 20, so it cannot be updated

  • Step 5: Thread 2 updates the copy of working memory to be consistent with main memory: 20

Great drawing!

If someone commits to the Develop branch and someone else wants to change the code in that branch, pull the Develop branch first to avoid committing conflicts.

Iii. Can you explain the underlying principle of CAS?

The source code to debug

Here we use the getAndIncrement() method of atomicInteger, which involves the principle of comparison and replacement.

The following is an example:

public static void  main(String[] args) throws InterruptedException {
    AtomicInteger atomicInteger = new AtomicInteger(10);
    Thread.sleep(100);

    new Thread(() -> {
        atomicInteger.getAndIncrement();
    }, "aaa").start();

    atomicInteger.getAndIncrement();
}
Copy the code

  • (1) The multithreaded debugging mode of IDEA needs to be enabled first

  • (2) We break the point to line 17. The main thread has reached this line, but the child thread AAA has not yet executed the increment operation.

The unsafe getAndIncrement method calls the getAndAddInt method,

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

  • (3) Set a breakpoint on line 361 of the source getAndAddInt method, and execute the main line to line 361 first

    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

    Delimit key point!!

    • Var1: The current object, the atomicInteger we defined
    • Var2: memory offset of the current object
    • Var4: the current increment is small. The default value is 1 and cannot be set to any other value
    • Var5: The value of the current variable
    • this.getIntVolatile(var1, var2): Gets the value of the main memory variable based on the current object var1 and its memory offset var2, assigns the value to var5, and stores a copy of var5 in the main thread’s working memory

  • (4) A breakpoint is set at line 362, and the main thread continues one step

    • Var5 fetches a value of 10 in main memory

  • (5) Switch to child thread AAA, again at 361 breakpoint, has not fetched the main memory value

  • (6) The child thread AAA continues to execute one step and obtains the value of VAR5 equal to 10

(7) Switch to the main thread for comparison and replacement

this.compareAndSwapInt(var1, var2, var5, var5 + var4)
Copy the code

Var5 =10, and the value obtained from var1 and var2 is also 10, since no other thread has modified the variable. The source of compareAndSwapInt will be discussed later.

Therefore, after comparison, it is found that the variable has not been modified by other threads, so it can be replaced with var5+ VAR4 =11. The value of the variable is changed to 11, that is, it increases by 1. This line of code returns true (increment succeeded) and exits the do while loop. The return value is the value 10 before the variable is updated.

(8) Switch to sub-thread AAA for comparison and auto-increment

If var5=10 and var5=10 and var5=10 and var5=10 and var5=10 and var5= 11 and var5=10 and var5=10 and var5=10 and var5=10 and var5=10 and var5=10 and var5= 11

  • (9) Sub-thread AAA continues to execute, and retrieves var=11

  • (10) The child thread AAA continues to execute, compare and replace, and the result is true

    Since var5=11, the variable value in main memory is also equal to 11, so it is equal after comparison and can be replaced by var5+ VAR4, the result is 12, that is, the increment of 1. Exit the loop and return the value var5=11 before the variable was updated.

At this point, the entire atomic increment logic of the getAndIncrement method is debugged. So the conclusion can be drawn:

If other threads modify the value of the main memory, the current thread cannot increment the value of the main memory. It needs to obtain the value of the main memory again, and then check whether it is the same as the value of the main memory again, and repeat.

What’s wrong with CAS?

I don’t know if you noticed that aaa threads can loop multiple times, because other threads can change the value of the main memory, but AAA threads still get the old data, there will be a loop, which will bring performance costs to the CPU. This is the spin.

  • Frequent spin, long cycle time, high overhead(Because it’s doing a do while, if it’s not successful and keeps looping, the worst case is that a thread keeps fetching different values than expected, and it keeps looping forever.)
  • Only guaranteeaAtomic operations that share variables
    • When theaWhen shared variables perform operations, we can loop CAS to ensure atomic operations
    • But formultipleWhen a shared variable operation is performed, the loop CAS cannot guarantee the atomicity of the operation, so only locks can be used to ensure atomicity
  • Leads to ABA questions (with Easter eggs)

Five, the summary

This paper begins with a conversation with his wife, telling his wife about CAS in popular language, which also involves concurrent locking. Then debug the underlying code step by step to deeply understand the principle of CAS.

Every picture is beautiful! Share + watch, guys!

Easter egg: there is an ABA problem not to tell everyone, in addition, how here is not AAB (tractor), AAA (golden flower)?

I spent a lot of time writing technical articles in the first three days of this week. I stayed up less and went to sleep. We will talk about ABA in the next period. Your support is my biggest motivation to write ~

Wukong, a coder trying to become stronger! I’m gonna be super Saiyan!

In addition, you can search “Wukong chat architecture” or PassJava666 to make progress together!

On my GitHub homepage, pay attention to my Spring Cloud actual combat project “Jia Bi Pass”.