CIS 4307: Monitors

Monitors

A Monitor is an abstract data type, i.e. a combination of data structures and operations, where at most one operation may be executing at one time. The required mutual exclusions are enforced by the compiler implementing the monitor.
Within a monitor it is possible to use a special kind of blocking semaphore, called a condition. Its operations are usually called wait for P, and signal for V. We will see later how conditions can be implemented. For now it suffices to know that the signal operation acts as a null operation in the case that no process is waiting on the condition.

Monitors were introduced to simplify the writing of concurrent programs since the direct use of spinlocks and semaphores results in programs that are hard to write correctly. Monitors are directly supported by languages such as Concurrent Pascal, Concurrent Euclid, Ada95. They are supported, in a simplified form, in Java[each object is a monitor with an implicit condition variable so that within the synchronized methods of the object one can use the methods wait, notify, and notifyAll]. Monitors, as a programming style, can be implemented in concurrent programs written in C using Unix system services with or even without threads [use processes, shared memory, and some form of semaphore].

Here is how we can write the Protected Bounded Buffer (it can be used to solve the Producers and Consumers problem) as a monitor:


Monitor PBBuffer
  b : BBuffer;  // This is an unprotected bounded buffer
  count : Integer;
  empty, full : condition;
procedure Init;
begin
  init(empty); init(full); init(b); count := 0;
end;
procedure Enqueue(I : Item)
begin
  if count == BufferSize(b) then wait(full);
  //BufferSize returns the maximum size of b
  count++;
  Enqueue(b, I);
  signal(empty);
end;
procedure Dequeue(I : out Item)
begin
  if count == 0 then wait(empty);
  count--;
  Dequeue(b, I);
  signal(full);
end;

Here is a monitor solution for the Dining Philosophers Problem [this solution is not fair]:


Monitor DiningPhilosophers
  HMNY  : constant integer = {the number of philosophers};
  HMNY1 : constant integer = HMNY - 1;
  state : array[0 .. HMNY1] of (thinking, hungry, eating) 
                            = (thinking, .., thinking);
  self  : array[0 .. HMNY] of condition; {We assume self's conditions 
                            are initialized}
function Left(K : 0 .. HMNY1) return 0 .. HMNY1 is
{This is an operation only used within the monitor}
begin
  return (K+1) mod HMNY;
end;
function Right(K : 0 .. HMNY1) return 0 .. HMNY1 is
{This is an operation only used within the monitor}
begin
  return (K-1) mod HMNY;
end;
procedure Test(K : 0 .. HMN1)
{This is an operation only used within the monitor}
begin
  if state[Left(K)] /= eating and
     state[K] == hungry and
     state[Right(K)] /= eating then {
     state[K] = eating;
     signal(self[K]); }
end;
procedure Pickup(I : 0 .. HMNY1)
begin
  state[I] = hungry;
  Test(I);
  if state[I] /= eating then wait(self[I]);
end;
procedure PutDown(I : 0 .. HMNY1)
begin
  state[I] = thinking;
  Test(Left(I));
  Test(Right(I));
end;

Each philosopher Pi will execute a simple loop:

  loop
    think;
    DiningPhilosophers.PickUp(i);
    eat;
    DiningPhilosophers.PutDown(i);
  forever;

Like most things also monitors are not perfect. For example it is easy to get into deadlocks if a monitor calls on another monitor. Suppose we have a PBBuffer and we write another monitor Moo with two operations Insert and Remove. Among other things, Insert calls on PBBuffer.Enqueue and Remove calls on PBBuffer.Dequeue. Now process A keeps on calling Moo.Insert until the buffer fills up. Then A calls Moo.Insert again. At this point A will be inside of Moo since the buffer is full. Another process B now calls Moo.Remove. It cannot enter Moo since A is inside of Moo. In turn A cannot progress until B (or somebody else, but we assume that nobody else is around) removes things from the buffer. Deadlock.

Implementing Monitors

Here we see the implementation of monitors using semaphores in the case that the Signal command can be applied anytime within the monitor, not just, as in the Brinch Hansen implementation for monitors, only when exiting monitor operations. It is a variation of the Hoare implementation and is close to the way that monitors behave in Posix threads.

Most of the code we present is modified from code in Silberschatz et al: Operating Systems Concepts.

We want to show how to implement a monitor using semaphores.

Global variables
- mutex: Semaphore initialized to 1; It is used to control the number of processes allowed in the monitor.
- next: Semaphore initialized to 0; it is used as a waiting queue by processes that are in the monitor after being released from a condition's queue by a signal operation.
- next_count: integer variable initialized to 0; It counts the number of processes sleeping in the next semaphore. It is always equal to the number of processes executing monitor operations, minus 1. [This is a complex way of saying that only one process at one time can be actively executing within a monitor operation, this process is called the active process. The processes waiting on next are the inactive processes]
Prologue Code executed when starting execution of a monitor's operation:
```
	P(mutex);
```
Epilogue Code executed when ending execution of a monitor's operation:
```
	if next_count > 0 then V(next) else V(mutex);
```

Implementation of Condition variables as instances of the abstract data type, or class, Condition:

	Abstract Data Type condition is
           count   : integer initialized to 0;
           queue   : semaphore initialized to 0 (i.e. blocking);
	procedure wait (x : in out condition) is
	begin
	   x.count++;
	   if next_count > 0 then V(next) else V(mutex);
	   P(x.queue);
           P(next); 
           next_count--;
	end;
	procedure signal (x : in out condition) is
	begin
	   if x.count > 0 then 
	   begin
		x.count--;
		next_count++;
		V(x.queue);
	   end;
	end;

Notes

A Monitor is not a process, not an active entity. It is just an abstract data type, or class, whose code can be executed by only one process at a time.
Let's notice that next_count is only modified within Condition operations. Thus if we do not use condition variables, the prologue code and epilogue code just make sure that only one process is executing within the monitor.
When condition variables are used within monitor procedures, they are used only to allow processes that do not want to continue at this point, to get out of the way to allow other processes to run. These processes will sleep in the semaphore next; next_count keeps track of their number.
The wait operation on conditions always puts to sleep the process that executes it. But before going to sleep, the current process either wakes up a process waiting in the next semaphore or, if next was empty, opens the mutex semaphore to allow some other process to enter from the outside. Notice that the wait operation puts to sleep the active process and gives precedence to the processes that are sleeping within the monitor over the processes that are trying to enter the monitor.
When the process that executed the wait and fell asleep on the condition variable is finally awaken by a signal, to avoid having two processes active within the monitor, it has to go to sleep on next, to be awaken then by a process that ceases to be active in the monitor.
The signal operation on condition variables is null if there is no process currently waiting on that condition.
The code for the Wait and Signal operations of Conditions, and for the Epilogue code, need not be protected as critical regions because only one process is executing in the monitor at a time.
If a process A executes the signal operation on a condition variable, and if a process B is the highest priority process waiting on this condition, then B moves to the next semaphore and A continues in Running state.
One might think that by moving the lines "x.count--; next_count++;" from before the "V(x.queue);" statement in signal to after the "P(x.queue);" statement in wait, one would get an equivalent program. That is not the case. Think of what happens if the thread executing signal continues out of the monitor before the thread executing wait has had time to increment next_count.

Within the monitor (intermediate) scheduling takes place. We are with three (semaphore) queues:

The mutex queue, where processes waiting to enter the monitor wait
The next queue, where processes that are within the monitor and ready, wait to become the active process, and
The condition queue(s), where a blocked process waits to be signaled.

In this implementation the active process is given precedence over the processes that are coming out of the condition queue; processes in the next queue take precedence over processes in the mutex queue [this is a form of FIFO scheduling].