Composable memory transactions

ABSTRACT

Writing concurrent programs is notoriously difficult, and is of increasing practical importance. A particular source of concern is that even correctly-implemented concurrency abstractions cannot be composed together to form larger abstractions. In this paper we present a new concurrency model, based on transactional memory, that offers far richer composition. All the usual benefits of transactional memory are present (e.g. freedom from deadlock), but in addition we describe new modular forms of blocking and choice that have been inaccessible in earlier work.

REFERENCES

• 1: Nick Benton , Luca Cardelli , Cédric Fournet, Modern Concurrency Abstractions for C#, Proceedings of the 16th European Conference on Object-Oriented Programming, p.415-440, June 10-14, 2002
• 2: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 3: Daume III, H. Yet Another Haskell Tutorial. 2004. Available at http://www.isi.edu/~hdaume/htut/ or via http://www.haskell.org/.
• 4: Ennals, R. Feris: a functional environment for retargetable interactive systems. Batchelors thesis, University of Cambridge Computer Laboratory, 2000.
• 5: Matthew Flatt , Robert Bruce Findler, Kill-safe synchronization abstractions, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 6: Fraser, K. Practical lock-freedom. PhD thesis, University of Cambridge Computer Laboratory, Feb. 2004. Also published as UCAM-CL-TR-579.
• 7: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 8: 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
• 9: 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
• 10: 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]
• 11: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 12: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 13: Mick J. Jordan , Malcolm P. Atkinson, Orthogonal Persistence for Java? - A Mid-term Report, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.335-352, January 1999
• 14: Kelsey, R., Rees, J., and Sperber, M. The incomplete scheme 48 reference manual for release 1.1. July 2004.
• 15: Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991 [doi>10.1145/125223.125244]
• 16: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 17: Simon Marlow , Simon Peyton Jones , Andrew Moran , John Reppy, Asynchronous exceptions in Haskell, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.274-285, June 2001, Snowbird, Utah, United States
• 18: José F. Martínez , Josep Torrellas, Speculative synchronization: applying thread-level speculation to explicitly parallel applications, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 19: E. B. Moss, NESTED TRANSACTIONS: AN APPROACH TO RELIABLE DISTRIBUTED COMPUTING, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 20: Jeffrey Oplinger , Monica S. Lam, Enhancing software reliability with speculative threads, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 21: Peyton Jones, S. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In Engineering theories of software construction, Marktoberdorf Summer School 2000, C. Hoare, M. Broy, and R. Steinbrueggen, Eds., NATO ASI Series, IOS Press, pp. 47--96.
• 22: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 23: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 24: 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
• 25: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 26: M. Satyanarayanan , Henry H. Mashburn , Puneet Kumar , David C. Steere , James J. Kistler, Lightweight recoverable virtual memory, ACM Transactions on Computer Systems (TOCS), v.12 n.1, p.33-57, Feb. 1994 [doi>10.1145/174613.174615]
• 27: 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]
• 28: Shinnar, A., Tarditi, D., Plesko, M., and Steensgaard, B. Integrating support for undo with exception handling. Tech. Rep. MSR-TR-2004-140, Microsoft Research, Dec. 2004.
• 29: Janice M. Stone , Harold S. Stone , Philip Heidelberger , John Turek, Multiple Reservations and the Oklahoma Update, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.4, p.58-71, November 1993 [doi>10.1109/88.260295]
• 30: Adam Welc , Antony L. Hosking , Suresh Jagannathan, Preemption-Based Avoidance of Priority Inversion for Java, Proceedings of the 2004 International Conference on Parallel Processing (ICPP'04), p.529-538, August 15-18, 2004 [doi>10.1109/ICPP.2004.60]
• 31: Welc, A., Jagannathan, S., and Hosking, A. Transactional monitors for concurrent objects. In Proceedings of the European Conference on Object-Oriented Programming (June 2004).

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Languages

Keywords:
locks, non-blocking algorithms, transactions