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.]
- 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 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.
- 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.
ingargiola.cis.temple.edu