Java ReentrantReadWriteLocks - how to safely acquire write lock when in a read lock?

Question

I am using in my code at the moment a ReentrantReadWriteLock to synchronize access over a tree-like structure. This structure is large, and read by many threads at once with occasional modifications to small parts of it - so it seems to fit the read-write idiom well. I understand that with this particular class, one cannot elevate a read lock to a write lock, so as per the Javadocs one must release the read lock before obtaining the write lock. I've used this pattern successfully in non-reentrant contexts before.

What I'm finding however is that I cannot reliably acquire the write lock without blocking forever. Since the read lock is reentrant and I am actually using it as such, the simple code

lock.getReadLock().unlock();
lock.getWriteLock().lock()

can block if I have acquired the readlock reentrantly. Each call to unlock just reduces the hold count, and the lock is only actually released when the hold count hits zero.

EDIT to clarify this, as I don't think I explained it too well initially - I am aware that there is no built-in lock escalation in this class, and that I have to simply release the read lock and obtain the write lock. My problem is/was that regardless of what other threads are doing, calling getReadLock().unlock() may not actually release this thread's hold on the lock if it acquired it reentrantly, in which case the call to getWriteLock().lock() will block forever as this thread still has a hold on the read lock and thus blocks itself.

For example, this code snippet will never reach the println statement, even when run singlethreaded with no other threads accessing the lock:

final ReadWriteLock lock = new ReentrantReadWriteLock();
lock.getReadLock().lock();

// In real code we would go call other methods that end up calling back and
// thus locking again
lock.getReadLock().lock();

// Now we do some stuff and realise we need to write so try to escalate the
// lock as per the Javadocs and the above description
lock.getReadLock().unlock(); // Does not actually release the lock
lock.getWriteLock().lock();  // Blocks as some thread (this one!) holds read lock

System.out.println("Will never get here");

So I ask, is there a nice idiom to handle this situation? Specifically, when a thread that holds a read lock (possibly reentrantly) discovers that it needs to do some writing, and thus wants to "suspend" its own read lock in order to pick up the write lock (blocking as required on other threads to release their holds on the read lock), and then "pick up" its hold on the read lock in the same state afterwards?

Since this ReadWriteLock implementation was specifically designed to be reentrant, surely there is some sensible way to elevate a read lock to a write lock when the locks may be acquired reentrantly? This is the critical part that means the naive approach does not work.

dtsazza_45664 · Answer

I have made a little progress on this. By declaring the lock variable explicitly as a ReentrantReadWriteLock instead of simply a ReadWriteLock (less than ideal, but probably a necessary evil in this case) I can call the getReadHoldCount() method. This lets me obtain the number of holds for the current thread, and thus I can release the readlock this many times (and reacquire it the same number afterwards). So this works, as shown by a quick-and-dirty test:

final int holdCount = lock.getReadHoldCount();
for (int i = 0; i < holdCount; i++) {
   lock.readLock().unlock();
}
lock.writeLock().lock();
try {
   // Perform modifications
} finally {
   // Downgrade by reacquiring read lock before releasing write lock
   for (int i = 0; i < holdCount; i++) {
      lock.readLock().lock();
   }
   lock.writeLock().unlock();
}

Still, is this going to be the best I can do? It doesn't feel very elegant, and I'm still hoping that there's a way to handle this in a less "manual" fashion.

user_594636 · Answer

What you want to do ought to be possible. The problem is that Java does not provide an implementation that can upgrade read locks to write locks. Specifically, the javadoc ReentrantReadWriteLock says it does not allow an upgrade from read lock to write lock.

In any case, Jakob Jenkov describes how to implement it. See http://tutorials.jenkov.com/java-concurrency/read-write-locks.html#upgrade for details.

Why Upgrading Read to Write Locks Is Needed

An upgrade from read to write lock is valid (despite the assertions to the contrary in other answers). A deadlock can occur, and so part of the implementation is code to recognize deadlocks and break them by throwing an exception in a thread to break the deadlock. That means that as part of your transaction, you must handle the DeadlockException, e.g., by doing the work over again. A typical pattern is:

boolean repeat;
do {
  repeat = false;
  try {
   readSomeStuff();
   writeSomeStuff();
   maybeReadSomeMoreStuff();
  } catch (DeadlockException) {
   repeat = true;
  }
} while (repeat);

Without this ability, the only way to implement a serializable transaction that reads a bunch of data consistently and then writes something based on what was read is to anticipate that writing will be necessary before you begin, and therefore obtain WRITE locks on all data that are read before writing what needs to be written. This is a KLUDGE that Oracle uses (SELECT FOR UPDATE ...). Furthermore, it actually reduces concurrency because nobody else can read or write any of the data while the transaction is running!

In particular, releasing the read lock before obtaining the write lock will produce inconsistent results. Consider:

int x = someMethod();
y.writeLock().lock();
y.setValue(x);
y.writeLock().unlock();

You have to know whether someMethod(), or any method it calls, creates a reentrant read lock on y! Suppose you know it does. Then if you release the read lock first:

int x = someMethod();
y.readLock().unlock();
// problem here!
y.writeLock().lock();
y.setValue(x);
y.writeLock().unlock();

another thread may change y after you release its read lock, and before you obtain the write lock on it. So y's value will not be equal to x.

Test Code: Upgrading a read lock to a write lock blocks:

import java.util.*;
import java.util.concurrent.locks.*;

public class UpgradeTest {

    public static void main(String[] args) 
    {   
        System.out.println("read to write test");
        ReadWriteLock lock = new ReentrantReadWriteLock();

        lock.readLock().lock(); // get our own read lock
        lock.writeLock().lock(); // upgrade to write lock
        System.out.println("passed");
    }

}

Output using Java 1.6:

read to write test

user_46991 · Answer

What you're looking for is a lock upgrade, and is not possible (at least not atomically) using the standard java.concurrent ReentrantReadWriteLock. Your best shot is unlock/lock, and then check that noone made modifications inbetween.

What you're attempting to do, forcing all read locks out of the way is not a very good idea. Read locks are there for a reason, that you shouldn't write. :)

EDIT:
As Ran Biron pointed out, if your problem is starvation (read locks are being set and released all the time, never dropping to zero) you could try using fair queueing. But your question didn't sound like this was your problem?

EDIT 2:
I now see your problem, you've actually acquired multiple read-locks on the stack, and you'd like to convert them to a write-lock (upgrade). This is in fact impossible with the JDK-implementation, as it doesn't keep track of the owners of the read-lock. There could be others holding read-locks that you wouldn't see, and it has no idea how many of the read-locks belong to your thread, not to mention your current call-stack (i.e. your loop is killing all read locks, not just your own, so your write lock won't wait for any concurrent readers to finish, and you'll end up with a mess on your hands)

I've actually had a similar problem, and I ended up writing my own lock keeping track of who's got what read-locks and upgrading these to write-locks. Although this was also a Copy-on-Write kind of read/write lock (allowing one writer along the readers), so it was a little different still.

user_258496 · Answer

to OP: just unlock as many times as you have entered the lock, simple as that:

boolean needWrite = false;
readLock.lock()
try{
  needWrite = checkState();
}finally{
  readLock().unlock()
}

//the state is free to change right here, but not likely
//see who has handled it under the write lock, if need be
if (needWrite){
  writeLock().lock();
  try{
    if (checkState()){//check again under the exclusive write lock
   //modify state
    }
  }finally{
    writeLock.unlock()
  }
}

in the write lock as any self-respect concurrent program check the state needed.

HoldCount shouldn't be used beyond debug/monitor/fast-fail detect.

Olivier_53369 · Answer

I suppose the ReentrantLock is motivated by a recursive traversal of the tree:

public void doSomething(Node node) {
  // Acquire reentrant lock
  ... // Do something, possibly acquire write lock
  for (Node child : node.childs) {
    doSomething(child);
  }
  // Release reentrant lock
}

Can't you refactor your code to move the lock handling outside of the recursion ?

public void doSomething(Node node) {
  // Acquire NON-reentrant read lock
  recurseDoSomething(node);
  // Release NON-reentrant read lock
}

private void recurseDoSomething(Node node) {
  ... // Do something, possibly acquire write lock
  for (Node child : node.childs) {
    recurseDoSomething(child);
  }
}

user_931 · Answer

Use the "fair" flag on the ReentrantReadWriteLock. "fair" means that lock requests are served on first come, first served. You could experience performance depredation since when you'll issue a "write" request, all of the subsequent "read" requests will be locked, even if they could have been served while the pre-existing read locks are still locked.

Java ReentrantReadWriteLocks - how to safely acquire write lock when in a read lock?

12 Answers

Why Upgrading Read to Write Locks Is Needed

Test Code: Upgrading a read lock to a write lock blocks:

Output using Java 1.6: