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

just follow what question says about semaphore S and follow the sequence 1 to 12 ....just write +2 from process x at last  is the key.

Answer 2

Let's consider increment operation is in 3 microinstruction

Step 1: Load Ri M

Step 2: Increment Ri

Step 3: M Ri

Where Ri is the local register allocated and it is used for temporary storage

1. Now consider process W, it increments x from 0 to 1 but after executing microinstruction and gets pre-empted. So at this time the value of  R1(temporary register)=1 but the x value will be still 0 since 3rd microinstruction is remaining.

2. Now consider process Y and Z runs completely and value of x change’s from 0 to -4.

3. Now W will start it’s execution and it will execute its 3rd microinstruction and overwrite x value from -4 to 1 and completes process x.

4. Now process X executes all instruction and it changes value of x from 1 to 2.

    So Maximum = 2

   Correct Answer: Option D (Maximum=2)

Answer 3

be greedy

see what i have done

see the arrows

main part is when X reads 1 from W allow context switch and dont update the value, as that is the maximum we can get, now let Y and Z write their values in any order they want, when everything completed, X will write final value 2 which it remembers. 
Hence 2 is the max value

Answer 4

The credit goes to @sanbaner

 

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!