Unit 6 · Self-check
Unit 6 Self-Check Quiz
Twenty-five questions covering race conditions, the critical-section problem, locks, semaphores, monitors, condition variables, and synchronization in Linux. Each question can be expanded to reveal a model answer.
Questions
Multiple choice and short answer
Answer each question before expanding. These span all seven lessons of Unit 6.
Question 1
What is a race condition, and what is the minimum condition under which one can occur?
Show answer
A race condition is a situation in which the output of a computation depends on the non-deterministic timing or interleaving of concurrent operations on shared state. It occurs whenever two or more threads (or processes) access a shared resource concurrently, at least one of the accesses is a write, and the accesses are not synchronised. All three conditions must hold: if there is no sharing, there is no race; if all accesses are reads, there is no race; if the accesses are protected by a lock or otherwise serialised, there is no race. Classic example:
counter++ performed by two threads — the read-modify-write sequence can interleave and lose an update.
Question 2
Which of the following is not a requirement of a correct critical-section solution?
Show answer
The fourth choice is not one of the classical three requirements. The three are mutual exclusion, progress, and bounded waiting. Bounded waiting does mean that a process cannot be indefinitely postponed, but it permits prioritised schemes in which a low-priority process waits longer than a high-priority one, as long as the wait is bounded. Strict starvation freedom for all processes irrespective of priority is stronger than what the classical problem requires, and many correct (if impolite) solutions do not provide it.
Question 3
Explain the difference between mutual exclusion, progress, and bounded waiting with a short example of a solution that satisfies two but not the third.
Show answer
Mutual exclusion: at most one thread is inside the critical section at a time. Progress: if no thread is in the critical section and some threads want to enter, the choice of which enters cannot be postponed indefinitely — some thread must be allowed to enter. Bounded waiting: after a thread has requested entry, there is a bound on how many times other threads may enter before it does. A classic example of a solution that satisfies mutual exclusion and progress but not bounded waiting is the naive test-and-set spinlock: it provides mutual exclusion and (on an unloaded system) progress, but a thread can be overtaken arbitrarily many times by others, so there is no bound on its wait. Adding a queue or ticket system (as in a ticket lock or Peterson's algorithm with a waiting array) restores bounded waiting.
Question 4
What is the essential idea of Peterson's algorithm, and why does it work?
Show answer
Peterson's algorithm uses two shared variables: a
flag array (one per thread) and a turn variable. To enter the critical section, a thread sets its flag to true and sets turn to the other thread's ID. It then waits until either the other thread's flag is false or the turn is its own. The combination is the key: a thread expresses both "I want to enter" (flag) and "I defer to the other" (turn). Mutual exclusion follows because the last writer of turn defers to the other; if both are inside, both would have to have set turn to each other, which is impossible. Progress and bounded waiting follow from the turn variable, which guarantees the waiting thread gets its chance on the next round. Peterson's algorithm is elegant but assumes sequential consistency; on modern hardware with relaxed memory models, memory fences are required, and the algorithm is not used in practice.
Question 5
Which hardware instruction is commonly used to implement a spinlock, and what does it do?
Show answer
The second choice.
TEST-AND-SET (or its equivalent, XCHG, LDREX/STREX, CMPXCHG) atomically reads the current value of a memory location and writes a new value (typically 1). The read and write cannot be interleaved with another core's access. A spinlock uses it like this: loop calling test-and-set; when it returns 0 (the lock was free), the caller has acquired the lock. Release is a simple store of 0. These instructions are the primitive on which mutexes, semaphores, and higher-level primitives are built.
Question 6
What is the difference between a spinlock and a mutex, and when would you prefer each?
Show answer
A spinlock makes the waiting thread busy-wait: it repeatedly tests the lock, consuming CPU cycles. A mutex blocks the waiting thread: the kernel deschedules it and wakes it when the lock is released. Spinlocks are appropriate only when the expected wait is shorter than the cost of two context switches (a few hundred nanoseconds) — typically for very short critical sections inside kernel code, or where sleeping is not allowed (for example, in an interrupt handler). Mutexes are preferred in user space and for any critical section that may be long or may involve blocking operations. Under contention, a spinlock wastes CPU and can even delay the lock holder (on a single core); a mutex lets other work proceed.
Question 7
What are the two atomic operations on a semaphore, and what does each do?
Show answer
The two operations are wait (also called P, from the Dutch proberen, "to test", or
sem_wait in POSIX) and signal (also called V, from verhogen, "to increment", or sem_post). Wait decrements the semaphore's value; if the value would become negative, the calling thread blocks until it can complete the decrement. Signal increments the value; if there are blocked waiters, one is woken. Both operations are atomic — the kernel or hardware guarantees that no other thread can observe an intermediate state.
Question 8
What is the difference between a binary semaphore and a counting semaphore?
Show answer
A binary semaphore takes only the values 0 and 1. It is used as a lock — equivalent to a mutex, though without ownership (any thread can signal it, whereas only the lock holder can unlock a mutex). A counting semaphore can take any non-negative integer value. It is used to count resources — for example, empty slots in a buffer, full slots, available connections in a pool. The initial value sets how many resources are available. The operations are the same; the difference is only in the range of values the semaphore may hold.
Question 9
In the producer-consumer problem with a bounded buffer of size B, what should the initial values of the three semaphores be?
Show answer
The second choice. At startup, the buffer is empty, so there are B empty slots (
empty = B) and zero filled slots (full = 0). The mutex is a binary semaphore protecting the buffer indices, so it starts at 1 (unlocked). Producers wait on empty before inserting and signal full after; consumers wait on full before removing and signal empty after. The critical section for the buffer modification is protected by mutex.
Question 10
What is a monitor, and what problem does it solve that semaphores leave to the programmer?
Show answer
A monitor is a programming-language construct that packages shared data with the operations that act on it, guaranteeing that at most one thread can be active inside the monitor at a time. It is defined in languages like Java (synchronized methods), Mesa, and C# (the
lock statement). The monitor solves the problem that with raw semaphores, the burden of correct placement — where to call wait and signal, in what order, with what initial values — is entirely on the programmer, and mistakes produce deadlocks or races that are hard to debug. The monitor's mutual exclusion is automatic: entering any monitor method implicitly acquires the monitor lock, and leaving it releases it. Condition variables inside the monitor provide waiting and signalling, again with the lock handled by the monitor.
Question 11
What is the difference between signal and broadcast on a condition variable, and when should each be used?
Show answer
signal wakes one waiting thread; broadcast wakes all of them. Use signal when the state change satisfies at most one waiter's predicate — for example, a producer inserts one item, so at most one consumer can now proceed. Use broadcast when the state change might satisfy several waiters, or when the predicate is complex and you cannot be sure which waiter is the right one. For example, when a reader-writer lock is released, whether a reader or a writer can proceed depends on the policy; broadcast is safe because each woken thread re-checks its own predicate. The cost of broadcast is a thundering-herd effect: many threads wake, contend for the lock, and all but one find the predicate still false and go back to sleep. Signal is more efficient when its correctness condition holds.
Question 12
Why must pthread_cond_wait be called inside a while loop rather than an if?
Show answer
Two reasons. First, POSIX permits spurious wakeups: the wait may return without any thread having signalled. If the code used
if, a spurious wakeup would lead the thread to proceed as if the predicate were true. Second, even a legitimate signal may not select the right thread: if multiple threads wait and a signal is delivered to an arbitrary one, the woken thread may find that another thread has already consumed the condition (a "stolen wakeup"). The while loop re-checks the predicate after every wakeup, so the thread only proceeds when the predicate is genuinely true. The general rule: the condition variable must always be used with a predicate, and the predicate must be re-checked after the wait.
Question 13
In the semaphore-based producer-consumer, why must the mutex-protected insert/remove happen between the semaphore operations, not before or after them?
Show answer
The semaphores
empty and full control how many slots are free and how many are filled. The mutex protects the buffer indices and the slot array. If the producer acquires the mutex first and then blocks on empty (because the buffer is full), the consumer cannot proceed: it needs the mutex to remove an item, but the producer holds it while waiting for the consumer to remove an item. Deadlock. If the operations are inverted (post the "filled" semaphore before inserting the item), a consumer may wake and remove a slot that has not yet been written — reading garbage. The rule is: wait on the "resource available" semaphore before entering the critical section, and post the "resource produced" semaphore after leaving it.
Question 14
Explain the difference between the readers-writers problem with reader preference and with writer preference. Which can starve, and why?
Show answer
Reader preference: a reader may enter as long as no writer is currently writing; readers do not exclude each other, so a stream of arriving readers can keep a writer waiting indefinitely — the writer starves. Writer preference: once a writer is waiting, new readers are blocked until the writer has completed. A stream of arriving writers can then keep readers waiting — the readers starve. Neither policy is fair; the fair policy (sometimes called "no starvation" or "FIFO") queues all requests in order and grants them in arrival sequence, at some cost in throughput. The Linux
rwlock is reader-preferring by default; the rwsem is writer-preferring.
Question 15
What is the difference between a futex and a traditional mutex in Linux?
Show answer
A futex (fast userspace mutex) is a kernel-supported primitive that combines a user-space atomic integer with a kernel wait queue. In the common uncontended case, the lock and unlock are performed entirely in user space by atomic instructions on the integer — no system call, no kernel involvement. Only when a thread must actually block (because the lock is held) does it make the
futex system call to put itself on the kernel's wait queue. This is dramatically faster than a traditional mutex, whose lock and unlock always involve a system call. POSIX mutexes on Linux are implemented on top of futexes, so the distinction is mostly one of implementation: the programmer sees pthread_mutex_lock, and the cost in the uncontended case is a single atomic operation.
Question 16
What is a "thundering herd", and how does it arise with condition variables?
Show answer
A thundering herd occurs when many threads are woken at once and all contend for a resource, but only one (or a few) can actually proceed. With condition variables, it arises when
broadcast is used: every waiting thread wakes, fights for the mutex, re-checks the predicate, and all but one find it still false and go back to sleep. The result is wasted CPU and increased latency. It is avoided by using signal where only one waiter can be satisfied, by partitioning waiters across multiple condition variables (so that a signal targets only those whose predicate could have changed), or by adopting a design where the predicate is satisfied for exactly as many waiters as are woken.
Question 17
In the dining philosophers problem, why does the naive solution (everyone picks up the left fork first) deadlock?
Show answer
In the naive solution each philosopher first acquires the fork on his left and then the fork on his right. Suppose all five philosophers simultaneously pick up their left forks. Each now holds one fork and is waiting for the other, which is held by a neighbour. No philosopher can proceed, and none will release the fork already held (they wait forever). The four necessary conditions for deadlock — mutual exclusion, hold and wait, no preemption, circular wait — are all satisfied. The fix is to break any one of them: for example, allow at most four philosophers to sit at the table at once (breaks the circular wait), or make odd-numbered philosophers pick up the right fork first (breaks the symmetry).
Question 18
Which of the following is a correct use of a condition variable?
Show answer
The second choice. Correct use requires (a) holding the mutex while checking and waiting, (b) checking the predicate in a
while loop (spurious wakeups and stolen wakeups), (c) calling pthread_cond_wait, which atomically releases the mutex and blocks, and (d) re-checking the predicate on every wakeup. The first choice is missing the loop; the third calls wait without the mutex (undefined behaviour); the fourth uses if instead of while. Signal and broadcast also require holding the mutex, though the reason is subtle — it guarantees that the signaller's predicate change is visible atomically to the waiter.
Question 19
What is the difference between voluntary and involuntary context switching, and how does this relate to synchronization?
Show answer
A voluntary context switch happens when a thread blocks — for example, on
pthread_mutex_lock when the lock is held, on pthread_cond_wait, on sem_wait, or on I/O. The thread chose to give up the CPU. An involuntary context switch happens when the scheduler preempts a running thread — for example, on a timer tick or when a higher-priority thread becomes ready. Synchronization primitives cause voluntary switches when a thread must wait, so an application that blocks frequently on locks or condition variables will show a high voluntary-switch count. A high involuntary count in a synchronised program usually means CPU contention, not lock contention. Tools like perf and /proc/<pid>/status expose both counts, which makes it possible to distinguish the two problems.
Question 20
What is the difference between a deadlock, a livelock, and starvation?
Show answer
A deadlock is a state in which two or more threads are each waiting for a resource held by another, and none can proceed. The threads are blocked; no work is done. A livelock is a state in which threads are not blocked but continually change state in response to each other without making progress — they are active but useless. (A classic example is two people stepping aside for each other in a corridor in perfect synchrony.) Starvation is a state in which one thread is indefinitely prevented from proceeding because others are always favoured. It is not blocked by a deadlock but by the scheduling or resource-allocation policy. All three are failures of liveness; they require different detection and mitigation strategies.
Question 21
In Linux, what is RCU (Read-Copy-Update), and for what workload is it best suited?
Show answer
RCU is a synchronization mechanism optimized for read-mostly data structures. Readers access the shared structure without any locking or atomic instruction on the fast path (they only need a memory barrier or, on some architectures, nothing at all). Writers create a new version of the modified element, atomically publish it (so new readers see the new version), and then wait for all pre-existing readers to finish before reclaiming the old version. The wait is tracked through quiescent states that each CPU reports. RCU is ideal for read-heavy workloads such as routing tables, file-descriptor tables, and security policy caches: reads are nearly free, writes are more expensive but infrequent. The main complexity is that write-side code must handle the deferred reclamation correctly.
Question 22
Why does the naive spinlock (busy-waiting on test-and-set) scale poorly on a multicore system with many cores contending for the lock?
Show answer
Every waiting core repeatedly executes an atomic instruction on the same cache line that holds the lock. Atomic instructions invalidate that cache line in all other cores' caches, so every test by every waiting core forces the lock holder's cache line to be re-fetched. The result is a storm of cache-coherence traffic that slows the critical section itself and can saturate the interconnect. This is why real systems use back-off strategies (pause between tests), queued locks (where each waiter spins on a distinct cache line and the lock is handed off in order), or futex-style blocking (where waiters sleep in the kernel rather than spin). A ticket lock or MCS lock restores scalability by making each waiter wait on its own cache line.
Question 23
What is the difference between a mutex and a semaphore from a correctness standpoint? Which is more error-prone, and why?
Show answer
A mutex has ownership: only the thread that locked it can unlock it. A semaphore has no ownership: any thread can signal it, regardless of which thread waited on it. This makes mutexes safer for the mutual-exclusion pattern (a thread cannot accidentally unlock a mutex it does not hold), but it makes mutexes unsuitable for the producer-consumer pattern where the producer signals and the consumer waits (or vice versa) and ownership is not meaningful. Semaphores are more error-prone because the programmer must ensure the wait and post calls are paired and in the right order, and the initial value is correct. A misplaced post can wake the wrong thread, inflate the count, or produce a state that violates a program invariant. Mutexes are more forgiving in the specific case of mutual exclusion; semaphores are more flexible but demand more discipline.
Question 24
What is the "lost wakeup" problem, and how does condition variable design prevent it?
Show answer
A lost wakeup occurs when a thread signals a condition variable but no thread is currently waiting, so the signal is discarded and a thread that later waits will wait forever. With condition variables, the problem is prevented by requiring the waiter to hold the mutex while checking the predicate and while calling
pthread_cond_wait, and requiring the signaller to hold the mutex while changing the predicate and while calling pthread_cond_signal. This mutual exclusion ensures that either the signaller runs first and changes the predicate before the waiter checks it (so the waiter sees the new predicate and does not wait), or the waiter runs first and is already waiting when the signaller signals (so the signal is not lost). Semaphores avoid the same problem by counting: a sem_post with no waiter simply increments the count, so the corresponding sem_wait will not block.
Question 25
In one or two sentences, state the central design principle that distinguishes a well-synchronised concurrent program from a poorly synchronised one.
Show answer
A well-synchronised program protects every access to shared mutable state with a lock (or another mechanism), uses the minimum holding time for each lock (so that contention and the chance of deadlock are minimised), and establishes a clear order among locks when more than one is held at a time. A poorly synchronised program leaves some accesses unprotected, holds locks across blocking operations, or acquires multiple locks in inconsistent orders — each of which produces races, deadlocks, or performance collapses that are notoriously difficult to reproduce and diagnose.
Ready for the graded quiz?
Once you are comfortable with every question above, take the graded Unit 6 quiz in the LMS. It covers the same material with multiple-choice questions, short-answer questions about synchronization design, and a worked interleaving problem.