Safe futures for Java

ABSTRACT

A future is a simple and elegant abstraction that allows concurrency to be expressed often through a relatively small rewrite of a sequential program. In the absence of side-effects, futures serve as benign annotations that mark potentially concurrent regions of code. Unfortunately, when computation relies heavily on mutation as is the case in Java, its meaning is less clear, and much of its intended simplicity lost.This paper explores the definition and implementation of safe futures for Java. One can think of safe futures as truly transparent annotations on method calls, which designate opportunities for concurrency. Serial programs can be made concurrent simply by replacing standard method calls with future invocations. Most significantly, even though some parts of the program are executed concurrently and may indeed operate on shared data, the semblance of serial execution is nonetheless preserved. Thus, program reasoning is simplified since data dependencies present in a sequential program are not violated in a version augmented with safe futures.Besides presenting a programming model and API for safe futures, we formalize the safety conditions that must be satisfied to ensure equivalence between a sequential Java program and its future-annotated counterpart. A detailed implementation study is also provided. Our implementation exploits techniques such as object versioning and task revocation to guarantee necessary safety conditions. We also present an extensive experimental evaluation of our implementation to quantify overheads and limitations. Our experiments indicate that for programs with modest mutation rates on shared data, applications can use futures to profitably exploit parallelism, without sacrificing safety.

REFERENCES

• 1: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 2: Jonathan Aldrich , Emin Gün Sirer , Craig Chambers , Susan J. Eggers, Comprehensive synchronization elimination for Java, Science of Computer Programming, v.47 n.2-3, p.91-120, May 2003 [doi>10.1016/S0167-6423(02)00129-6]
• 3: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 4: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 5: Bernstein, A. Program analysis for parallel processing. IEEE Transactions on Computers 15, 5 (Oct. 1966), 757--762.
• 6: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 7: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 8: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, ACM SIGPLAN Notices, v.37 n.11, November 2002
• 9: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 10: Michael J. Carey , David J. DeWitt , Chander Kant , Jeffrey F. Naughton, A status report on the OO7 OODBMS benchmarking effort, ACM SIGPLAN Notices, v.29 n.10, p.414-426, Oct. 1994
• 11: Michael J. Carey , David J. DeWitt , Jeffrey F. Naughton, The 007 Benchmark, ACM SIGMOD Record, v.22 n.2, p.12-21, June 1, 1993
• 12: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 13: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 14: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, ACM SIGPLAN Notices, v.33 n.10, p.48-64, Oct. 1998
• 15: Cormac Flanagan , Matthias Felleisen, The semantics of future and its use in program optimization, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.209-220, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199484]
• 16: C. Flanagan , M. Felleisen, The semantics of future and an application, Journal of Functional Programming, v.9 n.1, p.1-31, January 1999 [doi>10.1017/S0956796899003329]
• 17: 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
• 18: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.256-267, January 14-16, 2004, Venice, Italy
• 19: Cormac Flanagan , Shaz Qadeer, Types for atomicity, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 20: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 21: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 22: Tim Harris , Keir Fraser, Language support for lightweight transactions, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 23: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 24: M. P. Herlihy , J. E. B. Moss, Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.304-311, May 1992 [doi>10.1109/71.139204]
• 25: Antony L. Hosking , J. Eliot B. Moss, Object fault handling for persistent programming languages: a performance evaluation, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.288-303, September 26-October 01, 1993, Washington, D.C., United States
• 26: Jensen, E. H., Hagensen, G. W., and Broughton, J. M. A new approach to exclusive data access in shared memory multiprocessors. Tech. rep., Lawrence Livermore National Laboratories, 1987.
• 27: JSR166: Concurrency utilities. http://java.sun.com/j2se/1.5.0/docs/guide/concurrency/.
• 28: M. Katz, PARATRAN: A TRANSPARENT, TRANSACTION BASED RUNTIME MECHANISM FOR PARALLEL EXECUTION OF SCHEME, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 29: N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
• 30: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, ACM SIGPLAN Notices, v.24 n.7, p.81-90, July 1989
• 31: B. Liskov , L. Shrira, Promises: linguistic support for efficient asynchronous procedure calls in distributed systems, ACM SIGPLAN Notices, v.23 n.7, p.260-267, July 1988
• 32: John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
• 33: Eric Mohr , David A. Kranz , Robert H. Halstead, Jr., Lazy task creation: a technique for increasing the granularity of parallel programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.185-197, June 27-29, 1990, Nice, France [doi>10.1145/91556.91631]
• 34: Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 35: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Denver, Colorado, Nov.). ACM SIGPLAN Notices 34, 10 (Oct. 1999).
• 36: Polyvios Pratikakis , Jaime Spacco , Michael Hicks, Transparent proxies for java futures, ACM SIGPLAN Notices, v.39 n.10, October 2004
• 37: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 38: Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
• 39: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 40: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 41: L. A. Smith , J. M. Bull , J. Obdrzálek, A parallel java grande benchmark suite, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.8-8, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582042]
• 42: Cristian Ungureanu , Suresh Jagannathan, Concurrency Analysis for Java, Proceedings of the 7th International Symposium on Static Analysis, p.413-432, June 29-July 01, 2000
• 43: Christoph von Praun , Thomas R. Gross, Object race detection, ACM SIGPLAN Notices, v.36 n.11, p.70-82, 11/01/2001
• 44: Christoph von Praun , Thomas R. Gross, Static conflict analysis for multi-threaded object-oriented programs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 45: Welc, A., Jagannathan, S., and Hosking, A. L. Transactional monitors for concurrent objects. In Proceedings of the European Conference on Object-Oriented Programming (Oslo, Norway, June), M. Odersky, Ed. vol. 3086 of Lecture Notes in Computer Science. Springer-Verlag, 2004, pp. 519--542.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages; Object-oriented languages
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines; Control structures; Concurrent programming structures

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
Java, concurrency, futures, safety