The Java memory model

ABSTRACT

This paper describes the new Java memory model, which has been revised as part of Java 5.0. The model specifies the legal behaviors for a multithreaded program; it defines the semantics of multithreaded Java programs and partially determines legal implementations of Java virtual machines and compilers.The new Java model provides a simple interface for correctly synchronized programs -- it guarantees sequential consistency to data-race-free programs. Its novel contribution is requiring that the behavior of incorrectly synchronized programs be bounded by a well defined notion of causality. The causality requirement is strong enough to respect the safety and security properties of Java and weak enough to allow standard compiler and hardware optimizations. To our knowledge, other models are either too weak because they do not provide for sufficient safety/security, or are too strong because they rely on a strong notion of data and control dependences that precludes some standard compiler transformations.Although the majority of what is currently done in compilers is legal, the new model introduces significant differences, and clearly defines the boundaries of legal transformations. For example, the commonly accepted definition for control dependence is incorrect for Java, and transformations based on it may be invalid.In addition to providing the official memory model for Java, we believe the model described here could prove to be a useful basis for other programming languages that currently lack well-defined models, such as C++ and C#.

REFERENCES

• 1: Ada Joint Program Office. Ada 95 Rationale. Intermetrics, Inc., Cambridge, Massachusetts, 1995.
• 2: Sarita Vikram Adve, Designing memory consistency models for shared-memory multiprocessors, University of Wisconsin at Madison, Madison, WI, 1993
• 3: 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]
• 4: Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
• 5: Sarita V. Adve. The SC- memory model for Java, 2004. http://www.cs.uiuc.edu/~sadve/jmm.
• 6: S. V. Adve , J. K. Aggarwal, A Unified Formalization of Four Shared-Memory Models, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.613-624, June 1993 [doi>10.1109/71.242161]
• 7: Sarita V. Adve and Mark D. Hill. Sufficient conditions for implementing the data-race-free-1 memory model. Technical Report #1107, Computer Sciences Department, University of Wisconsin-Madison, September 1992.
• 8: Jan-Willem Maessen , Xiaowei Shen, Improving the Java memory model using CRF, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-12, October 2000, Minneapolis, Minnesota, United States
• 9: John K. Bennett , John B. Carter , Willy Zwaenepoel, Adaptive software cache management for distributed shared memory architectures, Proceedings of the 17th annual international symposium on Computer Architecture, p.125-134, May 28-31, 1990, Seattle, Washington, United States
• 10: Gianfranco Bilardi , Keshav Pingali, A framework for generalized control dependence, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.291-300, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 11: Christopher Brumme. C# memory model. http://blogs.msdn.com/cbrumme/archive/2003/05/17/51445.apx.
• 12: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 13: ECMA. Common Language Infrastructure (CLI), December 2002. http://www.ecma-international.org/publications/standards/Ecma-335.htm.
• 14: Kourosh Gharachorloo, Memory consistency models for shared-memory multiprocessors, Stanford University, Stanford, CA, 1996
• 15: Kourosh Gharachorloo, Sarita V. Adve, Anoop Gupta, John L. Hennessy, and Mark D. Hill. Programming for different memory consistency models. Journal of Parallel and Distributed Computing, 15(4):399--407, August 1992.
• 16: Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. Two techniques to enhance the performance of memory consistency models. In Proc. Intl. Conf. on Parallel Processing, pages I355--I364, 1991.
• 17: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 18: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 19: IBM System/370 Principles of Operation, May 1983. Publication Number GA22-7000-9, File Number S370-01.
• 20: Java Specification Request (JSR) 133. Java Memory Model and Thread Specification Revision, 2004. http://jcp.org/jsr/detail/133.jsp.
• 21: The Java memory model. Mailing list and web page. http://www.cs.umd.edu/users/pugh/java/memoryModel.
• 22: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 23: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 24: Vishnu Kotrajaras. Towards an Improved Memory Model for Java. PhD thesis, Department of Computing, Imperial College, August 2001.
• 25: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 26: Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, 9(29):690--691, 1979.
• 27: Bil Lewis , Daniel J. Berg, Multithreaded programming with Pthreads, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 28: Jeremy Manson , William Pugh, Core semantics of multithreaded Java, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.29-38, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376806]
• 29: Jeremy Manson and William Pugh. Semantics of Multithreaded Java. Technical Report CS-TR-4215, Dept. of Computer Science, University of Maryland, College Park, March 2001.
• 30: Jeremy Manson and William Pugh. Requirements for Programming Language Memory Models. In PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada, July 2004.
• 31: 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
• 32: A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
• 33: William Pugh, Fixing the Java memory model, Proceedings of the ACM 1999 conference on Java Grande, p.89-98, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304106]
• 34: William Pugh. The Java memory model is fatally flawed. Concurrency: Practice and Experience, 12(1):1--11, 2000.
• 35: Parthasarathy Ranganathan , Vijay S. Pai , Sarita V. Adve, Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.199-210, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258512]
• 36: Vijay Saraswat. Concurrent Constraint-based Memory Machines: A framework for Java Memory Models. Technical report, IBM TJ Watson Research Center, March 2004.
• 37: Douglas C. Schmidt , Tim Harrison, Double-checked locking, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 38: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]
• 39: Xiaowei Shen , Arvind , Larry Rudolph, Commit-reconcile & fences (CRF): a new memory model for architects and compiler writers, Proceedings of the 26th annual international symposium on Computer architecture, p.150-161, May 01-04, 1999, Atlanta, Georgia, United States
• 40: Richard L. Sites , Richard T. Witek, Alpha AXP architecture reference manual (2nd ed.), Digital Press, Newton, MA, 1995
• 41: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 42: Z. Sura, C.-L. Wong, X. Fang, J. Lee, S. Midkiff, and D. Padua. Automatic implementation of programming language consistency models. In Proc. of the 15th International Workshop on Languages and Compilers for Parallel Computing (LCPC'02), 2002. To appear Lecture Notes in Computer Science, Springer-Verlag.
• 43: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 44: Yue Yang , Ganesh Gopalakrishnan , Gary Lindstrom, Specifying Java thread semantics using a uniform memory model, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.192-201, November 03-05, 2002, Seattle, Washington, USA [doi>10.1145/583810.583832]
• 45: Yue Yang, Ganesh Gopalakrishnan, and Gary Lindstrom. Formalizing the Java memory model for multithreaded program correctness and optimization. Technical Report UUCS-02-011, University of Utah, April 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General
          Subjects: Standards

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Design, Languages, Standardization

Keywords:
Java, concurrency, memory model, multithreading