Monitors in Java

In Java, there is no special construct for a monitor; instead, every object has a lock that can be used for synchronizing access to fields of the object. Listing 7.3 shows a class for the producer—consumer problem. Once the class is defined, we can declare objects of this class:

PCMonitor monitor = new PCMonitor();

and then invoke its methods:

monitor.Append(5);
int n = monitor.Take();

The addition of the synchronized specifier to the declaration of a method means that a process must acquire the lock for that object before executing the method. From within a synchronized method, another synchronized method of the same object can be invoked while the process retains the lock. Upon return from the last synchronized method invoked on an object, the lock is released.

There are no fairness specifications in Java, so if there is contention to call synchronized methods of an object an arbitrary process will obtain the lock.

A class all of whose methods are declared synchronized can be called a Java monitor. This is just a convention because—unlike the case with protected objects in Ada there is no syntactical requirement that all of the methods of an object be declared as synchronized. It is up to the programmer to ensure that no synchronization errors occur when calling an unsynchronized method.

A Java monitor for the producer—consumer problem

class PCMonitor {
  final int N = 5;
  int Oldest = 0, Newest = 0;
  volatile int Count = 0;
  int Buffer[] = new int[N];

  synchronized void Append(int V) {
    while (Count == N) {
      try {
        wait();
      } catch (InterruptedException e) {}
    }
    Buffer[Newest] = V;
    Newest = (Newest + 1) % N;
    Count = Count + 1;
    notifyAll();
  }

  synchronized void Take() {
    while (Count == 0) {
      try {
        wait();
      } catch (InterruptedException e) {}
    }
    temp = Buffer[Oldest];
    Oldest = (Oldest + 1) % N;
    Count = Count - 1;
    notifyAll();
    return temp;
  }
}

If a process needs to block itself—for example, to avoid appending to a full buffer or taking from an empty buffer—it can invoke the method wait. (This method throws InterruptedException which must be thrown or caught.) The method notify is similar to the monitor statement signalC and will unblock one process, while notifyAll will unblock all processes blocked on this object.

The following diagram shows the structure of a Java monitor:

There is a lock which controls the door to the monitor and only one process at a time is allowed to hold the lock and to execute a synchronized method. A process executing wait blocks on this object; the process joins the wait set associated with the object shown on the righthand side of the diagram. When a process joins the wait set, it also releases the lock so that another process can enter the monitor. notify will release one process from the wait set, while notifyAll will release all of them, as symbolized by the circle and arrow.

A process must hold the synchronization lock in order to execute either notify or notifyAll, and it continues to hold the lock until it exits the method or blocks on a wait. The unblocked process or processes must reacquire the lock (only one at a time, of course) in order to execute, whereas with the IRR in the classical monitor, the lock is passed from the signaling process to the unblocked process. Furthermore, the unblocked processes receive no precedence over other processes trying to acquire the lock. In the terminology of Section 7.5, the precedence specification of Java monitors is \( E = W < S \).

An unblocked process cannot assume that the condition it is waiting for is true, so it must recheck it in a while loop before continuing:

synchronized method1() {
  while (!booleanExpression) {
    wait();
  }

  // Assume booleanExpression is true
}

synchronized method2() {
  // Make booleanExpression true
  notifyAll()
}

If the expression in the loop is false, the process joins the wait set until it is unblocked. When it acquires the lock again it will recheck the expression; if it is true, it remains true because the process holds the lock of the monitor and no other process can falsify it. On the other hand, if the expression is again false, the process will rejoin the wait set.

When notify is invoked an arbitrary process may be unblocked so starvation is possible in a Java monitor. Starvation-free algorithms may be written using the concurrency constructs defined in the library java.util.concurrent.

A Java monitor has no condition variables or entries, so that it is impossible to wait on a specific condition. Suppose that there are two processes waiting for conditions to become true, and suppose that process p has called method1 and process q has called method2, and that both have invoked wait after testing for a condition. We want to be able to unblock the process whose condition is now true:

synchronized method1() {
  if (x == 0) {
    wait();
  }
}

synchronized method2() {
  if (y == 0) {
    wait();
  }
}

synchronized method3(...) {
  if ( ... ) {
    x = 10;
    notify (someProcessBlockedInMethod1); // Not legal !!
  } else {
    y = 20;
    notify (someProcessBlockedInMethod2); // Not legal !!
  }
}

Since an arbitrary process will be unblocked, this use of notify is not correct, because it could unblock the wrong process. Instead, we have to use notifyAll which unblocks all processes; these processes now compete to enter the monitor again. A process must wait within a loop to check if its condition is now true:

synchronized method1() {
  while (x == 0) {
    wait();
  }
}

synchronized method2() {
  while (y == 0) {
    wait();
  }
}

synchronized method3(...) {
  if ( ... ) {
    x = 10;
    notify (someProcessBlockedInMethod1); // Not legal !!
  } else {
    y = 20;
    notify (someProcessBlockedInMethod2); // Not legal !!
  }
}

If the wrong process is unblocked it will return itself to the wait set.

However, if only one process is waiting for a lock, or if all the processes waiting are waiting for the same condition, then notify can be used, at a significant saving in context switching.

A Java solution for the problem of the readers and writers is shown in Listing 7.4. The program contains no provision for preventing starvation.

Synchronized blocks

We have shown a programming style using synchronized methods to build monitors in Java. But synchronized is more versatile because it can be applied to any object and to any sequence of statements, not just to a method. For example, we can obtain the equivalent of a critical section protected by a binary semaphore simply by declaring an empty object and then synchronizing on its lock. Given the declaration:

Object obj = new Object();

the statements within any synchronized block on this object in any process are executed under mutual exclusion:

synchronized (obj) {
  // critical section
}

There is no guarantee of liveness, however, because in the presence of contention for a specific lock, an arbitrary process succeeds in acquiring the lock.

A Java monitor for the problem of the readers and the writers

class RWMonitor {
  volatile int readers = 0;
  volatile boolean writing = false;

  synchronized void StartRead() {
    while (writing) {
      try {
        wait();
      } catch (InterruptedException e) {}
    }
    readers = readers + 1;
    notifyAll();
  }

  synchronized void EndRead() {
    readers = readers - 1;
    if (readers == 0) {
      notifyAll();
    }
  }

  synchronized void StartWrite() {
    while (writing || (readers != 0)) {
       try {
        wait();
      } catch (InterruptedException e) {}
      writing = true;
    }
  }

  synchronized void EndWrite() {
    writing = false;
    notifyAll();
  }