Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing

ABSTRACT

The Java™ programming language contains built-in synchronization primitives for use in constructing multithreaded programs. Efficient implementation of these synchronization primitives is necessary in order to achieve high performance.Recent research [9, 12, 10, 3, 7] has focused on the run-time elimination of the atomic operations required to implement object monitor synchronization primitives. This paper describes a novel technique called store-free biased locking which eliminates all synchronization-related atomic operations on uncontended object monitors. The technique supports the bulk transfer of object ownership from one thread to another, and the selective disabling of the optimization where unprofitable, using epoch-based bulk rebiasing and revocation. It has been implemented in the production version of the Java HotSpot™VM and has yielded significant performance improvements on a range of benchmarks and applications. The technique is applicable to any virtual machine-based programming language implementation with mostly block-structured locking primitives.

REFERENCES

• 1: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y. S. Ramakrishna , Derek White, An efficient meta-lock for implementing ubiquitous synchronization, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.207-222, November 01-05, 1999, Denver, Colorado, United States
• 2: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 3: Bacon, D. F. and Fink, S. Method and apparatus to provide concurrency control over objects without atomic operations on non-shared objects. U.S. Patent Number 6,772,153, issued August 3, 2004. Assignee: International Business Machines Corporation.
• 4: Bak, L. and Lindholm, T. G. Method and apparatus for concurrent thread synchronization. U.S. Patent Number 6,167,424, issued December 26, 2000. Assignee: Sun Microsystems, Inc.
• 5: Dice, D. Implementing fast Java monitors with relaxed locks. In proceedings of the Java Virtual Machine Research and Technology Symposium (JVM '01), April 2001, pp. 79--90.
• 6: Dice, D. Personal communication.
• 7: Gomes, B. A., Bak, L., and Stoutamire, D. P. Method and apparatus for speculatively locking objects in an object-based system. U.S. Patent Number 6,487,652, issued November 26, 2002. Assignee: Sun Microsystems, Inc.
• 8: Robert Griesemer , Srdjan Mitrovic, A Compiler for the Java HotSpotTM Virtual Machine, The School of Niklaus Wirth, "The Art of Simplicity", p.133-152, January 2000
• 9: Kiyokuni Kawachiya , Akira Koseki , Tamiya Onodera, Lock reservation: Java locks can mostly do without atomic operations, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 10: Kawachiya, K. Ph.D thesis, Graduate School of Media and Governance at Keio University, 2005.
• 11: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 12: Onodera, T., Kawachiya, K., and Koseki, K. Lock reservation for Java reconsidered. In proceedings of ECOOP '04, June 2004, pp. 559--583.
• 13: Paleczny, M., Vick, C., and Click, C. The Java HotSpot™server compiler. In proceedings of the Java Virtual Machine Research and Technology Symposium (JVM '01), April 2001.
• 14: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 15: Schmidt, R. W. System and method for facilitating safepoint synchronization in a multithreaded computer system. U.S. Patent Number 6,523,059, issued February 18, 2003. Assignee: Sun Microsystems, Inc.
• 16: Stoodley, M. Accelerating Java synchronization in Just-In-Time compiler-generated code. 3rd Workshop on Compiler-Driven Performance, October 2004. linebreak http://www.cs.ualberta.ca/~amaral/cascon/CDP04/
• 17: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages, Performance

Keywords:
Java, atomic, bias, lock, monitor, optimization, rebias, reservation, revoke, synchronization