A study of locking objects with bimodal fields

ABSTRACT

Object locking can be efficiently implemented by bimodal use of a field reserved in an object. The field is used as a lightweight lock in one mode, while it holds a reference to a heavyweight lock in the other mode. A bimodal locking algorithm recently proposed for Java achieves the highest performance in the absence of contention, and is still fast enough when contention occurs.However, mode transitions inherent in bimodal locking have not yet been fully considered. The algorithm requires busy-wait in the transition from the light mode (inflation), and does not make the reverse transition (deflation) at all.We propose a new algorithm that allows both inflation without busy-wait and deflation, but still maintains an almost maximum level of performance in the absence of contention. We also present statistics on the synchronization behavior of real multithreaded Java programs, which indicate that busy-wait in inflation and absence of deflation can be problematic in terms of robustness and performance. Actually, an implementation of our algorithm shows increased robustness, and achieves performance improvements of up to 13.1% in server-oriented benchmarks.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 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: Ole Agesen, Space and time-efficient hashing of garbage-collected objects, Theory and Practice of Object Systems, v.5 n.2, p.119-124, April 1999 [doi>10.1002/(SICI)1096-9942(1999)5:2<119::AID-TAPO5>3.3.CO;2-H]
• 4: Ole Agesen, David Detlefs, Alex Garthwaite, Ross Knippel, Y.S. R~makrishna, and Derek White. Aa Efficient Meta-lock for Implementing Ubiquitous Synchronization. OOPSLA'99 Conference Proceedings, To appear.
• 5: 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
• 6: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 7: IBM Corporation. Aglets Software Development Kit. http://www.tri.ibm.co.jp/aglets/ (current April 1, 1999).
• 8: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 9: Andreas Krall and Mark Probst. Monitors and Exceptions: How to Implement Java Efficiently. A CM 1998 Workshop on Java .for High-Performance Network Computing.
• 10: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa, Communications of the ACM, v.23 n.2, p.105-117, Feb. 1980 [doi>10.1145/358818.358824]
• 11: Beng-Hong Lim , Anant Agarwal, Waiting algorithms for synchronization in large-scale multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.3, p.253-294, Aug. 1993 [doi>10.1145/152864.152869]
• 12: Lotus Development Corporation. eSuige DevSite. http://esuite.lotus.com/ (current April 1, 1999).
• 13: Cathy May , Ed Silha , Rick Simpson , Hank Warren , CORPORATE International Business Machines, Inc., The PowerPC architecture: a specification for a new family of RISC processors, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 14: 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]
• 15: James G. Mitheell, William Maybury, and Richard Sweet. Mesa Language Manual CSL-79-3, Xerox Palo Alto Research Center (April 1979).
• 16: Tamiya Onodera. a Simple and Space-Ej~cient Monitor Optimization for Java. Research Report RT0259, IBM Research, Tokyo Research Laboratory (july 1998).
• 17: Transaction Processing Performance Council. TPC-C Benchmark Specification. http://www.tpc.org/cspe~.html (current April i, 1999).
• 18: John K. Ousterhout. Scheduling Techniques for Concurrent Systems. Proceedings of the 3rd In. tevnational Conference on Distributed Computing Systems, 1982, 22-30.
• 19: Sun Microsystems, inc. Hot Java Product Family. http"//java, sun. corn/products/hot java/ (current April 1, 1999).
• 20: Transvirtual Technologies, Inc. Knife. http ://www. transvirtual, com/kaffe .html (current April 1, 1999).
• 21: Gaku Yamamoto , Yuhichi Nakamura, Architecture and performance evaluation of a massive multi-agent system, Proceedings of the third annual conference on Autonomous Agents, p.319-325, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301219]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

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