What is CAS?

Concurrent Addition and Subtraction (often jokingly referred to, but actually Compare-And-Swap) is an atomic operation that compares the value in memory with an expected value and, if they match, updates it with a new value.

It is similar to pseudocode:

// current_value - current value in memory
// expected_value - expected value
// new_value - new value
if (current_value == expected_value) {
  current_value = new_value;
  return true; // Operation successful
} else {
  return false; // Expected value did not match, operation not performed
}

It is used in low-level synchronization primitives and lock-free algorithms to ensure thread safety without using locks (mutexes, semaphores). Java provides support for CAS through classes in the java.util.concurrent.atomic package, such as:

• AtomicInteger
• AtomicLong
• AtomicReference

Example of using AtomicInteger:

import java.util.concurrent.atomic.AtomicInteger;

public class CasExample {

    public static void main(String[] args) {
        AtomicInteger counter = new AtomicInteger(0);

        boolean success = counter.compareAndSet(0, 1); // Compare current 0 with expected 0, if matches, set to 1
        System.out.println("CAS successful: " + success); // Output: true
        System.out.println("Current value: " + counter.get()); // Output: 1

        success = counter.compareAndSet(0, 2); // Compare current 1 with expected 0, does not match
        System.out.println("CAS successful: " + success); // Output: false
        System.out.println("Current value: " + counter.get()); // Output: 1
    }
}

Advantages:

• Lock-free: Threads do not block each other when attempting CAS.
• High performance: On multi-processor systems, it can be faster than locks due to the absence of context switch overhead.

Disadvantages:

• ABA problem: If the value was changed from A to B, and then back to A between reading and executing CAS, the operation will be considered successful even if the value actually changed. Some classes (like AtomicStampedReference) solve this problem by adding a "stamp".
• Spurious wakeups: Threads may "spin" in a loop trying to perform CAS, consuming CPU resources.
• Complexity: Developing lock-free algorithms using CAS can be more complex than using locks.