Introduction of the CAS

What is CAS? Its full English name is compare-and-swap, Chinese name is “Compare And exchange”, it is a kind of idea, an algorithm.

In the case of multi-threading, the order of each code execution is uncertain, so to ensure concurrency safety, we can use mutex. The feature of CAS is to avoid the use of mutex. When multiple threads use CAS to update the same variable at the same time, only one thread succeeds, while all the other threads fail to update. Unlike synchronous mutex, however, the thread that failed to update is not blocked. Instead, it is told that the operation failed due to contention, but can try again.

CAS is widely used in the world of concurrent programming to implement data exchange operations that are not interrupted, thus achieving lockless thread safety.

The thinking of the CAS

In most of the processor’s instruction, will realize the CAS relevant instruction, the instruction can complete the comparison and exchange operations, it is because this is a (rather than multiple CPU instruction, so the CAS related instruction is atomic, this combination operation during execution will not be interrupted, so it can ensure the safety of the concurrent. Since this atomicity is guaranteed by the CPU, we programmers don’t have to worry about it.

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

To describe this, CAS assumes in advance that the current memory value V should be equal to the value A, which is usually the memory value V that was read before. If the current memory value V happens to be A, the CAS changes the memory value V to B, which is usually calculated based on A. If the memory value V is not equal to the memory value A during the CAS execution, it indicates that the memory value has been modified by another thread during the calculation of B. In this case, the CAS should not be modified this time to avoid errors caused by simultaneous modification by multiple threads. This is the main idea and process of CAS.

It is these CAS directives that the JDK leverages to implement concurrent data structures, such as atomic classes such as AtomicInteger.

Source:

/**
 * Atomically sets the value to the given updated value
 * if the current value {@code ==} the expected value.
 *
 * @param expect the expected value
 * @param update the new value
 * @return {@code true} if successful. False return indicates that
 * the actual value was not equal to the expected value.
 */
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
Copy the code

Broadening local methods

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Copy the code

The lock-free algorithm realized by CAS is just like when we negotiated in a very optimistic way and were friendly with each other. If the negotiation failed this time, we could try again. The CAS approach is completely different from the previous mutex approach. If it is a mutex, there is no negotiation mechanism and everyone will try to grab the resource. If they grab the resource, they will hold on to it until the operation is complete. Of course, both CAS and mutex guarantee concurrency security, and they are different means of achieving the same goal.

CAS semantic

Taking a look at the semantics of CAS, it becomes easier to understand with the following equivalent code, because the code is actually self-explanatory. Let’s take CAS apart to see what exactly is going on inside it. The code for the equivalent semantics of CAS is as follows:

/** * Description: simulates 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;

        }

        returnoldValue; }}Copy the code

In this code there is a compareAndSwap method. In this method there are two input parameters, the first one is expectedValue and the second one is newValue, which is the newValue we calculated and we want to update the newValue to the variable.

The compareAndSwap method is modified by synchronized, and we use synchronization to ensure atomicity for the CAS equivalent code.

I’m going to show you what we’re doing in compareAndSwap. To retrieve the current value of the variable, int oldValue = value is used to retrieve the current value. And then compare, “compare,” so if (oldValue == expectedValue) is used to compare the current value with the expectedValue, and if they are equal, that means the current value is exactly what we expect, satisfying the condition, In this case, swap can be performed. Therefore, change the value of value to newValue and return oldValue to complete the CAS process.

The core idea of CAS is reflected in the above process. It can be seen that compare refers to the comparison in if, comparing whether oldValue is equal to expectedValue; Similarly, swap essentially changes value to newValue and returns oldValue. So this whole compareAndSwap method restores the semantics of CAS and symbolizes what the CAS directive does behind the scenes.

This is similar to our implementation of optimistic locking for the database, where the version field controls whether the variable is updated. In a database optimistic lock implementation, we typically specify a field, in this case version(int). Update tablename set version = version +1, column_1 = val where version = version;

What is the specific process? After using the version field to control the version:

  1. Two people query the data firstselect * from tablename where id = 1

In this case, the queried data is the same as version = 0

  1. Mysql > update table (1); update table (1); update table (2);

update tablename set column_1 = 1, version = version + 1 where id = 1 and version = 0

After execution, the version field value will change to 1, and the second person will execute update:

update order set price = 1, version = version + 1 where id = 1 and version = 0

At this point, the value of version has been changed to 1, so the second person fails to change, and optimistic lock control is implemented.