UNDER CONSTRUCTION!

Monitors

Semaphores are like goto's and pointers: mistake prone, work okay but lack structure and ``discipline''.

For example, a disastrous typo: 

  V(S)
    critical section
  V(S)
This leads to deadlock: 
  P(S)
    critical section
  P(S)

Nested critical sections can lead to deadlock: 

  P1                  P2
  --                  --

    P(Q)                P(S)
    P(S)                P(Q)
    ...                 ...
    V(S)                V(Q)
    V(Q)                V(S)

Monitors are

Monitor, interface routines, condition variables, queues.

Monitors can be visualized as:

PostScript and Ascii alternatives

only one process at a time is allowed ``inside'' the monitor where ``inside'' means a call of an operation in the monitor is in progress or accepted

Two ``life simplifying'' assumptions regarding condition variables

  1. the signaler must exit the monitor immediately after signaling by executing a return statement so that nothing can change before the signaled process wakes up

  2. the signaled process is given priority to proceed inside the monitor over those processes waiting to enter the monitor through an operation call so that in this way the signaled process finds the condition still true when it resumes
This is called the signal and exit signaling discipline. We will look at another signaling discipline, signal and continue, later.

Monitors can be implemented with semaphores: 

                       semaphore mutex := 1

  monitor operation 1        .......      monitor operation n
    P(mutex)                                P(mutex)
      ...                                     ...
    V(mutex)                                V(mutex)
  end                                     end
Each condition variable cond_i has a COUNT_i integer variable (initially 0) and a SEM_i semaphore (initially 0) associated with it. 
  wait(cond_i):
    COUNT_i++
    V(mutex)
    P(SEM_i)
    P(mutex) <-----------------------delete---------
    COUNT_i--                                      |
                                                   |-- problem
  signal(cond_i):                                  |
    if COUNT_i > 0 then V(SEM_i)                   |
    V(mutex) <-----------------------insert else----
    exit the monitor
there is a problem with this in that it does not adhere to the two life-simplifying assumptions (signal and exit).
a third process may sneak in and do a P(mutex) and get in the monitor before the signaled process can do its P(mutex)

this third process may change the condition so when the signaled process does succeed in its P(mutex) the condition may no longer be true
so we change the code to 
    wait(cond_i):
      COUNT_i++
      V(mutex)
      P(SEM_i)
      COUNT_i--

    signal(cond_i):
      if COUNT_i > 0 then V(SEM_i)
      else V(mutex)
      exit the monitor
Now we have signal and exit implemented correctly with semaphores.

An SR resource that implements a collection of ops/procs is not a monitor because concurrent calls of the ops/procs can be made.

A monitor condition variable is not the same as a semaphore because

Monitors and SR

Here is how to compile and run and SR program that has a monitor in file monitor.m. The -sx argument means the signal and exit signaling discipline. 
      m2sr -sx monitor.m
      sr -o prog monitor.sr driver.sr
      prog

In the bounded buffer monitor, _print(cv) prints the number of processes in the wait queue on the condition variable cv; the boolean function _empty(cv) will indicate if that queue is empty or not. The size of the buffer is gotten with getarg since SR monitors cannot be parameterized like resources can (an SR monitor is like a global resource in this regard).
Bounded Buffer Monitor.
Bounded Buffer SR Driver.

if count=1 then signal(not_empty) has been changed to just signal(not_empty), ditto if count=N-1 then signal(not_full)

the program still works since signals on queueless condition variables are ignored, but each signal involves overhead even if ignored, so better just to send useful signals

We use an array of condition variables, one entry in the array per philosopher. A simple form of starvation prevention is used: a philosopher can become ``very hungry'' if it cannot eat when one of its neighbor's puts down its forks. A very hungry philosopher has priority to eat. Notice that signal and wait, while easier to understand, does create programming inconveniences. Since putting down forks may involve generating two signals, the philosopher finishing eating has to enter the monitor twice. To leave the philospher code unchanged, a new resource dining_interface in added to enter the monitor.
Starvation-Free Dining Philosophers Monitor.
Starvation-Free Dining Philosophers SR Driver.

A continual stream of arriving readers is not allowed to keep waiting writers from entering the database.
Starvation-Free Readers and Writers Monitor.
Starvation-Free Readers and Writers SR Driver.

Initializing Data in Monitors

Our monitor examples use getarg to initialize some of their data. This is not modular since all program parameters and data variables should be initialized in one place. The following program shows a general flexible technique that can be used to initialize the data in a monitor using a global resource. The Parameters global resource can be in a separate file, or it can be in the same file as the monitor, preceding the monitor code, as is the case in the sample compile and run shown. In the latter case, the m2sr preprocessor will pass through unchanged the global resource code preceding the monitor. In fact, the driver can be in the monitor file, too, if the programming conventions described in the ``man'' page for m2sr are followed.
Initializing Data in a Monitor using a global.

A note on two dimensional arrays of condition variables. The usual subscripting expression [i,j] will not work in _wait and _signal. Use [i][j] instead, as shown in the program above.

Signal and Continue Signaling Discipline

This discipline does not require the signaling process to leave the monitor after a signal on a condition variable. Nor does the signaled process have priority to proceed in the monitor over other process waiting to enter through an interface routine. Relaxing the first requirement can simplify the coding of some monitors. In the dining philosophers monitor program above, we had to introduce an interface resource, dining_interface, that made two calls to the monitor whenever a philosopher put down its forks. With signal and continue, only one call is needed, as shown below. Since we can no longer guarantee that the condition that led to the signal is still true when the signaled process proceeds in the monitor, we need to take the precaution of changing the `if' statement containing the wait, 
if condition -> _wait(condvar) fi
to a `do while' loop, 
do condition -> _wait(condvar) od
With multiple processes potentially being signaled before the signaler leaves the monitor, there is the possibility that the signal condition is no longer true when a particular waiting process wakes up. Further, some other process may have entered the monitor through an interface routine and modified the condition before the signaled process wakes up.

The -sc argument means the signal and continue signaling discipline. 

      m2sr -sc monitor.m
      sr -o prog monitor.sr driver.sr
      prog

The sample output in the following SR program illustrates the differences between the `signal and exit' and `signal and continue' signaling disciplines. Notice that m2sr -sx enforces that a process must exit the monitor after sending a signal. Also notice that m2sr -sc allows a process trying to get in the monitor for the first time to enter before a signaled process can continue inside the monitor.
Show Signaling Disciplines Monitor.
Show Signaling Disciplines Driver.

Here is the dining philosophers implemented with a `signal and continue' monitor.
Dining Philosophers ``Signal and Continue'' Monitor.
Dining Philosophers ``Signal and Continue'' Driver.

This Java program shows that wait() and notify() follow the ``signal and continue'' signaling discipline in a Java object written as a monitor (synchronized methods).
Java Program: Show Monitor Signaling Discipline.

SJH
shartley@mcs.drexel.edu