Language support for lightweight transactions

ABSTRACT

Concurrent programming is notoriously difficult. Current abstractions are intricate and make it hard to design computer systems that are reliable and scalable. We argue that these problems can be addressed by moving to a declarative style of concurrency control in which programmers directly indicate the safety properties that they require. In our scheme the programmer demarks sections of code which execute within lightweight software-based transactions that commit atomically and exactly once. These transactions can update shared data, instantiate objects, invoke library features and so on. They can also block, waiting for arbitrary boolean conditions to become true. Transactions which do not access the same shared memory locations can commit concurrently. Furthermore, in general, no performance penalty is incurred for memory accesses outside transactions.We present a detailed design of this proposal along with an implementation and evaluation. We argue that the resulting system (i) is easier for mainstream programmers to use, (ii) prevents lock-based priority-inversion and deadlock problems and (iii) can offer performance advantages.

REFERENCES

• 1: 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]
• 2: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y. S. Ramakrishna , Derek White, An efficient meta-lock for implementing ubiquitous synchronization, ACM SIGPLAN Notices, v.34 n.10, p.207-222, Oct. 1999
• 3: Gregory R. Andrews, Concurrent programming: principles and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 4: Per Brinch Hansen, Distributed processes: a concurrent programming concept, Communications of the ACM, v.21 n.11, p.934-941, Nov. 1978 [doi>10.1145/359642.359651]
• 5: Brinch Hansen, P. Edison -- a multiprocessor language. Software -- Practice and Experience 11, 4 (Apr. 1981), 325--361.
• 6: 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
• 7: Timothy L. Harris , Keir Fraser , Ian A. Pratt, A Practical Multi-word Compare-and-Swap Operation, Proceedings of the 16th International Conference on Distributed Computing, p.265-279, October 28-30, 2002
• 8: Harris, T. L. Design choices for language-based transactions. University of Cambridge Computer Laboratory Tech. Rep., Aug. 2003.
• 9: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 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 , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 12: Maurice Herlihy , Victor Luchangco , Mark Moir, The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures, Proceedings of the 16th International Conference on Distributed Computing, p.339-353, October 28-30, 2002
• 13: 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
• 14: Hoare, C. A. R. Towards a theory of parallel programming. In Operating Systems Techniques (1972), vol. 9 of A.P.I.C. Studies in Data Processing, Academic Press, pp. 61--71.
• 15: Sheng Liang , Gilad Bracha, Dynamic class loading in the Java virtual machine, ACM SIGPLAN Notices, v.33 n.10, p.36-44, Oct. 1998
• 16: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 17: Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983 [doi>10.1145/2166.357215]
• 18: D. B. Lomet, Process structuring, synchronization, and recovery using atomic actions, Proceedings of an ACM conference on Language design for reliable software, p.128-137, March 28-30, 1977, Raleigh, North Carolina
• 19: Manson, J., and Pugh, W. Semantics of multithreaded Java. Tech. Rep. UCMP-CS-4215, Department of Computer Science, University of Maryland, College Park, Jan. 2002.
• 20: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 21: Maged M. Michael , Michael L. Scott, Correction of a Memory Management Method for Lock-Free Data Structures, University of Rochester, Rochester, NY, 1995
• 22: Mark Moir, Transparent Support for Wait-Free Transactions, Proceedings of the 11th International Workshop on Distributed Algorithms, p.305-319, September 24-26, 1997
• 23: David S. Platt, Introducing Microsoft .Net, Second Edition, Microsoft Press, Redmond, WA, 2002
• 24: Schmid, H. A. On the efficient implementation of conditional critical regions and the construction of monitors. Acta Informatica 6, 3 (Aug. 1976), 227--249.
• 25: Michael L. Scott, Language support for loosely coupled distributed programs, IEEE Transactions on Software Engineering, v.13 n.1, p.88-103, Jan. 1987 [doi>10.1109/TSE.1987.232838]
• 26: 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]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

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

General Terms:
Algorithms, Languages

Keywords:
concurrency, conditional critical regions, non-blocking systems, transactions