Featured White Papers

• Measuring Risk to Improve Java Software Quality
• Do You Really Get Classloaders?
• Pragmatic Continuous Delivery with Jenkins, Nexus, and LiveRebel
• Your Next Java Web App: Less XML, No Long Restarts, Fewer Hassles
• Coding with JRebel, Java Forever Changed
• 2012 Developer Productivity Report: Java Tools, Tech, Devs, and Data

Sponsored Links

• Graph databases are 1000x faster than relational.

  Learn More!

• Career opportunities at Harman- Careers That'll Rock Your Socks Off.

  Learn More!

• Developer-friendly Java PDF libraries by Qoppa Software

  Live Demos

• Stop blaming your app! Diagnose Java performance issues.

  Free tool >

• UrbanCode: Go From Continuous Integration to
  Continuous Delivery

  Learn More!

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

Better monitors for Java

A Hoare-style monitor package for multithreaded programming in Java

By Theodore S. Norvell, JavaWorld.com, 10/04/07

Page 2 of 4

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

import 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 <= sec && sec < 60
            && 0 <= min && min < 60
            && 0 <= hr && hr < 24 ; }

}

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

import 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 < capacity */
    private final Condition notFull = makeCondition() ;

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

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

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

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

}

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

Figure 1. A UML class diagram for a FIFO queue (click for larger image)

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_notFull is count < capacity, while P_notEmpty 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().