Context Navigation

Synchronized vs. Lock vs. fair Lock

This page is dedicated to show an alarming change in the way Java 1.6 is handling synchronized on multi-core processors.

This can lead to severe starvation effects [3].

The problem

The problem I'm discussing is that several threads are trying to obtain the object monitor of the exact same resource, i.e.

synchronized(someObject) {
// do something
}

The assumption that multiple threads waiting for ownership of a monitor would receive the monitor in the order that they tried to acquire it ("first come, first serve") is simply incorrect.

This is documented behavior.

See the last paragraph of [1]:

"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. "

The documentation of Object.notifyAll() [2] states the following:

"[..] The awakened threads will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened threads enjoy no reliable privilege or disadvantage in being the next thread to lock this object."

The documentation in [5] also lists the following as a weak-spot of Built-in Synchronization in J2SE 1.4.x:

"No way to alter the semantics of a lock, for example, with respect to reentrancy, read versus write protection, or fairness."

Wrong assumptions…

I assumed that this wouldn't be a problem, that synchronized would be sufficiently fair even if it's not totally fair... but all that changed with Java 6 on multi-core systems!

Locking using synchronized has turned totally unfair!

Fairness of object monitor lock acquisition seems to be logical and a "good thing" but it's not specified that way, and for good reasons.

Without fairness in place, the VM can optimize the execution of an application much better. A context switch is a costly operation for a CPU so performance is increased significantly if such a switch can be omitted.

The solution

The only way to prevent this is the introduction of fairness into the locking process. The way to do this is to use ReentrantLock [4], or ReentrantReadWriteLock for that matter.

From the ReentrantLock javadoc:

"The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation."

The proof

Not convinced yet? Think I'm hallucinating? Just test it out for yourself!

Download SynchronizedVsFairLock.java, execute

javac SynchronizedVsFairLock.java

followed by

java SynchronizedVsFairLock

and see the results with your own eyes.

For best results :p you should use a Java 1.5 javac and run the app on a multi-core system using both java 1.5 and 1.6.

Some results, for your convenience…

iMac, 2.4GHz Intel Core 2 Duo, i.e. multi-core

Environment:
java.runtime.name    = Java(TM) SE Runtime Environment
java.runtime.version = 1.6.0_07-b06-153
java.vendor          = Apple Inc.
java.version         = 1.6.0_07
java.vm.name         = Java HotSpot(TM) 64-Bit Server VM
java.vm.info         = mixed mode
os.name              = Mac OS X
os.version           = 10.5.7
os.arch              = x86_64
##########################################
About to execute usingSynchronized...
Results for usingSynchronized:
runnables[0]: SynchronizedRunnable[counter=394, running=false]
runnables[1]: SynchronizedRunnable[counter=1, running=false]
runnables[2]: SynchronizedRunnable[counter=1, running=false]
runnables[3]: SynchronizedRunnable[counter=1, running=false]
runnables[4]: SynchronizedRunnable[counter=1, running=false]
runnables[5]: SynchronizedRunnable[counter=1, running=false]
runnables[6]: SynchronizedRunnable[counter=1, running=false]
runnables[7]: SynchronizedRunnable[counter=1, running=false]
runnables[8]: SynchronizedRunnable[counter=1, running=false]
runnables[9]: SynchronizedRunnable[counter=605, running=false]
##########################################
About to execute usingUnfairLock...
Results for usingUnfairLock:
runnables[0]: LockRunnable[counter=997, running=false]
runnables[1]: LockRunnable[counter=1, running=false]
runnables[2]: LockRunnable[counter=1, running=false]
runnables[3]: LockRunnable[counter=1, running=false]
runnables[4]: LockRunnable[counter=1, running=false]
runnables[5]: LockRunnable[counter=1, running=false]
runnables[6]: LockRunnable[counter=1, running=false]
runnables[7]: LockRunnable[counter=1, running=false]
runnables[8]: LockRunnable[counter=1, running=false]
runnables[9]: LockRunnable[counter=1, running=false]
##########################################
About to execute usingFairLock...
Results for usingFairLock:
runnables[0]: LockRunnable[counter=101, running=false]
runnables[1]: LockRunnable[counter=101, running=false]
runnables[2]: LockRunnable[counter=101, running=false]
runnables[3]: LockRunnable[counter=101, running=false]
runnables[4]: LockRunnable[counter=100, running=false]
runnables[5]: LockRunnable[counter=100, running=false]
runnables[6]: LockRunnable[counter=100, running=false]
runnables[7]: LockRunnable[counter=100, running=false]
runnables[8]: LockRunnable[counter=100, running=false]
runnables[9]: LockRunnable[counter=100, running=false]
##########################################

Environment:
java.runtime.name    = Java(TM) 2 Runtime Environment, Standard Edition
java.runtime.version = 1.5.0_16-b06-284
java.vendor          = Apple Inc.
java.version         = 1.5.0_16
java.vm.name         = Java HotSpot(TM) Client VM
java.vm.info         = mixed mode, sharing
os.name              = Mac OS X
os.version           = 10.5.7
os.arch              = i386
##########################################
About to execute usingSynchronized...
Results for usingSynchronized:
runnables[0]: SynchronizedRunnable[counter=101, running=false]
runnables[1]: SynchronizedRunnable[counter=101, running=false]
runnables[2]: SynchronizedRunnable[counter=101, running=false]
runnables[3]: SynchronizedRunnable[counter=101, running=false]
runnables[4]: SynchronizedRunnable[counter=101, running=false]
runnables[5]: SynchronizedRunnable[counter=101, running=false]
runnables[6]: SynchronizedRunnable[counter=100, running=false]
runnables[7]: SynchronizedRunnable[counter=100, running=false]
runnables[8]: SynchronizedRunnable[counter=100, running=false]
runnables[9]: SynchronizedRunnable[counter=100, running=false]
##########################################
About to execute usingUnfairLock...
Results for usingUnfairLock:
runnables[0]: LockRunnable[counter=485, running=false]
runnables[1]: LockRunnable[counter=495, running=false]
runnables[2]: LockRunnable[counter=19, running=false]
runnables[3]: LockRunnable[counter=1, running=false]
runnables[4]: LockRunnable[counter=1, running=false]
runnables[5]: LockRunnable[counter=1, running=false]
runnables[6]: LockRunnable[counter=1, running=false]
runnables[7]: LockRunnable[counter=1, running=false]
runnables[8]: LockRunnable[counter=1, running=false]
runnables[9]: LockRunnable[counter=1, running=false]
##########################################
About to execute usingFairLock...
Results for usingFairLock:
runnables[0]: LockRunnable[counter=101, running=false]
runnables[1]: LockRunnable[counter=101, running=false]
runnables[2]: LockRunnable[counter=101, running=false]
runnables[3]: LockRunnable[counter=101, running=false]
runnables[4]: LockRunnable[counter=101, running=false]
runnables[5]: LockRunnable[counter=100, running=false]
runnables[6]: LockRunnable[counter=100, running=false]
runnables[7]: LockRunnable[counter=100, running=false]
runnables[8]: LockRunnable[counter=100, running=false]
runnables[9]: LockRunnable[counter=100, running=false]
##########################################

IBM ThinkPad, Intel Pentium M processor 1.86GHz, i.e. single-core

Environment:
java.runtime.name    = Java(TM) SE Runtime Environment
java.runtime.version = 1.6.0_13-b03
java.vendor          = Sun Microsystems Inc.
java.version         = 1.6.0_13
java.vm.name         = Java HotSpot(TM) Client VM
java.vm.info         = mixed mode, sharing
os.name              = Windows XP
os.version           = 5.1
os.arch              = x86
##########################################
About to execute usingSynchronized...
Results for usingSynchronized:
runnables[0]: SynchronizedRunnable[counter=6, running=false]
runnables[1]: SynchronizedRunnable[counter=11, running=false]
runnables[2]: SynchronizedRunnable[counter=85, running=false]
runnables[3]: SynchronizedRunnable[counter=70, running=false]
runnables[4]: SynchronizedRunnable[counter=75, running=false]
runnables[5]: SynchronizedRunnable[counter=73, running=false]
runnables[6]: SynchronizedRunnable[counter=74, running=false]
runnables[7]: SynchronizedRunnable[counter=88, running=false]
runnables[8]: SynchronizedRunnable[counter=72, running=false]
runnables[9]: SynchronizedRunnable[counter=90, running=false]
##########################################
About to execute usingUnfairLock...
Results for usingUnfairLock:
runnables[0]: LockRunnable[counter=64, running=false]
runnables[1]: LockRunnable[counter=87, running=false]
runnables[2]: LockRunnable[counter=60, running=false]
runnables[3]: LockRunnable[counter=60, running=false]
runnables[4]: LockRunnable[counter=76, running=false]
runnables[5]: LockRunnable[counter=54, running=false]
runnables[6]: LockRunnable[counter=54, running=false]
runnables[7]: LockRunnable[counter=71, running=false]
runnables[8]: LockRunnable[counter=56, running=false]
runnables[9]: LockRunnable[counter=67, running=false]
##########################################
About to execute usingFairLock...
Results for usingFairLock:
runnables[0]: LockRunnable[counter=65, running=false]
runnables[1]: LockRunnable[counter=65, running=false]
runnables[2]: LockRunnable[counter=65, running=false]
runnables[3]: LockRunnable[counter=65, running=false]
runnables[4]: LockRunnable[counter=65, running=false]
runnables[5]: LockRunnable[counter=65, running=false]
runnables[6]: LockRunnable[counter=65, running=false]
runnables[7]: LockRunnable[counter=64, running=false]
runnables[8]: LockRunnable[counter=64, running=false]
runnables[9]: LockRunnable[counter=64, running=false]
##########################################

Environment:
java.runtime.name    = Java(TM) 2 Runtime Environment, Standard Edition
java.runtime.version = 1.5.0_13-b05
java.vendor          = Sun Microsystems Inc.
java.version         = 1.5.0_13
java.vm.name         = Java HotSpot(TM) Client VM
java.vm.info         = mixed mode, sharing
os.name              = Windows XP
os.version           = 5.1
os.arch              = x86
##########################################
About to execute usingSynchronized...
Results for usingSynchronized:
runnables[0]: SynchronizedRunnable[counter=65, running=false]
runnables[1]: SynchronizedRunnable[counter=65, running=false]
runnables[2]: SynchronizedRunnable[counter=65, running=false]
runnables[3]: SynchronizedRunnable[counter=65, running=false]
runnables[4]: SynchronizedRunnable[counter=65, running=false]
runnables[5]: SynchronizedRunnable[counter=65, running=false]
runnables[6]: SynchronizedRunnable[counter=65, running=false]
runnables[7]: SynchronizedRunnable[counter=64, running=false]
runnables[8]: SynchronizedRunnable[counter=64, running=false]
runnables[9]: SynchronizedRunnable[counter=64, running=false]
##########################################
About to execute usingUnfairLock...
Results for usingUnfairLock:
runnables[0]: LockRunnable[counter=50, running=false]
runnables[1]: LockRunnable[counter=86, running=false]
runnables[2]: LockRunnable[counter=63, running=false]
runnables[3]: LockRunnable[counter=54, running=false]
runnables[4]: LockRunnable[counter=72, running=false]
runnables[5]: LockRunnable[counter=72, running=false]
runnables[6]: LockRunnable[counter=54, running=false]
runnables[7]: LockRunnable[counter=72, running=false]
runnables[8]: LockRunnable[counter=70, running=false]
runnables[9]: LockRunnable[counter=57, running=false]
##########################################
About to execute usingFairLock...
Results for usingFairLock:
runnables[0]: LockRunnable[counter=65, running=false]
runnables[1]: LockRunnable[counter=65, running=false]
runnables[2]: LockRunnable[counter=65, running=false]
runnables[3]: LockRunnable[counter=65, running=false]
runnables[4]: LockRunnable[counter=64, running=false]
runnables[5]: LockRunnable[counter=64, running=false]
runnables[6]: LockRunnable[counter=64, running=false]
runnables[7]: LockRunnable[counter=64, running=false]
runnables[8]: LockRunnable[counter=64, running=false]
runnables[9]: LockRunnable[counter=64, running=false]
##########################################

Conclusion

synchronized was fair on 1.5, is a bit unfair on 1.6 single-core and very unfair on 1.6 multi-core.

Interestingly, unfair locks are even unfairer than synchronized on a 1.6 multi-core system while being as unfair as synchronized using 1.6 in case of 1.5 on a multi-core system. This means that the starvation effect was already present on 1.5 multi-core systems in case of locks while synchronized was still handled fairly.

On single-core systems, everything seems to be ok but isn't.

See Ceki Gülcüs Blog post on the topic: Biased Locking in Java SE 6.0 [6]

lilith