Programming Java threads in the real world, Part 3

Roll-your-own mutexes and centralized lock management

In 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:

  1. 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.

  2. 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 existing libraries. The problem in Java is that neither arrays nor primitive types really are true objects. If they were, they would contain all the methods needed to manipulate them. For example, you would be able to find a cosine using:

int x = PI;
x.cosine();

You'd also be able to extend int, and so forth. In the case of arrays, you ought to be able to sort them by asking them to sort themselves, like this:

int array[] = new int[];
//...
array.sort();

Unfortunately, Java isn't a "pure" object-oriented language in which everything is an object, so we have to make do with a utility class.

You can use the Arrays utility as follows to sort an array of int:

int array[] = new int[];
//...
Arrays.sort( array );

The problem is complicated a bit by arrays of objects of some arbitrary class. How can a generic sort utility figure out the correct ordering? The Object class contains an equals() function, but we'd need a greater_than() as well to do sorting.

The Strategy pattern

To the rescue comes the "Strategy" pattern. The notion is to pass into a method or object another object that encapsulates the strategy needed to do something. There are lots of examples of Strategy in Java. A java.awt.LayoutManager, for example, encapsulates the strategy that a Frame uses for laying itself out. You can change the layout simply by changing this strategy. You don't have to define a new kind of Frame class using derivation or some other mechanism. This, in turn, makes Frame much more "reusable" since the behavior of a Frame can be changed without changing any of the code that comprises Frame.

The Arrays utility uses the Strategy pattern to define a comparison strategy. In Listing 2, the Lock_comparator (at the bottom of the listing) implements the comparison strategy by implementing the new (to JDK 1.2) java.util.Comparator interface and its compare() method. (This works like C's strcmp(): it returns a negative number, zero, or a positive number depending on whether a is less than, equal to, or greater than b.) An instance of the Comparator is passed to the Arrays.sort() method like this:

Arrays.sort(locks, new Lock_comparator() );

The Lock_comparator object's compare() method is called by Arrays.sort() when it needs to compare objects. C programmers will recognize this approach as very similar to that of qsort(), which is passed a pointer to a compare method -- another example of Strategy.

How Lock_manager works

Now, let's look at what the Lock_manager actually does. It starts out with the static new_id() method that returns a unique int every time it's called. This method will be called from the various objects that implement the Semaphore interface to get the value they'll use for their ID.

The acquire multiple method is used to safely acquire groups of semaphores. You pass it an array of objects that implement Semaphore, it sorts the array by ID, and then acquires the semaphores one at a time in ID order. Consistent acquisition of multiple semaphores in ID order effectively eliminates the deadlock scenario we've been discussing.

A manageable mutex

Now let's move on and look at the other side of the equation: a class that implements a semaphore. The Mutex class in Listing 3 implements a simple mutual-exclusion semaphore. Whether it makes sense to use it (as compared to synchronizing on a lock object, as I did earlier) really depends on the situation. The main advantage is in being able to use the Lock_manager.acquire_multiple() to acquire several mutexes without worrying about an order-of-acquisition deadlock. I personally think the code also looks a little cleaner. I prefer this:

1| class some_class
2| {   
3|     private Mutex lock = new Mutex();
4| 
5|     public void f()
6|     {   lock.acquire();
7|         //...
8|         lock.release();
9|     }
10| }

to this:

1| class some_class
2| {
3|     private Object lock = new int[1];
4| 
5|     public void f()
6|     {   synchronized( lock )
7|         {
8|             //...
9|         }
10|     }
11| }

even though it's possible to forget the explicit release().

1| package com.holub.asynch;
2| 
3| import com.holub.asynch.Semaphore;
4| 
5| import com.holub.tools.Comparable;
6| import com.holub.tools.Sort;
7| 
8| // Implementation of a mutual-exclusion semaphore. It can be owned by
9| // only one thread at a time. The thread can acquire it multiple times,
10| // but there must be a release for every acquire.
11| 
12| public class Mutex implements Semaphore
13| {
14|     private Thread  owner      = null;  // Owner of mutex, null if nobody
15|     private int     lock_count = 0;
16| 
17|     private final int _id   = Lock_manager.new_id();
18|     public        int id()  {   return _id;         }
19| 
20|     /**
21|    * Acquire the mutex. The mutex can be acquired multiple times
22|    * by the same thread, provided that it is released as many
23|    * times as it is acquired. The calling thread blocks until
24|    * it has acquired the mutex. (There is no timeout).
25|    *
26|    * @see release
27|    * @see acquire_without_blocking
28|    */
29| 
30|     public synchronized void acquire( long timeout )
31|                                         throws InterruptedException
32|     {   while( acquire_without_blocking() == false)
33|             this.wait( timeout );
34|     }
35| 
36|     /**
37|    * Attempts to acquire the mutex. Returns false (and does not
38|    * block) if it can't get it.
39|    *
40|    * @see release
41|    * @see acquire
42|    */
43| 
44|     public synchronized boolean acquire_without_blocking()
45|     {
46|         // Try to get the mutex. Return true if you got it.
47| 
48|         if( owner == null )
49|         {   owner = Thread.currentThread();
50|             lock_count = 1;
51|             return true;
52|         }
53| 
54|         if( owner == Thread.currentThread() )
55|         {   ++lock_count;
56|             return true;
57|         }
58| 
59|         return false;
60|     }
61| 
62|     /**
63|    * Release the mutex. The mutex has to be released as many times
64|    * as it was acquired to actually unlock the resource. The mutex
65|    * must be released by the thread that acquired it
66|    *
67|    * @throws Mutex.OwnershipException (a RuntimeException) if a thread
68|    *      other than the current owner tries to release the mutex.
69|    */
70| 
71|     public synchronized void release()
72|     {
73|         if( owner != Thread.currentThread() )
74|             throw new OwnershipException();
75| 
76|         if( --lock_count <= 0 )
77|         {   owner = null;
78|             notify();
79|         }
80|     }
81| 
82|     public static class OwnershipException extends RuntimeException
83|     {   public OwnershipException()
84|         {   super("Thread calling release() doesn't own Mutex");
85|         }
86|     }
87| }

Listing 3: Mutex.java

Admittedly, this preference for the explicit call to acquire() is largely a matter of personal taste. We'll look at a few other semaphore implementations next month that are a bit harder to simulate with a simple synchronized, however.

Getting back to Listing 3, the Mutex class starts out with the stuff needed to keep the Lock_manager happy. It implements the Semaphore interface with an id() method that returns the value of the _id field, which in turn holds a unique value that came from the Lock_manager.

There are two versions of the acquire method: acquire() itself and acquire_without_blocking(). The latter simply returns false if it can't acquire the mutex. If the mutex isn't owned, it sets owner to reference the thread that called acquire_without_blocking() with the call to Thread.currentThread(), which does the obvious. The blocking version, acquire(), calls the nonblocking version and suspends itself with a wait() call if it can't get the mutex right off the bat. Note the use of a spin lock here. (I discussed spin locks last month.) The wait() call is inside a loop in case some other thread breaks in at an inopportune moment and steals the mutex.

Interestingly, the Mutex code doesn't actually use the Mutex object's monitor to implement the lock (though it does use the monitor to make sure that two threads don't try to acquire the same mutex simultaneously -- acquire() and release() are synchronized). A local field called owner is used to decide whether or not to block out an acquiring thread. The owner field references the Thread instance that contains the run() method for a given thread. If owner is null, the mutex is up for grabs, otherwise, some thread "owns" the mutex and any other thread that tries to acquire it will block at the wait() call in acquire().

My Mutex class implements a "recursive" mutex. The "owner" thread can acquire the mutex more than once, but it must release the mutex by calling release() as many times as it acquired it by calling acquire().

This facility is essential when two methods both must acquire the mutex. In the following code, for example, g() calls f(), but f() can also be called from outside -- without going through g() first. If the mutex weren't recursive, the thread that called g() would block when g() called f() and tried to acquire the mutex a second time. As it is, the double acquisition isn't a problem since every acquire() has a corresponding release(). The lock_count field keeps track of the number of times the mutex has been locked by its owner.

1| class some_class
2| {   Mutex lock = new Mutex();
3| 
4|     public void f()
5|     {   lock.acquire();
6|         //...
7|         lock.release();
8|     }
9| 
10|     public void g()
11|     {   lock.acquire();
12|         //...
13|         f();
14|         //...
15|         lock.release();
16|     }
17| }

Until next time

So that's a simple roll-your-own semaphore. Though it's easy enough to use Java's synchronized statement directly to do everything the Mutex does, the code is cleaner when you use the Mutex class, and the associated Lock_manager can solve a class of otherwise hard-to-manage deadlock problems.

Next month I'll look at a couple of other useful semaphores: a condition variable and a Djikstra counting semaphore. I'll also discuss critical sections and class-level locks. In future columns, we'll take a look at other thread-related classes, such as timers and reader/writer locks, and explore architectural solutions to threading-related problems.

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. Allen abandoned C++ for Java in early 1996 and 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. Get more information and contact Allen via his Web site http://www.holub.com.

Learn more about this topic

  • All the real code (the stuff in the com.holub.asynch package) is available in the "Goodies" section on my Web site http://www.holub.com
Join the discussion
Be the first to comment on this article. Our Commenting Policies