5.4 Nested Monitors

Suppose that we did not wish to use condition synchronization directly in the implementation of the buffer monitor class but instead we decided to use two semaphores full and empty to reflect the state of the buffer. The semaphore empty counts the number of spaces and is decremented during a put operation. The put is, of course, blocked if the value of empty is zero. Similarly, full counts the number of items in the buffer and is decremented by a get operation. The get is therefore blocked if the value of full is zero. The modified buffer class is shown in Program 5.8.

Program 5.8: Buffer class using semaphores.

 class SemaBuffer<E> implements Buffer<E> {   protected E[] buf;   protected int in = 0;   protected int out= 0;   protected int count= 0;   protected int size;   Semaphore full; //counts number of items   Semaphore empty; //counts number of spaces   SemaBuffer(int size) {     this.size = size; buf = (E[])new Object[size];     full = new Semaphore(0);     empty= new Semaphore(size);   }   synchronized public void put(E o)               throws InterruptedException {     empty.down();     buf[in] = o;     ++count;     in=(in+1) % size;     full.up();   }   synchronized public E get()                throws InterruptedException{     full.down();     E o =buf[out];     buf[out]=null;     --count;     out=(out+1) % size;     empty.up();     return (o);   } }

The semaphores of Program 5.8 replace the count variable in the original implementation, the conditional waits on the value of count and the notification of changes in its value. An updated model to reflect the changes in the buffer implementation is shown below:

 const Max = 5 range Int = 0..Max SEMAPHORE(I=0) = SEMA[I], SEMA[v:Int]    = (up->SEMA[v+1]                  |when(v>0) down->SEMA[v-1]                  ). BUFFER = (put -> empty.down ->full.up ->BUFFER          |get -> full.down ->empty.up ->BUFFER          ). PRODUCER = (put -> PRODUCER). CONSUMER = (get -> CONSUMER). ||BOUNDEDBUFFER = (PRODUCER|| BUFFER || CONSUMER                   ||empty:SEMAPHORE(5)                   ||full:SEMAPHORE(0))@{put,get}.

A problem occurs when we check this model using the analyzer tool LTSA and find that it reports a potential deadlock together with a trace of actions to that deadlock:

 Composing  potential DEADLOCK States Composed: 28 Transitions: 32 in 60ms Trace to DEADLOCK:      get

We discuss deadlock in more detail in the next chapter. However, in essence, it means that a system can make no further progress since there are no further actions it can take. The deadlock in the model can be seen in the demonstration version of the program by starting the consumer and letting it block, waiting to get a character from the empty buffer. When the producer is started, it cannot put a character into the buffer. Why? The reason is to do with the use of two levels of synchronization lock: the first gives mutually exclusive access to the buffer monitor and the second gives mutually exclusive access to the semaphores.

When the consumer calls get, it acquires the Buffer monitor lock and then acquires the monitor lock for the full semaphore by calling full.down() to check if there is something in the buffer. Since initially the buffer is empty, the call to full.down() blocks the consumer thread (using wait()) and releases the monitor lock for the full semaphore. However, it does not release the monitor lock for Buffer. Consequently, the producer cannot enter the monitor to put a character into the buffer and so no progress can be made by either producer or consumer – hence the deadlock. The situation described above is known as the nested monitor problem. The only way to avoid it in Java is by careful design. In our example, the deadlock can be removed by ensuring that the monitor lock for the buffer is not acquired until after semaphores are decremented (Program 5.9).

Program 5.9: Fixed bounded buffer using semaphores.

 class FixedSemaBuffer<E> implements Buffer<E> {   protected E[] buf;   protected int in = 0;   protected int out= 0;   protected int count= 0; //only used for display purposes   protected int size;   Semaphore full;  //counts number of items   Semaphore empty; //counts number of spaces   FixedSemaBuffer(int size) {     this.size = size; buf = (E[])new Object[size];     full = new Semaphore(0);     empty= new Semaphore(size);   }   public void put(E o)              throws InterruptedException {     empty.down();     synchronized(this){       buf[in] = o; ++count; in=(in+1)%size;     }     full.up();   }   public E get()           throws InterruptedException{     full.down(); E o;     synchronized(this){       o =buf[out]; buf[out]=null;       --count; out=(out+1)%size;     }     empty.up();     return (o);   } }

As mentioned before, in this book we advocate the use of the model and analysis to aid in the process of “careful design”. Those parts of the model which need to be revised to take into account the changes to the buffer, documented in Program 5.9, are shown below:

 BUFFER = (put -> BUFFER          |get -> BUFFER          ). PRODUCER = (empty.down->put ->full.up ->PRODUCER). CONSUMER = (full.down ->get ->empty.up->CONSUMER).

Moving the semaphore actions from the buffer process to the producer and consumer processes reflects the change in the implementation where the semaphore actions are performed outside the monitor (i.e. before acquiring the monitor lock). If this modified model is composed and minimized, it generates an identical LTS to that depicted in Figure 5.12 for the original model. This gives us confidence that our revised semaphore implementation of the bounded buffer is equivalent to the original one which used wait() and notify() directly.