Generic Lock-Free Memory Reclamation

Pedro Moreno

June 2024

---

Abstract

With the current tendency for CPUs to have increasingly more cores in each generation, being able to take advantage of such large amounts of computing resources becomes increasingly important. Data structures are a fundamental building block for most programs, and their properties are inherited by the programs that use them. Lock-freedom is an important property, that not only ensures immunity to deadlocks, live-locks and priority inversion, but also allows high efficiency, minimal synchronization and great scalability. However, lock-free data structures require additional constructs to manage memory, that are known as Safe Memory Reclamation (SMR) methods. It is key that these methods are as efficient as possible, both in performance and in memory usage, in order for programs to take advantage of the available computing resources.
In this thesis, we review how synchronization between cores and memory management happens from the CPU architecture level to the data structure level, going over the language constructs, operating system, memory allocator, SMR methods and progress guarantees. In particular, we focus on a lock-free data structure, called Lock-Free Hash Tries (LFHT), and we explore the viability of applying the LFHT data structure to real world programs and we show how to make it scalable to larger amounts of data. We also propose a redesign of the LFHT data structure that makes it simpler, compatible with more SMR methods and more cache friendly. As the new design puts additional pressure on the SMR method, we propose a novel memory allocator extension that allows to both simplify and improve the memory management capabilities of the state-of-the-art Optimistic Access (OA) SMR method, which can be generally applied to other lock-free data structures. To conclude, we apply our improved OA method to our new design of the LFHT data structure.
Experimental results, show that our contributions, either increase performance across the board or give new general capabilities to the system at no significant performance cost. And, in most cases, we are able to both increase performance and practicality.

Bibtex

@PhdThesis{moreno-phd,
  author =  {P. Moreno},
  title =   {{Generic Lock-Free Memory Reclamation}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {June},
  year =    {2024},
  type =    {{PhD Thesis}},
}

Download Thesis

PDF file