Free lesson · Operating Systems

What's wrong?

Easy13 min readoperating-systemsosconcurrency

How Synchronization Questions Appear in Interviews

Synchronization questions in FAANG interviews come in four forms. The first is conceptual - "explain what a mutex is" or "what is the difference between a semaphore and a condition variable." The second is bug identification - "what is wrong with this concurrent code." The third is design - "design a thread-safe data structure" or "how would you prevent deadlock in this system." The fourth is system design connection - "how does your web server handle concurrent requests" or "how does the database prevent lost updates."

This topic prepares you for all four forms by showing you the exact patterns that appear, the structured answers interviewers expect, and the common follow-up questions that separate strong candidates from average ones.

Pattern 1: "Explain the Difference Between X and Y"

These are the warm-up questions. They test whether you have a precise mental model or just memorized definitions. The key to a strong answer is to state the core difference in one sentence, then support it with a practical implication.

Mutex vs Semaphore

The core difference: A mutex provides mutual exclusion with ownership - the thread that locks it must unlock it. A semaphore is a counter with no ownership - any thread can signal it.

The practical implication: Mutexes are for protecting shared data (one writer at a time). Counting semaphores are for limiting concurrency (at most N threads). Binary semaphores are for signaling between threads (one thread waits, another signals).

The follow-up you should anticipate: "Can you implement a mutex using a semaphore?" Yes - a binary semaphore initialized to 1 behaves like a mutex for mutual exclusion, though without ownership semantics, recursive locking, or priority inheritance.

Semaphore vs Condition Variable

The core difference: A semaphore's signal accumulates (incrementing a counter). A condition variable's signal is lost if no thread is waiting (it does not accumulate). A semaphore is self-contained. A condition variable is always paired with a mutex.

The practical implication: Semaphores work well for counting problems where permits represent concrete resources. Condition variables work well for arbitrary boolean conditions that require evaluating shared state under a lock.

The follow-up: "Why must you always use a while loop with condition variables but not with semaphores?" Because condition variables use Mesa semantics - the condition might change between the signal and the wakeup (stolen wakeups, spurious wakeups). A semaphore's wait is guaranteed to consume exactly one permit, so no re-check is needed.

Process vs Thread Synchronization

The core difference: Threads within the same process share an address space, so they can use in-memory mutexes, semaphores, and condition variables directly. Processes have separate address spaces, so they need either shared memory (with synchronization primitives placed in the shared region) or kernel-mediated synchronization (POSIX named semaphores, file locks, pipes).

The practical implication: Thread synchronization is faster (no system calls for user-space locks like futexes in the fast path). Process synchronization is more robust (a crashed process does not corrupt another process's memory, but a crashed thread can corrupt the entire process).

Deadlock vs Livelock vs Starvation

The core difference: Deadlock - threads are blocked forever, waiting for each other in a cycle. Nobody makes progress. Livelock - threads are active but keep undoing each other's work. They are running but not making progress (like two people stepping side to side in a hallway). Starvation - one thread makes progress while another never gets a chance, even though it is ready to run.

The practical implication: Deadlock is detected by finding cycles in the resource-allocation graph. Livelock is harder to detect - the system is active but throughput is zero. Starvation is prevented by fairness mechanisms (FIFO queues, aging).

Pattern 2: "What Is Wrong with This Code?"

Bug identification questions give you concurrent code and ask you to find the synchronization error. Here are the four most common bugs and how to spot them.

Bug 1: Missing Lock

# What's wrong?
counter = 0

def increment():
    global counter
    counter += 1  # Not protected - race condition

What to say: "counter += 1 is a read-modify-write operation that compiles to three instructions (load, add, store). Without a lock, two threads can interleave these instructions and lose updates. The fix is to wrap the increment in a mutex, or use an atomic operation."

Bug 2: Lock Scope Too Narrow

# What's wrong?
lock = threading.Lock()

def transfer(from_acct, to_acct, amount):
    with lock:
        balance = from_acct.balance
    # Lock released here - another thread can modify from_acct.balance
    with lock:
        from_acct.balance = balance - amount
        to_acct.balance += amount

What to say: "The lock is acquired and released between the read and the write. Between those two critical sections, another thread can modify from_acct.balance, making the read value stale. The entire read-modify-write sequence must be under a single lock acquisition."

Bug 3: Deadlock from Lock Ordering

# What's wrong?
def transfer(from_acct, to_acct, amount):
    from_acct.lock.acquire()
    to_acct.lock.acquire()
    # ... transfer ...
    to_acct.lock.release()
    from_acct.lock.release()

# Thread A: transfer(account_1, account_2, 100)
# Thread B: transfer(account_2, account_1, 50)
# Thread A holds account_1's lock, waits for account_2's lock
# Thread B holds account_2's lock, waits for account_1's lock
# DEADLOCK

What to say: "Two threads acquiring the same two locks in opposite order creates a circular wait - one of the four Coffman conditions for deadlock. The fix is lock ordering: always acquire locks in a consistent order, such as by account ID. The thread that needs accounts 1 and 2 always locks account 1 first, regardless of which is the source and which is the destination."

# FIXED: consistent lock ordering
def transfer(from_acct, to_acct, amount):
    first, second = sorted([from_acct, to_acct], key=lambda a: a.id)
    first.lock.acquire()
    second.lock.acquire()
    # ... transfer ...
    second.lock.release()
    first.lock.release()

Bug 4: Condition Variable with if Instead of while

// What's wrong?
synchronized void consume() throws InterruptedException {
    if (queue.isEmpty()) {    // BUG: should be while
        wait();
    }
    Item item = queue.remove();  // Might throw - queue could be empty!
}

What to say: "Using if instead of while with a condition variable is a bug. After wait() returns, the condition might be false - either due to a spurious wakeup, or because another thread consumed the item between the signal and this thread re-acquiring the monitor. The while loop re-checks the condition after every wakeup."

Interview: General strategy for "find the bug" questions:

1. Identify the shared state. What data is accessed by multiple threads?
2. Check for missing synchronization. Is every access to shared state protected?
3. Check lock scope. Does the lock cover the entire logical operation, or just individual accesses?
4. Check for deadlock. Are multiple locks acquired? If so, is the order consistent?
5. Check condition variable discipline. Is wait in a while loop? Is the mutex held?

Walk the interviewer through these steps explicitly. Showing your systematic approach matters as much as finding the bug.

Pattern 3: "Design a Thread-Safe X"

Design questions ask you to build a concurrent data structure or system component. The approach is always the same: start with the single-threaded version, identify the shared state, then add synchronization.

graph TD
    S1["Step 1: Define the interface<br/>What operations does it support?"] --> S2["Step 2: Identify shared state<br/>What data do multiple threads touch?"]
    S2 --> S3["Step 3: Choose synchronization<br/>Mutex? Monitor? RWLock? Lock-free?"]
    S3 --> S4["Step 4: Implement<br/>Add locks, CVs, or atomics"]
    S4 --> S5["Step 5: Discuss tradeoffs<br/>Granularity, performance, alternatives"]
    
    style S1 fill:#4f46e5,stroke:#4338ca,color:#fff
    style S2 fill:#4f46e5,stroke:#4338ca,color:#fff
    style S3 fill:#4f46e5,stroke:#4338ca,color:#fff
    style S4 fill:#4f46e5,stroke:#4338ca,color:#fff
    style S5 fill:#4f46e5,stroke:#4338ca,color:#fff

This diagram shows the five-step approach for designing a thread-safe data structure in an interview. Step 1 is defining the interface and the operations it supports. Step 2 is identifying the shared state that multiple threads access. Step 3 is choosing the right synchronization mechanism such as a mutex, monitor, read-write lock, or lock-free approach. Step 4 is implementing the solution by adding locks, condition variables, or atomic operations. Step 5 is discussing tradeoffs including lock granularity, performance characteristics, and alternative approaches.

Example: Thread-Safe Bounded Queue

Step 1: Define the interface.

class ThreadSafeQueue:
    def put(self, item):    # Add item - block if full
        ...
    def get(self):           # Remove item - block if empty
        ...
    def size(self):          # Current number of items
        ...

Step 2: Identify shared state. The internal list/array, the count, and the read/write indices are all shared.

Step 3: Choose synchronization. A monitor (mutex + condition variables) is the cleanest choice. Two conditions: "not full" for producers, "not empty" for consumers.

Step 4: Implement with synchronization.

import threading

class ThreadSafeQueue:
    def __init__(self, capacity):
        self._queue = []
        self._capacity = capacity
        self._lock = threading.Condition()
    
    def put(self, item):
        with self._lock:
            while len(self._queue) >= self._capacity:
                self._lock.wait()
            self._queue.append(item)
            self._lock.notify_all()
    
    def get(self):
        with self._lock:
            while len(self._queue) == 0:
                self._lock.wait()
            item = self._queue.pop(0)
            self._lock.notify_all()
            return item
    
    def size(self):
        with self._lock:
            return len(self._queue)

# Quick verification
q = ThreadSafeQueue(3)
results = []

def producer():
    for i in range(5):
        q.put(i)

def consumer():
    for i in range(5):
        results.append(q.get())

t1 = threading.Thread(target=producer)
t2 = threading.Thread(target=consumer)
t1.start()
t2.start()
t1.join()
t2.join()
print(f"Results: {sorted(results)}")
print(f"All items received: {sorted(results) == [0,1,2,3,4]}")

Step 5: Discuss tradeoffs. After implementing, discuss:

• "I used notify_all() which wakes all waiters. For better performance, I could use two separate condition variables - one for producers and one for consumers - and use notify() to wake only the relevant waiter."
• "This uses a single lock, which serializes all access. For higher concurrency, I could use a lock-free implementation with CAS, but that is significantly more complex."
• "The pop(0) is O(n) for a list. In production, I would use collections.deque for O(1) pops from the left, or a circular buffer with head/tail indices."

Example: Design a ReadWriteLock

The interview approach:

"I would maintain three pieces of state: a reader count, a writer-active flag, and a writer-waiting flag. All three are protected by a mutex, and I would use two condition variables - one for readers to wait on and one for writers to wait on.

read_lock(): Acquire the mutex. While a writer is active or a writer is waiting (writers-preferred policy), wait on the readers' condition variable. Increment the reader count. Release the mutex.

read_unlock(): Acquire the mutex. Decrement the reader count. If the count reaches zero, signal the writers' condition variable - a waiting writer can now proceed. Release the mutex.

write_lock(): Acquire the mutex. Set writer-waiting to true. While a writer is active or the reader count is greater than zero, wait on the writers' condition variable. Set writer-active to true, writer-waiting to false. Release the mutex.

write_unlock(): Acquire the mutex. Set writer-active to false. Signal the writers' condition variable (for a waiting writer) and broadcast the readers' condition variable (for waiting readers). Release the mutex."

Then discuss: "This is writers-preferred because new readers block while a writer is waiting. For readers-preferred, remove the writer-waiting check from read_lock(). For FIFO fairness, use a single queue rather than separate conditions."

Pattern 4: System Design Connections

In system design interviews, synchronization questions appear as sub-problems within larger designs. You are not asked to implement a mutex - you are asked how your system handles concurrent access, and the answer requires demonstrating that you understand synchronization at a design level.

"How does your database handle concurrent writes to the same row?"

Strong answer structure:

"There are two main approaches - pessimistic locking and optimistic locking.

Pessimistic locking acquires an exclusive lock on the row before reading it. No other transaction can read or write the row until the lock is released. This is like a mutex on the row. It guarantees consistency but reduces concurrency - other transactions are blocked even if they would not conflict.

Optimistic locking does not lock the row. Instead, each row has a version number. When a transaction reads the row, it records the version. When it writes, it checks that the version has not changed. If it has, the write fails and the transaction retries. This is like a compare-and-swap on the version field. It allows more concurrency but adds retry overhead when conflicts occur.

Most production databases also support MVCC (Multi-Version Concurrency Control), where readers see a snapshot of the data at their transaction's start time. Readers never block writers, and writers never block readers. Only writer-writer conflicts are detected. PostgreSQL and MySQL InnoDB both use MVCC."

"How does your web server handle 10,000 concurrent requests?"

Synchronization relevance: The thread pool is a producer-consumer system. The main thread accepts connections (producer) and adds them to a task queue. Worker threads (consumers) take connections from the queue and handle them. The queue is a bounded buffer protected by a mutex and condition variables.

"I would use a thread pool with a bounded task queue. The main thread accepts connections and adds them to the queue. Worker threads wait on a condition variable for new tasks. If the queue is full, the main thread either blocks (back-pressure) or rejects the connection (load shedding). The queue size and thread count are tuning parameters - too few threads underutilize the CPU, too many threads cause excessive context switching."

"What happens if two users try to buy the last item in stock?"

Synchronization relevance: This is the check-then-act race condition from Topic 2.

"Without proper synchronization, both users check the stock count, see 1 item available, and both proceed to purchase - creating an oversell. The fix is to use an atomic operation: UPDATE inventory SET count = count - 1 WHERE product_id = X AND count > 0. This is a compare-and-swap at the database level - the decrement only succeeds if the count is still positive. Only one of the two concurrent requests will succeed."

graph TD
    subgraph PATTERNS["Four Interview Question Patterns"]
        P1["Pattern 1: Explain X vs Y<br/>Mutex vs Semaphore<br/>Deadlock vs Livelock"]
        P2["Pattern 2: Find the Bug<br/>Missing lock, wrong scope,<br/>deadlock, if vs while"]
        P3["Pattern 3: Design Thread-Safe X<br/>Bounded queue, RWLock,<br/>thread pool"]
        P4["Pattern 4: System Design Connection<br/>Database concurrency,<br/>server architecture"]
    end
    
    P1 -->|"tests"| K1["Vocabulary and<br/>precise definitions"]
    P2 -->|"tests"| K2["Bug pattern recognition<br/>and systematic analysis"]
    P3 -->|"tests"| K3["Implementation skill<br/>and tradeoff reasoning"]
    P4 -->|"tests"| K4["Architectural understanding<br/>and real-world application"]

This diagram shows the four patterns of synchronization interview questions. Pattern 1, explaining the difference between concepts, tests vocabulary and precise definitions. Pattern 2, finding bugs in concurrent code, tests bug pattern recognition and systematic analysis. Pattern 3, designing thread-safe data structures, tests implementation skill and tradeoff reasoning. Pattern 4, system design connections, tests architectural understanding and real-world application of synchronization concepts.

Quick Reference: What to Know Cold

These are the facts and comparisons you should be able to state without hesitation:

The Four Coffman Conditions for Deadlock

1. Mutual exclusion - resources are non-shareable
2. Hold and wait - thread holds one resource while waiting for another
3. No preemption - resources cannot be forcibly taken
4. Circular wait - cycle of threads waiting for each other

Break any one to prevent deadlock. In practice, resource ordering (breaking circular wait) is the most common strategy.

The Three Requirements for Critical Section Solutions

1. Mutual exclusion - only one thread in the critical section at a time
2. Progress - if the critical section is free, some waiting thread must be able to enter
3. Bounded waiting - no thread waits forever

Synchronization Primitive Comparison

Performance Numbers for Interviews

Interview: Final preparation checklist for synchronization interviews:

1. Can you define mutual exclusion, progress, bounded waiting, deadlock, livelock, starvation, race condition, data race, critical section?

2. Can you explain the difference between mutex/semaphore, semaphore/condition variable, Hoare/Mesa monitors, spinlock/mutex, pessimistic/optimistic locking?

3. Can you implement a thread-safe bounded queue using condition variables? A simple spinlock using test-and-set? A read-write lock using a mutex and condition variables?

4. Can you identify the bug in concurrent code - missing locks, wrong lock scope, deadlock from lock ordering, if-instead-of-while on condition variables?

5. Can you connect synchronization concepts to system design - how your database handles concurrent writes, how your web server handles concurrent requests, how you prevent the lost-update problem in your application?

If you can do all five, you are well prepared for synchronization questions at any level.

Exercise: Starter: Without looking at notes, write down the four Coffman conditions for deadlock and the three requirements for a correct critical section solution. For each Coffman condition, name one practical strategy to break it. Check your answers against the quick reference above.

Intermediate: Given this code, identify all synchronization bugs and fix them:

import threading
accounts = {"A": 1000, "B": 1000}
lock_a = threading.Lock()
lock_b = threading.Lock()

def transfer_a_to_b(amount):
    lock_a.acquire()
    lock_b.acquire()
    if accounts["A"] >= amount:
        accounts["A"] -= amount
        accounts["B"] += amount
    lock_b.release()
    lock_a.release()

def transfer_b_to_a(amount):
    lock_b.acquire()
    lock_a.acquire()
    if accounts["B"] >= amount:
        accounts["B"] -= amount
        accounts["A"] += amount
    lock_a.release()
    lock_b.release()

Advanced: Design and implement a thread-safe LRU cache in Python. The cache should support get(key) and put(key, value) with a fixed capacity. When the cache is full and a new item is added, the least recently used item is evicted. Both get and put should be thread-safe using a mutex. Then optimize: is a single global lock the best approach, or could you use finer-grained locking? What are the tradeoffs? Implement both versions and compare their behavior under concurrent access from 10 threads.

Back to Operating Systems