Mutual Exclusion and Synchronization in Java

Mimicking Win32 synchronization mechanisms

Dan is a software engineer for Hewlett-Packard's Workgroup Networks Division. He can be contacted at [email protected].

Although Java was designed as an object-oriented language, it has been strongly influenced by C++. One feature in Java that is not built into the C++ language, however, is concurrency. C++ (from its C background) took a minimalist approach, depending on the target platform and operating system to supply concurrency facilities (if available). Java, on the other hand, because it is intended to shield you from the idiosyncrasies of operating systems and specific hardware platforms, must supply facilities such as concurrency as features of the language. This does not mean that the concurrency features of Java are inflexible. Because it's object oriented, Java's facilities can be extended and adapted to meet most needs.

In this article, I will discuss Java's concurrency features, paying particular attention to the tools Java provides for serializing access to shared resources and synchronizing separate threads of execution. In addition, I'll present Java classes for mutual exclusion and synchronization that mimic the behavior and interfaces of the synchronization mechanisms available in the Win32 API. Although I originally developed these classes for use in network-management applications (in particular, Java applications that acted as servers for multiple Java applets used by a network traffic-management system), they are useful for many kinds of multithreaded Java applications -- and especially those that focus on embedded systems.

Java's Threading and Synchronization

In Java, you usually create a separate thread of execution by instantiating an object derived from the Thread class. However, this does not actually cause the thread to begin execution; it must be explicitly started with a separate method. Every object derived from the Thread class will have three methods of particular importance: start(), stop(), and run(). The start() method, as you might guess, begins the thread's execution by spawning a separate thread of execution that calls the run() method in the context of this new thread. The stop() method will cause the thread to stop execution, regardless of what it is doing at the time. A thread will also end when execution of the run() method completes. Since the run() method of the Thread class doesn't do anything (it is, in fact, an abstract method), you must derive an object from Thread, and override the run() method. The code in the run() method, then, is the code executed for the new thread. Listing One starts a thread that displays the date and time once every second until it is stopped after ten seconds by the main thread.

In any language, concurrency raises interesting problems with respect to handling shared resources, and Java is no exception. Typically, operating systems provide facilities for creating mutual-exclusion semaphores or similar objects useful for serializing access to a shared resource. However, in Java, it is desirable to avoid calling machine or operating-system-specific code. Fortunately, the designers of Java have provided some facilities for basic mutual exclusion that, in turn, can be extended to meet more sophisticated requirements.

The mechanism used in Java to serialize access to objects is the synchronized method or the synchronized statement. Every object in Java has an associated lock, which is implicitly obtained by a thread when a synchronized method is called or when the synchronized statement is executed.

Locks are simply convenient tokens that can be used by well-behaved cooperating threads to indicate which thread currently has access privileges to the shared object. When a synchronized instance method is called, the system attempts to obtain a lock for that instance. If no other thread owns the lock (meaning that no other threads are currently executing either a synchronized method or statement on the same instance of this class), then the calling thread obtains ownership of the lock, and execution is allowed to continue into the synchronized method.

However, if the lock for this instance is already owned, then the calling thread will be blocked until the current owner relinquishes the lock. When execution reaches the end of the synchronized method, the lock is implicitly released, allowing other waiting threads to obtain it. It is important to note that the lock is for a particular instance object of a class. Multiple threads will be allowed into the same synchronized method at the same time if the calling threads are operating on different instances of the class. This is important to remember if the method uses static variables, which might be shared by all instances of the class. A synchronized method is just like any other method, except that it uses the synchronized keyword as a modifier before the return type of the method. Listing Two is an example of a synchronized method.

A synchronized statement is similar, except that the object for which the lock is obtained is specified as a parameter, followed by a block of code. Just as with the synchronized method, when execution reaches the end of the block of code, the lock is automatically relinquished. The unsynchronized method in Listing Three is equivalent to the synchronized method just described.

The synchronized statement provides additional flexibility over the synchronized method, which is necessary in some cases. For example, if the shared resource is only accessed during a small part of the method, it might be desirable (for efficiency reasons) to obtain the lock only during that part of the method. Or it might be necessary to obtain a lock on more than one object before proceeding. For example, Listing Four must obtain a lock on two shared objects before performing the assignment. This ensures that during the copy operation, neither the name buffer passed in, nor the member variable myname, is modified by other well-behaved threads.

Well-Behaved Threads

The point about well-behaved threads is important, because there is nothing special about a lock that prevents access to the object by other threads. If other threads have public access to the object through unsynchronized methods, or if other threads somehow use the objects without obtaining a lock, then data corruption can occur. Much like in the real world, locks in the Java world are only useful for keeping out good citizens, while doing little to prevent unauthorized access by outlaws.

Threads also have a need to signal each other when certain events occur, in order to synchronize their activities. Perhaps one thread is monitoring an external device and needs to signal when the device is in a particular state so that other threads can use the device. This type of synchronization is done with the wait() and notify() methods. If a thread calls wait(), it will be added to the object's wait set. When a thread calls wait(), it must own a lock on the object, otherwise an exception is thrown. A thread in an object's wait set is blocked until the notify() method is called by another thread. As the term implies, more than one thread can be in the wait set at any given time. This is possible because when a thread is added to an object's wait set, it relinquishes its lock on the object, allowing other threads to gain a lock and operate on the object. When the notify() method is called, a thread in the wait set is chosen arbitrarily by the system and unblocked. If there is more than one thread in the wait set, there is no guarantee that any particular thread will be the one unblocked. However, once a thread is unblocked and begins running again, it will proceed only if a lock is available for that object; that is, it must reestablish the lock it had obtained before the call to wait().

This behavior results in the state machine in Figure 1. This state machine makes it clear that a thread in a wait set is in a different state than a blocked thread. A blocked thread is waiting for a lock on an object, whereas a thread in a wait set is waiting for another thread to call notify(). Finally, if the desired behavior is to have a thread notify all the waiting threads in the wait set, then it can call notifyAll(). Of course, all threads must contend for ownership of the lock that they had before their respective calls to wait().

Thread Priorities

Imagine all threads having the same priority. Different priorities for threads will have little impact on the fundamental behaviors discussed here. However, once a thread is scheduled to run (that is, once it is not blocked waiting for a lock, or in a wait set, or suspended), if it is the highest priority thread of all threads currently scheduled to run, then it will actually run. If a thread is blocked waiting for a lock, it really doesn't matter how high its priority is; what is more important is the priority of the thread currently holding the lock it is waiting for. If a low-priority thread is holding a lock needed by a high-priority thread, the high-priority thread must wait at the mercy of the lower-priority thread, which, in turn, could be starved out of CPU time by other unrelated (but higher-priority) threads. As you can see, thread priorities can quickly complicate the design of multithreaded applications. This topic, however, is outside the scope of this article.

Java Classes for Win32-like Mutual Exclusion and Synchronization

The facilities I've described so far are quite flexible, and can meet many of the needs of a typical multithreaded Java application or applet. However, more-traditional idioms may be helpful in some circumstances:

• Porting code from C++ to Java might be easier if more-conventional mutual-exclusion objects existed -- objects that, for example, resembled the Win32 mutex facilities.
• Mutual exclusion for primitive types might be necessary. Since primitive types are not derived from Object (the base class of all objects in Java), they do not have associated locks, wait sets, and so on. To guard access to a primitive type, a special wrapper class must be written, or a separate mutual-exclusion object must be created.
• A more-traditional approach may be preferable for restricting access to a resource to a specific number of concurrent users. For example, a communications object may have a fixed number of ports available, and will need to limit the number of threads using its services to match the number of ports it has. This is a more general case of exclusion, where the number of concurrent users may be greater than one but limited to a specific maximum.
• A special mutex class may be helpful when management of a shared resource is spread out over a larger portion of the program; for example, if exclusive access to an object is obtained in one method and released in another.

Special Class

Each of the situations just described could benefit from a special mutual-exclusion class that could be used by any arbitrary object or even used to gate access to primitive types. In the remainder of this article, I will present Java classes that emulate the interfaces and behavior of the Win32 synchronization mechanisms.

The Win32 API provides four high-level mechanisms for mutual exclusion and thread synchronization:

• Mutexes.
• Critical Sections.
• Events.
• Semaphores.

Although many of these can be used interchangeably, each has particular applications for which it is best suited or for which it more naturally expresses the problem at hand. In the following sections, I will describe each mechanism briefly, followed by a discussion of the Java class used to implement it. Figure 2 illustrates the Java class hierarchy. Three of the classes implement an interface I called Blockable. A thread may block (wait for access or ownership) on any Blockable object. A class that implements the Blockable interface must provide the waitForSingleObject methods. This is just like the Win32 API where a thread can call waitForSingleObject on Mutexes, Semaphores, or Events alike. The CriticalSection has a different interface and does not implement Blockable. However, before I discuss the four Win32-like synchronization mechanisms, a discussion of the BaseMutex abstract base class is in order.

The BaseMutex class (see Listing Five) is an abstract base class that provides the basic implementation inherited by the MtxEvent, Mutex, and CriticalSection classes. It implements a flexible synchronization class that can be customized by specifying the appropriate constructor arguments. These arguments specify the values of the two basic properties of a BaseMutex that determine its behavior:

• The signaled state. A BaseMutex object can be in one of two possible states, signaled or unsignaled. In the signaled state the BaseMutex is "on," indicating that no other thread currently owns the resource. If a thread calls the waitForSingleObject() method on a signaled BaseMutex, immediate access will be granted. If a BaseMutex is in the unsignaled state, threads calling waitForSingleObject() will be blocked until the BaseMutex is released (signaled) with a call to release().
• The reset mode. A BaseMutex object can be automatic or manual. In automatic mode, the BaseMutex object is automatically put in the unsignaled state when access is granted (through waitForSingleObject()). This behavior allows only a single waiting thread access when the previous owner releases the BaseMutex. On the other hand, in manual mode, a call to release puts it into the signaled state, and it stays in that state until an explicit call to reset() is made. A consequence of this mode is that when release is called on a manual BaseMutex, the state is set to signaled, and all currently waiting threads are unblocked and allowed access. This is not an effective mutual-exclusion mechanism, but is useful for signaling events.

  In addition to these properties, this class also supplies the implementation for the waitForSingleObject() method. The implementation of waitForSingleObject() is complicated by the timeout parameter. Java allows a parameter to be specified in the call to wait(). However, when control returns from wait(), there is no way to determine (based on the return value), whether control returned because the thread was notified or simply because the timeout expired. Therefore, it is necessary to add extra code to determine this and return the correct code from waitForSingleObject().

Mutexes

A mutex (short for mutual exclusion) is an object used to gate exclusive access to a shared resource; see Listing Six. Threads may request access to a mutex, and the mutex will only grant access when no other thread owns the mutex. A thread must be a good citizen and release its ownership of the mutex by a call to release the mutex. Releasing the mutex will allow other waiting threads to gain access in turn. If a thread already owns a mutex when it requests access again, it will immediately be granted continued access; however, the thread must release the mutex the same number of times that it requested access before other threads can gain ownership. Additionally, when a thread requests access to the mutex, it can optionally specify a timeout interval. If the mutex is not able to grant access before the timeout interval expires, it will return to the calling thread a return code indicating that access was not granted. In addition to the Blockable interface, the Mutex class also implements a releaseMutex method. Finally, one difference between the Java Mutex class in Listing Six and the Win32 mutex is that a Win32 mutex can be named, and therefore, may be used for synchronization across multiple processes. The Java Mutex class cannot be named or used for synchronization between different Java applications.

Critical Sections

A CriticalSection, like a Mutex, is useful for serializing multiple threads that need to access a shared resource; see Listing Seven. However, while you usually use a Mutex to protect a global resource (such as a variable, handle, or device), a CriticalSection is typically used to guard a section of code. At most, one thread will be allowed to execute that block of code at a time. The interface for CriticalSections consists of two methods: EnterCriticalSection(), which you place at the beginning of the critical block of code, and LeaveCriticalSection(), which is placed at the end of the block. These two methods (in addition to the default constructor) are the entire interface to CriticalSection; the CriticalSection class, therefore, does not implement the Blockable interface. It does, however, use BaseMutex for its implementation.

Events

Events are used to notify other threads that something has happened that the thread might need to synchronize its activity with; see Listing Eight. Events are powerful general-purpose synchronization mechanisms. There are two basic types of events: manual and automatic. An automatic event behaves just like a Mutex in that only a single waiting thread will be notified that the event occurred when the event is signaled. Threads using manual events must set (signal) and reset (release) the event explicitly; also, a manual event will notify all waiting threads when it is signaled. Since the set and reset actions are discrete calls, a manual event is not useful for serializing access to a resource. This is because more than one thread could get access in the interval of time between the call to set and the call to reset.

The Java class for the Win32 Event is named MtxEvent, and, like the Mutex class, it extends the BaseMutex class and implements the Blockable interface. In addition to the Blockable interface, the MtxEvent class also provides three additional public methods:

• setEvent(), which signals the event. If the MtxEvent is an automatic event, one waiting thread will be notified, and the MtxEvent is immediately placed in the reset state. If the MtxEvent is a manual event, all waiting threads will be notified, plus it remains in the signaled state.
• resetEvent(), which clears the event. This has the effect of blocking all subsequent threads that call waitForSingleObject() on the event.
• PulseEvent(), which calls setEvent() followed by resetEvent() in one operation. For a manual MtxEvent, pulseEvent() notifies all currently waiting threads that the MtxEvent is signaled (thus unblocking them), but immediately resets the event so that all subsequent threads that call waitForSingleObject() will be blocked, waiting for another pulseEvent() or setEvent().

Semaphores

Semaphores work much like mutexes, but they have a counter associated with them. They will grant ownership to more than one thread up to a preset maximum. In this sense, they are a superset of a Mutex, where a Mutex is a Semaphore with the maximum set to 1. The Java Semaphore class implements the Blockable interface, but does not extend the BaseMutex implementation. For performance and simplicity, the Semaphore class (Listing Nine) does not store a reference to each thread granted access (like the Mutex class does). Therefore, each request for ownership of the Semaphore counts as a distinct owner, even if it is the same thread repeatedly making the request.

Conclusion

There is much you can do to extend the classes presented here. For example, the Blockable interface allows Mutexes, Semaphores, and MtxEvents to be treated similarly by threads seeking access through the waitForSingleObject() methods. However, another helper class would need to be written to provide facilities similar to the Win32 waitForMultipleObjects. Also, you can write a wrapper class around the thread class to implement the Blockable interface for threads. Many other enhancements and helper classes can be built with the facilities presented here. Appropriate use of multithreading, along with the proper tools and techniques to manage the accompanying complexity, will help you create powerful Java applications and applets.

DDJ

Listing One

import java.util.Date;class MyThread extends Thread {
    public void run() {
        while (true) {
            System.out.println("It is now " + new Date());
            try {
                Thread.sleep(1000); // sleep for 1 second
            } catch (InterruptedException e) { }
        }
    }
}
class MyApp {
    public static void main (String args[]) {
        MyThread thrd = new MyThread();
        thrd.start();
        try {
            Thread.sleep(10000);    // sleep for 10 seconds
        } catch (InterruptedException e) { }
        thrd.stop();
        System.exit(0);
    }
}

Back to Article

Listing Two

 ...public synchronized void incrementCounter() { this.counter++; }
 ...

Back to Article

Listing Three

 ...public void incrementCounter() { 
synchronized(this) { this.counter++; }
}
 ...

Back to Article

Listing Four

 ...public void setName(StringBuffer name) { 
    synchronized(this) {
        synchronized(name) { 
            this.myname = new String(name);
        } 
    }
}
 ...

Back to Article

Listing Five

abstract class BaseMutex {    public BaseMutex(boolean bManual, boolean binitSignaled) {
        this.bSignaled = binitSignaled;
        this.bAuto = !bManual;
    }
    protected synchronized int waitForSingleObject(long ulTimeout) {
        if (bSignaled) {
            if (bAuto)
                reset();
            return Blockable.SUCCESS;
        }
        long t1, t2;
        try {
            t1 = System.currentTimeMillis();
            wait(ulTimeout);
            t2 = System.currentTimeMillis() - t1;
        } catch (InterruptedException e) {
            return Blockable.INTERRUPT;
        }
        if (t2 >= ulTimeout)
            return Blockable.TIMEOUT;
        if (bAuto)
            reset();
        return Blockable.SUCCESS;
    }
    protected synchronized void signal() {
        bSignaled = true;
        if (bAuto)
            notify();
        else
            notifyAll();
    }
    protected synchronized void reset() {
        bSignaled = false;
    }
    //----------------------------------------------
    boolean bSignaled;
    boolean bAuto;
}

Back to Article

Listing Six

class Mutex extends BaseMutex implements Blockable {    public Mutex(boolean bInitialOwner) {
        super(false, !bInitialOwner);
        if (bInitialOwner) {
            count = 1;
            thrd = Thread.currentThread();
        } else {
            count = 0;
            thrd = null;
        }
    }
    public int waitForSingleObject() {
        return this.waitForSingleObject(INFINITE);
    }
    public synchronized int waitForSingleObject(long ulTimeout) {
        // if the mutex is not owned by any other thread
        if (count == 0) {
            count = 1;
            thrd = Thread.currentThread();
            return super.waitForSingleObject(ulTimeout);
        }
        // Otherwise, check to see if the current owner is the same thread 
        // calling now; if so, grant immediate access
        if (thrd == Thread.currentThread()) {
            count++;
            return SUCCESS;
        }
        // Otherwise block and wait for the current owner to relinquish mutex
        int rc = super.waitForSingleObject(ulTimeout);
        if (rc == SUCCESS) {
            count = 1;
            thrd = Thread.currentThread();
        }
        return rc;
    }
    public synchronized int releaseMutex() {
        if (thrd != null)
            if (thrd == Thread.currentThread()) {
                count--;
                if (count == 0) {
                    thrd = null;
                    super.signal();
                }
                return SUCCESS;
            }
        return NOTOWNED;
    }
    // private data members
    private int    count;
    private Thread thrd;
}

Back to Article

Listing Seven

class CriticalSection extends BaseMutex {    public CriticalSection() {
        super(false, true);
    }
    public synchronized void enterCriticalSection() {
        while (waitForSingleObject(Blockable.INFINITE) != Blockable.SUCCESS) ;
    }
    public synchronized void leaveCriticalSection() {
        signal();
    }
}

Back to Article

Listing Eight

class MtxEvent extends BaseMutex implements Blockable {    public MtxEvent(boolean bManual, boolean bSignaled) {
        super(bManual, bSignaled);
    }
    public int waitForSingleObject() {
        return super.waitForSingleObject(INFINITE);
    }
    public synchronized int waitForSingleObject(long ulTimeout) {
        return super.waitForSingleObject(ulTimeout);
    }
    public synchronized void setEvent() {
        signal();
    }
    public synchronized void resetEvent() {
        reset();
    }
    public synchronized void pulseEvent() {
        signal();
        reset();
    }
}

Back to Article

Listing Nine

class Semaphore implements Blockable {    public static final int INVALID_INCREMENT = -1;
    
    public Semaphore(int initialValue, int maxValue) {
        currentLocks = initialValue;
        maxLocks = maxValue;
    }
    public int waitForSingleObject() {
        return this.waitForSingleObject(INFINITE);
    }
    public synchronized int waitForSingleObject(long ulTimeout) {
        long t1, t2;
        if (currentLocks == maxLocks) {
            try {
                t1 = System.currentTimeMillis();
                wait(ulTimeout);
                t2 = System.currentTimeMillis() - t1;
                if (t2 >= ulTimeout)
                    return TIMEOUT;
            } catch (InterruptedException e) {
                return INTERRUPT;
            }
        }
        currentLocks++;
        return SUCCESS;
    }
    public synchronized int releaseSemaphore(int increment) {
        if (currentLocks - increment >= 0) {
            currentLocks -= increment;
            for (int i=0; i < increment; i++)
                notify();
            return SUCCESS;
        }
        return INVALID_INCREMENT;
    }
    // private data members
    private int currentLocks;
    private int maxLocks;
}



Back to Article



DDJ

Copyright © 1998, Dr. Dobb's Journal