Better monitors for Java

Multithreaded programming is challenging but unavoidable, which is why you need the best tools and techniques for doing it safely. In this article Theodore S. Norvell introduces the conceptual underpinnings of Hoare-style monitors (such as the use of exclusive access, conditions, and assertions) then presents his own Java-based monitor package that automates assertion checking during execution.

It is all too easy to write unsafe multithreaded Java code, in part because the language’s notify() and wait() methods can be difficult to use correctly. In 1974, Tony Hoare proposed the concept of monitors for designing and reasoning about objects that are shared between multiple threads. The key property of these “Hoare-style” monitors is that threads can wait until some specific assertion about the monitor’s state is true and be guaranteed that it is still true after the thread has been awakened.

In this article, I describe an open source Java class library that supports the monitor concept much as Hoare originally proposed it. As I will demonstrate, object-oriented technology makes it possible to improve on Hoare’s concept by making assertions — which are traditionally stated as comments and then repeated in if statements and assert statements — executable objects. This approach reduces redundant coding and automates assertions checking during execution.

I’ll start by explaining why multithreaded programming is as unavoidable as it is challenging, then introduce you to the use of exclusive access, conditions and assertions in Hoare-style monitors. See the Resources section to download the Java-based monitors package.

The case for Hoare-style monitors

Three factors contribute to the ubiquity of multithreaded software, and thus the need for monitors:

1. Responsive, interactive software. To be responsive, interactive software must perform tasks that take more than a few tens of milliseconds on threads other than the GUI event thread.
2. Multiprocessor, multicore and simultaneous multithreading (hyper-threading) hardware. Computationally intensive applications must run with multiple threads to use more than a fraction of the capability of modern hardware.
3. Distributed computing. Distributed architectures often demand that applications deal with multiple requests simultaneously. For example, RMI invocations each run on their own thread.

Coordinating the activities of two or more threads can be very tricky and can be a source of latent defects in multithreaded code. Testing is ineffective because tests may not reveal race conditions. As software engineers we must equip ourselves with the intellectual and software tools to design correct multithreaded applications.

Monitoring multithreaded access

In the 1970s Edsger Dijkstra, Per Brinch Hansen and C.A.R. Hoare developed the idea of the monitor: an object that would protect data by enforcing single-threaded access. Only one thread at a time would be allowed to execute code within the monitor, making monitors islands of single-threaded calm in a turbulent sea of multithreadedness. Confining thread interactions to monitors would greatly improve the chance that they wouldn’t interfere with each other in unanticipated ways.

A number of variants on the idea of monitors have been proposed and implemented in various programming languages such as Concurrent Pascal, Mesa, Concurrent Euclid, Turing and more recently Java. The idea of single-threaded access to a monitor is straightforward and the same in all these variants; where they differ is in how threads wait for the state of the monitor to change, and how they communicate to each other that the state has changed. Of all the these approaches, I’ve always found Hoare’s version the easiest to use. In Hoare’s version, occupancy of the monitor is transferred directly from a signaling to a signaled thread: the state of the monitor object cannot change between the signaling thread leaving and the signaled thread arriving.

A Java-based implementation of Hoare-style monitors

For the rest of this article I’ll focus on a Java package I’ve developed that implements Hoare-style monitors. In addition to being a straightforward Java-based implementation of Hoare’s original concept, the monitor package has one novel feature: it allows all assertions used in designing a monitor to be expressed as part of the code and checked at runtime.

To get started, Table 1 summarizes the classes in the monitor package. See the Resources section for the source code for the monitor package.

Table 1. Summary of interfaces

Using monitors for exclusive access

A monitor is an object that only allows exclusive access to its data; that is, data can be accessed by only one thread at a time. In my monitor package, exclusive access is accomplished by inheriting from class AbstractMonitor and calling inherited method enter() to enter the monitor and inherited method leave() to leave it.

Between returning from enter() and invoking leave() a thread is said to occupy the monitor. At most one thread can occupy the monitor at any time; a thread that invokes enter() while the monitor is occupied must wait (on an entry queue associated with the monitor) until the monitor becomes unoccupied. When a thread calls leave(), one thread waiting on the entry queue — if there is such a thread — is selected and allowed to occupy the monitor.

Consider the class in Listing 1. Without the exclusive access provided by the calls to enter() and leave(), a client might find that the time is 25:60:60 (which should be impossible) or might find the time to be 13:59:59 when it is really 13:00:00.

Listing 1. A class with exclusive access

<code>import</code> <code>monitor.* ;
 
public class TimeOfDay extends AbstractMonitor {

    private volatile int hr = 0, min = 0, sec = 0 ;

    public void tick() {
        enter() ;
            sec += 1 ; min += sec/60 ; hr += min/60 ;
            sec = sec % 60 ; min = min % 60 ; hr = hr % 24 ;
        leave() ; }

    public void get( int[] time ) {
        enter() ;
            time[0] = sec ; time[1] = min ; time[2] = hr ;
        leave() ; }

    @Override
    protected boolean invariant() {
        return 0 &lt;= sec &amp;&amp; sec &lt; 60
            &amp;&amp; 0 &lt;= min &amp;&amp; min &lt; 60
            &amp;&amp; 0 &lt;= hr &amp;&amp; hr &lt; 24 ; }

}


</code>

Note that this example could equally well be implemented using Java’s synchronized keyword. The only advantage to using the monitor package for this example is that the class invariant, embodied as the overridden method invariant(), is checked as part of the entering and leaving process. The invariant describes the set of states the monitor may be in when the monitor is not occupied. If the invariant is found to be false on either a return from enter() or a call to leave(), an Error exception will be thrown. In such a simple class, checking the class invariant is probably not that useful. In more complex classes, however, checks of monitor invariants can provide a valuable indication of a bug during testing or even when the product is deployed.

I marked the fields of the example class as volatile so that the compiler will not assume that only one thread may access these fields. To be on the safe side, fields of a monitor should be marked either as final or volatile.

Because Java does not support multiple inheritance, it is sometimes inconvenient to inherit from AbstractMonitor. In this case you could use a private field of class Monitor. Monitor is just like AbstractMonitor, except its methods are public rather than protected.

Contracts for enter() and leave()

The enter() and leave() methods are well described by their contracts, such as, their preconditions and postconditions. Here I refer to the monitor’s invariant.

Conditions

The real power of Hoare-style monitors becomes evident when a thread may have to wait for something before completing its work in the monitor. A classic example is a bounded FIFO (first in, first out) queue. A thread that is fetching from the queue must wait until the queue is not empty; a thread that is depositing data into the queue must wait until there is room for data in the queue. Listing 2 shows a FIFO queue with a capacity of 10 objects, implemented in Java using my monitor package.

Listing 2. A FIFO queue

<code>import</code> <code>monitor.* ;

 public class FIFO extends AbstractMonitor {

    private final int capacity = 10 ;

    private final Object[] queue = new Object[ capacity ] ;

    private volatile int count = 0, front = 0 ;

    /** Awaiting ensures: count &lt; capacity */
    private final Condition notFull = makeCondition() ;

    /** Awaiting ensures: count &gt; 0 */
    private final Condition notEmpty = makeCondition() ;

    public Object fetch() {
        enter() ;
            if( ! (count &gt; 0 ) ) { notEmpty.await() ; assert count &gt; 0 ; }
            Object value = queue[ front ] ;
            --count;
            front = (front + 1) % capacity ;
            assert count &lt; capacity ; notFull.signal() ;
        leave() ;
        return value ; }

    public void deposit( Object value ) {
        enter() ;
            if( ! ( count &lt; capacity ) ) {
               notFull.await() ; assert count &lt; capacity ; }
            queue[ (front + count) % capacity ] = value ; ++count ;
            assert count &gt; 0 ; notEmpty.signal() ;
        leave() ; }

    @Override
    protected boolean invariant() {
        return 0&lt;=count &amp;&amp; count&lt;=capacity &amp;&amp; 0&lt;=front &amp;&amp; front&lt;capacity ; }

}


</code>

Figure 1 is a UML class diagram for the FIFO queue in Listing 2.

The number of objects in a queue is represented by count. A fetching thread may have to wait until count>0, while a depositing thread may have to wait until count<capacity. Each of these assertions about the state is represented by a condition object. The two condition objects are referenced by two private fields and are created by calls to method makeCondition() inherited from AbstractMonitor:

/** Awaiting ensures: count < capacity */
    private final Condition notFull = makeCondition() ;

    /** Awaiting ensures: count > 0 */
    private final Condition notEmpty = makeCondition();

Each condition object c is associated with an assertion P_c. In Listing 2 P<sub>notFull</sub> is count < capacity, while P<sub>notEmpty</sub> is count > 0.

When a thread needs to wait for an assertion P_c to become true, it invokes c.await(). The effect of c.await() is that the thread that calls it leaves the monitor and waits on a queue associated with the condition object. While the thread is waiting, it does not occupy the monitor, and so another thread can enter and possibly make the assertion become true. Because the thread that invokes await() leaves the monitor unoccupied, the class invariant should be true when await() is invoked, and indeed await() checks the invariant.

A thread that makes an assertion P_c true may (and usually should) transfer occupancy to some waiting thread, if there is one. It can do this by invoking the method c.signal(). If one or more threads are waiting on that condition object, one waiting thread is selected and it enters the monitor. As the selected thread enters the monitor, the signaling thread leaves the monitor to wait on the monitor’s entry queue. At no point during this exchange is the monitor unoccupied; thus the waiting thread will find the monitor in the same state it was in when the signaling thread called signal(). Only when the monitor is once again empty does the signaling thread get to re-occupy the monitor and return from signal().

Click here to see a flash animation that illustrates how monitored threads use enter(), leave(), await() and signal().

Conditions and ‘design by contract’

If we follow the convention that the assertion P_c is true whenever c.signal() is called, then P_c must be true when c.await() returns. This is a sort of contract that the person implementing the monitor makes with himself. Indeed, signal() and await() are best understood in terms of “design by contract” based on preconditions and postconditions.

A contract for await()

The precondition of c.await(), as you’ve seen, is the monitor’s invariant, which I’ll call I. The thread only returns from c.await() when another thread calls c.signal(). From the precondition of c.signal(), as you will see, P_c must be true at that time. The contract for c.await() is shown below.

A contract for signal()

What about signal()? If a thread is waiting on the condition’s queue, then P_c must be true as a precondition. On return, as the monitor was just empty, the monitor invariant will be true as a postcondition. But what if no thread is waiting? In that case, signal() does nothing and so, to ensure the invariant is true as a postcondition, it should be a precondition as well. You can express the contract using c.isEmpty(), which indicates whether any threads are waiting on the condition.

The precondition of the above contract is a bit complicated. In practice you can almost always use one of two simpler preconditions instead; each implies the contract’s precondition, as so, is a safe substitute. One precondition is

P_c && I && this thread alone occupies the monitor

and the other is

!c.isEmpty()&& P_c && this thread alone occupies the monitor

signalAndLeave()

Often, there is no need for a signaling thread to wait and later reoccupy the monitor. In this case you can call signalAndLeave(). Upon awakening an awaiting thread, if there is one, this method returns without re-occupying the monitor. The contract for signalAndLeave() is shown here.

More detailed contracts

There’s one more wrinkle to these contracts: they only work if neither the invariant I nor the assertion P_c depend on the number of threads waiting on c. That’s because the acts of starting to wait and ceasing to wait change this quantity. John H. Howard and Ole-Johan Dahl give correct contracts for the rare cases when I and P_c are dependent on the number of waiting threads.

Assertion objects

Looking back at Listing 2, you can see that each assertion appears four times, counting comments, assert statements and if statements. For good reason, software engineers abhor such duplication. Of course, you could encapsulate each duplicated assertion in a method, but then you would have to duplicate the call to the method. In my Java-based monitor package I’ve provided a better solution, wherein each assertion may be represented by an object.

Classes representing assertions are created by subclassing Assertion and overriding the abstract method isTrue(). Each condition object knows one Assertion object and checks the assertion upon any call to signal(), throwing an exception if the assertion is false. Based on this approach, you could change the FIFO queue in Listing 2 by rewriting the declarations of the condition objects as follows:

Listing 3. The FIFO queue with assertions

private final Condition notFull = makeCondition(
        new Assertion() {
            public boolean isTrue() {return count < capacity ; } } ) ;


    private final Condition notEmpty = makeCondition(
        new Assertion() {
            public boolean isTrue() {return count > 0 ; } } ) ;

You can also use assertion objects to replace if statements, such as those in fetch and deposit, with calls to conditionalAwait(). The rewritten deposit method is shown in Listing 4; the fetch method can be rewritten similarly. The classes for the revised FIFO queue are shown in Figure 2. Similarly, there is a conditionalSignal() method.

Listing 4. The deposit method rewritten

public void deposit( Object value ) {
        enter() ;
            notFull.conditionalAwait() ;
            queue[ (front + count) % capacity ] = value ;
            count++ ;
        notEmpty.signalAndLeave() ; }

In summary, the following checks are made automatically:

• The invariant is checked on the return from enter(), the call to leave(), on the call to await(), on the return from signal(), and, when there is no waiting thread, on the call to signalAndLeave().
• Assertion objects are checked on calls to signal() or signalAndLeave(), if there is a waiting thread, and on the return from await().

A voting example

As an interesting example of using Hoare-style monitors, let’s look at how a number of threads can synchronize and exchange information. The specific problem is that a number of threads must vote on a boolean result. I’ve used a simple majority, with ties going to false. Listing 5 shows the monitor.

Listing 5. The Vote Monitor

import monitor.* ;

public class VoteMonitor extends AbstractMonitor {


    private final int N ;
    private volatile int votesFor = 0, votesAgainst = 0 ;

    private Condition electionDone = makeCondition( new Assertion() {
        public boolean isTrue() { return votesFor+votesAgainst == N ; } } ) ;

    public VoteMonitor(int N) { assert N>0 ; this.N = N ; }

    @Override
    protected boolean invariant() {
        return 0 <= votesFor && 0 <= votesAgainst && votesFor+votesAgainst < N ;
    }

    public boolean castVoteAndWaitForResult(boolean vote) {
        enter() ;

            if( vote ) votesFor++ ; else votesAgainst++ ;

            electionDone.conditionalAwait() ;
            // votesFor + votesAgainst == N

            boolean result = votesFor > votesAgainst ;

            if( ! electionDone.isEmpty() ) {
               electionDone.signalAndLeave() ; }
            else {
               // The last one woken up is the first one out and cleans up.
               votesFor = votesAgainst = 0 ;
               leave() ; }

        return result ;
    }
}

About the code

The constructor takes the number of threads involved in the elections. After construction each thread casts its vote and receives the majority using the castVoteAndWaitForResult method.

The election is over when votesFor+votesAgainst==N and so this assertion is P<sub>electionDone</sub>. Interestingly, this assertion contradicts the invariant. After casting its vote, a thread waits for the election to be over by conditionally waiting on electionDone. On returning from electionDone.conditionalAwait(), the thread can be sure that P<sub>electionDone</sub> is true. Thus it could leave the monitor and return with the result at that time.

This would cause two problems, however: First, only the last thread to vote would get the result; all others would wait forever. Second, there would be no way to reuse the monitor object for a second election. To solve these two problems I divided the work: Each thread awakens one waiting thread until no threads are waiting on electionDone — I call this technique “daisy chaining.” The last thread on the chain finds there are no more threads to awaken; it resets the state of the monitor to the original state; having done that, it has reestablished the monitor invariant and may leave the monitor unoccupied.

Note that the invariant is not true when signalAndLeave is called. Despite the fact that the invariant has not been reestablished, it is acceptable for the signaling threads to leave the monitor, because they are not leaving it empty. As discussed in the next section, this approach would not be possible using Java’s standard methods.

Comparison to Java’s wait() and notify() methods

It wouldn’t be right to present my Java-based monitor package without comparing it with Java’s “native” monitors, which are built using the synchronized keyword and the wait() and notify() methods from the Object class.

In Java, every object is associated with two queues: an entry queue and a wait queue. When a thread calls a method marked as synchronized, the thread will wait on the entry queue until no other thread occupies the object. On returning from a synchronized method the thread relinquishes occupancy. Threads unconditionally wait on the wait queue by calling the wait() method of the synchronizing object. A call to notify() does not relinquish exclusive access; rather it simply moves some waiting thread, if there is one, from the object’s wait queue to the object’s entry queue. There also is a notifyAll() method that moves all threads from the wait queue to the entry queue.

Java’s native monitors are similar to those found in Mesa and are sometimes said to use the “signal and continue” (SC) signaling discipline. By contrast, my monitor package gives you a choice of “signal and wait” (SW) or “signal and leave” (SL).

The following list summarizes the main differences between my monitor package and Java’s wait() and notify() approach:

Defensive programming

The monitor package provides support for defensive programming through the invariant() method and the assertion objects associated with each condition object. Java’s notify() and wait() provide no assertion checking.

Multiple wait queues

The

monitor

package provides condition objects, each providing its own wait queue. Threads waiting for different assertions to become true wait on different queues. Using

wait()

, there is only one wait queue per object. Threads waiting for different assertions to become true must all wait on the same queue; thus a

notify()

call could awaken a thread that is waiting for the “wrong” assertion. The usual solution is to replace calls to

notify()

with calls to

notifyAll()

and to always put calls to

wait()

in a loop, so:

while( ! P<sub>c</sub> ) { wait(); }

Flexible assertions

With Hoare-style monitors it is possible for a waiting thread to awaken in a state where the class invariant is not true. This gives the designer more flexibility in choosing the assertions that threads can wait for. When a thread returns from wait(), it does so from the entry queue and so the invariant must be true.

Seamless passing of occupancy

In the monitor package, following Hoare’s suggestion, control is passed seamlessly from the signaling thread to an awaiting thread. You can be sure that, after returning from an await(), the assertion the thread has waited for is true. In contrast, the notify() and notifyAll() methods simply move a waiting thread back to the entry queue for the monitor. By the time the waiting thread actually becomes the occupant, the assertion for which it was waiting may no longer be true. This is a second reason for putting wait() calls in a loop. But such loops have a problem: an invocation of notify() that awakens a thread that then re-waits is effectively lost. As notify() calls can be lost, it can be difficult to ensure “sufficient signaling” — the property that any waiting thread is eventually awakened. With the monitor package, ensuring sufficient signaling requires only ensuring that each await() be matched by some signal() on the same condition object in the future.

In conclusion

Hoare-style monitors provide a sound programming method for coordinating the interactions of multiple threads. In the limited space of this article, I could only illustrate this point with very simple examples. As the complexity of the interactions increase, the benefit of using Hoare-style monitors increases.

In Hoare’s original concept, a monitor’s invariant and the assertions associated with condition variables were purely tools of design and documentation: the truth of the assertions can be proved and there is no need to check them at runtime. In practice though, even careful designers make mistakes and, as software evolves, errors can creep in. Thus it is pragmatic to check assertions at runtime. The monitor package in this article automatically checks assertions and invariants, letting you move the assertions out of the comments and into the code.

See the Resources section for the source code for the monitor package.

Acknowledgments

Thanks to Alain O’Dea for suggesting an improvement to the monitor package, to Michael Bruce-Lockhart and Dennis Peters for suggesting improvements to this article, and to Ric Holt for introducing me to Hoare-style monitors many years ago.