Programming Java threads in the
real world, Part
3 - JavaWorld -
November 1998
Tutorial Details:
Programming Java threads in the real world, Part 3
Programming Java threads in the real world, Part 3
By: By Allen Holub
Roll-your-own mutexes and centralized lock management
n last month's column , I demonstrated a simple deadlock scenario using two nested synchronized blocks that acquired the same two locks, but in a different order. (Please review last month's example if this isn't fresh in your mind.) This month, I'll take a look at a solution to this commonplace deadlock problem, presenting a roll-your-own exclusion semaphore class and a lock manager that supports the safe acquisition of multiple semaphores. Using these objects rather than the built-in synchronized can save you hours of searching for unexpected deadlocks. (They don't solve every possible deadlock problem, of course, but are nonetheless pretty useful.)
When 'synchronized' isn't good enough
The nested- synchronized -statements example from last month was -- admittedly -- contrived, but the multiple-lock situation comes up frequently in the real world. One common problem is the too-coarse, object-level granularity of the synchronized keyword: there's only one monitor per object, and sometimes that's not enough.
Consider the following class, the methods of which can be broken up into three partitions. The methods in the first partition use only a subset of the fields in the class. The methods in the second partition use a non-overlapping subset; they share fields that are not used by methods in the first partition. The methods in the third partition use everything.
1| class Complicated // NOT thread safe
2| {
3| private long a, b;
4| private long x, y;
5|
6| // partition 1, functions use a and/or b
7|
8| public void use_a() { do_something_with(a); ); }
9| public void use_b() { do_something_with(b); ); }
10 public void use_a_and_b() { do_something_with(a+b); ); }
11|
12| // partition 2, functions use x and/or y
13|
14| public void use_x() { do_something_with(x); ); }
15| public void use_y() { do_something_with(y); ); }
16| public void use_x_and_y() { do_something_with(x+y); ); }
17|
18| // partition 3, functions use a, b, x, and y
19|
20| public void use_everything() { do_something_with( a +
x ); }
21| public void use_everything_else(){ do_something_with( b +
y ); }
22| }
As it stands, this code is a multithreading disaster. Nothing is synchronized and we have guaranteed race conditions. (A race condition occurs when two threads try to access the same object at the same time, and chance determines which one wins the "race." Programs shouldn't work by chance.) Synchronizing all the methods would fix the problem, but then you couldn't call a method in partition 1 (emphasized in the code above) simply because some thread was using a method from partition 2 above. Since these two partitions don't interact with each other, this solution imposes needless access restrictions on the methods of the class. If you're accessing any method in partition 3, though, you do want to lock out everything in the other two partitions. We really need two locks in this situation. One to lock partition-1 variables and another for partition-2 variables. The methods in partition 3 can then grab both locks.
So, roll your own
You can implement the two-lock strategy by synchronizing on something other than the containing object. Rather than synchronizing the methods, you can define two local variables to use as locks and synchronize on them:
1| class Complicated_and_thread_safe
2| {
3| private long a, b;
4| private long x, y;
5|
6| private Object ab_lock = new int[];
7| private Object xy_lock = new int[];
8|
9| // partition 1, functions use a and/or b
10|
11| public void use_a() { synchronized(ab_lock){
/*...*/ } }
12| public void use_b() { synchronized(ab_lock){
/*...*/ } }
13| public void use_a_and_b(){ synchronized(ab_lock){
/*...*/ } }
14|
15| // partition 2, functions use x and/or y
16|
17| public void use_x() { synchronized(xy_lock){
/*...*/ } }
18| public void use_y() { synchronized(xy_lock){
/*...*/ } }
19| public void use_x_and_y(){ synchronized(xy_lock){
/*...*/ } }
20|
21| // partition 3, functions use a, b, x, and y
22|
23| public void use_everything()
24| { synchronized(ab_lock) // grab both locks
25| { synchronized(xy_lock)
26| { /*...*/
27| }
28| }
29| }
30|
31| public void use_everything_else()
32| { synchronized(ab_lock)
33| { synchronized(xy_lock)
34| { /*...*/
35| }
36| }
37| }
38| }
I haven't synchronized the methods themselves in this example. (Remember, synchronizing a method is effectively the same thing as wrapping all the code in the method in a synchronized(this){...} block.) Instead, I'm providing a unique lock for each partition ( ab_lock and xy_lock ) and then explicitly synchronizing on these individual locks.
Java associates locks with objects (instance of some class that extends Object , so I can't use primitive-type variables as locks here. I don't want to spend unnecessary time calling constructors and doing other initialization operations on complicated objects, however. Consequently, the locks themselves are declared as the simplest possible Object -- an array.
Arrays in Java are first-class objects: they implicitly extend the Object class. (If you don't believe me, compile the following code:
1| public class foo
2| { static Object ref = new int[]{ 10 };
3|
4| public static void main( String[] args )
5| { System.out.println( ref.toString() );
6| }
7| }
The class compiles just fine. Not only does the implicit cast from the array to Object work (because Object is a base class of all arrays), but the println() correctly invokes the compiler-generated toString() override (which prints absolutely nothing useful -- but you can't have everything). I've used a one-element array for my lock, rather than something like an Integer , because arrays come into existence very efficiently. For example, there's no constructor call.
In the foregoing example, it's critical that methods that acquire both locks always acquire them in the same order, otherwise we end up in the Wilma-and-Betty deadlock scenario discussed last month . Acquiring multiple locks is a commonplace enough problem that some operating systems have system calls for this purpose. It would be nice to have an easy way to acquire multiple locks, in Java, without having to worry about the order-of-acquisition problem. The remainder of this month's column describes one way to do that.
Semaphores
Listing 1 shows the core interface I use for all my roll-your-own semaphore classes: the Semaphore . It's in the com.holub.asynch package, as are all the thread-related classes and interfaces I'll be discussing. (I've also put all the code that appears in the listings into the "Goodies" section on my Web site; see Resources for the link.)
1| package com.holub.asynch;
2|
3| interface Semaphore
4| {
5| int id ();
6| void acquire(long timeout) throws InterruptedException;
7| void release();
8| }
Listing 1: Semaphore.java
If you haven't worked much with semaphores, a semaphore has to have two properties in order to be useful:
It must be able to identify itself using a unique ID when passed an id() request. The current implementation uses a unique integer for the purpose.
You must be able to acquire and release the semaphore, though the semantic meaning of "acquire" and "release" can vary, depending on what sort of semaphore you're dealing with.
Managing the locks
Any semaphore that implements Semaphore can be locked in groups using the Lock_manager class shown in Listing 2. There are several things going on here. First of all, I've used the Arrays.sort() method, one of the new JDK 1.2 data-structure facilities, to make life easier. The Arrays class is a "Booch utility" -- a class that contains nothing but static methods. The java.lang.Math utility is another example. In fact, the Lock_manager itself is a utility, since it's made up solely of static methods.
01| package com.holub.asynch;
02|
03| import com.holub.asynch.Semaphore;
04| import java.util.Arrays;
05| import java.util.Comparator;
06|
07| class Lock_manager
08| {
09| private static int[] id_lock = new int[1];
10| private static int id_pool = 0;
11|
12| public static int new_id( )
13| {
14| int id;
15| synchronized( id_lock ) {
16| id = id_pool++; }
17| return id;
18| }
19|
20| /**
21| * Every mutex is given a unique int ID when it's created.
22| * This function returns once all of the locks in the incoming
23| * array have been successfully acquired. Locks are always
24| * acquired in ascending order of ID to attempt to avoid
25| * deadlock situations.
26| *
27| * @param locks All of these locks must be acquired before
28| * acquire_multiple returns.
29| * @param timeout Maximum time to wait to acquire each
30| * lock (milliseconds). The total time for the multiple
31| * acquire operation could be (timeout * locks.length).
32| **/
33|
34| public static void acquire_multiple( Semaphore[] locks, long timeout )
35| throws InterruptedException
36| { try
37| {
38| Arrays.sort(locks, new Lock_comparator() );
39| for( int i = 0; i < locks.length; ++i )
40| locks[i].acquire( timeout ) ;
41| }
42| catch( Comparable.Not_comparable e )
43| {
44| // shouldn't happen. Convert it to an uncaught
45| // exception to terminate the program.
46|
47| throw new Error( e.toString() );
48| }
49| }
50|
51| private static class Lock_comparator implements Comparator
52| { public int compare(Object a, Object b)
53| throws Comparable.Not_comparable
54| { return ((Semaphore)a).id() - ((Semaphore)b).id();
55| }
56| public boolean equals(Object obj)
57| { return obj instanceof Lock_comparator;
58| }
59| }
60| }
Listing 2: Lock_manager.java
"Booch utilities"
Digressing for a moment, in most object-oriented languages, utilities are kludges needed to get around design problems in the language itself or in existin
Read
Tutorial at: Click here to view the tutorial
Rate Tutorial: Programming Java threads in the
real world, Part
3 - JavaWorld -
November 1998
View Tutorial: Programming Java threads in the
real world, Part
3 - JavaWorld -
November 1998
Related
Tutorials:
 Integrating Databases
Integrating Databases
|
Programming Java threads in the
real world, Part
8
Programming Java threads in the
real world, Part
8
|
How to write
a Java Card applet: A developer's
guide
How to write
a Java Card applet: A developer's
guide
|
I want my AOP!, Part 1
I want my AOP!, Part 1
|
I want my AOP!,
Part 2
I want my AOP!,
Part 2
|
I want my AOP!, Part 3
I want my AOP!, Part 3
|
Achieve strong performance with threads,
Part 1
Achieve strong performance with threads,
Part 1
|
Achieve strong performance with threads,
Part 2
Achieve strong performance with threads,
Part 2
|
Rumble in the
jungle: J2EE versus .Net, Part
1
Rumble in the
jungle: J2EE versus .Net, Part
1
|
J2SE 1.4
breathes new life into the CORBA community, Part
1
J2SE 1.4
breathes new life into the CORBA community, Part
1
|
Check out three
collections libraries
Check out three
collections libraries
|
Effort on the
edge, Part 1
Effort on the
edge, Part 1
|
J2SE 1.4.1
boosts garbage
collection
J2SE 1.4.1
boosts garbage
collection
|
Datastructures and algorithms, Part 1
Datastructures and algorithms, Part 1
|
Add concurrent processing with message-driven beans
Add concurrent processing with message-driven beans
|
Fixing the Java Memory Model, Part 2
Writing concurrent code is hard to begin with; the language should not make it any harder. While the Java platform included support for threading from the outset, including a cross-platform memory model that was intended to provide \"Write Once, Run Anywh
|
Real World HTML Parser
Real World HTML Parser
The two fundamental use-cases that are handled by the parser are extraction and transformation (the syntheses use-case, where HTML pages are created from scratch, is better handled by other tools closer to the source of data). Whil
|
JDBC scripting, Part 2
JDBC scripting, Part 2
Programming and Java scripting in JudoScript
Summary
JudoScript is a rich functional scripting language, and an easy and powerful general programming and Java scripting language.
JudoScript's power comes from its synergy of
|
The ABCs of Synchronization, Part 1
Threads may execute in a manner where their paths of execution are completely independent of each other. Neither thread depends upon the other for assistance. For example, one thread might execute a print job, while a second thread repaints a window. And
|
Understanding MIDP System Threads
Describes the multi-threaded aspects of the J2ME application environment. Understanding the interactions between systems threads, user-interface and application threads will help in avoiding MIDlet deadlock.
|
|
|
|
