03 - Custom Locking & Synchronization Mechanisms

In the Juspay Hackathon, you are frequently forbidden from using std::mutex, synchronized, or standard semaphore libraries. You must build thread-safety from scratch using compiler primitives or logic.

1. Why Naive `std::mutex` is Rejected

If you wrap your entire lock() function in a single global mutex:

std::mutex mtx;
bool lock(Node* n, int uid) {
    mtx.lock();
    // checks and updates
    mtx.unlock();
}

Why it fails the interview: It serializes all operations. If Thread A locks India and Thread B locks USA, they operate on completely independent subtrees, but Thread B must wait for Thread A. This kills concurrency and defeats the purpose of a multicore system.

The Goal: Fine-grained locking. Locking only the specific nodes (and their ancestors) involved in the transaction.

2. Hardware Atomics & Spinlocks

Modern CPUs provide specialized instructions that execute indivisibly (atomically) at the hardware level.

Compare-And-Swap (CAS)

CAS(memory_location, expected_value, new_value) The CPU reads the memory_location. If it equals expected_value, it writes new_value. This entire process cannot be interrupted.

Test-And-Set

__sync_lock_test_and_set(ptr, value) Atomically writes value to the memory address ptr and returns the old value that was there before the write.

Implementing Your Own Spinlock

A spinlock is a lock where the thread simply waits in a while loop ("spins") repeatedly checking if the lock is available.

class SpinLock {
private:
    // volatile tells the compiler: "Do not cache this in a register. 
    // Always fetch it from RAM because another thread might change it."
    volatile int state; // 0 = unlocked, 1 = locked

public:
    SpinLock() : state(0) {}

    void lock() {
        // If state was 0, it becomes 1, loop condition fails (we got the lock!)
        // If state was 1, it stays 1, loop continues spinning.
        while (__sync_lock_test_and_set(&state, 1) == 1) {
            // Spinning. Consumes 100% CPU on this core while waiting.
            // (In real life, we put an x86 PAUSE instruction here to save power)
        }
    }

    void unlock() {
        __sync_lock_release(&state); // Atomically sets state to 0
    }
};

Pros: Very fast for short critical sections (no OS context switch overhead). Cons: Wastes CPU cycles if the lock is held for a long time.

3. Atomic Counters (Lock-Free approach)

Instead of using a lock to update descendantsLocked, use atomic fetch-and-add.

// Atomically increments by 1 and returns the PREVIOUS value
int old_val = __sync_fetch_and_add(&node.descendantsLocked, 1);

// Atomically decrements by 1
__sync_fetch_and_sub(&node.descendantsLocked, 1);

Using this, multiple threads can safely increment a parent's counter without explicit mutexes.

4. Peterson's Algorithm (Pure Software Lock)

If the interviewer bans even compiler hardware atomics, you must use a pure software approach. Peterson's Algorithm guarantees mutual exclusion for two threads without any special hardware instructions.

bool flag[2] = {false, false}; // Intention flags
int turn = 0;                  // Who's turn is it?

void lock(int thread_id) {     // thread_id is 0 or 1
    int other = 1 - thread_id;
    
    flag[thread_id] = true;    // 1. Announce I want the lock
    turn = other;              // 2. Be polite: Give priority to the other thread
    
    // 3. Wait ONLY IF the other thread wants it AND it is the other thread's turn
    while (flag[other] == true && turn == other) {
        // spin
    }
}

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

Note: On modern CPUs, Peterson's algorithm can actually fail due to Out-Of-Order execution by the processor unless Memory Barriers are used, but for interview logic, it proves you understand pure concurrency theory.

5. Read-Write Locks (Shared vs Exclusive)

Used to optimize read-heavy systems.

Read Lock (Shared): Multiple threads can acquire this lock simultaneously, provided no one holds a Write lock.
Write Lock (Exclusive): Only one thread can hold this. Blocks all new readers and writers.

In Tree of Space Context: When locking a node (e.g., India), you must traverse up to Root to check if ancestors are locked.

You can acquire a Read Lock on Asia and Root while checking them. This allows other threads to also verify Asia simultaneously.
You only need a Write Lock on India itself (to change isLocked=true) and on Asia/Root exactly when you are modifying their descendantsLocked counter.

03-custom-locking-mechanisms.md