HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML
 

One of the significant advances of Java over C++, its nearest syntactic relative, is Java's built-in thread synchronization facilities. Java uses a very object-oriented approach to thread synchronization, in which each and every object has its own monitor, which is used to protect the objects sensitive sections of code from simultaneous access by multiple threads. In this article, we will review Java's built-in thread synchronization capabilities.

Java's synchronization techniques are so generalized, however, that sometimes the most common synchronization tasks are a little difficult to perform. I will present a thread synchronization package I have developed, called maso.synch, which performs those common tasks in a completely re-usable manner. That package is downloadable from the Internet, source code and all.

Basic Thread Synchronization
I'm writing this article from Oregon, where we have done away with the voting booth in favor of mail-in balloting. But the more traditional voting booth offers up some interesting and archetypical examples of synchronization problems. I'll review the in vivo voting procedure: in the traditional place of polling, many voters arrive at different times during the day, each one waiting to vote. Let's say at any one time there are V voters waiting to cast a ballot. Problem is, there are only N voting booths, so (V-N) voters on average are always waiting for a booth. When any one of the N voters who is currently voting finishes, she leaves her booth, and the next waiting voter takes her booth and begins voting. Only one voter may occupy a booth at a time, and the waiting voters must patiently organize themselves in a line (or "queue") until the next booth is ready.

This system can easily be modeled by a multi-threaded application. Each voter is represented by a single thread. That thread's lifetime is controlled by a routine call vote(), which can be written in pseudo-code as shown in Listing 1.

In an object-oriented world, the N voting booths would be represented by an array of N Booth objects, and the line the voter waited in would be a FIFO storage structure.

Each Voter thread must wait for any one of the Booth objects to be "unclaimed". In Java, every object has an associated monitor, which controls exclusive access by a single thread to that object. You bring sections of an object's code under the control of the object's monitor using the synchronized reserved word. By using this keyword, you are essentially saying, "I only want a single thread to have access to my object's instance data while in this code". In our voting booth example, you would control each Booth's castVoteFor() method with the Booth object's monitor, as illustrated in Listing 2.

Notice the use of the synchronized modifier in the castVoteFor() method. This indicates that only one thread at a time may enter this method with the same Booth object's instance data. That is, two threads may enter this method in the context of two different Booth objects. But only one of those threads may enter this method in the context of the same Booth object. That's because each object's unique monitor guards that object's instance data within synchronized code. In the event where two different threads attempt to call the same object's synchronized method, only one will enter and execute the code. The other will be suspended in a waiting state until the former leaves the synchronized code. At that point, the second thread will be allowed to run.

Back to our example (and the First Problem Of Monitors). What we want is a way for the first Voter thread in line to wait for any one of the Booth objects to become unoccupied. The First Problem Of Monitors is just this: there's no way for a single thread to wait for more than one object's monitor! It just can't be done in Java. (The maso.synch package described towards the end of this article solves this problem for the general case, but more on that later). That is, you have one Voter thread which wants any one of the N Booth object's monitors, whichever becomes free first. But the Voter thread can only wait for a single Booth object monitor.

The way around this problem is to use an intermediate object between the Voter threads and the Booth objects. This intermediate object will store all the free booths at any one time. That is, this intermediate object is a type of synchronized storage object. Instead of asking the Booth object's themselves if they are free, the Voter threads ask the synchronized storage for the next free Booth. The Voter thread will be suspended by the storage device as long as no Booth is free. Once a Booth becomes free, the next Voter thread is awoken. The code for this storage device, which I call a SynchedFIFO, is shown in Listing 3.

Each Voter thread calls SynchedFIFO.getNext() to retrieve the next object added to it (presumably a reference to a Booth object). In getNext(), the Voter will be suspended as long as there are no items stored in the SynchedFIFO. "But wait!", you say,"when a Voter gets suspended in the synchronized method SynchedFIFO.getNext(), no other Voter thread will be able to enter the method. Isn't that what the synchronized' modifier means, that only one thread may be executing the code at a time?!" That's a very astute question. Pat yourself on the back. The trick here is that the wait() method is used in getNext() to suspend any threads waiting for objects from the SynchedFIFO. The wait() call not only does what you'd expect, suspending the current thread indefinitely, but it also has the added side effect of giving up the monitor for the current object. So, several threads may enter the getNext() method simultaneously, each one getting suspended by the call to wait(), which releases the SynchedFIFO's monitor, allowing any other threads to enter the method and also get stuck.

To wake threads from a call to wait(), you must call notify() or notifyAll(). Notify() will pick one thread at random from all the threads stuck in a wait() within the object's synchronized code and wake it. NotifyAll() will wake all threads stuck in wait() calls. The woken thread must regain the object's monitor before it can continue executing within the synchronized method, however. SynchedFIFO.put() calls notifyAll() to wake up all threads waiting for objects to be returned from getNext(). Note that wait(), notify() and notifyAll() must all be called from within synchronized code.

So, our polling place example now has a cast of three types of characters: Voting threads, Booth objects, and a SynchedFIFO. When a Booth is freed, it must be registered with the SynchedFIFO so that a new Voting thread can use it. To do this, we modify Booth.castVoteFor() as shown in Listing 4.

Our vote() routine, in which the Voter threads run, can now be written as shown in Listing 5.

A quick review: the synchronized reserved word is used to bring sections of code under the control of an object's monitor. Only one thread at a time may execute synchronized code in the context of a particular object. Note that you can synchronize individual blocks of code, not just whole methods. This is illustrated in Listing 6.

The code surrounded by the synchronized(this) {...} delimiters is synchronized on the monitor of the this object.

Within a synchronized block of code, the wait() method can be used to suspend the current thread. Within a wait() call, the thread automatically gives up ownership of the object's monitor. Two overloaded versions of the wait() method are implemented in the Object class. That's right, in the Object class. That means all classes in Java have the wait() methods implemented, since all classes are ultimately derived from the Object class. One overloaded version of wait() causes the calling thread to wait indefinitely until it is woken by a call to notify within the context of the same object. The other overloaded version of wait() takes a time limit as a parameter, which will cause the calling thread to wait at most as long as the time duration specified in the parameters to that method. Use notify() or notifyAll() to wake threads suspended in a wait() call. Both notify() and notifyAll() are also implemented in the Object class.

Advanced Thread Synchronization
As explained earlier in this article, there's no easy way to wait for multiple monitors in Java. Instead, you must generally place an intermediate object between your thread and the objects it is waiting for. The SynchedFIFO class is provided above as a general solution to one type of problem caused by this limitation of monitors. But really there are a multitude of synchronization situations where the SynchedFIFO is inappropriate.

I have developed a generic thread synchronization package, called maso.synch, which solves a majority of the programming difficulties monitors present. The Scheduler class of maso.synch is able to synchronize an arbitrary number of threads on an arbitrary number of Synch objects. Specific classes of Synch object included in the package include Mutex, Semaphore, Signal, AutoSignal, CounterSynch, ThreadSynch, Timer, Clock and TickingClock.

Each one of these Synch object classes implements a generic synchronization behavior common to many thread synchronization problems. For example, the Semaphore object allows N threads to gain "ownership" of it simultaneously. The N+1-th thread which tries to gain access is suspended until one of the initial N's releases ownership. Sounds similar to our N voting booths problem? It's very similar. The problem of synchronizing access to a fixed number (N) of resources is common to multi-threaded applications, and the Semaphore class solves the generic problem pretty well.

I don't have the space to go deeply into the package, but I can give you a brief overview and a URL to where you can download this package, source and all, from the Web. The URL for the maso.synch package homepage is "http://www.europa.com/~bmaso/java/synch". There you'll find the API documentation of the package, sample Applets, and directions on how to download either the source or the compiled package.

The center of the maso.synch package is a Scheduler object. Using this object, you can synchronize a thread on the state of one or more Synch objects. Furthermore, you can synchronize your thread either on the state of all the Synchs, or on any one of them. That is, your thread can be made to wait until every Synch object in a set is in a release, or "signaled", state. Alternatively, the thread can be made to wait for any one of the Synch objects in a set to become signaled. A single call to Scheduler.waitFor() will suspend the calling thread until one of these two situations occurs, according to the parameters the method is passed. I encourage you to check out the maso.synch package homepage at the URL given above.

The nine specific Synch classes listed above each solve a particular type of thread synchronization problem. A Mutex is a degenerate form of a Semaphore in which N=1. Mutexes are generally used to control access to one or more "critical sections" of code, that is, code in which you only want a single thread running at any time. Monitors actually achieve a similar functionality quite successfully, although only by using the maso.synch package could you wait on multiple Mutexes simultaneously.

A Signal is the simplest type of Synch. It exposes methods which allow you to set its state to signaled or unsignaled by hand. The AutoSignal is a type of Signal which automatically becomes unsignaled whenever a thread waits for it and is released. Signals and AutoSignals can be used to indicate a global access flag, or any sort of boolean value.

A CounterSynch keeps an internal counter which is decremented whenever a thread waits for the object and is released. CounterSynchs can be used to keep track of a finite number of destructible resources, for example N objects pushed onto a stack which are popped off the stack whenever accessed. A Semaphore, by way of contrast, can be used to keep track of a finite number of renewable resources, such as voting booths.

A ThreadSynch becomes signaled when its associated thread terminates. Unlike the Thread.join() method, use of ThreadSynchs allows you to wait for multiple threads to terminate. The join() method only allows you to wait for one thread at a time.

The remaining three Synchs are all used to synchronize on quanta of time. Download the package and try it out. The maso.synch package makes complex thread synchronization in Java a lot easier.

About the Author
Brian Maso is a programming consultant working out of Portland, OR. He is the co-author of The Waite Group Press's upcoming release The Java API SuperBible. Before Java, Brian spent five years corralled in the MS Windows branch of programming, working for such notables as the Hearst Corp., First DataBank, and Intel. Readers are encouraged to contact Brian via e-mail at "[email protected]" with any comments or questions.

	

Listing 1

routine vote(Candidate c) {
wait for one of the N voting booths
Booth b = claim booth
b.castVoteFor(c)
release booth b

}

Listing 2

public class Booth extends Object {
...
public synchronized void castVoteFor(Candidate c) {
// Register the vote with the Secretary of State...
}
...
}

Listing 3

public class SynchedFIFO extends Vector {
	public synchronized Object getNext() {
		while(0 == countElements())
		  wait();
		Object o = getElementAt(0);
		removeElementAt(0);
		return o;
	}
	public synchronized void put(Object o) {
		append(o);
		   notifyAll();
	}
}

Listing 4

public class Booth extends Object {
	SynchedFIFO _sf = null;
	public Booth(SynchedFIFO sf) {
		_sf = sf;
		// Register this Booth initially, since is free
		// when created.
		_sf.put(this);
	}
public synchronized void castVoteFor(Candidate c) {
		// Register vote with the Secretary of State
		_sf.put(this);
	}
}

Listing 5

public void vote(SynchedFIFO sf, Candidate c) {
// wait for and claim next free booth...
	Booth b = (Booth)sf.getNext();
	// cast vote, which automatically frees Booth
	// for use by another Voter when it completes.
	b.castVoteFor(c);
	return;
}

Listing 6

public void MyUnsynchronizedMethod() {
	// bring a block of code under synchronization
	synchronized(this) {
	  // do some synchronized steps...
	}
	  // This code is not synchronized...
}

 

All Rights Reserved
Copyright ©  2004 SYS-CON Media, Inc.
  E-mail: [email protected]

Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.