Abstract
Mutual exclusion (mutex) locks limit concurrency but offer low single-thread latency. Software transactional memory (STM) typically has much higher latency, but scales well. We present transactional mutex locks (TML), which attempt to achieve the best of both worlds for read-dominated workloads. We also propose compiler optimizations that reduce the latency of TML to within a small fraction of mutex overheads.
Our evaluation of TML, using microbenchmarks on the x86 and SPARC architectures, is promising. Using optimized spinlocks and the TL2 STM algorithm as baselines, we find that TML provides the low latency of locks at low thread levels, and the scalability of STM for read-dominated workloads. These results suggest that TML is a good reference implementation to use when evaluating STM algorithms, and that TML is a viable alternative to mutex locks for a variety of workloads.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
McKenney, P.E.: Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels. PhD thesis, OGI School of Science and Engineering at Oregon Health and Sciences University (2004)
Lameter, C.: Effective Synchronization on Linux/NUMA Systems. In: Proc. of the May 2005 Gelato Federation Meeting, San Jose, CA (2005)
Shavit, N., Touitou, D.: Software Transactional Memory. In: Proc. of the 14th ACM Symp. on Principles of Distributed Computing, Ottawa, ON, Canada (1995)
Cascaval, C., Blundell, C., Michael, M., Cain, H.W., Wu, P., Chiras, S., Chatterjee, S.: Software Transactional Memory: Why Is It Only a Research Toy? Queue 6(5), 46–58 (2008)
Dalessandro, L., Spear, M.F., Scott, M.L.: NOrec: Streamlining STM by Abolishing Ownership Records. In: Proc. of the 15th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, Bangalore, India (2010)
Harris, T., Plesko, M., Shinar, A., Tarditi, D.: Optimizing Memory Transactions. In: Proc. of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, Ottawa, ON, Canada (2006)
Hudson, R.L., Saha, B., Adl-Tabatabai, A.R., Hertzberg, B.: A Scalable Transactional Memory Allocator. In: Proc. of the 2006 International Symp. on Memory Management, Ottawa, ON, Canada (2006)
Dice, D., Shalev, O., Shavit, N.: Transactional Locking II. In: Proc. of the 20th International Symp. on Distributed Computing, Stockholm, Sweden (2006)
Felber, P., Fetzer, C., Riegel, T.: Dynamic Performance Tuning of Word-Based Software Transactional Memory. In: Proc. of the 13th ACM SIGPLAN 2008 Symp. on Principles and Practice of Parallel Programming, Salt Lake City, UT (2008)
Spear, M.F., Silverman, M., Dalessandro, L., Michael, M.M., Scott, M.L.: Implementing and Exploiting Inevitability in Software Transactional Memory. In: Proc. of the 37th International Conference on Parallel Processing, Portland, OR (2008)
Welc, A., Saha, B., Adl-Tabatabai, A.R.: Irrevocable Transactions and their Applications. In: Proc. of the 20th ACM Symp. on Parallelism in Algorithms and Architectures, Munich, Germany (2008)
Menon, V., Balensiefer, S., Shpeisman, T., Adl-Tabatabai, A.R., Hudson, R., Saha, B., Welc, A.: Practical Weak-Atomicity Semantics for Java STM. In: Proc. of the 20th ACM Symp. on Parallelism in Algorithms and Architectures, Munich, Germany (2008)
Spear, M.F., Dalessandro, L., Marathe, V.J., Scott, M.L.: Ordering-Based Semantics for Software Transactional Memory. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 275–294. Springer, Heidelberg (2008)
Marathe, V.J., Spear, M.F., Scott, M.L.: Scalable Techniques for Transparent Privatization in Software Transactional Memory. In: Proc. of the 37th International Conference on Parallel Processing, Portland, OR (2008)
Harris, T., Marlow, S., Peyton Jones, S., Herlihy, M.: Composable Memory Transactions. In: Proc. of the 10th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, Chicago, IL (2005)
Brinch Hansen, P.: Operating System Principles. Prentice-Hall, Englewood Cliffs (1973)
Dragojevic, A., Ni, Y., Adl-Tabatabai, A.R.: Optimizing Transactions for Captured Memory. In: Proc. of the 21st ACM Symp. on Parallelism in Algorithms and Architectures, Calgary, AB, Canada (2009)
Spear, M.F., Michael, M.M., von Praun, C.: RingSTM: Scalable Transactions with a Single Atomic Instruction. In: Proc. of the 20th ACM Symp. on Parallelism in Algorithms and Architectures, Munich, Germany (2008)
Adl-Tabatabai, A.R., Lewis, B.T., Menon, V., Murphy, B.R., Saha, B., Shpeisman, T.: Compiler and Runtime Support for Efficient Software Transactional Memory. In: Proc. of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, Ottawa, ON, Canada (2006)
Spear, M.F., Michael, M.M., Scott, M.L., Wu, P.: Reducing Memory Ordering Overheads in Software Transactional Memory. In: Proc. of the 2009 International Symp. on Code Generation and Optimization, Seattle, WA (2009)
Rochester Synchronization Group, Department of Computer Science, University of Rochester: Rochester STM (2006–2009), http://www.cs.rochester.edu/synchronization/rstm/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dalessandro, L., Dice, D., Scott, M., Shavit, N., Spear, M. (2010). Transactional Mutex Locks. In: D’Ambra, P., Guarracino, M., Talia, D. (eds) Euro-Par 2010 - Parallel Processing. Euro-Par 2010. Lecture Notes in Computer Science, vol 6272. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15291-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-15291-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15290-0
Online ISBN: 978-3-642-15291-7
eBook Packages: Computer ScienceComputer Science (R0)