Consider the following pseudocode, where S is a semaphore initialized to 5 in…
2021
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.
int counter =0;
Semaphore S= init(5);
void parop(void)
{
wait(S);
wait(S);
counter++;
signal(S)
signal(S);
}
If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?
- A.
The value of counter is 5 after all the threads successfully complete the execution of parop
- B.
The value of counter is 1 after all the threads successfully complete the execution of parop
- C.
The value of counter is 0 after all the threads successfully complete the execution of parop
- D.
There is a deadlock involving all the threads
Attempted by 164 students.
Show answer & explanation
Correct answer: A, B, D
Explanation:
Initial facts: the semaphore starts at 5 and each thread executes two wait calls, so each thread needs two permits to reach the increment. The increment operation (counter++) is not atomic, so read-modify-write interleavings can produce lost updates.
Why a final value of 5 is possible: if threads are scheduled so that each one acquires two permits, performs the increment, and then releases the two permits before the next thread starts its increment, no lost-update occurs and each of the five increments takes effect. Therefore the counter can be 5 after all threads finish.
Why a final value of 1 (or other values < 5) is possible: because counter++ is non-atomic, a thread can read the counter and be preempted before writing back its incremented value. Other threads can then perform increments and complete. When the preempted thread resumes it may write its stale (earlier read + 1) value, overwriting later updates. This lost-update pattern can produce a final counter as low as 1 in some interleavings.
Why a final value of 0 is impossible if all threads complete: every thread that completes parop executes counter++ at least once, and that operation writes a value greater than the initial 0. No completed thread will write 0, so the final counter cannot remain 0 when all threads have finished.
Why a deadlock involving all threads is possible: if all five threads perform the first wait roughly concurrently, the semaphore count drops from 5 to 0 (each thread holds one permit). Each thread then attempts the second wait and blocks because no permits remain. Since none can reach their signal calls to release permits, all five remain blocked and the system is deadlocked.
Summary of possible behaviors: the program can terminate with counter = 5 under non-interleaving schedules, it can terminate with a smaller value such as 1 due to lost-update races, and it can also deadlock if all threads consume one permit and block on the second wait. A final value of 0 is not possible if all threads complete.
A video solution is available for this question — log in and enroll to watch it.