Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

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

JavaWorld.com > Java Development Tools >

Lock on to an alternate synchronization mechanism

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

By Tarak Modi, JavaWorld.com, 07/14/00

  • Print
  • Feedback
.

Page 5 of 5

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.

About the author

Tarak Modi, a lead systems architect at Online Insight, is part of a team responsible for setting, directing, and implementing the vision and strategy of the company's product offering from a technology and architectural perspective. A certified Java programmer, he has several years of experience working with Java, C++, and technologies such as EJB, CORBA, and DCOM. Tarak holds a bachelor's in EE, a master's in computer engineering, and an MBA with a concentration in IS.
  • Print
  • Feedback

Resources
  • Source code
  • Books