Atomicity via source-to-source translation

ABSTRACT

We present an implementation and evaluation of atomicity (also known as software transactions) for a dialect of Java. Our implementation is fundamentally different from prior work in three respects: (1) It is entirely a source-to-source translation, producing Java source code that can be compiled by any Java compiler and run on any Java Virtual Machine. (2) It can enforce "strong" atomicity without assuming special hardware or a uniprocessor. (3) The implementation uses locks rather than optimistic concurrency, but it cannot deadlock and requires inter-thread communication only when there is data contention.

REFERENCES

• 1: Martin Abadi , Cormac Flanagan , Stephen N. Freund, Types for safe locking: Static race detection for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.2, p.207-255, March 2006 [doi>10.1145/1119479.1119480]
• 2: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 4: C. Blundell, E. C. Lewis, and M. M. K. Martin. Deconstructing transactions: The subtleties of atomicity. In 4th Workshop on Duplicating, Deconstructing, and Debunking, June 2005.
• 5: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 6: Brian D. Carlstrom , Austen McDonald , Hassan Chafi , JaeWoong Chung , Chi Cao Minh , Christos Kozyrakis , Kunle Olukotun, The Atomos transactional programming language, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 7: R. Ennals. Software transactional memory should not be obstruction-free, 2005. http://www.cambridge.intel-research.net/ren-nais/notlockfree.pdf.
• 8: Cormac Flanagan , Stephen N. Freund , Marina Lifshin, Type inference for atomicity, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.47-58, January 10-10, 2005, Long Beach, California, USA [doi>10.1145/1040294.1040299]
• 9: D. Grossman. Software transactions are to concurrency as garbage collection is to memory management. Technical Report 2006-04-01, Univ. of Washington Dept. of Comp. Sci. & Engr., Feb. 2006.
• 10: R. Guerraoui, M. Herlihy, and S. Pochon. Polymorphic contention management. In 19th International Symposium on Distributed Computing, Sept. 2005.
• 11: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 12: T. Harris. Exceptions and side-effects in atomic blocks. In PODC Workshop on Concurrency and Synchronization in Java Programs, July 2004.
• 13: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 14: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 15: Tim Harris , Simon Marlow , Simon Peyton Jones, Haskell on a shared-memory multiprocessor, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.49-61, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088354]
• 16: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 17: 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]
• 18: B. Hindman and D. Grossman. Strong atomicity for Java without virtual-machine support. Technical Report 2006-05-01, Univ. of Washington Dept. of Computer Science & Engineering, May 2006.
• 19: Jeremy Manson , Jason Baker , Antonio Cunei , Suresh Jagannathan , Marek Prochazka , Bin Xin , Jan Vitek, Preemptible Atomic Regions for Real-Time Java, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.62-71, December 05-08, 2005 [doi>10.1109/RTSS.2005.34]
• 20: Jeremy Manson , William Pugh , Sarita V. Adve, The Java memory model, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-391, January 12-14, 2005, Long Beach, California, USA
• 21: V. J. Marathe, W. N. S. III, and M. L. Scott. Adaptive software transactional memory. In 19th International Symposium on Distributed Computing, Sept. 2005.
• 22: V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. S. III, and M. L. Scott. Lowering the overhead of nonblocking software transactional memory. Technical Report TR 893, Computer Science Department, University of Rochester, Mar. 2006.
• 23: Bill McCloskey , Feng Zhou , David Gay , Eric Brewer, Autolocker: synchronization inference for atomic sections, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.346-358, January 11-13, 2006, Charleston, South Carolina, USA
• 24: Austen McDonald , JaeWoong Chung , Brian D. Carlstrom , Chi Cao Minh , Hassan Chafi , Christos Kozyrakis , Kunle Olukotun, Architectural Semantics for Practical Transactional Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.53-65, June 17-21, 2006
• 25: N. Nystrom, M. R. Clarkson, and A. C. Myers. Polyglot: An extensible compiler framework for Java. In 12th International Conference on Compiler Construction, volume 2622 of Lecture Notes in Computer Science, Apr. 2003.
• 26: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 27: Michael F. Ringenburg , Dan Grossman, AtomCaml: first-class atomicity via rollback, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 28: N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, Special Issue(10), 1997.
• 29: TRANSACT: 1st ACM SIGPLAN workshop on languages, compilers, and hardware support for transactional computing, June 2006. http://www.cs.purdue.edu/homes/jv/events/TRANSACT/.
• 30: Willem Visser , Klaus Havelund , Guillaume Brat , Seungjoon Park , Flavio Lerda, Model Checking Programs, Automated Software Engineering, v.10 n.2, p.203-232, April 2003 [doi>10.1023/A:1022920129859]
• 31: 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
• 32: A. Welc, S. Jagannathan, and A. L. Hosking. Transactional monitors for concurrent objects. In European Conference on Object-Oriented Programming, 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages

Keywords:
Java, atomicity, concurrent programming, transactional memory