OS Concurrency & Locks: The Ultimate Deep Dive

(Comprehensive Guide tailored for the Juspay Hackathon Part B)

This guide covers everything from the absolute basics of OS threading to advanced lock-free algorithms, packed with C++ code examples and specific applications to your flat-vector Tree of Space architecture.

1. Concurrency Basics: Processes, Threads, and Chaos

Before we talk about locks, we need to understand what we are trying to control.

Process vs. Thread

Process: An executing program. It has its own isolated memory space. If Process A crashes, Process B is fine.
Thread: The unit of execution within a process. Crucially, all threads in a process share the same memory (heap, global variables, vectors). This sharing is what makes multithreading fast, but also dangerous.

The "Context Switch"

Your CPU only has a few cores (e.g., 4 or 8), but runs thousands of threads. The OS achieves this via Context Switching. It lets Thread A run for a few milliseconds, pauses it, saves its state, and lets Thread B run.

This switch can happen at ANY time, even between two halves of a single line of C++ code.

The Race Condition: The "Check-Then-Set" Trap

A Race Condition occurs when multiple threads access shared data simultaneously, and the final result depends on the exact timing of their execution.

Let's look at the classic bug in the Juspay Lock() method:

// Shared state across all threads
vector<int> locked(N, -1); 

bool lockNode(int node, int uid) {
    // 1. CHECK
    if (locked[node] == -1) {  
        
        // --- ⚠️ A CONTEXT SWITCH HAPPENS HERE! ⚠️ ---
        
        // 2. SET
        locked[node] = uid;    
        return true;
    }
    return false;
}

How it fails (Thread Interleaving Trace):

Time	Thread A (Trying to lock Node 5 for uid 1)	Thread B (Trying to lock Node 5 for uid 2)	`locked[5]` Value
T1	Evaluates `locked[5] == -1` (True)		`-1`
T2	(Context Switch - OS pauses Thread A)		`-1`
T3		Evaluates `locked[5] == -1` (True)	`-1`
T4		Sets `locked[5] = 2`	`2`
T5		Returns `true`	`2`
T6	(Thread A resumes)		`2`
T7	Sets `locked[5] = 1`		`1`
T8	Returns `true`		`1`

The Bug: Both threads think they successfully locked the node. Thread B's lock was overwritten (Lost Update).

2. Core OS Synchronization Concepts

To fix this, we need Atomicity. An atomic operation is indivisible—it happens completely or not at all. No context switch can interrupt it halfway.

Mutual Exclusion (Mutex)

A Mutex ensures that only one thread can access a specific piece of code (the Critical Section) at a time.

If Thread A "acquires" the mutex, it enters the critical section.
If Thread B tries to acquire it, Thread B is blocked (put to sleep by the OS) until Thread A releases the mutex.

What is a Mutex Internally? Is it a keyword?

In C++, mutex is not a keyword (like if or while). It is an object (a class instance) provided by the standard library (std::mutex).

Internally, an OS-level mutex is essentially a struct maintained by the Operating System containing two main things:

An atomic integer flag: (e.g., 0 for unlocked, 1 for locked).
A wait queue: A list of thread IDs that are currently waiting for the lock.

How the OS handles it: When a thread calls .lock() on this object:

The CPU uses a hardware-level atomic instruction (like "Test-And-Set") to try and change the flag from 0 to 1.
If it succeeds, the thread continues into the critical section.
If the flag is already 1, the OS intervenes. The OS takes the thread, adds it to the mutex's wait queue, and puts the thread to sleep (removing it from the CPU so it stops consuming power).
When the first thread calls .unlock(), it changes the flag back to 0, and tells the OS to wake up the next thread in the wait queue, moving it back to the CPU to run.

Semaphores vs Mutexes

Mutex: Like a bathroom key. 1 key, 1 person. The person who locks it MUST be the one who unlocks it.
Semaphore: Like a bouncer at a club with a capacity of 5. It holds a counter. wait() decreases the counter, signal() increases it. (A binary semaphore with capacity 1 acts like a mutex, but allows any thread to release it, not just the owner).

3. C++ Implementation: The Standard Way

Let's see how this works in C++.

The Bad Way: Manual `lock()` and `unlock()`

#include <mutex>
std::mutex mtx;
int counter = 0;

void unsafeIncrement() {
    mtx.lock();       // Acquire lock
    
    counter++;
    if (counter == 5) {
        // BUG: We return without unlocking! 
        // Any thread that calls unsafeIncrement() after this will hang FOREVER.
        return; 
    }
    
    mtx.unlock();     // Release lock
}

The Good Way: `std::lock_guard` (RAII)

C++ uses RAII (Resource Acquisition Is Initialization). A std::lock_guard locks the mutex when created, and automatically unlocks it when it goes out of scope, even if an exception is thrown or a return is hit.

void safeIncrement() {
    std::lock_guard<std::mutex> guard(mtx); // Locks immediately
    
    counter++;
    if (counter == 5) {
        return; // guard goes out of scope and unlocks automatically!
    }
} // guard goes out of scope and unlocks automatically!

`std::lock_guard` vs `std::unique_lock`

lock_guard: Simple, lightweight, locks on creation, unlocks on destruction. You cannot manually unlock it early.
unique_lock: Heavier. Allows you to lock(), unlock(), and try_lock() manually while still guaranteeing destruction if you forget.

4. The Vector Gotcha: Mutexes in Arrays

Since you use flat vectors like vector<int> locked, you need a mutex for every node.

Attempt 1: Will NOT compile

// ERROR: std::mutex is not copyable or movable. 
// std::vector requires its elements to be movable when it resizes.
std::vector<std::mutex> nodeLocks(N); 

Solution A: Use std::deque Deques allocate memory in chunks and never move existing elements in memory when resizing.

std::deque<std::mutex> nodeLocks(N); // Works perfectly!

Solution B: Use std::unique_ptr in a Vector

What if you really want to use a vector? You can store pointers to mutexes instead of the mutexes themselves.

What is std::unique_ptr? It is a "smart pointer". Unlike a raw C-style pointer (mutex* m = new mutex()), a smart pointer automatically cleans up and deletes the memory it points to when it goes out of scope, preventing memory leaks. It is "unique" because only one unique_ptr can own the object at a time.
What is std::make_unique? It is a safe helper function that creates the object (allocates memory on the heap) and immediately wraps it in a unique_ptr.
Why this works: You cannot move a mutex itself, but you CAN move a pointer that points to a mutex. When the vector resizes internally, it just shuffles the smart pointers around, while the actual heavy mutex objects stay safely pinned in their original memory locations on the heap.

std::vector<std::unique_ptr<std::mutex>> nodeLocks;
for(int i = 0; i < N; i++) {
    // Dynamically create a mutex on the heap and store the smart pointer
    nodeLocks.push_back(std::make_unique<std::mutex>());
}

// To use it later:
// nodeLocks[5]->lock();  
// Notice we use '->' instead of '.' because we are working with a pointer!

5. Deadlocks in Depth

When you have multiple locks, you introduce the risk of Deadlock.

The 4 Coffman Conditions

A deadlock ONLY happens if all 4 of these are true simultaneously:

Mutual Exclusion: Resources cannot be shared.
Hold and Wait: A thread holds one lock while waiting for another.
No Preemption: The OS cannot forcibly take a lock away from a thread.
Circular Wait: Thread A waits for B, B waits for C, C waits for A.

Preventing Deadlock via Lock Ordering

We prevent deadlocks by breaking condition #4 (Circular Wait). We do this by establishing a strict, universal order in which locks must be acquired.

Example of Deadlock:

std::mutex mtxA, mtxB;

void thread1() {
    std::lock_guard<std::mutex> l1(mtxA);
    // Context switch!
    std::lock_guard<std::mutex> l2(mtxB); // Waits for mtxB forever
}

void thread2() {
    std::lock_guard<std::mutex> l1(mtxB);
    // Context switch!
    std::lock_guard<std::mutex> l2(mtxA); // Waits for mtxA forever
}

The Fix: Always lock mtxA before mtxB. If thread2 tries to lock mtxA first, it simply waits for thread1 to finish. No deadlock.

6. Applying this to the "Tree of Space"

Why not one Global Mutex?

std::mutex globalMutex;
bool lock(int node) {
    std::lock_guard<std::mutex> lock(globalMutex);
    // do work...
}

If you do this, the interviewer will fail you. If Thread A locks a node in Asia, and Thread B wants to lock a node in Africa, they are completely independent. A global mutex forces Thread B to wait, destroying all parallelism.

Fine-Grained Locking & Leaf-to-Root Ordering

When locking a node in Juspay, you must update the node AND its ancestors (lockedDescendants). This means you need to lock the node AND all ancestors.

The Golden Rule: Sort the nodes by depth (deepest first). Lock from Leaf to Root.

bool threadSafeLock(int targetNode, int uid) {
    // 1. Gather all nodes we need to lock (target + ancestors)
    std::vector<int> nodesToLock;
    int curr = targetNode;
    while (curr != -1) {
        nodesToLock.push_back(curr);
        curr = parent[curr];
    }
    
    // 2. Sort them to prevent deadlocks!
    // Since we gathered from target to root, they are already ordered Leaf-to-Root!
    // nodesToLock[0] is deepest.
    
    // 3. Acquire locks in order (DO NOT USE lock_guard here, we need dynamic locking)
    for (int node : nodesToLock) {
        nodeLocks[node].lock();
    }
    
    // --- CRITICAL SECTION START ---
    bool success = false;
    if (canLock(targetNode)) { // Check conditions
        locked[targetNode] = uid;
        // Update ancestors...
        success = true;
    }
    // --- CRITICAL SECTION END ---
    
    // 4. Release locks (order doesn't matter for release, but reverse is good practice)
    for (int node : nodesToLock) {
        nodeLocks[node].unlock();
    }
    
    return success;
}

7. Hackathon "Hard Mode": Spinlocks and Atomics

In Part B, the interviewer will often ban std::mutex. You must build your own synchronization using compiler intrinsics.

Mutex vs. Spinlock

Mutex: If locked, the OS puts the thread to sleep. (High overhead, but doesn't waste CPU).
Spinlock: If locked, the thread runs a while(true) loop asking "Is it unlocked yet?" millions of times a second. (Very fast to acquire, but burns 100% CPU while waiting).

What exactly is "Test-And-Set"?

In our earlier "Check-Then-Set" bug, the problem was that checking the value (reading) and setting the value (writing) were two separate steps. The OS could interrupt the thread in between them.

Test-And-Set (TAS) is a special instruction built directly into the silicon of the CPU (like the XCHG instruction in x86). It allows the CPU to read a memory address AND write a new value to it in a single, indivisible hardware step. At the hardware level, it temporarily locks the memory bus, guaranteeing no other CPU core can touch that memory address until the instruction finishes.

How TAS works logically (but executed atomically):

Read the current value at the memory address.
Write a 1 to that memory address.
Return the old value that was read in step 1.

Why this guarantees safety: Imagine two threads execute the TAS instruction at the exact same picosecond on a flag that is currently 0. Because it's a hardware atomic instruction, the hardware forces one to go first.

Thread A (Winner): Reads 0, writes 1, returns 0. Because it received 0, Thread A knows it successfully claimed the lock.
Thread B (Loser): Executes immediately after. It reads the new 1, writes 1, returns 1. Because it received 1, Thread B knows someone else beat it to the lock, so it must wait.

Building a Spinlock in C++ (The Juspay Expectation)

In C/C++, you can trigger this specific hardware instruction using compiler intrinsics like __sync_lock_test_and_set.

// Our flat vector of spinlock flags (0 = unlocked, 1 = locked)
std::vector<int> spinFlags(N, 0);

void acquire_spinlock(int node) {
    // __sync_lock_test_and_set sets the value to 1, and returns the OLD value.
    // If it returns 1, someone else holds the lock. We spin.
    // If it returns 0, we just set it to 1, meaning we successfully claimed it!
    
    while (__sync_lock_test_and_set(&spinFlags[node], 1) == 1) {
        // Spin wait (Busy loop)
        // Note: In real production, you'd put a _mm_pause() here to save CPU power
    }
}

void release_spinlock(int node) {
    // Atomically sets the flag back to 0
    __sync_lock_release(&spinFlags[node]);
}

Peterson's Algorithm (No Hardware Atomics Allowed)

If the interviewer is exceptionally brutal and bans even hardware atomics, you must use Peterson's Algorithm. It provides mutual exclusion for exactly two threads using only standard variables.

bool flag[2] = {false, false}; // Indicates if thread wants to enter
int turn = 0;                  // Indicates whose turn it is

void lock(int thread_id) { // thread_id is 0 or 1
    int other = 1 - thread_id;
    
    flag[thread_id] = true;    // I want to enter
    turn = other;              // But I will be polite and let the other go first
    
    // Wait ONLY if the other thread wants to enter AND it's their turn
    while (flag[other] == true && turn == other) {
        // Busy wait
    }
}

void unlock(int thread_id) {
    flag[thread_id] = false; // I no longer want to enter
}

(Note: Peterson's algorithm rarely scales to N threads easily without complex arrays, which is why Lamport's Bakery algorithm exists, but Peterson's is the standard interview answer).

locks_primer.md