edited by
22,267 views
61 votes
61 votes

A shared variable $x$, initialized to zero, is operated on by four concurrent processes $W, X, Y, Z$ as follows. Each of the processes $W$ and $X$ reads $x$ from memory, increments by one, stores it to memory, and then terminates. Each of the processes $Y$ and $Z$ reads $x$ from memory, decrements by two, stores it to memory, and then terminates. Each process before reading $x$ invokes the $P$ operation (i.e., wait) on a counting semaphore $S$ and invokes the $V$ operation (i.e., signal) on the semaphore $S$ after storing $x$ to memory. Semaphore $S$ is initialized to two. What is the maximum possible value of $x$ after all processes complete execution?

  1. $–2$
  2. $–1$
  3. $1$
  4. $2$
edited by

9 Answers

Best answer
112 votes
112 votes

Since, initial value of semaphore is $2$, two processes can enter critical section at a time- this is bad and we can see why. 

Say, $X$ and $Y$ be the processes. $X$ increments $x$ by $1$ and $Z$ decrements $x$ by $2$. Now, $Z$ stores back and after this $X$ stores back. So, final value of $x$ is $1$ and not $-1$ and two Signal operations make the semaphore value $2$ again. So, now $W$ and $Z$ can also execute like this and the value of $x$ can be 2 which is the maximum possible in any order of execution of the processes.

(If the semaphore is initialized to $1$, processed would execute correctly and we get the final value of $x$ as $-2$.)

edited by
30 votes
30 votes

$x$ is initially $0$ and $S = 2$

$W$ process reads $x$ and increments it then it is preempted. Still value of $x$ is $0$, coz store operation is yet to be performed. for $W$ to execute it has first performed a $wait$ operation binary semaphore $S$. Now $S$ is $1$.

after this processes $Y$ and $Z$ came to do what ever they want to do with the value of $x$. This is possible because $S=1$. So, at the end when they both are done $S=1$ still.

after this $W$ is made to execute again to store the value $1$ in $x$ and makes $S=2$ just before it exits. After which process $X$ executes(without any problem coz it just needs $S$ to be $1$ atleast). It reads the value of $x$ as $1$ and increments it to $2$ and exits. 

answer = option D

8 votes
8 votes

S=2

x=0

  W               X                Y                 Z

1:P(S)         P(S)            P(S)              P(S)

2:x=x+1       x=x+1         x=x-2            x=x-2 

6:V(S)          V(S)            V(S)             V(S)

Instruction 2 has 3 parts 

3:Load x,R

4:Inc R

5:Store R,x

How process are runing ?

W: 1,2,3 | X:1,2,3,4,5,6 ............................................

Register R in W is having value 1 now whatever value we get from other processes is going to overwrite.

So

R=R +1=2

Store R,x

x=2 Maximum value possible 

Similarly, the Minimum value will be -4 

Option D

Answer:

Related questions