# GATE2013-39

12.7k views

A certain computation generates two arrays a and b such that $a[i] = f(i)$ for $0 \leq i < n$ and $b[i] = g(a[i])$ for $0 \leq i < n$. Suppose this computation is decomposed into two concurrent processes $X$ and $Y$ such that $X$ computes the array $a$ and $Y$ computes the array $b$. The processes employ two binary semaphores $R$ and $S$, both initialized to zero. The array $a$ is shared by the two processes. The structures of the processes are shown below.

Process X:

private i;
for (i=0; i< n; i++) {

a[i] = f(i);

ExitX(R, S);

}


Process Y:

private i;
for (i=0; i< n; i++) {

EntryY(R, S);

b[i] = g(a[i]);

}


Which one of the following represents the CORRECT implementations of ExitX and EntryY?

1. ExitX(R, S) {
P(R);
V(S);
}
EntryY(R, S) {
P(S);
V(R);
}

2. ExitX(R, S) {
V(R);
V(S);
}
EntryY(R, S) {
P(R);
P(S);
}

3. ExitX(R, S) {
P(S);
V(R);
}
EntryY(R, S) {
V(S);
P(R);
}

4. ExitX(R, S) {
V(R);
P(S);
}
EntryY(R, S) {
V(S);
P(R);
}


edited
5
Somebody please contrast the difference between option (C) and (D). Both seem to be possible answers to me.
1
give solution if anybody knows...
1

@Arjun Sir

How C can be the correct answer to this because we can have a sequence possible for option C also just like option D where we can execute Process X two times Before execution of Process Y so some iterations of Y will not be completed. Here Process X and Y are (after inserting ExitX and EntryY from option C):-

Process X                                   Process Y
{                                           {
1) private i;                               1) private i;
2) for (i=0; i< n; i++)                     2) for (i=0; i< n; i++)
{                                           {
3) a[i] = f(i);                             3) V(S);
4) P(S);                                    4) P(R);
5) V(R);                                    5) b[i] = g(a[i]);
}}                                           }} 

The sequence is:-

Process X:

Line 1

Line 2

Line 3    // it computes a

--------------------------------Got Preempted -------------------------

Process Y:

Line 1

Line 2

Line 3  // It makes S=1 because no one was yet waiting on S

-----------------Got Preempted----------------------

Process X

Line 4 // As S=1 so P(S) will be successful and makes S=0

Line 5// It makes R=1 because no one was yet waiting on R

Line 2 // here i=1

Line 3// it computes  a

--------------got preempted--------------------

Process Y

Line 4 // as R=1 so P(R) will be successful

Line 5// computes b

Clearly here we can see that we can have two iterations of process X before any iteration of Y in between

3
Option C is correct only...

in option C

Process X does Wait(S) followed by Signal(R)

in option D

Process X does Signal(R) then it is followed by Wait(S)

as the signals are getting lost their corresponding iterations will be missed out in Process Y .

If we change the order of Signal(S) and Wait(R) in Entry Y , then D option also correct.
2

your counter example is complete wrong, there is NO preemption possible.

Both  Process X and  Process Y will be executed without any intervention by other processs.

19

@Bikram Sir

Now I got what you were trying to explain thank you, Sir, for clearing my doubt.

My Mistake:-

I am wrong because I am trying to preempt the processes at any time when I want which is not the case in the real time.

Why Option C is Correct:-

--Firstly process X runs and finds a then it executes P(S) and will be blocked.

--Then Process Y runs and executes V(S) which makes process X to go to ready state from blocked state.

--Then Process Y executes P(R) and got blocked.

--Then Process X which the was in the ready state starts running and executes V(R) which makes process Y to go to ready state from blocked state.

--Then Process X finds a.and again executes P(S)  and get blocked.

--Then Process Y which was in ready state enters to running state and computes b.

and so on

Hence here no iteration of Process Y will be missed out and the placement of ExitX and EntryY is in such a way that both the process will able to complete their iterations and not two iterations of Process X can compete for consecutively without having one complete iteration of process Y in between these  two iterations of process X

1
@Arjun [email protected] Sir Can u plz tell me
what that line means  in ans of C) option
"So, this ensures that no two iterations of either X or Y can proceed without an iteration of the other being executed in between."
V(S) cannot executes without V(R) once
or we can say S cannot execute fully without R once,rt?
1

@srestha

So, this ensures that no two iterations of either X or Y can proceed without an iteration of the other being executed in between."

This means both X and Y are proceed without any preemption by other. It want to say Both X and Y are atomic.

1
please elaborate more. Unable to understand difference between C and D?
2
@Bikram Sir, Why Preemption is not possible in the middle?
0
@ akb1115
But we are calculating a and a before b as explained in ur comment itself. Isn't it wrong?
0

Had  it been given "Counting Semaphores" instead of Binary Semaphores then option B) & D) would have been correct?

0

Hi @sushmita ji,

Option (D) is also providing Mutual Exclusion. But process Y may not access entire array(means Y will not be able to compute b) because in some special cases signal loss may occur(Because S and R are Binary semaphore ) same is mentioned in the selected answer and various comments.

0
explain further
0
@Arjun Sir

I cannot understand how C is correct.

Process Y -> V(S), P(R) blocked

Process X -> Computes a[i] , P(S), V(R) , again computes a[i] for the second time. Y did not yet read one time. So Y cannot complete its full iteration.
0
since it is concurrent process we can preempt and wake it up using v(s).
0

please close this question because it is duplicate

0

@akb1115

"My Mistake:-

I am wrong because I am trying to preempt the processes at any time when I want which is not the case in the real time."

Why can't a process be preempted at any time? What if time quantum expires (and Round Robin scheduling was being used)?

0
Still not able to get the difference between option C and D even after going through discussions below. Can someone please help?

1. $X$ is waiting on $R$ and $Y$ is waiting on $X$. So, both cannot proceed.

2. Process $X$ is doing Signal operation on $R$ and $S$ without any wait and hence multiple signal operations can happen on the binary semaphore so Process $Y$ won't be able to get exactly $n$ successful wait operations. i.e., Process $Y$ may not be able to complete all the iterations.

3. Process $X$ does Wait(S) followed by Signal(R) while Process $Y$ does Signal(S) followed by Wait(R). So, this ensures that no two iterations of either $X$ or $Y$ can proceed without an iteration of the other being executed in between. i.e., this ensures that all $n$ iterations of $X$ and $Y$ succeeds and hence the answer.

4. Process $X$ does Signal(R) followed by Wait(S) while Process $Y$ does Signal(S) followed by Wait(R). There is a problem here that $X$ can do two Signal(R) operation without a Wait(R) being done in between by $Y$. This happens in the following scenario:
Process $Y$: Does Signal (S); Wait(R) fails; goes to sleep.
Process $X$: Does Signal(R); Wait(S) succeeds; In next iteration Signal(R) again happens;

So, this can result in some Signal operations getting lost as the semaphore is a binary one and thus Process $Y$ may not be able to complete all the iterations. If we change the order of Signal(S) and Wait(R) in EntryY, then (D) option also can work.

edited by
0

## Check it once more..both will be executed in strict alternation as X then Y.

5

Option C is indeed correct.

I would like to add why the two semaphores are being used.

S semaphore is used to ensure process Y arrives in entry section before X exits.

R semaphore is used to ensure b[i]=g(a[i]) executes after a[i]=f(i).

0

I have doubts related to the option C and D :

C : What if the processes are executed in the following order?

ExitX()

P(S) //After this, the process is preempted

EntryY()

V(S) //Again preempted

ExitX()

P(R)

and after this, x is again executed. In this fashion, X can execute multiple times. isn't it so?

D : Actually both the options, that is C and D seems to serve same purpose to me.

12
For those who are confusing in C and D,please see if my comment helps

In Y process we are doing P(R), but not V(R). So basically someone has to do V(R) for Y.Now Y does P(R) on every iteration so someone has to do V(R) for every iteration of Y,Now who can signal V(R) ?Only X.

Now if any V(R) from X is lost then at least one iteration of Y can be blocked.

Lets us see why d is wrong:-Assume we want to compute for i=1,2

X does V(R),now R is set to 1.

Y does V(S) now S=1.

X does P(S) ,now S=0.

Now X has done one iteration and it starts the second iteration.

X does V(R), set R=1.

X does P(S), and goes to block queue of S.

Now here X is in 2nd iteration and Y is in first iteration.

Now x has computed a and 

Now Y does V(S),unblocks X.

X will exit now,it has computed a and a

Now Y does P(R) ,and set R=0 and compute b.

Now Y does second iteration and does V(s),and proceeds

Now does P(R) and goes to block state.

Now,there is no one to wake process Y

So thats why it is wrong.

Shortcut is to see that Y needs someone to do V(R) for its each iteration.X is doin but if some signal is lost,y will be blocked
0
@ Sushant Gokhale how is it deadlock?

EntryY is now looping in P(R) but ExitX which is currently at V(R) according to your sequence can proceed. When it does, then EntryY can also stop looping and move forward.
7
Can i falsify D based upon following approach?

S=0 , R=0

X executes V(R) and set R=1. Now s=0 and R=1 and X preempted.

Y comes it does V(S) and set S=1.Now S=1,R=1 .Now Y does P(R) as R=1 so success.

So Y is about to start b here as a is not available.Whihc is wrong.Hence D cannot be the answer
0
yes @rahul  it's correct.
0
Then this seems to be easy way to eliminate option d as compared to the one mentioned in answer:)
0
Sir excellent approach
0
@rahul

Your approach of negating option D is exactly how I thought. But as Arjun sir in his ans said " If we change the order of Signal(S) and Wait(R) in EntryY, then D option also can work." In our case even this alternative won't work right?
7

Can i falsify D based upon following approach?

S=0 , R=0

X executes V(R) and set R=1. Now s=0 and R=1 and X preempted.

Y comes it does V(S) and set S=1.Now S=1,R=1 .Now Y does P(R) as R=1 so success.

So Y is about to start b here as a is not available.Whihc is wrong.Hence D cannot be the answer

This approach is wrong ! Why ?

Because , when X executes V(R) and set R=1.  then a is already computed because ExitX() is code performed on exit i.e. after i=0 iteration of 'for loop' is completed.

0
semaphore operation is atomic.can not preempted in between.
0

I think you did some mistake in your example

in below line of your example you already executed V(S) in first iteration of Y.

Y does V(S) now S=1.

and again you are executing V(S) again in this line

Now Y does V(S),unblocks X.
0
With option(D), Process Y can complete all the iterations successfully except the last one.
2

Hope this will help.

1

according to me option D is correct.

but option C is correct,

I'm having doubt that, the reason for option D is wrong, same reason is occurring in option C.

In Option D -

ExitX(R, S) {
V(R);
P(S);
}
EntryY(R, S) {
V(S);
P(R);
}

people are saying that option D is wrong because after V(S) & before P(R) in y, process x can come again through 2nd iteration, that's why the corresponding value of process y from x is missing.

I mean there could be possibility that, b != g(a)  but  b = g(a).

I think same thing can happen with option C also -

ExitX(R, S) {
P(S);
V(R);
}
EntryY(R, S) {
V(S);
P(R);
}

In process x, P(S) is blocked , so switched to V(S) of process y, now P(R) is blocked in process y, so switched to process x. Now in process x it may so happen that it will easily execute V(R) & then come again through loop with it's 2nd iteration. a = g(a), but here should be a = g(a).

Moreover in option C , Deadlock is possible.

after coming 2nd iteration, process x will stuck at P(S) & as process Y has already executed V(S) so it will execute from P(R), which is clearly a Deadlock.

Don't know where I'm lagging.

0
b[i] needs a[i] to be computed first. Hence process X should be starting before process Y. Should we not take care of that too ?
1
The last iteration will never complete in option D? Is that it? Is that why it's wrong?
0
i have a silly doubt. Since both Semaphores are initialized to zero, how is C the answer?
0
awesome :)

Approach that must be followed while solving this kind of problem :

1. Identify producer and consumer and which semaphore is acting as wake up signal for consumer.

2. Here there must be strict alteration as elements of B  is dependent on A and semaphores are binary. If there would have been counting semaphore then no need of strict alteration as count will be maintained by counting semaphore.

3. Producing element in a[] up(sem 1(signal for consumer)) then block it till b does not calculate f(a[i]) so down(sem 2 ) here producer will be blocked. Now b will consume signal generated by a(sem 1) and calculate element of b(fa[i]) hence down (sem 1) now as a[i] and b[i] is done to calculate next element of a up (sem 2) so that producer can get unblocked and produce next element.

c matches this process.

0
"If there would have been counting semaphore then no need of strict alteration as count will be maintained by counting semaphore."

Can you explain this statement a bit more..
0
If there would have been counting Semaphore then all the wait signals will keep getting saved and process can use it later (in counting semaphore we maintain integer means collection of bits to represent integer) whereas in binary semaphore or mutex only two bits are there 0 and 1 means only two values it can take ....so if binary semaphore's value is 1 and if signal is performed then it's value will be 1 only (it will not get incremented whereas in counting semaphore it will get incremented and hance signal will se saved)

Let us think of it in this way. To calculate value of $b$, we need to already have value of $a$ with us because $b = g(a)$, Else some error will be thrown.

So there can only be 2 cases:

1. $Process X$ is selected first, this is good. It will calculate the value of $a$ and then after this if $process Y$ executes, it will already have the corresponding value of $a$ to calculate value of $b$. If this case happens always, we do not need any semaphores.
2. $Process Y$ is selected first. This is bad because now $Process Y$ will try to calculate value of $b$ but value of $a$ is not calculated yet. Now look at option $C$. Before calculating the value of $b$, $Process Y$ needs to pass $EntryY$ first. Inititally $S=0, R=0$. To pass $EntryY$, it will first execute $V(S)$, simple up operation on $S$, now $S=1,R=0$. Now it tries to execute next line, $P(R)$. It will be blocked because $R=0$ and will have to wait for $R$ to be $1$, i.e. until up operation is performed on $R$. Now while it is waiting, $Process X$ executes and it finds value of $a$. (now we can find value of $b$ because $b = g(a)$). Now it will go inside the $exitX$ and executes $P(S)$ so now $S=0,R=0$. It goes to the next line which is V(R). This is what we have been waiting for and now $S=0,R=1$. Now $process Y$ resumes and calculates $b$. This can be generalized to $i, 0 < i < n$.

And hence we can safely calculate the arrays $a$ and $b$.

0
When process Y resumes, will it again execute EntryY or resume from P(R) ?

Option D is incorrect because If we consider n=2 than Process  X will compute a and a both but Process Y will not able to compute b because P(R) signal. Below Image is showing such a case that Y will not able to execute exactly n times. ## Related questions

1
7.4k 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$ ... $S$ is initialized to two. What is the maximum possible value of $x$ after all processes complete execution? $-2$ $-1$ $1$ $2$
A computer uses $46-bit$ virtual address, $32-bit$ physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table ($T1$), which occupies exactly one page. Each entry of $T1$ stores the base ... needed to guarantee that no two synonyms map to different sets in the processor cache of this computer? $2$ $4$ $8$ $16$
Consider a hard disk with $16$ recording surfaces $(0-15)$ having 16384 cylinders $(0-16383)$ and each cylinder contains $64$ sectors $(0-63)$. Data storage capacity in each sector is $512$ bytes. Data are organized cylinder-wise and the addressing format is <cylinder no., ... is the cylinder number of the last sector of the file, if it is stored in a contiguous manner? $1281$ $1282$ $1283$ $1284$
Three concurrent processes $X$, $Y$, and $Z$ execute three different code segments that access and update certain shared variables. Process $X$ executes the $P$ operation (i.e., $wait$) on semaphores $a$, $b$ and $c$; process $Y$ executes the $P$ operation on semaphores $b$, $c$ and $d$; process $Z$ executes the $P$ ... $X:$ $P(a)P(b)P(c)$ $Y:$ $P(c)P(b)P(d)$ $Z:$ $P(c)P(d)P(a)$