Lock on to an alternate synchronization mechanism

Software professionals have been debating multithreaded programming for quite some time now. The notion of threading is so ingrained within the Java platform that developers can rarely create even simple programs without inadvertently using threads. Although the built-in threading support within the Java platform has allowed developers to create powerful programs, it has also left its share of scarred developers. The most common hazards lie in event-handling and the access of AWT/JFC Swing components. Rudimentary as it is, Java’s built-in thread support is powerful enough to help build the most complex synchronization mechanisms required for commercial applications. The aim of this article is to illustrate that power by creating a reader/writer lock. The reader/writer lock implementation discussed here includes lock upgrade and downgrade capabilities. I’ll also examine enhancements such as lock-leasing, various performance improvement tips, and ways of dealing with issues such as priority inversion.

The reader/writer lock

I would like to clear up the fair amount of misconception that remains about the reader/writer lock. The name implies the presence of two distinct locks — one for reading and one for writing. However, that is not the case. A reader/writer lock is a single lock. Think of it as a lock with two levels, much like a building with two floors or a game with two levels — beginner and advanced.

A reader/writer lock can be acquired simultaneously by multiple threads as long as the threads only read from the shared resource that the lock is protecting. If the thread wants to write or modify the shared resource, only one thread at a time can acquire the lock.

That lock is useful if the read operation is lengthy, and no reason presents itself in preventing other threads from reading the shared resource at the same time — reading a file, reading the value of a static class variable, or reading a row from a table in a database, as examples. However, to ensure data integrity, only one thread can modify the shared resource. While it is making changes, no other threads are allowed access to the resource, even to read it. Thus, no other thread sees any intermediate changes or values of the shared resource.

Consider a list of all the names of people who have ever lived on the face of the earth as an example. The list is singly-linked, meaning traversal is possible in only one direction. Since it is a list, no random access is allowed. The list of names is huge — several billion people long, at least. Searching for a particular individual in such a list is time-consuming in itself. Now imagine a million clients accessing the list continuously, each one either looking for an individual, or inserting a newly born person in the list, or both. The simplest multithreaded program would synchronize on the list during the search and insert operations. But that means that we have serialized all access to the list, thereby foregoing almost all benefits bestowed upon us by Java’s multithreaded capability.

The example above, although contrived in nature, goes a long way in showing the usefulness of a reader/writer lock. Having multiple clients search the list at the same time is permitted; we really want to serialize only the inserts. That scenario is a perfect match for the reader/writer lock.

I have selected the reader/writer lock as the subject of this article for three reasons:

1. The reader/writer lock is an extremely powerful tool in the toolkit of a developer who deals with the challenges of a multithreaded environment. It provides an elegant solution to a common problem. Without the reader/writer lock, some complex combination of other more primitive synchronization mechanisms would have to be used.

2. In my opinion, the reader/writer lock is one of the more complex synchronization mechanisms. There are several reasons for that. First, as explained above, there is much confusion caused by the name itself. Second, it encompasses most of the functionality of a semaphore, a barrier, and a mutex. In other words, once you create a reader/writer lock, creating those other synchronization mechanisms should be a breeze.
3. Most example implementations that I have come across have been incomplete in terms of the lock’s features. For example, lock upgrading/downgrading has been left up to the reader. However, the design of the lock does not really lend itself to the incorporation of lock upgrading/downgrading. The implementation provided in this article is a fully functional reader/writer lock.

See Highlights of the reader/writer lock implementation for an overview of the lock.

The interface definition

Since I am a firm believer in separating behavior semantics from implementation specifics, let’s begin by defining the interface that will, in turn, define the contract for the reader/writer lock. The separation of behavior semantics and implementation allows us to switch lock implementations without affecting client code that depends on those locks.

RwLock.java illustrates the interface. The definitions of the exceptions thrown are found in InvalidWaitTime.java, UpgradeNotAllowed.java, and LockNotHeld.java. Those four files, along with all of the source code, can be downloaded as a zip file in Resources.

The semantics description for each method of the RWLock interface follows:

The forReading() method

There are two flavors of forReading(). The first flavor does not have any parameters and blocks access until the read lock is obtained. The second flavor takes a zero-based parameter in milliseconds to indicate the time to wait. For example, a 0 value indicates no wait at all, 1,000 indicates a 1-second wait, and so on. If the wait time specified is invalid, -100 for example, then an InvalidWaitTime exception is thrown. Finally, if the lock is obtained without timing out, a true value is returned to the calling thread.

The forWriting() method

forWriting() is similar to the forReading() method, except that it obtains the write lock. If a thread that already owns a read lock calls that method, the implementation should try to upgrade the lock. If the implementation does not allow upgrades, the method throws an UpgradeNotAllowed exception.

The upgrade() method

The two flavors of upgrade() behave similarly to the previous methods. As the name implies, upgrade() upgrades a read lock to a write lock. If the thread calling that method does not already own the lock, a LockNotHeld exception is thrown. If the lock implementation does not support that feature, it throws an UpgradeNotAllowed exception. As in the previous methods, if the wait time specified is invalid, then an InvalidWaitTime exception is thrown. If the lock held is already a write lock, no error occurs, and the call simply returns. Also, threads that already own a read lock are given a higher priority to receiving their write lock than those threads that do not own any lock. Finally, if the lock upgrades without timing out, a true value returns to the calling thread.

The downgrade() method

Since downgrade() can never block, it requires only one flavor. It downgrades a write lock to a read lock. If the thread calling that method does not already own the lock, a LockNotHeld exception is thrown. If the lock held is already a read lock, no error occurs and the call simply returns. If the lock is a write lock, it downgrades to a read lock. Threads waiting for read locks now receive them only if allowed. For example, if there is a thread waiting for a write lock before a thread waiting for a read lock, the thread waiting for the read lock cannot be granted its desired lock. Finally, if the lock downgrades, a true value returns to the calling thread.

The release() method

Similar to the downgrade() method, only one flavor exists for release(), as it also can never block. A thread relinquishing ownership of its lock calls that method. If the thread calling that method does not already own the lock, release() throws a LockNotHeld exception. When a lock releases, those threads waiting for locks receive them. Every forWriting() and forReading() invocation must also have a corresponding release() invocation. However, upgrade() and downgrade() calls do not have corresponding release() calls. That method has no return value.

Implementation details

Now let’s look at the implementation of the lock. The implementation discussed here requires JDK 1.2 or higher. RWLockImpl.java features that code in its entirety (see the accompanying zip file in Resources). The implementation of all the methods strictly adhere to the behavior contract specified by the RWLock interface.

The class RWLockImpl implements the RWLock interface. The constructor takes a parameter that toggles the upgrade() capability on/off (the default constructor turns the upgrade() capability off). I have also extended the Java linked list, which is part of the java.util package and implements the java.util.List interface. That is a doubly-linked list. Methods to randomly access elements of the list are provided, but internally the list still traverses sequentially from the beginning to the end to obtain to the element. Also, the list is not thread safe.

I have added three new methods to the linked list:

1. findMe(), to find the element in the linked list corresponding to the current thread
2. firstWriterIndex(), to find the very first writer
3. lastGrantedIndex(), to find the very last element that has a granted lock

We will see the use of those three methods when we implement the forReading(), forWriting(), upgrade(), downgrade(), and release() methods. That linked list serves as the queue in which threads waiting to obtain a lock are placed. Each element in that linked list is of type WaitingListElement. Each element is created by a thread. That thread’s ID is the key to its corresponding element. I have overridden the equals() method in the WaitingListElement class to define two elements as equal if their keys are equal.

forReading() and forWriting() methods delegate their no argument versions to their argument taking siblings. (That was too easy; I like that delegation stuff.)

The forReading() method

Let’s look at the forReading() (the argument-taking version) method implementation. That method tries to find the element corresponding to the thread on which the call is being made. If an element is not found, forReading() creates a new one and adds it to the waiting list. If an element is found, that indicates that the thread already owns a lock. It does not matter whether the lock owned is read or write, since the write lock includes read as part of it. Therefore, the lock count increases and the method returns. If the read lock cannot be granted, the thread waits if instructed to do so, as indicated by the wait-time parameter passed into the method call. Each time the thread wakes up, either because it timed out or because it was notified to wake up, it checks the condition to see if the read lock can be granted. That is referred to as the double-checked locking pattern. (see Chapter 20, “Double-Checked Locking” by Doug Schmidt and Tim Harrison in Pattern Languages of Program Design 3 [Software Patterns Series], Robert C. Martin, Dirk Riehle, Frank Buschmann, and John Vlissides in Resources for a discussion of that pattern.) Double-checked locking prevents erroneous locking conditions. Finally, if the lock cannot be obtained due to a time-out, a false value is returned to the method caller. Before returning that false value, the method cleans up the waiting list by removing the element corresponding to the calling thread from the list. We also notify all waiting threads so that they can be granted locks if possible.

The forWriting() method

Now, let’s look at the forWriting() (again, the argument-taking version) method implementation. It performs similar functions as the forReading() implementation, with a few exceptions. A thread is granted a write lock only when the element corresponding to that thread is the first in line, that is, there are no other threads with locks. In that case, when searching the waiting list for an element corresponding to that thread, the lock type matters. There are two cases to consider. If the lock type is for writing, the method simply returns with a true value. If the lock type is for reading, an attempt is made to upgrade the lock. If that attempt succeeds, the lock count increases, and the method returns a true value to the caller. That process may fail either because upgrades are not allowed by the implementation or because of a timeout. If either occurs, the method returns a false value.

The upgrade() method

upgrade() is probably the trickiest method. Since a thread can only upgrade a lock if it owns one in the first place, an element corresponding to the calling thread must be in the waiting list. If an element does not exist, a LockNotHeld exception is thrown. If the thread already owns a write lock, the method returns. However, if the thread owns a read lock, we must do two things.

First, we must find the last read lock that was granted in the waiting list. Place the element for that thread behind the element corresponding to the last granted read lock that we found. That process is important because there may be other threads that were granted read locks after the calling thread and we cannot upgrade until those locks are released. Note that a write lock cannot be waiting in the queue. Because the thread making the call has a read lock, no other thread can have a write lock. All threads wanting a write lock would have to wait until all read locks are released. That is in tune with the way a reader/writer lock works.

Second, we update the type of lock to write so that new threads coming in to receive a read lock are blocked. Now we proceed in a similar way to obtaining a write lock from scratch. Finally, if the upgrade failed due to a timeout, we set the lock type back to read and notify all waiting threads so that they can be granted read or write locks if possible.

The downgrade() method

The downgrade() method is more straightforward. Like the upgrade() method, the calling thread must own a lock to call downgrade(), otherwise a LockNotHeld exception is thrown. All the waiting threads are notified when a write lock is downgraded. That allows other threads to be granted read or write locks when possible.

The release() method

Finally, let’s look at the release() method. As in the upgrade() and downgrade() methods, the calling thread must own a lock to call that method; otherwise it throws a LockNotHeld exception. Each time a thread calls release(), the lock count decreases. When the lock count drops to zero, all the waiting threads are notified so that they can receive read or write locks if possible.

Test the reader/writer lock implementation

Test.java, is an example test program that exercises the implementation’s functionality. Test.log provides the output produced by the test program. Both of those files can be downloaded in Resources.

I have tested the reader/writer lock on Windows NT 4.0 (SP5) on my laptop, which has a PII 400 MHz processor with 288 MB of RAM, and on Solaris 2.6 on a Sun Ultra-2, with two 400 MHz UltraSPARC-II processors and 512 MB of RAM. In both cases, I used the Sun Microsystems JVM that comes with the JDK 1.2.2 download. Testing on the Solaris box included both native and green threads.

Assuming that all the threads (1 through 7) begin in order, let’s trace the program flow.

1. The program starts off by creating thread 1 to receive a read lock.
2. Thread 1 receives the read lock.
3. Thread 2 wants a write lock. It blocks because thread 1 already has a read lock.
4. Threads 3, 4, and 5 each want a read lock, but block because thread 2 is in line ahead of them, waiting for a write lock.
5. Thread 6 wants a write lock, and thread 7 wants a read lock. Both threads block. Hence, currently all threads except thread 1 are blocked.
6. After 2 seconds, thread 1 releases its lock, allowing thread 2 to get the write lock.
7. All other threads still block since no other threads can obtain any lock while another thread has a write lock.
8. After 2 more seconds, thread 2 then releases its lock.
9. Threads 3, 4, and 5 simultaneously receive the read locks.
10. Thread 4 wants to upgrade but has to wait because of threads 3 and 5. However, thread 4 still has priority over thread 6 for obtaining the write lock (as defined by the interface contract).
11. After yet another 2 seconds, threads 3 and 5 release their read locks, thus allowing thread 4 to upgrade.
12. Thread 4 then releases the write lock after 2 seconds.
13. Now thread 6 can receive the write lock. Thread 7, which wants a read lock, still blocks.
14. After 1 second, thread 6 downgrades its lock, and thread 7 receives a read lock.
15. After another 2 seconds, threads 6 and 7 release their locks.
16. Thread 2 illustrates how each forWriting() has a matching release call, and the additional release call generates a LockNotHeld exception.

The program does not test the wait time facility, which is fairly easy to verify. For example, have one thread receive a write lock to hold for 10 seconds. Have another thread try to receive a read lock now with a wait time of 2 seconds. The second thread will time out, which will be indicated by the false return value.

Enhance the reader/writer lock

There are several ways to improve upon that reader/writer lock implementation.

Build a lease mechanism

Currently, once a thread obtains a lock, that thread may keep the lock as long as it wants. Hence, at least two related problems result. First, what if the thread never releases the lock or prematurely ends (that is, dies) without releasing the lock? If the lock obtained by the misbehaving thread was a read lock, no other thread could obtain the write lock. Second, if the lock obtained by that thread was a write lock, no other thread could obtain any other read or write lock. That could be disastrous. To avoid that, build a leasing mechanism.

Instead of owning the locks permanently, interested threads lease — as one would lease a house or car — the locks for a set time period as indicated by the lease. If the lease is nearing its end and the thread still needs the lock, it can try renewing the lease. The reader/writer lock may deny a renewal, for example, it if determines that other threads in line need the lock. When a lease expires, the reader/writer lock seizes the lock from the thread.

You can easily incorporate a leasing mechanism by adding lease time and lease acquired fields in the WaitingListElement class and arrange for a thread to periodically wake up and check for expired leases. The signature of the forReading() and forWriting() methods could be changed to include an optional desired-lease-time parameter. Those methods could now return the actual lease, which may or may not be equal to the thread’s desired lease.

Make that lease-checking thread a daemon thread so that it only runs when no other significant processing is going on.

A new method renewLease(), which lock owners can call to renew an expiring lease, could be added as well.

An example implementation of incorporating that leasing mechanism is shown here (assuming that that thread class is an inner class of the lock implementation class):

public void run()
{
   // forever
   while(true)
   {
      // Note that we synchronize on the parent lock.
      // Assume this was passed in as a parameter
      // in the constructor.
      synchronized(parentLock)
      {
         ListIterator iter = waitingList.listIterator(0);
         boolean notifyRequired = false;
         while(iter.hasNext())
          {
             WaitingListElement e = (WaitingListElement)iter.next();
             if((e._lease+e._leaseAcquired) < System.currentTimeMillis())
             {
                 // Lease has expired,
                 // so remove from the list.
                 iter.remove()
                 notifyRequired = true;
             }     
         }
         if(notifyRequired)
         parentLock.notifyAll();                                
      }
      try
      {
         // You could make the sleep time configurable.
         sleep(5000);
      }
      catch(Exception e)
      {
      }
   }
}

An isValid() method could also be added to the reader/writer lock. A thread that owns a lock can call that method to ensure that it still owns a valid lease.

An example implementation of the isValid() method is shown here:

// A return value of false means that access 
// to the shared resource is denied.
synchronized public boolean isValid() 
{
   // If the lease had expired and the lease "cop" thread
   // has caught this, then we will not find this thread in
   // the list.
   // Or this thread never held a lock in the first place.
   // We cannot tell the difference and don't really care.
   int index = findMe();
   if(index == -1)
      return false;
   WaitingListElement e = waitingList.get(i);
   return ((e._lease + e._leaseAcquired) > System.currentTimeMillis());
}

Both the renewLease() and isValid() methods should be added to the RWLock interface.

Improve performance

Linked list usage

That execution of the reader/writer lock relies heavily on the linked-list implementation provided in the Java 2 language/platform. Also, the methods here use iterators to search the list. For a performance-intensive application, it may be replaced by a better-performing implementation. However, even with the current implementation using Java’s list, better performance may be achieved by using a for loop to iterate through the list. See Java 2 Performance and Idiom Guide, Craig Larman, Rhett Guthrie in Resources for a discussion.

Synchronize threads more efficiently

Currently when any lock is released or when a write lock is downgraded, notifyAll() wakes all waiting threads, which can be inefficient, especially with many waiting threads. Since determining which threads out of all the waiting threads can obtain a lock is fairly trivial, the downgrade() method can wake only the threads that will be able to proceed. One way of achieving that targeted wakeup is having each thread synchronize on a different object, such as on itself. Since each element in the waiting list has a reference to the thread that created it, we can use that reference to wake the individual thread.

Priority inversion

Currently, if there are threads that already have read locks, a thread trying to obtain a write lock will block. What happens if the thread seeking the write lock has a higher priority than the other threads? That is an example of priority inversion, and clearly not a desirable situation. After all, there is a reason the thread has a higher priority. To remedy the situation, temporarily boost all threads to match the priority of the blocked thread. Since we already keep track of all threads that have been granted locks, incorporating that enhancement would be fairly straightforward. Remember to unboost the priority in the release() method.

Conclusion

Multithreading is a powerful programming concept. With the added power however, comes additional responsibility and complexity. Java, by its platform-independent nature, adds another dimension, especially when using native threads, as they most likely will behave differently on each platform. The built-in threading support in Java serves as an excellent building block for creating more powerful higher-level synchronization mechanisms for a developer’s toolkit. In this article, I presented how to build a complete working implementation of the reader/writer lock using Java’s built-in threading support, along with a variety of enhancements to make the lock even better. Best of all, the design will accommodate those enhancements with little effort.

Source: www.infoworld.com