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

Consider the following proposed solution for the critical section problem. There are n processes: P0...Pn−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 6= 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?

Consider the following two-process synchronization solution.
Process 0   Process 1
---------   ----------
Entry: loop while (turn == 1);   Entry: loop while (turn == 0);
(critical section)   (critical section)
Exit: turn = 1;   Exit: turn = 0;

 

The shared variable turn is initialized to zero. Which one of the following is TRUE?

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.

P1(){
    C=B-1;
    B=2*c;
}
     P2(){
     D=2*B;
     B=D-1;
}

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 Si in a program if the following three conditions hold simultaneously:
i. There exists a statement Sj that uses x
ii. There is a path from Si to Sj in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at Si and Sj

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

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 operation on semaphores 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 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 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?

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

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.

Method used by PI Method used by P2
while (S1 = = S2) ;
Critical Section
S1 = S2;
while (S1 != S2) ;
 Critical section
 S2 = not (S1);

Which one of the following statements describes the properties achieved?

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

Process P0 Process P1 Process P2
 while (true) {
    wait (S0);
    print ‘0’
    release (S1);
    release (S2);
 }
 wait (S1);
 Release (S0);
 wait (S2);
 release (S0);

How many times will process P0 print ‘0’?

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?

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 Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores xb and yb are used to implement the semaphore operations P(s) and V(s) as follows:


P(s) : Pb (xb);
       s = s -1;
       if (s < 0) {
         Vb (xb);
         Pb (yb);
       }
       else Vb (xb);
V(s) : Pb (xb);
       s = s + 1;
       if (s <=0) Vb (yb);
         Vb (xb);

The initial values of xb and yb are respectively

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?