|
|
Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs
Page 2 of 5
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:
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.
See Highlights of the reader/writer lock implementation for an overview of the lock.
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:
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.
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 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.
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.
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.
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: