This article may contain URLs that were valid when originally published, but now link to sites or pages that no longer exist. To maintain the flow of the article, we've left these URLs in the text, but disabled the links.

java911@microsoft.com         Download the code (11KB)

The Urge to SWMRG How would I use Java to implement something like the SWMRG (Single Writer Multiple Reader Guard) synchronization object from Advanced Windows by Jeffrey Richter (Microsoft Press, 1997) in Java? Actually, constructing a SWMRG (pronounced "swimerge") class is fairly straightforward in Java. For those who haven't read Advanced Windows, a SWMRG is a reader/writer guard that permits multiple reader threads at the same time, but ensures that writer threads are granted exclusive access. Doing this allows reading to be more efficient than simple serialization of access, while still ensuring that data is never left to be read in an incomplete or corrupt state. In addition, a good SWMRG implementation will enforce rules for sharing access between readers and writers. A SWMRG that ignores this sharing problem runs the risk of "starving" reader or writer threads. Because Java monitors themselves provide no fairness guarantees (a given thread is not ever sure to obtain a lock that is in contention), this is very important. The TestSWMRG Application/Applet       The basic concepts used to implement the SWMRG class shown in Figure 1 are roughly the same ideas presented by Doug Lea in Concurrent Programming in Java (Addison-Wesley, 1997). The TestSWMRG app (see Figure 2 and Figure 3) demonstrates using a SWMRG object to synchronize access to data. In the case of TestSWMRG, the data is an integer, n. Writers gain access to n by calling the SWMRG.startWrite method. When startWrite returns, the thread is guaranteed to have exclusive access to n. All other threads wanting to access n fall into a wait state until the writer thread releases its exclusive access with a call to SWMRG.endWrite. Similarly, readers gain access to n by calling the SWMRG.startRead method. When this method returns, it is guaranteed only that no writer has access to n. There may be other reader threads with simultaneous access.

Figure 2: TestSWMRG

      TestSWMRG creates an interactive visual display that lets you see a SWMRG in action and discover what happens when the thread timing is changed. There are initially two writer and five reader threads. Each of these threads starts up and enters an infinite loop, writing or reading (depending on which type of thread it is) forever. As each thread does its stuff, it gives a visual indication of what's going on by updating a custom ThreadStatus component (shown in Figure 4).
      The write method (called by writer threads) enters the waiting state by calling SWMRG.startWrite. When this method returns, the thread has exclusive access to n and enters the writing state. Next, the writer does its writing—it increments n by 1, delays a little bit, then increments it again. Finally, the writer releases access by calling endWrite and enters the idle state for a while before returning to reenter the waiting state.
      The read method (called by reader threads) calls SWMRG.startRead to enter the waiting state. When startRead returns, the thread enters the reading state. If the number read from n is odd, then somehow the reader thread got access while the writer thread was writing. (The delay between the first and second increment in the writer is present to increase the potential for this failure.) This indicates that SWMRG has a bug in it! In practice, this has not occurred so far. Like the write method, the reader also enters the idle state before returning to reenter its waiting state.

Java Tip of the Month Threads certainly aren't free. And they may be more expensive than you think! The expense of creating a thread in a Java application is potentially as bad as the worst Java VM's threading implementation (and the same goes for synchronized blocks and methods). Also, in a typical application, Java itself starts several threads in each VM. With this kind of resource consumption built in, it's good advice to avoid creating any threads that you don't absolutely require!

If you have the opportunity before continuing, you should play around with the TestSWMRG demo a bit to get the feel for it. TestSWMRG is included is this month's code samples. But How Does it Work?       The SWMRG class itself is pretty simple. It uses wait and notify, in conjunction with a set of condition variables, to ensure that readers and writers yield to one another properly. The mechanism used to implement this is known as a condition variable loop, which is just a loop that waits until a condition is true: while (!condition) { wait(); }       When variable(s) that affect the condition expression being waited for are changed, the thread making the change(s) calls notifyAll. This call wakes any threads waiting in the condition variable loop (don't forget that Object.wait causes threads to drop their locks while they sleep!) and causes them to loop around and recheck their condition. If the condition is now true for a given thread, the thread exits the loop.       Except for allowReader and allowWriter, reading and writing are exactly symmetrical. Both the startRead and startWrite methods enter condition variable loops waiting until the allowReader/allowWriter predicate method returns true. As threads release access through calls to endRead and endWrite, notifyAll is called to make waiters reevaluate their condition variables.       In the appropriate places, SWMRG updates the number of waitingReaders, waitingWriters, activeReaders, activeWriters, consecutiveWrites, and consecutiveReads. These variables are used by the allowReader and allowWriter methods to create a policy for admitting readers and writers. The policy currently in place is to allow no more than maxConsecutiveWrites and no more than maxConsecutiveReads to occur in a row. This ensures that neither readers nor writers get too greedy with respect to one another.

Java Resource of the Month Java is way cool. But it ain't the final word in programming languages. Or even virtual machines. You certainly can create interesting programming languages that compile to the Java VM. Take a look at http://grunge.cs.tu-berlin.de/~tolk/vmlanguages.html. But Java bytecode is highly specialized. It heavily favors type-checked, structured, garbage-collected, object-oriented programming languages like, well, Java. Since Java bytecode is not as unconstrained or general purpose as, say, x86 or 68000 code, not all programming languages will run equally well on a Java VM. In fact, quirky, typeless languages like Perl (one of my favorites) would likely suffer heavy performance degradation if compiled for the Java VM. (For more information, see http://www.perl.com.) An extreme case of a language that falls in this "doesn't-currently-compile-for-the-Java-VM-and-may-never" category is C++.

Unfortunately, because of Java's weak guarantees of monitor fairness, it does not eliminate the possibility of one or more writers starving another writer. (This can't happen with readers because readers are not exclusive with respect to one another.) In the unlikely event that this is a practical problem, a scheduling mechanism (probably a FIFO queue) can be set up to ensure that writers compete fairly for the SWMRG's monitor when trying to awaken from the wait call in startWrite.       As you can see, nearly every application can benefit from the universal appeal of a few blinking lights. Cheers!

From the January 1998 issue of Microsoft Interactive Developer.