⚛️ File 03: Atomic Operations — `std::atomic<int>`, `AtomicInteger`, CAS Lock-Free

When the interviewer says: "Can you solve it without locks, using only atomic variables?"

📖 What is an Atomic Operation? (Simple Explanation)

An atomic operation is an operation that happens all at once — it's indivisible. No other thread can see it "half-done".

Analogy:

Non-atomic: Transferring money in two steps: (1) debit your account, (2) credit their account. If the system crashes between steps, money disappears! Another thread could see the intermediate state.
Atomic: Transferring money in one step: it either happens completely or not at all.

Why `x++` is NOT Atomic

int x = 5;
x++;  // Looks like one step, but it's THREE CPU instructions:

MOV EAX, [x]    ; Step 1: Read x from memory into CPU register (EAX = 5)
INC EAX         ; Step 2: Increment register (EAX = 6)
MOV [x], EAX    ; Step 3: Write result back to memory (x = 6)

If a context switch happens between Step 1 and Step 3:

Thread A: MOV EAX, [x]  → EAX_A = 5
          ─── CONTEXT SWITCH ───
Thread B: MOV EAX, [x]  → EAX_B = 5  (still reads 5!)
Thread B: INC EAX       → EAX_B = 6
Thread B: MOV [x], EAX  → x = 6
          ─── CONTEXT SWITCH BACK ───
Thread A: INC EAX       → EAX_A = 6
Thread A: MOV [x], EAX  → x = 6      ← SHOULD BE 7! Lost B's update!

Result: x should be 7, but it's 6. Lost update bug.

How `std::atomic<int>` Fixes This

std::atomic<int> x{5};
x++;  // Compiles to a SINGLE instruction:

LOCK INC [x]    ; ONE instruction that reads, increments, and writes ATOMICALLY
                ; LOCK prefix tells other CPU cores: "Don't touch this address!"

No gap. No context switch can interrupt. No lost update.

🔧 C++ `std::atomic` — The Key Operations

1. `load()` — Read atomically

std::atomic<int> x{42};
int value = x.load();  // Atomically reads x. Guaranteed to see the latest value.

2. `store()` — Write atomically

x.store(100);  // Atomically writes 100 to x. All other threads will see this.

3. `fetch_add()` / `fetch_sub()` — Atomic increment/decrement

x.fetch_add(1);  // Atomically: old = x; x = old + 1; return old;
                  // Compiles to: LOCK XADD (one instruction)
x.fetch_sub(1);  // Atomically: old = x; x = old - 1; return old;

4. `compare_exchange_strong()` — THE BIG ONE (CAS)

int expected = -1;
bool success = x.compare_exchange_strong(expected, uid);
// Translation:
// IF x == expected (-1):
//     x = uid        ← atomically set
//     return true    ← success!
// ELSE:
//     expected = x   ← update expected with actual current value
//     return false   ← someone else got there first

This is the foundation of ALL lock-free programming. It atomically checks-and-sets in one CPU instruction (LOCK CMPXCHG).

5. `compare_exchange_weak()` — Faster but may fail spuriously

// Same as strong, but may return false EVEN IF x == expected (spurious failure)
// Why? On some CPU architectures (ARM), the implementation uses LL/SC which 
// can fail if another core touches the same cache line (even for a different variable)
// Use weak in a loop (you're retrying anyway), strong for one-shot attempts
while (!x.compare_exchange_weak(expected, desired)) {
    expected = -1;  // reset
}

☕ Java `AtomicInteger` — The Java Equivalent

import java.util.concurrent.atomic.AtomicInteger;

AtomicInteger x = new AtomicInteger(-1);  // -1 = unlocked

// Atomic read
int value = x.get();

// Atomic write
x.set(100);

// Atomic increment
x.incrementAndGet();   // returns new value
x.getAndIncrement();   // returns old value

// CAS (Compare-And-Swap)
boolean success = x.compareAndSet(-1, uid);
// IF x == -1: set x = uid, return true
// ELSE: return false

🔑 Memory Ordering (Why It Matters)

CPUs and compilers can reorder instructions for performance. In single-threaded code, this is fine. In multi-threaded code, it's catastrophic.

// Thread A:                  Thread B:
data = 42;                    if (ready) {
ready = true;                     use(data);  // might see data = 0 !!
                              }

The CPU might execute ready = true BEFORE data = 42 (store buffer reordering). Thread B sees ready == true but data hasn't been written yet!

Memory Ordering Options in `std::atomic`:

Order	Meaning	When to Use
`memory_order_relaxed`	No ordering guarantees. Just atomic.	Simple counters where order doesn't matter
`memory_order_acquire`	All reads/writes AFTER this cannot be moved BEFORE it	When acquiring a lock (see latest data)
`memory_order_release`	All reads/writes BEFORE this cannot be moved AFTER it	When releasing a lock (flush writes)
`memory_order_acq_rel`	Both acquire AND release	CAS operations that both read and write
`memory_order_seq_cst`	Strongest. Total global ordering.	When in doubt (default, but slower)

Simple Rule for Our Tree Problem:

Lock acquisition  → memory_order_acquire (see latest state)
Lock release      → memory_order_release (flush our changes)
CAS operations    → memory_order_acq_rel (both)
Simple counters   → memory_order_relaxed (just need atomicity)

🌳 Tree of Space: Lock-Free with `std::atomic` (CAS Approach)

This is the lock-free approach — no mutexes, no spinlocks, just atomic variables and CAS.

#include <atomic>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// ============ DATA STRUCTURES ============
vector<atomic<int>> locked;         // -1 = unlocked, else uid
vector<atomic<int>> descCount;      // number of locked descendants
vector<int> par;                    // parent array
vector<vector<int>> adj;            // adjacency list
unordered_map<string, int> nameMap;

// ============ LOCK-FREE LOCK FUNCTION ============
bool lockCAS(const string& name, int uid) {
    int node = nameMap[name];
    
    // === Phase 1: Optimistic Pre-checks (no writes yet) ===
    
    // 1a. Quick check: any descendant locked?
    if (descCount[node].load(memory_order_acquire) > 0) {
        return false;  // Fast fail
    }
    
    // 1b. Walk up ancestors: any ancestor locked?
    int cur = par[node];
    while (cur != -1) {
        if (locked[cur].load(memory_order_acquire) != -1) {
            return false;  // Fast fail
        }
        cur = par[cur];
    }
    
    // === Phase 2: Atomic Claim (CAS) ===
    
    // Atomically try to set locked[node] from -1 to uid
    // If another thread beat us, CAS fails and we return false
    int expected = -1;
    if (!locked[node].compare_exchange_strong(
            expected, uid, memory_order_acq_rel)) {
        return false;  // Another thread claimed this node
    }
    
    // === Phase 3: Validate + Propagate ===
    // We now "own" this node. But an ancestor might have been locked
    // between Phase 1 and Phase 2. We must re-verify.
    
    cur = par[node];
    vector<int> updatedAncestors;  // track what we modified (for rollback)
    bool conflict = false;
    
    while (cur != -1) {
        // Atomically increment ancestor's descendant count
        descCount[cur].fetch_add(1, memory_order_acq_rel);
        updatedAncestors.push_back(cur);
        
        // Re-check: did this ancestor get locked while we were working?
        if (locked[cur].load(memory_order_acquire) != -1) {
            conflict = true;
            break;
        }
        
        cur = par[cur];
    }
    
    // === Phase 4: Rollback on Conflict ===
    if (conflict) {
        // Undo all ancestor count increments
        for (int anc : updatedAncestors) {
            descCount[anc].fetch_sub(1, memory_order_acq_rel);
        }
        // Release our claim on the node
        locked[node].store(-1, memory_order_release);
        return false;
    }
    
    return true;  // Successfully locked!
}

// ============ LOCK-FREE UNLOCK ============
bool unlockCAS(const string& name, int uid) {
    int node = nameMap[name];
    
    // Atomically: if locked[node] == uid, set to -1
    int expected = uid;
    if (!locked[node].compare_exchange_strong(
            expected, -1, memory_order_acq_rel)) {
        return false;  // Not locked by this uid
    }
    
    // Decrement ancestor counters
    int cur = par[node];
    while (cur != -1) {
        descCount[cur].fetch_sub(1, memory_order_acq_rel);
        cur = par[cur];
    }
    
    return true;
}

Why This Works (The Key Insight):

CAS guarantees: Only ONE thread can transition locked[node] from -1 to uid.
If two threads try simultaneously, exactly one CAS succeeds, the other fails.

The double-check pattern:
1. Pre-check ancestors (optimistic — might be stale)
2. CAS claim the node
3. Re-check ancestors (now we own the node, so any NEW ancestor lock
   will see our descCount and fail THEIR ancestor check)
4. If re-check fails → rollback (CAS back to -1, undo counts)

⚠️ The `descCount` Limitation:

Important: The CAS approach above uses descCount (integer counter) instead of set<int>. This means:

Descendant CHECK is O(1) ✅

But for UPGRADE, we can't find WHICH descendants are locked without BFS → O(N) ❌

The set approach is better for upgrade, but sets aren't thread-safe for concurrent writes

You'd need either a concurrent set or per-node locks for the set approach

☕ Java Version with `AtomicInteger`

import java.util.concurrent.atomic.AtomicInteger;

class TreeOfSpace {
    AtomicInteger[] locked;      // -1 = unlocked
    AtomicInteger[] descCount;   // number of locked descendants
    int[] parent;
    
    boolean lock(String name, int uid) {
        int node = nameToIndex.get(name);
        
        // Phase 1: Optimistic checks
        if (descCount[node].get() > 0) return false;
        
        int cur = parent[node];
        while (cur != -1) {
            if (locked[cur].get() != -1) return false;
            cur = parent[cur];
        }
        
        // Phase 2: Atomic claim
        if (!locked[node].compareAndSet(-1, uid)) {
            return false;  // Another thread claimed it
        }
        
        // Phase 3: Validate + Propagate
        cur = parent[node];
        List<Integer> updated = new ArrayList<>();
        boolean conflict = false;
        
        while (cur != -1) {
            descCount[cur].incrementAndGet();
            updated.add(cur);
            
            if (locked[cur].get() != -1) {
                conflict = true;
                break;
            }
            cur = parent[cur];
        }
        
        // Phase 4: Rollback if needed
        if (conflict) {
            for (int anc : updated) {
                descCount[anc].decrementAndGet();
            }
            locked[node].set(-1);
            return false;
        }
        
        return true;
    }
}

📝 What to Say to the Interviewer

"I can make lock() entirely lock-free using CAS. Each node stores its lock state as atomic<int> (-1 = unlocked, uid = locked by that user). The key operation is compare_exchange_strong(-1, uid) — it atomically checks if the node is unlocked and claims it in one CPU instruction (LOCK CMPXCHG). Ancestor descendant counts use atomic<int> with fetch_add/fetch_sub for atomic increments.

I use a validate-after-claim pattern: first optimistically check ancestors, then CAS-claim the node, then re-check ancestors. If any ancestor was locked between my initial check and my claim, I roll back by storing -1 and undoing the counter increments.

This approach has no locks, no context switches, and allows maximum parallelism. The trade-off is complexity in the rollback logic and the ABA problem (which we'd solve with version counters if needed)."

03_atomic_operations.md

⚛️ File 03: Atomic Operations — std::atomic<int>, AtomicInteger, CAS Lock-Free

📖 What is an Atomic Operation? (Simple Explanation)

Why x++ is NOT Atomic

How std::atomic<int> Fixes This

🔧 C++ std::atomic — The Key Operations

1. load() — Read atomically

2. store() — Write atomically

3. fetch_add() / fetch_sub() — Atomic increment/decrement

4. compare_exchange_strong() — THE BIG ONE (CAS)

5. compare_exchange_weak() — Faster but may fail spuriously

☕ Java AtomicInteger — The Java Equivalent