🔒 OS 04: Concurrency, Synchronization & Performance Trade-offs (Juspay 7-Hour Gauntlet)

Targeted for: Juspay Hackathon Part B Core Technical Challenge & 7+ Hour In-Depth Systems Grilling
Mastering the 7 Core Challenged Topics:

1. Concurrency Fundamentals & Memory Models
2. Race Conditions Deep Dive (Data Race vs Race Condition, TOCTOU, Lost Update, ABA, 8 Tree Races)
3. Atomic Operations & Hardware Primitives (TAS, CAS, LL/SC, Memory Fences, volatile vs atomic)
4. Mutexes, Locks & Low-Level Primitives (Mutex internals, Futex, Spinlocks, Ticket Locks, Adaptive Mutexes)
5. Shared vs Exclusive Locking (Reader-Writer locks, Reader/Writer Priority, Starvation, Lock Upgrading)
6. Synchronization Strategies (Coarse vs Fine-Grained, Lock Coupling, Hierarchical Ordering, OCC / Set-and-Test, Lock-Free vs Wait-Free)
7. Performance Trade-offs & Hardware Contention (Latency vs Throughput, Cache Bouncing, False Sharing, Convoy Effect, Priority Inversion, Amdahl's Law)

📑 Table of Contents

1. Topic 1: Concurrency Fundamentals & Memory Models
2. Topic 2: Race Conditions Deep Dive
3. Topic 3: Atomic Operations & Hardware Primitives
4. Topic 4: Mutexes, Locks & Low-Level Primitives
5. Topic 5: Shared vs Exclusive Locking (Reader-Writer Locks)
6. Topic 6: Synchronization Strategies & Paradigms
7. Topic 7: Performance Trade-offs & Hardware Contention
8. Juspay Part B Application: Tree-of-Space Concurrency Invariants
9. The 7-Hour Interview Defense Script (Verbatim Spoken Answers)

1. ⚙️ Concurrency Fundamentals & Memory Models

Concurrency vs. True Parallelism

• Concurrency: Dealing with multiple tasks at the same time by interleaving execution on one or more CPU cores (virtual overlap). Managed via time-slicing and OS context switching.
• Parallelism: Executing multiple computational tasks simultaneously on physically distinct CPU cores (true hardware overlap).

The Modern Hardware Memory Reality

On a modern multi-core x86/ARM system:

1. Each CPU core has private L1 Data/Instruction Caches (~32KB) and L2 Cache (~512KB).
2. All cores share an L3 Cache (~16MB–64MB) and Main Memory (DRAM).
3. Each core has a private Store Buffer and Invalidation Queue to decouple execution speed from slow memory writes.

Why Naive Code Fails: 3 Layers of Reordering

Code does not execute in the order you wrote it in C++:

1. Compiler Reordering: The compiler's optimizer reorders loads and stores, eliminates writes perceived as redundant, and hoists variables into registers.
2. CPU Out-of-Order (OoO) Execution: Hardware execution units reorder memory instructions to maximize pipeline utilization (e.g., executing an independent load while waiting for a cache miss on a store).
3. Memory Subsystem Visibility: Stores sitting in Core 0's private store buffer are invisible to Core 1 until flushed to coherent L1/L3 cache lines.

C++11 Memory Ordering Model

Memory operations on std::atomic<T> accept explicit ordering tags:

2. 💥 Race Conditions Deep Dive

Data Race vs. Race Condition (Crucial Interview Distinction!)

Interviewers frequently ask candidates to define the exact difference:

• Data Race (Hardware / Language Level): Two threads access the same memory location concurrently without synchronization, where at least one access is a write. In C++, this is Undefined Behavior (UB) at the compiler/CPU level.
• Race Condition (Program Logic / Semantic Level): A flaw in execution timing or sequence where the correctness of a program depends on the non-deterministic scheduling of threads. A program can be 100% free of data races (using atomics/locks everywhere) and still suffer from severe race conditions (e.g., TOCTOU logic bugs).

The 8 Classic Race Conditions in Concurrent Trees

1. The Lost Update Race (lockedDescCount++ or counter++)

• Trigger: Two sibling threads (China and India) simultaneously update their shared parent's (Asia) counter.
• Assembly Reality: Increment is 3 instructions: mov eax, [counter], add eax, 1, mov [counter], eax.
• Result: If interleaved, both read 0, both compute 1, both write 1. Asia registers only 1 locked descendant instead of 2.

2. Check-Then-Act / TOCTOU (Time-of-Check to Time-of-Use)

• Trigger: Two threads try to lock the exact same node (India).
• Flaw: Both evaluate if (locked[4] == -1) simultaneously before either writes locked[4] = uid.
• Result: Both threads pass the check and return true. One silently overwrites the other.

3. Shared Container Corruption (Sibling Set Collision)

• Trigger: Two threads concurrently call lockedDescendants[Asia].insert(3) and .insert(4).
• Flaw: std::unordered_set is a complex node-based hash table with dynamic bucket arrays. Concurrent writes cause memory corruption, dangling bucket pointers, or infinite loops during traversal.

4. Ancestor-Descendant Inversion (Cross-Hierarchy Race)

• Trigger: Thread 1 calls lock(World). Thread 2 calls lock(Asia).
• Flaw: Thread 1 verifies World has no locked descendants (Pass). Context switch. Thread 2 checks if Asia has locked ancestors (World is still -1, Pass). Both proceed to lock.
• Result: Invariant shattered: World is locked AND its child Asia is locked.

5. The "Ghost Lock" False Rejection (Lock vs. Unlock)

• Trigger: Thread 1 calls unlock(India). Thread 2 calls lock(World).
• Flaw: Thread 1 sets locked[India] = -1 but gets preempted before removing India from World.lockedDescendants. Thread 2 checks World.lockedDescendants, sees India still present, and returns false.
• Result: False rejection of a valid lock request.

6. Stale Ancestor Read (Delayed Memory Visibility)

• Trigger: Thread 1 unlocks World. Thread 2 calls lock(India).
• Flaw: Thread 1's store locked[World] = -1 remains in Core 0's store buffer. Core 1 reads its own stale L1 cache copy (locked[World] == uid).
• Result: Thread 2 falsely rejects due to stale cache visibility.

7. Double-Unlock Counter Underflow

• Trigger: Two threads concurrently call unlock(India, uid=5).
• Flaw: Both pass if (locked[India] == 5) and both walk up to decrement ancestors' counters.
• Result: Ancestor counter drops from 1 to -1. Because future lock checks test if (lockedDescCount > 0), the negative counter permanently corrupts the tree logic.

8. UpgradeLock Hijack / Interleaved Window Race

• Trigger: Thread 1 calls upgrade(Asia, uid=9) on Asia with locked children China and India.
• Flaw: Thread 1 unlocks China and India. Context switch. Thread 2 calls lock(China, uid=2). Because China is now -1, Thread 2 locks it. Thread 1 resumes and locks Asia.
• Result: Subtree containment invariant broken: Asia is locked by User 9, while its child China is locked by User 2.

The ABA Problem in Lock-Free Architectures

Suppose a concurrent stack uses Compare-And-Swap (CAS) on a Top pointer:

1. Thread 1 wants to pop A. It reads top = A and next = A->next (B).
2. Thread 1 is preempted before executing CAS.
3. Thread 2 pops A, pops B, frees B, and then pushes A back onto the stack (reusing node A's address from an allocator free-list).
4. Stack is now: [ A ] -> [ C ].
5. Thread 1 wakes up and executes CAS(&top, expected=A, new=B).
6. Since current top matches A, the CAS succeeds!
7. Catastrophe: top is set to B, which is already freed/corrupted memory.

The Fix: Tagged Pointers / Version Counters

Combine the pointer with a 64-bit monotonically incrementing sequence number:

3. 🔬 Atomic Operations & Hardware Primitives

What Makes an Operation Atomic at the Silicon Level?

On single-core CPUs, atomicity was achieved by temporarily disabling interrupts (cli/sti).
On modern multi-core processors, interrupts cannot stop another physical core. Instead, hardware atomicity is implemented via:

1. Cacheline Locking (MESI Snooping):
   • Modern x86 processors use the Cache Coherency Protocol (MESI).
   • When an atomic instruction (like LOCK CMPXCHG) is executed, the core requests Exclusive (E) or Modified (M) ownership of the target cacheline.
   • While the read-modify-write completes, the cache controller refuses all snoop requests from other cores for that specific 64-byte cache line.
2. Bus Locking (Fallback):
   • If the memory operand crosses a 64-byte cacheline boundary (an unaligned atomic), the processor asserts the physical LOCK# signal on the system interconnect bus, halting all memory transactions from all other cores across the entire CPU. (Extremely expensive: ~100ns penalty).

Primitive 1: Test-and-Set (TAS)

Atomically sets a variable to a new value and returns its old value:

• Hardware instruction: On x86, compiles to XCHG [rdi], eax (which carries an implicit LOCK prefix).

🛠️ What If the Interviewer BANS __sync_lock_test_and_set?

Interviewers in Juspay Part B often push candidates down the stack:
"You cannot use GCC intrinsics like __sync_lock_test_and_set. How do you implement it yourself?"

Here are the 3 progressive fallback levels to present:

Level 1: Standard C++11 <atomic> / std::atomic_flag

If legacy GCC built-ins are banned, use the portable C++11 standard library:

Level 2: Inline Assembly (asm volatile) on Bare Metal (x86-64)

If the interviewer bans <atomic> headers and intrinsics altogether, write the machine instructions directly in C++ using inline assembly:

Explain This to the Interviewer:
"On x86, the xchg instruction atomically swaps a CPU register with a memory address. The hardware automatically asserts a cacheline lock for the duration of the swap. By specifying the \"memory\" clobber, we instruct the compiler not to reorder any memory accesses across this boundary."

Level 3: Pure Software Algorithms (When ALL Atomics & Assembly Are Banned)

If the interviewer says: "No atomics, no assembly, no intrinsics whatsoever. Just pure integers and standard variables."

1. For 2 Threads: Use Peterson's Algorithm (covered in Section 5 with flag[2] and turn).
2. For N Threads: Use Lamport's Bakery Algorithm (pure software mutual exclusion for arbitrary $N$ threads using ticket numbers):

3. The Juspay "Set-and-Test" Optimistic Pattern (lockedCount): Instead of checking before locking, blindly claim the node first by incrementing an integer counter:
   // Set-and-Test Pattern: lockedCount[node]++; // 1. Set (blindly claim) if (lockedCount[node] > 1) { // 2. Test: did another thread also claim it? lockedCount[node]--; // Conflict detected -> Rollback return false; }
   (Note: Set-and-test can still suffer from multi-node interleaving edge cases, but demonstrating this pattern shows deep algorithmic thinking when hardware primitives are strictly prohibited).

Primitive 2: Compare-and-Swap (CAS)

The foundation of all lock-free data structures. Compares the value at ptr with expected. If equal, writes desired and returns true. Otherwise, updates expected with the actual value and returns false.

Architecture Mapping:

• x86: Uses a single CISC instruction: LOCK CMPXCHG.
• ARM / RISC-V: Uses Load-Linked / Store-Conditional (LL/SC) pairs (LDREX/STREX on ARM). LDREX loads a value and monitors the address. STREX only writes if no other core modified that address since the LDREX.

Primitive 3: Fetch-and-Add (FAA)

Atomically adds a value and returns the original value:

• On x86, compiles to LOCK XADD [rdi], eax.
• Significantly more scalable than CAS loops under high contention because it never suffers from CAS retry failures.

Why volatile is NOT Atomic in C/C++

Candidates frequently confuse Java's volatile with C/C++'s volatile:

• In Java: volatile guarantees memory visibility AND establishes a happens-before memory barrier (similar to acquire-release semantics).
• In C/C++: volatile only informs the compiler: "Do not optimize away reads/writes to this variable; do not cache it in a CPU register".
• What C/C++ volatile LACKS:
  1. Zero Atomicity: volatile int x; x++ still compiles to 3 separate instructions.
  2. Zero Memory Fences: The CPU hardware will still reorder surrounding loads and stores.
  3. Zero Cache Coherency Control: Does not force cache flushes across multi-core interconnects.

4. 🛡️ Mutexes, Locks & Low-Level Primitives

Synchronization Primitives Taxonomy

The Futex (Fast Userspace Mutex - Linux Standard)

How modern pthread_mutex and std::mutex work under Linux:

1. Uncontended Fast-Path (Userspace - 0 Syscalls):
   • Thread executes an atomic CAS (CMPXCHG) to flip a 32-bit integer in userspace memory from 0 (unlocked) to 1 (locked).
   • Time taken: ~10–15 nanoseconds.
2. Contended Slow-Path (Kernel Fallback):
   • If CAS fails (state already 1), the thread sets the state to 2 (locked with waiters) and invokes the Linux system call:
     sys_futex(&futex_word, FUTEX_WAIT, 2, NULL, NULL, 0);
   • The Linux kernel puts the thread into TASK_INTERRUPTIBLE sleep, moves its PCB to the kernel futex wait-queue, and switches CPU execution to another thread.
   • When unlocking, if state was 2, the releasing thread calls:
     sys_futex(&futex_word, FUTEX_WAKE, 1, NULL, NULL, 0);
     waking up one sleeping waiter.

Production Custom Spinlock Implementation with PAUSE

[!TIP] Why _mm_pause() / PAUSE instruction?
In a tight spin loop, the processor's aggressive speculative execution pipeline predicts loop branches, filling execution slots with speculative loads. When the lock is finally released, a pipeline flush penalty occurs (~40–100 cycles). The PAUSE instruction introduces a tiny architectural delay (~10ns), de-pipelines the loop, saves power, and prevents memory bus saturation.

The Ticket Lock (Eliminating Starvation in Spinlocks)

Standard spinlocks are unfair: when a lock is released, whichever core happens to win the bus arbitration grabs it, leading to thread starvation.
A Ticket Lock enforces FIFO fairness (like a bakery ticket dispenser):

5. 📖 Shared vs Exclusive Locking (Reader-Writer Locks)

In read-heavy systems, allowing multiple concurrent readers dramatically enhances throughput.

C++11 / C++14 Standard Implementation

Reader vs. Writer Priority & Starvation

Lock Upgrading & Downgrading Pitfalls

• Lock Downgrade (Safe): A thread holding an Exclusive lock transitions to a Shared lock by acquiring the shared state before releasing the exclusive state. This preserves atomic continuity.
• Lock Upgrade (Dangerous / Deadlock Trap):
  • Thread A holds a Shared lock and wishes to upgrade to Exclusive.
  • Thread B also holds a Shared lock and wishes to upgrade to Exclusive.
  • Thread A waits for Thread B to release its Shared lock.
  • Thread B waits for Thread A to release its Shared lock.
  • Result: Instant Deadlock.
  • Rule: Never attempt in-place lock upgrading without an explicit Try-Upgrade or atomic release-and-reacquire mechanism.

Can We Use Shared Locks in Tree-of-Space?

Interviewers often ask: "Can we acquire Shared Locks on all ancestors while checking, and only Exclusive Lock on the target node?"

The Subtle Trap:

1. When Thread 1 is locking node India, it checks ancestors Asia and World. If it only acquires shared_lock on Asia, Thread 2 can also acquire shared_lock on Asia.
2. However, once Thread 1 passes validation, it must update Asia.lockedDescendants.insert(India).
3. Inserting into lockedDescendants is a mutation (write)! A shared lock is insufficient for mutation.
4. If Thread 1 tries to upgrade its shared lock on Asia to an exclusive lock while Thread 2 also holds a shared lock on Asia, both threads deadlock.
5. Conclusion: Because locking a leaf node requires writing to ancestors' lockedDescendants sets/counters, ancestors must be protected with Exclusive locks during the modification phase.

6. 🗺️ Synchronization Strategies & Paradigms

1. Coarse-Grained vs. Fine-Grained Locking

• Coarse-Grained: Single mutex protecting the entire tree. Trivial correctness, but scales to exactly 1 core. On a 64-core machine, 98% of compute capacity is wasted.
• Fine-Grained: Mutex per node. Allows independent subtrees (e.g., Asia vs. Africa) to lock concurrently. Requires strict lock-ordering protocols to prevent deadlocks.

2. Lock Coupling / Hand-Over-Hand Locking

Used during linked list or B-tree traversal:

• Acquire Lock on Node $N$.
• Acquire Lock on Child $N+1$.
• Release Lock on Node $N$.
• Advantage: Prevents another thread from deleting or inserting ahead of the current traversal point without holding locks on the entire path.

3. Hierarchical Partial Ordering (Leaf-to-Root)

To eliminate Coffman's 4th condition (Circular Wait), locks must be acquired in a globally consistent linear sequence.
In Tree of Space, acquiring locks strictly from deepest node (Leaf) to shallowest node (Root) defines a DAG topological order. Circular wait becomes mathematically impossible.

4. Optimistic Concurrency Control (OCC) / Set-and-Test

Instead of locking upfront:

1. Read: Inspect tree state without holding locks.
2. Validate: Verify that no intervening writes invalidated the conditions.
3. Commit or Abort: If valid, apply atomic write. If invalid, roll back and retry.

• Limitation in Tree-of-Space: Because ancestor paths span multiple nodes and standard C++ containers (unordered_set) are not thread-safe for reads during concurrent writes, pure OCC without hardware transactional memory (HTM) leads to data races and complex rollback cascades.

5. Lock-Free vs. Wait-Free vs. Obstruction-Free

Interviewers probe candidates on theoretical concurrency guarantees:

1. Obstruction-Free: A thread is guaranteed to make progress only if all other competing threads are suspended.
2. Lock-Free: At least one thread in the system is guaranteed to make forward progress in a finite number of steps, regardless of thread scheduling. (System-wide progress; individual threads may starve).
3. Wait-Free: Every thread is guaranteed to complete its operation in a bounded number of execution steps, regardless of contention or other threads' actions. (Zero starvation; uses atomic FAA or array-based reservation rings).

7. 🏎️ Performance Trade-offs & Hardware Contention

1. Latency vs. Throughput

• Uncontended Lock Latency: Cost of acquiring a lock when no other thread is competing (~10–25ns for atomic instruction).
• Contended Lock Latency: Cost when multiple threads fight for the lock. Incurs OS sleep/wake context switches (~2,000–5,000ns) or burning 100% CPU in spinlocks.
• Throughput: Total completed operations per second across all cores. High contention causes throughput to collapse below single-threaded performance due to cache invalidation storms.

2. Cache Contention & Cache-Line Bouncing (MESI Protocol Collapse)

When Core 0 modifies an atomic variable lock_flag:

1. Core 0 broadcasts an Invalidate transaction across the interconnect bus.
2. Core 1, Core 2, Core 3 have their local L1 cache copies forced from Shared (S) to Invalid (I).
3. When Core 1 attempts to spin on lock_flag, it suffers an immediate L1 Cache Miss.
4. The 64-byte cache line must bounce across the system interconnect bus from Core 0 to Core 1.
5. With 16 cores spinning on the same atomic variable, the memory bus saturates with cache-line invalidation traffic. This is called Cache-Line Bouncing.

3. False Sharing: The Silent Performance Killer

Modern CPUs manage memory in chunks of 64 bytes (Cache Lines).
If two independent variables used by two different cores reside within the same 64-byte block, modifying one variable invalidates the entire cache line for the other core!

Even though Core 0 and Core 1 are accessing completely independent variables, their L1 caches repeatedly invalidate each other, causing performance drops of up to 20x–50x.

The Fix: Hardware Alignment

4. The Convoy Effect: Lock Convoy vs. CPU Scheduling Convoy

In Operating Systems, the term "Convoy Effect" appears in two distinct contexts:

A. In CPU Scheduling (The Classic FCFS Definition):

• What it is: In First-Come, First-Served (FCFS) scheduling, a CPU-bound process with a huge burst time gets the CPU first. Multiple short I/O-bound processes with small burst times are trapped in the Ready Queue waiting behind it.
• Analogy: A row of fast sports cars stuck behind a slow truck on a single-lane highway.
• Impact: Average waiting time skyrockets, and I/O devices sit completely idle while the CPU-heavy process runs.

B. In Concurrency & Multithreading (The "Lock Convoy"):

• What it is: When multiple threads of equal priority frequently compete for the same lock.
• The Chain Reaction: If the lock holder is preempted by the OS scheduler (e.g., timeslice expires or an I/O page fault occurs while holding the lock), all other threads pile up behind the lock and are put to sleep.
• The Aftermath: Even after the lock is released, threads wake up, contend, context-switch, and immediately fall back into queue behind the next holder. The threads become synchronized into a "convoy" where context-switching overhead dominates and system throughput collapses.

5. Priority Inversion & Priority Inheritance

• The Problem:
  1. Low-priority Thread $L$ acquires Mutex $M$.
  2. High-priority Thread $H$ preempts $L$ and attempts to acquire $M$. $H$ blocks.
  3. Medium-priority Thread $M_{ed}$ preempts $L$ (because $M_{ed} > L$).
  4. $M_{ed}$ runs for a long duration, preventing $L$ from ever finishing or releasing $M$.
  5. Result: A medium-priority task indirectly starves a high-priority task! (Famous cause of the 1997 Mars Pathfinder spacecraft reset bug).
• The Solution: Priority Inheritance Protocol:
  • When Thread $H$ blocks on Mutex $M$ held by Thread $L$, the OS temporarily elevates the priority of Thread $L$ to match Thread $H$.
  • Thread $L$ runs without being preempted by $M_{ed}$, quickly finishes, releases $M$, and its priority returns to normal. $H$ immediately acquires $M$.

6. Amdahl's Law Scaling Limit

Amdahl's Law defines the maximum theoretical speedup $S$ of a program on $N$ cores:

$$S(N) = \frac{1}{(1 - p) + \frac{p}{N}}$$

• $p$: Fraction of code that can be parallelized.
• $(1 - p)$: Fraction of code that is strictly sequential (lock acquisition, root node verification).

$$\lim_{N \to \infty} S(N) = \frac{1}{1 - p}$$

• Example: If your fine-grained locking strategy leaves just 5% of the execution serialized at common ancestors (like the Root node): $$\text{Max Theoretical Speedup} = \frac{1}{0.05} = 20\times$$ Even if you run on a 1,000-core supercomputer, your application will never exceed a $20\times$ speedup! This proves why minimizing lock hold times and critical section size is paramount.

8. 🌲 Juspay Part B Application: Tree-of-Space Concurrency Invariants

Problem Invariants:

1. A node $X$ can only be locked if:
   • $X$ itself is unlocked.
   • No ancestor of $X$ is locked.
   • No descendant of $X$ is locked.
2. Concurrent operations on disjoint subtrees (e.g., India and Europe) must proceed in parallel without blocking each other.

Correct Production-Grade C++ Implementation:

9. 🎙️ The 7-Hour Interview Defense Script (Verbatim Spoken Answers)

Question 1: "Why did you acquire locks on ancestors before checking conditions? Can't we check first to optimize?"

Say This:
"No. Checking conditions before acquiring locks introduces a classic TOCTOU (Time-of-Check to Time-of-Use) race condition. If two threads check locked[idx] == -1 simultaneously, both see the node as unlocked, both pass validation, and both acquire the lock sequentially, causing one thread to silently overwrite the other.
Furthermore, checking lockedDescendants.size() without holding a lock causes an unsynchronized read on a std::unordered_set while another thread may be calling .insert(). In C++, concurrent read and write on standard containers without synchronization is undefined behavior, causing hash-table corruption or segfaults. The entire sequence of condition checking and state mutation must be enclosed within the critical section."

Question 2: "You only locked the ancestor path. What if a thread locks a descendant of this node at the same time? Won't that race?"

Say This:
"No, there is no race condition. Any thread attempting to lock a descendant of node $X$ must also collect its own path up to the root. Because $X$ is an ancestor of that descendant, node $X$ is guaranteed to be in that thread's path.
Since all threads acquire locks in the same Leaf-to-Root order, that competing thread must acquire node $X$'s mutex before it can evaluate its checks or modify descendant state. Because our thread already holds the mutex on node $X$, the descendant thread is forced to block. Thus, holding the lock on node $X$ completely shields its entire subtree from concurrent lock operations."

Question 3: "Prove to me that your Leaf-to-Root locking strategy can never deadlock."

Say This:
"A deadlock can only occur if all four Coffman conditions are met, specifically Circular Wait. Circular wait requires a cycle in the Resource Allocation Graph: $T_1$ holds Lock $A$ and waits for Lock $B$, while $T_2$ holds Lock $B$ and waits for Lock $A$.
In our tree, every thread traverses monotonically upward from its starting leaf toward the root. This establishes a strict partial ordering (topological sort) based on tree depth: a lock at depth $D$ is always acquired before a lock at depth $D-1$. Because all threads acquire locks in monotonically decreasing depth order, an edge in the wait-for graph can only ever point from deeper nodes to shallower nodes. A directed acyclic graph cannot contain cycles, making circular wait mathematically impossible."

Question 4: "What happens if I ban std::mutex and tell you to implement this on bare metal?"

Say This:
"If standard library primitives are prohibited, I will implement a custom Spinlock per node using compiler atomic intrinsics. Specifically, I will use __sync_lock_test_and_set or std::atomic::exchange with memory_order_acquire for lock acquisition, and __sync_lock_release or std::atomic::store with memory_order_release for unlocking.
Inside the spin loop, I will use a Test-and-Test-and-Set (TTAS) pattern to spin on read-only cache lines, combined with the x86 _mm_pause() instruction to prevent pipeline stalls and reduce interconnect bus traffic. To eliminate false sharing across adjacent nodes, I will align each lock to 64 bytes using alignas(64)."

Question 5: "How does Amdahl's Law impact this fine-grained design?"

Say This:
"In our design, operations in disjoint subtrees proceed with full hardware parallelism. However, all paths eventually converge at the root node. The root node's mutex represents the strictly sequential bottleneck $(1 - p)$ in Amdahl's Law.
If the root lock is held for even 2% of the overall operation duration, the maximum speedup across infinite cores is capped at $\frac{1}{0.02} = 50\times$. To maximize throughput, we must make the critical section inside the root lock as minimal as possible—specifically by using pre-reserved hash sets and flat vector lookups to minimize CPU cycle consumption while holding the lock."