An efficient meta-lock for implementing ubiquitous synchronization

ABSTRACT

Programs written in concurrent object-oriented languages, especially ones that employ thread-safe reusable class libraries, can execute synchronization operations (lock, notify, etc.) at an amazing rate. Unless implemented with utmost care, synchronization can become a performance bottleneck. Furthermore, in languages where every object may have its own monitor, per-object space overhead must be minimized. To address these concerns, we have developed a meta-lock to mediate access to synchronization data. The meta-lock is fast (lock + unlock executes in 11 SPARC™ architecture instructions), compact (uses only two bits of space), robust under contention (no busy-waiting), and flexible (supports a variety of higher-level synchronization operations). We have validated the meta-lock with an implementation of the synchronization operations in a high-performance product-quality Java™ virtual machine and report performance data for several large programs.

REFERENCES

• 1: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y.S. Ramakrishna , Derek White, An Efficient Meta-lock for Implementing Ubiquitous Synchronization, Sun Microsystems, Inc., Mountain View, CA, 1999
• 2: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 3: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 4: 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
• 5: Lars Bak , John Duimovich , Jesse Fang , Scott Meyer , David Ungar, The new crop of Java virtual machines (panel), Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.179-182, October 18-22, 1998, Vancouver, British Columbia, Canada
• 6: Andrew Birrell. An Introduction to Programming with Threads. Digital Systems Research Center report no. 35, 1989.
• 7: David R. Butenhof, Programming with POSIX threads, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: Peter A. Buhr , Michel Fortier , Michael H. Coffin, Monitor classification, ACM Computing Surveys (CSUR), v.27 n.1, p.63-107, March 1995 [doi>10.1145/214037.214100]
• 9: Sylvia Dieckmann , Urs Hoelzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks, University of California at Santa Barbara, Santa Barbara, CA, 1998
• 10: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 11: Michael Greenwald , David Cheriton, The synergy between non-blocking synchronization and operating system structure, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.123-136, October 29-November 01, 1996, Seattle, Washington, United States
• 12: Per Brinch Hansen, Monitors and concurrent Pascal: a personal history, The second ACM SIGPLAN conference on History of programming languages, p.1-35, April 20-23, 1993, Cambridge, Massachusetts, United States
• 13: Per Brinch Hansen, Java's insecure parallelism, ACM SIGPLAN Notices, v.34 n.4, p.38-45, April 1999 [doi>10.1145/312009.312034]
• 14: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 15: William N. Joy. System and method for space efficient object locking using global and local locks. US Patent #5,761,670.
• 16: William N. Joy and Guy L. Steele. System and method for space and time efficient object locking. US Patent #5,862,376.
• 17: William N. Joy and Arthur Van Hoff. System and method for space efficient object locking using a data subarray and pointers. US Patent #5,701,470.
• 18: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 19: Andreas Krall and Mark Probst. Monitors and Exceptions: How to implement Java efficiently. In ACM 1998 Workshop on Java for High-Performance Computing, p. 15-24, Palo Alto, California, March 1998.
• 20: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 21: Xavier Leroy. The LinuxThreads library, http://pauillac.inria.fr/~xleroy/linuxthreads/index.html, 1997.
• 22: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 23: Peter Magnusson , Anders Landin , Erik Hagersten, Efficient Software Synchronization on Large Cache Coherent Multiprocessors, European Research Consortium for Informatics and Mathematics at SICS, 1994
• 24: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 25: Gilles Muller, B~bara Moura, Fabrice Bellard, and Charles Consel. Harissa: A Flexible and Efficient Java Environment Mixing Bytecode and Compiled Code. in Proc. of the 3rd Conference on Object-Oriented Technologies and Systems (COOTS), p. 1-20, Berkeley, California, June 1997.
• 26: John Neffinger. Which Java VM scales best? Java- World, August 1998. http://www'javaw~rld'c~m/javaworld/jw-08-1998/jw-08-volanomark.html. See also www.volano.com.
• 27: Todd A. Proebsting , Gregg Townsend , Patrick Bridges , John H. Hartman , Tim Newsham , Scott A. Watterson, Toba: Java For Applications: A Way Ahead of Time (WAT) Compiler, University of Arizona, Tucson, AZ, 1997
• 28: Ali-Reza Adl-Tabatabai , Michał Cierniak , Guei-Yuan Lueh , Vishesh M. Parikh , James M. Stichnoth, Fast, effective code generation in a just-in-time Java compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.280-290, June 17-19, 1998, Montreal, Quebec, Canada
• 29: SPECjvm98 Benchmarks. August 19, 1998 release. http ://w w w. spec. org/os g/j vm98.
• 30: Sun Microsystems, Inc. Java 2 on-line documentation: http:l/java.sun.com/products/jdk/1.21docs/api/ index.html.
• 31: Hong Zhang, Sheng Liang, and Lars Bak. Personal communication of draft paper: An Efficient Monitor Scheme for the JavaTM Virtual Machine.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory

Keywords:
concurrent threads, object-oriented language implementation, synchronization