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

Article

Atomicity via source-to-source translation

Authors:

Benjamin Hindman,

Dan GrossmanAuthors Info & Claims

MSPC '06: Proceedings of the 2006 workshop on Memory system performance and correctness

Pages 82 - 91

https://doi.org/10.1145/1178597.1178611

Published: 22 October 2006 Publication History

Abstract

We present an implementation and evaluation of atomicity (also known as software transactions) for a dialect of Java. Our implementation is fundamentally different from prior work in three respects: (1) It is entirely a source-to-source translation, producing Java source code that can be compiled by any Java compiler and run on any Java Virtual Machine. (2) It can enforce "strong" atomicity without assuming special hardware or a uniprocessor. (3) The implementation uses locks rather than optimistic concurrency, but it cannot deadlock and requires inter-thread communication only when there is data contention.

References

[1]

M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for Java. ACM Transactions on Programming Languages and Systems, 28(2), 2006.]]

Digital Library

[2]

A.-R. Adl-Tabatabai, B. Lewis, V. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and runtime support for efficient software transactional memory. In ACM Conference on Programming Language Design and Implementation, June 2006.]]

Digital Library

[3]

C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded transactional memory. In 11th International Symposium on High-Performance Computer Architecture, Feb. 2005.]]

Digital Library

[4]

C. Blundell, E. C. Lewis, and M. M. K. Martin. Deconstructing transactions: The subtleties of atomicity. In 4th Workshop on Duplicating, Deconstructing, and Debunking, June 2005.]]

[5]

C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Nov. 2002.]]

Digital Library

[6]

B. D. Carlstrom, J. Chung, A. McDonald, H. Chafi, C. Kozyrakis, and K. Olukotun. The Atomos transactional programming language. In ACM Conference on Programming Language Design and Implementation, June 2006.]]

Digital Library

[7]

R. Ennals. Software transactional memory should not be obstruction-free, 2005. http://www.cambridge.intel-research.net/ren-nais/notlockfree.pdf.]]

[8]

C. Flanagan, S. N. Freund, and M. Lifshin. Type inference for atomicity. In 2005 ACM International Workshop on Types in Language Design and Implementation, Jan. 2005.]]

Digital Library

[9]

D. Grossman. Software transactions are to concurrency as garbage collection is to memory management. Technical Report 2006-04-01, Univ. of Washington Dept. of Comp. Sci. & Engr., Feb. 2006.]]

[10]

R. Guerraoui, M. Herlihy, and S. Pochon. Polymorphic contention management. In 19th International Symposium on Distributed Computing, Sept. 2005.]]

Digital Library

[11]

L. Hammond, B. D. Carlstrom, V. Wong, B. Hertzberg, M. Chen, C. Kozyrakis, and K. Olukotun. Programming with transactional coherence and consistency (tcc). In International Conference on Architectural Support for Programming Languages and Operating Systems, 2004.]]

Digital Library

[12]

T. Harris. Exceptions and side-effects in atomic blocks. In PODC Workshop on Concurrency and Synchronization in Java Programs, July 2004.]]

[13]

T. Harris and K. Fraser. Language support for lightweight transactions. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Oct. 2003.]]

Digital Library

[14]

T. Harris, S. Marlow, S. P. Jones, and M. Herlihy. Composable memory transactions. In ACM Symposium on Principles and Practice of Parallel Programming, 2005.]]

Digital Library

[15]

T. Harris, S. Marlow, and S. Peyton Jones. Haskell on a shared-memory multiprocessor. In Proceedings of the 2005 ACM SIGPLAN Workshop on Haskell, Sept. 2005.]]

Digital Library

[16]

T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. In ACM Conference on Programming Language Design and Implementation, June 2006.]]

Digital Library

[17]

M. Herlihy, V. Luchangco, M. Moir, and W. Scherer. Software transactional memory for dynamic-sized data structures. In 22nd ACM Symposium on Principles of Distributed Computing, July 2003.]]

Digital Library

[18]

B. Hindman and D. Grossman. Strong atomicity for Java without virtual-machine support. Technical Report 2006-05-01, Univ. of Washington Dept. of Computer Science & Engineering, May 2006.]]

[19]

J. Manson, J. Baker, A. Cunei, S. Jagannathan, M. Prochazka, B. Xin, and J. Vitek. Preemptible atomic regions for real-time Java. In 26th IEEE Real-Time Systems Symposium, Dec. 2005.]]

Digital Library

[20]

J. Manson, W. Pugh, and S. V. Adve. The Java memory model. In 32nd ACM Symposium on Principles of Programming Languages, Jan. 2005.]]

Digital Library

[21]

V. J. Marathe, W. N. S. III, and M. L. Scott. Adaptive software transactional memory. In 19th International Symposium on Distributed Computing, Sept. 2005.]]

Digital Library

[22]

V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. S. III, and M. L. Scott. Lowering the overhead of nonblocking software transactional memory. Technical Report TR 893, Computer Science Department, University of Rochester, Mar. 2006.]]

[23]

B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In 33rd ACM Symposium on Principles of Programming Languages, 2006.]]

Digital Library

[24]

A. McDonald, J. Chung, B. D. Carlstrom, C. C. Minh, H. Chafi, C. Kozyrakis, and K. Olukotun. Architectural semantics for practical transactional memory. In 33rd International Symposium on Computer Architecture, June 2006.]]

Digital Library

[25]

N. Nystrom, M. R. Clarkson, and A. C. Myers. Polyglot: An extensible compiler framework for Java. In 12th International Conference on Compiler Construction, volume 2622 of Lecture Notes in Computer Science, Apr. 2003.]]

Digital Library

[26]

R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. In 32nd International Symposium on Computer Architecture, 2005.]]

Digital Library

[27]

M. F. Ringenburg and D. Grossman. AtomCaml: First-class atomicity via rollback. In 10th ACM International Conference on Functional Programming, Sept. 2005.]]

Digital Library

[28]

N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, Special Issue(10), 1997.]]

Digital Library

[29]

TRANSACT: 1st ACM SIGPLAN workshop on languages, compilers, and hardware support for transactional computing, June 2006. http://www.cs.purdue.edu/homes/jv/events/TRANSACT/.]]

[30]

W. Visser, K. Havelund, G. Brat, S. Park, and F. Lerda. Model checking programs. Automated Software Engineering Journal, 10(2), Apr. 2003.]]

Digital Library

[31]

C. von Praun and T. R. Gross. Static conflict analysis for multithreaded object-oriented programs. In ACM Conference on Programming Language Design and Implementation, 2003.]]

Digital Library

[32]

A. Welc, S. Jagannathan, and A. L. Hosking. Transactional monitors for concurrent objects. In European Conference on Object-Oriented Programming, 2004.]]

Cited By

Faes MGross TKell SMarr S(2018)Efficient VM-independent runtime checks for parallel programmingProceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281293(5-15)Online publication date: 4-Nov-2018
https://dl.acm.org/doi/10.1145/3281287.3281293
de Putter SWijs AZhang D(2018)The SLCO Framework for Verified, Model-Driven Construction of Component SoftwareFormal Aspects of Component Software10.1007/978-3-030-02146-7_15(288-296)Online publication date: 5-Oct-2018
https://doi.org/10.1007/978-3-030-02146-7_15
Zhang MBiswas SBond MZaks AHermenegildo M(2016)Relaxed dependence tracking for parallel runtime supportProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892229(45-55)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892229
Show More Cited By

Index Terms

Atomicity via source-to-source translation
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Accurate and efficient runtime detection of atomicity errors in concurrent programs
PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming

Atomicity is an important correctness condition for concurrent systems. Informally, atomicity is the property that every concurrent execution of a set of transactions is equivalent to some serial execution of the same transactions. In multi-threaded ...
Practical weak-atomicity semantics for java stm
SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

As memory transactions have been proposed as a language-level replacement for locks, there is growing need for well-defined semantics. In contrast to database transactions, transaction memory (TM) semantics are complicated by the fact that programs may ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MSPC '06: Proceedings of the 2006 workshop on Memory system performance and correctness

October 2006

114 pages

ISBN:1595935789

DOI:10.1145/1178597

General Chair:
Antony Hosking
Purdue U
,
Program Chair:
Ali-Reza Adl-Tabatabai
Intel

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MSPC '06

Sponsor:

SIGPLAN

MSPC '06: ACM SIGPLAN Workshop on Memory Systems Performance and Correctness 2006

October 22, 2006

California, San Jose

Acceptance Rates

Overall Acceptance Rate 6 of 20 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
398
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Faes MGross TKell SMarr S(2018)Efficient VM-independent runtime checks for parallel programmingProceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281293(5-15)Online publication date: 4-Nov-2018
https://dl.acm.org/doi/10.1145/3281287.3281293
de Putter SWijs AZhang D(2018)The SLCO Framework for Verified, Model-Driven Construction of Component SoftwareFormal Aspects of Component Software10.1007/978-3-030-02146-7_15(288-296)Online publication date: 5-Oct-2018
https://doi.org/10.1007/978-3-030-02146-7_15
Zhang MBiswas SBond MZaks AHermenegildo M(2016)Relaxed dependence tracking for parallel runtime supportProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892229(45-55)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892229
Zhang MHuang JCao MBond M(2015)Low-overhead software transactional memory with progress guarantees and strong semanticsACM SIGPLAN Notices10.1145/2858788.268851050:8(97-108)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688510
Matveev AShavit NFelber PMarlier PMiller EHand S(2015)Read-log-updateProceedings of the 25th Symposium on Operating Systems Principles10.1145/2815400.2815406(168-183)Online publication date: 4-Oct-2015
https://dl.acm.org/doi/10.1145/2815400.2815406
Zhang MHuang JCao MBond MCohen AGrove D(2015)Low-overhead software transactional memory with progress guarantees and strong semanticsProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688510(97-108)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688510
Cristal AOzkan BCohen EKestor GKuru IUnsal OTasiran SMutluergil SElmas T(2015)Verification Tools for Transactional ProgramsTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_14(283-306)Online publication date: 2015
https://doi.org/10.1007/978-3-319-14720-8_14
Chapman KHosking AMoss JRichards TKolodziej JChilders B(2014)Closed and open nested atomic actions for JavaProceedings of the 2014 International Conference on Principles and Practices of Programming on the Java platform: Virtual machines, Languages, and Tools10.1145/2647508.2647525(169-180)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1145/2647508.2647525
Stork SNaden KSunshine JMohr MFonseca AMarques PAldrich J(2014)ÆminiumACM Transactions on Programming Languages and Systems10.1145/254392036:1(1-42)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1145/2543920
Bond MKulkarni MCao MZhang MFathi Salmi MBiswas SSengupta AHuang J(2013)OCTETACM SIGPLAN Notices10.1145/2544173.250951948:10(693-712)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509519
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents