[concurrency-interest] Read-write-update lock

Niall Gallagher niall at npgall.com
Fri Jul 19 07:21:43 EDT 2013


I guess it must have been discussed when ReentrantReadWriteLock was being written, the limitation that the read lock cannot be upgraded to a write lock.

Two threads hold a read lock, both then try to acquire the write lock -> deadlock. So if a read-mostly thread might ever need write access, it must either hold a write lock for the whole time (blocking other concurrent readers for its whole duration), or it must drop the read lock before acquiring the write lock, with the risk that another thread might steal the write lock from it rendering any data it read as stale.

I've written an extension to the basic readers-writer lock concept: a read-write-update lock for Java: ReentrantReadWriteUpdateLock in Concurrent-Locks on Google Code[1].

I was wondering if people on this mailing list would like to code review it, or get involved in the project, before I make a 1.0 release to Maven Central?

The idea for a read-write-update lock is not new. I see a reference to it on the Linux kernel mailing list from circa 2000 here[2]. Maybe the concept goes by other names also?

Some differences between my implementation and the Linux kernel mailing list discussion: 
- My implementation is reentrant, which means you actually can acquire the Mutex again if you already hold a Write lock
- I didn't see any reason for Nothing -> Update to acquire both the Mutex and Read locks, so my implementation only acquires Mutex (which is enough to prevent other threads acquiring the Write lock anyway). In fact if it did acquire both, deadlock would occur in reentrant scenario Nothing -> Update (lock Mutex, lock Read), Update -> Update (lock Mutex again, lock Read again) followed by Update -> Write (drop Read, but hold count remains at 1, lock write = deadlock).

There is also an implementation of CompositeLock in the project for group-locking and group-unlocking collections of locks with rollback support, which I plan to use for locking nodes in hierarchical structures such as trees (I'm the author of Concurrent-Trees[3]).

For ReentrantReadWriteUpdateLock I re-used the JDK ReentrantReadWriteLock as much as possible, so you'll see the code is quite simple. So another question is do you think this kind of R-W-U-Lock might ever make it into the JDK, or is it still too esoteric?

Best regards,

Niall Gallagher

[1] Concurrent-Locks: Read-write-update / upgradable read-write locks for Java

[2] Linux kernel mailing list: Read/Write locks that can be changed into each other

[3] Concurrent-Trees: Concurrent Radix and Concurrent Suffix Trees for Java

More information about the Concurrency-interest mailing list