Wed 28 Oct 2015 16:15 - 16:37 at Grand Station 1 - 4. Concurrency Chair(s): Wolfgang De Meuter

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: (GMT-04:00) Eastern Time (US & Canada) change

15:30 - 17:00: OOPSLA - 4. Concurrency at Grand Station 1
Chair(s): Wolfgang De MeuterVrije Universiteit Brussel
oopsla201515:30 - 15:52
Peizhao OuUniversity of California at Irvine, USA, Brian DemskyUniversity of California at Irvine, USA
oopsla201515:52 - 16:15
Swarnendu BiswasOhio State University, USA, Minjia ZhangOhio State University, USA, Michael D. BondOhio State University, USA, Brandon LuciaCarnegie Mellon University, USA
DOI Pre-print
oopsla201516:15 - 16:37
Nachshon CohenTechnion, Israel, Erez PetrankTechnion, Israel
oopsla201516:37 - 17:00
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