Concurrent Programming in Java: What is CAS? Now I know

The idea of no locks

As we all know, the most common method of concurrency control in Java is locking, which ensures that only one thread can access the resources in a critical area at a time, thus achieving thread safety. However, locking, while effective, takes a pessimistic approach. It assumes that every access to a critical section resource will conflict, and that when one thread accesses the resource, the other threads must wait, so the lock will block thread execution.

Of course, every coin has two sides, and pessimism leads to optimism. Lockless is an optimistic strategy that assumes that threads have no conflicting access to resources, and that all thread execution can continue without waiting. If conflicts are encountered, a technique called CAS (Comparison switching) is used to identify thread conflicts, and if a conflict is detected, the current operation is retried until there are no conflicts.

Summary of the CAS

CAS stands for compare-and-swap, or Compare and Swap, and is a common algorithm used in concurrent programming. It takes three arguments: V, A, and B.

Where V represents the memory location to be read or written, A represents the old expected value, and B represents the new value

When executing the CAS instruction, V is set to B if and only if V is equal to the expected value A. If V is different from A, another thread may have updated it, and the current thread does nothing. Finally, CAS returns the true value of V.

In the case of multi-threading, when multiple threads use CAS to manipulate a variable at the same time, only one of them will succeed and update the value, while the rest will fail. However, the failed thread will not be suspended, but continuously retry in a loop. Because of this principle, CAS can detect interference from other threads to the current thread even when the lock is not used.

CAS application class

In Java application provides a series of CAS operation classes, these classes in Java. Util. Concurrent. The atomic package, one of the most commonly used is AtomicInteger, this class can be seen as the CAS operation of Integer, so, Let’s take a look at the big picture of how CAS is used.

Before we learn AtomicInteger, let’s look at a code example:

public class AtomicDemo {

    public static int NUMBER = 0;

    public static void increase() {
        NUMBER++;
    }

    public static void main(String[] args) throws InterruptedException {
        AtomicDemo test = new AtomicDemo();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                for(int j = 0; j < 1000; j++) test.increase(); }).start(); } Thread.sleep(200); System.out.println(test.NUMBER); }}Copy the code

Increase () is called in turn. We know that the result is not the value we expected, because we did not do thread-safe processing, so the resource NUMBER in the critical area of the 10 thread traffic operation will fail.

The solution is not too difficult, and using the locks we learned earlier, such as synchronized, to modify a block of code, the program will normally output 10,000. Of course, locking is not the way we want to do it, because locking blocks threads and affects application performance, where AtomicInteger comes in handy.

Modify the above program to look like this:

public static AtomicInteger NUMBER = new AtomicInteger(0);

public static void increase() {
    NUMBER.getAndIncrement();
}

public static void main(String[] args) throws InterruptedException {
    AtomicDemo test = new AtomicDemo();
    for (int i = 0; i < 10; i++) {
        new Thread(() -> {
            for (int j = 0; j < 1000; j++)
                test.increase();
        }).start();
    }
    Thread.sleep(200);
    System.out.println(test.NUMBER);
}
Copy the code

When we run main, the program outputs the desired value, which is 10000.

Increment_increment (); increment_increment (); increment_increment (); increment_increment (); increment_increment (); increment_increment (); It calls the broadening.getAndAddInt() method:

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

GetAndAddInt increments the current value and returns the old value.

Unsafe is a variable of the unsafe class, and is retrieved via unsafe.getunsafe ()

private static final Unsafe unsafe = Unsafe.getUnsafe();
Copy the code

The Unsafe class is a special class that is exclusively for use within the JDK. You cannot view the source directly with the Unsafe editor, just the decomcompiled class file.

Even though Java itself does not have access to the operating system, native methods are required. The Unsafe class, for example, contains a large number of native methods, improving Java’s ability to operate on the underlying atoms of the system. For example, the bottom layer of getAndAddInt() used in our code is to call a native method, click the method with IDEA, and get the following decomcompiled code:

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;
}
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Copy the code

CompareAndSwapInt is used to compare and swap integer values. If the specified field value is equal to the expected value, ‘A’ (expected value) in CAS, it is set to the new value (‘B’ in CAS). It is not hard to imagine that the internal implementation of this method must rely on atomic operations. The Unsafe class also offers methods for atomic operations, such as getIntVolatile, which uses volatile semantics to obtain the value of a given object. These methods improve performance at the application level through low-level atomic operations.

The disadvantage of the CAS

Although CAS performance is much more powerful than locks, it does have some disadvantages, such as:

1, the cycle time cost is large

In the getAndAddInt method, we can see that simply setting a value calls the loop, and if the CAS fails, it keeps trying. If the CAS is not successful for a long time, then the loop will run continuously, which will undoubtedly cause a lot of overhead to the system.

2. ABA problems

As mentioned above, the condition for CAS to judge the success of variable operation is that the value of V is consistent with the value of A. There is A small defect in this logic, that is, if the value of V is A at the beginning, it is changed to B before it is changed to the new value, and then it is changed back to A, the value of the object is still the old value after two threads change. Then the CAS operation will misperform and this variable has never been modified. This is the “ABA” problem in CAS.

Of course, there is a solution to the “ABA” problem. Java provides a time-stamped object reference AtomicStampedReference that maintains both an object value and a timestamp inside, If the value of an AtomicStampedReference is modified, both the data and the timestamp are updated. The modification is successful only when both the object value and timestamp meet the expected value. Here are a few methods of timestamp information for AtomicStampedReference:

// Set the following parameters: Expected Write New value Expected Time Stamp New time stamp public Boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, Public int getStamp(); // Set the current object reference and timestamp public voidset(V newReference, int newStamp)
Copy the code