research-article

Drop the anchor: lightweight memory management for non-blocking data structures

Authors:

Anastasia Braginsky,

Erez PetrankAuthors Info & Claims

SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

Pages 33 - 42

https://doi.org/10.1145/2486159.2486184

Published: 23 July 2013 Publication History

Abstract

Efficient memory management of dynamic non-blocking data structures remains an important open question. Existing methods either sacrifice the ability to deallocate objects or reduce performance notably. In this paper, we present a novel technique, called Drop the Anchor, which significantly reduces the overhead associated with the memory management while reclaiming objects even in the presence of thread failures. We demonstrate this memory management scheme on the common linked list data structure. Using extensive evaluation, we show that Drop the Anchor significantly outperforms Hazard Pointers, the widely used technique for non-blocking memory management.

References

[1]

H. Attiya and A. Fouren. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput., 31(2):642--664, 2001.

Digital Library

[2]

A. Braginsky, A. Kogan, and E. Petrank. Drop the anchor: Lightweight memory management for non-blocking data structures (full version). http://www.cs.technion.ac.il/~erez/Papers/DropTheAnchorFull.pdf.

Digital Library

[3]

A. Braginsky and E. Petrank. Locality-conscious lock-free linked lists. In ICDCN, pages 107--118, 2011.

Digital Library

[4]

D. Detlefs, P. A. Martin, M. Moir, and G. L. Steele. Lock-free reference counting. Distributed Computing, 15(4):255--271, 2002.

Digital Library

[5]

A. Dragojevic, M. Herlihy, Y. Lev, and M. Moir. On the power of hardware transactional memory to simplify memory management. In PODC, pages 99--108, 2011.

Digital Library

[6]

A. Gidenstam, M. Papatriantafilou, H. Sundell, and P. Tsigas. Efficient and reliable lock-free memory reclamation based on reference counting. TPDS, 20(8):1173--1187, 2009.

Digital Library

[7]

T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In DISC, pages 300--314, 2001.

Digital Library

[8]

T. E. Hart, P. E. McKenney, A. D. Brown, and J. Walpole. Performance of memory reclamation for lockless synchronization. Journal of Parallel and Distributed Computing, 67(12):1270--1285, 2007.

Digital Library

[9]

M. Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, 1991.

Digital Library

[10]

M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking memory management support for dynamic-sized data structures. ACM Trans. Comput. Syst., 23(2):146--196, 2005.

Digital Library

[11]

M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., 2008.

Digital Library

[12]

M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990.

Digital Library

[13]

P. E. McKenney and J. D. Slingwine. Read-copy update: Using execution history to solve concurrency problems. In PDCS, pages 509--518, 1998.

[14]

M. M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. TPDS, 15:491--504, 2004.

Digital Library

[15]

H. Sundell. Wait-free reference counting and memory management. In IPDPS, 2005.

Digital Library

[16]

J. D. Valois. Lock-free linked lists using compare-and-swap. In PODC, pages 214--222, 1995.

Digital Library

Cited By

Nikolaev RRavindran B(2024)A Family of Fast and Memory Efficient Lock- and Wait-Free ReclamationProceedings of the ACM on Programming Languages10.1145/36588518:PLDI(2174-2198)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3658851
Singh ABrown TMashtizadeh A(2024)Simple, Fast and Widely Applicable Concurrent Memory Reclamation via NeutralizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333567135:2(203-220)Online publication date: Feb-2024
https://doi.org/10.1109/TPDS.2023.3335671
Sheffi GPetrank EOshman RNolin AHalldorsson MBalliu A(2023)The ERA Theorem for Safe Memory ReclamationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594564(102-112)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594564
Show More Cited By

Index Terms

Drop the anchor: lightweight memory management for non-blocking data structures

Recommendations

Releasing Memory with Optimistic Access: A Hybrid Approach to Memory Reclamation and Allocation in Lock-Free Programs
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

Lock-free data structures are an important tool for the development of concurrent programs as they provide scalability, low latency and avoid deadlocks, livelocks and priority inversion. However, they require some sort of additional support to guarantee ...
Automatic memory reclamation for lock-free data structures
OOPSLA '15

Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual'' in the sense that the developer has to ...
Efficient Memory Management for Lock-Free Data Structures with Optimistic Access
SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

Lock-free data structures achieve high responsiveness, aid scalability, and avoid deadlocks and livelocks. But providing memory management support for such data structures without foiling their progress guarantees is difficult. Often, designers employ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

July 2013

348 pages

ISBN:9781450315722

DOI:10.1145/2486159

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Berthold Vöcking
RWTH Aachen University, Germany

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA '13

Sponsor:

SPAA '13: 25th ACM Symposium on Parallelism in Algorithms and Architectures

July 23 - 25, 2013

Québec, Montréal, Canada

Acceptance Rates

SPAA '13 Paper Acceptance Rate 31 of 130 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
299
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikolaev RRavindran B(2024)A Family of Fast and Memory Efficient Lock- and Wait-Free ReclamationProceedings of the ACM on Programming Languages10.1145/36588518:PLDI(2174-2198)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3658851
Singh ABrown TMashtizadeh A(2024)Simple, Fast and Widely Applicable Concurrent Memory Reclamation via NeutralizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333567135:2(203-220)Online publication date: Feb-2024
https://doi.org/10.1109/TPDS.2023.3335671
Sheffi GPetrank EOshman RNolin AHalldorsson MBalliu A(2023)The ERA Theorem for Safe Memory ReclamationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594564(102-112)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594564
Moreno PRocha RAgrawal KShun J(2023)Releasing Memory with Optimistic Access: A Hybrid Approach to Memory Reclamation and Allocation in Lock-Free ProgramsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591089(177-186)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591089
Nikolaev RRavindran BFreund SYahav E(2021)Snapshot-free, transparent, and robust memory reclamation for lock-free data structuresProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454090(987-1002)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454090
Anderson DBlelloch GWei YFreund SYahav E(2021)Concurrent deferred reference counting with constant-time overheadProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454060(526-541)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454060
Singh ABrown TMashtizadeh ALee JPetrank E(2021)NBRProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441625(175-190)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441625
Correia ARamalhete PFelber PLee JPetrank E(2021)OrcGCProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441596(205-218)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441596
Solomon DMorrison ALee JPetrank E(2021)Efficiently reclaiming memory in concurrent search data structures while bounding wasted memoryProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441582(191-204)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441582
Rodriguez MHassan ASpear M(2021)Exploiting Locality in Scalable Ordered Maps2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS51616.2021.00099(998-1008)Online publication date: Jul-2021
https://doi.org/10.1109/ICDCS51616.2021.00099
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