MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Operating Systems Module 5

Synchronisation: races, locks, semaphores and monitors interview questions

Interview questions on “Synchronisation: races, locks, semaphores and monitors”: warm-ups, then what each harder question tests and how a good answer starts.

19 questions: 5 warm-ups and 14 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    What three requirements must a solution to the critical-section problem meet, and what does each one rule out?

    Answered in the lesson Race conditions and the critical-section problem

  2. Fresher to mid

    How does Peterson's algorithm keep two threads out of their critical section at the same time?

    Answered in the lesson Peterson, Dekker and the bakery algorithm

  3. Fresher to mid

    What do test-and-set and compare-and-swap do, and what is each one used for?

    Answered in the lesson Hardware atomics, memory order and spinlocks

  4. Fresher to mid

    What is a futex, and why are Linux mutexes built on one?

    Answered in the lesson Mutexes, futexes and lock contention

  5. Fresher to mid

    What is the difference between a binary semaphore and a mutex, and when do you use each?

    Answered in the lesson Semaphores: counting, binary and ordering

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Fresher to mid

    Four threads increment a shared int counter without a lock. A teammate says the code is fine because the test that checks the total has passed a thousand times in a row. What do you tell them, and how do you show them the bug?

    What it tests
    counter++ as a load, an add and a store; why passing tests and optimised builds hide lost updates; data races as undefined behaviour; ThreadSanitizer; and the fixes.
    First step
    Split counter++ into its three instructions and show one interleaving in which two threads load the same value, so one increment disappears. Passing tests only prove that the runs so far were lucky, or that the optimiser shrank the window. Then make it visible: build with -fsanitize=thread, which reports the data race even in a run whose total is right.
    Follow-ups

    From the lesson Race conditions and the critical-section problem

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  2. Mid to senior

    A booking service checks whether a show has seats left, then records the booking in a second step. Each step takes the same mutex for itself. Under load, two customers sometimes both get the last seat. Explain why, and fix it.

    What it tests
    Check-then-act as a race condition without a data race, why locking each step separately does not help, one critical section or a conditional update, and a test that reproduces the bug.
    First step
    Each step is protected, but the pair is not: between one customer's check and their booking, the mutex is free, so a second customer's check can still see the last seat. The decision and the update must be one atomic action: hold the mutex across both, or let the store do it in one conditional update.
    Follow-ups

    From the lesson Race conditions and the critical-section problem

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  3. Mid to senior

    A colleague protects a two-thread ring buffer with Peterson's algorithm on plain int variables. Debug builds work; the release build hangs on one machine and loses data on another. Explain both failures and what you would ship instead.

    What it tests
    What an optimiser may do to plain shared variables, store-buffer reordering in the processor, volatile against atomics, sequentially consistent ordering and fences, and choosing a real lock.
    First step
    Treat it as two bugs with one root: the proof assumes that every read returns the latest write. Ask what the optimiser may assume about a plain variable that another thread writes, which explains the hang, and what each core may do with its own stores before other cores see them, which explains the lost data. Then decide what restores the assumption, and what you would ship.
    Follow-ups

    From the lesson Peterson, Dekker and the bakery algorithm

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  4. Fresher to mid

    In a protocol for two threads, thread i sets flag[i] = true and then waits while flag[j] is true; after its critical section it sets flag[i] = false. Which of mutual exclusion, progress and bounded waiting hold? Prove each answer.

    What it tests
    Building a counter-example schedule, arguing mutual exclusion from the order of a write and a read, and telling deadlock apart from starvation.
    First step
    Look for a schedule that breaks each requirement before trying to prove it. Both threads can raise their flags before either tests, and then each waits for the other for ever, so progress fails. Mutual exclusion holds: a thread enters only after raising its own flag and then seeing the other's down.
    Follow-ups

    From the lesson Peterson, Dekker and the bakery algorithm

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  5. Mid to senior

    Why does Lamport's bakery algorithm need its choosing flags? Give a schedule in which two threads both enter without them, and say exactly what the flags change.

    What it tests
    The role of the doorway, ticket taking as a read followed by a write, tie-breaking by thread id, and reasoning from a counter-example.
    First step
    Write taking a ticket as what it is, a read of the other tickets followed later by a write of your own, and look at the moment between the two. Ask what the other thread sees if it compares tickets in that moment, and what the tie-break does once both tickets are written. Then say what a thread must wait for before it compares.
    Follow-ups

    From the lesson Peterson, Dekker and the bakery algorithm

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  6. Mid to senior

    A service protects a shared hash map with a test-and-set spinlock. With 8 threads on 8 cores it is fast; with 32 threads on the same 8 cores, CPU use is 100 % and throughput collapses. Explain, with numbers, and choose a fix.

    What it tests
    Why spinning wastes a time slice when the lock holder is not running, cache-line traffic of test-and-set, ticket lock behaviour under oversubscription, and when to sleep instead.
    First step
    Count runnable threads against cores. With 32 threads on 8 cores, a holder is often preempted inside the critical section, and every waiter then spins through its whole time slice while nothing can progress. Spin only when the holder runs on another core and the hold time is short; otherwise use a lock that sleeps.
    Follow-ups

    From the lesson Hardware atomics, memory order and spinlocks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  7. Mid to senior

    A thread fills a config struct and then sets an atomic ready flag with memory_order_relaxed; readers spin on the flag with relaxed loads and then read the struct. Tests on x86 laptops pass, but on Arm servers readers sometimes see half-built configs. Explain and fix it with the weakest correct orders.

    What it tests
    Release and acquire as a pair, why x86 hides the bug, the weakest correct orders, and why relaxed is right only when nobody synchronises on the value.
    First step
    The flag is atomic but orders nothing: relaxed lets the struct's stores and the flag's store become visible in another order, and lets a reader's struct loads run before its flag load. Make the flag's store a release and the reader's load an acquire, then work out why the x86 tests never showed the bug.
    Follow-ups

    From the lesson Hardware atomics, memory order and spinlocks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  8. Senior to staff

    A lock-free stack pops with a compare-and-swap on its head pointer and reuses freed nodes. About once a day under load it loses nodes or crashes. Explain the ABA problem, show the schedule, and compare two fixes with their costs.

    What it tests
    The ABA schedule, why compare-and-swap cannot see it, tagged pointers or version counters, safe memory reclamation with hazard pointers or epochs, and what each fix costs.
    First step
    Start from what the compare-and-swap really checks: that the head holds the pointer it read, not that nothing happened in between. Write down a schedule in which one pop stalls between its read and its swap while another thread changes the stack and the same node comes back to the head. Then decide whether to fix the comparison or the reuse of nodes, and what each costs.
    Follow-ups

    From the lesson Hardware atomics, memory order and spinlocks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  9. Mid to senior

    A service writes a log line to a network collector while holding the mutex that guards its request table. Under load, p99 latency rises from 5 ms to 400 ms while CPU use stays at 30 %. Explain what is happening and fix it.

    What it tests
    Seeing contention as a queue on the lock, why low CPU with high latency points at waiting, what holding a lock across I/O does, and how to move the slow work out.
    First step
    Measure how long the mutex is held and how long threads wait for it. A network send inside the critical section makes the hold time milliseconds, so every request that needs the table queues behind it, asleep, which is why CPU is low. Copy what the log line needs under the lock and send it after unlocking, or hand it to a queue.
    Follow-ups

    From the lesson Mutexes, futexes and lock contention

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  10. Senior to staff

    An in-memory cache behind one mutex serves 300,000 lookups a second on 4 cores but does not get faster on 32. How do you show that the lock is the limit, and how would you split it without new bugs?

    What it tests
    Measuring contention, estimating a lock's capacity from its hold time, lock striping and its collision odds, ordering several locks, and alternatives for read-mostly data.
    First step
    Measure wait time on the mutex and the hold time per lookup: one lock can serve at most one lookup per hold time, so a 3-microsecond hold caps it near 330,000 a second whatever the core count. Then split the map so that lookups of different keys need different locks, and decide how an operation that needs several of them takes them.
    Follow-ups

    From the lesson Mutexes, futexes and lock contention

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  11. Mid to senior

    To signal that data is ready, thread A locks a pthread mutex at start-up and thread B unlocks it when the data is written; a waiting thread then locks it. It passes tests on Linux. What is wrong, and what should it use?

    What it tests
    Mutex ownership, why an unlock by a non-owner is undefined for a normal mutex, what error-checking mutexes report, and choosing a semaphore or a condition variable for signalling.
    First step
    A mutex has an owner and only the owner may unlock it: for the default type, B's unlock is undefined behaviour that happens to work today, and an error-checking mutex would return EPERM. Signalling between threads needs a tool without an owner, such as a semaphore that B posts, or a condition variable with a ready flag.
    Follow-ups

    From the lesson Mutexes, futexes and lock contention

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  12. Mid to senior

    A cache is guarded by a semaphore that starts at 1, with sem_wait before each update and sem_post after it. Under load, two threads are sometimes inside at once and the cache is corrupted. How do you find the cause and fix it?

    What it tests
    The semaphore invariant, why a semaphore cannot detect a stray post, finding unmatched P and V pairs, and replacing the lock with a mutex.
    First step
    Use the invariant: the value is 1 plus the posts minus the completed waits, so two threads inside means some sem_post ran without a matching sem_wait, often on an error path or a retry. Count waits and posts per thread, or log the value, to find it; then replace the semaphore with a mutex, which reports such an unlock.
    Follow-ups

    From the lesson Semaphores: counting, binary and ordering

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  13. Mid to senior

    A service limits itself to 20 concurrent calls to a payment provider with a counting semaphore. After several days every request hangs, although the provider is healthy. Explain the likely cause, how to confirm it and how to prevent it.

    What it tests
    Counting semaphores as permits, leaks on error paths, using the invariant to confirm a leak, scoped release, and timeouts on the wait.
    First step
    Use the invariant: the value is 20 plus the posts minus the completed waits. If every call waits while few or none are in flight, some completed waits were never matched by a post. Compare the semaphore's value with the calls in flight to confirm it, then look for the paths between a wait and its post that can leave early.
    Follow-ups

    From the lesson Semaphores: counting, binary and ordering

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  14. Fresher to mid

    Two threads must both finish set-up before either starts work. Each waits on the other's semaphore, both starting at 0, and then posts its own. The program hangs every time. Explain why and fix it.

    What it tests
    The rendezvous pattern, why waiting before signalling deadlocks, checking the order with schedules, and extending the idea to N threads with a barrier.
    First step
    Trace both threads from the start: for each wait, find the post that can release it and what the posting thread must do before it gets there. Decide whether any schedule gets both threads past their waits; if none does, the bug is the order of the operations, not the timing.
    Follow-ups

    From the lesson Semaphores: counting, binary and ordering

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

All Operating Systems interview questions · The Operating Systems track