Forkscan: Conservative memory reclamation for modern operating systems

D.-A. Alistarh, W. Leiserson, A. Matveev, N. Shavit, in:, ACM, 2017, pp. 483–498.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Alistarh, Dan-AdrianIST Austria; Leiserson, William; Matveev, Alexander; Shavit, Nir
Abstract
The problem of efficient concurrent memory reclamation in unmanaged languages such as C or C++ is one of the major challenges facing the parallelization of billions of lines of legacy code. Garbage collectors for C/C++ can be inefficient; thus, programmers are often forced to use finely-crafted concurrent memory reclamation techniques. These techniques can provide good performance, but require considerable programming effort to deploy, and have strict requirements, allowing the programmer very little room for error. In this work, we present Forkscan, a new conservative concurrent memory reclamation scheme which is fully automatic and surprisingly scalable. Forkscan's semantics place it between automatic garbage collectors (it requires the programmer to explicitly retire nodes before they can be reclaimed), and concurrent memory reclamation techniques (as it does not assume that nodes are completely unlinked from the data structure for correctness). Forkscan's implementation exploits these new semantics for efficiency: we leverage parallelism and optimized implementations of signaling and copy-on-write in modern operating systems to efficiently obtain and process consistent snapshots of memory that can be scanned concurrently with the normal program operation. Empirical evaluation on a range of classical concurrent data structure microbenchmarks shows that Forkscan can preserve the scalability of the original code, while maintaining an order of magnitude lower latency than automatic garbage collection, and demonstrating competitive performance with finely crafted memory reclamation techniques.
Publishing Year
Date Published
2017-01-01
Acknowledgement
William Leiserson, Alexander Matveev, and Nir Shavit were supported by the NSF under grants IIS-1447786 and CCF-1563880, and Dan Alistarh was supported by a Swiss National Fund Ambizione Fellowship.
Page
483 - 498
Conference
EuroSys: European Conference on Computer Systems
IST-REx-ID
789

Cite this

Alistarh D-A, Leiserson W, Matveev A, Shavit N. Forkscan: Conservative memory reclamation for modern operating systems. In: ACM; 2017:483-498. doi:10.1145/3064176.3064214
Alistarh, D.-A., Leiserson, W., Matveev, A., & Shavit, N. (2017). Forkscan: Conservative memory reclamation for modern operating systems (pp. 483–498). Presented at the EuroSys: European Conference on Computer Systems, ACM. https://doi.org/10.1145/3064176.3064214
Alistarh, Dan-Adrian, William Leiserson, Alexander Matveev, and Nir Shavit. “Forkscan: Conservative Memory Reclamation for Modern Operating Systems,” 483–98. ACM, 2017. https://doi.org/10.1145/3064176.3064214.
D.-A. Alistarh, W. Leiserson, A. Matveev, and N. Shavit, “Forkscan: Conservative memory reclamation for modern operating systems,” presented at the EuroSys: European Conference on Computer Systems, 2017, pp. 483–498.
Alistarh D-A, Leiserson W, Matveev A, Shavit N. 2017. Forkscan: Conservative memory reclamation for modern operating systems. EuroSys: European Conference on Computer Systems 483–498.
Alistarh, Dan-Adrian, et al. Forkscan: Conservative Memory Reclamation for Modern Operating Systems. ACM, 2017, pp. 483–98, doi:10.1145/3064176.3064214.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar