Semaphores and Process Ordering MCQs: 10 Solved Questions

Semaphore questions are won by tracking one state change at a time. These 10 questions cover wait/signal arithmetic, alternation, starvation, stale reads, deadlock prevention, barriers, rendezvous and a broken mutex. Choose an option first, then write each P/V operation. Revise CS Fundamentals first if the underlying terms are unfamiliar.

Use one trace method for every semaphore question

Trace step, process, value, and status. With signed counts and S = 2: A waits, 2 -> 1; B waits, 1 -> 0; C waits, 0 -> -1 and blocks; B signals, -1 -> 0 and wakes C; A signals, 0 -> 1; C eventually signals, 1 -> 2. Follow the stem if it uses another convention.

For ordering, let S = 1, T = 0. P prints 00 and signals T; Q prints 11 and signals S. Repeating the handoff gives 00110011.... The counter-and-queue model is developed in Process Synchronization and Semaphores.

Questions 4, 9 and 10 also occur in Process Synchronization MCQs: 12 Solved GATE Questions, which surveys critical sections, two-process algorithms and semaphores. Here they isolate starvation, zero-initialized rendezvous and unmatched signals. Process Synchronization MCQs: 10 Solved Cross-Concept Questions instead spans IPC, monitors, spinlocks and lock-aware scheduling.

Semaphores MCQs 1-2: atomic operations and count arithmetic

Question 1 (UGC NET 2017)

Two atomic operations permissible on Semaphores are __________ and __________.

• (a) wait, stop

• (b) wait, hold

• (c) hold, signal

• (d) wait, signal

Correct answer: (d) wait, signal.

P/wait acquires; V/signal releases and may wake a waiter. Each update is indivisible.

Question 2 (RSSB 2022)

A counting semaphore was initialized to 8.

Then 12 P (wait) operations and 7 V (signal) operations were completed on this semaphore.

The resulting value of semaphore is :

• (a) 4

• (b) 3

• (c) 5

• (d) 1

Correct answer: (b) 3.

Apply every completed operation:

8 - 12 + 7 = -4 + 7 = 3

Semaphores MCQs 3-4: waiting queues and starvation

Question 3 (UGC NET 2017)

There are three processes P1 , P2 and P3 sharing a semaphore for synchronizing a variable. Initial value of semaphore is one. Assume that negative value of semaphore tells us how many processes are waiting in queue. Processes access the semaphore in following order :

(a) P2 needs to access

(b) P1 needs to access

(c) P3 needs to access

(d) P2 exits critical section

(e) P1 exits critical section

The final value of semaphore will be :

• (a) 0

• (b) 1

• (c) - 1

• (d) - 2

Correct answer: (a) 0.

Signed trace: P2 1 -> 0; waiting P1 0 -> -1; waiting P3 -1 -> -2; P2 exits -2 -> -1 and wakes P1; P1 exits -1 -> 0 and wakes P3.

Question 4 (GATE 2005)

Given below is a program which when executed spawns two concurrent processes :

semaphore X : = 0 ; /* Process now forks into concurrent processes P1 & P2 */

P1 : repeat forever P2 : repeat forever

V (X) ; P(X) ;

Compute ; Compute ;

P(X) ; V(X) ;

Consider the following statements about processes P1 and P2:

1. It is possible for process P1 to starve.

2. It is possible for process P2 to starve.

Which of the following holds?

• (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

Correct answer: (a) Both I and II are true.

There is no fairness guarantee. After a V(X), P2 may repeatedly win the next P(X), starving P1; alternatively, P1 may repeatedly regain X before P2 runs, starving P2.

Semaphores MCQs 5-6: forced output and stale reads

Question 5 (GATE 2003)

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P:
while (1) {
W:
   print '0';
   print '0';
X:
}
	
Process Q:
while (1) {
Y:
   print '1';
   print '1';
Z:
}

Synchronization statements can be inserted only at points W, X, Y and Z.

Which of the following will always lead to an output starting with '001100110011' ?

• (a) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1

• (b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0

• (c) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1

• (d) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0

Correct answer: (b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0.

Trace: S = 1 lets P print 00; V(T) makes T: 0 -> 1; Q prints 11; V(S) makes S: 0 -> 1; repeat. A/D lack cross-signals; C lets both start.

Question 6 (GATE/BARC 2013)

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?

• (a) -2

• (b) -1

• (c) 1

• (d) 2

Correct answer: (d) 2.

Maximum trace: X reads 0, saves 1; Y reads 0, writes -2; Z reads -2, writes -4; X writes stale 1; W reads 1, writes 2. Two permits allow this overlap.

Semaphores MCQs 7-8: deadlock-free acquisition and a barrier

Question 7 (GATE/BARC 2013)

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

• (a) X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)

• (b) X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

• (c) X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)

• (d) X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

Correct answer: (b) X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d).

B obeys b < a < c < d: X takes b,a,c; Y b,c,d; Z a,c,d, preventing circular wait. A conflicts on a,c; C and D conflict on b,c.

Question 8 (GATE 2020)

Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

CODE SECTION P

wait(a); count=count+1;

if (count==n) signal (b);

signal (a); wait (b) ; signal (b);

CODE SECTION Q

What does the code achieve ?

• (a) It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.

• (b) It ensures that two processes are in CODE SECTION Q at any time.

• (c) It ensures that all processes execute CODE SECTION P mutually exclusively.

• (d) It ensures that at most n-1 processes are in CODE SECTION P at any time.

Correct answer: (a) It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.

a protects count. The first n-1 processes block at wait(b); process n signals b. Each released process signals b for the next, so Q starts only after all finish P.

Semaphores MCQs 9-10: per-item handoff and a broken mutex

Question 9 (GATE/BARC 2013)

A certain computation generates two arrays a and b such that a[i]=f(i) for 0 <= i < n and b[i] = g(a[i]) for 0 <= i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.

Process X:

private i;

for (i=0; i< n; i++) {

a[i] = f(i);

ExitX(R, S);

}

Process Y:

private i;

for (i=0; i< n; i++) {

EntryY(R, S);

b[i] = g(a[i]);

}

Which one of the following represents the CORRECT implementations of ExitX and EntryY ?

• (a)

ExitX(R, S) {
 P(R);
 V(S);
}

EntryY(R, S) {
 P(S);
 V(R);
}

• (b)

ExitX(R, S) {
 V(R);
 V(S);
}

EntryY(R, S) {
 P(R);
 P(S);
}

• (c)

ExitX(R, S) {
 P(S);
 V(R);
}

EntryY(R, S) {
 V(S);
 P(R);
}

• (d)

ExitX(R, S) {
 V(R);
 P(S);
}

EntryY(R, S) {
 V(S);
 P(R);
}

Correct answer: (c) ExitX is P(S); V(R); and EntryY is V(S); P(R);.

Per index, Y signals readiness on S; after writing a[i], X waits on S and signals R; Y waits on R before reading a[i]. Thus both zero-initialized semaphores rendezvous.

Question 10 (GATE 1997)

Each Process Pi, i = 1......9 is coded as follows

repeat
    P(mutex)
    {Critical section}
    V(mutex)
forever

The code for P10 is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

• (a) 1

• (b) 2

• (c) 3

• (d) None of above

Correct answer: (d) None of above.

Repeated unmatched V operations by P10 accumulate permits. Then P1-P9 can each pass P(mutex) and pause inside while P10 also enters: maximum 10, absent from A-C.

Semaphores: final trace check

Record the initial count, each wait and signal, the blocked queue, ownership and any fairness assumption before choosing. Continue with Computer Science Fundamentals for Placements by Sanchit Sir for wider core-CS revision.