retagged by
13,216 views
21 votes
21 votes

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}$
  4. There is a deadlock involving all the threads
retagged by

4 Answers

Best answer
21 votes
21 votes

Correct Options: A,B,D

The given code allows up to $2$ threads to be in the critical section as the initial value of semaphore is $5$ and $2$ wait operations are necessary to enter the critical section $(\lceil 5/2\rceil = 2).$

In the critical section the increment operation is not atomic. So, multiple threads entering the critical section simultaneously can cause race condition.


  1. Assume that the $5$ threads execute sequentially with no interleaving then after each thread ends the counter value increments by 1. Hence after $5$ threads finish, counter value will be incremented $5$ times from $0$ to $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
selected by
5 votes
5 votes

Answer should be: A, B, D

No way it’s a Mutex problem since the Capacity of the Semaphore, S is 5
Hence, at any given point of time, total 5 processes can encounter to get into the Critical Section and that’s the property of Counting Semaphore.

Now, if we go option-by-option not by looking at the program too much (since, that’d be the time efficient way to solve here) – 

Option A: The value of the counter is 5 after all the threads successfully complete the execution. Yes, possible. Why even 5, it can be any value 6, 7, 10. 50, whatever it wants if all the processes follow a sequential order to execute the Critical section. Here, it’s given in the question that, 5 threads are processing the block, so yes – if they process sequentially, then Counter value can be 5 at the end. So, Option A is correct.

Option B: The value of the Counter is 1 after all the threads successfully complete the execution. Yes, possible.
Because, this ‘Counter++;’ is a line of code which is actually 3 lines of machine code should look like – 

Line #1: reg = Counter;
Line #2: reg = reg + 1;
Line #3: Counter = reg;

Now, let’s say Process, P1 is the first process which went inside the critical section and executed only Line #1 and after that. gets preempted by the CPU. So, when Process P1 will wake up later, it will only remember reg = 0 and from there, it’ll start executing again from Line #2.

Now, let’s say – when this Process P1 is in preempted mode and sleeping, other of processes came and made the Counter value as 4 (Because leaving P1, there should be other 4 processes since in the question, it’s given 5 threads are executing the parop())
But when P1 will wake up, it doesn’t make any sense to Process P1 and P1 will still remember only one thing – My reg value is 0 and from there it’ll start executing and will finally make Counter value as 1 and will come out of the Critical Section. 
Hence, final value of the Counter as 1 is possible. Option B is also correct.

Option C: The value of the Counter is 0 after all the threads successfully completed. No, never ever possible.
Even a single process also completes all the steps successfully, then minimum value would be 1, but never 0

Option D: There is a Deadlock involving all the steps. Yes, possible.
Let’s say – 

Process P1 came and execute the first W(S); (Line #5 in the question) and gets preempted by CPU. So, current updated value of Semaphore, S = 4

Then, Process P2 came and execute the first W(S); (Line #5 in the question) and gets preempted by CPU. So, current updated value of Semaphore, S = 3

Then, Process P3 came and execute the first W(S); (Line #5 in the question) and gets preempted by CPU. So, current updated value of Semaphore, S = 2 

Then, Process P4 came and execute the first W(S); (Line #5 in the question) and gets preempted by CPU. So, current updated value of Semaphore, S = 1

Then, Process P5 came and execute the first W(S); (Line #5 in the question) and gets preempted by CPU. So, current updated value of Semaphore, S = 0

So, the capacity of Semaphore, S is NULL now. No further process from outside can execute the first W(S) 
Also, even any of these 5 processes which are already invoked, if wakes up or, even more than one process wake up, they can’t make any further progress.
Because, there is no Semaphore, S left to execute the second W(S) (Line #6 in the question)
So, Deadlock is possible following this manner.

Hence, Option D is also valid

edited by
3 votes
3 votes
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.

Therefore Deadlock occur.

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.
Answer:

No related questions found