Official PYQ · 2024Set 2 · Q36Concurrency and SynchronizationMSQ2 marks

GATE CS 2024 Set 2 Q36 — Concurrency and Synchronization

Consider a multi-threaded program with two threads $\mathrm{T} 1$ and $\mathrm{T} 2$ . The threads share two semaphores: $s1$ (initialized to $1$ ) and $s2$ (initialized to $0$ ). The threads also share a global variable $\mathrm{x}$ (initialized to $0$ ). The threads execute the code shown below.

//code of T 1
wait (s1);
x = x+1;
print (x);
wait (s2);
signal(s1);

// code of T2
wait (s1);
x= x+1;
print (x) ;
signal (s2);
signal (s1);

Which of the following outcomes is/are possible when threads $\mathrm{T} 1$ and $\mathrm{T} 2$ execute concurrently?

View worked solution

Answer: B;C

To find the possible outcomes, let us trace the execution of threads $\text{T1}$ and $\text{T2}$ under different scheduling scenarios.

Initial State:
$s1 = 1$ , $s2 = 0$ , and $x = 0$ .

Scenario 1: Thread $\text{T1}$ starts first

$\text{T1}$ executes wait(s1): Since $s1 = 1$ , it decrements to $0$ , and $\text{T1}$ proceeds.
$\text{T1}$ executes x = x + 1: $x$ becomes $1$ .
$\text{T1}$ executes print(x): Prints $1$ .
$\text{T1}$ executes wait(s2): Since $s2 = 0$ , $\text{T1}$ blocks and goes to the waiting queue of $s2$ .
Now, $\text{T2}$ attempts to run and executes wait(s1): Since $s1 = 0$ , $\text{T2}$ blocks and goes to the waiting queue of $s1$ .

At this point, $\text{T1}$ is blocked waiting for $s2$ (which only $\text{T2}$ can signal), and $\text{T2}$ is blocked waiting for $s1$ (which only $\text{T1}$ can signal). This is a deadlock.

Outcome: $\text{T1}$ prints $1$ , and $\text{T2}$ does not print anything due to deadlock. (Matches Option C)

Scenario 2: Thread $\text{T2}$ starts first

$\text{T2}$ executes wait(s1): Since $s1 = 1$ , it decrements to $0$ , and $\text{T2}$ proceeds.
$\text{T2}$ executes x = x + 1: $x$ becomes $1$ .
$\text{T2}$ executes print(x): Prints $1$ .
$\text{T2}$ executes signal(s2): $s2$ becomes $1$ .
$\text{T2}$ executes signal(s1): $s1$ becomes $1$ . $\text{T2}$ finishes execution.
Now, $\text{T1}$ runs and executes wait(s1): Since $s1 = 1$ , it decrements to $0$ , and $\text{T1}$ proceeds.
$\text{T1}$ executes x = x + 1: $x$ becomes $2$ .
$\text{T1}$ executes print(x): Prints $2$ .
$\text{T1}$ executes wait(s2): Since $s2 = 1$ , it decrements to $0$ , and $\text{T1}$ proceeds without blocking.
$\text{T1}$ executes signal(s1): $s1$ becomes $1$ . $\text{T1}$ finishes execution.

Outcome: $\text{T2}$ prints $1$ , and then $\text{T1}$ prints $2$ . (Matches Option B)

Conclusion

Option A is incorrect because if $\text{T1}$ runs first, it inevitably blocks on wait(s2) before $\text{T2}$ can execute.
Option D is incorrect because if $\text{T2}$ runs first, it signals both semaphores, allowing $\text{T1}$ to complete successfully without any deadlock.