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.
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.