Title: Effective memory reclamation for lock-free data structures in C++
Language: English
Authors: Pöter, Manuel Johannes 
Qualification level: Diploma
Advisor: Träff, Jesper Larsson  
Issue Date: 2018
Number of Pages: 170
Qualification level: Diploma
Abstract: 
Diese Arbeit befasst sich mit der Problematik der Wiederverwendung von alloziertem Speicher im Kontext von nebenläufigen Datenstrukturen. Speicherverwaltung ist ein wesentlicher Aspekt in fast allen shared-memory concurrent Datenstrukturen und Algorithmen, bestehend aus Allokation und Freigabe bzw. Wiederverwendung von Resourcen. Speziell die Freigabe bzw. Wiederverwendung nicht mehr benötigter Objekte stellt eine große Herausforderung dar und ist daher nach wie vor ein aktives Forschungsgebiet. Diese Arbeit bietet einen ausführlichen Überblick über den aktuellen Forschungsstand und beschreibt einen Großteil der aktuellen Reclamation Schemata. Desweiteren wird ein neues Schema namens Stamp-it vorgestellt. Einige der beschriebenen Reclamation Schemata wurden in C++ implementiert. Die Implementierung basiert auf einem generalisierten, abstrakten Interface, welches für den C++ Standard vorgeschlagen wurde. Es wurden die folgenden Schemata implementiert: Lock-free Reference Counting, Hazard Pointers, Quiescent State-based Reclamation, Epoch-based Reclamation, New Epoch-based Reclamation und Stamp-it. Ausführliche Erklärungen der Implementierungen werden ebenso präsentiert wie Argumente zu ihrer Korrektheit, basierend auf dem C++11 Speichermodell. Die implementierten Schemata wurden in einer umfangreichen, experimentellen Analyse untersucht. Es wurden sowohl neue, als auch häufig genutzte Benchmarks auf vier verschiedenen shared-memory Systemen eingesetzt. Die Ergebnisse zeigen, dass Stamp-it in den meisten Fällen vergleichbare, in einigen Fällen auch bessere Performance bietet als andere Schemata.

This thesis deals with the aspect of memory reclamation in concurrent data structures. Memory management is a critical component in almost all shared-memory, concurrent data structures and algorithms, consisting in the efficient allocation and the subsequent reclamation of shared memory resources. Especially the reclamation of no longer used memory becomes a real challenge in the face of concurrent lock-free data structures, and therefore this is still a very active research topic. This work provides an extensive overview over the current state of the art, and also presents yet another reclamation scheme called Stamp-it. Some of the discussed reclamation schemes have been implemented in C++, based on a generalized, abstract interface that has been proposed for the C++ standard. The implemented schemes are: Lock-free Reference Counting, Hazard Pointers, Quiescent State-based Reclamation, Epoch-based Reclamation, New Epoch-based Reclamation and Stamp-it. A detailed discussion of these implementations is provided, including correctness arguments based on the the C++11 memory model semantics. The implemented schemes have been analyzed in an extensive, experimental evaluation, presenting results for both new and commonly used benchmarks, on four different shared-memory systems with hardware supported thread counts ranging from 48 to 512. The results show Stamp-it to be competitive with and in many cases and aspects outperforming other schemes.
Keywords: Nebenläufige Algoirthmen und Datenstrukturen; Speicherverwaltung; Speicherwiederverwendung
Concurrent Algorithms and Data Structures; Memory Management; Memory Reclamation
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-109661
http://hdl.handle.net/20.500.12708/4346
Library ID: AC14552708
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

62
checked on Jul 27, 2021

Download(s)

1,326
checked on Jul 27, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.