skip to main content
10.1145/1229428.1229442acmconferencesArticle/Chapter ViewAbstractPublication PagesppoppConference Proceedingsconference-collections
Article

Open nesting in software transactional memory

Published: 14 March 2007 Publication History

Abstract

Transactional memory (TM) promises to simplify concurrent programming while providing scalability competitive to fine-grained locking. Language-based constructs allow programmers to denote atomic regions declaratively and to rely on the underlying system to provide transactional guarantees along with concurrency. In contrast with fine-grained locking, TM allows programmers to write simpler programs that are composable and deadlock-free.
TM implementations operate by tracking loads and stores to memory and by detecting concurrent conflicting accesses by different transactions. By automating this process, they greatly reduce the programmer's burden, but they also are forced to be conservative. Incertain cases, conflicting memory accesses may not actually violate the higher-level semantics of a program, and a programmer may wish to allow seemingly conflicting transactions to execute concurrently.
Open nested transactions enable expert programmers to differentiate between physical conflicts, at the level of memory, and logical conflicts that actually violate application semantics. A TMsystem with open nesting can permit physical conflicts that are not logical conflicts, and thus increase concurrency among application threads.
Here we present an implementation of open nested transactions in a Java-based software transactional memory (STM)system. We describe new language constructs to support open nesting in Java, and we discuss new abstract locking mechanisms that a programmer can use to prevent logical conflicts. We demonstrate how these constructs can be mapped efficiently to existing STM data structures. Finally, we evaluate our system on a set of Java applications and data structures, demonstrating how open nesting can enhance application scalability.

References

[1]
Ali-Reza Adl-Tabatabai, Brian T. Lewis, Vijay S. Menon, Brian R. Murphy, Bratin Saha, and Tatiana Shpeisman. Compiler and runtime support for efficient software transactional memory. In PLDI, pages 26--37, June 2006.
[2]
Brian D. Carlstrom, Austen McDonald, Hassan Chafi, JaeWoong Chung, Chi Cao Minh, Christos Kozyrakis, and Kunle Olukotun. The Atomos transactional programming language. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 1--13, New York, NY, USA, 2006. ACM Press.
[3]
Hector Garcia-Molina. Using semantic knowledge for transaction processing in a distributed database. ACM Trans. Database Syst., 8(2):186--213, 1983.
[4]
Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
[5]
Tim Harris and Keir Fraser. Language support for lightweight transactions. In OOPSLA 2003: Object-Oriented Programing, Systems, Languages, and Applications, pages 388--402, New York, NY, USA, 2003. ACM Press.
[6]
Tim Harris, Simon Marlow, Simon Peyton-Jones, and Maurice Herlihy. Composable memory transactions. In PPoPP 2005: Principles and Practice of Parallel Programming, pages 48--60, New York, NY, USA, 2005. ACM Press.
[7]
Maurice Herlihy, Victor Luchangco, Mark Moir, and III William N. Scherer. Software transactional memory for dynamic-sized data structures. In PODC 2003: Principles of Distributed Computing, pages 92--101, New York, NY, USA, 2003. ACM Press.
[8]
Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA 1993: International Symposium on Computer Architecture, pages 289--300, New York, NY, USA, 1993. ACM Press.
[9]
Virendra J. Marathe, William N. Scherer, and Michael L. Scott. Design tradeoffs in modern software transactional memory systems. In LCR 2004: Languages, Compilers, and Run-time Support for Scalable Systems, 2004.
[10]
Austen McDonald, JaeWoong Chung, Brian D. Carlstrom, Chi Cao Minh, Hassan Chafi, Christos Kozyrakis, and Kunle Olukotun. Architectural semantics for practical transactional memory. In ISCA '06: Proceedings of the 33rd International Symposium on Computer Architecture, pages 53--65, Washington, DC, USA, 2006. IEEE Computer Society.
[11]
Michelle J. Moravan, Jayaram Bobba, Kevin E. Moore, Luke Yen, Mark D. Hill, Ben Liblit, Michael M. Swift, and David A. Wood. Supporting nested transactional memory in LogTM. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 378--391, San Jose, California, October 2006. Association for Computing Machinery.
[12]
J. Eliot B. Moss. Nested transactions: an approach to reliable distributed computing. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1981.
[13]
J. Eliot B. Moss. Open nested transactions: Semantics and support. In WMPI 2005, 2005. Poster presentation.
[14]
J. Eliot B. Moss and Antony L. Hosking. Nested transactional memory: model and preliminary architecture sketches. In OOPSLA Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL), 2005.
[15]
J. Eliot B. Moss and Antony L. Hosking. Nested transactional memory: Model and architecture sketches. Science of Computer Programming (Elsevier), 63(2):186--201, December 2006.
[16]
Nathaniel Nystrom, Michael R. Clarkson, and Andrew C. Myers. Polyglot: an extensible compiler framework for Java. In CC: International Conference on Compiler Construction, Lecture Notes in Computer Science 2622, pages 138--152, April 2003.
[17]
Ravi Rajwar, Maurice Herlihy, and Konrad Lai. Virtualizing transactional memory. In ISCA 2005: International Symposium on Computer Architecture, pages 494--505, Washington, DC, USA, 2005. IEEE Computer Society.
[18]
Michael F. Ringenburg and Dan Grossman. AtomCaml: first-class atomicity via rollback. In ICFP 2005: International Conference on Functional Programming, pages 92--104, New York, NY, USA, 2005. ACM Press.
[19]
Bratin Saha, Ali-Reza Adl-Tabatabai, Rick Hudson, Chi Cao Minh, and Benjamin Hertzberg. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In PPoPP: Principles and Practice of Parallel Programming, pages 187--197, 2006.
[20]
Nir Shavit and Dan Touitou. Software transactional memory. In PODC 1995: Principles of Distributed Computing, pages 204--213, New York, NY, USA, 1995. ACM Press.
[21]
Gerhard Weikum. A theoretical foundation of multi-level concurrency control. In PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, pages 31--43, New York, NY, USA, 1986. ACM Press.
[22]
Gerhard Weikum, Christof Hasse, Peter Broessler, and Peter Muth. Multi-level recovery. In PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 109--123, New York, NY, USA, 1990. ACM Press.
[23]
Adam Welc, Suresh Jagannathan, and Antony L. Hosking. Transactional monitors for concurrent objects. In ECOOP 2004: European Conference on Object-Oriented Programming, volume 3086 of Lecture Notes in Computer Science, pages 519--542. Springer-Verlag, 2004.

Cited By

View all
  • (2023)When Concurrency Matters: Behaviour-Oriented ConcurrencyProceedings of the ACM on Programming Languages10.1145/36228527:OOPSLA2(1531-1560)Online publication date: 16-Oct-2023
  • (2022)Veracity: declarative multicore programming with commutativityProceedings of the ACM on Programming Languages10.1145/35633496:OOPSLA2(1726-1756)Online publication date: 31-Oct-2022
  • (2022)A Survey of B-Tree Locking TechniquesOn Transactional Concurrency Control10.1007/978-3-031-01873-2_2(17-43)Online publication date: 26-Feb-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming
March 2007
284 pages
ISBN:9781595936028
DOI:10.1145/1229428
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. abstract locks
  2. nested transactions
  3. open nesting
  4. transactional memory

Qualifiers

  • Article

Conference

PPoPP07
Sponsor:

Acceptance Rates

PPoPP '07 Paper Acceptance Rate 22 of 65 submissions, 34%;
Overall Acceptance Rate 230 of 1,014 submissions, 23%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)When Concurrency Matters: Behaviour-Oriented ConcurrencyProceedings of the ACM on Programming Languages10.1145/36228527:OOPSLA2(1531-1560)Online publication date: 16-Oct-2023
  • (2022)Veracity: declarative multicore programming with commutativityProceedings of the ACM on Programming Languages10.1145/35633496:OOPSLA2(1726-1756)Online publication date: 31-Oct-2022
  • (2022)A Survey of B-Tree Locking TechniquesOn Transactional Concurrency Control10.1007/978-3-031-01873-2_2(17-43)Online publication date: 26-Feb-2022
  • (2021)Descriptor based consensus for blockchain transactionsProceedings of the 15th ACM International Conference on Distributed and Event-based Systems10.1145/3465480.3466927(114-125)Online publication date: 28-Jun-2021
  • (2021)Decomposing Data Structure Commutativity Proofs with $$m\!n$$-DifferencingVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-67067-2_5(81-103)Online publication date: 12-Jan-2021
  • (2020)Nesting and composition in transactional data structure librariesProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374514(405-406)Online publication date: 19-Feb-2020
  • (2020)Optimized Transactional Data Structure Approach to Concurrency Control for In-Memory Databases2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)10.1109/SBAC-PAD49847.2020.00025(107-115)Online publication date: Sep-2020
  • (2020)Synthesizing Precise and Useful Commutativity ConditionsJournal of Automated Reasoning10.1007/s10817-020-09573-wOnline publication date: 29-Aug-2020
  • (2019)On Transactional Concurrency ControlSynthesis Lectures on Data Management10.2200/S00912ED2V01Y201904DTM05914:5(1-404)Online publication date: 11-Jun-2019
  • (2019)MV-RLUProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304040(779-792)Online publication date: 4-Apr-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media