Lock on to an alternate synchronization mechanism

Learn how to implement a reader/writer lock for flexible protection

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.

1 2 3 Page 1
Page 1 of 3