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?

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

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 _______.

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.

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?

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

A critical region is