all_thread_safety_mechanisms.md

🛡️ Tree of Space: Concurrency & Synchronization Deep Dive

Focused Guide for Juspay Part B: Mutex, Peterson's Algorithm, Test-and-Set, Compare-and-Swap, Semaphores, and Condition Variables

📌 Executive Summary & Context

In the Juspay Tree of Space problem, we manage an $M$-ary tree with $N$ nodes where threads call:

  1. lock(node, uid): Lock a node if neither the node, any ancestor, nor any descendant is locked.
  2. unlock(node, uid): Unlock a node if currently locked by uid.
  3. upgradeLock(node, uid): Lock a node and unlock all its locked descendants if at least one descendant is locked, all locked descendants belong to uid, and no ancestor is locked.

During the Juspay Hackathon Part B interview, the discussion progresses systematically through core synchronization concepts:

  • Starting with standard std::mutex (and analyzing its OS overhead).
  • Moving to pure software synchronization: Peterson's Algorithm (when all hardware atomics are banned).
  • Moving to hardware-assisted synchronization: Test-and-Set (TAS) and Compare-and-Swap (CAS) (both conceptual logic functions and real compiler/CPU implementations).
  • Answering critical design questions: Can Semaphores be used? and Can Condition Variables be used?

📑 Table of Contents

  1. 1. Mutual Exclusion (std::mutex) & OS Sleep Overhead
  2. 2. Peterson's Algorithm (Pure Software Solution)
  3. 3. Test-and-Set (TAS) Instruction
  4. 4. Compare-and-Swap (CAS) Instruction
  5. 5. Can Semaphores Be Used or Not?
  6. 6. Can Condition Variables Be Used or Not?
  7. 7. Summary Comparison Table

1. Mutual Exclusion (std::mutex) & OS Sleep Overhead

Concept & Fine-Grained Locking

Wrapping the entire tree in a single global std::mutex serializes all operations. If Thread 1 locks a node in Asia and Thread 2 locks a node in Africa, they do not conflict, yet a global mutex forces Thread 2 to wait.

To preserve concurrency, we assign an individual std::mutex to each node. When locking a node, a thread must acquire locks for the node and all its ancestors up to the root.

  • Deadlock Prevention (Leaf-to-Root Ordering): To prevent circular wait (Coffman Condition 4), all threads must acquire node mutexes in the same universal direction: Leaf to Root.
#include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <string> #include <mutex> #include <memory> using namespace std; unordered_map<string, int> wordToIndex; vector<int> parentNode; vector<int> locked; vector<unordered_set<int>> descendentsLocked; vector<unique_ptr<mutex>> nodeLocks; // N mutexes bool lockWithMutex(const string& name, int uid) { int idx = wordToIndex[name]; // 1. Gather ancestor path (Leaf-to-Root order) vector<int> path; int curr = idx; while (curr != -1) { path.push_back(curr); curr = parentNode[curr]; } // 2. Acquire locks in strict leaf-to-root order (prevents deadlocks) vector<unique_lock<mutex>> locks; for (int node : path) { locks.emplace_back(*nodeLocks[node]); } // 3. Verify conditions inside critical section if (locked[idx] != -1) return false; if (!descendentsLocked[idx].empty()) return false; for (size_t i = 1; i < path.size(); i++) { if (locked[path[i]] != -1) return false; } // 4. Update state and propagate up locked[idx] = uid; for (size_t i = 1; i < path.size(); i++) { descendentsLocked[path[i]].insert(idx); } return true; // Mutexes automatically release when vector 'locks' goes out of scope (RAII) }

Why Interviewers Reject std::mutex: The "OS Sleep Overhead"

Modern std::mutex implementations use futex (Fast Userspace Mutex) on Linux and WaitOnAddress / SRWLock on Windows.

  1. Fast Path (No Contention): An atomic CAS instruction claims the lock in user space in $\sim$1–5 nanoseconds.
  2. Slow Path (Contention / Collision): When two threads contend for the same lock, the waiting thread cannot stay in user space. It issues a system call (sys_futex(FUTEX_WAIT)) asking the OS kernel to put it to sleep.

What Happens When the OS Puts a Thread to Sleep:

  1. Ring Transition: Privilege level escalates from User Mode (Ring 3) to Kernel Mode (Ring 0).
  2. State Change & Queueing: OS changes thread state from TASK_RUNNING to WAITING and enqueues the thread onto the mutex's wait queue.
  3. Context Switch: The OS scheduler swaps CPU registers (RIP, stack pointer, general-purpose registers, SIMD/AVX registers), switches address space page tables (CR3), and runs a different thread.
  4. Waking Up: When the lock is freed, sys_futex(FUTEX_WAKE) moves the thread back to the run queue. The thread must wait for its turn in the OS scheduler.
  5. Cold Cache Penalty: While asleep, other processes run on the CPU core and evict the thread's tree data from L1/L2 caches and TLB. When the thread wakes up, every memory access incurs a slow DRAM read miss ($\sim$50–100 ns).

The Time Scale Comparison:

OperationLatency
Read/Write a variable in L1 cache$\sim$0.5 – 1 ns
Tree of Space Critical Section (Check 5 nodes)$\sim$20 – 40 ns
OS Sleep + Context Switch + Wakeup$\sim$1,000 – 5,000 ns (3,000 – 15,000 CPU cycles)

Interview Summary: Putting a thread to sleep for 3,000 nanoseconds to wait for an operation that finishes in 30 nanoseconds wastes massive CPU resources. That is why low-latency systems prefer user-space spinlocks or lock-free atomic operations.

2. Peterson's Algorithm (Pure Software Solution)

Concept & Why It Is Asked

When an interviewer says:

"Assume the hardware has NO atomic instructions (lock, xchg, cmpxchg do not exist). You only have standard memory reads and writes. How can two threads achieve mutual exclusion?"

Peterson's Algorithm (1981) solves mutual exclusion for 2 threads using only two shared variables:

  1. flag[2]: Boolean array where flag[i] = true means Thread $i$ wants to enter the critical section.
  2. turn: Integer indicating which thread has priority to enter.

The "Politeness" Principle

When Thread 0 wants to lock, it sets flag[0] = true, but politely sets turn = 1 ("you go first"). Thread 0 only waits if Thread 1 also wants to enter (flag[1] == true) AND it is Thread 1's turn (turn == 1).

C++ Implementation

#include <iostream> #include <thread> class PetersonLock { private: // volatile tells the compiler: "Do not cache this in CPU registers. // Always read from and write to main memory." volatile bool flag[2]; volatile int turn; public: PetersonLock() { flag[0] = false; flag[1] = false; turn = 0; } void lock(int threadId) { int other = 1 - threadId; flag[threadId] = true; // 1. Announce intent to enter turn = other; // 2. Be polite: give priority to the other thread // 3. Busy-wait ONLY IF other thread wants to enter AND it is other thread's turn while (flag[other] == true && turn == other) { // Busy wait (spin) } } void unlock(int threadId) { // 4. Release claim flag[threadId] = false; } };

Critical Limitations & Hardware Reality

  1. Strictly 2 Threads: Peterson's algorithm only works for two threads. For $N$ threads, you must use Lamport's Bakery Algorithm.
  2. Modern CPU Out-of-Order Execution: Modern superscalar CPUs (x86, ARM) perform out-of-order execution and memory store buffering. A CPU core can execute turn = other before flag[threadId] = true is flushed to the cache bus. On modern hardware, Peterson's algorithm requires explicit Memory Barriers (std::atomic_thread_fence(std::memory_order_seq_cst)) to prevent CPU store reordering.
  3. Application to Tree of Space: Each node would need an instance of PetersonLock, limiting concurrency to 2 threads per contested node.

3. Test-and-Set (TAS) Instruction

Conceptual Logical Function (What Hardware Does)

The Test-and-Set instruction reads a memory address and writes true (or 1) to it as a single, indivisible hardware operation.

If this were written as regular C++ code, it would look like this:

// CONCEPTUAL SIMULATION (Logical definition of TAS): // In software alone, this is BUGGY because a context switch can happen // between Line 3 and Line 4. // In HARDWARE, the CPU silicon executes both lines as ONE single clock cycle. bool TestAndSet_Conceptual(bool* target) { bool oldValue = *target; // 1. Read current value *target = true; // 2. Write true (1) return oldValue; // 3. Return the value before the write }
  • Why software cannot emulate this without hardware: If Thread A and Thread B call TestAndSet_Conceptual simultaneously, both can read oldValue = false before either sets *target = true. Both would return false (both think they claimed the lock). The hardware guarantees that at the electrical bus level, the memory controller executes the read and write atomically.

Real Built-in & Hardware Implementations

Option A: Custom Compiler Built-in Function (__sync_lock_test_and_set)

The legacy GCC/Clang built-in maps directly to the x86 xchg instruction:

#include <immintrin.h> // for _mm_pause() class CustomTASSpinLock { private: volatile int lockState; // 0 = unlocked, 1 = locked public: CustomTASSpinLock() : lockState(0) {} void lock() { // __sync_lock_test_and_set sets lockState to 1 and returns previous value. // If previous was 1: someone else held it -> continue spinning. // If previous was 0: it was free, we changed it to 1 -> we acquired the lock! while (__sync_lock_test_and_set(&lockState, 1) == 1) { // Test-and-Test-and-Set (TTAS) optimization: // Spin reading from local cache without locking the memory bus while (lockState == 1) { _mm_pause(); // Emits x86 PAUSE instruction to prevent CPU pipeline stalls } } } void unlock() { // Releases the lock with a memory barrier __sync_lock_release(&lockState); } };

Option B: Modern Standard C++ Built-in (std::atomic_flag)

The standard C++11 way to execute TAS:

#include <atomic> class StandardAtomicFlagLock { private: std::atomic_flag flag = ATOMIC_FLAG_INIT; public: void lock() { // test_and_set returns the previous value with acquire memory ordering while (flag.test_and_set(std::memory_order_acquire)) { #if defined(__x86_64__) || defined(_M_X64) _mm_pause(); #endif } } void unlock() { // Clears the flag with release memory ordering flag.clear(std::memory_order_release); } };

Tree of Space Implementation with TAS Spinlock

We maintain a vector of CustomTASSpinLock objects, locking from leaf to root:

#include <vector> #include <string> #include <unordered_set> #include <unordered_map> using namespace std; vector<CustomTASSpinLock> tasNodeLocks; vector<int> pNode; vector<int> nodeLocked; vector<unordered_set<int>> nodeDescLocked; unordered_map<string, int> nameToIndex; bool lockTreeWithTAS(const string& name, int uid) { int idx = nameToIndex[name]; // 1. Gather path vector<int> path; int curr = idx; while (curr != -1) { path.push_back(curr); curr = pNode[curr]; } // 2. Acquire TAS spinlocks in leaf-to-root order for (int node : path) { tasNodeLocks[node].lock(); } // 3. Critical Section bool success = true; if (nodeLocked[idx] != -1) success = false; if (success && !nodeDescLocked[idx].empty()) success = false; if (success) { for (size_t i = 1; i < path.size(); i++) { if (nodeLocked[path[i]] != -1) { success = false; break; } } } // 4. Mutate state if checks passed if (success) { nodeLocked[idx] = uid; for (size_t i = 1; i < path.size(); i++) { nodeDescLocked[path[i]].insert(idx); } } // 5. Release locks in reverse order (root to leaf) for (auto it = path.rbegin(); it != path.rend(); ++it) { tasNodeLocks[*it].unlock(); } return success; }

4. Compare-and-Swap (CAS) Instruction

Conceptual Logical Function (What Hardware Does)

Compare-and-Swap operates on three arguments: a memory location (target), an expected value, and a newValue.

  • If *target == expected, the CPU sets *target = newValue and returns the old value (or true).
  • If *target != expected, the CPU leaves *target unchanged and returns the current value (or false).
// CONCEPTUAL SIMULATION (Logical definition of CAS): // Executed as a SINGLE atomic hardware instruction (CMPXCHG on x86) int CompareAndSwap_Conceptual(int* target, int expected, int newValue) { int oldValue = *target; if (oldValue == expected) { *target = newValue; } return oldValue; // Returns old value so caller knows if swap succeeded }

Real Built-in & Hardware Implementations

Option A: Custom Compiler Built-in (__sync_val_compare_and_swap / __sync_bool_compare_and_swap)

#include <immintrin.h> class CustomCASSpinLock { private: volatile int lockState; // 0 = unlocked, 1 = locked public: CustomCASSpinLock() : lockState(0) {} void lock() { // Attempt to atomically swap 0 -> 1. // __sync_val_compare_and_swap returns the previous value. // If old value != 0, someone else holds the lock -> spin! while (__sync_val_compare_and_swap(&lockState, 0, 1) != 0) { while (lockState == 1) { _mm_pause(); } } } void unlock() { // Atomically set lockState back to 0 __sync_lock_release(&lockState); } };

Option B: Modern Standard C++ Built-in (std::atomic::compare_exchange_strong)

#include <atomic> class StandardCASLock { private: std::atomic<int> state{0}; // 0 = free, 1 = locked public: void lock() { int expected = 0; // If state == expected (0), sets state = 1 and returns true. // If state != expected, updates expected = state and returns false. while (!state.compare_exchange_strong(expected, 1, std::memory_order_acquire, std::memory_order_relaxed)) { expected = 0; // Reset expected before trying again #if defined(__x86_64__) _mm_pause(); #endif } } void unlock() { state.store(0, std::memory_order_release); } };

Tree of Space Implementation with CAS (Lock-Free State Transition)

Instead of using CAS just to build a spinlock, we can use CAS directly for Lock-Free State Transitions on node states without holding mutual exclusion locks:

#include <vector> #include <atomic> #include <string> #include <unordered_map> using namespace std; // Each node directly stores its lock state as an atomic int: -1 = unlocked, >=0 = uid vector<atomic<int>> atomicLocked; // Descendant counts updated atomically vector<atomic<int>> atomicDescCount; vector<int> pArr; unordered_map<string, int> nameIndex; bool lockNodeWithCAS(const string& name, int uid) { int idx = nameIndex[name]; // 1. Optimistic descendant check if (atomicDescCount[idx].load(memory_order_acquire) > 0) { return false; } // 2. Optimistic ancestor check int curr = pArr[idx]; while (curr != -1) { if (atomicLocked[curr].load(memory_order_acquire) != -1) { return false; } curr = pArr[curr]; } // 3. Atomic CAS: Attempt to claim node by transitioning from -1 to uid int expected = -1; if (!atomicLocked[idx].compare_exchange_strong(expected, uid, memory_order_acq_rel, memory_order_acquire)) { // Conflict! Another thread locked this node first return false; } // 4. Atomically propagate descendant count up to root curr = pArr[idx]; vector<int> updatedAncestors; bool conflict = false; while (curr != -1) { atomicDescCount[curr].fetch_add(1, memory_order_acq_rel); updatedAncestors.push_back(curr); // Verification check: did an ancestor get locked while we were propagating? if (atomicLocked[curr].load(memory_order_acquire) != -1) { conflict = true; break; } curr = pArr[curr]; } // 5. Rollback if ancestor collision detected if (conflict) { for (int anc : updatedAncestors) { atomicDescCount[anc].fetch_sub(1, memory_order_acq_rel); } atomicLocked[idx].store(-1, memory_order_release); return false; } return true; }

5. Can Semaphores Be Used or Not?

Short Answer:

A Binary Semaphore CAN be used as a replacement for a mutex, but a Counting Semaphore CANNOT be used to solve Tree of Space locking.

Detailed Technical Breakdown

1. Can a Binary Semaphore (sem_t / std::binary_semaphore) be used?

  • Mechanically: Yes. A binary semaphore initialized with value 1 can guard each node. Calling wait() decrements $1 \to 0$ (lock), and calling signal() / release() increments $0 \to 1$ (unlock).
  • Why it is strongly discouraged in practice:
    1. No Ownership Concept: In a std::mutex, only the thread that acquired the lock is allowed to release it. If Thread A calls lock(), and Thread B attempts to call unlock(), it results in Undefined Behavior or an exception. In a Semaphore, any thread can call release(). If Thread B erroneously signals the semaphore, it accidentally unlocks a critical section held by Thread A!
    2. No Priority Inversion Protection: Operating system mutexes support Priority Inheritance (if a high-priority thread waits on a lock held by a low-priority thread, the OS temporarily boosts the low-priority thread's priority). Semaphores do not support priority inheritance.
    3. Identical OS Sleep Overhead: Semaphores suffer from the exact same OS context-switch and kernel sleep overhead as std::mutex. When wait() blocks, the thread is put to sleep by the kernel.

2. Can a Counting Semaphore be used?

  • NO. A counting semaphore allows up to $K$ concurrent threads to access a resource.
  • The Tree of Space invariant requires strict mutual exclusivity:
    • If a node is locked, 0 ancestors and 0 descendants can be locked.
    • You cannot model ancestor-descendant hierarchy constraints with a simple counter because counting semaphores do not track which specific paths are locked. A counter cannot distinguish between locks in independent subtrees versus conflicting locks on the same branch.

Interview Verdict to State: "We could technically use binary semaphores per node, but they lack ownership semantics and have the same kernel sleep overhead as mutexes. Counting semaphores cannot represent tree hierarchy conflicts. Therefore, semaphores provide no advantage over mutexes or spinlocks."

6. Can Condition Variables Be Used or Not?

Short Answer:

NO, Condition Variables cannot make lock() thread-safe by themselves. They are signaling primitives (wait/notify), not mutual exclusion locks.

Detailed Technical Breakdown

1. What a Condition Variable Actually Is:

A condition variable (std::condition_variable) allows threads to sleep until another thread notifies them that a boolean predicate has changed (e.g., in a Producer-Consumer queue).

  • A condition variable always requires an underlying mutex (std::unique_lock<std::mutex>).
  • It does not protect data from concurrent race conditions on its own.

2. Why Condition Variables Do Not Fit the Tree of Space lock():

  1. The Problem Demands Immediate True/False: The Tree of Space specification states that lock() must return true if successful and false immediately if any condition fails. It is a non-blocking operation. Condition variables are designed for blocking waits (putting a thread to sleep until a condition becomes true).
  2. If we tried to make lock() block until the node is available: Suppose we attempted to make threads wait using cv.wait(lock, [&]() { return canLock(node); }):
    • Deadlock Hazard: If Thread 1 holds an ancestor and waits for a descendant, while Thread 2 holds the descendant and waits for the ancestor, both threads sleep forever in a circular wait.
    • Thundering Herd Problem: When the root unlocks, notifying all waiting threads (notify_all()) wakes up dozens of threads simultaneously, causing massive CPU contention and cache thrashing as they all scramble to re-check the tree.

Interview Verdict to State: "Condition variables are designed for signaling state changes (producer/consumer), not mutual exclusion. They require an accompanying mutex to operate. Furthermore, lock() is a non-blocking operation that returns false on conflict, making condition variable wait-queues fundamentally inapplicable."

7. Summary Comparison Table

MechanismTypeOS Sleep?Threads SupportedHardware RequirementUsable in Tree of Space?Verdict & Role in Interview
std::mutexOS LockYes (futex)ArbitraryAtomic instructionsYesBaseline solution. Usually rejected by interviewers due to context-switch latency.
Peterson's AlgorithmSoftware AlgorithmNo (Spins)Strictly 2None (Plain memory)Yes (Limited)The answer when all hardware atomics are banned. Demonstrates deep OS theory.
Test-and-Set (TAS)Hardware PrimitiveNo (Spins)Arbitraryxchg / TAS instructionYesPrime Juspay answer. Solves the OS sleep overhead via user-space spinlocks.
Compare-and-Swap (CAS)Hardware PrimitiveNoArbitrarycmpxchg / CAS instructionYesAdvanced answer. Allows lock-free state transitions and atomic counters.
Binary SemaphoreOS PrimitiveYesArbitraryAtomic instructionsYes (Discouraged)Functions like a mutex, but lacks ownership checks and priority inheritance.
Counting SemaphoreOS CounterYesUp to $K$Atomic instructionsNOCannot model hierarchical tree dependency constraints.
Condition VariableSignaling QueueYesArbitraryRequires std::mutexNONot a mutual exclusion primitive. Irrelevant for non-blocking lock checks.