Dark Mode

22,761 views

98 votes

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?

0

1

137 votes

Best answer

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

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

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

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

19 votes

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

0

12 votes

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:

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