skip to main content
10.1145/1178597.1178610acmconferencesArticle/Chapter ViewAbstractPublication PagesmspConference Proceedingsconference-collections
Article

Memory models for open-nested transactions

Published: 22 October 2006 Publication History

Abstract

Open nesting provides a loophole in the strict model of atomic transactions. Moss and Hosking suggested adapting open nesting for transactional memory, and Moss and a group at Stanford have proposed hardware schemes to support open nesting. Since these researchers have described their schemes using only operational definitions, however, the semantics of these systems have not been specified in an implementation-independent way. This paper offers a framework for defining and exploring the memory semantics of open nesting in a transactionl-memory setting.Our framework allows us to define the traditional model of serializability and two new transactional-memory models, race freedom and prefix race freedom. The weakest of these memory models, prefix race freedom, closely resembles the Stanford openesting model. We prove that these three memory models are equivalent for transactional-memory systems that support only closed nesting, as long as aborted transactions are "ignored." We prove that for systems that support open nesting, however, the models of serializability, race freedom, and prefix race freedom are distinct. We show that the Stanford TM system implements a model at least as strong as prefix race freedom and strictly weaker than race freedom. Thus, their model compromises serializability, the property traditionally used to reason about the correctness of transactions.

References

[1]
C. Beeri, P. A. Bernstein, and N. Goodman. A model for concurrency in nested transactions systems. Journal of the ACM, 36(2):230--269, 1989.
[2]
C. Blundell, E. C. Lewis, and M. M. K. Martin. Deconstructing transactions: The subtleties of atomicity. In Fourth Annual Workshop on Duplicating, Deconstructing, and Debunking, Jun 2005.
[3]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill, second edition, 2001.
[4]
C. Davies. Recovery semantics for a DB/DC system. In ACM National Conference, pages 136--141, 1973.
[5]
M. Feng and C. E. Leiserson. Efficient detection of determinacy races in Cilk programs. In SPAA, pages 1--11, Newport, Rhode Island, June 1997.
[6]
M. Frigo. The weakest reasonable memory model. Master's thesis, Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science, Jan. 1998.
[7]
M. Frigo and V. Luchangco. Computation-centric memory models. In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '98), pages 240--249, 1998.
[8]
J. Gray. The transaction concept: Virtues and limitations. In Proceedings of the 7th International Conference on Very Large Databases, pages 144--154, Sept. 1981.
[9]
J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
[10]
T. Harris. Exceptions and side-effects in atomic blocks. In In PODC Workshop on Concurrency and Synchronization in Java Programs, 2004.
[11]
M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In Principles of Distributed Computing, pages 92--101, New York, NY, USA, 2003. ACM Press.
[12]
M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In International Symposium on Computer Architecture, 1993.
[13]
D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe. Dependence graphs and compiler optimizations. In POPL '81: Proceedings of the 8th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 207--218, New York, NY, USA, 1981. ACM Press.
[14]
L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690--691, Sept. 1979.
[15]
B. Liblet. An operational semantics for LogTM. Technical report, Department of Computer Sciences, University of Wisconsin-Madison, August 2006.
[16]
A. McDonald, J. Chung, B. D. Carlstrom, C. Cao Minh, H. Chafi, C. Kozyrakis, and K. Olukotun. Architectural semantics for practical transactional memory. In International Symposium on Computer Architecture, June 2006.
[17]
J. E. B. Moss. Nested transactions and reliable distributed computing. In SRDS, pages 33--39, Pittsburgh, PA, July 1982.
[18]
J. E. B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. MIT Press, Cambridge, MA, USA, 1985.
[19]
J. E. B. Moss. Open nested transactions:semantics and support. In Workshop on Memory Performance Issues, Austin, Texas, Feb 2006.
[20]
J. E. B. Moss, N. D. Griffeth, and M. H. Graham. Abstraction in recovery management. In SIGMOD, pages 72--83, 1986.
[21]
J. E. B. Moss and A. L. Hosking. Nested transactional memory: Model and preliminary architecture sketches. In Synchronization and Concurrency in Object-Oriented Languages (SCOOL) Conference Proceedings, San Diego, California, Oct. 2005.
[22]
C. H. Papadimitriou. The serializability of concurrent database updates. Journal of the ACM, 26(4):631--653, 1979.
[23]
D. P. Reed. Naming and Synchronization in a Decentralized Computer System. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1978.
[24]
M. L. Scott. Sequential specification of transactional memory semantics. In TRANSACT: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.
[25]
I. Traiger. Trends in systems aspects of database management. In International Conference on Databases, pages 1--21. Wiley Heyden Ltd, 1983.
[26]
G. Weikum and H.-J. Schek. Concepts and applications of multilevel transactions and open nested transactions. In Database Transaction Models for Advanced Applications, pages 515--553. Morgan Kaufmann, San Francisco, CA, USA, 1992.
[27]
C. Zilles and L. Baugh. Extending hardware transactional memory to support non-busy waiting and non-transactional actions. In TRANSACT: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.

Cited By

View all
  • (2015)Transactional Read-Modify-Write Without AbortsACM Transactions on Architecture and Code Optimization10.1145/268890411:4(1-24)Online publication date: 9-Jan-2015
  • (2013)Scheduling Open-Nested Transactions in Distributed Transactional MemoryCoordination Models and Languages10.1007/978-3-642-38493-6_8(105-120)Online publication date: 2013
  • (2012)Scheduling Closed-Nested Transactions in Distributed Transactional MemoryProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.26(179-188)Online publication date: 21-May-2012
  • Show More Cited By

Recommendations

Comments

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
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2006

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

MSPC '06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 6 of 20 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Transactional Read-Modify-Write Without AbortsACM Transactions on Architecture and Code Optimization10.1145/268890411:4(1-24)Online publication date: 9-Jan-2015
  • (2013)Scheduling Open-Nested Transactions in Distributed Transactional MemoryCoordination Models and Languages10.1007/978-3-642-38493-6_8(105-120)Online publication date: 2013
  • (2012)Scheduling Closed-Nested Transactions in Distributed Transactional MemoryProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.26(179-188)Online publication date: 21-May-2012
  • (2012)An efficient scheduler for closed nested transactions that satisfies all-reads-consistency and non-interferenceProceedings of the 13th international conference on Distributed Computing and Networking10.1007/978-3-642-25959-3_30(409-423)Online publication date: 3-Jan-2012
  • (2011)Correctness of concurrent executions of closed nested transactions in transactional memory systemsProceedings of the 12th international conference on Distributed computing and networking10.5555/1946143.1946152(95-106)Online publication date: 2-Jan-2011
  • (2011)Composable, nestable, pessimistic atomic statementsACM SIGPLAN Notices10.1145/2076021.204813246:10(865-884)Online publication date: 22-Oct-2011
  • (2011)Composable, nestable, pessimistic atomic statementsProceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications10.1145/2048066.2048132(865-884)Online publication date: 22-Oct-2011
  • (2011)Transaction communicatorsACM SIGPLAN Notices10.1145/2038037.194157846:8(169-178)Online publication date: 12-Feb-2011
  • (2011)Transaction communicatorsProceedings of the 16th ACM symposium on Principles and practice of parallel programming10.1145/1941553.1941578(169-178)Online publication date: 12-Feb-2011
  • (2011)Lowering STM Overhead with Static AnalysisLanguages and Compilers for Parallel Computing10.1007/978-3-642-19595-2_3(31-45)Online publication date: 2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media