Abstract

We use a read/write lock manager to illustrate some advanced Java thread programming techniques, and some pitfalls of thread programming.

Introduction

A read/write lock manager allows a server to manage its data resource for client read and write requests. We implement a simple read/write lock manager in Java as a thread programming example.

Let's review the difference between a read lock, and a write lock. The following table lists the different locking levels, and the compatibilities between each locking levels.

A read lock is required before reading on a data item. A write lock is required before writing on a data item. Multiple parties can read on a data item with no problem. This is indicated in the table by looking at the intersection of requested lock (read), and already granted lock (read also). We should find the 'yes' compatibility label in the intersection. On the other hand, one cannot write on a data item while there are still readers out there. Similarly, one cannot read on a data item while there is a writer out there. For practice, look up these two statements in the compatibility table.

A Simple Java Read/Write Lock Manager

Because the lock manager is going to be used as an example, this is a limited implementation which lefts out some advanced features. However, the basic feature set is quite usable.

1. Locking a lock more than once is not supported.
2. Lock upgrading is not supported.
3. Can recover from a client dying while holding a lock.
4. Competition lock granting policy is used.

Sample Usages

Any client that want to access a data item should first obtain a read lock, then after the data item is read, release the lock.

Any client that want to write a data item should first obtain a write lock, then after the data item is written, release the lock.

public class Person
{
  int age;
  rwLockMgr lockmanager;
  public Person()
  {
    age = 17;
    lockmanager = new rwLockMgr();
  }
  public int getAge()
  {
    lockmanager.lockRead();
    return age;
  }
  public void putAge(int newage)
  {
    lockmanager.lockWrite();
    age = newage;
  }
  public void releaseLock()
  {
    lockmanager.releaseLock();
  }
}

Source Code

001   import java.util.*;
002   /* a lock manager supporting read locks and write locks */
003   public class rwLockMgr
004   {
005     Object readerQueue = new Integer(0); // reader wait queue
006     Object writerQueue = new Integer(0); // writer wait queue
007     HashSet ownerTable = new HashSet(); // owner table
008     int ownerType; // 0 - read lock, 1 - write lock
009   
010     /* wake up a reader */
011     private void wakeReader()
012     {
013       synchronized(this.readerQueue)
014       {
015         this.readerQueue.notify(); // wake up 1 reader
016       }
017     }
018   
019     /* wake up a writer */
020     private void wakeWriter()
021     {
022       synchronized(this.writerQueue)
023       {
024         this.writerQueue.notify(); // wake up 1 writer
025       }
026     }
027   
028     /* release held lock */
029     public synchronized void releaseLock()
030     {
031       ownerTable.remove(Thread.currentThread());
032       if (ownerTable.size() == 0) // no more owners
033       {
034         // let the reader and writer compete
035         this.wakeReader();
036         this.wakeWriter();
037       }
038       else if (ownerType == 0)
039       {
040         this.wakeReader(); // owner is reader, admit more reader
041       }
042     }
043   
044     /* request write lock */
045     public void lockWrite()
046     {
047       int loopcount = 0;
048       for (;;)
049       {
050         synchronized(this)
051         {
052           if ((loopcount != 0) && (ownerTable.size() > 0))
053           {
054             // see if any of the owner thread has died
055             Iterator it = this.ownerTable.iterator();
056             while (it.hasNext())
057             {
058               Thread th = (Thread) it.next();
059               if (! th.isAlive()) it.remove(); // remove dead owner
060             }
061           }
062           if (ownerTable.size() == 0) // no owners
063           {
064             Thread mythread = Thread.currentThread();
065             this.ownerTable.add(mythread);
066             this.ownerType = 1; // owner is write type
067             return;
068           }
069         }
070         synchronized(this.writerQueue)
071         {
072           try
073           {
074             this.writerQueue.wait(3000L); // 3 second sleep in writer queue
075           }
076           catch (InterruptedException e) {}
077         }
078         ++loopcount;
079       }
080     }
081   
082     /* request read lock */
083     public void lockRead()
084     {
085       int loopcount = 0;
086       for (;;)
087       {
088         synchronized(this)
089         {
090           if ((loopcount != 0) && (ownerTable.size() > 0))
091           {
092             // see if any of the owner thread has died
093             Iterator it = this.ownerTable.iterator();
094             while (it.hasNext())
095             {
096               Thread th = (Thread) it.next();
097               if (! th.isAlive()) it.remove(); // remove dead owner
098             }
099           }
100           if ((ownerTable.size() == 0) || (ownerType == 0))
101           {
102             // OK to grab read lock
103             Thread mythread = Thread.currentThread();
104             this.ownerTable.add(mythread);
105             this.ownerType = 0; // owner is read type
106             this.wakeReader(); // wake up 1 fellow reader
107             return;
108           }
109         }
110         synchronized(this.readerQueue)
111         {
112           try
113           {
114             this.readerQueue.wait(3000L); // 3 second sleep in reader queue
115           }
116           catch (InterruptedException e) {}
117         }
118         ++loopcount;
119       }
120     }
121
122     /* returns true if current thread owns a lock */
123     public synchronized boolean isOwner()
124     {
125       return this.ownerTable.contains(Thread.currentThread());
126     }
127   }

Lock the Control Data Structure First

The first thing you should notice is that the control data structure is locked before the subroutines reads or writes to the data structure. Look at line 123; the subroutine is synchronized even if it only reads the data structure. This is absolutely necessary. Not locking a read subroutine can cause dirty data to be read.

Use Java Object to Simulate Wait Queue

A Java object in combination to wait() and notify() can be used to simulate a wait queue. Actually going ahead and implementing a queue of threads can be an over-kill.

The lock manager has 3 synchronized regions: one for the control data structure, one for the read wait queue, and one for the write wait queue. It is very important to release the lock on control data structure when a thread goes to sleep on the wait queues (line 70, and line 110). If the thread goes to sleep and still holds the control data lock, then the system will be deadlocked.

Competition Based Policy versus Hard-Wired Policy

When a resource becomes available, which client should be granted access to it? The best answer may just be: any one! Using a more sophisticated policy may bring more trouble than it is worth.

For example, the lock manager has two wait queues: the read wait queue, and the write wait queue. From which queue should we grant the lock request to? If we always dispatches readers, then writers can be starved. If we always dispatches writers, then readers can be starved. What if we implement a strict first in, first serve policy? That can also be trouble, because of the well known convoy issue. A client can have only one operation with a resource before being kicked to the back of the queue, making the scheduler too busy.

Competition based policy simply allows the interested clients race to grab the resource. The first one to reach the resource gets it. This kind of policy can be attractive because high priority threads automatically gains more power to grab a resource without any extra programming effort.

In the example program, you will see on line 35, and line 36 that one client from the reader queue, and one client from the writer queue are dispatched. They compete to grab the resource. The read queue may have a very slight advantage because it is dispatched first. To be strictly fair, the order of the launch may have to be flipped every other time.

Avoid the Thundering Herd

The difference between notify() and notifyAll() is that notify() wakes up one thread waiting on an object, while notifyAll() wakes up all threads waiting on an object.

If there is only one resource, waking up all clients would just cause most of them to go back to sleep immediately. In this case, wake up the client one at a time.

Even when waking up everyone seems safe, there may be alternative arrangements that are better. It may appear safe when releasing a read lock to wake up all waiting readers. However, what if before any of the readers can get the lock, a writer grabs the lock. That means all the readers have to go back to sleep again.

In the example program, if you look at line 106, once a reader obtains a read lock, it dispatches a fellow reader to join in. No thundering herd here.

Avoid Unnecessary Locks

In the example program, the owner table is implemented by HashSet (line 7). If we implement the owner table with Hashtable when there would be unnecessary locks present. The difference is that HashSet is not synchronized, while Hashtable is synchronized. Because we are already synchronizing on the control data structure, we don't need to synchronize on the hash table again.

Handling Client Death

It is possible for a client to die before going through the protocol completely. An example would be the client grabs a write lock, and the client dies before it could release the lock. Robust thread programming requires graceful recovery from client death.

For the case of a wait queue implemented by wait() / notify() pair, no clean up is required. The Java VM automatically takes care of threads that die while sleeping.

For other data structures that contains thread references, clean up is required. Look at line 52; if the system has been blocked for a while, it checks to see of any of the lock owners are dead, and cleans them up from the data structure.

Wake Up Periodically to Retry Operation

The ability to clean up from dead client is enhanced by codes that automatically retry operations periodically. Look at line 74, and 114; if the client sleeps forever, then client death recovery becomes troublesome again.

Before you put in an obj.wait() statement, think about if it is better to retry the operation periodically via obj.wait(long).

Put Recovery Code in the Slow Path

Because recovery code is generally slow, it may be necessary to avoid putting recovery code in the performance critical fast path. Look at line 52, and line 90; we only recover from client death if the system has been blocked for 3 seconds.

Use Synchronized Blocks, Don't Avoid It by Tricky Programming

Many threading codes fail because they employ tricky programming to avoid synchronized blocks. On-the-fly initialization, and the so called double-checked-idiom are very hard to get right. Many Java JVMs do not support double-checked-idioms, so I am not even explaining what it is.

A common signaling mechanism is to change a member variable in one thread, and have a second thread read that member variable, all without any synchronization. When synchronizations are not present, the Java memory specification is ambiguous enough to allow the reader to obtain garbage value, and fail as a result. Better safe than sorry.

References

James Gosling, Bill Joy, Guy Steele, "The Java Language Specification", Addison Wesley, (1996)

David R. Butenhof, Programming with POSIX Threads, Addison Wesley, 1997

Paul Jakubik, "Multiprocessor Safety and Java", 1999

William Pugh, "Fixing the Java Memory Model", Proceedings of the Java Grande Conference, June 12-14, 1999