4.1k views

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 | 4.1k views
0
Co relate this example with lock variable for Mutual exclusion. Why does lock fail? You will get the approach.

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
+2

they have asked the maximum possible value of $x$, which is +2

+6
Thats what I also told.
+1
you wrote $-2$ at end. that's why..
+15
+2

Arjun ,

I understand when you say the final value of x = 1 for the first two processes entered , but as X & Y processes, each will use 'signal(S)' after the assignment of x=1, so when one of them uses 'signal(S)' , 'S' will be  S =1, and one of the other two processes (W&Z) will enter the critical section.In that case the answer will be x =0,

As x will be decremented by 2 and then incremented by 1 (if Z enters first and then W)

OR

x will be incremented by 1 and then decremented by 2 (if W enters first and then Z)

+1
what is the meaning of stores back  and its effect ?
+1
How do we know which process to preempt and at which place..?
+2
by intuition
+1
are the previous x values overwritten ?
+1
They are overwritten in the memory only after the store instruction has executed.
+1
Well explained Sir :)
+2
and the minimum value possible is -4. Right?
+3
My intuition tells many thing how can I possibly decide whats correct in 3 Mins while solving question?
+3
yes minimum --4
+1
@arjun sir here the process will get executed only once right ???
+1

@srestha

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

The question says that before reading it invokes wait on it......so wait(S) and suppose process X reads the value ...even it prempts now.....other process cannot read it since signal is not yet done right?

so one process should execute completely , store back in mmeory and then the next processs will execute

where am i wrong

0
Yeah. How is it possible to decide in 3 mins
0
@Arjun Sir, in last line shouldn't the maximum possible value will be 1 when semaphore is initialized with 1 because we don't know the ordering of the all 4 processed. Please clarify?
0
If the operation of incrementing/decrementing the values were atomic, as in TSL, then the output would've been -2?
0

@ sir, Sir what is the approach of this type of question to solve correctly, I mean rather than choosing an execution sequence can we say like this, that S=2 i.e anytime only 2 process can enter maximum, so to achieve maximality we can assume that W & X will enter simultaneously & make the value 0+1+1=2 as they both are incrementing.

I mean to say that regardless of any execution sequence maximum value of x=2 & minimum value of x= -4(y & z simultaneously), as thinking of a correct execution sequence which will give max. value is little bit tough for me.

please Correct me if I'm wrong.

$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.

0
Can a process be preempted while it is in critical section?
0
it can be preempted but

the condition to enter in any process is to qualify wait(s)

so generally we can achieve mutual exclusion when s is binary

but here it is two so here after preemption it can go in other process
0
got it sir thanks
+1 vote

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.

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

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

p(S)

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 .
+12

inc and dec operations can be written as:

for W&X= 1:P(S)

3:increment X by 1

4:store X;

5:V(S)

For Y&Z

1:P(S)

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

1