04-synchronization-and-concurrency.md

🔒 Module 04: Synchronization & Concurrency Mastery

Focus: Race Conditions, Critical Section, Hardware Atomics (CAS, TAS, MESI), Peterson's Algorithm, Mutex vs Semaphores, Monitors & Condition Variables, Read-Write Locks, Classical Problems, Deadlocks & Banker's Algorithm, Priority Inversion, and Fine-Grained Tree-Locking (Juspay / High-Scale Systems).

📑 Table of Contents

  1. Concurrency, Race Conditions & Critical Sections
  2. Hardware Synchronization Primitives (CAS, TAS, MESI)
  3. Software Solutions: Peterson's & Bakery Algorithms
  4. Mutex vs Semaphore: The Definitive Comparison
  5. Spinlocks vs Sleep Locks (Futex Internals)
  6. Monitors & Condition Variables (Mesa vs Hoare)
  7. Shared vs Exclusive Locking (Read-Write Locks)
  8. Classical Synchronization Problems
  9. Deadlocks: The 4 Conditions & Handling Strategies
  10. Deadlock Avoidance: Banker's Algorithm Step-by-Step
  11. Livelock, Starvation & Priority Inversion (PIP)
  12. High-Scale Concurrency & Fine-Grained Tree Locking (Juspay Prep)
  13. Practice Problems with Solutions
  14. High-Yield Interview Questions & Answers

1. Concurrency, Race Conditions & Critical Sections

What is a Race Condition?

A Race Condition occurs when multiple threads or processes read and write shared data concurrently, and the final outcome depends on the non-deterministic order/timing of execution.

THE CLASSIC "LOST UPDATE" BUG (counter++): In C/C++, `counter++` compiles into 3 separate assembly instructions: 1. MOV RAX, [counter] (Load from RAM to CPU Register) 2. ADD RAX, 1 (Increment Register) 3. MOV [counter], RAX (Store back to RAM) INTERLEAVED EXECUTION (Initial counter = 0): Time | Thread 1 | Thread 2 | RAX_T1 | RAX_T2 | RAM Value ------|--------------------------|--------------------------|--------|--------|---------- t1 | 1. MOV RAX, [counter] | | 0 | - | 0 t2 | 2. ADD RAX, 1 | | 1 | - | 0 t3 | --- CONTEXT SWITCH --- | 1. MOV RAX, [counter] | 1 | 0 | 0 t4 | | 2. ADD RAX, 1 | 1 | 1 | 0 t5 | | 3. MOV [counter], RAX | 1 | 1 | 1 t6 | --- CONTEXT SWITCH --- | | 1 | 1 | 1 t7 | 3. MOV [counter], RAX | | 1 | 1 | 1 <-- BUG! Result: counter is 1 instead of 2. One increment was permanently LOST.

The Critical Section Problem

The Critical Section is the code segment where shared resources (memory, file, socket) are accessed. Any valid synchronization solution must satisfy 3 mandatory requirements:

┌────────────────────────────────────────────────────────────────────────────────────────┐ │ 3 CRITICAL SECTION REQUIREMENTS │ ├────────────────────────────────────────────────────────────────────────────────────────┤ │ 1. MUTUAL EXCLUSION (Safety) │ │ If Thread T1 is executing in its critical section, NO other threads can enter. │ ├────────────────────────────────────────────────────────────────────────────────────────┤ │ 2. PROGRESS (Liveness) │ │ If no thread is in the critical section and some threads want to enter, only those │ │ threads not in their remainder section can participate in deciding who enters next, │ │ and the decision CANNOT be postponed indefinitely. │ ├────────────────────────────────────────────────────────────────────────────────────────┤ │ 3. BOUNDED WAITING (Fairness / Starvation-Free) │ │ There must be a limit on the number of times other threads are allowed to enter │ │ their critical sections after a thread has requested entry, before its request is │ │ granted. │ └────────────────────────────────────────────────────────────────────────────────────────┘

2. Hardware Synchronization Primitives (CAS, TAS, MESI)

Software-level algorithms alone are vulnerable to modern out-of-order CPU execution and multi-core memory caching. Modern CPUs provide hardware atomic instructions:

ATOMIC HARDWARE PRIMITIVES │ ┌───────────────────────────────────┼───────────────────────────────────┐ ▼ ▼ ▼ Test-And-Set (TAS) Compare-And-Swap (CAS) Fetch-And-Add (FAA) Atomic: writes true, returns Atomic: if val == old, val = new; Atomic: increments val, previous value. returns success/old value. returns previous value.

1. Compare-And-Swap (CAS)

CAS is the foundation of modern lock-free data structures (Java AtomicInteger, C++ std::atomic):

// Hardware-level atomic semantics: bool compare_and_swap(int* ptr, int expected_val, int new_val) { // This entire block happens atomically in hardware (e.g., x86 `LOCK CMPXCHG`) if (*ptr == expected_val) { *ptr = new_val; return true; // Successfully swapped } return false; // Another thread modified it first! } // Lock-Free Atomic Increment using CAS: void atomic_increment(int* counter) { int current; do { current = *counter; } while (!compare_and_swap(counter, current, current + 1)); }

2. Cache Coherence & The MESI Protocol

In multi-core systems, each core has private L1/L2 caches. When Core 0 modifies memory at address 0xA000, Core 1's cached copy must be synchronized. The MESI Protocol maintains state per cache line (64 bytes):

  • M (Modified): Cache line is present only in current cache and is dirty (differs from main memory RAM).
  • E (Exclusive): Cache line is clean and present only in this core's cache.
  • S (Shared): Cache line is clean and may be present in multiple cores' caches (Read-Only).
  • I (Invalid): Cache line is stale/outdated; reading requires a bus transaction.

3. Software Solutions: Peterson's & Bakery Algorithms

1. Peterson's Algorithm (2-Process Solution)

Classic algorithm satisfying Mutual Exclusion, Progress, and Bounded Waiting for two processes ($P_0$ and $P_1$):

// Shared variables: bool flag[2] = {false, false}; // flag[i] = true means Pi wants to enter int turn = 0; // Whose turn to enter if both want // Process Pi (where j = 1 - i): void process_i() { while (true) { flag[i] = true; // I want to enter turn = j; // Be polite: give priority to other process // Busy wait while other process wants to enter AND it's their turn while (flag[j] && turn == j); // --- CRITICAL SECTION --- // (Access shared data) // --- EXIT SECTION --- flag[i] = false; // I am done // --- REMAINDER SECTION --- } }

Proof of Correctness:

  • Mutual Exclusion: For both $P_0$ and $P_1$ to be in CS simultaneously, flag[0] == true and flag[1] == true. But turn can only be $0$ or $1$, not both. If turn == 0, $P_1$ is trapped in the while loop; if turn == 1, $P_0$ is trapped.
  • Progress & Bounded Waiting: The turn variable resolves ties immediately, guaranteeing that a process waits at most 1 turn before entering.

2. Lamport's Bakery Algorithm ($N$-Process Solution)

Based on a deli/bakery ticket machine: each process receives a ticket number upon arrival. The process with the smallest ticket number is served next. Ties are broken by lowest Process ID.

4. Mutex vs Semaphore: The Definitive Comparison

┌────────────────────────────────────────────────────────┐ │ MUTEX │ │ • "Lock" with strictly ONE owner. │ │ • ONLY the thread that locked the mutex can unlock it. │ │ • Binary state (0 or 1). │ │ • Used for MUTUAL EXCLUSION on a shared resource. │ ├────────────────────────────────────────────────────────┤ │ SEMAPHORE │ │ • "Signaling mechanism" with an integer counter. │ │ • ANY thread can signal/post to increment the count! │ │ • Can be Binary (0 or 1) or Counting (0 to N). │ │ • Used for RESOURCE COUNTING & TASK SIGNALING. │ └────────────────────────────────────────────────────────┘

Detailed Comparison Table

AttributeMutex (Mutual Exclusion Lock)Counting Semaphore
Underlying TypeLocking PrimitiveSignaling Mechanism
OwnershipHas Ownership: The thread that calls lock() MUST call unlock().No Ownership: Thread A can wait (sem_wait), and Thread B can signal (sem_post).
Value RangeBinary only (Locked / Unlocked)Integer ($\ge 0$). Initialized to capacity $N$.
Primary Use CaseProtecting a single critical section or shared data structure.Managing a pool of $N$ identical resources (e.g., DB connections, parking spots).
Operationslock() / unlock() (or acquire() / release())wait() / P() (decrement) and signal() / V() (increment).
ReentrancyCan be made Recursive (same thread can re-lock without deadlock).Semaphores do not track thread identity; no recursive support.

5. Spinlocks vs Sleep Locks (Futex Internals)

WHEN A LOCK IS ALREADY HELD: │ ┌──────────────────────────┴──────────────────────────┐ ▼ ▼ SPINLOCK SLEEP LOCK (Mutex) • Thread burns CPU in a tight • Thread voluntarily yields CPU. loop: `while(locked) {}` • Kernel moves thread to `WAITING` state. • Context Switch Cost: **0 ns** • Context Switch Cost: **~2,000 - 5,000 ns** • Best for: Ultra-short critical • Best for: Long operations (I/O, network, sections (< 50 CPU cycles). complex data structures).

Linux Futex (Fast Userspace Mutex)

Modern POSIX mutexes (pthread_mutex) use Linux Futex for optimal performance:

  1. Uncontended Case: Uses a fast user-space atomic CAS instruction to grab the lock. 0 system calls!
  2. Contended Case: If another thread holds the lock, it drops into the kernel via sys_futex(FUTEX_WAIT) to put the thread to sleep.

6. Monitors & Condition Variables (Mesa vs Hoare)

A Monitor is a high-level programming language construct (e.g., synchronized in Java) that encapsulates shared variables and procedures, guaranteeing that only one thread can execute any monitor method at a time.

MONITOR STRUCTURE ┌─────────────────────────────────────────────────────────────────┐ │ Entry Queue: [ T3 ] [ T4 ] (Waiting to enter monitor lock) │ ├─────────────────────────────────────────────────────────────────┤ │ Monitor Data & Methods (Only 1 active thread inside: [ T1 ]) │ │ │ │ Condition Variable `cv`: │ │ Waiting Queue: [ T2 ] [ T5 ] (Called cv.wait(); sleeping) │ └─────────────────────────────────────────────────────────────────┘

Condition Variable Operations:

  • wait(mutex): Atomically releases the mutex and suspends the thread on the condition queue. When awakened, re-acquires the mutex before returning.
  • signal() / notify(): Wakes up one waiting thread from the condition queue.
  • broadcast() / notifyAll(): Wakes up all waiting threads.

Mesa vs Hoare Semantics: Why while is Mandatory!

// ❌ INCORRECT (Hoare assumption - Vulnerable under Mesa semantics): if (!condition) { cv.await(); } do_work(); // ✅ CORRECT (Mesa Semantics - Universal Standard): while (!condition) { cv.await(); } do_work();

Why the while loop is required (Mesa Semantics):

  1. Intervening Thread: When Thread A is signaled and wakes up, another Thread B might jump in before Thread A re-acquires the lock and consume the condition.
  2. Spurious Wakeups: The OS kernel/CPU may occasionally wake up a sleeping thread even without an explicit signal() call.

7. Shared vs Exclusive Locking (Read-Write Locks)

A Read-Write Lock (std::shared_mutex / pthread_rwlock) allows high read concurrency while protecting write integrity:

┌────────────────────────────────────────────────────────┐ │ SHARED LOCK (Read Lock): │ │ • Multiple reader threads can hold the lock CONCURRENTLY.│ │ • Writers are blocked. │ ├────────────────────────────────────────────────────────┤ │ EXCLUSIVE LOCK (Write Lock): │ │ • Exactly ONE writer thread holds the lock. │ │ • ALL other readers and writers are strictly blocked. │ └────────────────────────────────────────────────────────┘

Reader-Preference vs Writer-Preference Policies:

  • Reader-Preference: New readers are granted the lock immediately even if a writer is waiting. Problem: Can cause Writer Starvation under high read traffic.
  • Writer-Preference: Once a writer requests the lock, incoming readers are queued up until the writer finishes. Prevents writer starvation.

8. Classical Synchronization Problems

8.1 Producer-Consumer (Bounded Buffer)

PRODUCER BOUNDED BUFFER [ N slots ] CONSUMER ┌──────────┐ ┌───┬───┬───┬───┬───┐ ┌──────────┐ │ Generates│ ──► [ sem_wait(empty) ] │ D │ D │ │ │ [ sem_wait(full) ] ──►│ Consumes │ │ Items │ [ sem_wait(mutex) ] └───┴───┴───┴───┘ [ sem_wait(mutex) ] │ Items │ └──────────┘ └──────────┘

Semaphore Implementation:

#define BUFFER_SIZE 10 int buffer[BUFFER_SIZE]; int in = 0, out = 0; semaphore mutex = 1; // For mutual exclusion on buffer indices semaphore empty = BUFFER_SIZE; // Tracks count of free slots semaphore full = 0; // Tracks count of filled slots void* producer(void* arg) { while (true) { int item = produce_item(); sem_wait(&empty); // Decrement empty slots (blocks if buffer is full) sem_wait(&mutex); // Lock buffer buffer[in] = item; in = (in + 1) % BUFFER_SIZE; sem_post(&mutex); // Unlock buffer sem_post(&full); // Increment full slots (wakes waiting consumer) } } void* consumer(void* arg) { while (true) { sem_wait(&full); // Decrement full slots (blocks if buffer is empty) sem_wait(&mutex); // Lock buffer int item = buffer[out]; out = (out + 1) % BUFFER_SIZE; sem_post(&mutex); // Unlock buffer sem_post(&empty); // Increment empty slots (wakes waiting producer) consume_item(item); } }

8.2 Readers-Writers Problem

Writer-Starvation-Free Solution (Using Mutex and Read Counter):

int read_count = 0; semaphore mutex = 1; // Protects `read_count` variable semaphore rw_mutex = 1; // Common lock for readers and writers void* reader(void* arg) { while (true) { sem_wait(&mutex); read_count++; if (read_count == 1) { sem_wait(&rw_mutex); // First reader locks exclusive write lock! } sem_post(&mutex); // --- READING PERFORMED --- read_data(); sem_wait(&mutex); read_count--; if (read_count == 0) { sem_post(&rw_mutex); // Last reader releases exclusive write lock! } sem_post(&mutex); } } void* writer(void* arg) { while (true) { sem_wait(&rw_mutex); // Exclusive access // --- WRITING PERFORMED --- write_data(); sem_post(&rw_mutex); } }

8.3 Dining Philosophers Problem

Five philosophers sit around a circular table with 5 bowls of rice and 5 chopsticks. A philosopher needs both left and right chopsticks to eat.

Philosopher 0 [ 0 ] Chopstick 4 Chopstick 0 [ 4 ] [ 1 ] Philosopher 4 Philosopher 1 Chopstick 3 Chopstick 1 [ 3 ] [ 2 ] Philosopher 3 Philosopher 2 Chopstick 2

The Naive Deadlock:

If all 5 philosophers simultaneously pick up their left chopstick, all 5 right chopsticks are unavailable. Everyone waits forever $\rightarrow$ Circular Deadlock.

3 Deadlock-Free Solutions:

  1. Asymmetric Seating (Odd-Even Rule): Odd philosophers pick Left then Right; Even philosophers pick Right then Left. Breaks Circular Wait.
  2. Resource Ordering (Total Order): Always pick the chopstick with the lower index first ($\min(i, (i+1)%5)$).
  3. State Monitor / Arbitrator: Allow a philosopher to pick chopsticks only if both neighbors are not currently eating.

8.4 Sleeping Barber & Cigarette Smokers

  • Sleeping Barber: Tests synchronization with a waiting room queue and a sleeping worker thread using counting semaphores (customers, barber, accessSeats).
  • Cigarette Smokers: Demonstrates agent-driven resource distribution with multiple interdependent condition variables.

9. Deadlocks: The 4 Conditions & Handling Strategies

A Deadlock is a state where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process in the set.

THE 4 COFFMAN CONDITIONS (All 4 must hold simultaneously for deadlock): ┌────────────────────────────────────────────────────────────────────────────────────────┐ │ 1. MUTUAL EXCLUSION : At least one resource must be held in a non-shareable mode. │ │ 2. HOLD AND WAIT : A process must be holding >=1 resource and waiting for others. │ │ 3. NO PREEMPTION : Resources cannot be forcibly seized; only released voluntarily. │ │ 4. CIRCULAR WAIT : A closed chain of processes {P0, P1... Pn} exists such that │ │ P0 waits for P1, P1 waits for P2... and Pn waits for P0. │ └────────────────────────────────────────────────────────────────────────────────────────┘

Deadlock Handling Strategies:

  1. Ostrich Algorithm: Stick your head in the sand and ignore the problem. (Used by Linux & Windows for general desktop apps where deadlocks are rare and resolution overhead isn't justified).
  2. Deadlock Prevention: Structurally eliminate at least one of the 4 Coffman conditions:
    • Break Circular Wait: Enforce a global lock hierarchy (Total Order $F(R)$). A thread can only request resource $R_b$ if $F(R_b) > F(R_a)$.
    • Break Hold & Wait: Must request all needed resources simultaneously at startup.
    • Break No Preemption: If a process holding resources is denied a new request, all its current resources are preempted.
  3. Deadlock Avoidance: Dynamically inspect resource allocation state before granting requests using Banker's Algorithm.
  4. Deadlock Detection & Recovery: Periodically inspect Wait-For Graph for cycles. Recover by terminating processes or rolling back to checkpoints.

10. Deadlock Avoidance: Banker's Algorithm Step-by-Step

Banker's Algorithm ensures the system never enters an Unsafe State (a state that could lead to a deadlock).

Matrices Defined:

  • $n$: Number of processes, $m$: Number of resource types.
  • Available $[m]$: Quantity of available instances of each resource.
  • Max $[n \times m]$: Maximum demand of each process.
  • Allocation $[n \times m]$: Resources currently allocated to each process.
  • Need $[n \times m]$: Remaining resources needed: $$\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j]$$

Numerical Walkthrough

Given System State:

  • Resources: $A (10 \text{ total}), B (5 \text{ total}), C (7 \text{ total})$.
  • Allocation & Max tables:
ProcessAllocation (A B C)Max (A B C)Need = Max - Alloc (A B C)
P00 1 07 5 37 4 3
P12 0 03 2 21 2 2
P23 0 29 0 26 0 0
P32 1 12 2 20 1 1
P40 0 24 3 34 3 1

Current Total Allocated: $A = 7, B = 2, C = 5$.
Available Vector:
$\text{Available} = \text{Total} - \text{Allocated} = (10-7, 5-2, 7-5) = \mathbf{[3, 3, 2]}$.

Finding the Safe Sequence:

  1. Step 1: Check P0: Need $[7, 4, 3] \le \text{Available } [3, 3, 2]$? False. Cannot run P0.
  2. Step 2: Check P1: Need $[1, 2, 2] \le \text{Available } [3, 3, 2]$? True!
    • P1 finishes and releases its allocation: $\text{Available} = [3, 3, 2] + [2, 0, 0] = \mathbf{[5, 3, 2]}$.
    • Sequence: $\langle P_1 \rangle$.
  3. Step 3: Check P3: Need $[0, 1, 1] \le \text{Available } [5, 3, 2]$? True!
    • P3 finishes: $\text{Available} = [5, 3, 2] + [2, 1, 1] = \mathbf{[7, 4, 3]}$.
    • Sequence: $\langle P_1, P_3 \rangle$.
  4. Step 4: Check P0: Need $[7, 4, 3] \le \text{Available } [7, 4, 3]$? True!
    • P0 finishes: $\text{Available} = [7, 4, 3] + [0, 1, 0] = \mathbf{[7, 5, 3]}$.
    • Sequence: $\langle P_1, P_3, P_0 \rangle$.
  5. Step 5: Check P2: Need $[6, 0, 0] \le \text{Available } [7, 5, 3]$? True!
    • P2 finishes: $\text{Available} = [7, 5, 3] + [3, 0, 2] = \mathbf{[10, 5, 5]}$.
    • Sequence: $\langle P_1, P_3, P_0, P_2 \rangle$.
  6. Step 6: Check P4: Need $[4, 3, 1] \le \text{Available } [10, 5, 5]$? True!
    • P4 finishes: $\text{Available} = [10, 5, 5] + [0, 0, 2] = \mathbf{[10, 5, 7]}$.
    • Sequence: $\langle P_1, P_3, P_0, P_2, P_4 \rangle$.

Result: The system is in a Safe State.
Safe Sequence: $\mathbf{\langle P_1, P_3, P_0, P_2, P_4 \rangle}$.

11. Livelock, Starvation & Priority Inversion (PIP)

┌────────────────────────────────────────────────────────────────────────────────────────┐ │ LIVELOCK │ │ • Two or more threads continuously change their states in response to each other, but │ │ NONE of them make forward progress. │ │ • Analogy: Two polite people in a hallway repeatedly stepping to the same side. │ │ • CPU is 100% active, but 0 useful work gets done. │ ├────────────────────────────────────────────────────────────────────────────────────────┤ │ STARVATION │ │ • A runnable thread is perpetually denied access to resources because other greedy or │ │ higher-priority threads keep jumping ahead. │ ├────────────────────────────────────────────────────────────────────────────────────────┤ │ PRIORITY INVERSION & PRIORITY INHERITANCE PROTOCOL (PIP) │ │ • Scenario: Low-priority thread L holds Lock X. High-priority thread H needs Lock X. │ │ Medium-priority thread M preempts L (since M > L). │ │ • Result: High-priority thread H is indirectly blocked by Medium thread M! │ │ • Solution (PIP): While L holds a lock needed by H, L temporarily **inherits** the │ │ high priority of H, preventing M from preempting it until L releases Lock X. │ └────────────────────────────────────────────────────────────────────────────────────────┘

12. High-Scale Concurrency & Fine-Grained Tree Locking (Juspay Prep)

In high-concurrency systems (like database indexes or Juspay's Tree of Space), coarse-grained global locking destroys throughput.

COARSE-GRAINED LOCKING FINE-GRAINED PER-NODE LOCKING ┌──────────────────────────────────────┐ ┌──────────────────────────────────────┐ │ [ GLOBAL MUTEX ] │ │ (Node A [Lock A]) │ │ Entire tree locked by Thread 1. │ │ / \ │ │ Thread 2 on completely separate │ │ (Node B [Lock B]) (Node C [Lock C]) │ subtree is BLOCKED! │ │ Thread 1 locks B; Thread 2 locks C! │ │ Throughput = O(1) │ │ Throughput = O(N) Concurrent Ops │ └──────────────────────────────────────┘ └──────────────────────────────────────┘

Implementing Safe Fine-Grained Tree Locking:

  1. Lock Ordering: Always acquire locks in a strict top-down (root-to-leaf) or bottom-up (leaf-to-root) order to prevent circular wait deadlocks.
  2. Hand-Over-Hand Locking (Crabbing):
    • Lock Parent $\rightarrow$ Lock Child $\rightarrow$ Unlock Parent $\rightarrow$ Proceed to Next Child.
  3. Lock-Free Status via Atomic CAS:
    • Instead of heavy mutexes per node, maintain an atomic<int> lock_state and use CAS loops to set/clear locks, dramatically reducing memory overhead.

13. Practice Problems with Solutions

Problem 1: Semaphore Counting Value

Question: A system has a counting semaphore initialized to $10$. During execution, the following sequence of operations is performed: $6\text{ P()}, 4\text{ V()}, 2\text{ P()}, 5\text{ P()}, 3\text{ V()}$.
What is the final value of the semaphore?

Solution:

  • Initial value $= 10$.
  • $6\text{ P()}$ (decrements): $10 - 6 = 4$.
  • $4\text{ V()}$ (increments): $4 + 4 = 8$.
  • $2\text{ P()}$ (decrements): $8 - 2 = 6$.
  • $5\text{ P()}$ (decrements): $6 - 5 = 1$.
  • $3\text{ V()}$ (increments): $1 + 3 = 4$.
  • Answer: The final semaphore value is 4.

Problem 2: Banker's Safety Request Evaluation

Question: Using the Banker's Algorithm state from Section 10 (where $\text{Available} = [3, 3, 2]$), suppose process $P_1$ requests additional resources $[1, 0, 2]$. Can this request be granted immediately?

Solution:

  1. Check if $\text{Request} \le \text{Need}(P_1)$: $[1, 0, 2] \le [1, 2, 2]$ $\rightarrow$ True.
  2. Check if $\text{Request} \le \text{Available}$: $[1, 0, 2] \le [3, 3, 2]$ $\rightarrow$ True.
  3. Pretend to allocate:
    • $\text{Available}' = [3, 3, 2] - [1, 0, 2] = [2, 3, 0]$.
    • $\text{Alloc}(P_1)' = [2, 0, 0] + [1, 0, 2] = [3, 0, 2]$.
    • $\text{Need}(P_1)' = [1, 2, 2] - [1, 0, 2] = [0, 2, 0]$.
  4. Run Safety Algorithm on new state:
    • Check $P_1$: $\text{Need} [0, 2, 0] \le \text{Available}' [2, 3, 0]$ $\rightarrow$ True.
    • $P_1$ finishes: $\text{Available}'' = [2, 3, 0] + [3, 0, 2] = [5, 3, 2]$.
    • From $[5, 3, 2]$, processes $P_3, P_0, P_2, P_4$ can all safely complete as proven in Section 10.
  5. Conclusion: Yes, the state remains safe. The request is granted immediately.

14. High-Yield Interview Questions & Answers

Q1: What is the fundamental difference between a Mutex and a Binary Semaphore?

Answer:

  1. Ownership: A Mutex has the concept of ownership—only the specific thread that locked the mutex is allowed to unlock it. A Semaphore has no ownership; any thread (e.g., an interrupt handler or producer thread) can signal (sem_post) to wake up a waiting thread.
  2. Purpose: Mutexes are designed for Mutual Exclusion over a shared critical section. Semaphores are designed for Signaling and Coordination between concurrent tasks.
  3. Priority Inversion Protection: Mutexes support Priority Inheritance Protocols (PIP) because the owner is known; semaphores cannot reliably implement PIP because the unlocking thread is unknown.

Q2: Why is the volatile keyword NOT sufficient for thread synchronization in C/C++ or Java?

Answer: volatile only tells the compiler not to cache the variable in a CPU register and to fetch it from RAM on each read. However:

  1. It does NOT make compound operations atomic (volatile int c; c++ is still a broken 3-step non-atomic race condition).
  2. In C/C++, volatile provides no memory ordering barriers or fences, meaning the CPU hardware can still reorder surrounding instructions out of order.
    For thread synchronization, one must use proper atomic primitives (std::atomic) or locks.

Q3: What is Priority Inversion and how does Mars Pathfinder illustrate it?

Answer: Priority Inversion occurs when a high-priority task is indirectly preempted by a medium-priority task because a low-priority task is holding a shared resource required by the high-priority task.
In the 1997 Mars Pathfinder spacecraft, an information bus mutex was held by a low-priority meteorological task. A medium-priority communications task preempted the low-priority task, preventing it from releasing the mutex. This starved the high-priority attitude control thread, triggering repeated system watchdog resets. It was fixed remotely by enabling Priority Inheritance.

Q4: How does a Read-Write Lock handle upgrade and downgrade operations safely?

Answer:

  • Downgrade (Exclusive $\rightarrow$ Shared): Safe and easy. The thread already holds exclusive write access, so it can atomically decrement its state to shared read access without releasing the lock.
  • Upgrade (Shared $\rightarrow$ Exclusive): Highly prone to deadlocks if multiple readers attempt to upgrade simultaneously (each waits for the other readers to release). Safe upgrade requires either a specialized lock policy where only one designated reader is permitted to upgrade, or unlocking the shared lock and acquiring the exclusive lock anew.

Proceed to Module 05: Memory Management & Virtual Memory!