MetaTM/TxLinux: transactional memory for an operating system

ABSTRACT

This paper quantifies the effect of architectural design decisions onthe performance of TxLinux. TxLinux is a Linux kernel modifiedto use transactions in place of locking primitives in several key subsystems.We run TxLinux on MetaTM, which is a new hardwaretransaction memory (HTM) model.MetaTM contains features that enable efficient and correct interrupthandling for an x86-like architecture. Live stack overwrites can corrupt non-transactional stack memory and requires a smallchange to the transaction register checkpoint hardware to ensurecorrect operation of the operating system. We also propose stack based early release to reduce spurious conflicts on stack memorybetween kernel code and interrupt handlers.We use MetaTM to examine the performance sensitivity of individualarchitectural features. For TxLinux we find that Polka and SizeMatters are effective contention management policies, someform of backoff on transaction contention is vital for performance,and stalling on a transaction conflict reduces transaction restartrates, but does not improve performance. Transaction write setsare small, and performance is insensitive to transaction abort costsbut sensitive to commit costs.

REFERENCES

• 1: A. Alameldeen and D. Wood. Variability in architectural simulations of multi-threaded workloads, 2003.
• 2: 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]
• 3: A. Arcangeli, M. Cao, P. McKenney, and D. Sarma. Using read-copy-update techniques for system V IPC in the Linux 2.5 kernel. In USENIX Annual Technical Conference, FREENIX Track, pages 297--309, 2003.
• 4: C. Blundell, E.C. Lewis, and M. Martin. Deconstructing transactional semantics: The subtleties of atomicity. In Proceedings of the Fourth Workshop on Duplicating, Deconstructing, and Debunking, Jun 2005.
• 5: Jeff Bonwick, The slab allocator: an object-caching kernel memory allocator, Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, p.6-6, June 06-10, 1994, Boston, Massachusetts
• 6: 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
• 7: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 8: Weihaw Chuang , Satish Narayanasamy , Ganesh Venkatesh , Jack Sampson , Michael Van Biesbrouck , Gilles Pokam , Brad Calder , Osvaldo Colavin, Unbounded page-based 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
• 9: 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
• 10: J. Chung, H. Chafi, C. Cao Minh, A. McDonald, B. Carlstrom, C. Kozyrakis, and K. Olukotun. The common case transactional behavior of multithreaded programs. In HPCA-12. Feb 2006.
• 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: D. Dice, O. Shalev, and N. Shavit. Transactional locking ii. In Proc. of the 20th International Symposium on Distributed Computing (DISC), 2006.
• 13: 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
• 14: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 15: 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
• 16: 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
• 17: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 18: 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]
• 19: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 20: 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]
• 21: 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
• 22: Tom Knight, An architecture for mostly functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.105-112, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319854]
• 23: 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]
• 24: Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
• 25: 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
• 26: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based transactional memory. In HPCA, 2006.
• 27: 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
• 28: E. Moss and T. Hosking. Nested transactional memory: Model and preliminary architecture sketches. In SCOOL, 2005.
• 29: 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
• 30: 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
• 31: 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
• 32: H. Ramadan, C. Rossbach, and E. Witchel. The Linux kernel: A challenging workload for transactional memory. In Proceedings of the Workshop on Transactional Memory Workloads, June 2006.
• 33: 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]
• 34: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 35: T. Skare and C. Kozyrakis. Early release: Friend or foe? In Workshop on Transactional Memory Workloads, Jun 2006.
• 36: Sun Microsystems, Inc. The fortress Language specification,2006. http://research.sun.com/projects/plrg/fortress0903.pdf.
• 37: C. Zilles and L. Baugh. Extending hardware transactional memory to support non-busy waiting and non-transactional actions. In ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, Jun 2006.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.0 General

General Terms:
Design, Performance

Keywords:
MetaTM, OS support, TxLinux, transactional memory