CS 5204, Operating Systems
Summary of Tuesday, January 21, 1997

by Jeff Nielsen

Contents

The three topics covered on January 21 were

1. Condition Synchronization
2. The Monitor Model
3. Implementing Monitors in Java

Condition Synchronization

Condition synchronization is a more complex form of synchronization than simple mutual exclusion. The goal of condition synchronization is to associate conditions on the state of the system with certain operations, so that those operations are performed only when the system is in some acceptable state. For example, in the producer-consumer problem we only want producers to produce when the buffer is not full. In that case, the operation is producing, and the condition we want to associate with that operation is "buffer not full."

Another requirement of condition synchronization that the state of the system doesn't change while conditions are being evaluated. If it did, there could obviously be all kinds of consistency problems.

SUMMARY OF REQUIREMENTS

• Operations performed only when some condition is true
• System state can't change during condition evaluation

The Monitor Model

The monitor model (developed by Tony Hoare) is a way of achieving the requirements of condition synchronization. The key parts of the model are

1. A monitor "object" (i.e., abstract data type) with a mutual-exclusion lock encapsulating the object,
2. A set of state variables inside the monitor,
3. A set of condition variables, each with its own queue and two supported operations:
• wait()
• signal()

All shared resources must be accessed through the procedures/methods provided by the monitor object. The state variables store the current state of the system. The condition variables are used to keep track of which processes/threads are waiting on which conditions. The way that these parts of the model work together is as follows.

In order to access a shared resource (or perform some other potentially-dangerous operation), a thread must call one of the monitor methods. Because of the mutual-exclusion lock, only one process is allowed to execute a monitor method at a time. Once the thread enters the monitor, the state variables are used to test the condition(s) that must be true for the thread to proceed. If the condition is true, the thread is allowed to continue and the state variables are updated as necessary. If the condition is false, however, the wait() method of the associated condition variable is called, causing the thread to to placed on the condition variable's queue. Later, when subsequent operations by other threads make the condition true, the signal() method of the condition variable is called to wake up the thread (or threads) that were waiting for that condition.

There are some possible variations in the exact semantics of the signal() operation.

• Signal & Block (used in Hoare's original model) means that the thread calling the signal() is immediately made to wait, ensuring that it doesn't proceed to do something which would make the condition false again.
• Signal & Continue means that the thread continues executing even after calling the signal(). This is usually acceptable since, in practice, threads are not likely to "undo" conditions they just made true.
• Signal & Return means that calling a signal() is the last thing a thread can do before exiting the monitor.

Implementing Monitors in Java

Monitors can be implemented using the Java programming language. The three key parts of the model are implemented as follows.

1. Any Java class/object can be turned into a monitor by declaring one or more of its methods to be synchronized. This provides the mutual-exclusion lock on the object when these methods are running.
2. Class member variables can be used as state variables since these are protected by the mutual-exclusion lock. (Java defines a primitive boolean type which can be used to store true/false conditions.)
3. The effect of condition variables can be simulated by using the wait(), notify(), and notifyAll() methods which are "built into" each Java object (these methods are defined in the Object class, which is the superclass of all other Java classes). These methods operate with a single "queue" for each object, meaning that there is effectively one implicit condition variable per object. Java uses Signal & Continue semantics for notify() and notifyAll().

The following example shows a bounded counter implemented using both Hoare-style pseudocode and Java code. Comments on the example are given below.

// HOARE'S MONITOR MODEL            // MONITOR IMPLEMENTED IN JAVA

monitor BoundedCounterVST           class BoundedCounterVST extends Object
begin                               {

  condition belowMax, aboveMin;       // One implicit condition variable
  integer value;                      private int value;
  constant MAX=100, MIN=0;            final int MAX=100, MIN=0;

  integer value()                     public synchronized int value()
  begin                               {
    return value;                        return value;
  end                                 }
   
  void inc()                          public synchronized void inc()
  begin                               {
    if (value == MAX)                   while (value == MAX) 
      belowMax.wait();                    try {wait();} catch(Exception e) {}
    value = value + 1;                  value += 1;
    if (value == MIN+1)                 if (value == MIN+1)
      aboveMin.signal();                  notifyAll();
  end                                 }

  void dec()                          public synchronized void dec()
  begin                               {
    if (value == MIN)                   while (value == MIN)
      aboveMin.wait();                    try {wait();} catch(Exception e) {}
    value = value - 1;                  value -= 1;
    if (value == MAX-1)                 if (value == MAX-1)
      belowMax.signal();                  notifyAll();
  end                                 }

  begin                               BoundedCounterVST() {
    value = MIN;                        value = MIN; 
  end                                 }

end                                 }

Notice that condition variables are not declared in the Java code, since there is no explicit condition variable type (although we could write our own). This means that there is no way in Java to specify or determine which condition a particular thread is waiting for if there is more than one condition tested by the monitor. Most of the other differences in the code can be attributed to this limitation.

• Instead of calling the wait() operation associated with a specific condition variable (e.g., belowMax.wait()), the Java code can only use the generic wait() and the single implicit queue that comes with it.
• When a condition becomes true, the Java code can not notify only the thread or threads waiting on that condition. Thus, instead of belowMax.signal() or aboveMin.signal() we must do a notifyAll() and wake up all threads waiting for any condition.
• When a Java thread wakes up, there is no guarantee that the condition it was waiting for is true. This is why the conditions are tested in a while loop in the Java code, as opposed to a simple if test in Hoare's model. Each time a Java thread wakes up, it must re-test the condition and call wait() again if the condition is still false.