Universal wait-free memory reclamation
Authors:
Open Access
- 19 February 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 130-143
Abstract
In this paper, we present a universal memory reclamation scheme, Wait-Free Eras (WFE), for deleted memory blocks in wait-free concurrent data structures. WFE's key innovation is that it is completely wait-free. Although some prior techniques provide similar guarantees for certain data structures, they lack support for arbitrary wait-free data structures. Consequently, developers are typically forced to marry their wait-free data structures with lock-free Hazard Pointers or (potentially blocking) epoch-based memory reclamation. Since both these schemes provide weaker progress guarantees, they essentially forfeit the strong progress guarantee of wait-free data structures. Though making the original Hazard Pointers scheme or epoch-based reclamation completely wait-free seems infeasible, we achieved this goal with a more recent, (lock-free) Hazard Eras scheme, which we extend to guarantee wait-freedom. As this extension is non-trivial, we discuss all challenges pertaining to the construction of universal wait-free memory reclamation. WFE is implementable on ubiquitous x86_64 and AArch64 (ARM) architectures. Its API is mostly compatible with Hazard Pointers, which allows easy transitioning of existing data structures into WFE. Our experimental evaluations show that WFE's performance is close to epoch-based reclamation and almost matches the original Hazard Eras scheme, while providing the stronger wait-free progress guarantee.Keywords
All Related Versions
Funding Information
- Office of Naval Research (N00014-16-1-2711, N00014-18-1-2022)
- Air Force Office of Scientific Research (FA9550-16-1-0371)
This publication has 29 references indexed in Scilit:
- Reclaiming Memory for Lock-Free Data Structures2015
- ThreadScan2015
- Efficient Memory Management for Lock-Free Data Structures with Optimistic Access2015
- A methodology for creating fast wait-free data structures2012
- Performance of memory reclamation for lockless synchronizationJournal of Parallel and Distributed Computing, 2007
- Nonblocking memory management support for dynamic-sized data structuresACM Transactions on Computer Systems, 2005
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- Lock-free reference countingDistributed Computing, 2002
- A Pragmatic Implementation of Non-blocking Linked-lists2001
- Lock-free linked lists using compare-and-swap1995