22,761 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);
}


Took Me About 5 Minutes to figure that (C) is the answer and why (D) is not the Answer. I Guess Even if we can derive at the Answer, should Kind Of Leave Such Questions In Actual Exam And Save Time.
before going through the best answer, can someone explain on what lines I should think in order to move in the direction of the solution. Unable to proceed...
If we are storing the value of f(i) in array a[i] , then why is required to have same iteration present for both the values a[i] and b[i] , why cant i skip one and calculate other later as in option b or d.

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

i have a silly doubt. Since both Semaphores are initialized to zero, how is C the answer?
edited by
awesome :)
Also check premption condition

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

"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..
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)
hello Tushar, since GO doesn't allow sending messages, could we connect on LinkedIn?

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

### 1 comment

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[0] and a[1] both but Process Y will not able to compute b[1] because P(R) signal. Below Image is showing such a case that Y will not able to execute exactly n times.