Programming Java threads in the real world, Part 7

Singletons, critical sections, and reader/writer locks

This month I'm going to tie up a few synchronization-related loose ends left over from my previous Java Toolbox installments in this series. I'll start out looking at singletons, or one-of-a-kind objects. These are surprisingly difficult to implement efficiently in a multithreaded environment, but are essential in most programs. (java.awt.Toolkit is an example of a singleton.) Along the way, I'll also look at critical sections, or blocks of code -- as compared to objects -- that can be locked.

I'll finish up with a completely unrelated topic: reader/writer locks, which give you efficient, thread-safe access to read/write resources such as data structures and files. Reader/writer locks are simple enough to implement that I didn't want to devote an entire column to them, but they're essential in any multithreaded program that performs I/O operations, so I wanted to include them in the present series of articles. Reader/writer locks combined with the various semaphores and locks I've presented in previous installments of this series comprise a reasonably complete toolkit for solving thread-related synchronization problems.

Critical sections, singletons, and the Class object

So far in this series I've been concentrating on the monitor -- a means of locking an entire object while a body of code is being executed. The other essential sort of lock you should be aware of is the critical section. Critical sections are essential in implementing one-time initialization code when that code can be accessed from multiple threads.

A critical section is a chunk of code that can be executed by only one thread at a time. Compare this notion with a normal synchronized code block -- a monitor -- which is basically an exclusion semaphore that guards an entire object. Several threads can simultaneously execute a synchronized method, but only if the objects that are receiving the associated messages are different. In a critical section, the code itself is locked, not the object. Only one thread can be in the critical section at a time, even if the receiving objects are different. The mutex that guards a monitor is an object-level mutex; the mutex that guards a critical section is effectively a class-level mutex. Think of it this way: the code is defined in the class, not the object, so when you're locking the code itself, you're locking the entire class of objects. (By the way, I've seen authors get this wrong in print when they call a block of code inside a nonstatic method a "critical section." A block of code in a nonstatic method is part of the object's monitor; it is not a critical section.)

Static members

In Java, the notion of a critical section is closely tied to that of a static member, so let's start there. Java, like all OO languages, supports two categories of fields and methods:

Class variables:variables that control the state of all objects within a class.
Instance variables:variables that control the state of a single object within a class.

A class variable is implemented in Java by placing a static keyword before its definition.

To best explain how the two types of variables are used in practice, an example seems in order. Back in the dark ages (the early 1990s) somebody had the bright idea that every window on a computer screen should use a different color scheme, even within a single application. Magenta backgrounds with yellow borders, turquoise backgrounds with chartreuse borders -- it make your eyes hurt. (The reasoning was that the users would somehow remember the color combinations and more easily identify the windows. Nice theory, but the human mind just doesn't work that way.) In this system, a window's color scheme is an "instance variable": every instance -- every window -- potentially has a different value for its color scheme.

Eventually, people came to their senses and made all the windows the same color. Now the color scheme is a "class variable." The entire class of window objects uses the same color scheme. If the scheme changes, then all the windows should change their appearance.

You can model the class-level behavior like this:

class Window                    // not the AWT window
{   
   private static Color foreground = SystemColor.windowText;
   private static Color background = SystemColor.window;
synchronized static public change_color_scheme( Color foreground, Color background )
    {
        this.foreground = foreground;
        this.background = background;
        // code goes here that tells all the extant Window objects to
        // redraw themselves with the new color scheme.
    }
}

There are several problems with this simplistic approach, however, the first being threading.

Java creates a Class class object for every class in your system, and the static fields are members of this Class object. A Class object is a real object: It has methods (declared static in the class definition) and state (defined by the static fields). The Class object also has its own monitor. When you call a synchronized static method, you enter the monitor associated with the Class object. This means that no two synchronized static methods can access the static fields of the class at the same time. You can also lock the Class object explicitly, like this:

synchronized( Window.class )
{   // modify static fields here
}

Unfortunately, the Class-level monitor is in no way connected to the monitors of the various instances of the object, and a synchronized, but nonstatic, method can also access the static fields. Entering the synchronized nonstatic method does not lock the Class object. Why is this a problem? Well, in the previous example, it would appear to be harmless to omit the static (but not the synchronized) from the definition of change_color_scheme() since the static fields will be modified, even if the modifying method isn't static. Appearances are deceiving, though. If two threads simultaneously send change_color_scheme() messages to two different objects of class Window, a race condition results, and the color scheme will be in an unknown state. In other words, the individual Window objects are locked, but locking a Window object does not lock the corresponding Class object (which contains the class variables), and the static fields are unguarded. Consequently, we have two threads modifying two variables at the same time.

After threading, the second problem with the naive implementation is that there's no way to guarantee that all the existing objects stay in synch with changes to the class variables. A sloppy programmer can add an instance method (one that is not static) to the Window class, and that instance method can change the foreground or background fields without notifying the other windows, or even without updating its own color.

You can fix both the race-condition and lack-of-update problems by encapsulating the two static fields in a class of their own:

class Color_scheme
{
   private Color foreground = SystemColor.windowText;
   private Color background = SystemColor.window;
    /*package*/ synchronized change_color_scheme(
                                    Color foreground, Color background )
    {
        this.foreground = foreground;
        this.background = background;
        // code goes here that tells all the extant Window objects to
        // redraw themselves with the new color scheme.
    }
}
class Window                    // not the AWT window
{   
    static Scheme color_scheme = new Color_scheme();
    static change_color_scheme( Color foreground, Color background )
    {   scheme.change_color_scheme( foreground, background );
    }
}

Now there's no way to modify the foreground or background color without notifying the other windows. Note that this is one of the few cases in which you must use package access rather than an inner class. Had Color_scheme been an inner class of Window, direct access to foreground and background would still be possible from methods of Window. This approach also has the advantage of making the monitor that controls the Color_scheme more visible -- it's obviously the one associated with the explicit Color_scheme object, not the one associated with the Window.

Singletons

There's another problem with the earlier code, however. We really want only one Color_scheme to exist, ever. In the earlier code, I've done it accidentally by making the reference static and only calling new once, but I'd really like to guarantee that only one instance of the object can exist. The Gang of Four's (see Resources) Singleton pattern describes exactly this situation. Two excerpts from the Gang of Four book are relevant. The "Intent" section in the Gang of Four book's chapter on singletons states:

Ensure a class only has one instance, and provide a global point of access to it.

and the "Consequences" section says:

[Singleton] permits a variable number of instances. The pattern makes it easy to change your mind and allow more than one instance of the singleton class. Moreover, you can use the same approach to control the number of instances that the application uses. Only the [Instance] operation that grants access ot the singleton instance needs to change.

That excerpt from the "Consequences" section is interesting because it allows a Class object to be considered a singleton, even though there's more than one instance of the Class class in the program. It's guaranteed that there will be only a single instance of Class for a given class, so it's a singleton: Some_class.class (the "operation that grants access") always evaluates to the same Class object. The static fields and methods, since they are members of the Class object, define the state and methods of the singleton object as well. Exploiting this reasoning, I can ensure that only one instance of the Color_scheme exists by moving everything into the Class object (making everything static):

class Color_scheme
{
   private static Color foreground = SystemColor.windowText;
   private static Color background = SystemColor.window;
    private Color_scheme(){}
    /*package*/ synchronized static change_color_scheme(
                                    Color foreground, Color background )
    {
        this.foreground = foreground;
        this.background = background;
        // code goes here that tells all the extant Window objects to
        // redraw themselves with the new color scheme.
    }
}

Note that I've also added a private constructor. A class, all of whose constructors are private, can be created only by a new that's invoked in a method that legitimately has access to the class's other private components. There are no such methods here, so no instances of Color_scheme can actually be created. This guarantees that only one object can exist -- the Class object, a singleton.

I also have to change the Window to use the Class object rather than a specific instance:

class Window                    // not the AWT window
{   
    // Note that there's no field here, now.
    change_color_scheme( Color foreground, Color background )
    {   Color_scheme.change_color_scheme( foreground, background );
    }
}

I've eliminated the static field in the Window class and have invoked change_color_scheme() directly through the class.

This sort of singleton -- a class all of whose methods are static -- is called a Booch utility (after Grady Booch, who identified the pattern in one of his early books). Java's Math class is a good example of a utility-style singleton.

The problem with the make-everything-static approach to singleton creation is that all the information needed to create the object must be known at class-load time, and that isn't always possible. Java's Toolkit is a good example. An application must load a different Toolkit than an applet, but a given chunk of code doesn't know whether it's running in an application or an applet until runtime. The actual instance of the toolkit is brought into existence by calling the static method Toolkit.getDefaultToolkit(). The object itself doesn't exist until the method is called the first time. Subsequent calls return a reference to the object that's created by the first call.

Critical sections

Bringing a singleton into existence at runtime (rather than at load-time) is fraught with peril in a multithreaded environment. You can implement the creation function naively as follows:

public static synchronized Singleton get_instance()
{   if( instance == null )
        instance =  new Singleton();
    return instance;
}

The static synchronized method forms a critical section -- a block of code that can be executed by only one thread at a time. If get_instance() weren't synchronized, a thread could be preempted after the if statement was processed, but before the instance=new Singleton() was executed. The preempting thread could then call get_instance(), create an instance, and yield. The preempted thread would then wake up, think that there were no instances (because it has already performed the test), and create a second instance of the object. The "critical section" eliminates the multiple-creation problem by preventing any thread from entering get_instance() if any other thread is already inside the method. Any singleton object can be used to implement a critical section. Here, the Class object whose monitor we're using is itself a singleton, so by locking this object implicitly when we enter the static method, we prevent other threads from executing the method in parallel. (All synchronized static methods actually are critical sections when you look at them that way.)

This strategy of using the Class object's monitor as the critical-section lock doesn't always work out because you lock all the static methods of the class, not just the singleton-creation method. You can do the same thing with an explicitly declared singleton lock as follows:

private static Object lock = new Object();
public static Singleton get_instance()  // not synchronized
{   synchronized( lock )
    {   if( instance == null )
            instance =  new Singleton();
        return instance;
    }
}

This version still assures that only one instance of the singleton will be created, but it won't interfere with the execution of other static methods.

The main problem with this naive approach is efficiency. We acquire the lock every time we call get_instance(), even though the code only needs to be locked the first time the method is called. The solution to this problem is Doug Schmidt's "double-checked locking" strategy. Here's the general pattern:

class Singleton
{
   private Singleton instance;
    //...
   public static Singleton get_instance()  // not synchronized
    {   if( instance == null )
        {   synchronized( Std.class )
            {   if( instance == null )
                    instance =  new Singleton();
            }
        }
        return instance;
    }
}

Most of the time, the object will exist when get_instance() is called, so we won't do any synchronization at all. On the first call, however, instance is null, so we enter the if statement and synchronize explicitly on the Class object to enter a critical section. Now we have to test for instance==null again, because we might have been preempted just after the first if was processed but before the synchronized statement was executed. If instance is still null, then no other thread will be creating the singleton, and we can create the object safely.

Listing 1 shows you a real-world application of a singleton that compensates for a problem in the design of the System class. A proper OO design never uses public fields except for symbolic constants, and I really mean "constant" here: The exposed field must be immutable, not just final. (An object accessed via a final reference can be modified; an "immutable" object (like a String) can't be modified at all.) This rule applies to both "class" and "instance" variables, and there are no exceptions to this rule. Ever. Period. Strong encapsulation of an object's implementation is so central to what "object orientation" means, that this point is simply not negotiable. If you use public fields, your program just isn't object oriented -- it's some sort of part-OO/part-procedural polyglot, and you will reap virtually none of the real benefits of OO such as improved maintenance. The only legitimate public members of a class are those methods that handle messages defined in your design's dynamic-model.

The foregoing notwithstanding, there is one place in the Java packages where instance variables are exposed: System.in, System.out, and System.err. To my mind, this exposure is a serious design flaw: These fields are not Reader or Writer derivatives, so they are not internationalizable. Consequently, you can't use these variables without wrapping them in a Reader or Writer. If System.in, System.out, and System.err had been accessed through "accessor" methods rather than directly, this wrapping could have been done transparently by the (missing) method that returned the I/O stream. This method could have easily been modified to return a PrintWriter rather than a PrintStream without impacting much of the code that used it. As it is, there's a lot of incorrect code out there that uses the three streams directly.

Listing 1 solves the problem (or at least hides it) by using the Singleton pattern. You write to standard output, for example, like this: Std.out().println("Hello world"); The out() method (Listing 1, line 33) creates a singleton PrintWriter wrapper around System.out and returns it. Subsequent calls to Std.out() return the same wrapper object, so you don't have to create a new one every time you need to write a string.

Other methods in the class work the same way: Std.err() returns a singleton PrintWriter that wraps System.err, and Std.in() returns a BufferedReader that wraps System.in. I've also provided a Std.bit_bucket() that returns an implementation of PrintWriter that does nothing. This is occasionally useful for throwing away otherwise undesirable output. For example, you might pass a method a Writer onto which it prints error or status messages. Passing this method Std.bit_bucket() causes the messages to not be printed.

Note, by the way, that the Bit_bucket class (Listing 1, line 61) is private, but it extends PrintWriter -- a public class -- overriding all the methods with no-ops. This notion of a private class implementing a public interface is a useful one. The outside world sees a Bit_bucket object as a Print_writer, knowing nothing about its actual implementation -- not even its class name. Though it doesn't do it here, the private inner class can define a set of methods that comprise a private interface to the outer class. This way the outer-class object can communicate with the inner-class object using methods that nobody else can access.

Listing 1: /src/com/holub/tools/Std.java
001  
002  
003  
004  
package com.holub.tools;
import java.io.*;
import com.holub.asynch.JDK_11_unloading_bug_fix;
/** A convenience class that takes care of wrapping a writer around
 |    standard output.
 */
005  
006  
007  
008  
009  
010  
011  
012  
013  
014  
public final class Std
{
   static{ new JDK_11_unloading_bug_fix(Std.class); }
   private static BufferedReader input;        //= null
   private static PrintWriter    output;       //= null
   private static PrintWriter    error;        //= null
   private static PrintWriter    bit_bucket;   //= null
    /*******************************************************************
     |    A private constructor, prevents anyone from manufacturing an instance.
     */
015  
016  
  private Std(){}
    /*******************************************************************
     |    Get a BufferedReader that wraps System.in
     */
017  
018  
019  
020  
021  
022  
023  
024  
025  
026  
027  
028  
029  
030  
031  
032  
  public static BufferedReader in()
    {
        if( input == null )
            synchronized( Std.class )
            {   if( input == null )
                    try
                    {   input = new BufferedReader(
                                        new InputStreamReader(System.in));
                    }
                    catch( Exception e )
                    {   throw new Error( e.getMessage() );
                    }
            }
        return input;
    }
    /*******************************************************************
     |    Get a PrintWriter that wraps System.out.
     */
033  
034  
035  
036  
037  
038  
039  
040  
041  
  public static PrintWriter out()
    {   if( output == null )
            synchronized( Std.class )
            {   if( output == null )
                    output = new PrintWriter( System.out, true );
            }
        return output;
    }
    /*******************************************************************
     |    Get a PrintWriter that wraps System.err.
     */
042  
043  
044  
045  
046  
047  
048  
049  
050  
051  
  public static PrintWriter err()
    {   if( error == null )
            synchronized( Std.class )
            {   if( error == null )
                    error = new PrintWriter( System.err, true );
            }
        return error;
    }
    /*******************************************************************
     |    Get an output stream that just discards the characters that are sent to it.
     */
052  
053  
054  
055  
056  
057  
058  
059  
060  
  public static PrintWriter bit_bucket()
    {   if( bit_bucket == null )
            synchronized( Std.class )
            {   if( bit_bucket == null )
                    bit_bucket = new Bit_bucket();
            }
        return bit_bucket;
    }
    /**
     |    The Bit_bucket class overrides all methods of PrintWriter to do nothing.
     */
061  
062  
063  
064  
065  
066  
067  
068  
069  
070  
071  
072  
073  
074  
075  
076  
077  
078  
079  
080  
081  
082  
083  
084  
085  
086  
087  
088  
089  
090  
091  
092  
093  
094  
095  
096  
097  
098  
099  
100  
101  
102  
103  
104  
105  
  private static final class Bit_bucket extends PrintWriter
    {
       private Bit_bucket()
        {   super( System.err );    // have to pass it something legal. Is never used.
        }
       public void    close()                              {}
       public void    flush()                              {}
       public void    print(boolean b)                     {}
       public void    print(char c)                        {}
       public void    print(char[] s)                      {}
       public void    print(double d)                      {}
       public void    print(float f)                       {}
       public void    print(int i)                         {}
       public void    print(long l)                        {}
       public void    print(Object o)                      {}
       public void    print(String  s)                     {}
       public void    println()                            {}
       public void    println(boolean b)                   {}
       public void    println(char c)                      {}
       public void    println(char[] s)                    {}
       public void    println(double d)                    {}
       public void    println(float f)                     {}
       public void    println(int i)                       {}
       public void    println(long l)                      {}
       public void    println(Object o)                    {}
       public void    write(char[] buf)                    {}
       public void    write(char[] buf, int off, int len)  {}
       public void    write(int c)                         {}
       public void    write(String buf)                    {}
       public void    write(String buf, int off, int len)  {}
    }
   static public class Test
    {
       static public void main( String[] args ) throws IOException
        {   String s;
            while( (s = Std.in().readLine()) != null )
            {   Std.out().println( s );
                Std.err().println( s );
                Std.bit_bucket().println( s );
            }
        }
    }
}

The final thread-related subtlety is the static initializer block (Listing 1, line 8):

    static{ new JDK_11_unloading_bug_fix(Std.class); } 

The JDK_11_unloading_bug_fix class in Listing 2 gets around a bug in the VM released with all versions of JDK 1.1. The VM in those releases was much too aggressive about unloading (and garbage collecting) Class objects: If the only reference to an object of a given class was a self-referential static member of the Class object, then the VM would unload the class from memory, thereby destroying our only copy of the singleton. The next time someone tried to get an instance, the class would be reloaded and a second instance of the singleton would be created. Sometimes this behavior did nothing but make the program a little slower. But if the act of creating the singleton object has side effects (like creating temporary files or opening data-base connections ), this second creation can be a problem.

The fix in Listing 2 is a kluge, but it works. I'm counting on the fact that the VM itself keeps around references to potentially active threads. If the current program is not running under a 1.1 version of the JDK System.getProperty("java.version").startsWith("1.1") ) is false, nothing at all happens. If version 1.1 is active, the JDK_11_unloading_bug_fix's constructor creates a Thread derivative whose one field holds a reference to the Class object passed in as an argument. The thread's run() method immediately suspends itself by calling wait(). Since there never will be a notify(), the thread doesn't use up any machine cycles, but since the Thread object isn't garbage collected, the Class-object reference will continue to exist, preventing the class from being unloaded. The created thread is given "daemon" status so that its existence won't stop the program from terminating when the non-daemon threads shut down.

Listing 2 (/src/com/holub/asynch/JDK_11_unloading_bug_fix.java): Fixing the 1.1 JDK's unloading problem
01  
02  
package com.holub.asynch;
/**
 |    
(c) 1999, Allen I. Holub.

This code may not be distributed by yourself except in binary form, incorporated into a java .class file. You may use this code freely for personal purposes, but you may not incorporate it into any commercial product without getting my express permission in writing.

This class provides a workaround for a bug in the JDK 1.1 VM that unloads classes too aggressively. The problem is that if the only reference to an object is held in a static member of the object, the class is subject to unloading, and the static member will be discarded. This behavior causes a lot of grief when you're implementing a singleton. Use it like this:

   class Singleton
    {   private Singleton()
        {   new JDK_11_unloading_bug_fix(Singleton.class);
        }
        // ...
    }

In either event, once the "JDK_11_unloading_bug_fix" object is created, the class (and its static fields) won't be unloaded for the life of the program.

 */
03  
04  
05  
06  
07  
08  
09  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
public class JDK_11_unloading_bug_fix
{
   public JDK_11_unloading_bug_fix( final Class the_class )
    {   
        if( System.getProperty("java.version").startsWith("1.1") )
        {
            Thread t = new Thread()
           {   private Class singleton_class = the_class;
               public synchronized void run()
                {   try{ wait(); }catch(InterruptedException e){}
                }
            };
            t.setDaemon(true);  // otherwise the program won't shut down
            t.start();
        }
    }
}

Reader/writer locks

And now for something completely different...

Controlling access to a shared resource such as a file or a data structure in a multithreaded environment is a commonplace problem. Typically, you'd like to allow any number of threads to simultaneously read from or otherwise access a resource, but you want only one thread at a time to be able to write to or otherwise modify the resource. That is, read operations can go on in parallel, but write operations must be serialized -- and reads and writes can't go on simultaneously. Moreover, it's nice if the write requests are guaranteed to be processed in the order they are received so that sequential writes to a file, for example, are indeed sequential.

The simplest solution to this problem is to lock the entire data structure -- just synchronize everything. But this approach is too simplistic to be workable in the real world. With most resources (such as data structures and file systems), there's absolutely no problem with multiple threads all accessing a shared resource simultaneously, provided the resource isn't modified while it's being accessed. If the "read" operations were all synchronized methods, though, no thread could read while another was in the process of reading: You'd effectively serialize the read operations.

This problem is solved using a reader/writer lock. An attempt to acquire the lock for reading will block only if any write operations are in progress, so simultaneous read operations are the norm. An attempt to acquire the lock for writing will block while ether read or write operations are in progress, and the requesting thread will be released when the current read or write completes. Write operations are serialized (on a first-come, first-served basis in the current implementation), so that no two writing threads will be permitted to write simultaneously. Readers who are waiting when a writer thread completes are permitted to execute (in parallel) before subsequent write operations are permitted.

Listing 3 implements a reader/writer lock that behaves as I've just described. Generally, you'll use it like this:

public class Data_structure_or_resource
{
    Reader_writer lock = new Reader_writer();
   public void access( )
    {       try
        {   lock.request_read();
                // do the read/access operation here.       }
        finally
        {   lock.read_accomplished();
        }
    }
   public void modify( )
    {       try
        {   lock.request_write();
                // do the write/modify operation here.       }
        finally
        {   lock.write_accomplished();
        }
    }
}

I've also provided nonblocking versions of request_write() (request_immediate_write(), Listing 3, line 65) and request_read() (request_immediate_read(), Listing 3, line 24), which return error flags (false) if they can't get the resource, but these are not used as often as the blocking forms.

The implementation logic is straightforward, and requires a surprisingly small amount of code. (Most of Listing 3 is made up of comments and a test routine.) I keep a count of the number of active readers -- readers that are in the process of reading (active_readers (Listing 3, line 8)). This count is incremented when a reader requests the lock, and is decremented when the reader releases the lock. If a writer thread comes along and requests access to the resource while reads are in progress, we have to wait for the active readers to finish before the writer can be let loose. A lock is created (on line 49), and the requesting thread is made to wait() on that lock. These locks are queued up in the writer_locks linked list (Listing 3, line 12). If any additional reader threads come along while a writer is waiting, they are blocked (by a wait() on line 20) until the current batch of readers and the waiting writer have finished. (The waiting_readers field [Listing 3, line 9] keeps track of how many readers are blocked, waiting for access.) Same goes with additional writers that come along at this point; they're just added to the queue of waiting writers, blocked on a roll-your-own lock.

As the readers finish up, they call read_accomplished() (Listing 3, line 32), which decrements the active_readers count. When that count goes to zero, the first writer in the queue is released. That thread goes off and does its thing, then it calls write_accomplished() (Listing 3, line 74). If any readers have been patiently waiting while all this is going on, they're released all at once at this point (they're all waiting on the current Reader_writer object's internal condition variable). When that batch of readers finishes reading, the process just described is repeated, and the next batch of readers is released. If no readers are waiting when a writer completes, then the next writer in line is released.

Listing 3 (/src/com/holub/asynch/Reader_writer.java): A reader/writer lock
001  
002  
003  
004  
package com.holub.asynch;
import java.util.LinkedList;
/**
 |    
(c) 1999, Allen I. Holub.

This code may not be distributed except in binary form, incorporated into a java .class file. You may use this code freely for personal purposes, but you may not incorporate it into any commercial product without getting my express permission in writing.

This reader/writer lock prevents reads from occurring while writes are in progress, and it also prevents multiple writes from happening simultaneously. Multiple read operations can run in parallel, however. Reads take priority over writes, so any read operations that are pending while a write is in progress will execute before any subsequent writes execute. Writes are guaranteed to execute in the order in which they were requested -- the oldest request is processed first.

You should use the lock as follows:

   public class Data_structure_or_resource
    {
        Reader_writer lock = new Reader_writer();
        public void access( )
        {           try
            {   lock.request_read();
                    // do the read/access operation here.           }
            finally
            {   lock.read_accomplished();
            }
        }
        public void modify( )
        {           try 
            {   lock.request_write();
                    // do the write/modify operation here.           }
            finally
            {   lock.write_accomplished();
            }
        }
    }

This implementation is based on the one in Doug Lea's

Concurrent Programming in Java

(Addison Wesley, 1997, pp. 300-303), I've simplified the code (and cleaned it up) and added the nonblocking acquisition methods. I've also made the lock a standalone class rather than a base class from which you have to derive. You might also want to look at the very different implementation of the reader/writer lock in Scott Oaks and Henry Wong's

Java Threads

(O'Reilly, 1997, pp. 180-187).

@author Allen

I. Holub

 */
005  
006  
007  
008  
009  
010  
011  
public class Reader_writer
{
   private int active_readers;     // = 0
   private int waiting_readers;    // = 0
   private int active_writers;     // = 0
    /******************************************************************
     |    I keep a linked list of writers waiting for access so that I can release them in the order that the requests were received. The size of this list is the "waiting writers" count. Note that the monitor of the Reader_writer object itself is used to lock out readers while writes are in progress, thus there's no need for a separate "reader_lock."
     */
012  
013  
  private final LinkedList writer_locks = new LinkedList();
    /******************************************************************
     |    Request the read lock. Block until a read operation can be performed safely. This call must be followed by a call to read_accomplished() when the read operation completes.
     */
014  
015  
016  
017  
018  
019  
020  
021  
022  
023  
  public synchronized void request_read()
    {
        if( active_writers==0 && writer_locks.size()==0 )
            ++active_readers;
        else
        {   ++waiting_readers;
           try{ wait(); }catch(InterruptedException e){}
        }
    }
    /******************************************************************
     |    This version of read() requests read access and returns true if you get it. If it returns false, you may not safely read from the guarded resource. If it returns true, you should do the read, then call read_accomplished in the normal way. Here's an example:
   public void read()
    {   if( lock.request_immediate_read() )
        {   try
            {
                // do the read operation here
            }
            finally
            {   lock.read_accomplished();
            }
        }
        else
            // couldn't read safely.
    }

     */
024  
025  
026  
027  
028  
029  
030  
031  
  public synchronized boolean request_immediate_read()
    {
        if( active_writers==0 && writer_locks.size()==0 )
        {   ++active_readers;
            return true;
        }
        return false;
    }
    /******************************************************************
     |    Release the lock. You must call this method when you're done with the read operation.
     */
032  
033  
034  
035  
  public synchronized void read_accomplished()
    {   if( --active_readers == 0 )
            notify_writers();
    }
    /******************************************************************
     |    Request the write lock. Block until a write operation can be performed safely. Write requests are guaranteed to be executed in the order received. Pending read requests take precedence over all write requests. This call must be followed by a call to write_accomplished() when the write operation completes.
     */
036  
037  
038  
039  
040  
041  
042  
043  
044  
045  
046  
047  
048  
049  
050  
051  
052  
053  
054  
055  
056  
057  
058  
059  
060  
061  
062  
063  
064  
  public void request_write()
    {
        // This method can't be synchronized or there'd be a nested-monitor
        // lockout problem: We have to acquire the lock for "this" in
        // order to modify the fields, but that lock must be released
        // before we start waiting for a safe time to do the writing.
        // If request_write() were synchronized, we'd be holding
        // the monitor on the Reader_writer lock object while we were
        // waiting. Since the only way to be released from the wait is
        // for someone to call either read_accomplished()
        // or write_accomplished() (both of which are synchronized),
        // there would be no way for the wait to terminate.
       Object lock = new Object();
        synchronized( lock )
        {   synchronized( this )
            {   boolean okay_to_write = writer_locks.size()==0 
                                        && active_readers==0
                                        && active_writers==0;
                if( okay_to_write )
                {   ++active_writers;
                    return; // the "return" jumps over the "wait" call
                }
                writer_locks.addLast( lock );
            }
            try{ lock.wait(); } catch(InterruptedException e){}
        }
    }
    /******************************************************************
     |    This version of the write request returns false immediately (without blocking) if any read or write operations are in progress and a write isn't safe; otherwise, it returns true and acquires the resource. Use it like this:
  public void write()
    {   if( lock.request_immediate_write() )
        {   try
            {
                // do the write operation here
            }
            finally
            {   lock.write_accomplished();
            }
        }
        else
            // couldn't write safely.
    }

     */
065  
066  
067  
068  
069  
070  
071  
072  
073  
  synchronized public boolean request_immediate_write()
    {
        if( writer_locks.size()==0  && active_readers==0
                                    && active_writers==0 )
        {   ++active_writers;
            return true;
        }
        return false;
    }
    /******************************************************************
     |    Release the lock. You must call this method when you're done with the read operation.
     */
074  
075  
076  
077  
078  
079  
080  
081  
082  
083  
084  
085  
086  
087  
088  
  public synchronized void write_accomplished()
    {
        // The logic here is more complicated than it appears.
        // If readers have priority, you'll  notify them. As they
        // finish up, they'll call read_accomplished(), one at
        // a time. When they're all done, read_accomplished() will
        // notify the next writer. If no readers are waiting, then
        // just notify the writer directly.
        --active_writers;
        if( waiting_readers > 0 )   // priority to waiting readers
            notify_readers();
        else
            notify_writers();
    }
    /******************************************************************
     |    Notify all the threads that have been waiting to read.
     */
089  
090  
091  
092  
093  
094  
  private void notify_readers()       // must be accessed from a
    {                                   //  synchronized method
        active_readers  += waiting_readers;
        waiting_readers = 0;
        notifyAll();
    }
    /******************************************************************
     |    Notify the writing thread that has been waiting the longest.
     */
095  
096  
097  
098  
099  
100  
101  
102  
103  
104  
  private void notify_writers()       // must be accessed from a
    {                                   //  synchronized method
        if( writer_locks.size() > 0 )
        {   
            Object oldest = writer_locks.removeFirst();
            ++active_writers;
            synchronized( oldest ){ oldest.notify(); }
        }
    }
    /*******************************************************************
     |    The Test class is a unit test for the other code in the current file. Run the test with:
   java com.holub.asynch.Reader_writer\$Test

(the backslash isn't required with windows boxes), and don't include this class file in your final distribution. The output could vary in trivial ways, depending on system timing. The read/write order should be exactly the same as in the following sample:
   Starting w/0
                    w/0 writing
    Starting r/1
    Starting w/1
    Starting w/2
    Starting r/2
    Starting r/3
                    w/0 done
    Stopping w/0
                    r/1 reading
                    r/2 reading
                    r/3 reading
                    r/1 done
    Stopping r/1
                    r/2 done
                    r/3 done
    Stopping r/2
    Stopping r/3
                    w/1 writing
                    w/1 done
    Stopping w/1
                    w/2 writing
                    w/2 done
    Stopping w/2

     */
105  
106  
107  
108  
  public static class Test
    {
        Resource resource = new Resource();
        /**
         |    The Resource class simulates a simple locked resource. The read operation simply pauses for .1 seconds. The write operation (which is typically higher overhead) pauses for .5 seconds. Note that the use of try...finally is not critical in the current test, but it's good style to always release the lock in a finally block in real code.
         */
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
      static class Resource
        {   Reader_writer lock = new Reader_writer();
           public void read( String reader )
            {   try
                {   lock.request_read();
                    System.out.println( "\t\t" + reader + " reading" );
                    try{ Thread.currentThread().sleep( 100 ); }
                    catch(InterruptedException e){}
                    System.out.println( "\t\t" + reader + " done" );
                }
                finally
                {   lock.read_accomplished();
                }
            }
           public void write( String writer )
            {   try
                {   lock.request_write();
                    System.out.println( "\t\t" + writer + " writing" );
                    try{ Thread.currentThread().sleep( 500 ); }
                    catch(InterruptedException e){}
                    System.out.println( "\t\t" + writer + " done" );
                }
                finally
                {   lock.write_accomplished();
                }
            }
           public boolean read_if_possible()
            {   if( lock.request_immediate_read() )
                {   
                    // in the real world, you'd actually do the read here
                    lock.read_accomplished();
                    return true;
                }
                return false;
            }
           public boolean write_if_possible()
            {   if( lock.request_immediate_write() )
                {   
                    // in the real world, you'd actually do the write here
                    lock.write_accomplished();
                    return true;
                }
                return false;
            }
        }
        /**
         |    A simple reader thread. Just reads from the resource, passing it a unique string id.
         */
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
      class Reader extends Thread
       {   private String name;
            Reader( String name ){ this.name = name; }
           public void run( )
            {   
                System.out.println("Starting " + name );
                resource.read( name );
                System.out.println("Stopping " + name );
            }
        }
        /**
         |    A simple writer thread. Just writes to the resource, passing it a unique string id.
         */
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
      class Writer extends Thread
       {   private String name;
            Writer( String name ){ this.name = name; }
           public void run()
            {   
                System.out.println("Starting " + name );
                resource.write( name );
                System.out.println("Stopping " + name );
            }
        }
        /**
         |    Test by creating several readers and writers. The initial write operation (w/0) should complete before the first read (r/1) runs. Since readers have priority, r/2 and r/3 should run before w/1; and r/1, r/2 and r3 should all run in parallel. When all three reads complete, w1 and w2 should execute sequentially in that order.
         */
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
      public Test()
        {
            if( !resource.read_if_possible() )
                System.out.println("Immediate read request didn't work");
            if( !resource.write_if_possible() )
                System.out.println("Immediate write request didn't work");
            new Writer( "w/0" ).start();
            new Reader( "r/1" ).start();
            new Writer( "w/1" ).start();
            new Writer( "w/2" ).start();
            new Reader( "r/2" ).start();
            new Reader( "r/3" ).start();
        }
       static public void main( String[] args )
        {   Test t = new Test();
        }
    }
}

It's a wrap

So, that's it for the part of this series that discusses what I think of as the "low-level" thread-related problems. The toolkit I've developed over the past few months should put you well on the way to solving many thorny issues that crop up in every multithreaded program. But we're not done yet.

If you've been following this series from the beginning, you're probably asking yourself why you ever thought that programming with threads was a good idea. There's just so much complexity, and the bugs are so hard to find. Fortunately, there is a general solution to both problems: good architecture. It's possible to design a program for multithreading in such a way that many of the synchronization issues I've been discussing become immaterial. (Which is not to say that synchronization-related problems don't pop up regularly, even when the overall system is well designed. I regularly use all those semaphores and locks we've been looking at for the last few months. With the proper architecture, though, synchronization issues do tend to move to the background). Next month I'll start looking at architectural solutions to threading problems, with a discussion of thread pools and synchronous dispatching.

Allen Holub has been working in the computer industry since 1979. He is widely published in magazines (Dr. Dobb's Journal, Programmers Journal, Byte, MSJ, among others). He has seven books to his credit, and is currently working on an eighth that will present the complete sources for a Java compiler written in Java. After eight years as a C++ programmer, Allen abandoned C++ for Java in early 1996. He now looks at C++ as a bad dream, the memory of which is mercifully fading. He's been teaching programming (first C, then C++ and MFC, now OO-Design and Java) both on his own and for the University of California Berkeley Extension since 1982. Allen offers both public classes and in-house training in Java and object-oriented design topics. He also does object-oriented design consulting and contract Java programming. Get information, and contact Allen, via his Web site http://www.holub.com.

Learn more about this topic

  • Bill Venners discussed static members, though without much coverage of the implementation issues, in his Design Techniques column, "Design with static members" http://www.javaworld.com/javaworld/jw-03-1999/jw-03-techniques.html
  • The Singleton pattern is presented in the "Gang of Four" (or GoF) bookErich Gamma, Richard Helm, Ralph Johnson, and John Vlissides's Design Patterns Elements of Reusable Object-Oriented Software (Reading, MAAddison Wesley, 1995). This book is essential reading for any OO designer.
  • John Vlissides's Pattern HatchingDesign Patterns Applied (Reading, MAAddison Wesley, 1998) also has a lot to say about singletons in Chapter 2 and the first section of Chapter 3.
  • The double-checked locking strategy for singleton creation is described in "Double-Checked Locking" by Douglas C. Schmidt and Tim Harrison, Pattern Languages of Program Design 3 (Reading, MAAddison Wesley, 1998, pp. 363-375).
  • Reader/writer locks are described in Doug Lea's Concurrent Programming in Java (Reading, MAAddison Wesley, 1997, pp. 300-303). My implementation is based on Lea's.
  • Reader/writer locks are also described in Scott Oaks and Henry Wong's Java Threads (Sebastopol, CAO'Reilly, 1997, pp. 180-187).
Join the discussion
Be the first to comment on this article. Our Commenting Policies