Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

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

JavaWorld.com

Programming Java threads in the real world, Part 7

Singletons, critical sections, and reader/writer locks

By Allen Holub, JavaWorld.com, 04/01/99

  • Print
  • Feedback
.

Page 5 of 5

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  

    /*******************************************************************
      |      A private constructor, prevents anyone from manufacturing an instance. 
     */

015  
016  

    /*******************************************************************
      |      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


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  

    /******************************************************************
      |      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  

    /******************************************************************
      |      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.

About the author

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.
  • Print
  • Feedback

Resources
  • 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).