8.8k 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 | 8.8k views
+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...
0

@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[0]

--------------------------------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[1]

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

Process Y

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

Line 5// computes b[0]

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

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

+13

@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[0] 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[1].and again executes P(S)  and get blocked.

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

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[0] and a[1] before b[0] 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

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.

by Veteran (420k points)
edited by
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?
+3

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[0] here as a[0] 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[0] 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.
+1

Hope this will help.

0

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[0] != g(a[0])  but  b[0] = g(a[1]).

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[0] = g(a[1]), but here should be a[0] = g(a[0]).

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.

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.

by Loyal (7.1k points)
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[0]$, we need to already have value of $a[0]$ with us because $b[0] = g(a[0])$, 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[0]$ and then after this if $process Y$ executes, it will already have the corresponding value of $a[0]$ to calculate value of $b[0]$. 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[0]$ but value of $a[0]$ is not calculated yet. Now look at option $C$. Before calculating the value of $b[0]$, $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[0]$. (now we can find value of $b[0]$ because $b[0] = g(a[0])$). 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[0]$. This can be generalized to $i, 0 < i < n$.

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

by (23 points)

1
2