GATE does not ask you to recite the producer-consumer solution. It gives you the code, runs an interleaving through it, and asks for a semaphore's final value, how many processes are blocked, or which swapped line causes deadlock. That is a trace-table skill, and most aspirants never practise it as one. Here we trace each classic synchronisation problem line by line, with the exact traps multiple-select questions are built on.
Counting semaphores: the two rules every trace table uses
A counting semaphore S is an integer manipulated by two atomic operations. In the standard textbook definition, the one GATE pseudocode almost always follows:
wait(S) (also written P(S) or down(S)): decrement S by 1. If S becomes negative, the calling process blocks and joins S's queue.
signal(S) (also written V(S) or up(S)): increment S by 1. If S is still zero or negative after the increment, wake one blocked process.
Two consequences do all the work:
The invariant. At any instant, S = initial value + (signals completed) − (waits executed). Nothing else ever changes it.
The reading of a negative value. When S is negative, its magnitude is exactly the number of processes blocked on S. When S is positive, it counts how many waits can still succeed without blocking.
Some books use a convention where wait blocks while S is 0 and the value never goes negative. The pseudocode printed in the question decides; when only "counting semaphore" is stated, the decrement-then-block definition above is standard, and everything below uses it.
Producer-consumer: the bounded-buffer trace table
The bounded-buffer solution uses three semaphores for a buffer of size N: empty = N (free slots), full = 0 (filled slots), mutex = 1 (guards the buffer). The producer runs wait(empty), wait(mutex), insert, signal(mutex), signal(full); the consumer runs wait(full), wait(mutex), remove, signal(mutex), signal(empty). Order matters, which is what the trap below exploits.
Take N = 3, with consumer C1 arriving before anything is produced, then producer P1 producing one item.
Step | Operation | empty | full | mutex | What happened |
|---|---|---|---|---|---|
start | initial values | 3 | 0 | 1 | buffer empty |
1 | C1: wait(full) | 3 | -1 | 1 | C1 blocks, no item exists |
2 | P1: wait(empty) | 2 | -1 | 1 | a free slot is claimed |
3 | P1: wait(mutex) | 2 | -1 | 0 | P1 enters the buffer |
4 | P1: signal(mutex) | 2 | -1 | 1 | item placed, buffer released |
5 | P1: signal(full) | 2 | 0 | 1 | full rises to 0, C1 wakes |
6 | C1: wait(mutex) | 2 | 0 | 0 | C1 enters the buffer |
7 | C1: signal(mutex) | 2 | 0 | 1 | item removed |
8 | C1: signal(empty) | 3 | 0 | 1 | back to the start state |
Read step 1 again, because it is the trap. After it, full is −1, not 0: a blocked consumer drives the semaphore negative, and the magnitude counts the waiters. In general, with p producers and c consumers, full ranges over [−c, N] and empty over [−p, N]. Range statements like these are standard multiple-select bait.
The swapped-wait deadlock, traced
Now the classic single-line mutation: the producer runs wait(mutex) before wait(empty), starting from a full buffer (empty = 0, full = 3, mutex = 1).
Step | Operation | empty | full | mutex | What happened |
|---|---|---|---|---|---|
1 | P1: wait(mutex) | 0 | 3 | 0 | P1 takes the buffer lock |
2 | P1: wait(empty) | -1 | 3 | 0 | P1 blocks holding mutex |
3 | C1: wait(full) | -1 | 2 | 0 | an item exists, C1 passes |
4 | C1: wait(mutex) | -1 | 2 | -1 | C1 blocks on the held lock |
P1 waits for empty, which only C1 can signal. C1 waits for mutex, which only P1 holds. Circular wait, deadlock, and the final snapshot (empty = −1, full = 2, mutex = −1) is exactly the value set GATE asks you to produce. Note the asymmetry examiners love: swapping the two waits can deadlock; swapping the two signals only reorders wakeups and is harmless.
Readers-writers: tracing readcount and wrt together
The first-readers-preference solution uses an integer readcount = 0 and two semaphores: mutex = 1 guarding readcount, wrt = 1 guarding the data. A writer does wait(wrt), writes, signal(wrt). A reader increments readcount under mutex, and only the first reader in does wait(wrt); on exit, only the last reader out does signal(wrt). Trace two readers overlapping one writer:
Step | Operation | readcount | mutex | wrt | What happened |
|---|---|---|---|---|---|
start | initial values | 0 | 1 | 1 | idle |
1 | R1: wait(mutex); readcount=1 | 1 | 0 | 1 | first reader in |
2 | R1: wait(wrt); signal(mutex) | 1 | 1 | 0 | R1 locks writers out, reads |
3 | R2: wait(mutex); readcount=2; signal(mutex) | 2 | 1 | 0 | not first, skips wrt, reads |
4 | W1: wait(wrt) | 2 | 1 | -1 | writer blocks behind readers |
5 | R1 exits: readcount=1 | 1 | 1 | -1 | not last, wrt untouched |
6 | R2 exits: readcount=0; signal(wrt) | 0 | 1 | 0 | last reader out, W1 wakes |
7 | W1 writes; signal(wrt) | 0 | 1 | 1 | back to idle |
Three facts fall straight out of the table, and all three appear as answer options. First, wrt is touched only by the first reader in and the last reader out; a middle reader never changes it. Second, while readers hold the data and w writers wait, wrt sits at −w. Third, readcount is a plain integer, not a semaphore; it stays consistent only because mutex serialises every touch. The structural weakness is visible too: as long as new readers keep arriving, readcount never returns to 0 and the writer at step 4 starves. This variant is the writers-can-starve solution.
Dining philosophers: tracing five chopsticks into deadlock
Five philosophers, five chopsticks, each chopstick a semaphore initialised to 1. The naive protocol for philosopher i: wait(chopstick[i]), wait(chopstick[(i+1) mod 5]), eat, signal both. Run the worst case: all five get hungry at once, and each completes its first wait before any starts the second.
After round one, every chopstick reads 0: five waits succeeded, each philosopher holds a left chopstick.
In round two, each waits on the right chopstick, which a neighbour holds. Every chopstick drops to −1 and every philosopher blocks.
All four deadlock conditions hold, and the trace shows the numbers: five processes blocked, each semaphore at −1. GATE variants then ask which fix breaks the cycle:
At most four at the table. Add a semaphore room = 4, waited on before the first chopstick. If all five arrive, room runs 4, 3, 2, 1, 0, then −1: one philosopher blocks at the door and the remaining four can never close a five-way cycle.
Break the symmetry. Make one philosopher (or every even-numbered one) pick the right chopstick first, so the circular wait cannot close.
Pick both atomically. Take both chopsticks inside one critical section, so round one's hold-and-wait never forms.
How GATE tests semaphore traces
The multiple-select format is the natural home for this topic: each classic problem generates several independently checkable statements, a final semaphore value, a blocked-process count, a range claim, a deadlock or starvation claim. You clear such a question only by running the table. For scoring rules and the current paper pattern, rely on the official GATE information brochure published by the organising institute for your cycle, not a coaching summary. Use the current official GATE portal to locate the organising institute's cycle-specific brochure.
Two habits make the traces fast. First, use the invariant instead of simulating mentally: value = initial + signals − waits, then check the sign. Second, always ask which process a signal wakes, because the woken process completes its wait without decrementing again. If the topic still feels loose, the concept sequence in Operating Systems for GATE places synchronisation next to scheduling and deadlock, and the Operating System, Process Synchronization learn module carries the solved-question drill for exactly these problems.
The short version and your next step
Learn the two semaphore rules, then hand-trace each classic once: producer-consumer to a negative full, the swapped-wait deadlock to its final snapshot, readers-writers through first-in and last-out, and dining philosophers into the five-way cycle. After that, every trace question is arithmetic.
For a structured route through the whole OS paper, GATE Guidance by Sanchit Sir builds a personalised plan around your target score, and the GATE CS Exam category collects the subject resources if you only need to patch specific topics. Ten traced tables beat a hundred read pages; start with the three above.
