Atomic operations and cas

1. What are Atomic Operations?

An atomic operation is an operation that cannot be interrupted or divided into smaller operations. In other words, it either executes completely or does not execute at all. This ensures safety in multi-threaded environments, where multiple threads may access shared resources concurrently.

Why Are Atomic Operations Important?

• In a multi-threaded environment, if multiple threads access and modify a shared variable simultaneously, race conditions may occur.
• If an operation is atomic, no other thread can see or modify the variable in the middle of the operation.
• This ensures data integrity and prevents inconsistencies.

Example of an Atomic Operation

volatile int i = 0; 
i = 1;

The above assignment (i = 1) is atomic because:

1. The value 1 is stored in the CPU register.
2. The value 1 is directly written to the variable i in memory.
3. There are no intermediate steps where another thread can interrupt the operation.

However, the following is NOT an atomic operation:

i++; // Not atomic!

This operation actually consists of three separate steps:

1. Read the value of i from memory.
2. Increment the value.
3. Write the new value back to memory.

If multiple threads execute i++ simultaneously, race conditions can occur because two threads may read the same value before either of them writes back.

---

2. The Problem of Non-Atomic Operations in Multi-Threading

When multiple threads modify a shared variable, race conditions occur. Consider the following case:

Example Without Atomic Operations

class Counter {
    private int count = 0;

    public void increment() {
        count++; // Not atomic!
    }

    public int getCount() {
        return count;
    }
}

If multiple threads call increment() simultaneously, the following issue may arise:

1. Thread A reads count = 5 from memory.
2. Thread B reads count = 5 before Thread A writes back.
3. Thread A increments count and writes 6.
4. Thread B increments count and writes 6 again. (Lost update!)

The correct result should be 7, but due to a race condition, the result is 6.

---

3. CAS (Compare-And-Swap) - The Solution

What is CAS?

Compare-And-Swap (CAS) is a lock-free synchronization mechanism that ensures safe updates in a multi-threaded environment.

How CAS Works

1. Read the current value.
2. Compare the read value with an expected value.
3. If they match, update the value.
4. If they do not match, retry the operation.

This prevents lost updates and race conditions without using locks.

CAS in Java (AtomicInteger)

Java provides the java.util.concurrent.atomic package, which includes atomic classes like AtomicInteger, AtomicLong, and AtomicReference. These classes use CAS internally to ensure thread safety.

Example: Using AtomicInteger for Thread-Safe Increment

import java.util.concurrent.atomic.AtomicInteger;

class AtomicCounter {
    private AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        count.incrementAndGet(); // Atomic operation
    }

    public int getCount() {
        return count.get();
    }
}

public class CASExample {
    public static void main(String[] args) {
        AtomicCounter counter = new AtomicCounter();
        counter.increment();
        System.out.println(counter.getCount()); // 1
    }
}

• incrementAndGet() internally uses CAS, ensuring the value is updated safely.
• No need for explicit locks (synchronized).

---

4. CAS vs. Locking (synchronized, ReentrantLock)

Feature CAS (AtomicInteger) Locking (synchronized, ReentrantLock)

Thread Blocking	Non-blocking	Blocking
Performance	Fast, since threads do not wait	Slower due to thread contention
Fairness	No fairness guarantee	Guarantees fairness in ReentrantLock
Complexity	More complex in certain cases	Simple to use

When to Use CAS vs. Locks?

• Use CAS (AtomicInteger) when high performance and low contention are required.
• Use locks (synchronized or ReentrantLock) when contention is high, and fairness is needed.

---

5. CAS-Based Implementations in Java

• AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference
• ConcurrentHashMap
• LongAdder (for high-performance counters)

Example: Custom CAS Implementation

import java.util.concurrent.atomic.AtomicInteger;

class CASCounter {
    private AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        int oldValue, newValue;
        do {
            oldValue = count.get();
            newValue = oldValue + 1;
        } while (!count.compareAndSet(oldValue, newValue)); // CAS operation
    }

    public int getCount() {
        return count.get();
    }
}

public class CustomCASExample {
    public static void main(String[] args) {
        CASCounter counter = new CASCounter();
        counter.increment();
        System.out.println(counter.getCount()); // 1
    }
}

• compareAndSet(oldValue, newValue) ensures only one thread can update the value at a time.
• If another thread modifies the value, it retries until successful.

---

6. Summary

✅ What We Learned

1. Atomic Operations ensure an operation is executed completely or not at all.
2. CAS (Compare-And-Swap) is a non-blocking algorithm used for thread-safe updates without locks.
3. Java provides AtomicInteger, AtomicLong, and AtomicReference, which internally use CAS.
4. CAS is more efficient than locks in low-contention scenarios but may cause performance issues under high contention.

🛠 When to Use CAS?

✔ When you need lightweight, high-performance synchronization.
✔ When thread contention is low, making retries rare.
❌ Avoid CAS when contention is high, as repeated retries can degrade performance.