By Jacob Jankov

Original text: tutorials.jenkov.com/java-concur…

Translation: If you have a better translation version of Pan Shenlian’s personal website, please submit an issue or contribute to ❤️

Update: the 2022-02-24

CAS (Compare and Swap) is a technique used in the design of concurrent algorithms. Basically, CAS compares the value of the variable to the expected value, and if the values are equal, sets the swap of the variable to the new value. CAS may sound a bit complicated, but it’s actually quite simple once you understand it, so let me elaborate on this topic further.

By the way, compare and swap is sometimes short for CAS, so if you see some concurrent article or video that mentions CAS, it most likely refers to the compare and swap operation.

CAS Tutorial Video

If you like videos, I have this CAS video tutorial version here :(green Internet) CAS video tutorial

CAS Application Scenarios (Check Then Act)

A common pattern in concurrent algorithms is the check then Act pattern. The Check then Act pattern occurs when code first checks the value of a variable and then acts on that value. Here’s a simple example:

public class ProblematicLock {

    private volatile boolean locked = false;

    public void lock(a) {

        while(this.locked) {
            // Wait busily - until this.locked == false
        }

        this.locked = true;
    }

    public void unlock(a) {
        this.locked = false; }}Copy the code

This code is not a 100% correct implementation of multithreaded locks. That’s why I named it ProblematicLock. However, I created this faulty implementation to show how to solve its problems with the CAS functionality.

The lock() method first checks that the member variables are locked equal to false. This is done inside the while-loop. If the locked variable is false, the lock() method leaves the while loop and sets locked to true. In other words, the lock() method first checks the values of the variables locked, and then acts on that check. Check first and then execute.

If multiple threads access the same ProblematicLock instance almost at the same time, the above lock() method has some problems, such as:

If thread A checks that the locked values are false (expected), it will exit the while-loop loop to execute the subsequent logic. If thread B checks locked values before thread A sets them to true, thread B will exit the while-loop loop to execute the logic. This is a classic problem of resource competition.

Check Then Act must be atomic

In order to work properly in multithreaded applications (to avoid resource contention), Check Then Act must be atomic. Atomicity means that both checking and executing actions are performed as atomic (indivisible) blocks of code. Any thread that starts executing the block completes the block without interference from other threads. Other threads are not allowed to execute the same atomic block at the same time.

An easy way to atomize a Block of Java code is to tag it with Java’s synchronized keyword. See the section on synchronized. Here’s how to convert the lock() method into an atomic block using the synchronized keyword before ProblematicLock:

public class MyLock {

    private volatile boolean locked = false;

    public synchronized void lock(a) {

        while(this.locked) {
            // Wait busily - until this.locked == false
        }

        this.locked = true;
    }

    public void unlock(a) {
        this.locked = false; }}Copy the code

Now that the lock() method has declared synchronization, the lock() method of the same instance is allowed to be accessed by only one thread at a time. The lock() method is atomic.

Blocking threads is costly

When two threads attempt to enter a synchronized block in Java at the same time, one thread is blocked and the other thread is allowed to enter the synchronized block. Waiting threads are allowed to enter the block only when the thread that entered the synchronized block exits the block again.

If the thread is allowed access to execution, it is not costly to enter a synchronized block of code. However, if another thread is forced to wait to block because one thread is already executing in the synchronized block, the cost of that blocked thread is high.

In addition, you can’t be sure exactly when a blocked thread will be unblocked when the synchronized block is idle again. It is usually up to the operating system or execution platform to coordinate the unblocking of the blocking threads. Of course, it won’t take seconds or minutes before the blocking thread is unblocked and allowed in, but some time might be wasted blocking the thread because it could have access to the shared data structure. This is illustrated here:

Atomic CAS operation provided by hardware

Modern cpus have built-in support for atomic manipulation of CAS. In some cases, CAS operations can be used instead of synchronous blocks or other blocking data structures. The CPU guarantees that only one thread can perform CAS operations at a time, even across CPU cores. Examples are provided later in the code.

When the CAS function provided by the hardware or CPU is used instead of synchronized, Lock, and mutex provided by the operating system or execution platform, the operating system or execution platform does not need to handle thread blocking and unblocking. This causes threads using CAS to wait less time to execute operations and to have less congestion and higher throughput. As shown below:

As you can see, threads trying to enter a shared data structure are never completely blocked. It keeps trying to perform the CAS operation until it succeeds and is allowed access to the shared data structure. This minimizes the latency before threads enter the shared data structure.

Of course, if a thread waits for a long time to repeatedly execute the CAS, it can waste a lot of CPU cycles that could have been spent on other tasks (other threads). But in many cases, this is not the case. This depends on how long the shared data structure is used by another thread. In fact, shared data structures have not been used for very long, so this should not happen very often. But again it depends on the situation, the code, the data structure, the number of threads trying to access the data structure, the system load, and so on. In contrast, the blocked thread does not use the CPU at all.

Java in the CAS

Starting from Java 5, you can through the Java. Util. Concurrent. The atomic package some of the new method of atomic classes to access the CPU level of CAS. These classes are:

  • AtomicBoolean
  • AtomicInteger
  • AtomicLong
  • AtomicReference
  • AtomicStampedReference
  • AtomicIntegerArray
  • AtomicLongArray
  • AtomicReferenceArray

The advantage of using CAS functionality that comes with Java 5+ rather than implementing it yourself is that the BUILT-IN CAS functionality in Java 5+ allows your applications to take advantage of the CPU’s underlying capabilities to perform CAS operations. This makes your CAS implementation code faster.

Guarantee of CAS

The CAS feature can be used to secure Critical sections to prevent multiple threads from executing Critical sections simultaneously.

? The critical section is the section of code in each thread that accesses critical resources, whether hardware or software, and that multiple threads must mutually exclusive access. The Section of code in each thread that accesses Critical resources is called the Critical Section. The Section of the program in each thread that accesses a Critical resource is called a Critical Section (a Critical resource is a shared resource that only one thread is allowed to use at a time). Only one thread is allowed to enter a critical section at a time, and no other thread is allowed to enter.

The following example shows how the CAS functionality of the AtomicBoolean class can be used to implement and thus safeguard the lock() method shown earlier (only one thread at a time can exit the lock() method).

public class CompareAndSwapLock {

    private AtomicBoolean locked = new AtomicBoolean(false);

    public void unlock(a) {
        this.locked.set(false);
    }

    public void lock(a) {
        while(!this.locked.compareAndSet(false.true)) {
            // busy wait - until compareAndSet() succeeds}}}Copy the code

Note that the locked variable is no longer a Boolean but an AtomicBoolean. This class has a compareAndSet() method that compares the value of the instance (the variables locked) to the first argument (false). If the comparison results are the same (that is, the values locked are equal to the first argument false), the instance’s values locked are swapped with the expected value true (that is, the locked variable is set to true, indicating that it is locked). The compareAndSet() method returns true if the exchange was successful and false if it was not.

In the example above, the compareAndSet() method call compares the locked values with false values. If the locked values result in false, the locked values are set to true.

Because only one thread is allowed to execute the compareAndSet() method at a time, only one thread can see that the AtomicBoolean instance value is false and swap it to true. Therefore, only one thread can exit the while-loop at a time, and CompareAndSwapLock is unlocked by calling unlock() and setting locked to false so that only one thread at a time can exit the while-loop.

CAS implements optimistic locking

You can also use the CAS feature as an optimistic locking mechanism. Optimistic locking allows multiple threads to enter a critical section at the same time, but only one of them is allowed to commit its work at the end of the critical section.

Here is an example of a concurrency counter class that uses an optimistic locking strategy:

public class OptimisticLockCounter{

    private AtomicLong count = new AtomicLong();


    public void inc(a) {

        boolean incSuccessful = false;
        while(! incSuccessful) {long value = this.count.get();
            long newValue = value + 1;

            incSuccessful = this.count.compareAndSet(value, newValue); }}public long getCount(a) {
        return this.count.get(); }}Copy the code

Notice how the inc() method gets the existing count value from the AtomicLong instance variable count. The new value is then calculated from the old value. Finally, the Inc () method tries to set the new value by calling the compareAndSet() method of the AtomicLong instance.

If the AtomicLong instance value count still has the same value at comparison time as it did when it was last fetched (long Value = this.count.get()), then compareAndSet() executes successfully. However, if another thread has already called compareAndSet() at the same time, the compareAndSet() call will fail. Because the expected value value is no longer equal to the stored value AtomicLong (the original value has been changed by the previous thread). In this case, the inc() method does another iteration in the while-loop and tries to increase the AtomicLong value again.

(The end of this article)

Original text: tutorials.jenkov.com/java-concur…

Translation: If you have a better translation version of Pan Shenlian’s personal website, please submit an issue or contribute to ❤️