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 Oct Times are displayed in time zone: Eastern Time (US & Canada) change
15:30 - 17:00: 4. ConcurrencyOOPSLA at Grand Station 1 Chair(s): Wolfgang De MeuterVrije Universiteit Brussel | |||
15:30 - 15:52 Talk | AutoMO: Automatic Inference of Memory Order Parameters for C/C++11 OOPSLA Peizhao OuUniversity of California at Irvine, USA, Brian DemskyUniversity of California at Irvine, USA DOI | ||
15:52 - 16:15 Talk | Valor: Efficient, Software-Only Region Conflict Exceptions OOPSLA Swarnendu BiswasOhio State University, USA, Minjia ZhangOhio State University, USA, Michael D. BondOhio State University, USA, Brandon LuciaCarnegie Mellon University, USA DOI Pre-print | ||
16:15 - 16:37 Talk | Automatic Memory Reclamation for Lock-Free Data Structures OOPSLA DOI | ||
16:37 - 17:00 Talk | Protocol-Based Verification of Message-Passing Parallel Programs OOPSLA Hugo LópezTechnical University of Denmark, Eduardo MarquesUniversity of Lisbon, Portugal, Francisco MartinsUniversity of Lisbon, Portugal, Nicholas NgImperial College London, UK, César SantosUniversity of Lisbon, Portugal, Vasco VasconcelosUniversity of Lisbon, Portugal, Nobuko YoshidaImperial College London, UK Link to publication |