JavaEECAS — Multithreading (7)

CAS

1. What is CAS
2. CAS pseudocode
3. How is CAS implemented?
4. Application of CAS
- 4.1 Implementing atomic classes
- 4.2 Implement spin lock
5. ABA issues with CAS

1. What is CAS

CAS: Full name Compare and swap, literal meaning: “Compare and swap”
Able to compare and exchange the value in a certain register with the value in memory to see if they are equal. If they are equal, put the value in another register The value is exchanged with memory

2. CAS pseudocode

The code written below is not atomic. The real CAS is completed by an atomic hardware instruction. This pseudocode is only to assist in understanding the workflow of CAS.

boolean CAS(address, expectValue, swapValue) {<!-- -->
 if ( & amp;address == expectedValue) {<!-- -->
    & amp;address = swapValue;
        return true;
   }
    return false;
}

Pseudocode explanation

address is the memory address, and the remaining two are values in the register – one representing the old data, and one representing the value to be updated.
This piece of logic is completed through a CPU instruction – so this operation is atomic
Explain the reason why the exchange statement has only one assignment statement: exchange the value of the address memory with the value of the swapValue register, but we generally focus on the value in the memory. Registers are often used as a method to save temporary data. What is the value here? Yes, often ignored

3. How CAS is implemented

For different operating systems, JVM uses different CAS implementation principles. To put it simply:

Java’s CAS uses the CAS operation provided by the unsafe class;
unsafe’s CAS relies on Atomic::cmpxchg implemented by jvm for different operating systems;
The implementation of Atomic::cmpxchg uses assembly CAS operations and uses the lock mechanism provided by the CPU hardware to ensure its atomicity.

In short,it is because the hardware supports it that the software can do it

4. Application of CAS

4.1 Implementing atomic classes

The standard library provides the java.util.concurrent.atomic package, and the classes in it are all implemented based on this method.

The typical one is the AtomicInteger class. The getAndIncrement is equivalent to the i++ operation.

Use of atomic classes

public static AtomicInteger count = new AtomicInteger(0);
public static void main(String[] args) throws InterruptedException {<!-- -->
    Thread t1 = new Thread(() -> {<!-- -->
        for (int i = 0; i < 5000; i + + ) {<!-- -->
            // count + +
            count.getAndIncrement();
            // + + count
            // count.incrementAndGet();
            // count--
            // count.getAndDecrement();
            // --count
            // count.decrementAndGet();
        }
    });

    Thread t2 = new Thread(() -> {<!-- -->
        for (int i = 0; i < 5000; i + + ) {<!-- -->
            // count + +
            count.getAndIncrement();
        }
    });

    t1.start();
    t2.start();
    t1.join();
    t2.join();

    System.out.println(count.get());
}

Pseudo code implementation

class AtomicInteger {<!-- -->
    private int value;
    public int getAndIncrement() {<!-- -->
        int oldValue = value;
        while ( CAS(value, oldValue, oldValue + 1) != true) {<!-- -->
            oldValue = value;
       }
        return oldValue;
   }
}

Assume that two threads call getAndIncrement at the same time

Both threads read the value of value into oldValue. (oldValue is a local variable on the stack. Each thread has its own stack)

Thread 1 first performs the CAS operation. Since the values of oldValue and value are the same, value is assigned directly.

Notice:
- CAS directly reads and writes memory, rather than operating registers.
- CAS’s memory reading, comparison, and memory writing operations are a hardware instruction and are atomic.

Thread 2 performs the CAS operation again. During the first CAS operation, it is found that oldValue and value are not equal and cannot be assigned. Therefore, a loop needs to be entered;
Reread value in the loop and assign it to oldValue

Thread 2 then executes CAS for the second time. At this time, oldValue and value are the same, so the assignment operation is performed directly.
Thread 1 and thread 2 can return their respective oldValue values.

An atomic class can be implemented through the above code. Multi-threaded auto-increment operations can be completed efficiently without using heavyweight locks.

Originally, operations like check and set are not atomic from a code perspective. However, at the hardware level, one instruction can complete this operation, and it becomes atomic.

4.2 Implementing spin lock

Implement more flexible locks based on CAS and gain more control.

Spin lock pseudocode

public class SpinLock {<!-- -->
    private Thread owner = null;
    public void lock(){<!-- -->
        // Use CAS to see if the current lock is held by a thread.
        // If this lock is already held by another thread, then spin and wait.
        // If this lock is not held by another thread, then set owner to the thread currently trying to lock.
        while(!CAS(this.owner, null, Thread.currentThread())){<!-- -->
       }
   }
    public void unlock (){<!-- -->
        this.owner = null;
   }
}

Pseudocode analysis

5. ABA issues of CAS

The key point of CAS is to compare the value of register 1 and the memory, and determine whether the value of the memory has changed by whether they are equal;
- If the value of the memory variable exists, it has been modified by other threads;
- If the memory value has not changed and no other thread has modified it, subsequent modifications are safe.
The question is raised: If the value here has not changed, does it mean that no other thread has modified it?
- the answer is negative!
- The memory value change process may be A -> B -> A
- This is the so-called ABA problem
In most cases, even if there is an ABA problem, it will not have much impact, but if there are some extreme scenarios, it may not be the case.

Bugs caused by ABA issues

solution

Introduce a version number to the value to be modified. While CAS compares the current value of the data with the old value, it also needs to compare whether the version number meets expectations.
- When the CAS operation reads the old value, it also reads the version number.
- When it comes to actual modifications,
  - If the current version number is the same as the read version number, modify the data and add the version number + 1
  - If the current version number is higher than the read version number, the operation fails (the data is considered to have been modified).

The AtomicStampedReference class is provided in the Java standard library. This class can wrap a certain class and internally provide the version management function described above.