Open nesting in software transactional memory

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.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Concurrent programming structures