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

The process 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 solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal().

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

A multithreaded program P executes with x number of threads and used y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

Consider the following proposed solution for the critical section problem. There are n processes: P₀...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 Pi:

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?

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

Consider the procedure below for the Producer-Consumer problem which uses semaphores:

semaphore n=0;
semaphore s=1;
void producer()          void consumer()
{                        {
     while(true)              while(true)
     {                        {
     produce();               semWait(s);
     semWait(s);              semWait(n);
     addToBuffer();           removeFromBuffer();
     semSignal(s);            semSignal();
     semSignal(n);            consume();
     }                        }
}                         }

Which one of the following is TRUE?

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.

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.

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 is 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 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): 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 X_b and Y_b are respectively

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

  /* P1 */
while (true) {
  wants1 = true;
  while (wants2 == true);
  /* Critical
    Section */
  wants1=false;
}
/* Remainder section */       


/* P2 */
while (true) {
  wants2 = true;
  while (wants1==true);
  /* Critical
    Section */
  wants2 = false;
}
/* Remainder section */ 

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

The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore S.

void P (binary_semaphore *s)
{
    unsigned y;
    unsigned *x = &(s->value);
    do
    {
        fetch-and-set x, y;
    }
    while (y);
}
void V (binary_semaphore *s)
{
    S->value = 0;
}

Which one of the following is true?

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void) {
1:   P(S);
2:   process_arrived++;
3.   V(S);
4:   while (process_arrived !=3);
5:   P(S);
6:   process_left++;
7:   if (process_left==3) {
8:      process_arrived = 0;
9:      process_left = 0;
10:  }
11:  V(S);
}

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

The above implementation of barrier is incorrect. Which one of the following is true?

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void) {
1:   P(S);
2:   process_arrived++;
3.   V(S);
4:   while (process_arrived !=3);
5:   P(S);
6:   process_left++;
7:   if (process_left==3) {
8:      process_arrived = 0;
9:      process_left = 0;
10:  }
11:  V(S);
} 

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

Which one of the following rectifies the problem in the implementation?

Consider two processes P₁ and P₂ accessing the shared variables X and Y protected by two binary semaphores S_X and S_Y respectively, both initialized to 1. P and V denote the usual semaphone operators, where P decrements the semaphore value, and V increments the semaphore value. The pseudo-code of P₁ and P₂ is as follows:

P1 :
 While true do {
   L1 : ................
   L2 : ................
   X = X + 1;
   Y = Y - 1;
   V(SX);
   V(SY);             
 }
P2 :
 While true do {
   L3 : ................   
   L4 : ................
   Y = Y + 1;
   X = Y - 1;
   V(SY);
   V(SX);            
}

In order to avoid deadlock, the correct operators at L₁, L₂, L₃ and L₄ are respectively

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P:
while (1) {
W:
   print '0';
   print '0';
X:
}
	
Process Q:
while (1) {
Y:
   print '1';
   print '1';
Z:
}

Synchronization statements can be inserted only at points W, X, Y and Z.

Which of the following will always lead to an output staring with '001100110011'?