Design and Implementation of a Memory Allocator to Achieve Cache Partitioning in the Linux Kernel

Predictability is one of the key properties of hard real-time systems. A system is predictable when it is possible to guarantee in advance that the timing constraints of all the tasks in the system will be met. Achieving predictability on modern multi-core systems is, however, very challenging, mainly due to shared architectural resources, such as cache memories. It has been shown that the interference caused by a shared cache can increase the task execution time by up to 40%, with even higher delay spikes that are hard to predict. The problem of mitigating the effects of cache interference has received much attention in the real-time systems community. A popular and effective approach is a software cache-partitioning technique called page coloring. With page coloring, memory is partitioned into colors. Assigning different colors to different tasks avoids cache interference between the tasks, as they do not contend for the same cache partitions. Therefore, the tasks are spatially isolated in cache. Various uses of page coloring have been proposed in the literature. However, the existing implementation efforts only take into account single page requests and do not isolate kernel processes, which can still interfere with other tasks. Conversely to previous works, this thesis targets both user-space and kernel memory. The objective of this work is to provide insights into the design and implementation of a page coloring solution for the latest Linux PREEMPT-RT kernel. The proposed implementation supports both single-page and multiple-page allocation schemes. Experimental results show significant improvements in task isolation, as our solution reduces the effects of cache interference. Interference affecting worst-case execution times is decreased from 14.6% to a maximum of 4.4%