Real interview question: Please talk about the CAS mechanism in concurrency

I don’t know if students have ever experienced such an interview:

Interviewer: Please talk about the CAS mechanism in concurrency
Xiao Ming : Well, CAS, right? I seem to have heard of it... Let me think about it (my brain is thinking rapidly)

2 minutes have passed...
The air is deathly still.. .

The interviewer couldn't sit still and cleared his throat: Ahem... Well, can you tell me briefly?
Xiao Minghanhanyixiao: Hehe, I seem to have forgotten...
Interviewer: Oh, it doesn’t matter. That’s it for today’s interview. You go back and wait. Let me know
Xiao Ming left dejectedly...

Don't laugh, Xiao Ming is actually the shadow of many people, and there are many classmates who made awkward conversations during the interview process. Of course, I am included. In fact, this reflects a very cruel reality: The foundation is not solid!

So here comes the question, how to defeat the interviewer during the interview and be as stable as a rock?

Learn! What's the use of just talking? You have to learn, you have to read the books you buy, and you have to follow the courses you buy. Don't just play games and follow TV dramas. If you want to become stronger, you have to be bald!

It is now 0:08 Beijing time. I am writing an article in code. How about you?

A small example to talk about what thread safety is

Concurrency is The foundation of Java programming. In our daily work, we often deal with concurrency. Of course, this is also the focus of the interview. In concurrent programming, the most mentioned concept is thread safety. Let’s first look at a piece of code to see what will happen after running:

In the

public class Test {
    private static int inc = 0;

    public static void main(String[] args) {
     // 设置栅栏，保证主线程能获取到程序各个线程全部执行完之后的值
        CountDownLatch countDownLatch = new CountDownLatch(1000000);
        // 设置100个线程同时执行
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
             // 循环10000次，对inc实现 +1 操作
                for (int j = 0; j < 10000; j++) {
                    inc++;
                    countDownLatch.countDown();
                }
            }).start();
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        // 运行完毕，期望获取的结果是 1000000
        System.out.println("执行完毕，inc的值为：" + inc);
    }
}

program, I created 100 threads. In each thread, the shared variable inc is accumulated 10,000 times. If it is executed synchronously, the final value of inc should be 1,000,000, but We know that in multi-threading, programs are executed concurrently, which means that different threads may read the same value from the main memory at the same time, such as this scenario:

• Thread A At a certain moment, the inc value of the main memory was read as 1000. In its own working memory 1, inc became 1001;
• Thread B read it at the same moment. The inc value of the main memory is 1000, and it also sets the inc value of 1 in its own working memory, and inc becomes 1001;
• They want to write the inc value to the main memory. There is no synchronization control, so they may write 1001 of their working memory to the main memory;
• Then it is obvious that the main memory is performing two 1 operations. Finally, the actual result was only 1 once and became 1001.

This is a very typical problem caused by multi-threads concurrently modifying shared variables. Obviously, its running results are as we analyzed, and in some cases it cannot be achieved. 1000000:

执行完毕，inc的值为：962370

Some people say that this problem can be solved by using the volatile keyword, because volatile can guarantee visibility between threads, which means that threads can read the latest data in main memory. variable value and then operate on it.

Note that volatile can only guarantee the thread's visibility, but not the atomicity of the thread's operation. Although the thread has read the latest inc of the main memory value, but reading,inc 1,writing to main memory is a three-step operation, so volatile cannot solve the problem of thread safety of shared variables.

So how to solve this problem? Java provides us with the following solutions.

几种保证线程安全的方案

1. 通过synchronized关键字实现同步：

public class Test {
    private static int inc = 0;

    public static void main(String[] args) {
        // 设置栅栏，保证主线程能获取到程序各个线程全部执行完之后的值
        CountDownLatch countDownLatch = new CountDownLatch(1000000);
        // 设置100个线程同时执行
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                // 循环10000次，对inc实现 +1 操作
                for (int j = 0; j < 10000; j++) {
                 // 设置同步机制，让inc按照顺序执行
                    synchronized (Test.class) {
                        inc++;
                    }

                    countDownLatch.countDown();
                }
            }).start();
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("执行完毕，inc的值为：" + inc);
    }
}

在上面的代码中，我们给 inc ++ 外面加了一层代码，使用 synchronized 设置类锁，保证了代码的同步执行，这是一种基于JVM自身的机制来保障线程的安全性，如果在并发量比较大的情况下，synchronized 会升级为重量级的锁，效率很低。synchronized无法获取当前线程的锁状态，发生异常的情况下会自动解锁，但是如果线程发生阻塞，它是不会释放锁的

执行结果：

执行完毕，inc的值为：1000000

可以看到，这种方式是可以保证线程安全的。

2. 通过Lock锁实现同步

public class Test {
    private static int inc = 0;
    private static Lock lock = new ReentrantLock();

    public static void main(String[] args) {
        // 设置栅栏，保证主线程能获取到程序各个线程全部执行完之后的值
        CountDownLatch countDownLatch = new CountDownLatch(1000000);

        // 设置100个线程同时执行
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                // 循环10000次，对inc实现 +1 操作
                for (int j = 0; j < 10000; j++) {
                 // 设置锁
                    lock.lock();
                    try {
                        inc++;
                    } finally {
                     // 解锁
                        lock.unlock();
                    }
                    countDownLatch.countDown();
                }
            }).start();
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("执行完毕，inc的值为：" + inc);
    }
}

ReentrantLock的底层是通过AQS + CAS来实现的，在并发量比较小的情况下，它的性能不如 synchronized，但是随着并发量的增大，它的性能会越来越好，达到一定量级会完全碾压synchronized。并且Lock是可以尝试获取锁的，它通过代码手动去控制解锁，这点需要格外注意。

执行结果：

执行完毕，inc的值为：1000000

3. 使用 Atomic 原子类

public class Test {
    private static AtomicInteger inc = new AtomicInteger();

    public static void main(String[] args) {
        // 设置栅栏，保证主线程能获取到程序各个线程全部执行完之后的值
        CountDownLatch countDownLatch = new CountDownLatch(1000000);

        // 设置100个线程同时执行
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                // 循环10000次，对inc实现 +1 操作
                for (int j = 0; j < 10000; j++) {
                    inc.getAndAdd(1);
                    countDownLatch.countDown();
                }
            }).start();
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("执行完毕，inc的值为：" + inc.get());
    }
}

AtomicInteger 底层是基于 CAS 的乐观锁实现的，CAS是一种无锁技术，相对于前面的方案，它的效率更高一些，在下面会详细介绍。

执行结果：

执行完毕，inc的值为：1000000

4. 使用 LongAdder 原子类

public class Test {
    private static LongAdder inc = new LongAdder();

    public static void main(String[] args) {
        // 设置栅栏，保证主线程能获取到程序各个线程全部执行完之后的值
        CountDownLatch countDownLatch = new CountDownLatch(1000000);

        // 设置100个线程同时执行
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                // 循环10000次，对inc实现 +1 操作
                for (int j = 0; j < 10000; j++) {
                    inc.increment();
                    countDownLatch.countDown();
                }
            }).start();
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("执行完毕，inc的值为：" + inc.intValue());
    }
}

LongAdder 原子类在 JDK1.8 中新增的类，其底层也是基于 CAS 机制实现的。适合于高并发场景下，特别是写大于读的场景，相较于 AtomicInteger、AtomicLong 性能更好，代价是消耗更多的空间，以空间换时间。

执行结果：

执行完毕，inc的值为：1000000

CAS理论

讲到现在，终于我们今天的主角要登场了，她就是CAS。

CAS的意思是比较与交换（Compare And Swap），它是乐观锁的一种实现机制。

什么是乐观锁？通俗的来说就是它比较乐观，每次在修改变量的值之前不认为别的线程会修改变量，每次都会尝试去获得锁，如果获取失败了，它也会一直等待，直到获取锁为止。说白了，它就是打不死的小强。

而悲观锁呢，顾名思义，就比较悲观了，每次在修改变量前都会认为别人会动这个变量，所以它会把变量锁起来，独占，直到自己修改完毕才会释放锁。说白了，就是比较自私，把好东西藏起来自己偷偷享用，完事了再拿出来给别人。像之前的synchronized关键字就是悲观锁的一种实现。

CAS是一种无锁原子算法，它的操作包括三个操作数：需要读写的内存位置(V)、预期原值(A)、新值(B)。仅当 V值等于A值时，才会将V的值设为B，如果V值和A值不同，则说明已经有其他线程做了更新，则当前线程继续循环等待。最后，CAS 返回当前V的真实值。CAS 操作时抱着乐观的态度进行的，它总是认为自己可以成功完成操作。

CAS的实现

在Java中，JUC的atomic包下提供了大量基于CAS实现的原子类：

我们以AtomicInteger来举例说明。

AtomicInteger类内部通过一个Unsafe类型的静态不可变的变量unsafe来引用Unsafe的实例。

 // setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();

然后，AtomicInteger类用value保存自身的数值，并用get()方法对外提供。注意，它的value是使用volatile修饰的，保证了线程的可见性。

private volatile int value;

/**
 * Creates a new AtomicInteger with the given initial value.
 *
 * @param initialValue the initial value
 */
public AtomicInteger(int initialValue) {
    value = initialValue;
}

/**
 * Gets the current value.
 *
 * @return the current value
 */
public final int get() {
    return value;
}

一路跟踪incrementAndGet方法到的末尾可以看到是一个native的方法：

/**
 * Atomically increments by one the current value.
 *
 * @return the updated value
 */
public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

//  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;
}

// compareAndSet方法
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

可以看到其实incrementAndGet内部的原理就是通过compareAndSwapInt调用底层的机器指令不断比较内存旧值和期望的值，如果比较返回false就继续循环比较，如果返回true则将当前的新值赋给内存里的值，本次处理完毕。

由此我们知道，原子类实现的自增操作可以保证原子性的根本原因在于硬件（处理器）的相关指令支持。将语义上需要多步操作的行为通过一条指令来完成，CAS指令可以达到这个目的。

Disadvantages of CAS

• As an implementation of optimistic locking, when multi-threads compete for resources fiercely, multiple The thread will spin and wait, which will consume a certain amount of CPU resources.
• CAS will inevitably have ABA problems. For explanations and solutions to ABA problems, you can refer to my article: The interviewer asks you: Do you know what ABA problems are? ?
  
  

---

Okay, this is the end of this issue’s sharing about CAS. Concurrency, as the cornerstone of Java programming, is a very important knowledge point. If students have a weak grasp of this area, I hope that after reading the article, I can type the code by myself and think about what CAS is. What are the advantages and disadvantages, and what are the ways to implement them. Of course, concurrency is a very big concept. Here is just a tip, a small knowledge point, and some of my own learning experiences. If there is anything that is not explained properly or is wrong, please send me a private message to discuss it together, thank you!

I am programmer Qingge. This ends the interview questions shared here. I want to improve myself and advance to the next level. Students in the factory must pay attention to my official account: Java Study Guide, where I will take you to learn and summarize Java-related knowledge based on actual interviews every day, and help you expand your skills. stack to enhance personal strength. See you next time~

The above is the detailed content of Real interview question: Please talk about the CAS mechanism in concurrency. For more information, please follow other related articles on the PHP Chinese website!