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

Article

Design tradeoffs in modern software transactional memory systems

Authors:

Virendra J. Marathe,

William N. Scherer,

Michael L. ScottAuthors Info & Claims

LCR '04: Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems

Pages 1 - 7

https://doi.org/10.1145/1066650.1066660

Published: 22 October 2004 Publication History

Abstract

Software Transactional Memory (STM) is a generic non-blocking synchronization construct that enables automatic conversion of correct sequential objects into correct concurrent objects. Because it is nonblocking, STM avoids traditional performance and correctness problems due to thread failure, preemption, page faults, and priority inversion.In this paper we compare and analyze two recent object-based STM systems, the DSTM of Herlihy et al. and the FSTM of Fraser, both of which support dynamic transactions, in which the set of objects to be modified is not known in advance. We highlight aspects of these systems that lead to performance tradeoffs for various concurrent data structures. More specifically, we consider object ownership acquisition semantics, concurrent object referencing style, the overhead of ordering and bookkeeping, contention management versus helping semantics, and transaction validation. We demonstrate for each system simple benchmarks on which it outperforms the other by a significant margin. This in turn provides us with a preliminary characterization of the applications for which each system is best suited.

References

[1]

J. H. Anderson and M. Moir. Universal Constructions for Large Objects. In Proceedings of the 9th International Workshop on Distributed Algorithms, pages 168--182. Springer-Verlag, 1995.

Digital Library

[2]

J. H. Anderson and M. Moir. Universal Constructions for Multi-Object Operations. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pages 184--193, 1995.

Digital Library

[3]

G. Barnes. A Method for Implementing Lock-Free Shared Data Structures. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 261--270, 1993.

Digital Library

[4]

C. Cole and M. P. Herlihy. Snapshots and Software Transactional Memory. In Proceedings of Workshop on Concurrency and Synchronization in Java Programs, 2004.

[5]

K. Fraser. Practical Lock-Freedom. Technical Report UCAM-CL-TR-579, Cambridge University Computer Laboratory, February 2004.

[6]

K. Fraser and T. Harris. Concurrent Programming without Locks. Submitted for publication.

[7]

T. Harris and K. Fraser. Language Support for Lightweight Transactions. In Proceedings of 18th Annual ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 388--402, 2003.

Digital Library

[8]

M. P. Herlihy, V. Luchangco, and M. Moir. Obstruction Free Synchronization: Double-Ended Queues as an Example. In Proceedings of 23rd International Conference on Distributed Computing Systems, pages 522--529, May 2003.

Digital Library

[9]

M. P. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software Transactional Memory for Dynamic-sized Data Structures. In Proceedings of 22nd Annual ACM Symposium on Principles of Distributed Computing, July 2003.

Digital Library

[10]

M. P. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 289--300, May 1993.

Digital Library

[11]

M. P. Herlihy and J. M. Wing. Linearizability: a Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990.

Digital Library

[12]

A. Israeli and L. Rappoport. Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pages 151--160, 1994.

Digital Library

[13]

D. Lea. Concurrency JSR-166 Interest Site. http://gee.cs.oswego.edu/dl/concurrency-interest/.

[14]

V. J. Marathe and M. L. Scott. A Qualitative Survey of Modern Software Transactional Memory Systems. Technical Report TR 839, Department of Computer Science, University of Rochester, June 2004.

[15]

W. N. Scherer III and M. L. Scott. Contention Management in Dynamic Software Transactional Memory. In Proceedings of Workshop on Concurrency and Synchronization in Java Programs, pages 70--79, 2004.

[16]

N. Shavit and D. Touitou. Software Transactional Memory. In Proceedings of 14th Annual ACM Symposium on Principles of Distributed Computing, pages 204--213, 1995.

Digital Library

[17]

J. M. Stone, H. S. Stone, P. Heidelberger, and J. Turek. Multiple Reservations and the Oklahoma Update. IEEE Parallel and Distributed Technology, 1(4):58--71, November 1993.

Digital Library

[18]

J. Turek, D. Shasha, and S. Prakash. Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking. In Proceedings of the 11th ACM Symposium on Principles of Database Systems, pages 212--222, 1992.

Digital Library

Cited By

Tanabe THoshino TKawashima HTatebe O(2020)An analysis of concurrency control protocols for in-memory databases with CCBenchProceedings of the VLDB Endowment10.14778/3424573.342457513:13(3531-3544)Online publication date: 27-Oct-2020
https://dl.acm.org/doi/10.14778/3424573.3424575
Zhang DLaborde PLebanoff LDechev D(2018)Lock-Free Transactional Transformation for Linked Data StructuresACM Transactions on Parallel Computing10.1145/32096905:1(1-37)Online publication date: 13-Jun-2018
https://dl.acm.org/doi/10.1145/3209690
Fatourou P(2017)Concurrency for the Masses: The Paradigm of Software Transactional Memory2017 19th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2017.00012(17-22)Online publication date: Sep-2017
https://doi.org/10.1109/SYNASC.2017.00012
Show More Cited By

Recommendations

Time-Based Software Transactional Memory

Software transactional memory (STM) is a concurrency control mechanism that is widely considered to be easier to use by programmers than other mechanisms such as locking. The first generations of STMs have either relied on visible read designs, which ...
Tradeoffs in transactional memory virtualization
Proceedings of the 2006 ASPLOS Conference

For transactional memory (TM) to achieve widespread acceptance, transactions should not be limited to the physical resources of any specific hardware implementation. TM systems should guarantee correct execution even when transactions exceed scheduling ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

LCR '04: Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems

October 2004

134 pages

ISBN:9781450377997

DOI:10.1145/1066650

General Chair:
Alan Cox
Rice University
,
Program Chair:
Jaspal Subhlok
University of Houston

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

The Texas Learning & Computation Center
University of Houston

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

LCR04

Sponsor:

LCR04: 7th Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers

October 22 - 23, 2004

Texas, Houston, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
526
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tanabe THoshino TKawashima HTatebe O(2020)An analysis of concurrency control protocols for in-memory databases with CCBenchProceedings of the VLDB Endowment10.14778/3424573.342457513:13(3531-3544)Online publication date: 27-Oct-2020
https://dl.acm.org/doi/10.14778/3424573.3424575
Zhang DLaborde PLebanoff LDechev D(2018)Lock-Free Transactional Transformation for Linked Data StructuresACM Transactions on Parallel Computing10.1145/32096905:1(1-37)Online publication date: 13-Jun-2018
https://dl.acm.org/doi/10.1145/3209690
Fatourou P(2017)Concurrency for the Masses: The Paradigm of Software Transactional Memory2017 19th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2017.00012(17-22)Online publication date: Sep-2017
https://doi.org/10.1109/SYNASC.2017.00012
Ghosh AChaki RChaki N(2017)Abort-Free STM: A Non-blocking Concurrency Control Approach Using Software Transactional MemoryAdvanced Computing and Systems for Security10.1007/978-981-10-3409-1_4(53-71)Online publication date: 10-Mar-2017
https://doi.org/10.1007/978-981-10-3409-1_4
Zhang DDechev DScheideler CGilbert S(2016)Lock-free Transactions without Rollbacks for Linked Data StructuresProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935780(325-336)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935780
Leiserson C(2016)A simple deterministic algorithm for guaranteeing the forward progress of transactionsInformation Systems10.1016/j.is.2015.10.01357:C(69-74)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1016/j.is.2015.10.013
Ghosh AChaki RChaki N(2015)A new concurrency control mechanism for multi-threaded environment using transactional memoryThe Journal of Supercomputing10.1007/s11227-015-1507-871:11(4095-4115)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s11227-015-1507-8
Fatourou PIaremko MKanellou EKosmas E(2015)Algorithmic Techniques in STM DesignTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_5(101-126)Online publication date: 2015
https://doi.org/10.1007/978-3-319-14720-8_5
Attiya HFatourou P(2015)Disjoint-Access Parallelism in Software Transactional MemoryTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_4(72-97)Online publication date: 2015
https://doi.org/10.1007/978-3-319-14720-8_4
Saha AChatterjee APal NGhosh AChaki N(2014)A Lightweight Implementation of Obstruction-Free Software Transactional MemoryApplied Computation and Security Systems10.1007/978-81-322-1988-0_5(67-84)Online publication date: 27-Aug-2014
https://doi.org/10.1007/978-81-322-1988-0_5
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