# GATE CSE 2021 Set 1 | Question: 46

428 views

Consider the following pseudocode, where $\textsf{S}$is a semaphore initialized to $5$ in line $\#2$ and $\textsf{counter}$ is a shared variable initialized to $0$ in line $\#1$. Assume that the increment operation in line $\#7$ is $\textit{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 $\textsf{parop}$ concurrently, which of the following program behavior(s) is/are possible?

1. The value of $\textsf{counter}$ is $5$ after all the threads successfully complete the execution of $\textsf{parop}$
2. The value of $\textsf{counter}$ is $1$ after all the threads successfully complete the execution of $\textsf{parop}$
3. The value of $\textsf{counter}$ is $0$ after all the threads successfully complete the execution of $\textsf{parop}$

edited
0
A: Possible, all threads execute one by one

B: Possible, thread 1 and 2 enters first. Both read value as 0 and only 1st write. Now all other threads (2,3,4) comes and increment the value. Finally 2nd threads write its value which is 1

C: Not sure

D: Possible, all threads execute line 5 before anyone executes line 6
1
A,B,D

1 vote
Given that five threads concurrently executing parop()

case 1 : when all those five threads execute line 5 and preempt, then All threads blocked at line 6.

case 2 : If line 5 to Line 10, executive without preemption by threads one after another. then Counter value is 5.

Case 3 : Initially counter = 0, let T1, execute line 5,6 and note that line 7 is non-atomic instruction. So before saving 1, T1 preempt.

And remaining Threads completes the execution. After that T1 resume and make counter = 1 and completes the execution.

Note that Case 3 produces minimum value of counter. So Counter can’t be 0 after the execution of threads.

A,B,D

1. Assume the processes execute sequentially with no interleaving then after each process ends the counter value increments by 1, hence after 5 process 5 increments to zero hence a counter value of 5. Possible.
2. Let’s assume that a process used 2 waits and reads the counter value and didn’t update the value yet, all the other process let’s say the other processes executed sequentially incremented and stored the value as 4 but since the value isn’t written the first process yet the current value is overwritten by the first process as 1. Possible
3. There exists no pattern of execution in which the process increments the current value and completes while maintaining 0 as the counter value.Not possible
4. Assume that all the process use up the first wait operation, the semaphore value will now become zero and deadlock would’ve occurred. Possible

edited

## Related questions

1 vote
1
659 views
1 vote
Which of the following standard $C$ library functions will always invoke a system call when executed from a single-threaded process in a $\text{UNIX/Linux}$ operating system? $\textsf{exit}$ $\textsf{malloc}$ $\textsf{sleep}$ $\textsf{strlen}$