CIS 307: Monitors

[Monitors], [Implementing Hoare's Monitors]

Monitors

Monitors are treated very nicely in Tanenbaum section 2.2.7 and section 2.2.9. Here we summarize this topic.
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 implementation of the monitor.
Within a monitor it is possible to use a special kind of blocking semaphore, called a conditon. 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 tended to result in programs that were hard to write correctly. Though monitors were intended for use as language constructs when programming in languages such as Concurrent Pascal, or Concurrent Euclid, and now in Ada95 and, in a simplified form, in Java, monitors, as an idea, can be used very conveniently in our concurrent programs written in C and using Unix system services.

Here is how we can write the Protected Bounded Buffer as a monitor:


Monitor PBBuffer
  b : BBuffer;
  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 then wait(full);
  count++;
  Enqueue(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;
    DP.PickUp(i);
    eat;
    DP.PutDown(i);
  forever;

Implementing Hoare's 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 Tanenbaum, when exiting monitor calls. That is, while Tanenbaum shows the Brinch Hansen implementation for monitors, here we examine the Hoare implementation. This latter implementation is less restrictive and less efficient. It is interesting as an example of complex concurrent program and it is useful if you want to use monitors in your programs.

Most of the code we present appears 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 and want to allow other processes to run in the monitor.
- 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 executing within a monitor operation, this process is called the active process.]

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;
	procedure wait (x : in out condition) is
	begin
	   x.count++;
	   if next_count > 0 then V(next) else V(mutex);
	   P(x.queue);
	   x.count--;
	end;
	procedure signal (x : in out condition) is
	begin
	   if x.count > 0 then begin
	      next_count++;
	      V(x.queue);
	      P(next);
	      next_count--;
	   end;
	end;

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);
```

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 turn and 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 withing the monitor over the processes that are trying to enter 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 A moves to Ready state and B to Running state. That is, B has priority over A.
We could have implemented the signal operation so that A has priority on B until A exits the monitor.

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 the implementation we have shown processes that are coming out of the condition queue take precedence over the active process and over the next queue; in turn processes in the next queue take precedence over processes on the mutex queue. These decisions are based on some FIFO ideas, but alternative decisions could be made.

ingargiola.cis.temple.edu