Wednesday, November 3, 2010

Unfairs Fair

This conundrum was on our internal mailing lists:

Take a ReentrantReadWriteLock. One thread calls readLock(), gets the lock and calls lock() on it.

A second calls writeLock() and also calls lock(). The first thread still holds the read lock so the write lock blocks. No surprises there.

But then a third thread also gets a read lock and tries to call lock() on it and it too blocks - even though it is a read lock.

Surprised? Why should a read block when a fellow read holds the lock? Doesn't the JavaDocs for the ReadWriteLock interface say:

"The read lock may be held simultaneously by multiple reader threads"


Well, this is a special case. Yes, usually if a read lock is being held then other reading threads can lock even if there is one or more writer threads attempting to take the write lock. This is true irrespective of the ReentrantReadWriteLock being fair or not.

The special case is this: if a read lock is held but the next bid for the lock comes from an attempt to attain a write lock, subsequent read locks will block and wait for the write operation to complete.

You won't find this in the JavaDocs but in a small comment in the ReentrantReadWriteLock.NonfairSync code. I found this snippet from Sun's 1.6.05 implementation while stepping through the code to diagnose this behaviour:

final boolean readerShouldBlock(Thread current) {

/* As a heuristic to avoid indefinite writer starvation,

* block if the thread that momentarily appears to be head

* of queue, if one exists, is a waiting writer. This is

* only a probablistic effect since a new reader will not

* block if there is a waiting writer behind other enabled

* readers that have not yet drained from the queue.


return apparentlyFirstQueuedIsExclusive();


This may or may not be the case on other JVMs.

No comments:

Post a Comment