The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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 (408k points)
edited by | 5k views
Seems as a past year gate problem.
0 it is.
It would have taken less time than typing if u had searched.
@mcjoshi thks ...
Co relate this example with lock variable for Mutual exclusion. Why does lock fail? You will get the approach.

 Each of the processes reads x from memory, increments by one, stores it to memory, and then terminates.

it is not atomic so preemption can happpen anywhere.


All possible values of x are-


5 Answers

+61 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 (408k points)
edited by
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.


@MRINMOY_HALDER The question is, after all processes complete execution. So, you can't say those values.

+21 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.6k 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
Why after process W, Process Y was executed and why not Process X
+2 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 (331 points)
+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 (6k 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 (247 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
49,548 questions
54,174 answers
71,128 users