research-article

Closed and open nested atomic actions for Java: language design and prototype implementation

Authors:

Antony L. Hosking,

J. Eliot B. Moss,

Tim RichardsAuthors Info & Claims

PPPJ '14: Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java platform: Virtual machines, Languages, and Tools

Pages 169 - 180

https://doi.org/10.1145/2647508.2647525

Published: 23 September 2014 Publication History

Abstract

We describe the design and prototype implementation of a dialect of Java, XJ, that supports both closed and open nested transactions. As we have previously advocated, open nesting most naturally attaches to the class as the primary abstraction mechanism of Java. The resulting design allows natural expression of layered abstractions for concurrent data structures, while promoting improved concurrency for operations on those abstractions. Moreover, we describe our approach to constructing a prototype implementation of XJ that runs on standard Java virtual machines, by grafting support for transactions onto both application code and library code via load-time bytecode rewriting, for full execution coverage. We rely on extensions to the javac compiler, a JVMTI run-time agent to intercept and rewrite Java classes as they are loaded into the virtual machine, and a run-time library that tracks and manages all transaction meta-data. The resulting prototype will allow further exploration of implementation alternatives for open and closed nested transactions in Java. Our design also addresses the issue of internal deadlock caused by accessing the same data in both closed and open nesting fashion by carefully disallowing such access.

References

[1]

Y. Afek, U. Drepper, P. Felber, C. Fetzer, V. Gramoli, M. Hohmuth, E. Riviere, P. Stenstrom, O. Unsal, W. Maldonadao Moreira, D. Harmanci, P. Marlier, S. Diestelhorst, M. Pohlack, A. Cristal, I. Hur, A. Dragojevic, R. Gerraoui, M. Kapalka, S. Tomic, G. Korland, N. Shavit, M. Nowack, and T. Riegel. The Velox transactional memory stack. IEEE Micro, 30(5):76--87, Sep./Oct. 2010.

Digital Library

[2]

Y. Afek, G. Korland, and A. Zilberstein. Lowering STM overhead with static analysis. In International Workshop on Languages and Compilers for Parallel Computing, volume 6548 of Lecture Notes in Computer Science, pages 31--45, Houston, Texas, Oct. 2010. Springer.

[3]

E. Bruneton. ASM 4.0: A Java bytecode engineering library, Sept. 2011. URL http://download.forge.objectweb.org/asm/asm4-guide.pdf. Version 2.0.

[4]

B. D. Carlstrom, A. McDonald, H. Chafi, J. Chung, C. C. Minh, C. Kozyrakis, and K. Olukotun. The Atomos transactional programming language. In ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 1--13, Ottawa, Canada, June 2006.

Digital Library

[5]

T. L. Harris and K. Fraser. Language support for lightweight transactions. In ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 388--402, Anaheim, California, 2003 2003.

Digital Library

[6]

M. Herlihy and E. Koskinen. Transactional boosting: A methodology for highly-concurrent transactional objects. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 207--216, Salt Lake City, Utah, Feb. 2008.

Digital Library

[7]

M. Herlihy and E. Koskinen. Composable transactional objects: A position paper. In European Symposium on Programming, volume 8410 of Lecture Notes in Computer Science, pages 1--7, Grenoble, France, Apr. 2014. Springer.

Digital Library

[8]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In 22nd Annual ACM Symposium on Principles of Distributed Computing, pages 84--91, Boston, Massachusetts, 2003.

Digital Library

[9]

M. Herlihy, V. Luchangco, and M. Moir. A flexible framework for implementing software transactional memory. In ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 253--262, Portland, Oregon, Oct. 2006.

Digital Library

[10]

M. P. Herlihy and J. M. Wing. Linearizability: A correctness criterion for concurrent objects. ACM Trans. Prog. Lang. Syst., 12(3): 463--492, July 1990.

Digital Library

[11]

B. Hindman and D. Grossman. Atomicity via source-to-source translation. In ACM SIGPLAN Workshop on Memory System Performance and Correctness, pages 82--91, San Jose, California, Oct. 2006.

Digital Library

[12]

G. Korland, N. Shavit, and P. Felber. Noninvasive concurrency with Java STM. In Workshop on Programmability Issues for Heterogeneous Multicores, Pisa, Italy, Jan. 2010.

[13]

P. McGachey, A. L. Hosking, and J. E. B. Moss. Class transformations for transparent distribution of Java applications. Journal of Object Technology, 10:9:1--35, Aug. 2011.

[14]

J. E. B. Moss. Nested transactions: an approach to reliable distributed computing. PhD thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1981.

Digital Library

[15]

J. E. B. Moss and A. L. Hosking. Nested transactional memory: model and architecture sketches. Science of Computer Programming, 63:186--201, Dec. 2006.

Digital Library

[16]

Multiverse. URL http://multiverse.codehaus.org.

[17]

Y. Ni, V. Menon, A.-R. Adl-Tabatabai, A. L. Hosking, R. L. Hudson, J. E. B. Moss, B. Saha, and T. Shpeisman. Open nesting in software transactional memory. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 68--78, San Jose, California, Mar. 2007.

Digital Library

[18]

C. H. Papadimitriou. The serializability of concurrent database updates. J. ACM, 26(4):631--653, Oct. 1979.

Digital Library

[19]

B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. C. Minh, and B. Hertzberg. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 187--197, New York, Mar. 2006.

Digital Library

[20]

ScalaSTM. URL http://nbronson.github.io/scala-stm.

[21]

Transactional Memory Specification Drafting Group. Original draft specification of transactional language constructs for C++. Technical report, Programming Language C++, EWG, SG5 Transactional Memory, Feb. 2012. Version 1.1.

Cited By

Painter ZCook VPeterson CDechev DMargara AValle E(2021)Descriptor based consensus for blockchain transactionsProceedings of the 15th ACM International Conference on Distributed and Event-based Systems10.1145/3465480.3466927(114-125)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1145/3465480.3466927
Peterson CWilson APirkelbauer PDechev D(2020)Optimized Transactional Data Structure Approach to Concurrency Control for In-Memory Databases2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)10.1109/SBAC-PAD49847.2020.00025(107-115)Online publication date: Sep-2020
https://doi.org/10.1109/SBAC-PAD49847.2020.00025
Chapman KHosking AMoss J(2016)Hybrid STM/HTM for nested transactions on OpenJDKACM SIGPLAN Notices10.1145/3022671.298402951:10(660-676)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984029
Show More Cited By

Index Terms

Closed and open nested atomic actions for Java: language design and prototype implementation
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures

Recommendations

Open nesting in software transactional memory
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

Transactional memory (TM) promises to simplify concurrent programming while providing scalability competitive to fine-grained locking. Language-based constructs allow programmers to denote atomic regions declaratively and to rely on the underlying ...
Nested transactional memory: model and architecture sketches
Special issue: Synchronization and concurrency in object-oriented languages

We offer a reference model for nested transactions at the level of memory accesses, and sketch possible hardware architecture designs that implement that model. We describe both closed and open nesting. The model is abstract in that it does not relate ...
On open nesting in distributed transactional memory
SYSTOR '12: Proceedings of the 5th Annual International Systems and Storage Conference

Distributed Transactional Memory (DTM) is a recent but promising model for programming distributed systems. It aims to present programmers with a simple to use distributed concurrency control abstraction (transactions), while maintaining performance and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPPJ '14: Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java platform: Virtual machines, Languages, and Tools

September 2014

214 pages

ISBN:9781450329262

DOI:10.1145/2647508

General Chair:
Joanna Kolodziej
Cracow University of Technology, Poland
,
Program Chair:
Bruce Childers
University of Pittsburgh

Copyright © 2014 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

SIGAPP: ACM Special Interest Group on Applied Computing
SIGPLAN: ACM Special Interest Group on Programming Languages
Sabre: Sabre
PK: Cracow University of Technology

In-Cooperation

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 September 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computer and Network Systems

Conference

PPPJ '14

Sponsor:

SIGAPP
SIGPLAN
Sabre
PK

PPPJ '14: 2014 INTERNATIONAL CONFERENCE ON PRINCIPLES AND PRACTICES OF PROGRAMMING ON THE JAVA PLATFORM VIRTUAL MACHINES, LANGUAGES AND TOOLS

September 23 - 26, 2014

Cracow, Poland

Acceptance Rates

Overall Acceptance Rate 29 of 58 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
111
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Painter ZCook VPeterson CDechev DMargara AValle E(2021)Descriptor based consensus for blockchain transactionsProceedings of the 15th ACM International Conference on Distributed and Event-based Systems10.1145/3465480.3466927(114-125)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1145/3465480.3466927
Peterson CWilson APirkelbauer PDechev D(2020)Optimized Transactional Data Structure Approach to Concurrency Control for In-Memory Databases2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)10.1109/SBAC-PAD49847.2020.00025(107-115)Online publication date: Sep-2020
https://doi.org/10.1109/SBAC-PAD49847.2020.00025
Chapman KHosking AMoss J(2016)Hybrid STM/HTM for nested transactions on OpenJDKACM SIGPLAN Notices10.1145/3022671.298402951:10(660-676)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984029
Chapman KHosking AMoss JHosking ASrisa-an W(2016)Extending OpenJDK to support hybrid STM/HTM: preliminary designProceedings of the 8th International Workshop on Virtual Machines and Intermediate Languages10.1145/2998415.2998417(1-5)Online publication date: 31-Oct-2016
https://dl.acm.org/doi/10.1145/2998415.2998417
Chapman KHosking AMoss JVisser ESmaragdakis Y(2016)Hybrid STM/HTM for nested transactions on OpenJDKProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984029(660-676)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2983990.2984029

View Options

Get Access

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