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. Conferences, Workshops, Symposiums, and Seminars
  4. Fast and Robust Memory Reclamation for Concurrent Data Structures
 
conference paper

Fast and Robust Memory Reclamation for Concurrent Data Structures

Balmau, Oana Maria  
•
Guerraoui, Rachid  
•
Herlihy, Maurice
Show more
2016
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16)

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
Loading...
Thumbnail Image
Name

p349-balmau.pdf

Type

Publisher's Version

Version

Published version

Access type

openaccess

Size

929.83 KB

Format

Adobe PDF

Checksum (MD5)

c61b057a549c88ce92780831ffb5470a

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