Correct and Efficient Synchronization of Java ThreadsTS-754, William Pugh and Doug Lea 1TS -754, Correct and Efficient Synchronization of Java Threads1Correct and Efficient Synchronization of Java™Technology-based ThreadsDoug Lea and William Pughhttp://gee.cs.oswego.eduhttp://www.cs.umd.edu/~pughTS -754, Correct and Efficient Synchronization of Java Threads2Audience• Assume you are familiar with basics of Java™technology-based threads (“Java threads”)– Creating, starting and joining threads– Synchronization– wait and notifyAll• Will talk about things that surprised a lot of experts– Including us, James Gosling, Guy Steele, …(others discovered many of these)TS -754, Correct and Efficient Synchronization of Java Threads3Java Thread Specification• Chapter 17 of the Java Language Spec– Chapter 8 of the Virtual Machine Spec• Very, very hard to understand– Not even the authors understood it– Has subtle implications• That forbid standard compiler optimizations– All existing JVMsviolate the specification• Some parts should be violatedTS -754, Correct and Efficient Synchronization of Java Threads4Safety Issues in Multithreaded Systems• Many intuitive assumptions do not hold• Some widely used idioms are not safe– Double-check idiom– Checking non-volatile flag for thread termination• Can’t use testing to check for errors– Some anomalies will occur only on some platforms• e.g., multiprocessorsTS -754, Correct and Efficient Synchronization of Java Threads5Revising the Thread Spec• Work is underway to consider revising the Java Thread Spec– http://www.cs.umd.edu/~pugh/java/memoryModel• Goals– Clear and easy to understand– Foster reliable multithreaded code– Allow for high performance JVMs• Will effect JVMs– And badly written existing code• Including parts of Sun’s JDKTS -754, Correct and Efficient Synchronization of Java Threads6What to do Today?• Guidelines we will provide should work under both existing and future thread specs• Don’t try to read the official specs• Avoid corner cases of the thread spec– Not needed for efficient and reliable programsCorrect and Efficient Synchronization of Java ThreadsTS-754, William Pugh and Doug Lea 2TS -754, Correct and Efficient Synchronization of Java Threads7Three Aspects of Synchronization• Atomicity– Locking to obtain mutual exclusion• Visibility– Ensuring that changes to object fields made in one thread are seen in other threads• Ordering– Ensuring that you aren’t surprised by the order in which statements are executedTS -754, Correct and Efficient Synchronization of Java Threads8Don’t Be Too Clever• People worry about the cost of synchronization– Try to devise schemes to communicate between threads • Without using synchronization• Very difficult to do correctly– Inter-thread communication without synchronization is not intuitiveTS -754, Correct and Efficient Synchronization of Java Threads9Quiz Timex = y = 0x = 1j = yThread 1y = 1i = xThread 2Can this result in i = 0 and j = 0?start threadsTS -754, Correct and Efficient Synchronization of Java Threads10Answer: Yes!x = y = 0x = 1j = yThread 1y = 1i = xThread 2How can i = 0 and j = 0?start threadsTS -754, Correct and Efficient Synchronization of Java Threads11How Can This Happen?• Compiler can reorder statements– Or keep values in registers• Processor can reorder them• On multi-processor, values not synchronized in global memory• Must use synchronization to enforce visibility and ordering– As well as mutual exclusionTS -754, Correct and Efficient Synchronization of Java Threads12Synchronization Actions(approximately)// block until obtain locksynchronized(anObject) {// get main memory value of field1 and field2int x = anObject.field1;int y = anotherObject.field2;anotherObject.field3 = x+y;// commit value of field3 to main memory}// release lockmoreCode();Correct and Efficient Synchronization of Java ThreadsTS-754, William Pugh and Doug Lea 3TS -754, Correct and Efficient Synchronization of Java Threads13When Are Actions Visible to Other Threads?x = 1unlock MThread 1lock Mi = xThread 2TS -754, Correct and Efficient Synchronization of Java Threads14What Does Volatile Mean?• C/C++ ARM– There is no implementation independent meaning of volatile• Situation a little better with Java technology– Volatile reads/writes guaranteed to go directly to main memory• Can’t be cached in registers or local memoryTS -754, Correct and Efficient Synchronization of Java Threads15class Animator implements Runnable {private volatile boolean stop = false;public void stop() { stop = true; }public void run() {while (!stop) oneStep();}private void oneStep() { /*...*/ }}Using Volatile• Volatile used to guarantee visibility of writes– stop must be declared volatile– Otherwise, compiler could keep in register TS -754, Correct and Efficient Synchronization of Java Threads16Nobody Implements Volatile Correctly• Existing JMM requires sequential consistency for volatile variables– In quiz example, if x and y are volatile– Should be impossible to see i = 0 and j = 0– Haven’t found any JVMsthat enforce it• Some JVMs ignore volatile flagTS -754, Correct and Efficient Synchronization of Java Threads17Why Use Volatile?• Since the semantics are implemented inconsistently• Future-proof your code– Prohibit optimizations compilers might do in the future• Works well for flags– More complicated uses are tricky• Revising the thread spec...– Test compliance– Strengthen to make easier to useTS -754, Correct and Efficient Synchronization of Java Threads18Cost of Synchronization• Few good public multithreaded benchmarks– See us if you want to help• Volano Benchmark– Most widely used server benchmark– Multithreaded chat room server– Client performs 4.8M synchronizations• 8K useful (0.2%)– Server 43M synchronizations• 1.7M useful (4%)Correct and Efficient Synchronization of Java ThreadsTS-754, William Pugh and Doug Lea 4TS -754, Correct and Efficient Synchronization of Java Threads19Synchronization in VolanoMark Client90.3%5.6%1.8%0.9%0.9%0.4%0.2%java.io.BufferedInputStreamjava.io.BufferedOutputStreamjava.util.Observablejava.util.Vectorjava.io.FilterInputStreameverything elseAll shared monitors7,684 synchronizations on shared monitors4,828,130 thread local synchronizationsTS -754, Correct and Efficient Synchronization of Java Threads20Cost of Synchronization in
View Full Document
Unlocking...