Process synchronization MCQs from the KnowledgeGate question bank
Synchronization is the topic where a small misreading of a code fragment costs the whole mark. The examiners keep circling the same ideas: what a critical section really is, when a race condition arises, why Peterson's algorithm needs both a flag and a turn variable, and how semaphores enforce mutual exclusion, ordering and mutual signalling. Below are 12 solved MCQs from KnowledgeGate's published question bank, all GATE previous-year questions with the year noted. Read each fragment carefully before you answer; the explanation after each is short on purpose. Every question links to its exact solved page in the process synchronization module.
Critical section and race conditions
Q1. A critical region is *(GATE 1987, see the solved page)*
(a) one which is enclosed by a pair of P and V operations on semaphores
(b) a program segment that has not been proved bug-free
(c) a program segment that often causes unexpected system crashes
(d) a program segment where shared resources are accessed
Answer: (d).
A critical region is defined by what it does, access shared resources, not by the mechanism that protects it. P and V operations guard the region, but wrapping code in them is not the definition; the region exists the moment shared state is touched.
Q2. When the result of a computation depends on the order of process execution, there is said to be *(GATE 1998, see the solved page)*
(a) cycle stealing
(b) race condition
(c) a time lock
(d) a deadlock
Answer: (b) race condition.
A race condition is exactly this order-dependence: the final value hinges on which process reaches its critical section first. That non-determinism is why unsynchronised access to shared data is unsafe, and why mutual exclusion exists.
Q3. Threads T1 and T2 update shared variables a and b, both initially 1. T1 runs a = a + 1; b = b + 1; and T2 runs b = 2 * b; a = 2 * a;. Each statement is atomic. Which option lists all possible (a, b) combinations after both finish? *(GATE 2024, see the solved page)*
(a) (4, 4); (3, 3); (4, 3)
(b) (3, 4); (4, 3); (3, 3)
(c) (4, 4); (4, 3); (3, 4)
(d) (2, 2); (2, 3); (3, 4)
Answer: (a).
Each variable's final value depends only on the order of its own two operations. For a, "add then double" gives (1+1)×2 = 4 and "double then add" gives (1×2)+1 = 3; b behaves identically. The reachable pairs are (4,4), (3,3) and (4,3); the combination (3,4) cannot occur because of how the two threads' statements interleave.
Two-process solutions: Peterson and strict alternation
Q4. In Peterson's algorithm, process i sets flag[i] = true; turn = j; and then busy-waits while (P). For mutual exclusion, the predicate P should be *(GATE 2001, see the solved page)*
(a) flag[j] == true and turn == i
(b) flag[j] == true and turn == j
(c) flag[i] == true and turn == j
(d) flag[i] == true and turn == i
Answer: (b) flag[j] == true and turn == j.
Process i must wait only while the other process also wants in and it is the other's turn. It keeps looping while both hold, and enters the moment j loses interest or cedes the turn. Referring to flag[i] would make a process wait on its own state, which is meaningless.
Q5. Two processes use while (turn == 1); and while (turn == 0); at entry, setting turn to the other value at exit, with turn initialised to 0. This solution *(GATE 2016, see the solved page)*
(a) is a correct two-process synchronization solution
(b) violates the mutual exclusion requirement
(c) violates the progress requirement
(d) violates the bounded wait requirement
Answer: (c) violates progress.
This is strict alternation. Mutual exclusion holds because only the process whose turn it is can enter. But if it is process 0's turn and process 0 does not want to enter, process 1 is blocked even though the critical section is free, which is exactly a progress violation.
Q6. Two processes use shared flags wants1 and wants2, each set to true before entry and to false after, with while (wantsOther == true); as the wait. Which statement is TRUE? *(GATE 2007, see the solved page)*
(a) It does not ensure mutual exclusion
(b) It does not ensure bounded waiting
(c) It requires strict alternation of entry
(d) It does not prevent deadlocks, but ensures mutual exclusion
Answer: (d).
Because each process checks the other's flag, mutual exclusion holds. But with no turn variable, both can set their flag to true at once and then wait forever for the other to clear it, which is a deadlock. This is the classic reason Peterson added the turn variable.
Q7. Processes P1 and P2 use shared booleans S1 and S2. P1 waits while (S1 == S2); then sets S1 = S2; after its critical section. P2 waits while (S1 != S2); then sets S2 = not(S1);. Which properties hold? *(GATE 2010, see the solved page)*
(a) Mutual exclusion but not progress
(b) Progress but not mutual exclusion
(c) Neither mutual exclusion nor progress
(d) Both mutual exclusion and progress
Answer: (a) mutual exclusion but not progress.
P1 enters only when S1 and S2 differ and P2 only when they are equal, so the two entry conditions are mutually exclusive and both can never be inside together. But the flags force an alternation, so a process that does not want to enter can still block the other, breaking progress.
Semaphores and ordering
Q8. In a producer-consumer solution, P1 adds an item and P2 removes one, using a mutex plus counting semaphores empty and full. The statements K, L (in P1, around the add) and M, N (in P2, around the remove) are respectively *(GATE 2004, see the solved page)*
(a) P(full), V(empty), P(full), V(empty)
(b) P(full), V(empty), P(empty), V(full)
(c) P(empty), V(full), P(empty), V(full)
(d) P(empty), V(full), P(full), V(empty)
Answer: (d) P(empty), V(full), P(full), V(empty).
The producer must wait for an empty slot before adding, P(empty), and signal a filled slot after, V(full). The consumer mirrors this: wait for a full slot, P(full), and signal a freed slot, V(empty). Swapping any pair either overflows the buffer or lets the consumer read from an empty one.
Q9. Processes P1 to P9 each run P(mutex); critical section; V(mutex);. P10 is identical but uses V(mutex) in place of the leading P(mutex). With mutex initialised to 1, what is the largest number of processes that can be inside the critical section at once? *(GATE 1997, see the solved page)*
(a) 1
(b) 2
(c) 3
(d) None of the above
Answer: (d) None of the above.
P10 signals V(mutex) before entering, which increments the semaphore instead of decrementing it. Because P10 loops forever, it can keep raising the count, so mutual exclusion collapses entirely and any number of processes can be inside at once. The answer is therefore "none of the above", not a fixed small number.
Q10. Two processes share a semaphore X initialised to 0. P1 repeats V(X); Compute; P(X); and P2 repeats P(X); Compute; V(X);. Consider: (I) P1 can starve, (II) P2 can starve. Which holds? *(GATE 2005, see the solved page)*
(a) Both I and II are true
(b) I is true but II is false
(c) II is true but I is false
(d) Both I and II are false
Answer: (a) Both I and II are true.
If the scheduler always favours P1, it can loop V then P repeatedly and P2 never runs its P(X), so P2 starves. Symmetrically, once P1 has done its first V, a scheduler that always favours P2 keeps P1 out of its next V, so P1 starves too. Neither process has any guarantee of progress.
Q11. A barrier for three processes increments process_arrived under a semaphore, then spins while (process_arrived != 3); before resetting counters. It has a race across barrier cycles. Which change fixes it? *(GATE 2006, see the solved page)*
(a) Replace the reset lines with a single decrement of process_arrived
(b) The first process to enter waits until process_arrived is zero before proceeding to P(S)
(c) Disable context switches for the whole barrier
(d) Make process_left private instead of shared
Answer: (b).
The bug is that a fast process can re-enter the barrier and start incrementing process_arrived before the previous cycle has reset it. Forcing the first arrival to wait until process_arrived is zero guarantees the counters are clean before a new cycle begins, closing the overlap.
Q12. Process X computes a[i] = f(i) and process Y computes b[i] = g(a[i]) for each i, using binary semaphores R and S initialised to 0. X ends each iteration with ExitX(R, S) and Y begins each with EntryY(R, S). Which pair is correct? *(GATE 2013, see the solved page)*
(a) ExitX: P(R); V(S); EntryY: P(S); V(R);
(b) ExitX: V(R); V(S); EntryY: P(R); P(S);
(c) ExitX: P(S); V(R); EntryY: V(S); P(R);
(d) ExitX: V(R); P(S); EntryY: V(S); P(R);
Answer: (c).
This is a per-index rendezvous: Y must read a[i] only after X has written it. EntryY signals readiness with V(S) then waits with P(R); ExitX waits with P(S) then signals completion with V(R). The handshake pairs one V with one P on each semaphore, so the two processes stay locked in step for every i.
Where these 12 fit in your preparation
The set follows the syllabus arc: the definitions of critical section and race condition (Q1-Q3), the two-process software solutions where progress and deadlock are the traps (Q4-Q7), and the semaphore questions on producer-consumer, mutual exclusion, starvation and rendezvous (Q8-Q12). If a fragment confuses you, trace one concrete interleaving by hand; almost every wrong answer here comes from assuming an interleaving that the code actually allows or forbids.
For the theory behind every answer, work through the process synchronization learn module and its PYQ sets, and place the topic in the wider syllabus with our Operating Systems for GATE breakdown. GATE aspirants get the full OS sequence inside GATE Guidance by Sanchit Sir; NET aspirants can start from the NET CS category page. Solve, review your misses, and return to the set a week later.