A study on dynamic memory allocation mechanisms for small block sizes in real-time embedded systems

Abstract

Embedded real-time and battery-powered systems are increasing in numbers, and their software complexity is growing. This creates a demand for more efficient dynamic memory allocation in real-time embedded systems. Small improvements in dynamic memory allocation can greatly reduce system overall memory usage, fragmentation and energy consumption. Most of today’s general-purpose allocators are unsuitable for real-time embedded systems since they are not designed for real-time constraints.

This thesis contains a study on the suitability of dynamic memory allocation mechanisms for small block allocation in real-time embedded systems. We first perform a literature survey on dynamic memory allocation mechanisms and then analyze general-purpose allocators. From this we arrive to a set of allocation mechanisms for additional experimental study. We then conduct simulations on the selected mechanisms by using both real and synthetic traces to measure the mechanism fragmentation and WCET. We then evaluate the mechanisms and their tradeoffs and present an analysis on their suitability for small block allocation in real-time embedded systems.

This thesis additionally introduces Bitframe allocator, a new bitmapped fits allocator. The introduced allocator demonstrates that bitmapped fits can be used effectively for dynamic memory allocation. We are however unsure if bitmapped fits can offer better efficiency than other mechanisms.

Our results confirm that TLSF is one of the best allocators for real-time systems in terms of performance and fragmentation. Our results also confirm that reaps has low fragmentation and very low WCET when small blocks are allocated. Our results also show that simple segregated storage and region mechanism should not be used in real-time systems due to high worst-case fragmentation.