Autocoder

Process Synchronization Interview Questions: Semaphores, Mutex and Classic Problems

Last updated 2026-11-19

Synchronization is the part of operating systems where small details decide whether an answer is right: the order of wait and signal, whether a semaphore starts at 0 or 1, whether a lock is held while sleeping. Interviews ask you to define the critical section problem, compare a mutex with a semaphore, trace the value of a semaphore after a series of operations, and write the producer-consumer solution.

This page covers those, plus Peterson's algorithm, hardware atomic instructions, monitors and the readers-writers and dining philosophers problems. The same ideas return in Java and Python concurrency questions, so the code samples use real threading libraries. For the surrounding subject see operating systems interview questions, and for deadlocks caused by bad lock order see deadlock interview questions.

Three requirementsMutual exclusion, progress, bounded waiting
Classic problemsProducer-consumer, readers-writers, dining philosophers
CodePython lock fix for a race, semaphore producer-consumer

Semaphore rules that settle most questions

Process Synchronization Interview Questions: questions with worked answers

  1. 1

    What is the critical section problem and what three requirements must a solution satisfy?

    easy

    A critical section is a segment of code that accesses shared data and must not be executed by more than one process at a time. A solution must give mutual exclusion (only one inside), progress (if none is inside and some want to enter, only those not in their remainder section decide who enters and the decision cannot be postponed forever) and bounded waiting (there is a limit on how many times others may enter after a process has requested entry, so nobody starves).

  2. 2

    What is a race condition? Show one and fix it.

    easy

    The final value depends on thread timing. counter += 1 is really three steps (load, add, store), so two threads can both load 5 and both store 6, losing an update. Protecting the update with a lock makes it atomic.

    python
    import threading
    counter = 0
    lock = threading.Lock()
    
    def work(n):
        global counter
        for _ in range(n):
            with lock:          # remove this line to see lost updates
                counter += 1
    
    ts = [threading.Thread(target=work, args=(100000,)) for _ in range(4)]
    for t in ts: t.start()
    for t in ts: t.join()
    print(counter)              # always 400000 with the lock
  3. 3

    Explain Peterson's algorithm and what it guarantees.

    medium

    Peterson's algorithm solves mutual exclusion for two processes using shared variables flag[2] and turn. To enter, process i sets flag[i] = true, then sets turn = j (giving priority to the other), and spins while flag[j] is true and turn == j. On exit it sets flag[i] = false. It satisfies mutual exclusion, progress and bounded waiting. On modern CPUs with instruction reordering it needs memory barriers to be correct, so in practice hardware atomics or OS locks are used.

  4. 4

    What are test-and-set and compare-and-swap, and how do they build a lock?

    medium

    They are atomic hardware instructions. Test-and-set reads a memory word and sets it to 1 in one indivisible step, returning the old value. A spinlock loops while test-and-set returns 1; when it returns 0 the caller has acquired the lock, and release writes 0. Compare-and-swap (CAS) atomically sets a location to a new value only if it equals an expected value, and is the basis of lock-free data structures and Java's AtomicInteger.

  5. 5

    Differentiate between a mutex and a semaphore.

    medium

    A mutex is a locking mechanism with ownership: only the thread that locked it should unlock it, and it protects a critical section. A semaphore is a signalling counter with no owner: any thread may signal it, and a counting semaphore can admit up to N threads or count available resources. A binary semaphore resembles a mutex but lacks ownership, so it does not support priority inheritance and is better for signalling than for locking.

  6. 6

    Numerical: A counting semaphore is initialised to 10. 6 wait operations and 4 signal operations complete. What is its value? What if it was initialised to 1 and 3 waits occur?

    medium

    Each wait subtracts 1 and each signal adds 1. First case: 10 - 6 + 4 = 8. Second case: 1 - 3 = -2. The first wait takes the value to 0 and succeeds; the next two make it -1 and -2 and block, so the magnitude 2 equals the number of blocked processes.

  7. 7

    What is a spinlock? When is it better than a blocking lock?

    medium

    A spinlock makes a waiting thread loop (busy-wait) until the lock is free, using CPU time instead of sleeping. It avoids the cost of a context switch, so it wins when the lock is held for less time than a switch takes, as in short kernel critical sections on multiprocessors. On a single CPU it is pointless because the holder cannot run while the waiter spins. Long waits should block instead.

  8. 8

    Write the bounded-buffer (producer-consumer) solution using semaphores.

    medium

    Use three semaphores: empty = N counts free slots, full = 0 counts filled slots, mutex = 1 protects the buffer. The producer waits on empty, then mutex, inserts, signals mutex, then signals full. The consumer waits on full, then mutex, removes, signals mutex, then signals empty. Reversing the order of waiting on mutex and on empty/full can deadlock: a producer holding mutex with a full buffer would block forever while the consumer cannot get mutex.

    python
    import threading, collections
    N = 5
    buf = collections.deque()
    empty = threading.Semaphore(N)
    full = threading.Semaphore(0)
    mutex = threading.Lock()
    
    def producer():
        for i in range(20):
            empty.acquire()
            with mutex: buf.append(i)
            full.release()
    
    def consumer():
        for _ in range(20):
            full.acquire()
            with mutex: item = buf.popleft()
            empty.release()
            print(item)
  9. 9

    Describe the readers-writers problem and the starvation issue.

    medium

    Many readers may read shared data at once, but a writer needs exclusive access. In the first readers-writers solution readers have priority: the first reader locks the writers out (wrt semaphore) and the last reader releases it, with a mutex guarding the reader count. A steady stream of readers can starve a writer. The second version gives writers priority and can starve readers. Fair solutions queue requests in arrival order, and many systems provide read-write locks.

  10. 10

    Explain the dining philosophers problem with a semaphore solution.

    medium

    Five philosophers alternate thinking and eating, and each needs the fork on both sides. Representing each fork as a semaphore and letting every philosopher take the left fork first can deadlock when all hold one. A correct solution limits the table to four philosophers using a semaphore initialised to 4, or makes one philosopher pick the right fork first, which breaks circular wait. Monitor-based solutions track a state (thinking, hungry, eating) and let a philosopher eat only if neither neighbour is eating.

  11. 11

    What is a monitor and how does it differ from a semaphore?

    medium

    A monitor is a language-level construct that bundles shared data with the procedures that access it, and the compiler guarantees that only one thread is active inside at a time. Threads that cannot proceed wait on condition variables using wait() and wake others with signal(). Java's synchronized methods with wait/notify are monitors. Monitors are easier to use correctly than raw semaphores because mutual exclusion is automatic and misordered wait and signal calls are far less likely.

  12. 12

    Why must condition variable waits be in a loop?

    medium

    A woken thread is not guaranteed that the condition still holds: another thread may have run first (a stolen wakeup), or the wakeup may be spurious. The standard idiom is while (!condition) wait(); so the condition is rechecked after every wakeup. Using if instead of while is a common source of rare, hard-to-reproduce bugs, such as a consumer taking from an empty queue.

  13. 13

    What is priority inversion and how do mutexes help avoid it?

    hard

    A low-priority thread holds a lock that a high-priority thread needs, and a medium-priority thread runs instead of the low one, delaying the high-priority thread indefinitely. Priority-inheritance mutexes temporarily raise the holder to the priority of the highest waiter so it can finish and release the lock. Priority ceiling protocols assign each lock a ceiling priority that holders run at. Real-time operating systems rely on these.

  14. 14

    What is a deadlock-prone use of semaphores? Give an example.

    hard

    Two semaphores acquired in opposite orders: process P does wait(S); wait(Q), process R does wait(Q); wait(S). If each completes its first wait, both block forever. Another is signalling before waiting in the wrong order so the wakeup is lost and a thread blocks forever. The remedies are a global acquisition order, timeouts with try-acquire, and holding at most one lock at a time. See deadlock interview questions.

  15. 15

    What is the difference between a user-space lock like a futex and a pure kernel lock?

    hard

    A futex (fast userspace mutex) on Linux handles the uncontended case entirely in user space with an atomic operation on a shared integer, with no system call. Only when there is contention does the thread call into the kernel to sleep or wake. Since most lock acquisitions are uncontended, this makes locking much cheaper than a system call on every lock and unlock, while keeping blocking behaviour for the contended case.

Frequently asked questions

What is the difference between wait/signal on semaphores and wait/notify in Java?

Semaphore signal increments a counter, so a signal sent before a wait is remembered. Java notify wakes a waiting thread only if one is already waiting, and a notify with no waiters is lost, which is why the condition must be tested in a loop under the lock.

Can a mutex cause deadlock?

Yes, if two threads acquire two mutexes in opposite orders, or if a thread tries to relock a non-recursive mutex it already holds. Lock ordering prevents the first; recursive mutexes or better design prevent the second.

What are atomic operations and why are they useful?

They complete as one indivisible step, so no other thread can see an intermediate state. Atomic counters and compare-and-swap avoid locks for simple shared state and are the basis of lock-free structures.

Is synchronization needed on a single-core CPU?

Yes. A thread can be preempted in the middle of a read-modify-write, so a race can still occur. A single core does remove the need for spinlocks in many cases and for memory-ordering between cores.

Related guides

More in CS Fundamentals Interview Questions

See all in this section