GATE CS 2021 Set 1 Q.56 (CS Q.46): Process Synchronization and Concurrency

Consider the following pseudocode, where $S$ is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.

1. int counter = 0;
2. Semaphore S = init(5);
3. void parop(void)
4. {
5.     wait(S);
6.     wait(S);
7.     counter++;
8.     signal(S);
9.     signal(S);
10. }

If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?

The value of counter is 5 after all the threads successfully complete the execution of parop.

The value of counter is 1 after all the threads successfully complete the execution of parop.

The value of counter is 0 after all the threads successfully complete the execution of parop.

There is a deadlock involving all the threads.

Official answer and solution

Official answer: A, B and D
From: Official GATE 2021 answer key

Solution

Analyze thread interleavings with non-atomic increments and investigate potential semaphore deadlocks.

The function parop executes two consecutive wait(S) calls before the critical section and two signal(S) calls after it. Semaphore $S$ is initialized to 5.

Scenario 1 (Deadlock - Option D): Suppose all 5 threads execute line#5 concurrently. Each thread successfully executes its first wait(S), decrementing $S$ from 5 down to 0. Now, all 5 threads advance to line#6 and invoke their second wait(S). Because $S = 0$ , every thread blocks waiting for a signal(S) that can only be issued inside the critical section. Thus, a circular wait deadlock occurs involving all 5 threads.

Scenario 2 (Serial execution - Option A): If threads acquire the semaphore sequentially (e.g., thread 1 takes 2 permits ( $S=3$ ), increments counter, and releases both permits ( $S=5$ ), followed by threads 2, 3, 4, and 5 in sequence), each thread completes its execution without race conditions, leaving counter = 5.

Scenario 3 (Interleaved race condition - Option B): Two threads can enter the critical section simultaneously because 5 permits allow two threads to each acquire 2 permits ( $S = 5 - 4 = 1$ ). Because counter++ is not atomic (consisting of read, modify, write), threads can read the shared value 0 concurrently and both write back 1. Repeating this interleaving across all threads allows the final value of counter to be 1.

Scenario 4 (Option C): Once all threads have successfully completed execution of parop, at least one thread must have executed the write stage of counter++ from initial value 0. Since counter is only incremented, it is impossible for counter to remain 0 after all threads complete successfully.

Therefore, program behaviors A, B, and D are possible.

Final answer

A, B, D

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 56 of 65, printed as CS Q.46
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source