1
$\begingroup$

I came across following problem:

A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i]=g(a[i]) for 0 ≤ 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:              | Process Y:              |
| private i;              | private i;              |
| for (i=0; i < n; i++) { | for (i=0; i < n; i++) { |
|    a[i] = f(i);         |    EntryY(R, S);        |
|    ExitX(R, S);         |    b[i]=g(a[i]);        |
| }                       | }                       |
+-------------------------+-------------------------+

How to correctly implement ExitX() and EntryY()?

Given solution:

+---------------+----------------+
| ExitX(R, S) { | EntryY(R, S) { |
|   wait(S);    |   signal(S);   |
|   signal(R);  |   wait(R);     |
| }             | }              |
+---------------+----------------+

Question 1 - can we swap wait and signal operations?

My doubt is will it make difference if we swap these operations, something like below?

+---------------+----------------+
| ExitX(R, S) { | EntryY(R, S) { |
|   signal(R);  |   wait(R);     |
|   wait(S);    |   signal(S);   |
| }             | }              |
+---------------+----------------+

I believe there is no difference in the behavior and overall outcome of the code when either of above two solutions is used. Am I right?

Question 2 - is weak alternation even required for this problem?

I feel the solution above does enforce weak alternation between two processes. That is, at max process X can generate k+2 a's when Y has generated k b's. To produce (k+3)th a, X has to wait for Y to produce (k+1)th b, as during computation of (k+1)th b, Y will signal X, unblocking it. Such weak alternation is not required.

Also I feel we dont really need two semaphores here and one semaphore T will suffice. It will be used by X to signal Y when it is blocked, in case there are no further a's produced by X, which can be used by Y to produce b's. Also this will need us to have a variable m share by both processes to keep track of difference between a's and b's produced by X and Y as follows:

+-------------------------+-------------------------+
| Process X:              | Process Y:              |
| private i;              | private i;              |
| for (i=0; i < n; i++) { | for (i=0; i < n; i++) { |
|    a[i] = f(i);         |    if(m==0) wait(T);    |
|    m++;                 |    b[i]=g(a[i]);        |
|    if(m==1) signal(T);  |    m--;                 |
| }                       | }                       |
+-------------------------+-------------------------+

Question 3

The text from which I was reading this says having signal() in both EntryY() and ExitX() as a first statement will cause process X to do two signal(R) operation without a wait(R) being done in between by process Y. In given solution, wait() is done twice by process X without letting process Y to do signal() multiple times in between. I believe both have same overall effect of weak alternation as explained in question 2 and none is more preferable than other. Am I correct with this?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.