GATE Questions & Answers of Inter-Process Communication, Concurrency and Synchronization

The following C program is executed on a Unix/Linux system:

#include <unistd.h>

int main()

{

int i;

for (i=0; i<10; i++)

if (i%2 == 0) fork();

return 0;

}

The total number of child processes created is ________. 

Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.

The processes are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y – X is _____________.

Consider the following snapshot of a system running n concurrent processes. Process i is holding X_i instances of a resource R, $ 1\leq i\leq n. $ Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Y_i additional instances of R while holding the X_i instances it already has. Of the n processes, there are exactly two processes p and q such that Y_p = Y_q = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?

•  (A)  $ X_p+X_q\;<\;\mathrm{Min}\;\{Y_k\vert1\leq k\leq n,\;\mathrm k\neq\mathrm p,\;\mathrm k\neq\mathrm q\} $
•  (B)  $ X_p+X_q\;<\;\mathrm{Max}\;\{Y_k\vert1\leq k\leq n,\;\mathrm k\neq\mathrm p,\;\mathrm k\neq\mathrm q\} $
•  (C)  $ \mathrm{Min}\;(X_p,\;X_q)\;\geq\;\mathrm{Min}\;\{Y_k\vert1\leq k\leq n,\;\mathrm k\neq\mathrm p,\;\mathrm k\neq\mathrm q\} $
•  (D)  $ \mathrm{Min}\;(X_p,\;X_q)\;\leq\;\mathrm{Max}\;\{Y_k\vert1\leq k\leq n,\;\mathrm k\neq\mathrm p,\;\mathrm k\neq\mathrm q\} $

Which one of the following assignments to P, Q, R and S will yield the correct solution?

•  (A) P: full, Q: full, R: empty, S: empty
•  (B) P: empty, Q: empty, R: full, S: full
•  (C) P: full, Q: empty, R: empty, S: full
•  (D) P: empty, Q: full, R: full, S: empty

Consider the following proposed solution for the critical section problem. There are $n$ processes: $ P_0\;...\;P_{n-1}\;. $ In the code, function pmax returns an integer not smaller than any of its arguments. For all $i$, t[i] is initialized to zero.

Code for $P_i:$
do {
      c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0;
     for every j≠i in {0,...,n-1} {

         while (c[j]);
         while (t[j] != 0 && t[j]<=t[i]);
     }
     Critical Section;
     t[i]=0;
      Remainder Section;
} while (true);

Which one of the following is TRUE about the above solution?

•  (A)  At most one process can be in the critical section at any time
•  (B)  The bounded wait condition is satisfied
•  (C)  The progress condition is satisfied
•  (D)  It cannot cause a deadlock

•  (A)  This is a correct two-process synchronization solution.
•  (B)  This solution violates mutual exclusion requirement.
•  (C)  This solution violates progress requirement.
•  (D)  This solution violates bounded wait requirement.

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ______.

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

The number of distinct values that B can possibly take after the execution is__________.

A variable x is said to be live at a statement S_i in a program if the following three conditions hold simultaneously:
i. There exists a statement S_j that uses x
ii. There is a path from S_i to S_j in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at S_i and S_j

The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are

•  (A)  p, s, u
•  (B)  r, s, u
•  (C)  r, u
•  (D)  q, v

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process  X  executes the P operation (i.e., wait) on semaphores  a , b and c; process Y executes the P operat ion on semaphore s b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

•  (A) X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)
•  (B) X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)
•  (C) X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)
•  (D) X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?

•  (A) –2
•  (B) –1
•  (C) 1
•  (D) 2

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  compu tes the array a and  Y  computes the array b. T he processes employ two binary  semaphores  R  and S, both initi alized to zero. The array a is shared by the two processes. The structures of the processes are shown below.

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

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.

AcquireLock(L){
          while (Fetch_And_Add(L,1))
                  L = 1;
}
ReleaseLock(L){
          L = 0;
}

This implementation

•  (A) fails as L can overflow
•  (B) fails as L can take on a non-zero value when the lock is actually available
•  (C) works correctly but may starve some processes
•  (D) works correctly without starvation

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared Boolean variables S1 and S2 are randomly assigned.

Which one of the following statements describes the properties achieved?

•  (A) Mutual exclusion but not progress
•  (B) Progress but not mutual exclusion
•  (C) Neither mutual exclusion nor progress
•  (D) Both mutual exclusion and progress

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.

How many times will process P0 print ‘0’?

•  (A) At least twice
•  (B) Exactly twice
•  (C) Exactly thrice
•  (D) Exactly once

The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:

void enter_CS(X)
{
             while (test-and-set(X)) ;
}
void leave_CS(X)
{
             X=0;
}

In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:

I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV. More than one process can enter CS at the same time.

Which of the above statements are TRUE?

•  (A) I only
•  (B) I and II
•  (C) II and III
•  (D) IV only

The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:
P(s) : s = s - 1;
      if s < 0 then wait;
V(s) : s = s + 1;
     if s <= 0 then wakeup a process waiting on s;
Assume that P_b and V_b the wait and signal operations on binary semaphores are provided. Two binary semaphores x_b and y_b are used to implement the semaphore operations P(s) and V(s) as follows:

P(s) : P_b (x_b);
       s = s -1;
       if (s < 0) {
         V_b (x_b);
         P_b (y_b);
       }
       else V_b (x_b);
V(s) : P_b (x_b);
       s = s + 1;
       if (s <=0) V_b (y_b);
         V_b (x_b);

The initial values of x_b and y_b are respectively

•  (A) 0 and 0
•  (B) 0 and 1
•  (C) 1 and 0
•  (D) 1 and 1

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?

•  (A)   It does not ensure mutual exclusion.
•  (B)   It does not ensure bounded waiting.
•  (C)   It requires that processes enter the critical section in strict alternation.
•  (D)   It does not prevent deadlocks, but ensures mutual exclusion.