The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 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$
asked in Operating System by Veteran (367k points)
edited by | 4.1k views
Co relate this example with lock variable for Mutual exclusion. Why does lock fail? You will get the approach.

5 Answers

+60 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$.)

answered by Veteran (367k points)
edited by

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

Thats what I also told.
you wrote $-2$ at end. that's why..
The sentence starts with "if". Please read the whole sentence always.

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)


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

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


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

Yeah. How is it possible to decide in 3 mins
@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?
If the operation of incrementing/decrementing the values were atomic, as in TSL, then the output would've been -2?

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

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

answered by Boss (30.9k points)
Can a process be preempted while it is in critical section?
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
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.

answered by Loyal (6.3k points)
0 votes



  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.


R=R +1=2

Store R,x

x=2 Maximum value possible 

Similarly, the Minimum value will be -4 

Option D

answered by (159 points)
–4 votes

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 .
answered by (249 points)

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;


For Y&Z


2:load X

3:decrement X by 2

4:store X


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




Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,942 questions
49,497 answers
65,748 users