Fast Memory Compaction for Page Allocators
- Typ der Arbeit: Bachelorarbeit
- Status der Arbeit: abgeschlossen
- Projekte: ParPerOS
- Betreuer: Lars Wrenger, Daniel Lohmann
- Ende der Arbeit: 01. Apr 2023
In ParPerOS, we examine new OS-level memory management abstractions for new memory technologies. For this, we are developing a new lock- and log-free page frame allocator for systems with many CPUs and a lot of memory.
A common problem for allocators is memory fragmentation. Fragmentation can occur if an allocator manages different sized chunks (in our case, between 1 and 1024 pages). Depending on how the memory is allocated, these allocations could be spread out over the memory area, so that only small holes of free memory are left. These holes might be too small for larger allocation, even if combined enough free memory is avaliable. In this case, the allocator is fragmented and has to be manually defragmented. The allocated pages must be moved to other locations to create larger holes to satisfy large allocations. This is called memory compaction. Several memory compaction algorithms have been researched that minimize the number of pages that have to be moved to clear large contiguous chunks.
The goal of this thesis is to research memory compactions algorithms and optionally implement them for the new lo(ck|g)-free allocator. These algorithms could then be compared against each other on different metrics, like performance, the number of moved pages and the number of cleared large chunks. The allocator is implemented in the Rust programming language and can be tested and benchmarked in the userspace like every other application. Thus, no detailed knowledge about operating systems or the Linux Kernel is needed.
Depending on your focus, this thesis might be a pure literature review or the more practical implemenetation and evaluation of multiple algorithms.
Keywords
- Page allocators
- Memory compaction
- Low-level programming
- Rust, (C)