GATE CS 2013 Q.39 (CS Q.39): Process Synchronization and Concurrency

A certain computation generates two arrays $a$ and $b$ such that $a[i]=f(i)$ for $0 \le i < n$ and $b[i] = g(a[i])$ for $0 \le 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]);
}                                    }

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

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

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

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

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

Official answer and solution

Official answer: C
From: Official GATE 2013 answer key

Solution

Identify the synchronization pattern needed to enforce strict alternation between process X computing array element a[i] and process Y consuming a[i] to compute b[i].

In this problem:

Process $X$ computes $a[i] = f(i)$ and then calls ExitX(R, S).
Process $Y$ calls EntryY(R, S) and then computes $b[i] = g(a[i])$ .
Semaphores $R$ and $S$ are both binary semaphores initialized to 0.
Array element $a[i]$ must be written by $X$ before it is read by $Y$ . Furthermore, $X$ must not overwrite $a[i]$ in the next iteration until $Y$ has finished consuming it.

Let us analyze the implementations in option (C):

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

Tracing iteration $i = 0$ :

Initially, $R = 0, S = 0$ .
Process $X$ begins and computes $a[0] = f(0)$ . Then $X$ calls ExitX, where it executes P(S). Since $S = 0$ , process $X$ blocks.
Process $Y$ calls EntryY and executes V(S). This increments $S$ and wakes up process $X$ .
Process $Y$ then executes P(R). Since $R = 0$ , process $Y$ blocks waiting for data to be ready.
Process $X$ continues and executes V(R), signaling that $a[0]$ is ready. This unblocks process $Y$ .
Process $X$ advances to the next iteration $i = 1$ , computes $a[1]$ , and calls ExitX, blocking again on P(S).
Process $Y$ proceeds safely to read $a[0]$ and compute $b[0] = g(a[0])$ . When $Y$ advances to iteration $i = 1$ , it executes EntryY, signals V(S), and waits on P(R).

This handshaking pattern perfectly ensures strict alternation with no race conditions or deadlocks.

In contrast:

In option (A), $X$ executes P(R) and $Y$ executes P(S). Since both $R$ and $S$ start at 0, both processes block immediately, resulting in deadlock.
In option (B), both ExitX and EntryY do not synchronize the step-by-step lockstep consumption of each element.

Therefore, option (C) is the correct implementation.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 39 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source