Dynamic memory storage has been widely used during years in computer science. However, its use in real-time systems has not been considered important issue because the spatial and temporal worst case for allocation deallocation operations were unbounded or bounded but with a very large bound.
Described in this paper is TLSF (Two Level Segregated Fit), a new allocator that has been designed specifically to meet real-time constraints in both the time and space dimensions..
While the temporal behavior of TLSF is excellent, the spatial constraint is configured for embedded systems with limited resources. This paper analyzes the performance of the TLSF allocator and compares it with other relevant allocator algorithms.
Because of the deterministic responses needed in real time systems, this requires the use of dynamic memory mechanisms which are completely predictable. Addressed are the temporal costs of dynamic allocation and deallocation in the context of the potential memory fragmentation that may occur. The conditions within which this analysis operated are:
1 – Bounded response time. The worst-case execution time (WCET) of memory allocation and deallocation has got to be known in advance and be independent of application data.
2 – Fast response time. Besides having a bounded response time, the response time has got to be short for the dynamic storage algorithm (DSA) to be usable. (A bounded DSA algorithm that is 10 times slower than a conventional one is not useful ).
3 – Memory requests need to be always satisfied. No real-time applications can receive a null pointer or just be killed by the OS when the system runs out of memory. Although it is obvious that it is not possible to always grant all the memory requested, the DSA algorithm has got to minimise the chances of exhausting the memory pool by minimizing the amount of fragmentation and wasted memory.
4 – Efficient use of memory . The allocator has got to manage memory efficiently; that is, the amount of wasted memory should be as small as possible.
(To read this external content in full, download the complete paper from the author archives on CiteSeerX.)