GATE CSE 2013 | Question: 34

Question

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?

• A. $–2$
• B. $–1$
• C. $1$
• D. $2$

Comments

All possible values of x are-

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

---

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.

---

It can be solved using lost update concept.

Answer 1

p(S)

Read x;

store x;

v(s) so max possible value -2 by execution of any possiblity of sequence w x=1,X x=2,Y x=0,Z x=-2 or w x=1,Y x=-1,X x=0,Z x=-2 or any other squence .

Comments

Answer should be 2 

inc and dec operations can be written as:

for W&X= 1:P(S)

2:load X

3:increment X by 1

4:store X;

5:V(S)

For Y&Z

1:P(S)

2:load X

3:decrement X by 2

4:store X

5:V(S)

now W exeute step 1&2  and preempt so--> S=1,X=0{x has loaded  X so no change in X}

now Y execute 1,2,3,4 so..-->S=1{initially S is made 0 but after line 4 it again made 1},and X= -2

now Z execute 1,2,3,4 so -->S=1{initially S is made 0 but after line 4 it made 1},and X=-4

now W again executed line 3,4,5,so -->S=2{It only did signal oprtn On X causing it to 2} and X=1{overwrite X= -4}

Now x execute line 1,2,3,4,5 so  S-->2{first decremented then incremented} And X=2

Now