[concurrency-interest] Read-write-update lock

Nathan Reynolds nathan.reynolds at oracle.com
Fri Jul 19 13:27:46 EDT 2013


I ran into upgrading a lock problem a while back.  The solution I took 
is first have the thread read acquire the lock.  Then if the thread 
detects that it needs the write lock, it releases the read lock and 
starts over by acquiring the write lock.  Of course, all of the data the 
thread collected in the read lock is considered invalid.  This greatly 
improved scalability and the "upgrade" didn't hurt performance.  This is 
because  writes mostly happen at start up and are rare otherwise.

The above logic works great and there hasn't been a need for a 
read-write-update lock.  The problem in my situation is that I can't 
predict at the time of acquiring the lock if I will need to do any 
writes.  The thread has to check the protected state and then decide if 
any writes are necessary.  (I would guess this scenario is true of most 
caches.)  If all threads do update acquires, then I am back to the same 
contention I had with all threads doing write acquires.

I haven't needed this kind of lock.  Every time I run into lock 
contention, I always solve the problem without it.  If I had such a lock 
in my toolbox, maybe I would select it.

Can you give a good example of where update acquires can actually help?  
A toy example is one method which always needs to do reads and another 
method which has to do a lot of reads with a very small portion to do 
writes.  The first method is called very frequently relative to the 
second method.  Is there such a situation in software?

-Nathan

On 7/19/2013 4:21 AM, Niall Gallagher wrote:
> Hi,
>
> 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
> www.npgall.com
>
> [1] Concurrent-Locks: Read-write-update / upgradable read-write locks for Java
>      http://code.google.com/p/concurrent-locks/
>
> [2] Linux kernel mailing list: Read/Write locks that can be changed into each other
>      http://lkml.indiana.edu/hypermail/linux/kernel/0004.3/0117.html
>
> [3] Concurrent-Trees: Concurrent Radix and Concurrent Suffix Trees for Java
>      http://code.google.com/p/concurrent-trees/
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130719/a4092135/attachment-0001.html>


More information about the Concurrency-interest mailing list