Safe open-nested transactions through ownership

ABSTRACT

Researchers in transactional memory (TM) have proposed open-nested transactions for increasing concurrency. The idea is to ignore "low-level" memory operations of the open-nested transaction when detecting conflicts for its parent transaction, and instead perform abstract concurrency control for the "high-level" operation that nested transaction represents. Unfortunately, because the TM runtime is unaware of the different levels of memory, an unconstrained use of open-nested commits can lead to anomalous program behavior.

We propose ownership-aware transactional memory (OATM) which explicitly incorporates the notion of modules into the TM system, and requires that transactions and data be associated with specific transactional modules or Xmodules. When a transaction in the OATM commits, the TM system uses this information about Xmodules and commits a piece of data differently depending on whether the current Xmodule owns the data or not. We call this commit mechanism ownership-aware commit, and it is a hybrid between an open-nested and closed-nested commit. Moreover, we give a set of precise constraints on interactions and sharing of data among the Xmodules based on familiar notions of abstractions. We prove that OATM has has clean memory-level semantics and can guarantee serializability by modules, which is an adaptation of multilevel serializability from databases to TM. Finally, we prove that if transactions in the process of aborting obey restrictions on their memory footprint, the OATM is free from semantic deadlock.

REFERENCES

• 1: Kunal Agrawal , Charles E. Leiserson , Jim Sukha, Memory models for open-nested transactions, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178610]
• 2: Chandrasekhar Boyapati , Barbara Liskov , Liuba Shrira, Ownership types for object encapsulation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-223, January 15-17, 2003, New Orleans, Louisiana, USA
• 3: Brian D. Carlstrom , Austen McDonald , Michael Carbin , Christos Kozyrakis , Kunle Olukotun, Transactional collection classes, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229441]
• 4: 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
• 5: 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
• 6: J. E.B. Moss, Nested transactions: an approach to reliable distributed computing, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 7: J. E. B. Moss. Open nested transactions : Semantics and support. In Proceedings of the Workshop on Memory Performance Issues(WMPI), Austin, Texas, Feb 2006.
• 8: J. Eliot B. Moss , Antony L. Hosking, Nested transactional memory: model and architecture sketches, Science of Computer Programming, v.63 n.2, p.186-201, 1 December 2006 [doi>10.1016/j.scico.2006.05.010]
• 9: Yang Ni , Vijay S. Menon , Ali-Reza Adl-Tabatabai , Antony L. Hosking , Richard L. Hudson , J. Eliot B. Moss , Bratin Saha , Tatiana Shpeisman, Open nesting in software transactional memory, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229442]
• 10: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]

INDEX TERMS

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

General Terms:
Design, Languages

Keywords:
abstract serializability, open-nested transactions, ownership types, ownership-aware transactions, serializability by levels, serializability by modules, transactional memory, xmodules