Fast and Robust Memory Reclamation for Concurrent Data Structures

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.

Published in:
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
Presented at:
28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16), Pacific Grove, California, USA, July 11 - 13, 2016

Note: The status of this file is: Anyone

 Record created 2016-12-15, last modified 2020-07-29

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)