Friday, June 05, 2009

Biased Locking in Java SE 6.0

As a result of the ensuing discussion in response to this blog entry, it is now pretty clear that the issue described herein is not specific to Java SE 6. Please do not reach any conclusions without reading the entire post, including the comments, and especially the comments.

Joern Huxhorn recently informed logback developers that locking in Java SE 6.0 was unfair. Indeed, Java documentation regularly mentions that one should not make assumptions about Java's thread scheduler. For example, the last paragraph of Thread Priority on the Solaris™ Platform, states:
Likewise, no assumptions should be made about the order in which threads are granted ownership of a monitor or the order in which threads wake in response to the notify or notifyAll method. An excellent reference for these topics is Chapter 9, "Threads," in Joshua Bloch's book "Effective Java Programming Language Guide."
If you actually bother to read the book, in Item 51, Joshua Bloch writes:
When multiple threads are runnable, the thread scheduler determines which threads get run and for how long. Any reasonable JVM implementation will attempt some sort of fairness when making this determination.
While Joshua Bloch's statement above is specifically about the JVM scheduler, I think that the notion of "some sort of fairness" applies to locks as well. The general principle is the same.

Here is a small java application called LockingInJava which illustrates the locking behavior in question.

public class LockingInJava implements Runnable {

static int THREAD_COUNT = 5;
static Object LOCK = new Object();
static Runnable[] RUNNABLE_ARRAY = new Runnable[THREAD_COUNT];
static Thread[] THREAD_ARRAY = new Thread[THREAD_COUNT];

private int counter = 0;

public static void main(String args[]) throws InterruptedException {
printEnvironmentInfo();
execute();
printResults();
}

public static void printEnvironmentInfo() {
System.out.println("java.runtime.version = "
+ System.getProperty("java.runtime.version"));
System.out.println("java.vendor = "
+ System.getProperty("java.vendor"));
System.out.println("java.version = "
+ System.getProperty("java.version"));
System.out.println("os.name = "
+ System.getProperty("os.name"));
System.out.println("os.version = "
+ System.getProperty("os.version"));
}

public static void execute() throws InterruptedException {
for (int i = 0; i < THREAD_COUNT; i++) {
RUNNABLE_ARRAY[i] = new LockingInJava();
THREAD_ARRAY[i] = new Thread(RUNNABLE_ARRAY[i]);
}
for (Thread t : THREAD_ARRAY) {
t.start();
}
// let the threads run for a while
Thread.sleep(10000);

for (int i = THREAD_COUNT - 1; i >= 0; i--) {
THREAD_ARRAY[i].interrupt();
}
Thread.sleep(100); // wait a moment for termination, too lazy for join ;)
}

public static void printResults() {
for (int i = 0; i < RUNNABLE_ARRAY.length; i++) {
System.out.println("runnable[" + i + "]: " + RUNNABLE_ARRAY[i]);
}
}

public void run() {
for (;;) {
synchronized (LOCK) {
counter++;
try {
Thread.sleep(10);
} catch (InterruptedException ex) {
break;
}
}
}
}

public String toString() {
return "counter=" + counter;
}
}
When run under Sun's JDK version 1.6.0_11 on a 64bit Dual Core AMD Opteron running Linux, here is what gets printed on the console.
java.runtime.version = 1.6.0_11-b03
java.vendor = Sun Microsystems Inc.
java.version = 1.6.0_11
os.name = Linux
os.version = 2.6.25-gentoo-r6
runnable[0]: counter=1002
runnable[1]: counter=0
runnable[2]: counter=0
runnable[3]: counter=0
runnable[4]: counter=0
Notice how only the first thread gets any work done. All the other threads are completely starved while waiting for the lock. The same application run with JDK 1.5 or older will have much more uniform results. Some threads will get more often access to the lock than others, but all threads will get some access. With JDK 1.6, access to locks is dispensed in a biased fashion. In other words, the thread currently holding the lock will always be favored compared to other competing threads. Sun calls it biased locking. It purportedly makes better use of CPU capabilities.

As for the argument about no guarantees offered about fairness, while true in letter, it is invalid in spirit. The argument is too punctilious and formalistic. Any developer reading the documentation will naturally assume that while there are no guarantees, the synchronization mechanism will not actively impede fairness.

Biased locking, as introduced in JDK 1.6, will affect thousands of unsuspecting applications. The fact that the bias is intentional does not make it less damaging. It's still a bug.