Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. Fast and Robust Memory Reclamation for Concurrent Data Structures
 
report

Fast and Robust Memory Reclamation for Concurrent Data Structures

Balmau, Oana Maria  
•
Guerraoui, Rachid  
•
Herlihy, Maurice
Show more
2016

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.

  • Files
  • Details
  • Metrics
Type
report
Author(s)
Balmau, Oana Maria  
Guerraoui, Rachid  
Herlihy, Maurice
Zablotchi, Mihail Igor  
Date Issued

2016

Total of pages

13

Subjects

Memory reclamation

•

Concurrent algorithms

•

Performance

•

Robustness

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
May 17, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/126134
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés