The Pure Danger of Unfair Read-Write Locks

March 13, 2009

Attending the local No Fluff Just Stuff conference in Saint Louis on Friday, I raised a question during Alex Miller’s talk on Java Concurrency Idioms regarding the documented behavior of the ReentrantReadWriteLock of “A nonfair lock that is continously contended may indefinitely postpone one or more reader or writer threads, […]

So I commented on Alex’s “Writing while reads pile up” blog entry, saying:

My question on Friday was regarding the potential for a sequential set of overlapping readers locking out a waiting writer forever. It seems that this could happen, as the JavaDoc explicitly says, “A nonfair lock that is continously contended may indefinitely postpone one or more reader or writer threads”.
The scenario I had in mind would work like this:
1. Reader 1 gets a read lock.
2. The writer requests a write lock, and is blocked.
3. Reader 2 requests a read lock — and let’s say they get it.
4. Reader 1 releases their read lock.
5. Reader 3 requests a read lock — and let’s say they get it.
6. Reader 2 releases their read lock.
As long as steps 5 and 6 are repeated as shown above, the writer would be delayed indefinately.
However, in writing tests for this, I’m finding that the ‘java.util.concurrent.locks.ReentrantReadWriteLock’ class has the (apparently undocumented) behavior that it stops granting read locks when a write lock is requested. So it appears that even in non-fair mode, readers will NOT block writers indefinitely. (…as long as every lock holder releases their lock within a reasonable period of time!)
What I find is that in step 3 above, Reader 2 is delayed until the writer gets, uses and releases the write lock. So the write does NOT get indefinitely postponed in this scenario.

Not wanting to keep secrets, I am posting here the code I’m using to come to this conclusion:

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;
import org.junit.Test;

public class LockTest {
private List readThreads = new ArrayList();

@Test
public void runTest() throws InterruptedException {
final boolean isFair = false;
final ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock(isFair);
final ReadLock readLock = readWriteLock.readLock();
final WriteLock writeLock = readWriteLock.writeLock();

System.out.println(“===================================”);
System.out.println(“–> Start working read threads.”);
final int readersPerBatch = 5;
for (int idx = 0; idx Start blocking read threads.”);
for (int idx = 0; idx >> WRITE LOGIC HERE <<<“);
writeLock.unlock();
System.out.println(“Main: Released write lock.”);
System.out.println(“===================================”);

for (final Thread thread : readThreads) {
thread.join();
}
System.out.println(“===================================”);
System.out.println(“Done.”);
}

private void startReadLockThread(final ReadLock readLock, final int thisReaderNumber) {
final Thread thread = new Thread(new Runnable() {
@Override
public void run() {
final String messagePrefix = “Reader ” + thisReaderNumber + “: “;
System.out.println(messagePrefix + “Started.”);
sleepSeconds(1);
System.out.println(messagePrefix + “Asking for read lock.”);
readLock.lock();
try {
System.out.println(messagePrefix + “Has read lock.”);
System.out.println(messagePrefix + “‘Working’ with read lock.”);
sleepSeconds(6);
} finally {
System.out.println(messagePrefix + “Releasing read lock.”);
readLock.unlock();
}
}
});
readThreads.add(thread);
thread.start();
}

private static void sleepSeconds(double seconds) {
try {
final long milliseconds = Math.round(seconds * 1000);
Thread.sleep(milliseconds);
} catch (InterruptedException ex) {
ex.printStackTrace();
}
}
}

Sample Output:

===================================
--> Start working read threads.
Reader 1: Started.
Reader 3: Started.
Reader 2: Started.
Main: Sleeping.
Reader 5: Started.
Reader 4: Started.
Reader 5: Asking for read lock.
Reader 5: Has read lock.
Reader 5: 'Working' with read lock.
Reader 3: Asking for read lock.
Reader 3: Has read lock.
Reader 3: 'Working' with read lock.
Reader 1: Asking for read lock.
Reader 1: Has read lock.
Reader 1: 'Working' with read lock.
Reader 4: Asking for read lock.
Reader 4: Has read lock.
Reader 4: 'Working' with read lock.
Reader 2: Asking for read lock.
Reader 2: Has read lock.
Reader 2: 'Working' with read lock.
===================================
--> Start blocking read threads.
Reader 6: Started.
Reader 8: Started.
Reader 7: Started.
Reader 9: Started.
Main: Attempting to acquire write lock.
Reader 10: Started.
Reader 8: Asking for read lock.
Reader 10: Asking for read lock.
Reader 9: Asking for read lock.
Reader 7: Asking for read lock.
Reader 6: Asking for read lock.
Reader 2: Releasing read lock.
Reader 4: Releasing read lock.
Reader 1: Releasing read lock.
Reader 3: Releasing read lock.
Reader 5: Releasing read lock.
===================================
Main: Has write lock.
Main: >>> WRITE LOGIC HERE <<<
Main: Released write lock.
===================================
Reader 8: Has read lock.
Reader 8: 'Working' with read lock.
Reader 10: Has read lock.
Reader 10: 'Working' with read lock.
Reader 6: Has read lock.
Reader 6: 'Working' with read lock.
Reader 7: Has read lock.
Reader 7: 'Working' with read lock.
Reader 9: Has read lock.
Reader 9: 'Working' with read lock.
Reader 8: Releasing read lock.
Reader 6: Releasing read lock.
Reader 10: Releasing read lock.
Reader 7: Releasing read lock.
Reader 9: Releasing read lock.
===================================
Done.

Observe that the Main thread starts up five Reader threads, and waits for them to acquire read locks and start “working.” Main then fires up five more read threads and requests a write lock before the new threads request their read locks. Notice that the five new Reader threads WAIT until the first five threads finish, and the main thread acquires, uses and releases the write lock. And then the five Reader threads that have been waiting all get their locks, do their “work” and finish.

This is much better behavior than I had expected.


Why Matthias Ernst’s “Chaining: A Modest Language Proposal” for Java would be nice to have

February 14, 2009

OK, shouting at my MP3 player hasn’t been doing me any good; it’s just helping other drivers recognize how passionate I am. ;-> So I’ll try writing about it instead:

After listening to recent Java Posse podcast episodes, I’ve been working my way back to earlier episodes, and I keep tripping over discussions (as in Episide #151) of Matthias Ernst’s “Chaining: A Modest Language Proposal” — which would make the compiler enable a method chaining / “fluid interface” convention on methods returning the void type.

Like the Java Posse members, I’m also somewhat bothered by the idea of reinterpreting void return types, but I think it will be helpful to consider this example of code that would be fixed by his proposal:

Consider these two classes:
public class Base {
  public Base setBaseStuff() { /* ... */ return this; }
}
public class Sub extends Base {
  public Sub setSubStuff() { /* ... */ return this; }
}

This code works:
  new Sub().setSubStuff().setBaseStuff();
This code doesn’t compile:
  new Sub().setBaseStuff().setSubStuff();

The problem is that when you’re using method chaining on classes that extend other classes and which add methods…  You MUST call subclass methods before calling superclass methods.  Otherwise it won’t compile.

With the “Chained Invocations” proposal, if the methods returned void, both method calling orders would compile and work fine.

This happens because the compiler knows more about the type of the callee than the method declaration: When the compiler assumes that void methods return ‘this’, it knows the specific subclass type of ‘this’ — while the method declarations don’t.

In essence…
  new Sub().setBaseStuff().setSubStuff();
becomes
  Sub s = new Sub();
  s.setBaseStuff();
  s.setSubStuff();

This may not seem like much. But what happens when you have a significant number of methods, and possibly several inheritance levels?

Consider these classes:

  public class A {
    public A a1() { /* ... */ return this; }
    public A a2() { /* ... */ return this; }
    public A a3() { /* ... */ return this; }
  }
  public class B extends A {
    public B b1() { /* ... */ return this; }
    public B b2() { /* ... */ return this; }
    public B b3() { /* ... */ return this; }
  }
  public class C extends B {
    public C c1() { /* ... */ return this; }
    public C c2() { /* ... */ return this; }
    public C c3() { /* ... */ return this; }
  }

And this expression:
  new C().c1().c2().c3().b1().b2().b3().a1().a2().a3();

DON’T GET ANY METHOD CALLS OUT OF ORDER!
Like this:
  new C().c1().c2().a2().c3().b1().b2().b3().a1().a3();
OR IT DOESN’T COMPILE!!!

So are we on the same page now, as to why this change might be nice to have?


LINQ for Java? Anders Norås’ Quaere Library

February 8, 2009

I just heard about Anders Norås’ Quaere Library yesterday:

My friend Google was easily able to direct me to additional information at…

  • [Anders Norås’ Blog entry, “Introducing Quaere – Language integrated queryies for Java” is no longer available online.]
  • TheServerSide article, “LINQ for Java: Quaere”

Naturally, this prompted me to document this development in my favorite place — a LanguageIntegratedQueryForJava page on Ward’s Wiki.

Quaere doesn’t seem to offer database or XML operations. But I don’t see why this idea couldn’t be expanded to do such things. It’s a very interesting idea. I hope it’s successful.