in Operating System edited by
22,065 views
60 votes
60 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$
in Operating System edited by
by
22.1k views

4 Comments

All possible values of x are-

-4,-3,-2,-1,0,1,2

13
13
edited by

1.   $\\W\\ P(S)\\ 1.Load R_{w},M[x]\\ 2.INCR, R_{w}\\ 3.Store\ M[x], R_{w}\\ V(S)\\$ 2.  Similarly for X         3.  $\\ Y\\ P(S)\\ 1.Load R_{y}, M[x]\\ 2.DECR, R_{y}\\ 3.Store \ M[x],R_{y}\\ V(S)\\$       4.   Similarly for Z

For Minimum value=-4

Y(complete)- Z(till 2)- W(complete)- X(complete)- Z(remaining)

For maximum value=2

One possibility

W(till 2)- Y(complete)- Z(complete)- W(remaining)- X(complete)

Other values like -3, -2 , -1 , 0 , 1 can also be generated.

4
4
It can be solved using lost update concept.
0
0

9 Answers

112 votes
112 votes
Best answer

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
by

4 Comments

@Rusty_01 preemption can take place inside CS 

0
0

@abir_banerjee In the case of Atomic operation, I mean.

0
0
ohh!!! thts why this is the best answer
0
0
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

4 Comments

got it sir thanks
0
0
Why after process W, Process Y was executed and why not Process X
0
0

@Avinash Choudhary
Because here we’ve to design the process flow such a way, that we can maximize the value of X. Yes, of course we can consider Process X after Process W, but if we do so, we would not be able to maximize the value of X.

So, to maximize the value of X, steps would be – 

Step 1: Process W arrives and makes the Counting Semaphore, S value down to 1 from 2 and Reads the value of X, i.e., 0 and let’s say, gets preempted by CPU.
So, when Process, W will be alive again, it would read X=0 only.

Step 2: Then, we should must send Process, Y and it makes the counting Semaphore value S=0 from 1 (since, W is already sleeping somewhere inside the Critical Section and it has not still come out) and read the value of X which is still 0.
By executing X = X – 2; the new value of X becomes X = (-2) and comes out of Critical Section.
So, new updated value of X = (-2) and Counting Semaphore, S is available with its value 1

Step 3: Next, we must need to send the Process, Z and it makes the Counting Semaphore value from 1 to 0
It executes again X = X – 2; as its role and makes the new updated value of X = (-2) – (-2) = (-4)
Since, already the value X was -2 done by Process Y
then, Z comes out of the Critical Section and again, makes the Counting Semaphore, S available with value 1

Step 4: Now, W let’s say wakes up from Preemption and as we know, W doesn’t know abuot the updated value of X = (-4)
W still remembers what it last read when it was just going to sleep, i.e., 0
So, now Process W executes X = X + 1; and makes the new value of X as 0 + 1 = 1
Hence, the value of X = (-4) is totally lost now, there is no further existence of X = (-4)
And, then W comes out of the Critical Section by updating Counting Semaphore value as 2 (because, last time when Process Z left Critical Section, that time value of Counting Semaphore was 1)

Step 5: Now last process is left and that’s Process X
it’ll be invoked now and will make the Counting Semaphore value S = 1 from 2
Now, it’ll be executing X = X + 1; and will make the new value of X = 1 + 1 = 2 and will come out of the Critical Section again by making the Counting Semaphore available with its value 2

Hence, finally the Maximum value of X would be 2 and to get that, you must have to follow this sequence. 
So, basically there are 2 sequences of execution possible to achieve the maximum value of X (i.e., 2) and those would be – 

  1. Process W (needs to preempt just after reading value of X) → Process Y (complete) → Process Z (complete) → Process W (complete) → Process X (complete)     OR, 
  2. Process X (needs to preempt just after reading value of X) → Process Y (complete) → Process Z (complete) → Process X (complete) → Process W (complete)

Similarly, to get the minimum value of X (i.e., -4), there also we have 2 ways – 

  1. Process Y (needs to preempt just after reading value of X) → Process W (complete) → Process X (complete) → Process Y (complete) → Process Z (complete)     OR, 
  2. Process Z (needs to preempt just after reading value of X) → Process W (complete) → Process X (complete) → Process Z (complete) → Process Y (complete)

Hope this helps!

4
4
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

4 votes
4 votes

We will be getting Max value of  x as 2

Answer:

Related questions