Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual; in the sense that the developer has to specify when nodes have retired and may be reclaimed. Retiring nodes adequately is non-trivial and often requires the modification of the original lock-free algorithm. In this paper we present an automatic lock-free reclamation scheme for lock-free data-structures in the spirit of a mark-sweep garbage collection. The proposed algorithm works with any normalized lock-free algorithm and with no need for the programmer to retire nodes or make changes to the algorithm. Evaluation of the proposed scheme on a linked-list and a hash table shows that it performs similarly to the best manual (lock-free) memory reclamation scheme.
Wed 28 OctDisplayed time zone: Eastern Time (US & Canada) change
15:30 - 17:00 | |||
15:30 22mTalk | AutoMO: Automatic Inference of Memory Order Parameters for C/C++11 OOPSLA Peizhao Ou University of California at Irvine, USA, Brian Demsky University of California at Irvine, USA DOI | ||
15:52 22mTalk | Valor: Efficient, Software-Only Region Conflict Exceptions OOPSLA Swarnendu Biswas Ohio State University, USA, Minjia Zhang Ohio State University, USA, Michael D. Bond Ohio State University, USA, Brandon Lucia Carnegie Mellon University, USA DOI Pre-print | ||
16:15 22mTalk | Automatic Memory Reclamation for Lock-Free Data Structures OOPSLA DOI | ||
16:37 22mTalk | Protocol-Based Verification of Message-Passing Parallel Programs OOPSLA Hugo A. López Technical University of Denmark, Eduardo Marques University of Lisbon, Portugal, Francisco Martins University of Lisbon, Portugal, Nicholas Ng Imperial College London, UK, César Santos University of Lisbon, Portugal, Vasco T. Vasconcelos University of Lisbon, Portugal, Nobuko Yoshida Imperial College London, UK Link to publication |