Programming Java threads in the real world, Part 7

Singletons, critical sections, and reader/writer locks

1 2 3 4 Page 4
Page 4 of 4
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).
1 2 3 4 Page 4
Page 4 of 4