Guava: a dialect of Java without data races

ABSTRACT

We introduce Guava, a dialect of Java whose rules statically guarantee that parallel threads access shared data only through synchronized methods. Our dialect distinguishes three categories of classes: (1) monitors, which may be referenced from multiple threads, but whose methods are accessed serially; (2) values, which cannot be referenced and therefore are never shared; and (3) objects, which can have multiple references but only from within one thread, and therefore do not need to be synchronized. Guava circumvents the problems associated with today's Java memory model, which must define behavior when concurrent threads access shared memory without synchronization.We present an overview of the syntax and the semantic rules of Guava. We discuss how implementations of Guava can exploit these rules to re-enable compiler optimizations inhibited by standard Java. We discuss how compilers for certain multiprocessor architectures can automatically generate certain programming idioms, such as double-check reads, as optimizations of serialized monitors.

REFERENCES

• 1: ALPHA ARCHITECTURE COMMITTEE. Alpha Architecture Reference Manual, third ed. Digital Press, 1998.
• 2: Per Brinch Hansen, Structured multiprogramming, Communications of the ACM, v.15 n.7, p.574-578, July 1972 [doi>10.1145/361454.361473]
• 3: BRINCH HANSEN, P. The programming language Concurrent Pascal. IEEE Trans. Softw. Eng. SE-1, 2 (June 1975), 199-207.
• 4: BRINCH HANSEN, P. The Solo operating system. Software - Practice and Experience 6, 2 (Apr.-June 1976), 141-200.
• 5: Per Brinch Hansen, Java's insecure parallelism, ACM SIGPLAN Notices, v.34 n.4, p.38-45, April 1999 [doi>10.1145/312009.312034]
• 6: CARDELLI, L., DONAHUE, J., GLASSMAN, L., JORDAN, M., KALSOW, B., AND NELSON, G. Modula-3 report. Tech. Rep. ORC-1, Olivetti Research Center, 1988.
• 7: Edwin C. Chan , John T. Boyland , William L. Scherlis, Promises: limited specifications for analysis and manipulation, Proceedings of the 20th international conference on Software engineering, p.167-176, April 19-25, 1998, Kyoto, Japan
• 8: DETLEFS, D. L., LEINO, K. R. M., NELSON, G., AND SAXE, J. B. Extended static checking. Tech. Rep. 159, Compaq Systems Research Center, http://www.resem'ch.digital.com/SRC, 1998.
• 9: Cormac Flanagan , Martín Abadi, Object Types against Races, Proceedings of the 10th International Conference on Concurrency Theory, p.288-303, August 24-27, 1999
• 10: Cormac Flanagan , Martín Abadi, Types for Safe Locking, Proceedings of the 8th European Symposium on Programming Languages and Systems, p.91-108, March 22-28, 1999
• 11: Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.219-232, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 13: 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]
• 14: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 15: John Hogg, Islands: aliasing protection in object-oriented languages, Conference proceedings on Object-oriented programming systems, languages, and applications, p.271-285, October 06-11, 1991, Phoenix, Arizona, United States
• 16: HOLT, R. C. Concurrent Euclid, the Unix System, and Tunis. Addison-Wesley, Reading, Mass., 1983.
• 17: Geraint Jones, Programming in Occam, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1986
• 18: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 19: J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
• 20: MAY, C., SILHA, E., SIMPSON, R., AND WARREN, H., Eds. The PowerPC Architecture. Morgan Kaufmann, 1994.
• 21: 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]
• 22: John C. Reynolds, Syntactic control of interference, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-46, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512766]
• 23: Douglas C. Schmidt , Tim Harrison, Double-checked locking, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 24: Robert E. Strom , David F. Bacon , Arthur P. Goldberg , Andy Lowry , Daniel M. Yellin , Shaula Alexander Yemini, Hermes: a language for distributed computing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 25: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 26: WroTH, N. Design and implementation of Modula. Software - Practice and Experience 7, 1 (Jan.-Feb. 1977), 67-s4.
• 27: WroTH, N. Modula: a language for modular multiprogramming. Software - Practice and Experience 7, 1 (Jam-Feb. 1977), 3-35.

INDEX TERMS

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

          Nouns: Java

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Languages, Performance, Theory

Keywords:
Java, concurrency, data races, monitors, multiprocessors, programming languages, thread safety