Question on Semaphores

34. 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:
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++)  { 
    Entry(R, S);
    b[i] = g(a[i]);
}

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

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

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

(B)
ExitX (R, S) {
    V(R) ;
    V(S) ;
}

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

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

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

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

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

Answer : (C)

Explanation :

Lets see the difinition of Semaphore Wait (P) and Signal (V)

P(S) {
        While (S <= 0) ; //no op
         S--;
}

V(S) {
        S++;
}

If semaphore initialized to n, usually n processes can enter the critical section guarder by P(S).

Now, Lets examine the options.

Option A :

Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    P(R) ;
    V(S) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    P(S) ;
    V(R) ;
    b[i] = g(a[i]);
}

As you can see both the processes X and Y, wait for P(R) and P(S) respectfully as R and S are intialized to 0. This is like a deadlock situation.

Option B
Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    V(R) ;
    V(S) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    P(R) ;
    P(S) ;
    b[i] = g(a[i]);
}

As you can see, process Y cannot go further as it waits on R (and S). Process X can release those semaphores and process Y can go inside. This works well in normal scenario. But, it could be possible that after first execution of ExitX, process X can continue and try to execute ExitX before Y can execute EntryY. Since this is a binary semaphore (which can possibly have only two values), this is a invalid use-case.

Option D
Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    V(R) ;
    P(S) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    V(S) ;
    P(R) ;
    b[i] = g(a[i]);
}

The same invalid use-case can happen in this scenario as well. Process X runs V(R) and Process Y runs V(S) and then X can execute P(S) can go through the for loop again and try to run V(R). But that would be invalid as R is already 1.

Option C:
Process X:
private i;
for  (i  = 0; i < n; i++)  { 
    a[i] = f(i);
    P(S) ;
    V(R) ;
}

Process Y:
private i;
for  (i  = 0; i < n; i++)  { 
    V(S) ;
    P(R) ;
    b[i] = g(a[i]);
}

Process Y would go first here and execute V(S) and then it waits on P(R). Process X then executes P(S) and executes V(R) and continues. Process Y then can excute P(R) now and initialize b[i]. Now, X would come back at P(S) again and waits and similarly process Y would go through the for loop and executes V(S). This way X and Y execute altenatively one after the other i.e., X initializes a[0] and then Y generates b[0] and X generates a[1] etc.

Topics to Revise :
Semaphore

References :