Practical Lock-Free Dynamic Memory Allocation

Ricardo Leite

December 2018

---

Abstract

Dynamic memory allocation is an important component of most applications. Nowadays, due to the use of thread-level parallelism by applications, an important requirement in a memory allocator implementation is the ability to be thread safe. To guarantee thread safety, current state-of-the-art memory allocators use lock-based data structures. The use of locks has implications in terms of program performance, availability, robustness and flexibility. As such, current memory allocators attempt to minimize the effects of locking by using fine-grained locks, by reducing the frequency of lock operations and by providing synchronization-free allocations as much as possible through the use of thread-specific caches. An interesting but challenging alternative is to use lock-free data structures and atomic operations to guarantee thread safety.
We present LRMalloc, a lock-free memory allocator that leverages lessons of modern memory allocators and combines them with a lock-free scheme. Current state-of-the-art memory allocators possess good performance but lack desirable lock-free properties, such as, guarantees of system- wide progress, priority inversion tolerance, kill-tolerance availability, and/or deadlock and livelock immunity. LRMalloc’s purpose is to show the feasibility of lock-free memory management algorithms, without sacrificing competitiveness in comparison to commonly used state-of-the-art memory allocators, especially for concurrent multithreaded applications.
We also present a lock-free best-fit mechanism, capable of lock-free coalescing and splitting of blocks. To the best of our knowledge, our mechanism is the first lock-free general coalescing mechanism that supports coalescing and splitting of blocks with arbitrary sizes and does not put restrictions on how coalescing can be performed. Our mechanism ultimately aims to be used as a lower-level allocator for LRMalloc or other lock-free memory allocators, allowing them to manage memory without the assistance of the operating system, potentially improving performance by reducing the number of system calls.

Bibtex

@MastersThesis{leite-msc,
  author =  {R. Leite},
  title =   {{Practical Lock-Free Dynamic Memory Allocation}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {December},
  year =    {2018},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file