G52CON 2008-2009: Solution to Exercise 2, Semaphores

Questions:

1. devise a semaphore solution to the multiple Producer-multiple Consumer problem using a bounded buffer which ensures that:
   • data items are not overwritten before they are read;
   • data items are read only once;
   • no data items are read from an empty buffer;
   • items are consumed in the order they are produced; and
   • all items produced are eventually consumed.

2. does your solution satisfy the properties of Mutual Exclusion, Absence of Deadlock, Absence of Unnecessary Delay and Eventual Entry?
3. how many classes of critical sections does your solution have?

Model Solution:

1. 
   // Producer process i                       // Consumer Process j
   Object x = null;                            Object y = null;
   while(true) {                               while(true) {
       // produce data x ...                       P(full);
                                                   P(mutexC);
       P(empty);                                   y = buf[out];
       P(mutexP);                                  out = (out + 1) % n;
       buf[in] = x;                                V(mutexC);
       in = (in  + 1) % n;                         V(empty)
       V(mutexP);                                  // use the data y ...
       V(full);
   }                                           }
   
                       // Shared variables
                       integer n = BUFFER_SIZE, in = 0, out =0;
                       Object[] buf = new Object[n];
                       general semaphore empty = n, full = 0;
                       binary semaphore mutexP = 1, mutexC = 1;
   

   In this case the problem is to ensure that two different producers don't attempt to append items to the buffer at the same time, as this can result in both items being put in the same slot. This can happen if both assign to buf[in] before either increments in (see Lecture 2). Similarly, we must ensure that two different consumers don't attempt to remove the same item, if both copy the same item into y before either increments out. Both appending and removing items become critical sections. Both operations must be executed with mutual exclusion with respect to other producers (for append) and consumers (for remove), but one producer and one consumer can execute concurrently with one another, since the empty and full semaphores already ensure that the producer and consumer can't access the same slot. The solution is similar to the semaphore solution to the single Producer-single Consumer problem using a bounded buffer presented in lecture 8, with additional binary semaphores to protect each critical section (see Lecture 7).

2. The solution satisfies Mutual Exclusion, Absence of Deadlock and Absence of Unnecessary Delay. However Eventual Entry is true only if the semaphores are fair (see Lecture 7).

3. There are two classes of critical sections. Recall that a critical section is a section of code belonging to a process that access shared variables, where, to ensure correct behaviour, the critical section must be given mutually exclusive access to the shared variables (see Lecture 2). Both a producer and a consumer can access the buffer at the same time, so long as the condition synchronisation conditions are met. For example, a producer could be writing an item into one end of the buffer, while a consumer is reading an item from the other end of the buffer. However no more than one producer or one consumer may access the buffer at the same time. Both appending and removing items are critical sections: both operations must be executed with mutual exclusion with respect to other producers (for append) and consumers (for remove).