Operating SystemsInterview Problem Types

Interview Problem Types

LevelAdvanced

Duration180 mins

TopicInterview Problem Types

2 / 5

Synchronization Problems

The Concurrency Challenge in Interviews

Synchronization problems represent the most intellectually demanding category of OS interview questions. Unlike scheduling—which is primarily computational—synchronization problems test your ability to reason about concurrent execution, race conditions, mutual exclusion, and correctness properties that emerge only under specific timing conditions.

These problems are notoriously tricky. A solution that seems correct under casual inspection may harbor subtle bugs that manifest only with specific interleavings. The interviewer isn't just checking if you know the primitives—they're evaluating whether you can think rigorously about concurrent behavior and prove your solution's correctness.

What You Will Master

By the end of this page, you will: (1) Understand and apply synchronization primitives (mutex, semaphores, monitors, condition variables), (2) Recognize and solve classic synchronization problems with correct solutions, (3) Identify and fix race conditions and synchronization bugs, (4) Analyze solutions for deadlock, livelock, and starvation, (5) Implement synchronization patterns correctly under interview pressure.

Synchronization Primitives: Complete Reference

Before solving problems, you must have absolute clarity on synchronization primitives. Interviewers often probe your understanding of subtle distinctions.

Mutex (Mutual Exclusion Lock)

A mutex provides exclusive access to a critical section. It has two operations:

lock(): Acquire the mutex. If already held, block until released.
unlock(): Release the mutex. Wake one waiting thread.

Critical Properties:

Only the owner thread should unlock (enforced by some implementations)
Recursive/reentrant mutexes allow same thread to lock multiple times
Non-reentrant mutexes cause deadlock if same thread locks twice

Semaphore

A semaphore is a generalized counter with atomic operations:

wait() / P() / down(): Decrement counter. If negative, block.
signal() / V() / up(): Increment counter. Wake one blocked thread if any.

Types:

Binary semaphore: Counter ∈ {0, 1}. Similar to mutex.
Counting semaphore: Counter ∈ ℤ (often ≥ 0). Controls access to multiple resources.

Semaphore vs Mutex:

Semaphore can be signaled by any thread; mutex ownership is strict
Semaphore enables signaling/synchronization; mutex is for mutual exclusion
Semaphore can allow n threads into a region; mutex allows exactly 1

Primitive Comparison Matrix
Primitive	Purpose	Ownership	Counter	Blocking Behavior
Mutex	Mutual exclusion	Yes (owner unlocks)	Binary (locked/unlocked)	Lock blocks if held
Binary Semaphore	Mutual exclusion/signaling	No (any can signal)	0 or 1	Wait blocks if 0
Counting Semaphore	Resource pooling/signaling	No	Any non-negative integer	Wait blocks if ≤ 0
Spinlock	Busy-wait mutual exclusion	Yes	Binary	Spins instead of blocking
Condition Variable	Wait for condition	Used with mutex	No counter	Wait releases mutex, blocks

Condition Variables

Condition variables enable threads to wait for a condition to become true. They MUST be used with a mutex.

Operations:

wait(cv, mutex): Atomically releases mutex and blocks on cv. Upon waking, re-acquires mutex.
signal(cv): Wakes one thread waiting on cv.
broadcast(cv): Wakes all threads waiting on cv.

The Waiting Pattern:

mutex.lock()
while (!condition) {    // WHILE, not IF!
    cv.wait(mutex)
}
// Critical section with condition true
mutex.unlock()

Why WHILE, not IF? Spurious wakeups can occur. The condition might be false when you wake. Always recheck in a loop!

Common Interview Trap

Using if instead of while around condition variable waits is a classic bug. Interviewers specifically look for this. Spurious wakeups (or another thread consuming the resource first) mean the condition may be false when you wake. ALWAYS use a while loop!

primitives_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import threading
from threading import Semaphore, Lock, Condition
 
# Semaphore for bounded buffer (producer-consumer)
class BoundedBuffer:
    def __init__(self, capacity: int):
        self.buffer = []
        self.capacity = capacity
        self.mutex = Lock()
        self.empty = Semaphore(capacity)  # Slots available for producers
        self.full = Semaphore(0)          # Items available for consumers
    
    def produce(self, item):
        self.empty.acquire()      # Wait for empty slot
        with self.mutex:          # Critical section: add item
            self.buffer.append(item)
        self.full.release()       # Signal item available
    
    def consume(self):
        self.full.acquire()       # Wait for item
        with self.mutex:          # Critical section: remove item
            item = self.buffer.pop(0)
        self.empty.release()      # Signal slot available
        return item
 
# Condition variable example
class BlockingQueue:
    def __init__(self, capacity: int):
        self.queue = []
        self.capacity = capacity
        self.lock = Lock()
        self.not_empty = Condition(self.lock)
        self.not_full = Condition(self.lock)
    
    def put(self, item):
        with self.lock:
            while len(self.queue) >= self.capacity:  # WHILE, not IF!
                self.not_full.wait()
            self.queue.append(item)
            self.not_empty.notify()  # Wake one waiting consumer
    
    def get(self):
        with self.lock:
            while len(self.queue) == 0:              # WHILE, not IF!
                self.not_empty.wait()
            item = self.queue.pop(0)
            self.not_full.notify()   # Wake one waiting producer
            return item

The Producer-Consumer Problem: Comprehensive Analysis

The producer-consumer (bounded buffer) problem is the most fundamental synchronization problem. Every synchronization concept can be illustrated through it, and it appears directly or as a component in most interview questions.

Problem Statement:

Multiple producer threads generate data items
Multiple consumer threads consume data items
A shared buffer of fixed capacity stores items
Producers must block when buffer is full
Consumers must block when buffer is empty
Buffer access must be mutually exclusive

Invariants to Maintain:

Buffer count: 0 ≤ count ≤ capacity
Producers wait when count = capacity
Consumers wait when count = 0
Only one thread modifies buffer at a time

Solution 1: Using Semaphores

This is the classic textbook solution:

// Shared state
buffer[CAPACITY]
mutex = Semaphore(1)      // For mutual exclusion
empty = Semaphore(CAPACITY)  // Empty slots available
full = Semaphore(0)          // Items available

Producer():
    while (true):
        item = produce()
        empty.wait()          // Wait for empty slot
        mutex.wait()          // Enter critical section
        buffer.add(item)
        mutex.signal()        // Leave critical section
        full.signal()         // Signal item available

Consumer():
    while (true):
        full.wait()           // Wait for item
        mutex.wait()          // Enter critical section
        item = buffer.remove()
        mutex.signal()        // Leave critical section
        empty.signal()        // Signal slot available
        consume(item)

Deadly Order Bug

What if we swap the order in Producer to: mutex.wait() then empty.wait()?

DEADLOCK! If buffer is full: Producer holds mutex, waits on empty. Consumers cannot acquire mutex to remove items and signal empty. Everyone blocks forever.

Solution 2: Using Condition Variables

The monitor-based solution:

// Shared state with condition variables
buffer[CAPACITY]
count = 0
lock = Mutex()
not_full = ConditionVariable()
not_empty = ConditionVariable()

Producer():
    while (true):
        item = produce()
        lock.acquire()
        while (count == CAPACITY):   // WHILE loop!
            not_full.wait(lock)
        buffer.add(item)
        count++
        not_empty.signal()           // Wake a consumer
        lock.release()

Consumer():
    while (true):
        lock.acquire()
        while (count == 0):          // WHILE loop!
            not_empty.wait(lock)
        item = buffer.remove()
        count--
        not_full.signal()            // Wake a producer
        lock.release()
        consume(item)

Comparison of Approaches:

Aspect	Semaphores	Condition Variables
Elegance	Lower level, more explicit	Higher level, more abstracted
State tracking	Implied in semaphore counts	Explicit counter variable
Error proneness	Deadlock if wrong order	Spurious wakeup if using IF
Flexibility	Fixed pattern	More flexible conditions
Common in	Systems programming	Object-oriented monitors

Interview Insight: Know both approaches. Some interviews specify semaphores; others expect monitors. Being able to convert between them demonstrates deep understanding.

Correct Solution Properties

•Mutual exclusion for buffer access
•Producers block on full buffer
•Consumers block on empty buffer
•No deadlock possible
•No race conditions
•Progress guaranteed (no livelock)

Common Bugs

•Wrong semaphore order → Deadlock
•Signaling before/outside mutex
•Using IF instead of WHILE
•Signaling wrong condition variable
•Missing mutex around buffer access
•Using notify instead of notifyAll when needed

The Readers-Writers Problem: All Variants

The readers-writers problem models concurrent access to a shared resource where reads can be concurrent but writes require exclusive access.

Problem Statement:

Multiple reader threads want to read shared data
Multiple writer threads want to modify shared data
Multiple readers can read simultaneously (no data conflict)
Writers require exclusive access (no concurrent readers or writers)

Three Variants:

First Readers-Writers: No reader waits unless writer has permission (readers-preference)
Second Readers-Writers: Once a writer is ready, no new readers may start (writers-preference)
Third Readers-Writers (Fair): Neither readers nor writers can starve

Starvation Alert

First variant starves writers (continuous reader stream prevents writers). Second variant starves readers (pending writers block all new readers). Only the third variant is truly fair. Interviewers often ask you to identify which variant a solution implements.

Solution: First Readers-Writers (Readers Preference)

// Shared state
read_count = 0
mutex = Semaphore(1)       // Protects read_count
write_lock = Semaphore(1)  // Write access / read group access

Reader():
    while (true):
        mutex.wait()
        read_count++
        if (read_count == 1):     // First reader locks out writers
            write_lock.wait()
        mutex.signal()
        
        // READ DATA (concurrent with other readers)
        
        mutex.wait()
        read_count--
        if (read_count == 0):     // Last reader lets writers in
            write_lock.signal()
        mutex.signal()

Writer():
    while (true):
        write_lock.wait()         // Exclusive access
        // WRITE DATA
        write_lock.signal()

Analysis: The first reader acquires write_lock, blocking writers. Subsequent readers increment count and proceed. The last reader releases write_lock. Writers wait whenever any readers exist. A continuous stream of readers starves writers indefinitely.

Solution: Writers Preference (Second Variant)

// Additional state for writers preference
read_count = 0
write_count = 0
mutex_read = Semaphore(1)     // Protects read_count
mutex_write = Semaphore(1)    // Protects write_count
read_try = Semaphore(1)       // Readers check if writers waiting
resource = Semaphore(1)       // Actual resource access

Reader():
    read_try.wait()           // Writers can block new readers here
    mutex_read.wait()
    read_count++
    if (read_count == 1):
        resource.wait()       // First reader locks resource
    mutex_read.signal()
    read_try.signal()
    
    // READ DATA
    
    mutex_read.wait()
    read_count--
    if (read_count == 0):
        resource.signal()
    mutex_read.signal()

Writer():
    mutex_write.wait()
    write_count++
    if (write_count == 1):
        read_try.wait()       // Block new readers
    mutex_write.signal()
    
    resource.wait()           // Exclusive write access
    // WRITE DATA
    resource.signal()
    
    mutex_write.wait()
    write_count--
    if (write_count == 0):
        read_try.signal()     // Allow readers again
    mutex_write.signal()

Analysis: When a writer arrives, it blocks read_try, preventing new readers. Existing readers finish, then writer proceeds. Continuous writers starve readers.

Solution: Fair (No Starvation)

The fair solution uses a shared queue or turnstile:

// Fair solution using service queue
read_count = 0
mutex = Semaphore(1)
resource = Semaphore(1)
service_queue = Semaphore(1)  // FIFO ordering

Reader():
    service_queue.wait()      // Wait in line
    mutex.wait()
    read_count++
    if (read_count == 1):
        resource.wait()
    service_queue.signal()    // Let next in queue proceed
    mutex.signal()
    
    // READ DATA
    
    mutex.wait()
    read_count--
    if (read_count == 0):
        resource.signal()
    mutex.signal()

Writer():
    service_queue.wait()      // Wait in line
    resource.wait()           // Get exclusive access
    service_queue.signal()    // Can release: we have resource
    
    // WRITE DATA
    
    resource.signal()

Analysis: service_queue enforces FIFO ordering. Readers and writers alternate fairly. No starvation for either party.

Readers-Writers Variants Comparison
Variant	Read Concurrency	Write Priority	Starvation
First (Readers Preference)	Maximum	Low	Writers can starve
Second (Writers Preference)	Limited	High	Readers can starve
Third (Fair)	Moderate	Equal	None

Dining Philosophers: Deadlock and Solutions

The dining philosophers problem is specifically designed to illustrate deadlock. It's essential for demonstrating your understanding of deadlock conditions and prevention strategies.

Problem Statement:

5 philosophers sit around a circular table
5 forks are placed between them (one between each adjacent pair)
To eat, a philosopher needs both the left and right fork
Philosophers alternate between thinking and eating
Goal: No deadlock, no starvation

Naive Solution (DEADLOCKS!):

Philosopher(i):
    while (true):
        think()
        pick_up(fork[i])          // Left fork
        pick_up(fork[(i+1) % 5])  // Right fork
        eat()
        put_down(fork[i])
        put_down(fork[(i+1) % 5])

Deadlock Scenario: All 5 philosophers simultaneously pick up their left fork. Each waits for their right fork—which is another philosopher's left fork. Circular wait → Deadlock!

The Four Deadlock Conditions

For deadlock to occur, ALL four conditions must hold simultaneously:

Mutual Exclusion: Forks can only be held by one philosopher
Hold and Wait: Philosophers hold left fork while waiting for right
No Preemption: Forks cannot be forcibly taken
Circular Wait: Philosopher 0 waits for 1, 1 waits for 2, ..., 4 waits for 0

Breaking ANY one condition prevents deadlock!

Solution 1: Resource Hierarchy (Break Circular Wait)

Number forks 0-4. Always acquire lower-numbered fork first.

Philosopher(i):
    while (true):
        think()
        first = min(i, (i+1) % 5)
        second = max(i, (i+1) % 5)
        pick_up(fork[first])
        pick_up(fork[second])
        eat()
        put_down(fork[second])
        put_down(fork[first])

Why it works: Philosopher 4's forks are 4 and 0. They pick up 0 first. This breaks the circular chain—no one holds a higher fork while waiting for a lower one.

Solution 2: Limit Diners (Break Hold-and-Wait)

Allow at most 4 philosophers to attempt eating simultaneously.

room = Semaphore(4)  // Only 4 can try to eat

Philosopher(i):
    while (true):
        think()
        room.wait()              // Limit concurrency
        pick_up(fork[i])
        pick_up(fork[(i+1) % 5])
        eat()
        put_down(fork[i])
        put_down(fork[(i+1) % 5])
        room.signal()

Why it works: With only 4 philosophers at the table, circular wait is impossible—there's always at least one available fork.

Solution 3: Chandy/Misra (Optimistic with Backoff)

Forks are "dirty" or "clean". Philosophers request forks, may get denied.

Philosopher(i):
    while (true):
        think()
        request_forks()  // Politely request both forks
        eat()            // Clean forks after eating
        mark_forks_dirty()

Rules:

After eating, forks become dirty
If neighbor requests your dirty fork, give it up (cleaned)
Only give up dirty forks
Initially, all forks are dirty, given to lower-numbered philosopher

This is the most efficient solution but rarely tested in depth.

Solution 4: Monitor with Condition Variables

state[5] = THINKING  // Each philosopher's state
state_lock = Mutex()
condition[5] = ConditionVariable()  // One per philosopher

Philosopher(i):
    while (true):
        think()
        take_forks(i)
        eat()
        put_forks(i)

take_forks(i):
    state_lock.acquire()
    state[i] = HUNGRY
    test(i)  // Try to acquire
    while (state[i] != EATING):
        condition[i].wait(state_lock)
    state_lock.release()

put_forks(i):
    state_lock.acquire()
    state[i] = THINKING
    test(LEFT)   // Wake left neighbor if waiting
    test(RIGHT)  // Wake right neighbor if waiting
    state_lock.release()

test(i):
    // Can philosopher i eat?
    if (state[i] == HUNGRY and 
        state[LEFT] != EATING and 
        state[RIGHT] != EATING):
        state[i] = EATING
        condition[i].signal()

This is the most commonly expected interview solution.

Dining Philosophers Solutions Comparison
Solution	Mechanism	Condition Broken	Parallelism
Resource Hierarchy	Ordered acquisition	Circular Wait	2 can eat simultaneously
Limit Diners (n-1)	Semaphore limit	Hold-and-Wait denied	2 can eat simultaneously
Chandy/Misra	Request/defer protocol	Hold-and-Wait relaxed	Maximum possible
Monitor Solution	Explicit state machine	Coordinated acquisition	2 can eat simultaneously

Identifying and Fixing Race Conditions

Beyond classic problems, interviewers frequently present buggy code and ask you to identify race conditions. This requires systematic analysis of all possible interleavings.

What is a Race Condition?

A race condition occurs when the program's correctness depends on the relative timing of events—specifically, when:

Multiple threads access shared data
At least one thread writes to the data
Access is not properly synchronized
The outcome differs based on which thread "wins the race"

Analysis Framework:

Identify shared state: What data is accessed by multiple threads?
Identify read-write patterns: Which threads read? Which write?
Find critical sections: Where must access be atomic?
Consider interleavings: What happens if Thread A is interrupted mid-operation?
Construct attack scenario: Show a specific interleaving that causes incorrect behavior

Example: Broken Counter

int counter = 0;

void increment() {
    counter = counter + 1;  // Race condition!
}

Bug Analysis:

This single line is NOT atomic. It compiles to:

Load counter into register
Add 1 to register
Store register to counter

Attack Scenario:

Initial: counter = 0
Thread A: Load counter (0) into register
Thread B: Load counter (0) into register
Thread A: Add 1 (register = 1)
Thread B: Add 1 (register = 1)
Thread A: Store 1 to counter
Thread B: Store 1 to counter
Final: counter = 1 (should be 2!)

Fix:

mutex_t lock;

void increment() {
    mutex_lock(&lock);
    counter = counter + 1;
    mutex_unlock(&lock);
}

Subtle Race Condition Example

if (ptr != NULL) {
    use(ptr);  // Race: ptr could become NULL between check and use!
}

This time-of-check-to-time-of-use (TOCTOU) bug is common in security vulnerabilities. Another thread could set ptr = NULL after the check but before the use.

Common Race Condition Patterns:

Pattern	Example	Risk
Check-then-act	`if (x > 0) x--;`	Value changes between check and act
Read-modify-write	`counter++`	Non-atomic update sequence
Lazy initialization	`if (instance == NULL) create()`	Double creation
Compound operations	`if (map.containsKey(k)) map.get(k)`	Key removed between check and get

Debug Strategy:

When analyzing for races:

List all shared variables
For each, determine thread access pattern
Look for non-atomic compound operations
Check for missing locks around multi-step operations
Verify lock consistency (all accesses protected by same lock)

double_checked_locking.java
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// BROKEN Double-Checked Locking (without volatile)
class Singleton {
    private static Singleton instance;  // BUG: needs volatile!
    
    public static Singleton getInstance() {
        if (instance == null) {              // First check (no lock)
            synchronized (Singleton.class) {
                if (instance == null) {      // Second check (with lock)
                    instance = new Singleton();  // Reordering bug!
                }
            }
        }
        return instance;
    }
}
 
// Why it's broken:
// The constructor call "instance = new Singleton()" involves:
// 1. Allocate memory for Singleton
// 2. Initialize Singleton fields
// 3. Assign reference to instance
// 
// Without volatile, compiler/CPU may reorder to: 1 -> 3 -> 2
// Thread A executes 1, 3 (instance is non-null but not initialized)
// Thread B sees non-null instance, returns it, uses uninitialized object!
 
// CORRECT version:
class SingletonFixed {
    private static volatile Singleton instance;  // volatile prevents reordering
    
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (SingletonFixed.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

Deadlock Detection and Prevention

Deadlock questions require you to analyze whether deadlock is possible, detect it in running systems, or modify solutions to prevent it.

Deadlock Definition:

A set of processes is deadlocked if each process is waiting for a resource held by another process in the set, forming a cycle with no way to make progress.

The Four Necessary Conditions (Coffman Conditions):

Mutual Exclusion: Resources cannot be shared
Hold and Wait: Processes hold resources while waiting for others
No Preemption: Resources cannot be forcibly taken
Circular Wait: Circular chain of processes, each waiting for next's resource

ALL FOUR must hold for deadlock to occur.

Resource Allocation Graph (RAG) Analysis:

Draw a directed graph:

Nodes: Processes (circles) and Resources (rectangles)
Request edge: P → R (process P wants resource R)
Assignment edge: R → P (resource R assigned to process P)

Deadlock Detection:

For single-instance resources: Deadlock ⟺ cycle in RAG
For multi-instance resources: Cycle is necessary but not sufficient; use banker's algorithm

Example RAG:

P1 → R1 → P2 → R2 → P1  (Cycle! Deadlock if R1, R2 are single instance)

Banker's Algorithm for Deadlock Avoidance:

Given:

Available[]: Resources currently available
Max[][]: Maximum resources each process may need
Allocation[][]: Resources currently allocated to each process
Need[][] = Max - Allocation: Resources still needed

Safety Algorithm:

1. Work = Available (copy)
   Finish[] = false for all processes

2. Find process i such that:
   - Finish[i] == false
   - Need[i] <= Work (can complete with available)

3. If found:
   Work = Work + Allocation[i]  (release resources)
   Finish[i] = true
   Go to step 2

4. If Finish[] all true: SAFE
   Otherwise: UNSAFE (potential deadlock)

Resource Request Algorithm:

When process P requests resources:

If Request > Need: Error (exceeds declared max)
If Request > Available: P waits
Pretend-allocate: Available -= Request, Allocation[P] += Request
Run safety algorithm
If safe: Grant. If unsafe: Rollback, P waits.

Interview Approach

For deadlock problems: (1) Draw the RAG, (2) Check for cycles, (3) If multi-instance resources, apply Banker's algorithm, (4) For prevention questions, identify which Coffman condition to break and how.

Prevention Strategies (Break Each Condition):

Condition	Prevention Strategy	Tradeoff
Mutual Exclusion	Make resources sharable (readers-writers)	Not always possible
Hold and Wait	Request all resources at start	Poor resource utilization
No Preemption	Allow resource preemption	May cause inconsistency
Circular Wait	Impose resource ordering	Limits flexibility

Practical Choices:

Ordering (circular wait prevention): Most common in practice. All programs acquire resources in same global order.
Timeout (break no-preemption): If lock not acquired in time, release all held locks and retry. Used in databases.
Detection and Recovery: Let deadlock happen, detect via periodic RAG analysis, kill a process to break it.

Additional Classic Synchronization Problems

Beyond the core three problems, several other classic problems frequently appear in interviews.

The Sleeping Barber Problem:

One barber, N waiting chairs
If no customers, barber sleeps
Arriving customer wakes barber OR waits (if chairs available) OR leaves

Solution Sketch:

barber_ready = Semaphore(0)    // Barber signals readiness
customer_ready = Semaphore(0)  // Customer signals arrival  
mutex = Semaphore(1)           // Protect waiting count
waiting = 0                    // Number waiting

Barber():
    while (true):
        customer_ready.wait()  // Sleep until customer
        barber_ready.signal()  // Signal ready for haircut
        cut_hair()

Customer():
    mutex.wait()
    if (waiting < N):
        waiting++
        customer_ready.signal()  // Wake barber
        mutex.signal()
        barber_ready.wait()      // Wait for barber
        waiting--
        get_haircut()
    else:
        mutex.signal()           // No chairs, leave

Cigarette Smokers Problem:

Three smokers, each has infinite supply of one ingredient (tobacco, paper, matches). An agent places two ingredients on table. Smoker with third ingredient takes them, smokes, signals agent.

Challenge: The straightforward solution deadlocks. Each smoker waits for their two needed ingredients specifically.

Key Insight: Requires intermediate "pusher" threads that observe which two ingredients are on table and signal the appropriate smoker.

The H₂O Problem:

Multiple hydrogen and oxygen threads. Must bond exactly 2 hydrogens with 1 oxygen to form water, then release all three together.

Solution uses a barrier:

Hydrogens wait at barrier until 2 present and 1 oxygen
Oxygen waits at barrier for 2 hydrogens
All three release together

Building H₂O Problem (code sketch):

hydrogen_sem = Semaphore(0)
oxygen_sem = Semaphore(0)
barrier = Barrier(3)
mutex = Mutex()
hydrogen_count = 0

hydrogen():
    mutex.lock()
    hydrogen_count++
    if (hydrogen_count == 2):
        oxygen_sem.signal()    // Wake oxygen
        hydrogen_sem.signal()  // Let other hydrogen proceed
        hydrogen_count = 0
    mutex.unlock()
    
    hydrogen_sem.wait()        // Wait to be paired
    barrier.wait()             // Synchronize bonding
    // Bond!

oxygen():
    oxygen_sem.wait()          // Wait for 2 hydrogens
    hydrogen_sem.signal()      // Release second hydrogen
    barrier.wait()             // Synchronize bonding
    // Bond!

Barrier Synchronization

A barrier blocks all arriving threads until N have reached it, then releases all simultaneously. Useful for phased computations and bonding problems like H₂O. In POSIX: pthread_barrier_t. In Java: CyclicBarrier.

Summary: Synchronization Problem Mastery

Key Takeaways

•Know your primitives cold: Mutex vs semaphore vs condition variable—their semantics, use cases, and pitfalls.
•Master the classic three: Producer-consumer, readers-writers, dining philosophers form the foundation for all synchronization problems.
•Always use WHILE loops: Around condition variable waits, never IF. Spurious wakeups happen.
•Check for deadlock: Analyze ordering of lock acquisition. Break at least one Coffman condition for prevention.
•Construct attack scenarios: When analyzing race conditions, show a specific interleaving that causes failure.
•Verify all invariants: After designing a solution, check: no race, no deadlock, no starvation, progress guaranteed.

Page Complete

You now have comprehensive knowledge of synchronization problems for OS interviews. The next page covers memory calculations—computing page table sizes, address translations, TLB hit ratios, and memory access times with precision.

2 / 5

Loading learning content...

Operating SystemsInterview Problem Types

Interview Problem Types

LevelAdvanced

Duration180 mins

TopicInterview Problem Types

2 / 5

Synchronization Problems

The Concurrency Challenge in Interviews

What You Will Master

Synchronization Primitives: Complete Reference

Before solving problems, you must have absolute clarity on synchronization primitives. Interviewers often probe your understanding of subtle distinctions.

Mutex (Mutual Exclusion Lock)

A mutex provides exclusive access to a critical section. It has two operations:

lock(): Acquire the mutex. If already held, block until released.
unlock(): Release the mutex. Wake one waiting thread.

Critical Properties:

Only the owner thread should unlock (enforced by some implementations)
Recursive/reentrant mutexes allow same thread to lock multiple times
Non-reentrant mutexes cause deadlock if same thread locks twice

Semaphore

A semaphore is a generalized counter with atomic operations:

wait() / P() / down(): Decrement counter. If negative, block.
signal() / V() / up(): Increment counter. Wake one blocked thread if any.

Types:

Binary semaphore: Counter ∈ {0, 1}. Similar to mutex.
Counting semaphore: Counter ∈ ℤ (often ≥ 0). Controls access to multiple resources.

Semaphore vs Mutex:

Semaphore can be signaled by any thread; mutex ownership is strict
Semaphore enables signaling/synchronization; mutex is for mutual exclusion
Semaphore can allow n threads into a region; mutex allows exactly 1

Primitive Comparison Matrix
Primitive	Purpose	Ownership	Counter	Blocking Behavior
Mutex	Mutual exclusion	Yes (owner unlocks)	Binary (locked/unlocked)	Lock blocks if held
Binary Semaphore	Mutual exclusion/signaling	No (any can signal)	0 or 1	Wait blocks if 0
Counting Semaphore	Resource pooling/signaling	No	Any non-negative integer	Wait blocks if ≤ 0
Spinlock	Busy-wait mutual exclusion	Yes	Binary	Spins instead of blocking
Condition Variable	Wait for condition	Used with mutex	No counter	Wait releases mutex, blocks

Condition Variables

Condition variables enable threads to wait for a condition to become true. They MUST be used with a mutex.

Operations:

wait(cv, mutex): Atomically releases mutex and blocks on cv. Upon waking, re-acquires mutex.
signal(cv): Wakes one thread waiting on cv.
broadcast(cv): Wakes all threads waiting on cv.

The Waiting Pattern:

mutex.lock()
while (!condition) {    // WHILE, not IF!
    cv.wait(mutex)
}
// Critical section with condition true
mutex.unlock()

Why WHILE, not IF? Spurious wakeups can occur. The condition might be false when you wake. Always recheck in a loop!

Common Interview Trap

primitives_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import threading
from threading import Semaphore, Lock, Condition
 
# Semaphore for bounded buffer (producer-consumer)
class BoundedBuffer:
    def __init__(self, capacity: int):
        self.buffer = []
        self.capacity = capacity
        self.mutex = Lock()
        self.empty = Semaphore(capacity)  # Slots available for producers
        self.full = Semaphore(0)          # Items available for consumers
    
    def produce(self, item):
        self.empty.acquire()      # Wait for empty slot
        with self.mutex:          # Critical section: add item
            self.buffer.append(item)
        self.full.release()       # Signal item available
    
    def consume(self):
        self.full.acquire()       # Wait for item
        with self.mutex:          # Critical section: remove item
            item = self.buffer.pop(0)
        self.empty.release()      # Signal slot available
        return item
 
# Condition variable example
class BlockingQueue:
    def __init__(self, capacity: int):
        self.queue = []
        self.capacity = capacity
        self.lock = Lock()
        self.not_empty = Condition(self.lock)
        self.not_full = Condition(self.lock)
    
    def put(self, item):
        with self.lock:
            while len(self.queue) >= self.capacity:  # WHILE, not IF!
                self.not_full.wait()
            self.queue.append(item)
            self.not_empty.notify()  # Wake one waiting consumer
    
    def get(self):
        with self.lock:
            while len(self.queue) == 0:              # WHILE, not IF!
                self.not_empty.wait()
            item = self.queue.pop(0)
            self.not_full.notify()   # Wake one waiting producer
            return item

The Producer-Consumer Problem: Comprehensive Analysis

Problem Statement:

Multiple producer threads generate data items
Multiple consumer threads consume data items
A shared buffer of fixed capacity stores items
Producers must block when buffer is full
Consumers must block when buffer is empty
Buffer access must be mutually exclusive

Invariants to Maintain:

Buffer count: 0 ≤ count ≤ capacity
Producers wait when count = capacity
Consumers wait when count = 0
Only one thread modifies buffer at a time

Solution 1: Using Semaphores

This is the classic textbook solution:

// Shared state
buffer[CAPACITY]
mutex = Semaphore(1)      // For mutual exclusion
empty = Semaphore(CAPACITY)  // Empty slots available
full = Semaphore(0)          // Items available

Producer():
    while (true):
        item = produce()
        empty.wait()          // Wait for empty slot
        mutex.wait()          // Enter critical section
        buffer.add(item)
        mutex.signal()        // Leave critical section
        full.signal()         // Signal item available

Consumer():
    while (true):
        full.wait()           // Wait for item
        mutex.wait()          // Enter critical section
        item = buffer.remove()
        mutex.signal()        // Leave critical section
        empty.signal()        // Signal slot available
        consume(item)

Deadly Order Bug

What if we swap the order in Producer to: mutex.wait() then empty.wait()?

DEADLOCK! If buffer is full: Producer holds mutex, waits on empty. Consumers cannot acquire mutex to remove items and signal empty. Everyone blocks forever.

Solution 2: Using Condition Variables

The monitor-based solution:

// Shared state with condition variables
buffer[CAPACITY]
count = 0
lock = Mutex()
not_full = ConditionVariable()
not_empty = ConditionVariable()

Producer():
    while (true):
        item = produce()
        lock.acquire()
        while (count == CAPACITY):   // WHILE loop!
            not_full.wait(lock)
        buffer.add(item)
        count++
        not_empty.signal()           // Wake a consumer
        lock.release()

Consumer():
    while (true):
        lock.acquire()
        while (count == 0):          // WHILE loop!
            not_empty.wait(lock)
        item = buffer.remove()
        count--
        not_full.signal()            // Wake a producer
        lock.release()
        consume(item)

Comparison of Approaches:

Aspect	Semaphores	Condition Variables
Elegance	Lower level, more explicit	Higher level, more abstracted
State tracking	Implied in semaphore counts	Explicit counter variable
Error proneness	Deadlock if wrong order	Spurious wakeup if using IF
Flexibility	Fixed pattern	More flexible conditions
Common in	Systems programming	Object-oriented monitors

Interview Insight: Know both approaches. Some interviews specify semaphores; others expect monitors. Being able to convert between them demonstrates deep understanding.

Correct Solution Properties

•Mutual exclusion for buffer access
•Producers block on full buffer
•Consumers block on empty buffer
•No deadlock possible
•No race conditions
•Progress guaranteed (no livelock)

Common Bugs

•Wrong semaphore order → Deadlock
•Signaling before/outside mutex
•Using IF instead of WHILE
•Signaling wrong condition variable
•Missing mutex around buffer access
•Using notify instead of notifyAll when needed

The Readers-Writers Problem: All Variants

The readers-writers problem models concurrent access to a shared resource where reads can be concurrent but writes require exclusive access.

Problem Statement:

Multiple reader threads want to read shared data
Multiple writer threads want to modify shared data
Multiple readers can read simultaneously (no data conflict)
Writers require exclusive access (no concurrent readers or writers)

Three Variants:

First Readers-Writers: No reader waits unless writer has permission (readers-preference)
Second Readers-Writers: Once a writer is ready, no new readers may start (writers-preference)
Third Readers-Writers (Fair): Neither readers nor writers can starve

Starvation Alert

Solution: First Readers-Writers (Readers Preference)

// Shared state
read_count = 0
mutex = Semaphore(1)       // Protects read_count
write_lock = Semaphore(1)  // Write access / read group access

Reader():
    while (true):
        mutex.wait()
        read_count++
        if (read_count == 1):     // First reader locks out writers
            write_lock.wait()
        mutex.signal()
        
        // READ DATA (concurrent with other readers)
        
        mutex.wait()
        read_count--
        if (read_count == 0):     // Last reader lets writers in
            write_lock.signal()
        mutex.signal()

Writer():
    while (true):
        write_lock.wait()         // Exclusive access
        // WRITE DATA
        write_lock.signal()

Solution: Writers Preference (Second Variant)

// Additional state for writers preference
read_count = 0
write_count = 0
mutex_read = Semaphore(1)     // Protects read_count
mutex_write = Semaphore(1)    // Protects write_count
read_try = Semaphore(1)       // Readers check if writers waiting
resource = Semaphore(1)       // Actual resource access

Reader():
    read_try.wait()           // Writers can block new readers here
    mutex_read.wait()
    read_count++
    if (read_count == 1):
        resource.wait()       // First reader locks resource
    mutex_read.signal()
    read_try.signal()
    
    // READ DATA
    
    mutex_read.wait()
    read_count--
    if (read_count == 0):
        resource.signal()
    mutex_read.signal()

Writer():
    mutex_write.wait()
    write_count++
    if (write_count == 1):
        read_try.wait()       // Block new readers
    mutex_write.signal()
    
    resource.wait()           // Exclusive write access
    // WRITE DATA
    resource.signal()
    
    mutex_write.wait()
    write_count--
    if (write_count == 0):
        read_try.signal()     // Allow readers again
    mutex_write.signal()

Analysis: When a writer arrives, it blocks read_try, preventing new readers. Existing readers finish, then writer proceeds. Continuous writers starve readers.

Solution: Fair (No Starvation)

The fair solution uses a shared queue or turnstile:

// Fair solution using service queue
read_count = 0
mutex = Semaphore(1)
resource = Semaphore(1)
service_queue = Semaphore(1)  // FIFO ordering

Reader():
    service_queue.wait()      // Wait in line
    mutex.wait()
    read_count++
    if (read_count == 1):
        resource.wait()
    service_queue.signal()    // Let next in queue proceed
    mutex.signal()
    
    // READ DATA
    
    mutex.wait()
    read_count--
    if (read_count == 0):
        resource.signal()
    mutex.signal()

Writer():
    service_queue.wait()      // Wait in line
    resource.wait()           // Get exclusive access
    service_queue.signal()    // Can release: we have resource
    
    // WRITE DATA
    
    resource.signal()

Analysis: service_queue enforces FIFO ordering. Readers and writers alternate fairly. No starvation for either party.

Readers-Writers Variants Comparison
Variant	Read Concurrency	Write Priority	Starvation
First (Readers Preference)	Maximum	Low	Writers can starve
Second (Writers Preference)	Limited	High	Readers can starve
Third (Fair)	Moderate	Equal	None

Dining Philosophers: Deadlock and Solutions

The dining philosophers problem is specifically designed to illustrate deadlock. It's essential for demonstrating your understanding of deadlock conditions and prevention strategies.

Problem Statement:

5 philosophers sit around a circular table
5 forks are placed between them (one between each adjacent pair)
To eat, a philosopher needs both the left and right fork
Philosophers alternate between thinking and eating
Goal: No deadlock, no starvation

Naive Solution (DEADLOCKS!):

Philosopher(i):
    while (true):
        think()
        pick_up(fork[i])          // Left fork
        pick_up(fork[(i+1) % 5])  // Right fork
        eat()
        put_down(fork[i])
        put_down(fork[(i+1) % 5])

Deadlock Scenario: All 5 philosophers simultaneously pick up their left fork. Each waits for their right fork—which is another philosopher's left fork. Circular wait → Deadlock!

The Four Deadlock Conditions

For deadlock to occur, ALL four conditions must hold simultaneously:

Mutual Exclusion: Forks can only be held by one philosopher
Hold and Wait: Philosophers hold left fork while waiting for right
No Preemption: Forks cannot be forcibly taken
Circular Wait: Philosopher 0 waits for 1, 1 waits for 2, ..., 4 waits for 0

Breaking ANY one condition prevents deadlock!

Solution 1: Resource Hierarchy (Break Circular Wait)

Number forks 0-4. Always acquire lower-numbered fork first.

Philosopher(i):
    while (true):
        think()
        first = min(i, (i+1) % 5)
        second = max(i, (i+1) % 5)
        pick_up(fork[first])
        pick_up(fork[second])
        eat()
        put_down(fork[second])
        put_down(fork[first])

Why it works: Philosopher 4's forks are 4 and 0. They pick up 0 first. This breaks the circular chain—no one holds a higher fork while waiting for a lower one.

Solution 2: Limit Diners (Break Hold-and-Wait)

Allow at most 4 philosophers to attempt eating simultaneously.

room = Semaphore(4)  // Only 4 can try to eat

Philosopher(i):
    while (true):
        think()
        room.wait()              // Limit concurrency
        pick_up(fork[i])
        pick_up(fork[(i+1) % 5])
        eat()
        put_down(fork[i])
        put_down(fork[(i+1) % 5])
        room.signal()

Why it works: With only 4 philosophers at the table, circular wait is impossible—there's always at least one available fork.

Solution 3: Chandy/Misra (Optimistic with Backoff)

Forks are "dirty" or "clean". Philosophers request forks, may get denied.

Philosopher(i):
    while (true):
        think()
        request_forks()  // Politely request both forks
        eat()            // Clean forks after eating
        mark_forks_dirty()

Rules:

After eating, forks become dirty
If neighbor requests your dirty fork, give it up (cleaned)
Only give up dirty forks
Initially, all forks are dirty, given to lower-numbered philosopher

This is the most efficient solution but rarely tested in depth.

Solution 4: Monitor with Condition Variables

state[5] = THINKING  // Each philosopher's state
state_lock = Mutex()
condition[5] = ConditionVariable()  // One per philosopher

Philosopher(i):
    while (true):
        think()
        take_forks(i)
        eat()
        put_forks(i)

take_forks(i):
    state_lock.acquire()
    state[i] = HUNGRY
    test(i)  // Try to acquire
    while (state[i] != EATING):
        condition[i].wait(state_lock)
    state_lock.release()

put_forks(i):
    state_lock.acquire()
    state[i] = THINKING
    test(LEFT)   // Wake left neighbor if waiting
    test(RIGHT)  // Wake right neighbor if waiting
    state_lock.release()

test(i):
    // Can philosopher i eat?
    if (state[i] == HUNGRY and 
        state[LEFT] != EATING and 
        state[RIGHT] != EATING):
        state[i] = EATING
        condition[i].signal()

This is the most commonly expected interview solution.

Dining Philosophers Solutions Comparison
Solution	Mechanism	Condition Broken	Parallelism
Resource Hierarchy	Ordered acquisition	Circular Wait	2 can eat simultaneously
Limit Diners (n-1)	Semaphore limit	Hold-and-Wait denied	2 can eat simultaneously
Chandy/Misra	Request/defer protocol	Hold-and-Wait relaxed	Maximum possible
Monitor Solution	Explicit state machine	Coordinated acquisition	2 can eat simultaneously

Identifying and Fixing Race Conditions

Beyond classic problems, interviewers frequently present buggy code and ask you to identify race conditions. This requires systematic analysis of all possible interleavings.

What is a Race Condition?

A race condition occurs when the program's correctness depends on the relative timing of events—specifically, when:

Multiple threads access shared data
At least one thread writes to the data
Access is not properly synchronized
The outcome differs based on which thread "wins the race"

Analysis Framework:

Identify shared state: What data is accessed by multiple threads?
Identify read-write patterns: Which threads read? Which write?
Find critical sections: Where must access be atomic?
Consider interleavings: What happens if Thread A is interrupted mid-operation?
Construct attack scenario: Show a specific interleaving that causes incorrect behavior

Example: Broken Counter

int counter = 0;

void increment() {
    counter = counter + 1;  // Race condition!
}

Bug Analysis:

This single line is NOT atomic. It compiles to:

Load counter into register
Add 1 to register
Store register to counter

Attack Scenario:

Initial: counter = 0
Thread A: Load counter (0) into register
Thread B: Load counter (0) into register
Thread A: Add 1 (register = 1)
Thread B: Add 1 (register = 1)
Thread A: Store 1 to counter
Thread B: Store 1 to counter
Final: counter = 1 (should be 2!)

Fix:

mutex_t lock;

void increment() {
    mutex_lock(&lock);
    counter = counter + 1;
    mutex_unlock(&lock);
}

Subtle Race Condition Example

if (ptr != NULL) {
    use(ptr);  // Race: ptr could become NULL between check and use!
}

This time-of-check-to-time-of-use (TOCTOU) bug is common in security vulnerabilities. Another thread could set ptr = NULL after the check but before the use.

Common Race Condition Patterns:

Pattern	Example	Risk
Check-then-act	`if (x > 0) x--;`	Value changes between check and act
Read-modify-write	`counter++`	Non-atomic update sequence
Lazy initialization	`if (instance == NULL) create()`	Double creation
Compound operations	`if (map.containsKey(k)) map.get(k)`	Key removed between check and get

Debug Strategy:

When analyzing for races:

List all shared variables
For each, determine thread access pattern
Look for non-atomic compound operations
Check for missing locks around multi-step operations
Verify lock consistency (all accesses protected by same lock)

double_checked_locking.java
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// BROKEN Double-Checked Locking (without volatile)
class Singleton {
    private static Singleton instance;  // BUG: needs volatile!
    
    public static Singleton getInstance() {
        if (instance == null) {              // First check (no lock)
            synchronized (Singleton.class) {
                if (instance == null) {      // Second check (with lock)
                    instance = new Singleton();  // Reordering bug!
                }
            }
        }
        return instance;
    }
}
 
// Why it's broken:
// The constructor call "instance = new Singleton()" involves:
// 1. Allocate memory for Singleton
// 2. Initialize Singleton fields
// 3. Assign reference to instance
// 
// Without volatile, compiler/CPU may reorder to: 1 -> 3 -> 2
// Thread A executes 1, 3 (instance is non-null but not initialized)
// Thread B sees non-null instance, returns it, uses uninitialized object!
 
// CORRECT version:
class SingletonFixed {
    private static volatile Singleton instance;  // volatile prevents reordering
    
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (SingletonFixed.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

Deadlock Detection and Prevention

Deadlock questions require you to analyze whether deadlock is possible, detect it in running systems, or modify solutions to prevent it.

Deadlock Definition:

A set of processes is deadlocked if each process is waiting for a resource held by another process in the set, forming a cycle with no way to make progress.

The Four Necessary Conditions (Coffman Conditions):

Mutual Exclusion: Resources cannot be shared
Hold and Wait: Processes hold resources while waiting for others
No Preemption: Resources cannot be forcibly taken
Circular Wait: Circular chain of processes, each waiting for next's resource

ALL FOUR must hold for deadlock to occur.

Resource Allocation Graph (RAG) Analysis:

Draw a directed graph:

Nodes: Processes (circles) and Resources (rectangles)
Request edge: P → R (process P wants resource R)
Assignment edge: R → P (resource R assigned to process P)

Deadlock Detection:

For single-instance resources: Deadlock ⟺ cycle in RAG
For multi-instance resources: Cycle is necessary but not sufficient; use banker's algorithm

Example RAG:

P1 → R1 → P2 → R2 → P1  (Cycle! Deadlock if R1, R2 are single instance)

Banker's Algorithm for Deadlock Avoidance:

Given:

Available[]: Resources currently available
Max[][]: Maximum resources each process may need
Allocation[][]: Resources currently allocated to each process
Need[][] = Max - Allocation: Resources still needed

Safety Algorithm:

1. Work = Available (copy)
   Finish[] = false for all processes

2. Find process i such that:
   - Finish[i] == false
   - Need[i] <= Work (can complete with available)

3. If found:
   Work = Work + Allocation[i]  (release resources)
   Finish[i] = true
   Go to step 2

4. If Finish[] all true: SAFE
   Otherwise: UNSAFE (potential deadlock)

Resource Request Algorithm:

When process P requests resources:

If Request > Need: Error (exceeds declared max)
If Request > Available: P waits
Pretend-allocate: Available -= Request, Allocation[P] += Request
Run safety algorithm
If safe: Grant. If unsafe: Rollback, P waits.

Interview Approach

Prevention Strategies (Break Each Condition):

Condition	Prevention Strategy	Tradeoff
Mutual Exclusion	Make resources sharable (readers-writers)	Not always possible
Hold and Wait	Request all resources at start	Poor resource utilization
No Preemption	Allow resource preemption	May cause inconsistency
Circular Wait	Impose resource ordering	Limits flexibility

Practical Choices:

Ordering (circular wait prevention): Most common in practice. All programs acquire resources in same global order.
Timeout (break no-preemption): If lock not acquired in time, release all held locks and retry. Used in databases.
Detection and Recovery: Let deadlock happen, detect via periodic RAG analysis, kill a process to break it.

Additional Classic Synchronization Problems

Beyond the core three problems, several other classic problems frequently appear in interviews.

The Sleeping Barber Problem:

One barber, N waiting chairs
If no customers, barber sleeps
Arriving customer wakes barber OR waits (if chairs available) OR leaves

Solution Sketch:

barber_ready = Semaphore(0)    // Barber signals readiness
customer_ready = Semaphore(0)  // Customer signals arrival  
mutex = Semaphore(1)           // Protect waiting count
waiting = 0                    // Number waiting

Barber():
    while (true):
        customer_ready.wait()  // Sleep until customer
        barber_ready.signal()  // Signal ready for haircut
        cut_hair()

Customer():
    mutex.wait()
    if (waiting < N):
        waiting++
        customer_ready.signal()  // Wake barber
        mutex.signal()
        barber_ready.wait()      // Wait for barber
        waiting--
        get_haircut()
    else:
        mutex.signal()           // No chairs, leave

Cigarette Smokers Problem:

Three smokers, each has infinite supply of one ingredient (tobacco, paper, matches). An agent places two ingredients on table. Smoker with third ingredient takes them, smokes, signals agent.

Challenge: The straightforward solution deadlocks. Each smoker waits for their two needed ingredients specifically.

Key Insight: Requires intermediate "pusher" threads that observe which two ingredients are on table and signal the appropriate smoker.

The H₂O Problem:

Multiple hydrogen and oxygen threads. Must bond exactly 2 hydrogens with 1 oxygen to form water, then release all three together.

Solution uses a barrier:

Hydrogens wait at barrier until 2 present and 1 oxygen
Oxygen waits at barrier for 2 hydrogens
All three release together

Building H₂O Problem (code sketch):

hydrogen_sem = Semaphore(0)
oxygen_sem = Semaphore(0)
barrier = Barrier(3)
mutex = Mutex()
hydrogen_count = 0

hydrogen():
    mutex.lock()
    hydrogen_count++
    if (hydrogen_count == 2):
        oxygen_sem.signal()    // Wake oxygen
        hydrogen_sem.signal()  // Let other hydrogen proceed
        hydrogen_count = 0
    mutex.unlock()
    
    hydrogen_sem.wait()        // Wait to be paired
    barrier.wait()             // Synchronize bonding
    // Bond!

oxygen():
    oxygen_sem.wait()          // Wait for 2 hydrogens
    hydrogen_sem.signal()      // Release second hydrogen
    barrier.wait()             // Synchronize bonding
    // Bond!

Barrier Synchronization

Summary: Synchronization Problem Mastery

Key Takeaways

•Know your primitives cold: Mutex vs semaphore vs condition variable—their semantics, use cases, and pitfalls.
•Master the classic three: Producer-consumer, readers-writers, dining philosophers form the foundation for all synchronization problems.
•Always use WHILE loops: Around condition variable waits, never IF. Spurious wakeups happen.
•Check for deadlock: Analyze ordering of lock acquisition. Break at least one Coffman condition for prevention.
•Construct attack scenarios: When analyzing race conditions, show a specific interleaving that causes failure.
•Verify all invariants: After designing a solution, check: no race, no deadlock, no starvation, progress guaranteed.

Page Complete

2 / 5