GATE 2023 CS Q.38: solution and answer

GATE 2023 · CSQ.38 · 2 marks · MCQ

Consider the two functions incr and decr shown below.

incr(){
 wait(s);
 X = X+1;
 signal(s);
}

decr(){
 wait(s);
 X = X-1;
 signal(s);
}

There are 5 threads each invoking incr once, and 3 threads each invoking decr once, on the same shared variable X. The initial value of X is 10.

Suppose there are two implementations of the semaphore s, as follows:

I-1: s is a binary semaphore initialized to 1.

I-2: s is a counting semaphore initialized to 2.

Let V1, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively.

Which one of the following choices corresponds to the minimum possible values of V1, V2, respectively?

(A)
15, 7
(B)
7, 7
(C)
12, 7
(D)
12, 8

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The minimum possible values are V1 = 12 and V2 = 7, option (C).

Official answer: CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

I-1 (binary semaphore, initial 1). Only one thread can be between wait(s) and signal(s) at a time, so each update of X is atomic and no update is lost.
Every incr adds 1 and every decr subtracts 1, in any order, so $V_{1} = 10 + 5 - 3 = 12$ . It is the same in every execution, so the minimum is $12$ .
I-2 (counting semaphore, initial 2). Two threads can be inside the critical section together, so two read-modify-write sequences can overlap and an update can be overwritten (lost). A thread always writes the value it read, plus 1 (incr) or minus 1 (decr).
Lower bound. Let $d$ be the number of decr writes completed so far. Claim: $X \geq 10 - d$ at all times. Initially $X = 10$ and $d = 0$ . An incr writes $r + 1$ , where $r$ is an earlier value of $X$ , and $r \geq 10 - d_{then} \geq 10 - d_{now}$ , so the claim still holds. A decr writes $r - 1$ with $r \geq 10 - d_{before}$ , and $d$ rises by 1, so $X \geq 10 - d_{after}$ . With only 3 decrements, $d \leq 3$ , so the final value is at least $10 - 3 = 7$ .
A schedule that reaches 7. Decr thread $D_{1}$ takes one permit, reads $X = 10$ , and stalls inside the critical section.
The other permit is free for one thread at a time, so the 5 incr threads run one after another: $X = 10 \to 15$ .
$D_{1}$ resumes and writes $10 - 1 = 9$ , overwriting all five increments, so $X = 9$ .
The two remaining decr threads run one after another: $9 \to 8 \to 7$ . (If they overlapped and both read 9, the result would be 8, which is not smaller.)
So $V_{2} = 7$ is reachable and cannot be beaten, and the minimum pair is $(V_{1}, V_{2}) = (12, 7)$ , option (C).

KEY IDEA

A binary semaphore initialised to 1 gives mutual exclusion, so there are no lost updates. A counting semaphore initialised to 2 lets two threads overlap, so one thread's stale write can wipe out many increments. The value can never fall below $10 - 3 = 7$ , because only decrements lower it, and each can lower it by at most 1 from some value that was itself at least that high.

WATCH OUT FOR

Taking 7 for V1 as well, as if the binary semaphore also allowed lost updates. Another slip is thinking the counting semaphore lets the decrements stack to $10 - 3 = 7$ only without losing increments, or forgetting that a stalled decr can overwrite the increments.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 7 Synchronisation questions, with notes

GATE 2023 CS Q.38: solution and answer

Answer and solution

More Synchronisation questions