GATE CSE 2013 | Question: 39

Question

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?

• 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(S); 
   V(R); 
  }
  EntryY(R, S) { 
   V(S); 
   P(R); 
  }
  

• D.

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

Comments

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.

---

@samir757
There is a chance that $Y$ won't get enough $signals$ to get all $n$ values in $b$.

Answer 1

https://youtu.be/ka7e9gMIoPg

Answer 2

//A
private i; 
for (i=0; i< n; i++) { 
    a[i] = f(i); 
    ExitX(R, S); 
} 

//B
private i;
for (i=0; i< n; i++) { 
    EntryY(R, S); 
    b[i] = g(a[i]); 
}


A and B are supposed to execute such that A[0]->B[0]->A[1]->B[1] and so on

Consider Option A :

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

A	B
a[0] = f(0)
Busy waiting //R==0
	Busy waiting //S==0

This creates a deadlock hence A not possible.

Option B:

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

A	B
a[0] = f(0)
R=1
S=1
a[1] = f(1)
R=1
S=1
a[2] = f(2)

This will starve B and lead to incorrect results.

 

Option D :

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

A	B
a[0] = f(0)
R=1
S=0 // Busy Waiting
	S=1
S=0
a[1] = f(1)
R=1

This leads to incorrect solution again.
A,B,D eliminated, C can be proven to work in the same way.