A runtime system for software lock elision

ABSTRACT

The advent of multi-core processors means that exploiting parallelism is key to increasing the performance of programs. Many researchers have studied the use of atomic blocks as a way to simplify the construction of scalable parallel programs. However, there is a large body of existing lock-based code, and typically it is incorrect to simply replace lock-based critical sections with atomic blocks. Some problems include the need to do IO within critical sections; the use of primitives such as condition variables; and the sometime reliance on underlying lock properties such as fairness or priority inheritance.

In this paper we investigate an alternative: a software runtime system that allows threads to speculatively execute lock-based critical sections in parallel. Execution proceeds optimistically, dynamically detecting conflicts between accesses by concurrent threads. However, if there are frequent conflicts, or if there are attempts to perform operations that cannot be done speculatively, then execution can fall back to acquiring a lock. Conversely, implementations of atomic blocks must typically serialise all operations that cannot be performed speculatively.

Our runtime system has been designed with the requirements of systems code in mind: in particular it does not require that programs be written in type-safe languages, nor does it require any form of garbage collection. Furthermore, we never require a thread holding a lock to wait for a thread that has speculatively acquired it. This lets us retain any useful underlying properties of a given lock implementation, e.g. fairness or priority inheritance.

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: R. D. Blumofe , C. F. Joerg , B. C. Kuszmaul , C. E. Leiserson , K. H Randall , Y. Zhou, Cilk: An Efficient Multithreaded Runtime System, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 4: 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
• 5: Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC '08: Proc. IEEE International Symposium on Workload Characterization, pages 35--46, September 2008.
• 6: Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC '06: Proc. 20th International Symposium on Distributed Computing, pages 194--208, September 2006.
• 7: Keir Fraser. Practical lock freedom. PhD thesis, Cambridge University Computer Laboratory, 2003. Also available as Technical Report UCAM-CL-TR-579.
• 8: 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
• 9: Tim Harris , Keir Fraser, Revocable locks for non-blocking programming, 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.1065954]
• 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: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 12: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• 13: Jim Larus and Ravi Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2007.
• 14: Virendra Jayant Marathe , Mark Moir, Toward high performance nonblocking software 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.1345240]
• 15: Virendra J. Marathe, Michael F. Spear, Christopher Heriot, Athul Acharya, David Eisenstat, William N. Scherer, III, and Michael L. Scott. Lowering the overhead of software transactional memory. Technical Report TR 893, Computer Science Department, University of Rochester, March 2006.
• 16: Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Richard Hudson, Bratin Saha, and Adam Welc. Single global lock semantics in a weakly atomic S™. In TRANSACT '08, 3rd ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, February 2008.
• 17: Vijay Menon, Steven Balensiefer, Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Richard L. Hudson, Bratin Saha, and Adam Welc. Towards a lock-based semantics for Java S™. Technical Report UW-CSE-07-11-01, University of Washington, Nov 2007.
• 18: Maged M. Michael, Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.491-504, June 2004 [doi>10.1109/TPDS.2004.8]
• 19: Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. Log™: Log-based transactional memory. In Proc. 12th International Symposium on High-Performance Computer Architecture, pages 254--265. February 2006.
• 20: Marek Olszewski , Jeremy Cutler , J. Gregory Steffan, JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.365-375, September 15-19, 2007 [doi>10.1109/PACT.2007.42]
• 21: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 22: Torvald Riegel and Diogo Becker de Brum. Making object-based S™ practical in unmanaged environments. In TRANSACT '08, 3rd ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, February 2008.
• 23: Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 24: Amitabha Roy, Steven Hand, and Tim Harris. Exploring the Limits of Disjoint Access Parallelism. In Proceedings of HotPar '09: 1st USENIX Workshop on Hot Topics in Parallelism (to appear), March 2009.
• 25: Yannis Smaragdakis , Anthony Kay , Reimer Behrends , Michal Young, General and efficient locking without blocking, Proceedings of the 2008 ACM SIGPLAN workshop on Memory systems performance and correctness: held in conjunction with the Thirteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '08), March 02-02, 2008, Seattle, Washington [doi>10.1145/1353522.1353524]
• 26: Michael F. Spear, Virendra J. Marathe, Luke Dalessandro, and Michael L. Scott. Privatization techniques for software transactional memory. Technical Report TR 915, Computer Science Department, University of Rochester, February 2007.
• 27: Michael F. Spear, Maged M. Michael, and Michael L. Scott. Inevitability mechanisms for software transactional memory. In TRANSACT '08: Proc 3rd ACM SIGPLAN Workshop on Transactional Computing. February 2008.
• 28: Cheng Wang , Wei-Yu Chen , Youfeng Wu , Bratin Saha , Ali-Reza Adl-Tabatabai, Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language, Proceedings of the International Symposium on Code Generation and Optimization, p.34-48, March 11-14, 2007 [doi>10.1109/CGO.2007.4]
• 29: Yin Wang, Terence Kelly, Manjunath Kudlur, Stéphane Lafortune, and Scott A. Mahlke. Gadara: Dynamic deadlock avoidance for multithreaded programs. In OSDI '08: Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, pages 281--294, 2008.
• 30: Adam Welc , Bratin Saha , Ali-Reza Adl-Tabatabai, Irrevocable transactions and their applications, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378584]
• 31: Lukasz Ziarek , Adam Welc , Ali-Reza Adl-Tabatabai , Vijay Menon , Tatiana Shpeisman , Suresh Jagannathan, A Uniform Transactional Execution Environment for Java, Proceedings of the 22nd European conference on Object-Oriented Programming, July 07-11, 2008, Paphos, Cypress [doi>10.1007/978-3-540-70592-5_7]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
revocable locks, software transactional memory, speculative lock elision, unmanaged environments