More Web Proxy on the site http://driver.im/

Article

Implementation and Use of Transactional Memory with Dynamic Separation

Authors:

Andrew Birrell,

Michael IsardAuthors Info & Claims

CC '09: Proceedings of the 18th International Conference on Compiler Construction: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009

Pages 63 - 77

https://doi.org/10.1007/978-3-642-00722-4_6

Published: 27 March 2009 Publication History

Abstract

We introduce the design and implementation of dynamic separation (DS) as a programming discipline for using transactional memory. Our approach is based on the programmer indicating which objects can be updated in transactions, which can be updated outside transactions, and which are read-only. We introduce explicit operations that identify transitions between these modes of access. We show how to guarantee strong semantics for programs that use these DS operations correctly, even over an STM implementation that provides only weak atomicity. We describe a run-time checking tool (analogous to a data-race detector) that can test whether or not a program is using DS operations correctly. We also examine the use of DS in an asynchronous IO library.

References

[1]

Herlihy, M., Moss, J.E.B.: Transactional memory: Architectural support for lock-free data structures. In: ISCA 1993, 20th International Symposium on Computer Architecture, pp. 289-301 (May 1993).

[2]

Harris, T., Marlow, S., Peyton Jones, S., Herlihy, M.: Composable memory transactions. In: PPoPP 2005, 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 48-60 (June 2005).

[3]

Isard, M., Birrell, A.: Automatic mutual exclusion. In: HotOS 2007, 11th Workshop on Hot Topics in Operating Systems (May 2007).

[4]

Smaragdakis, Y., Kay, A., Behrends, R., Young, M.: Transactions with isolation and cooperation. In: OOPSLA 2007, 22nd ACM SIGPLAN Conference on Object Oriented Programming Systems and Applications (October 2007).

[5]

Spear, M.F., Marathe, V.J., Dalessandro, L., Scott, M.L.: Privatization techniques for software transactional memory. Technical Report 915, CS Dept, U. Rochester (February 2007).

[6]

Abadi, M., Birrell, A., Harris, T., Isard, M.: Semantics of transactional memory and automatic mutual exclusion. In: POPL 2008, 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 63-74 (2008).

[7]

Moore, K.F., Grossman, D.: High-level small-step operational semantics for transactions. In: POPL 2008, 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 51-62 (January 2008).

[8]

Menon, V., Balensiefer, S., Shpeisman, T., Adl-Tabatabai, A.R., Hudson, R.L., Saha, B., Welc, A.: Practical weak-atomicity semantics for Java STM. In: SPAA 2008, 20th Symposium on Parallelism in Algorithms and Architectures, pp. 314- 325 (June 2008).

[9]

Blundell, C., Lewis, E.C., Martin, M.M.K.: Deconstructing transactional semantics: The subtleties of atomicity. In: WDDD 2005, 4th Workshop on Duplicating, Deconstructing and Debunking, pp. 48-55 (June 2005).

[10]

Dice, D., Shavit, N.: What really makes transactions faster? In: TRANSACT 2006, 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (June 2006).

[11]

Dice, D., Shalev, O., Shavit, N.: Transactional locking II. In: DISC 2006, 20th International Symposium on Distributed Computing, pp. 194-208 (September 2006).

[12]

Wang, C., Chen, W.Y., Wu, Y., Saha, B., Adl-Tabatabai, A.R.: Code generation and optimization for transactional memory constructs in an unmanaged language. In: CGO 2007, International Symposium on Code Generation and Optimization, pp. 34-48 (March 2007).

[13]

Shavit, N., Touitou, D.: Software transactional memory. In: Proc. 14th Annual ACM Symposium on Principles of Distributed Computing, pp. 204-213 (August 1995).

[14]

Shpeisman, T., Menon, V., Adl-Tabatabai, A.R., Balensiefer, S., Grossman, D., Hudson, R.L., Moore, K.F., Saha, B.: Enforcing isolation and ordering in STM. In: PLDI 2007, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 78-88 (June 2007).

[15]

Schneider, F.T., Menon, V., Shpeisman, T., Adl-Tabatabai, A.R.: Dynamic optimization for efficient strong atomicity. In: OOPSLA 2008, 23rd ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, pp. 181-194 (October 2008).

[16]

Abadi, M., Harris, T., Mehrara, M.: Transactional memory with strong atomicity using off-the-shelf memory protection hardware. In: PPoPP 2009, 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (February 2009).

[17]

Abadi, M., Harris, T., Moore, K.F.: A model of dynamic separation for transactional memory. In: CONCUR 2008, 19th International Conference on Concurrency Theory, pp. 6-20 (August 2008).

[18]

Abadi, M., Birrell, A., Harris, T., Hsieh, J., Isard, M.: Dynamic separation for transactional memory. Technical Report MSR-TR-2008-43 (March 2008).

[19]

Harris, T., Plesko, M., Shinnar, A., Tarditi, D.: Optimizing memory transactions. In: PLDI 2006, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 14-25 (June 2006).

[20]

Saraswat, V.A., Jagadeesan, R., Michael, M., von Praun, C.: A theory of memory models. In: PPoPP 2007, 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 161-172 (March 2007).

[21]

Saha, B., Adl-Tabatabai, A.R., Hudson, R.L., Minh, C.C., Hertzberg, B.: McRTSTM: a high performance software transactional memory system for a multicore runtime. In: PPoPP 2006, 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 187-197 (March 2006).

[22]

Adve, S.V., Hill, M.D.: Weak ordering - a new definition. ACM SIGARCH Comput. Archit. News 18(3a), 2-14 (1990).

[23]

Hill, M.D.: Multiprocessors should support simple memory-consistency models. Computer 31(8), 28-34 (1998).

[24]

Lev, Y., Maessen, J.W.: Towards a safer interaction with transactional memory by tracking object visibility. In: SCOOL 2005, Workshop on Synchronization and Concurrency in Object-Oriented Languages (October 2005).

Cited By

Khyzha AAttiya HGotsman ARinetzky N(2018)Safe privatization in transactional memoryACM SIGPLAN Notices10.1145/3200691.317850553:1(233-245)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178505
Khyzha AAttiya HGotsman ARinetzky NKrall AGross T(2018)Safe privatization in transactional memoryProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178505(233-245)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178505
Abadi MBirrell AHarris TIsard M(2011)Semantics of transactional memory and automatic mutual exclusionACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/1889997.188999933:1(1-50)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.1145/1889997.1889999
Show More Cited By

Recommendations

An efficient lock-aware transactional memory implementation
ICOOOLPS '09: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems

Transactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the ...
Safe privatization in transactional memory
PPoPP '18

Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...
Safe privatization in transactional memory
PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CC '09: Proceedings of the 18th International Conference on Compiler Construction: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009

March 2009

280 pages

ISBN:9783642007217

Editors:
Oege Moor
Computing Laboratory, Oxford University, Oxford, UK OX1 3QD
,
Michael I. Schwartzbach
Department of Computer Science, Aarhus University, Aarhus N., Denmark 8200

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khyzha AAttiya HGotsman ARinetzky N(2018)Safe privatization in transactional memoryACM SIGPLAN Notices10.1145/3200691.317850553:1(233-245)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178505
Khyzha AAttiya HGotsman ARinetzky NKrall AGross T(2018)Safe privatization in transactional memoryProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178505(233-245)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178505
Abadi MBirrell AHarris TIsard M(2011)Semantics of transactional memory and automatic mutual exclusionACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/1889997.188999933:1(1-50)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.1145/1889997.1889999
Attiya HHillel E(2010)The cost of privatizationProceedings of the 24th international conference on Distributed computing10.5555/1888781.1888789(35-49)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1888781.1888789

View Options

View options

Media

Figures

Other

Tables

View Table of Contents