CIS 307: Implementing Hoare's Monitors

Monitors are treated very nicely in Tanenbaum section 2.2.7 and section 2.2.9. Here I show 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. In fact, though monitors were intended for use as language constructs when programming in languages such as Concurrent Pascal, or Concurrent Euclid, monitors, as an idea, can be used very conveniently in our concurrent programs written in C and using Unix system services.

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:

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