IPC, semaphores and bounded buffers
Goals and assumptions
Choose between message passing and shared memory, distinguish communication from synchronization, and trace semaphore-based ordering and bounded buffers. Prerequisite: the published races/critical-sections lesson. Pseudocode uses sequential consistency and atomic semaphore operations. Threads preserve program order; operations eventually complete when enabled under a fair scheduler. This is a reasoning model, not a promise about unsynchronized C/C++ code or all real semaphore implementations.
1. Two ways to exchange information
Think of two cooks coordinating. Passing a written order is like message passing: a send and receive transfer information through a channel. Writing on a common board is like shared memory: both cooks access a shared region. The board does not prevent one cook from reading a half-finished update. Likewise, shared memory provides a way to communicate but does not automatically prevent races.
Message passing also needs a contract. Does send block until a receiver is ready, or merely enqueue the message? Is the queue bounded? Are message boundaries preserved? A byte-stream pipe and a message queue need not have identical semantics. A blocking receive on an empty channel waits for data, not for CPU service alone. Do not infer a total order across independent senders without an ordering guarantee.
A concrete pipe model here is a finite FIFO byte stream with one reader and one writer. Bytes are read in stream order; a read can return fewer bytes than requested. End-of-file is observed after all write endpoints are closed and buffered data has been drained. An empty pipe with an open writer is not already EOF. A full pipe may block a blocking writer. These conditions explain why closing unused endpoints matters; the model is not a complete API manual.
2. A semaphore counts permission
Use a nonnegative-token abstraction. wait(S), also called P/down, atomically consumes one token if available; otherwise the caller blocks until it can acquire one. signal(S), also called V/up/post, adds or hands over a token and may enable a waiter. The pseudocode must not split testing and decrementing into unprotected operations. Implementations sometimes expose negative counters for waiters; do not mix that representation with this nonnegative model.
A semaphore initialized to 1 can control one-at-a-time access when used correctly. A counting semaphore initialized to k represents k permits. A mutex usually has ownership rules: the thread that locks it must unlock it. A semaphore can be signaled by another thread, which makes it useful for event ordering. Neither a semaphore nor a lock alone guarantees FIFO admission or freedom from starvation without further assumptions.
Worked permit trace: S starts at 2. A and B each complete wait(S), leaving 0 free tokens. C attempts wait(S) and blocks. When A signals once, C may acquire the released permit and continue; at most two unreturned permits are held. C does not create a third permit merely by waiting.
3. Enforcing A before B
Initialize done=0. Producer executes A; signal(done). Consumer executes wait(done); B. B cannot pass its wait until a token exists, and the producer supplies that token only after A. If the signal happens before the wait, the token persists, so the consumer can consume it later. That persistence differs from a bare condition-variable notification, which is not a stored semaphore token.
Initializing done=1 would allow B before A. Reversing A and signal(done) would also break the intended ordering. A scheduler delay is not synchronization: a guessed sleep duration cannot prove that A finished.
4. Bounded buffer: count slots and protect structure
For capacity N>0, initialize empty=N, full=0, mutex=1. The queue starts empty. Each producer performs:
wait(empty); wait(mutex); insert one item; signal(mutex); signal(full).
Each consumer performs:
wait(full); wait(mutex); remove one item; signal(mutex); signal(empty).
empty reserves capacity; full reserves available items; mutex protects queue indices and storage updates. They have different jobs. Waiting for capacity or an item happens before acquiring mutex, so a blocked participant does not hold the queue lock while preventing its counterpart from making progress.
Worked boundary trace, capacity 2: after two complete productions and no consumption, the queue holds 2 items, empty=0, full=2. A third producer blocks on empty before locking mutex. A consumer acquires full, locks the queue, removes one item, unlocks and signals empty. The third producer can now acquire capacity. At a quiescent boundary (no partially completed operations), empty+full=N. During a partial operation, reservations may make this sum smaller: after wait(empty) but before signal(full), a slot is reserved but not yet advertised as a full item. Do not demand the boundary equation at every instruction.
5. A wrong order with a concrete deadlock
Suppose capacity 1 is full. A broken producer first acquires mutex, then waits on empty=0 while holding mutex. A consumer can reserve the available item with wait(full), but blocks on mutex and cannot remove the item or signal empty. Each side waits for progress the other cannot make. This is why mechanically placing a mutex around every wait is unsafe.
Exam checklist
State initial values, atomic operations, blocking rules and queue capacity. Trace permits separately from physical items. Look for a possible blocked state before claiming correctness. Do not equate shared memory with race freedom, an empty channel with EOF, a binary semaphore with ownership-enforcing mutex semantics, or a signaling action with immediate CPU dispatch.
Original practice: six single-correct MCQs
Choose exactly one option. Each question states its own required assumptions.
IP01. Two processes map a common writable memory region. Which extra property follows merely from the mapping?
A. All compound updates become atomic B. Both can access the shared region C. Deadlock becomes impossible D. Reads always wait for completed records
Answer: B
A: Mapping does not make compound updates atomic.
B: Shared accessibility is the communication mechanism; coordination still needs a protocol.
C: Synchronization choices can still deadlock.
D: Record completeness requires an explicit protocol.
IP02. In the nonnegative-token semaphore model, S=2. A and B each complete wait(S), with no signal. C then attempts wait(S). What happens?
A. C acquires a third permit B. C blocks until a permit becomes available C. C resets S to 2 D. B is forcibly terminated
Answer: B
A: Only two permits existed.
B: A and B consumed both tokens; C must wait for a release.
C: wait does not reset initial capacity.
D: Semaphore acquisition does not terminate another holder.
IP03. Producer executes A; signal(S). Consumer executes wait(S); B. Only producer signals once. What initial S guarantees A occurs before B in the token model?
A. 0 B. 1 C. 2 D. Any nonnegative value
Answer: A
A: No initial token exists, so B waits for the post-A signal.
B: An initial token lets B proceed before A.
C: Two initial tokens also permit premature B.
D: The initial count changes the ordering guarantee.
IP04. An empty buffer of capacity 4 uses the standard empty/full/mutex semaphore protocol. What are initial values in that order?
A. 0,4,1 B. 4,0,1 C. 4,4,0 D. 1,0,4
Answer: B
A: This describes a full buffer, not an empty one.
B: There are four free slots, no items and one mutex permit.
C: It advertises nonexistent items and initially blocks queue access.
D: Capacity and mutual-exclusion counts are exchanged.
IP05. A capacity-1 buffer is full. Producer acquires mutex then waits on empty=0 without releasing mutex. Consumer needs mutex before removing the item. What is possible?
A. Deadlock between producer and consumer B. Guaranteed immediate insertion C. Two simultaneous removals D. The mutex automatically becomes 2
Answer: A
A: Producer needs a free slot; consumer cannot free it while producer holds mutex.
B: No slot is available and no removal can proceed.
C: The mutex prevents the needed removal; it does not duplicate items.
D: Waiting does not manufacture mutex permits.
IP06. A finite FIFO byte-stream pipe has no buffered bytes but at least one write endpoint remains open. Under the stated blocking model, what should an ordinary read do if no new data arrives yet?
A. Return EOF solely because currently empty B. Wait for data or the closure condition C. Invent a zero byte D. Reverse the stream order
Answer: B
A: Empty with an open writer is not the EOF condition.
B: Data may still arrive; EOF requires drained data and all writers closed.
C: The pipe does not synthesize content.
D: FIFO order is not reversed by waiting.
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