Chapter 5: Monitors and Condition Synchronization

Monitors are language features for concurrent programming. A monitor encapsulates data, which can only be observed and modified by monitor access procedures. Only a single access procedure may be active at a time. An access procedure thus has mutually exclusive access to the data variables encapsulated in the monitor. Monitors should sound familiar since we have already seen the monitor concept in the last chapter, though explained using different terminology. An object satisfies the data access requirement of a monitor since it encapsulates data which, if declared private, can be accessed only by the object’s methods. These methods can be synchronized to provide mutually exclusive access. Thus, a monitor is simply represented in Java as a class that has synchronized methods.

Monitors support condition synchronization in addition to ensuring that access to the data they encapsulate is mutually exclusive. Condition synchronization, as the term suggests, permits a monitor to block threads until a particular condition holds, such as a count becoming non-zero, a buffer becoming empty or new input becoming available. This chapter describes how condition synchronization in monitors is modeled and how it is implemented in Java.

5.1 Condition Synchronization

We illustrate condition synchronization using a simple example. A controller is required for a car park, which only permits cars to enter when the car park is not full and, for consistency, does not permit cars to leave when there are no cars in the car park. A snapshot of our Java simulation of the car park is given in Figure 5.1. It depicts the situation in which the car park is full, the barrier is down and no further cars are permitted to enter. Car arrivals and departures are simulated by separate threads. In Figure 5.1, the departures thread has been stopped to allow the car park to become full. The arrivals thread is therefore blocked from further progress.

Figure 5.1: Car park display.

5.1.1 Car Park Model

The first step in modeling a system is to decide which events or actions are of interest. In the car park system, we can abstract details such as display panel rotation and the starting and stopping of the display threads. We thus omit the actions concerned with running, rotation, pausing and terminating threads that we modeled in section 3.2.1. Instead, we concern ourselves with only two actions: car arrival at the car park and car departure from the car park. These actions are named arrive and depart respectively. The next step is to identify the processes. These are the arrivals process, the departures process and the process that controls access to the car park. Both the arrivals process and the departures process are trivial. They attempt to generate, respectively, a sequence of arrival actions and a sequence of departure actions. The car park control must only permit arrival actions to occur when there is space in the car park and departures to occur when there are cars in the car park. This expresses the synchronization conditions that must be satisfied by the other processes when interacting with the car park.

The car park model is given in Figure 5.2. The CARPARKCONTROL process uses the indexed state SPACES to record the number of available spaces in the car park. The control requirements described above have been modeled using the FSP guarded action construct (see section 2.1.5). Thus in state SPACES[0], arrive actions are not accepted and in state SPACES[N], depart actions are not accepted.

Figure 5.2: Car park model.

The behavior of the car park system is depicted as an LTS in Figure 5.3. The LTS has been generated directly from the model of Figure 5.2. It clearly shows that a maximum of four arrive actions can be accepted before a depart action must occur.

Figure 5.3: Car park LTS.

5.1.2 Car Park Program

Our models of concurrent systems represent all the entities in a system as processes. In implementing the behavior of a model as a Java program, we must decide which entities are active and which are passive. By active, we mean an entity that initiates actions; this is implemented as a thread. By passive, we mean an entity that responds to actions; this is implemented as a monitor. As we will see in subsequent examples, the decision as to which processes in a model become threads in the implementation and which become monitors is not always clear-cut. However, in the car park example, the decision is clear. The processes ARRIVALS and DEPARTURES, which initiate arrive and depart actions, should be implemented as threads. The CARPARKCONTROL process, which responds to arrive and depart actions, should be a monitor. The class structure of the car park program is depicted in Figure 5.4.

Figure 5.4: Car park class diagram.

We have omitted the DisplayThread and GraphicCanvas threads managed by ThreadPanel to simplify Figure 5.4. These are organized in exactly the same way as depicted in the class diagram for ThreadDemo in Chapter 3. The classes that are relevant to the concurrent execution of the program are the two Runnable classes, Arrivals and Departures, and the CarParkControl class, which controls arrivals and departures. Instances of these classes are created by the CarPark applet start() method:

 public void start() {   CarParkControl c =      new DisplayCarPark(carDisplay,Places);      arrivals.start(new Arrivals(c));      departures.start(new Departures(c)); }

Arrivals and Departures are instances of the ThreadPanel class and carDisplay is an instance of CarParkCanvas as shown in the class diagram.

The code for the Arrivals and Departures classes is listed in Program 5.1. These classes use a ThreadPanel.rotate() method which takes as its parameter the number of degrees the rotating display segment is moved. The CarParkControl class must block the activation of arrive() by the arrivals thread if the car park is full and block the activation of depart() by the departures thread if the car park is empty. How do we implement this in Java?

Program 5.1: Arrivals and Departures classes.

 class Arrivals implements Runnable {   CarParkControl carpark;   Arrivals(CarParkControl c) {carpark = c;}   public void run() {     try {       while(true) {         ThreadPanel.rotate(330);         carpark.arrive();         ThreadPanel.rotate(30);       }     } catch (InterruptedException e){}   } } class Departures implements Runnable {   CarParkControl carpark;   Departures(CarParkControl c) {carpark = c;}   public void run() {     try {       while(true) {         ThreadPanel.rotate(180);         carpark.depart();         ThreadPanel.rotate(180);       }     } catch (InterruptedException e){}   } }

5.1.3 Condition Synchronization in Java

Java provides a thread wait set per monitor; actually, per object, since any object may have a monitor synchronization lock associated with it. The following methods are provided by class Object from which all other classes are derived.

 public finalvoid notify()

Wakes up a single thread that is waiting on this object’s wait set.

 public finalvoid notifyAll()

Wakes up all threads that are waiting on this object’s wait set.

 public finalvoid wait() throwsInterruptedException

Waits to be notified by another thread. The waiting thread releases the synchronization lock associated with the monitor. When notified, the thread must wait to reacquire the monitor before resuming execution.

The operations fail if called by a thread that does not currently “own” the monitor (i.e. one that has not previously acquired the synchronization lock by executing a synchronized method or statement). We refer to a thread entering a monitor when it acquires the mutual exclusion lock associated with the monitor and exiting the monitor when it releases the lock. From the above definitions, it can be seen that a thread calling wait() exits the monitor. This allows other threads to enter the monitor and, when the appropriate condition is satisfied, to call notify() or notifyAll() to awake waiting threads. The operation of wait() and notify() is depicted in Figure 5.5.

Figure 5.5: Monitor wait() and notify().

The basic format for modeling a guarded action for some condition cond and action act using FSP is shown below:

 FSP: when cond act -> NEWSTAT

The corresponding format for implementing the guarded action for condition cond and action act using Java is as follows:

 Java: public synchronized void act()              throws InterruptedException       {         while (!cond) wait();         // modify monitor data         notifyAll()       }

The while loop is necessary to ensure that cond is indeed satisfied when a thread re-enters the monitor. Although the thread invoking wait() may have been notified that cond is satisfied, thereby releasing it from the monitor wait set, cond may be invalidated by another thread that runs between the time that the waiting thread is awakened and the time it re-enters the monitor (by acquiring the lock).

If an action modifies the data of the monitor, it can call notifyAll() to awaken all other threads that may be waiting for a particular condition to hold with respect to this data. If it is not certain that only a single thread needs to be awakened, it is safer to call notifyAll() than notify() to make sure that threads are not kept waiting unnecessarily.

Returning to the car park example, the implementation of the CarParkControl monitor is given in Program 5.2. Since either the ARRIVALS thread is blocked waiting space or the DEPARTURES thread is blocked waiting cars and these conditions are exclusive, only a single thread may be waiting on the monitor queue at any one time. Consequently, we can use notify() rather than notifyAll(). Note that we have made the spaces and capacity variables protected rather than private so that they can be accessed by the display class that is derived from CarParkControl.

Program 5.2: CarParkControl monitor.

 class CarParkControl {   protected int spaces;   protected int capacity;   CarParkControl(n)     {capacity = spaces = n;}   synchronized void arrive()       throws InterruptedException {     while (spaces==0) wait();     --spaces;     notify();   }   synchronized void depart()      throws InterruptedException{     while (spaces==capacity) wait();     ++spaces;     notify();   } }

The general rules for guiding the translation of the process model into a Java monitor are as follows:

Each guarded action in the model of a monitor is implemented as a synchronized method which uses a while loop and wait() to implement the guard. The while loop condition is the negation of the model guard condition.

and

Changes in the state of the monitor are signaled to waiting threads using notify() or notifyAll().

Thus in the car park model:

 FSP: when(i>0) arrive->SPACES[i-1]

becomes

 Java: while (spaces==0) wait(); --spaces;

and

 FSP: when(i<N) depart->SPACES[i+1]

becomes

 Java: while (spaces==N) wait(); ++spaces;

The state of the car park monitor is the integer variable spaces. Each method modifies spaces and consequently, the change is signaled by notify() at the end of each method.