A constant-time dynamic storage allocator for real-time systems
M. Masmano,  Ismael Ripoll,  Patricia Balbastre,  A. Crespo,  
Real-Time Systems
Dynamic memory allocation has been used for decades. However, it has seldom been used in real-time systems since the worst case of spatial and temporal requirements for allocation and deallocation operations is either unbounded or bounded but with a very large bound. In this paper, a new allocator called TLSF (Two Level Segregated Fit) is presented. TLSF is designed and implemented to accommodate real-time constraints. The proposed allocator exhibits time-bounded behaviour, O(1), and maintains a very good execution time. This paper describes in detail the data structures and functions provided by TLSF. We also compare TLSF with a representative set of allocators regarding their temporal cost and fragmentation. Although the paper is mainly focused on timing analysis, a brief study and comparative analysis of fragmentation incurred by the allocators has been also included in order to provide a global view of the behaviour of the allocators. The temporal and spatial results showed that TLSF is also a fast allocator and produces a fragmentation close to that caused by the best existing allocators. http://dx.doi.org/10.1007/s11241-008-9052-7
Not available
Author = {Masmano M., Ripoll Ismael, Balbastre Patricia, Crespo A., },
title = {A constant-time dynamic storage allocator for real-time systems},
journal = {Real-Time Systems},
volume = {40},
number = {2},
pages = {149-179},
year = {2008},
issn = {0922-6443 (Print) 1573-1383}