What is the CAS (Compare-And-Swap) mechanism?

The Compare-And-Swap (CAS) mechanism is an atomic machine operation used to implement lock-free synchronization.

Working principle:

1. Reads the current value of a memory cell (expectedValue).
2. Attempts to write a new value (newValue) to this cell only if the current value matches expectedValue.
3. Returns a boolean value: true if the write was successful (i.e., the values matched), false otherwise.

In Java, CAS is implemented in classes from the java.util.concurrent.atomic package, such as AtomicInteger, AtomicLong, AtomicReference.

Example of using AtomicInteger:

// java
import java.util.concurrent.atomic.AtomicInteger;

public class CasExample {
    private AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        while (true) {
            int expectedValue = count.get(); // Read the current value
            int newValue = expectedValue + 1;
            if (count.compareAndSet(expectedValue, newValue)) {
                // If the current value hasn't changed since reading,
                // perform the write and exit the loop
                break;
            }
            // If the value changed, retry
        }
    }
}

Advantages:

• Non-blocking: threads do not block each other, reducing overhead from context switching, especially under low contention.
• Avoids deadlock issues.

Disadvantages:

• ABA problem: if the cell's value changes from A to B, and then back to A, CAS will think no change occurred. This problem is addressed using classes like AtomicStampedReference or AtomicMarkableReference.
• Can lead to many failed attempts (spin loops) under high contention.