Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

wait (a); count = count+1;
if (count==n) signal (b);
signal (a); wait (b); signal (b);

What does the code achieve?

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

The concurrent programming constructs fork and join are as below:
fork which creates a new process executing from the specified label
join which decrements the specified synchronization variable (by 1) and terminates the process if the new value is not 0.
Show the precedence graph for S1, S2, S3, S4, and S5 of the concurrent program below.

   N = 2
   M = 2
   fork L3
   fork L4
   S1
L1:join N
   S3
L2:join M
   S5
L3:S2
   goto L1
L4:S4
   goto L2
next: 

A critical section is a program segment

Each Process P_i, i = 1.......9 is coded as follows

    repeat 
           P(mutex)
           {Critical section}
           V(mutex)
    forever   

The code for P₁₀ is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

A counting semaphore was initialized to 10. Then 6P (wait) operations and 4V (signal) operations were completed on this semaphore. The resulting value of the semaphore is

When  the  result  of  a  computation  depends  on  the  speed  of  the  processes involved there is said to be

(a) A certain processor provides a 'test and set' instruction that is used as follows:

 TEST register, flag 

This instruction atomically copies flag to register and sets flag to 1. Give pseudo-code for implementing the entry and exit code to a critical region using this instruction.

(b) Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of count and assignment to count are atomic operations.

            Producer:      
                Repeat 
                         Produce an item;
                         if count = 1 then sleep;
                         place item in buffer.
                         Count = 1;
                         Wakeup(Consumer);
               Forever 

            Consumer:
               Repeat
                         if count = 0 then sleep;
                         Remove item from buffer;
                         Count = 0;
                         Wakeup(Producer);
                         Consume item;
              Forever; 

Show that in this solution it is possible that both the processes are sleeping at the same time.

(a) Fill in the boxes below to get a solution for the readers-writers problem, using a single binary semaphore, mutex (initialized to 1) and busy waiting. Write the box numbers (1, 2 and 3), and their contents in your answer book.

     int R = 0, W = 0;
     Reader () {
 L1:        wait (mutex);
            If (W ==0) {
                R = R +1; 
                ▭______(1)
     }
     else {
                ▭______(2)
                goto L1;
                }
                …./* do the read */
                wait (mutex)
                R = R – 1;
                signal (mutex);
          }
          Writer () {
 L2:            wait(mutex);
                If (▭) {______(3)
                    signal (mutex);
                    goto L2;
                }
                W=1;
                signal (mutex);
                …./*do the write*/
                wait(mutex)
                W = 0;
                signal (mutex); 

(b) Can the above solution lead to starvation of writers?

Let m[0] … m[4] be mutexes (binary semaphores) and P[0] … P[4] be processes. Suppose each process P[i] executes the following:

  wait (m[i]); wait(m[(i+1) mode 4]);
  ------
  release (m[i]); release (m[(i+1)mod 4]);

This could cause:

Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

   repeat   
      flag[i] = true; 
      turn = j; 
      while (P) do no-op; 
      Enter critical section, perform actions, then exit critical 
      section 
      flag[i] = false; 
      Perform other non-critical section actions. 
   until false; 

For the program to guarantee mutual exclusion, the predicate P in the while loop should be.

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'?

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 ensure that the output string never contains a substring of the form 01ⁿ0 or 10ⁿ1 where n is odd?

The wait and signal operations of a monitor are implemented using semaphores as follows. In the following,
x is a condition variable,
mutex is a semaphore initialized to 1,
x_sem is a semaphore initialized to 0,
x_count is the number of processes waiting on semaphore x_sem, initially 0, next is a semaphore initialized to 0,
next_count is the number of processes waiting on semaphore next, initially 0.
The body of each procedure that is visible outside the monitor is replaced with the following:

P(mutex); 
      ⋮
body of procedure 
      ⋮
if (next_count > 0)
    V(next);
else
    V(mutex); 

x_count = x_count + 1;
if (next_count > 0)
    V(next)
else
    V(mutex);
------------------------------------------------------------ E1;
x_count = x_count - 1; 

if (x_count > 0)
{
    next_count = next_count + 1;
    ------------------- E2;
    P(next),
    next_count = next_count - 1;
} 

Consider the solution to the bounded buffer producer/consumer problem by using general semaphores S, F, and E. The semaphore S is the mutual exclusion semaphore initialized to 1. The semaphore F corresponds to the number of free slots in the buffer and is initialized to N. The semaphore E corresponds to the number of elements in the buffer and is initialized to 0.

Producer Process                Consumer Process
Produce an item;                Wait(E);
Wait(F);                        Wait(S);
Wait(S);
Append the items to the buffer; Signal(S);
Signal(S);                      Signal(F);
Signal(E);                      Consume the item;

Which of the following interchange operations may result in a deadlock? 1. Interchanging Wait (F) and Wait (S) in the Producer process 2. Interchanging Signal (S) and Signal (F) in the Consumer process

Synchronization in the classical readers and writers problem can be achieved through use of semaphores. In the following incomplete code for readers-writers problem, two binary semaphores mutex and wrt are used to obtain synchronization

wait (wrt)
writing is performed
signal (wrt)
wait (mutex)  
  readcount = readcount + 1
  if readcount = 1 then S1
S2
reading is performed
S3
  readcount = readcount - 1
  if readcount = 0 then S4 
signal (mutex) 

The values of S1, S2, S3, S4, (in that order) are

Processes P1 and P2 use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program.

        get_exclusive_access ( ) 
{ 
  if (critical _flag == FALSE) { 
      critical_flag = TRUE ; 
      critical_region () ; 
      critical_flag = FALSE; 
      } 
}

Consider the following statements. i. It is possible for both P1 and P2 to access critical_region concurrently. ii. This may lead to a deadlock.

Which of the following holds?

The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores equipped with the standard P and V operations.

semaphore S = 1, Q = 0; 
integer x; 
producer:                            consumer:
while(true) do                      while(true) do 
     P(S);                               P(Q); 
     x = produce ();                     consume (x); 
     V(Q);                               V(S); 
done                                done