| April 1999 |
| Get FREE JW e-mail alerts | ||
|
|
Programming Java threads in the real world, Part 7
S Singletons, critical sections, and reader/writer locks
Summary
This month's column builds on the preceding installments of the Java Toolbox threads series, adding a few more tools to your multithreading arsenal. Columnist Allen Holub looks at reader/writer locks, which let multiple threads safely access a shared resource in an efficient way. (Multiple threads can read from the resource while only one thread at a time can write to it, and reads and writes can't occur at the same time.) He'll also discuss the Singleton pattern, with a focus on implementing it in a multithreaded environment, and critical sections, or blocks of code that can be executed by only one thread at a time. (5,300 words)
|
Mail this article to a friend
| |||
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 = ""> synchronized static public change_color_scheme( Color foreground, Color background ) { this.foreground = foreground; this.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 = ""> /*package*/ synchronized change_color_scheme( Color foreground, Color background ) { this.foreground = foreground; this.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 "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 Singleton
states:
Ensure a class only has one instance, and provide a global point of access to it.
and the "Consequences" section says:
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 = ""> private Color_scheme(){} /*package*/ synchronized static change_color_scheme( Color foreground, Color background ) { this.foreground = foreground; this.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 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.
|
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.
|
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.
|
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.
|
|
|
|
|
- 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) book: Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides's Design Patterns: Elements of Reusable Object-Oriented Software (Reading, MA: Addison Wesley, 1995). This book is essential reading for any OO designer.
- John Vlissides's Pattern Hatching: Design Patterns Applied (Reading, MA: Addison 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, MA: Addison Wesley, 1998, pp. 363-375).
- Reader/writer locks are described in Doug Lea's Concurrent Programming in Java (Reading, MA: Addison 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, CA: O'Reilly, 1997, pp. 180-187).
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.
Reach Allen at allen.holub@xxxxxxxxxxxxx.
What did you think of this article?
|
-Very worth reading -Worth reading -Not worth reading |
-Too long -Just right -Too short |
-Too technical -Just right -Not technical enough |
| Comments: | |
| Name: | |
| Email: | |
| Company Name: | |
If you have problems with this magazine, contact
webmaster@xxxxxxxxxxxxx
URL: http://www.javaworld.com/javaworld/jw-04-1999/jw-04-toolbox.html
Last modified: Friday, March 26, 1999