Towards transactional memory semantics for C++

ABSTRACT

Transactional memory (TM) eliminates many problems associated with lock-based synchronization. Over recent years, much progress has been made in software and hardware implementation techniques for TM. However, before transactional memory can be integrated into mainstream programming languages, we must precisely define its meaning in the context of these languages. In particular, TM semantics should address the advanced features present in the existing software TM implementations, such as interactions between transactions and locks, explicit user-level abort and support for legacy code.

In this paper, we address these topics from both theoretical and practical points of view. We give precise formulations of several popular TM semantics for the domain of sequentially consistent executions and show that some of these semantics are equivalent for C++ programs that do not contain other forms of synchronization. We show that lock-based semantics, such as Single Global Lock Atomicity (SLA) or Disjoint Lock Atomicity (DLA), do not actually guarantee atomicity for race-free programs and propose a new semantics, Race-Free Atomicity (RFA) that gives such a guarantee. We compare these semantics from the programmer and implementation points of view and explain why supporting non-atomic transactions is useful. Finally, we propose a new set of language constructs that let programmers explicitly specify whether transactions should be atomic and describe how these constructs interact with user-level abort and legacy code.

REFERENCES

• 1: Martín Abadi , Andrew Birrell , Tim Harris , Michael Isard, Semantics of transactional memory and automatic mutual exclusion, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 2: Martín Abadi , Tim Harris , Mojtaba Mehrara, Transactional memory with strong atomicity using off-the-shelf memory protection hardware, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 3: Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.115-126, June 21-25, 2008
• 4: C. Blundell, E. C. Lewis, and M. M. K. Martin. Deconstructing transactions: The subtleties of atomicity. In Fourth Annual Workshop on Duplicating, Deconstructing, and Debunking, 2005.
• 5: H. Boehm. Transactional memory should be an implementation technique, not a programming interface. In to HotPar 2009, to appear.
• 6: Hans-J. Boehm , Sarita V. Adve, Foundations of the C++ concurrency memory model, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 7: Nathan G. Bronson , Christos Kozyrakis , Kunle Olukotun, Feedback-directed barrier optimization in a strongly isolated STM, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
• 8: C++ Standards Committee, Pete Becker, ed. Working draft, standard for programming language C++. C++ standards committee paper WG21/N2857=PL22.16/09-0047, March 2009. http://www.open-std.org/JTC1/ SC22/WG21/docs/papers/2009/n2857.pdf.
• 9: L. Crowl, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Integrating transactional memory into c++. In The Second ACM SIGPLAN Workshop on Transactional Computing, 2007.
• 10: L. Dalessandro and M. L. Scott. Strong isolation is a weak idea. In The Fourth ACM SIGPLAN Workshop on Transactional Computing, 2009.
• 11: Dave Dice , Yossi Lev , Mark Moir , Daniel Nussbaum, Early experience with a commercial hardware transactional memory implementation, Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, March 07-11, 2009, Washington, DC, USA
• 12: D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In DISC 2006.
• 13: 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
• 14: C. Flanagan, S. N. Freund, and J. Yi. Velodrome: A sound and complete dynamic atomicity checker for multithreaded programs.
• 15: Rachid Guerraoui , Michal Kapalka, On the correctness of transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345233]
• 16: 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
• 17: 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]
• 18: 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]
• 19: Benjamin Hindman , Dan Grossman, Atomicity via source-to-source translation, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178611]
• 20: J. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2006.
• 21: Shan Lu , Joseph Tucek , Feng Qin , Yuanyuan Zhou, AVIO: detecting atomicity violations via access interleaving invariants, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 22: Victor Luchangco, Against lock-based semantics for transactional memory, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378549]
• 23: 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
• 24: V. J. Marathe, W. N. Scherer, III, and M. L. Scott. Adaptive software transactional memory. In International Symposium on Distributed Computing 2005.
• 25: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 26: Vijay Menon , Steven Balensiefer , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Bratin Saha , Adam Welc, Practical weak-atomicity semantics for java stm, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378588]
• 27: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 28: Yang Ni , Adam Welc , Ali-Reza Adl-Tabatabai , Moshe Bach , Sion Berkowits , James Cownie , Robert Geva , Sergey Kozhukow , Ravi Narayanaswamy , Jeffrey Olivier , Serguei Preis , Bratin Saha , Ady Tal , Xinmin Tian, Design and implementation of transactional constructs for C/C++, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 29: Florian T. Schneider , Vijay Menon , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai, Dynamic optimization for efficient strong atomicity, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 30: Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 31: Michael F. Spear , Maged M. Michael , Christoph von Praun, RingSTM: scalable transactions with a single atomic instruction, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378583]
• 32: Michael F. Spear , Luke Dalessandro , Virendra J. Marathe , Michael L. Scott, Ordering-Based Semantics for Software Transactional Memory, Proceedings of the 12th International Conference on Principles of Distributed Systems, December 15-18, 2008, Luxor, Egypt [doi>10.1007/978-3-540-92221-6_19]
• 33: Michael F. Spear , Virendra J. Marathe , Luke Dalessandro , Michael L. Scott, Privatization techniques for software transactional memory, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281161]
• 34: H. Volos, N. Goyal, and M. Swift. Pathological interactions of locks with transactional memory. In The Third ACM SIGPLAN Workshop on Transactional Computing, 2008.

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; Frameworks

General Terms:
Design, Languages, Theory

Keywords:
atomicity, c++, serializability, synchronization, transactional memory