Monitors

In this section we present






Example: Bounded Buffer in a Hoare Monitor 

 





 
 

 boundedbuffer monitor

begin buffer:array 0..n-1of portion;

      lastpointer: 0..n-1;

      count: 0..n;

      nonempty,nonfull: condition;

 

 procedure append(x:portion);

   begin if count=n then nonfull.wait; {note: 0<=count<n}

                     buffer[lastpointer] := x;

                     lastpointer:= (lastpointer + 1) mod n;

                      count:=count+1;

           nonempty.signal;

   end append;

 

   procedure remove(result x:portion);

   begin if count=0 then nonempty.wait;

             {note:0 <count<or=n}

              x:=buffer[(lastpointer-1)mod n];

              count:=count-1;

              nonfull.signal;

   end remove;

 {initialization section}

 count:=0; lastpointer:=0;

 end boundedbuffer;

 








Example: Building a Semaphore with a Monitor

SingleResource: monitor;

begin busy: boolean;

 nonbusy: condition;

 procedure acquire;

    begin if busy then {note: resource is busy} nonbusy.wait;

    {note: resource is free} busy:= true;

    end

 procedure release;

    begin {note: resource is busy} busy := false;

  {note: resource is free} nonbusy.signal;

    end

 {initialization section}

 busy := false;

end SingleResource;

 






Example: Alarm Clock (Hoare) Monitor

·         Each process that wants to wait for a specific amount of time will call alarmclock.wakeme(time) and the alarmclock will awaken it at current time + time.

·         A hardware clock will call alarmclock.tick each time it is updated

·         Skeleton Code:

 

 alarmclock: monitor;

 begin now: integer;   {now is current time}

           condition;  { condition variable ordered FIFO within priority}

 procedure wakeme(n:integer);

    begin alarmsetting:integer;

    alarmsetting := now + n;

    while now < alarmsetting do wakeup.wait(alarmsetting);

 {note that "alarmsetting" is the priority of this process}

    wakeup.signal; {in case more than one process at this time}

 end;

 procedure tick;

    begin now := now+1;

               wakeup.signal;

    end;

 {initialization section}

 

 now := 0;

 

 end alarmclock;

 






Implementing Hoare's Monitor with Semaphores

·         Each method (entry) must have a gatekeeper which prevents a process from entering the monitor if it is currently occupied. This is accomplished by queueing it (1) on a "mutex" semaphore.

·         When a process executes a "wait(condvar)" (2), it is queued on a "condvar" semaphore.

·         On execution of a "signal(condvar)" (3), a process is released from the "condvar" semaphore and added to the "ready list" of the OS scheduler. The executing process is then queued on an "urgent" semaphore.

·         On execution of an exit from a method (4), if there are no processes waiting on the "urgent" semaphore, the gatekeeper opens the gate "mutex" so waiting processes can enter the monitor

Implementing Hoare's Monitor with Semaphores

We will use three semaphores - mutex, condsem, and urgent. "mutex" will protect the monitor entries (methods); "condsem" will keep track of processes waiting on this condition; "urgent" will hold those processes which have issued "signals" from within the monitor and are waiting to get back into the monitor, since the process which was "signaled" has highest priority for the monitor. 

 
 
  
entry: P(mutex);
exit: if urgentcount > 0 then V(urgent) else V(mutex)
cond.wait:

 condcount := condcount + 1;

 if urgentcount > 0 then V(urgent) else V(mutex)

P(condsem); condcount := condcount +1;

  
cond.signal

 urgentcount := urgentcount + 1;

 if condcount > 0 then {V(condsem);P(urgent)}

 urgentcount := urgentcount - 1;



Example: Readers and Writers using Kessels' Monitor

·         In the Kessels' monitor concept, a relational expression is associated with the condition variables.

·         Each time execution of "wait condvar" evaluates the expression and waits until the expression is true before proceeding.

·         In this example, processes wish to "read" or "write" shared data. Writers must operate in a mutually exclusive manner, while readers can execute in parallel on the shared data. Writers must also exclude readers. Monitors can be used to implement "startread", "endread", "startwrite", and "endwrite" methods.

 

 

Reader:                           Writer:

-     -

-     -

readerwriter.startread    readerwrite.startwrite

read data                 write data

readerwriter.endread      readerwriter.endwrite

-     -

-     -

end                       end

 

 

readerwriter monitor

begin readercount, writercount: integer;

 writerbusy: boolean;

 readallowed: condition writercount = 0;

writeallowed: condition readercount =0 and not writerbusy;

procedure startread;

begin wait readallowed;

 readercount:=readercount + 1;

end;

procedure endread;

begin readercount := readercount -1 end;

procedure startwrite;

 

begin writercount := writercount + 1;

 wait writeallowed;

 writerbusy := true;

end;

procedure endwrite;

begin writerbusy := false; writercount := writercount - 1; end;

{initialization section}

readercount := 0; writercount := 0; writerbusy := false;

end

Example: Simple Buffer Allocator Monitor with Kessels' Conditions

·         Processes which form a pipeline each acquire buffers from a common pool before filling the buffer and placing it in the next stream, which interconnects the processes in the pipeline.

·         The "bufferallocator" monitor must prevent one process from being starved of buffers, or the entire pipeline will deadlock.

·         Conditions for granting acquire: count[i] < minclaim[i] or common > 0

where: common = Nb - sum(j)max(minclaim[j], count[j])

·         "Nb" is total number of buffers available and "count[j]" is the current number of buffers held by process j.

·         Each process i is guaranteed "minclaim[i]" number of buffers to guarantee it can make progress.

·         Processes then release buffers back to the monitor for use by other processes.



bufferallocator: monitor 

 

begin type stream = 1..Np; {number of streams}

    buffer := 1..Nb; {number of buffers}

    common: integer;

    freepool: powerset buffer;

    streaminfo: array stream of

          record count, minclaim: integer;

                      goon: condition count < minclaim or common > 0;

           end;

procedure acquire(result b: buffer; s:stream);

begin with streaminfo[s] do

   begin wait goon;

   count := count + 1;

   if count > minclaim then common := common - 1;

   b := first(freepool);

   freepool := freepool - {b};

end end;

 

procedure release (b: buffer; s: stream);

begin with streaminfo[s] do

   begin if count > minclaim then common := common +1;

             count := count - 1;

             freepool := freepool + {b};

end end;

freepool := all buffers; common:= Nb;

for s: stream do with streaminfo[s] do

                           begin count:= 0;

                              read(minclaim);

                              common := common - minclaim

                           end

end 

 




Implementing Kessel's Monitor with Semaphores

·         Use a boolean function "B", a semaphore "sem", and an integer "wp" to count processes to implement a condition.

·         Use three arrays, "B", "sem", and "wp". sem[0] is used as "mutex".

·         Assume "get[n]" which returns

·         n=0, if none true or n=i if "i" is first true

·         Formally, true{get(n)} (n>0 => B[n] and wp[n] > 0)

·         Initial Conditions

sem[0] = 1

sem[i] = 0, 1<=i<=N

wp[i] = 0, 1<=i<=N

·         Implementation

·         entry: p(sem[0]);

·         wait(i):

  if not B[i] then

   {wp[i] := wp[i] + 1;

   get(next);

   v(sem[next]);

   p(sem[i]);

   wp[i] := wp[i] -1;}

  
exit: get(next);
 v(sem[next]);

 

Monitors in Java

·         Java supports objects with methods or code blocks which can be synchronized.

·         Any method or code block marked as "synchronized" is executed in a mutually exclusive fashion (one thread at a time).

·         Java provides "wait" and "notify" as synchronizing primitives (similar to "wait" and "signal" in Hoare's monitor).

·         However, only one "lock" per object is provided (whereas Hoare permits declaration of any number of condition variables).

·         Thus, "wait" suspends the executing thread on the hidden object lock and releases the monitor.

·         "notify" releases one (arbitrary) thread from the object lock to execute in the monitor.

·         "notifyAll" releases all of the threads from the internal object lock.

·         Java also provides an interface specification.

·         Java monitors are re-entrant.




Example: Bounded Buffer in Java

public interface BoundedBuffer {

   public int capacity(); //invariant: 0 <= capacity

   public int count();     //invariant: 0 <= count <= capacity

   public void put(Object x); //add only when count < capacity

   public Object take(); //remove only when count > 0

}

public class BoundedBufferVST implements BoundedBuffer {

   protected Object[] array_;    //the elements

   protected int putPtr_ = 0;     //circular indices

   protected int takePtr_ = 0;

   protected int usedSlots_ = 0; //the count

  public BoundedBufferVST(int capacity)

    throws IllegalArgumentException {

     if (capacity <= 0)

       throw new IllegalArgumentException()

     array_ = new Object[capacity];

   }

   public int count() {

     return usedSlots_;

   }

   public int capacity() {

     return array_.length;

   }

   public synchronized void put(Object x) {

     while (usedSlots_ = = array_.length) //wait until not full

        try {wait(); } catch(InterruptedException ex) {};

      array_[putPtr_] = x;

      putPtr_ = (putPtr_ +1) % array_.length; //cyclically increment

      if (usedSlots_++ == 0) //signal if it was empty

        notifyAll();

   }

   public synchronized Object take() {

   while (usedSlots_ == 0) //wait until not empty

     Try { wait(); } catch(InterruptedException ex) {};

   Object x = array_[takePtr_];

   array_[takePtr_] = null;

   takePtr_ = (takePtr_ + 1 ) % array_.length;

   if (usedSlots_-- == array_.length) //signal if it was full

     notifyAll();

   Return x;

   }

}