Synchronization

GATE CS previous year questions · 2 questions

GATE CS 2024 Set 1 | Question 40

MCQ · 2 marks · −0.66

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption.

    T1                T2

a = a + 1;        b = 2 * b;
b = b + 1;        a = 2 * a;

Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3) (a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3) (a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4) (a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Explanation

Answer: (A)

Each thread runs its two statements in order, so the four atomic statements interleave in \(\binom{4}{2} = 6\) ways. Writing the results as \((a, b)\):

T1 entirely first: \(a = 2\), \(b = 2\), then \(b = 4\), \(a = 4\): (4, 4).
T2 entirely first: \(b = 2\), \(a = 2\), then \(a = 3\), \(b = 3\): (3, 3).
Each of the other four orders runs a = a + 1 before a = 2 * a and b = 2 * b before b = b + 1, giving (4, 3).

(3, 4) is impossible: \(a = 3\) needs T2 to finish before T1 starts, while \(b = 4\) needs T1 to finish before T2 starts. Options B, C and D all contain it.

Answer: A

GATE CS 2024 Set 2 | Question 46

MSQ · 2 marks

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized to 0). The threads execute the code shown below.

// code of T1
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 T1 and T2 execute concurrently?

T1 runs first and prints 1, T2 runs next and prints 2 T2 runs first and prints 1, T1 runs next and prints 2 T1 runs first and prints 1, T2 does not print anything (deadlock) T2 runs first and prints 1, T1 does not print anything (deadlock)

Explanation

Answer: (B), (C)

Only one thread at a time can be between wait(s1) and signal(s1), and s2 starts at 0.

If T2 gets s1 first, it prints 1, and its signal(s2) and signal(s1) never block. T1 then enters, prints 2, finds s2 at 1 and finishes. So (B) is possible, and (D) is not: T1 cannot stay blocked.
If T1 gets s1 first, it prints 1 and blocks on wait(s2) while still holding s1. Only T2 could signal s2, but it is stuck at wait(s1), so both wait forever and T2 prints nothing. So (C) is possible and (A) is not.

Answer: B, C