Synchronization: atomic primitives, Peterson and conditions
Goals and reasoning model
Explain why an atomic read-modify-write fixes a split test/set race, trace Peterson's two-thread algorithm, and use a condition variable without a lost wake-up. Prerequisites: the published critical-sections lesson and the semaphore lesson. All algorithm traces assume atomic shared reads/writes, sequential consistency, visibility of updates and eventual execution of runnable threads. Critical sections terminate. The pseudocode is not directly portable C/C++; actual languages and CPUs require appropriate atomic types, memory ordering and library primitives.
1. A single key dispenser
A broken key dispenser first checks whether a key is present and, later, removes it. Two people may both pass the check. A correctly atomic dispenser combines checking and removing into one indivisible action. Define test_and_set(L) to atomically return the old value of L and write 1 into L. Initially L=0. Acquire by repeating test_and_set(L) while its return value is 1; release by storing 0 with the required release semantics in an implementation.
Worked collision: A and B both attempt acquisition. Atomic operations have an order. If A's operation comes first, it returns 0 and leaves L=1. B's next operation returns 1 and cannot enter. Even if both operations begin nearly together, they cannot both return the same old 0 before either update. This repairs mutual exclusion, assuming everyone follows the protocol.
It does not ensure bounded waiting. After a release, a newly arriving or repeatedly successful thread can win before an older waiter. Spinning also consumes CPU while waiting; on one CPU it is especially wasteful if the lock holder is not running. Disabling interrupts only on one processor does not stop another processor from accessing the same shared data.
2. Peterson: intention plus a tie-breaker
For exactly two threads i∈{0,1}, let j=1−i. Initially flag[0]=flag[1]=false; turn can start at either value. Thread i's entry is:
flag[i]=true; turn=j; while (flag[j] and turn==j) spin.
Then it enters its critical section and on exit sets flag[i]=false. The flag announces interest; turn gives the other contender priority when both are interested. Neither variable alone carries both jobs.
Worked contention: T0 sets flag[0]=true and turn=1. T1 then sets flag[1]=true and turn=0. Both flags are true, and final turn=0. T0 tests flag[1] and turn==1: false because turn is 0, so T0 may enter. T1 tests flag[0] and turn==0: true, so it waits. After T0 clears flag[0], T1 can enter. The last turn writer yields to the other thread; “turn names the thread that must wait” is a misleading shortcut.
Under the declared model, the algorithm gives mutual exclusion, progress and bounded overtaking. Those are algorithmic properties, not a wall-clock deadline if a thread stops being scheduled. Proof intuition: with both flags true, turn cannot simultaneously equal both 0 and 1, so both wait conditions cannot be false in the way needed for both to enter while each remains interested. A full proof also respects the order of flag and turn writes. Do not remove either line or extend this exact two-thread code to arbitrary n without a different algorithm.
3. Condition variables wait for a predicate
A condition variable is like a doorbell telling you to check whether a parcel is available. The bell is not the parcel and does not store a permanent “one parcel” token. Use a shared predicate, such as ready, protected by a mutex M.
This is a single-publication notification example: initially ready=false, and the producer publishes exactly one item once. A reusable bounded buffer also needs a not-full predicate and corresponding producer wait, as in the earlier semaphore lesson; repeatedly running this producer without that check could overwrite an unconsumed item.
Consumer: lock(M); while not ready: wait(CV,M); consume the ready item; set ready=false; unlock(M).
Producer: lock(M); create the item; set ready=true; signal(CV); unlock(M).
The wait operation atomically releases M and arranges the thread's wait, then reacquires M before returning. This atomic release-and-wait avoids a gap in which the producer updates and signals after the consumer tests false but before it begins waiting. Keeping M locked during sleep would instead prevent the producer from setting the predicate.
4. Why a loop, and why persistent state?
We use Mesa-style semantics: signaling makes a waiter eligible to run; it does not instantly transfer the mutex or guarantee the predicate remains true. Another consumer may acquire M and consume the item first. Spurious wake-ups may also be permitted. Therefore a returning waiter rechecks the predicate in a while loop, not a one-time if.
Worked early-producer case: producer sets ready=true and signals before any consumer waits. The signal itself need not be remembered. Later the consumer locks M, sees ready=true and skips waiting, so work is not lost. If the producer only rings a bell and records no predicate, a later consumer might wait forever despite the earlier event. A semaphore initialized to zero can store a signal token; a bare condition notification is different.
5. Classic problems are specifications, not magic names
Producer-consumer was solved with empty/full/mutex in the earlier lesson. In readers-writers, the safety rule allows concurrent readers but requires an active writer to exclude both readers and writers. A reader-preference solution can starve writers under continuous readers; a writer-preference policy can delay readers. Fairness must be specified separately from safety. Dining philosophers illustrates circular acquisition: requiring a common strict fork order breaks the cycle, as the deadlock lesson's lock-order argument shows. Adding a mutex somewhere is not itself a proof of either correctness or fairness.
Self-check
Name the atomic step, state the memory model, separate mutual exclusion from bounded waiting, and identify the predicate protected by every condition wait. Never replace an atomic acquire with an ordinary check followed by a write, or assume that a wake-up is ownership of the resource.
Original practice: six single-correct MCQs
Choose exactly one option. Each question states its own required assumptions.
SY01. Initially L=0. Two threads perform atomic test_and_set(L), which returns old L and writes 1. No release occurs between them. What return values are possible in operation order?
A. 0,0 B. 0,1 C. 1,0 D. 1,1
Answer: B
A: Atomicity prevents both from reading old 0 before either update.
B: First sees 0 and writes 1; second sees 1.
C: The first sees the specified initial 0.
D: The first cannot see 1 with no prior writer.
SY02. A simple test-and-set spinlock correctly enforces mutual exclusion but specifies no waiter ordering. Which additional property is not guaranteed?
A. At most one holder B. Atomic acquisition attempt C. Bounded waiting for each contender D. A failed attempt may observe a held lock
Answer: C
A: This is the stated mutual-exclusion property.
B: The primitive is defined atomic.
C: A contender may repeatedly lose after releases without fairness machinery.
D: Observing 1 is the normal failed-acquisition result.
SY03. Peterson uses flag[i]=true; turn=j; while(flag[j] and turn==j) wait. Both flags are true and final turn=0 before either enters. Which thread can pass its loop?
A. Only T0 B. Only T1 C. Both D. Neither
Answer: A
A: For T0, j=1 and turn==1 is false.
B: For T1, j=0 and both parts of its wait condition are true.
C: T1 is blocked by its true condition.
D: T0 has a false wait condition.
SY04. In a correct mutex/condition-variable wait, what happens to the associated mutex while the caller waits and when wait returns?
A. Held throughout sleep, returned unlocked B. Atomically released for waiting, reacquired before return C. Destroyed, then recreated D. Released permanently without reacquisition
Answer: B
A: Holding the mutex prevents the producer from changing protected state.
B: This prevents a test-to-sleep gap and restores protected access on return.
C: A wait does not destroy the mutex.
D: The caller needs the lock again to safely recheck the predicate.
SY05. Under Mesa-style condition signaling, why should a consumer use while(not ready) wait rather than if(not ready) wait?
A. A signal guarantees permanent resource ownership B. The predicate can be false again before the waiter reacquires the mutex C. while removes the need for a mutex D. A condition variable stores unlimited tokens
Answer: B
A: Signal does not transfer lasting ownership.
B: Another consumer or a spurious wake-up can invalidate the assumption.
C: The shared predicate still needs synchronized access.
D: That is not the contract of a condition notification.
SY06. Producer sets ready=true while holding M and signals before any consumer waits. Later a consumer locks M and checks ready in a while loop. Assuming no intervening consumer, what should happen?
A. It must sleep because the old signal vanished B. It sees ready=true and need not wait C. It must reset ready before checking D. It enters without locking M
Answer: B
A: Persistent predicate state, not a remembered signal, records available work.
B: The while condition is false, so it proceeds using the stored state.
C: Resetting first would discard the availability information.
D: The specified protocol locks M before inspecting ready.
Sources and scope
This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in