Reader-Writer locks and fair scheduling

We take a brief detour from kitchen remodeling.

I've been considering using a reader-writer lock in a project I'm doing at the office, but I'm concerned about the fair scheduling problem. So let's define those terms, briefly:

• A reader-writer lock is a synchronization primitive which is more sophisticated that the simple mutual-exclusion lock. With a mutual-exclusion lock, only one thread at a time is allowed to enter the critical section. With a reader-writer lock, callers must identify themselves as readers or writers; multiple readers may enter the critical section simultaneously, but a writer may only enter the critical section alone.

• Fair scheduling ensures that waiting threads aren't starved of access to the critical section. Many naive implementations of the reader-writer lock suffer from write starvation, in which a writer may wait an arbitrarily long time if readers continue to arrive at the critical section while the writer is waiting.

There are a variety of possible scheduling policies that can be used once threads begin to contend for a reader-writer lock.

It's interesting that the JDK 1.6 ReentrantReadWriteLock provides an execution mode which supports fair scheduling:

When constructed as fair, threads contend for entry using an approximately arrival-order policy. When the currently held lock is released either the longest-waiting single writer thread will be assigned the write lock, or if there is a group of reader threads waiting longer than all waiting writer threads, that group will be assigned the read lock.

The Sun JDK documentation for the ReadWriteLock class has a nice summary of the design issues to consider when investigating the use of a reader-writer lock for concurrency.