Fast and Robust Memory Reclamation for Concurrent Data Structures
Authors:
Open Access
- 11 July 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 349-359
Abstract
In concurrent systems without automatic garbage collection, it is challenging to determine when it is safe to reclaim memory, especially for lock-free data structures. Existing concurrent memory reclamation schemes are either fast but do not tolerate process delays, robust to delays but with high overhead, or both robust and fast but narrowly applicable. This paper proposes QSense, a novel concurrent memory reclamation technique. QSense is a hybrid technique with a fast path and a fallback path. In the common case (without process delays), a high-performing memory reclamation scheme is used (fast path). If process delays block memory reclamation through the fast path, a robust fallback path is used to guarantee progress. The fallback path uses hazard pointers, but avoids their notorious need for frequent and expensive memory fences. QSense is widely applicable, as we illustrate through several lock-free data structure algorithms. Our experimental evaluation shows that QSense has an overhead comparable to the fastest memory reclamation techniques, while still tolerating prolonged process delays.Keywords
This publication has 24 references indexed in Scilit:
- Reclaiming Memory for Lock-Free Data Structures2015
- ThreadScan2015
- A Better x86 Memory Model: x86-TSO2009
- 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
- High performance dynamic lock-free hash tables and list-based sets2002
- A Pragmatic Implementation of Non-blocking Linked-lists2001
- Lock-free reference counting2001
- Transactional memory1993