🔒 File 01: Mutex — What It Is, Internals, and Tree of Space Code

📖 What is a Mutex? (Formal Interview Definition)

What to say directly in the interview: "A Mutex (short for Mutual Exclusion) is a synchronization primitive that grants exclusive access to a shared critical section to at most one thread at a time. It enforces a strict ownership semantic: only the specific thread that successfully acquired (locked) the mutex is legally permitted to release (unlock) it.

A modern OS mutex utilizes a hybrid two-phase approach:

A fast user-space path using an atomic CPU instruction (LOCK CMPXCHG) which completes in ~1-5 nanoseconds under zero contention.

A slow kernel fallback using Linux futex (or Windows WaitOnAddress), where contending threads are put to sleep by the OS scheduler to avoid wasting CPU cycles when the lock is held for a long time."

Intuitive Analogy (Bathroom Door Lock)

Only one person can occupy the room at a time.
When you enter, you lock the door → other people must wait.
When you finish, you unlock the door → the next waiting person enters.
Strict Ownership: Only the person inside can unlock it. (If a third person could unlock it from the outside, that would be a binary semaphore, NOT a mutex).

Thread A calls mutex.lock()   → Thread A acquires lock, enters critical section
Thread B calls mutex.lock()   → Thread B blocked (put to sleep by OS scheduler)
Thread A calls mutex.unlock() → Thread A exits, OS wakes up Thread B to enter

🔬 How Does a Mutex Actually Work Internally?

A modern mutex has two execution paths:

Fast Path (Zero Contention — Lock Is Free)

Step 1: Thread calls mutex.lock()
Step 2: CPU executes atomic instruction: LOCK CMPXCHG
        - LOCK prefix: Asserts CPU bus lock / cache coherency for that line
        - CMPXCHG: "If mutex state is 0 (free), write 1 (locked) and return old value"
Step 3: CMPXCHG succeeds → Thread immediately holds lock (~1-5 nanoseconds).
        Zero OS kernel overhead!

Slow Path (Contention — Someone Else Holds the Lock)

Step 1: Thread calls mutex.lock()
Step 2: CMPXCHG fails (mutex state is already 1)
Step 3: Thread spins briefly in user space (~few hundred cycles) hoping lock frees up
Step 4: If still locked → Thread transitions to Kernel Mode via syscall: futex(FUTEX_WAIT)
Step 5: OS puts thread from RUNNING to WAITING state, adds it to the mutex wait queue,
        and performs a CONTEXT SWITCH to schedule another thread on this CPU core
Step 6: When owner finishes, it calls futex(FUTEX_WAKE)
Step 7: OS wakes the waiting thread, switches back to it, thread acquires lock

📐 The Hardware Formula: Linking Big-O to Real Nanoseconds

How do we convert theoretical Big-O complexity into actual execution time on modern hardware?

The Core Formula:

Actual Wall-Clock Time = (Operations × Cycles_Per_Op / CPU_Clock_Speed) + Memory_Stall_Latency

Hardware Baseline (3.5 GHz CPU):

1 CPU Clock Cycle: ~0.28 nanoseconds
L1 Cache Access: ~1.0 - 1.5 ns (4 cycles)
L2 Cache Access: ~3.5 - 5.0 ns (12-14 cycles)
L3 Shared Cache Access: ~10 - 15 ns (40 cycles)
Main Memory (DRAM Cache Miss): ~60 - 100 ns (200-300 cycles)
OS Thread Context Switch: ~1,000 - 5,000 ns (3,000 - 15,000 cycles)

Calculation for Tree of Space with N = 100,000 (1e5) Nodes:

For an M-ary balanced tree with $M = 2$, Tree Height $H = \log_2(100,000) \approx \mathbf{17\text{ levels}}$.

Inside the critical section of lock():

Self & Descendant Check: 2 memory reads = ~2 ns
Ancestor Check (17 levels up to root): 17 pointer hops × 1.5 ns (L1/L2 cache hit) = ~25 ns
Ancestor Update (17 levels up to root): 17 pointer hops × 1.5 ns = ~25 ns
ALU Arithmetic & Branch checks: ~35 instructions × 0.3 ns = ~10 ns

Scenario	Critical Section Time	What It Means
Warm Cache (L1/L2 Hits)	30 to 60 nanoseconds	Upper tree levels stay hot in CPU cache
Cold Cache (DRAM Misses)	500 to 800 nanoseconds	Worst case when reading cold nodes from RAM
OS `std::mutex` Context Switch	2,000 to 5,000 nanoseconds	Cost of sleeping and waking up via kernel

💡 The Interview Takeaway: Our critical section takes only ~30 to 60 nanoseconds. Putting a thread to sleep with an OS std::mutex costs ~3,000 nanoseconds in context-switch overhead! Sleeping for 3,000 ns to wait for a 50 ns task is 60× slower than spinning. That is why custom spinlocks or lock-free atomic designs win here.

🧱 The Internal Structure of a Mutex (C++ / Linux)

┌──────────────────────────────────────────────┐
│                  std::mutex                  │
│                                              │
│  ┌─────────────┐                             │
│  │ state (int) │ ← 0=unlocked, 1=locked     │
│  └─────────────┘                             │
│                                              │
│  lock():                                     │
│    ┌───────────────────┐   SUCCESS           │
│    │ LOCK CMPXCHG 0→1  │──────────► ACQUIRED │
│    └───────────────────┘                     │
│            │ FAIL                            │
│            ▼                                 │
│    ┌───────────────┐                         │
│    │ Spin (retry)  │ ← tries a few times     │
│    └───────────────┘                         │
│            │ STILL FAIL                      │
│            ▼                                 │
│    ┌─────────────────────┐                   │
│    │ futex(FUTEX_WAIT)   │ ← syscall         │
│    │ Thread goes to SLEEP│                   │
│    └─────────────────────┘                   │
│                                              │
│  unlock():                                   │
│    ┌───────────────┐                         │
│    │ state = 0     │ (atomic store)          │
│    └───────────────┘                         │
│            │                                 │
│            ▼                                 │
│    ┌─────────────────────┐                   │
│    │ futex(FUTEX_WAKE)   │ ← wake waiters    │
│    └─────────────────────┘                   │
└──────────────────────────────────────────────┘

🌳 Why Use Mutex Here? (Tree of Space Context)

In the Tree of Space problem, when two threads try to lock nodes that share an ancestor, they can corrupt shared data:

Same node race → Both read "unlocked", both write "locked" → TOCTOU bug
Ancestor-descendant race → One thread checks ancestor unlocked, another locks it mid-check
Shared data corruption → Two threads insert into the same set concurrently → memory corruption

A mutex prevents ALL of these by ensuring only one thread can access the critical section at a time.

❌ Solution 1: Global Mutex (REJECTED — Kills Parallelism)

#include <mutex>

mutex globalMutex;

bool lock(int node, int uid) {
    lock_guard<mutex> guard(globalMutex);  // Entire function is locked
    
    if (locked[node] != -1) return false;
    if (!lockedDescendants[node].empty()) return false;
    
    int cur = parent[node];
    while (cur != -1) {
        if (locked[cur] != -1) return false;
        cur = parent[cur];
    }
    
    locked[node] = uid;
    propagateUp(node, node, true);
    return true;
}

Why This is Bad:

Thread 1 wants to lock China (under Asia)
Thread 2 wants to lock Egypt (under Africa)
→ They are in COMPLETELY DIFFERENT subtrees
→ But with global mutex, Thread 2 WAITS for Thread 1 to finish
→ Parallelism = ZERO

Interviewer will say: "You can't lock the complete tree. Multiple threads should work on different parts simultaneously."

✅ Solution 2: Per-Node Mutex (THE CORRECT MUTEX ANSWER)

Each node gets its own mutex. A thread only locks the nodes on its path to the root.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <mutex>
#include <memory>
#include <queue>

using namespace std;

// ============ GLOBAL DATA STRUCTURES ============
int N, M;
unordered_map<string, int> nameToIndex;
vector<vector<int>> adj;           // adj[i] = children of node i
vector<int> par;                   // par[i] = parent of node i (-1 for root)
vector<int> locked;                // locked[i] = uid or -1
vector<unordered_set<int>> lockedDesc;  // lockedDesc[i] = set of locked descendant indices
vector<unique_ptr<mutex>> nodeMutex;    // ONE mutex per node

// ============ TREE BUILDING ============
void buildTree(vector<string>& names, int m) {
    N = names.size();
    adj.resize(N);
    par.resize(N, -1);
    locked.resize(N, -1);
    lockedDesc.resize(N);
    nodeMutex.resize(N);
    
    for (int i = 0; i < N; i++) {
        nameToIndex[names[i]] = i;
        nodeMutex[i] = make_unique<mutex>();
    }
    
    // BFS-order tree construction
    queue<int> q;
    q.push(0);
    int idx = 1;
    while (!q.empty() && idx < N) {
        int cur = q.front(); q.pop();
        for (int i = idx; i < min(N, idx + m); i++) {
            adj[cur].push_back(i);
            par[i] = cur;
            q.push(i);
        }
        idx += m;
    }
}

// ============ THREAD-SAFE LOCK (PER-NODE MUTEX) ============
bool lockNode(const string& name, int uid) {
    int node = nameToIndex[name];
    
    // Step 1: Gather the path from node to root
    vector<int> path;
    int cur = node;
    while (cur != -1) {
        path.push_back(cur);
        cur = par[cur];
    }
    
    // Step 2: Acquire mutexes in LEAF-TO-ROOT order (prevents deadlocks)
    // Why leaf-to-root? If Thread A locks China→Asia→World and
    // Thread B locks India→Asia→World, they acquire in the same direction.
    // No circular wait = no deadlock.
    vector<unique_lock<mutex>> locks;
    for (int p : path) {
        locks.emplace_back(*nodeMutex[p]);
    }
    
    // ===== CRITICAL SECTION START =====
    // Now we hold exclusive access to the entire path.
    // No other thread can read or write any node on this path.
    
    // Check 1: Is node itself already locked?
    if (locked[node] != -1) return false;
    // (locks auto-release when function returns via RAII)
    
    // Check 2: Any descendant locked? (O(1) with the set)
    if (!lockedDesc[node].empty()) return false;
    
    // Check 3: Any ancestor locked?
    for (int i = 1; i < (int)path.size(); i++) {
        if (locked[path[i]] != -1) return false;
    }
    
    // All checks pass → Lock the node
    locked[node] = uid;
    
    // Propagate: inform all ancestors
    for (int i = 1; i < (int)path.size(); i++) {
        lockedDesc[path[i]].insert(node);
    }
    
    // ===== CRITICAL SECTION END =====
    return true;
    // All mutexes auto-release here (vector of unique_lock goes out of scope)
}

// ============ THREAD-SAFE UNLOCK ============
bool unlockNode(const string& name, int uid) {
    int node = nameToIndex[name];
    
    vector<int> path;
    int cur = node;
    while (cur != -1) {
        path.push_back(cur);
        cur = par[cur];
    }
    
    vector<unique_lock<mutex>> locks;
    for (int p : path) {
        locks.emplace_back(*nodeMutex[p]);
    }
    
    if (locked[node] != uid) return false;
    
    locked[node] = -1;
    for (int i = 1; i < (int)path.size(); i++) {
        lockedDesc[path[i]].erase(node);
    }
    
    return true;
}

Why This Preserves Parallelism:

Thread 1: lock(China, 1)  → acquires mutexes on [China, Asia, World]
Thread 2: lock(Egypt, 2)  → acquires mutexes on [Egypt, Africa, World]

China and Egypt's paths only overlap at World.
Thread 1 and Thread 2 can proceed in parallel until they both try to
acquire World's mutex. Then one waits briefly while the other finishes.

But if they were locking nodes in completely separate subtrees with
no shared ancestor (different trees), they'd never block each other!

⚠️ The Upgrade Deadlock Trap

lock(China) acquires: China → Asia → World    (LEAF TO ROOT)
upgrade(Asia) needs:  Asia → China             (ROOT TO LEAF — finding descendants!)

Thread 1: upgrade(Asia) — holds Asia's mutex, wants China's mutex
Thread 2: lock(China)   — holds China's mutex, wants Asia's mutex
→ CIRCULAR WAIT → DEADLOCK!

Fix: Global Node ID Ordering

Instead of leaf-to-root, always acquire mutexes in increasing order of node index (BFS level order).

China = index 3, Asia = index 1, World = index 0
Both lock(China) and upgrade(Asia) acquire in order: [0, 1, 3]
No circular wait possible!

📝 What to Say to the Interviewer

"I'll give each node its own mutex. When locking node X, I acquire the mutex on X and every ancestor up to the root, always in leaf-to-root order to prevent deadlocks. Two threads operating on independent subtrees proceed in parallel — they only contend when their paths share a common ancestor. The trade-off is that std::mutex uses OS futex under contention, which means kernel transitions and context switches that take ~3000 ns, much longer than our ~30 ns critical section. If you want to avoid that overhead, I can build a custom spinlock."

01_mutex_explained.md