64 Do You Know What CAS Is #

In this lesson, I will explain CAS.

Introduction to CAS #

CAS is actually a common topic in interviews because it is the underlying principle of atomic classes and optimistic locking. So when you go for an interview, you may often encounter questions like “Do you know what types of locks there are?” and you may answer “Pessimistic lock and optimistic lock”, then the next question is likely to be about the principle of optimistic lock, which is related to CAS. Of course, it may also continue to ask you about the application scenarios or disadvantages of CAS. In this lesson and the next two lessons, I will guide you on how to answer these questions.

First, let’s take a look at what CAS is. Its full name in English is Compare-And-Swap, which means “comparing and swapping” in Chinese. It is a concept, an algorithm.

In a multi-threaded environment, the execution order of various code segments cannot be determined. In order to ensure concurrency safety, we can use mutex locks. The characteristic of CAS is to avoid using mutex locks. When multiple threads use CAS to update the same variable at the same time, only one of the threads can successfully operate, while the other threads will fail to update. However, unlike synchronization mutex locks, the threads that fail to update are not blocked, but are informed that the operation failed due to competition, but they can try again.

CAS is widely used in the field of concurrent programming to achieve data exchange operations that are not interrupted, thus achieving lock-free thread safety.

Idea of CAS #

Most processors’ instructions implement CAS-related instructions. This instruction can complete the operation of “comparing and swapping”. It is precisely because this is a single (not multiple) CPU instruction that CAS-related instructions have atomicity. This combination operation will not be interrupted during execution, thus ensuring concurrency safety. Since this atomicity is guaranteed by the CPU, we programmers do not need to worry about it.

CAS has three operands: the memory value V, the expected value A, and the value to be modified B. The core idea of CAS is that the memory value is modified to B only when the expected value A is the same as the current memory value V.

Let’s describe this in more detail: CAS assumes in advance that the current memory value V should be equal to value A, and value A is often the memory value V read at the time. When executing CAS, if the current memory value V is exactly A, CAS will change the memory value V to value B. Value B is often calculated based on value A. If the execution of CAS finds that the current memory value V is not equal to value A, it means that during the calculation of B just now, the memory value has been modified by other threads. In this case, this CAS should not be modified again, to avoid errors caused by multiple simultaneous modifications. This is the main idea and process of CAS.

JDK uses these CAS instructions to implement concurrent data structures, such as AtomicInteger and other atomic classes.

The lock-free algorithm implemented using CAS is like negotiating with a very optimistic attitude during negotiations, being friendly to each other. If we fail to reach an agreement this time, we can try again. The idea of CAS is completely different from the idea of mutex locks. If it is a mutex lock, there is no mechanism for negotiation. Everyone will try to seize resources. If they succeed, they will firmly hold onto the resources until the operation is completed. Of course, both CAS and mutex locks can ensure concurrency safety. They are different means to achieve the same goal.

Example #

Next, let’s make the process of CAS clearer with diagrams and examples, as shown in the following figure:

Assume that there are two threads using two CPUs respectively, and they both want to use CAS to change the value on the right. Let’s start with thread 1, which uses CPU 1. Suppose it executes first and expects the current value to be 100 and wants to change it to 150. During the execution, it will check whether the current value is 100. It finds that it is indeed 100, so it can make the change. After the change, the value on the right will change from 100 to 150.

As shown in the above diagram, suppose it is now the turn for thread 2 to use CPU 2. It wants to change the value from 100 to 200, so it also expects the current value to be 100. However, the actual current value is 150, so it finds that the current value is not the expected value, so it does not really continue to change 100 to 200. In other words, the whole operation has no effect, and the CAS operation fails.

Of course, thread 2 can still perform other operations next, which depends on the business requirements, such as retrying, throwing an error, or simply skipping. For example, in a flash sale scenario, multiple threads are executing the flash sale at the same time, and if one of them succeeds, it is enough. When the remaining threads find that their CAS fails, it actually means that the other threads have succeeded, so there is no need to continue executing. This is called skipping. Therefore, different business logics will have different processing methods, but no matter how they are handled later, the previous CAS operation has already failed.

Semantics of CAS #

Let’s take a look at the semantics of CAS. After having the following equivalent code, it will be easier to understand because the code is actually clear at a glance. Next, let’s unpack CAS and see what it does internally. The equivalent code for the semantics of CAS is as follows:

/**
 * Description: Simulate CAS operation, equivalent code

*/
public class SimulatedCAS {

    private int value;

    public synchronized int compareAndSwap(int expectedValue, int newValue) {

        int oldValue = value;

        if (oldValue == expectedValue) {

            value = newValue;

        }

        return oldValue;

    }

}

In this code, there is a compareAndSwap method with two parameters: the expected value expectedValue and the new value newValue. We want to update the variable with this new value.

You may notice that the compareAndSwap method is synchronized. This synchronized method ensures the atomicity of the CAS equivalent code.

Next, I will explain what happens in the compareAndSwap method. Firstly, the current value of the variable is obtained using int oldValue = value. Then, a comparison is made using the if (oldValue == expectedValue) statement. If the current value and the expected value are equal, it means that the current value is exactly what we expected. In this case, the condition is satisfied, and the swap can be performed. The value of value is modified to newValue, and finally, oldValue is returned, completing the entire CAS process.

The core idea of CAS is demonstrated in this process. As you can see, compare refers to the comparison in the if statement, where oldValue is compared to expectedValue. Similarly, swap implies changing value to newValue and returning oldValue. Therefore, this entire compareAndSwap method represents the semantics of CAS and the work done behind the scenes by CAS instructions.

Example Demonstration: Two threads competing with CAS, one of them losing #

With the equivalent code mentioned earlier, let us now dive into a specific example: two threads executing CAS and attempting to modify data. The first thread successfully modifies the data, while the second thread, arriving late, finds that the data has already been modified and therefore does not make any changes. By debugging, we can see the specific situation during the execution of CAS.

Below is the code that demonstrates what happens when CAS is used by two threads in competition. I have also recorded a video demonstrating this, which you can watch directly if you prefer.

We look at the following code:

public class DebugCAS implements Runnable {

    private volatile int value;

    public synchronized int compareAndSwap(int expectedValue, int newValue) {

        int oldValue = value;

if (oldValue == expectedValue) {

    value = newValue;

    System.out.println("Thread "+Thread.currentThread().getName()+" executed successfully");

}

return oldValue;

}

public static void main(String[] args) throws InterruptedException {

    DebugCAS r = new DebugCAS();

    r.value = 100;

    Thread t1 = new Thread(r,"Thread 1");

    Thread t2 = new Thread(r,"Thread 2");

    t1.start();

    t2.start();

    t1.join();

    t2.join();

    System.out.println(r.value);

}

@Override

public void run() {

    compareAndSwap(100, 150);

}

The compareAndSwap method here is the code for the equivalent semantics of CAS just discussed. We added one line of code on top of this. If executed successfully, it will print which thread is executing successfully.

In the main() method, we first instantiate the DebugCAS class and modify the value to 100, so that its initial value is 100. Then we create two threads, Thread t1 and Thread t2, start them, and have the main thread wait for the two threads to finish execution before printing out the final value.

What do these two new threads do? You can see from the run() method that they execute the compareAndSwap method, expecting a value of 100 and hoping to change it to 150. So, when these two threads both execute the run() method, it is foreseeable that only one thread will execute successfully, and the other thread will not print the sentence “executed successfully” because when it executes, it will find that the value has already been changed and is no longer 100.

First, let’s run it without setting breakpoints and see the results:

Thread Thread 1 executed successfully
150

As you can see, Thread 1 executed successfully, and the result is 150. In this case, the probability of printing “Thread 1 executed successfully” is much higher than the probability of printing “Thread 2 executed successfully” because Thread 1 was started first.

Now, let’s debug the code to see how it works internally. First, set a breakpoint at the line “if (oldValue == expectedValue) {” and run it in debug mode.

You can see that the program has stopped at the breakpoint. The one that stopped is Thread 1 (the current thread name and status can be displayed in the debugger), while Thread 2 is in the Monitor state (corresponding to the Blocked state of the Java thread), which means it hasn’t acquired the lock synchronized and is waiting outside.

Now Thread 1 has entered the compareAndSwap method. You can clearly see that the oldValue is 100, and the value of expectedValue is also 100, so they are equal.

Continue running the code step by step. Since the if condition is satisfied, the if statement will be entered, and then the value will be changed to newValue, where newValue is exactly 150.

After the modification is complete, it will also print the sentence “Thread 1 executed successfully”, as shown in the following image.

Next, press the execute button on the left, and now it’s Thread 2’s turn. The situation is different now.

As you can see, oldValue gets a value of 150 because the value of value has already been modified by Thread 1. So, 150 is not equal to the expected value of Thread 2, which is 100, so it will skip the entire if statement and won’t print the sentence “Thread 2 executed successfully”. The final result is that it will return oldValue without modifying it.

At this point, the two threads have finished executing. In the console, only “Thread 1 executed successfully” is printed, and “Thread 2 executed successfully” is not printed. The reason for this has been revealed through the use of debugging.

The code above uses debugging to show how two threads compete for CAS, with one thread succeeding and the other failing.