TxLinux: using and managing hardware transactional memory in an operating system

ABSTRACT

TxLinux is a variant of Linux that is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first to manage HTM in the scheduler. This paper describes and measures TxLinux and discusses two innovations in detail: cooperation between locks and transactions, and theintegration of transactions with the OS scheduler. Mixing locks and transactions requires a new primitive, cooperative transactional spinlocks (cxspinlocks) that allow locks and transactions to protect the same data while maintaining the advantages of both synchronization primitives. Cxspinlocks allow the system to attemptexecution of critical regions with transactions and automatically roll back to use locking if the region performs I/O. Integrating the scheduler with HTM eliminates priority inversion. On a series ofreal-world benchmarks TxLinux has similar performance to Linux, exposing concurrency with as many as 32 concurrent threads on 32 CPUs in the same critical region.

REFERENCES

• 1: BES. Akgul, VJM. III, HThane, and PKuacharoen. Hardware support for priority inheritance. rtss, 00:246, 2003.
• 2: Alaa R. Alameldeen , David A. Wood, Variability in Architectural Simulations of Multi-Threaded Workloads, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.7, February 08-12, 2003
• 3: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 4: Colin Blundell , Joe Devietti , E. Christopher Lewis , Milo M. K. Martin, Making the fast case common and the uncommon case simple in unbounded transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: 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. Jun 2005.
• 6: Daniel Bovet , Marco Cesati, Understanding The Linux Kernel, Oreilly & Associates Inc, 2005
• 7: Brian D. Carlstrom , Austen McDonald , Hassan Chafi , JaeWoong Chung , Chi Cao Minh , Christos Kozyrakis , Kunle Olukotun, The Atomos transactional programming language, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 8: Andy Chou , Junfeng Yang , Benjamin Chelf , Seth Hallem , Dawson Engler, An empirical study of operating systems errors, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 9: Weihaw Chuang , Satish Narayanasamy , Ganesh Venkatesh , Jack Sampson , Michael Van Biesbrouck , Gilles Pokam , Brad Calder , Osvaldo Colavin, Unbounded page-based transactional memory, ACM SIGPLAN Notices, v.41 n.11, November 2006
• 10: JaeWoong Chung , Chi Cao Minh , Austen McDonald , Travis Skare , Hassan Chafi , Brian D. Carlstrom , Christos Kozyrakis , Kunle Olukotun, Tradeoffs in transactional memory virtualization, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 11: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 12: E. Elnozahy, D. Johnson, and Y. Wang. A survey of rollback-recovery protocols in message-passing systems, 1996.
• 13: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 14: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 15: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 16: Michael Greenwald , David Cheriton, The synergy between non-blocking synchronization and operating system structure, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.123-136, October 29-November 01, 1996, Seattle, Washington, United States
• 17: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 18: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 19: Tim Harris, Exceptions and side-effects in atomic blocks, Science of Computer Programming, v.58 n.3, p.325-343, December 2005 [doi>10.1016/j.scico.2005.03.005]
• 20: 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]
• 21: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 22: 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
• 23: O. S. Hofmann, D. E. Porter, C. J. Rossbach, H. E. Ramadan, and E. Witchel. Solving difficult HTM problems without difficult hardware. In ACM TRANSACT Workshop, 2007.
• 24: Intel Corporation. IA-32 Intel Architecture Software Developer's Manuals, 2006. http://developer.intel.com/design/processor/.
• 25: Sanjeev Kumar , Michael Chu , Christopher J. Hughes , Partha Kundu , Anthony Nguyen, Hybrid transactional memory, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123003]
• 26: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 27: Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
• 28: Butler W. Lampson, A scheduling philosophy for multiprocessing systems, Communications of the ACM, v.11 n.5, p.347-360, May 1968 [doi>10.1145/363095.363144]
• 29: J. R. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool, 2006.
• 30: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 31: Henry Massalin , Calton Pu, A Lock-Free Multiprocessor OS Kernel, ACM SIGOPS Operating Systems Review, v.26 n.2, p.108, April 1992
• 32: 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
• 33: Jim Mauro , Richard McDougall, Solaris Internals (2nd Edition), Prentice Hall PTR, Upper Saddle River, NJ, 2006
• 34: Microsoft Corporation. Transactional NTFS (TxF), 2006. http://msdn2.microsoft.com/en-us/library/aa365456.aspx.
• 35: K. E. Moore, JBobba, M. J. Moravan, MD. Hill , and D. A. Wood. Logtm: Log-based transactional memory. In HPCA, 2006.
• 36: Michelle J. Moravan , Jayaram Bobba , Kevin E. Moore , Luke Yen , Mark D. Hill , Ben Liblit , Michael M. Swift , David A. Wood, Supporting nested transactional memory in logTM, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 37: E. Moss and T. Hosking. Nested transactional memory: Model and preliminary architecture sketches. In SCOOL, 2005.
• 38: J. Eliot B Moss , Nancy D. Griffeth , Marc H. Graham, Abstraction in recovery management, ACM SIGMOD Record, v.15 n.2, p.72-83, June 1986
• 39: 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]
• 40: J. K. Ousterhout. Why aren't operating systems getting faster as fast as hardware? In USENIX Summer, 1990.
• 41: C. Pramode. Experiments with kernel 2.6 on a hyperthreaded Pentium 4 LG. Linux Gazette, 2007.
• 42: 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
• 43: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 44: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 45: H. Ramadan, C. Rossbach, D. Porter, O. Hofmann, A. Bhandari, and E. Witchel. Evaluating transactional memory tradeoffs with TxLinux. In ISCA, 2007.
• 46: H. Ramadan, C. Rossbach, and E. Witchel. The Linux kernel: A challenging workload for transactional memory. In Workshop on Transactional Memory Workloads, June 2006.
• 47: S. Rostedt and D. V. Hart. Internals of the RT patch. In Linux Symposium, 2007.
• 48: Mark E. Russinovich , David A. Solomon, Microsoft Windows Internals, Fourth Edition: Microsoft Windows Server(TM) 2003, Windows XP, and Windows 2000 (Pro-Developer), Microsoft Press, Redmond, WA, 2004
• 49: Bratin Saha , Ali-Reza Adl-Tabatabai , Quinn Jacobson, Architectural Support for Software Transactional Memory, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.185-196, December 09-13, 2006 [doi>10.1109/MICRO.2006.9]
• 50: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 51: Herb Sutter , James Larus, Software and the concurrency revolution, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095421]
• 52: A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
• 53: S. Tweedie. Journaling the Linux ext2fs filesystem. In LinuxExpo '98, 1998.
• 54: A. Welc, A. L. Hosking, and S. Jagannathan.Transparently reconciling transactions with locking for java synchronization. In ECOOP, Jul 2006.
• 55: Luke Yen , Jayaram Bobba , Michael R. Marty , Kevin E. Moore , Haris Volos , Mark D. Hill , Michael M. Swift , David A. Wood, LogTM-SE: Decoupling Hardware Transactional Memory from Caches, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.261-272, February 10-14, 2007 [doi>10.1109/HPCA.2007.346204]
• 56: C. Zilles and L. Baugh. Extending hardware transactional memory to support non-busy waiting and non-transactional actions. In ACM TRANSACT Workshop, Jun 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Threads; Mutual exclusion

General Terms:
Design, Performance

Keywords:
MetaTM, TxLinux, operating systems, optimistic concurrency, synchronization, transactional memory