Dynamic lock-free data structures require a memory reclamation scheme with a similar progress. Until today, lock-free schemes are applied to data structures on a case-by-case basis, often with algorithm modifications to the data structure.
In this paper we introduce two new lock-free reclamation schemes, one manual and the other automatic with user annotated types. The manual reclamation scheme, named pass-the-pointer (PTP), has lock-free progress and a bound on the number of unreclaimed objects that is linear with the number of threads.
The automatic lock-free memory reclamation scheme, which we named OrcGC, uses PTP and object reference counting to automatically detect when to protect and when to de-allocate an object. OrcGC has a linear bound on memory usage and can be used with any allocator. We propose a new methodology that utilizes OrcGC to provide lock-free memory reclamation to a data structure.
We conducted a performance evaluation on two machines, an Intel and an AMD, applying PTP and OrcGC to several lock-free data structures, providing lock-free memory reclamation where before there was none. On the Intel machine we saw no significant performance impact, while on AMD we observed a worst-case performance drop below 50%.
Conference DayTue 2 MarDisplayed time zone: Eastern Time (US & Canada) change
10:00 - 11:00
|NBR: Neutralization Based Reclamation|
Ajay SinghUniversity of Waterloo, Trevor BrownUniversity of Waterloo, Ali MashtizadehUniversity of WaterlooLink to publication
|Efficiently Reclaiming Memory in Concurrent Search Data Structures While Bounding Wasted Memory|
Main ConferenceLink to publication
|OrcGC: Automatic Lock-Free Memory Reclamation|
Andreia CorreiaUniversity of Neuchatel, Switzerland, Pedro RamalheteCisco Systems, Pascal FelberUniversity of NeuchâtelLink to publication
|Are Dynamic Memory Managers on GPUs Slow? A Survey and Benchmarks|
Martin WinterGraz University of Technology, Mathias PargerGraz University of Technology, Daniel MlakarGraz University of Technology, Markus SteinbergerGraz University of TechnologyLink to publication