Question

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

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

}

Answer 1

Correct Answer - Option 3 :

ExitX(R, S) {

        P(S);

        V(R);

}

EntryY(R, S) {

          V(S);

          P(R);

}

The correct answer is “option 3”.

EXPLANATION:

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

}

From the given structure of two processes, main purpose is :

1. Deadlock should not occur

2. Binary semaphore must not be assigned value greater than 1.

Option 1: FALSE

ExitX(R, S) {

P(R);

V(S);

}

EntryY(R, S) {

P(S);

V(R);

}

This statement will leads to deadlock.

So this statement is false.

Option 2: FALSE

ExitX(R, S) {

      V(R);

      V(S);

}

EntryY(R, S) {

         P(R);

          P(S)

This statement will increase value of semaphore between 1 to n.

But value of binary semaphore must be less than 1.

So this statement is false.

Option 3: TRUE

ExitX(R, S) {

        P(S);

        V(R);

}

EntryY(R, S) {

          V(S);

          P(R);

}

In this statement, each and every value inserted by the process X in array will be immediately consumed by process R.

Hence, this statement represents correct implementation of ExitX & EntryY.

Option 4: FALSE

ExitX(R, S) {

        V(R);

        P(S);

}

EntryY(R, S) {

         V(S);

         P(R);

}

This statement will also increase value of semaphore R & S between 2 in many cases which should be less than 1.

So this statement is false.

Hence, the correct answer is “option 3”.