Memory Management Algorithms for MMU-Less Systems


There are several different approaches for memory management that can solve the fragmentation problem on MMU-less embedded systems. Each algorithm is classified according to the way that it finds a free block of the most appropriate size. There are five categories extendedly analyzed in M. Masmano el al. [1], Sun et al. [2] and P. R. Wilson [10] works: Sequential Fit, Segregated Free Lists, Buddy Systems, Indexed Fit and Bitmap Fit.

A simple but not always feasible solution is the formatting of the available system memory into uniform blocks. By using this approach, embedded systems have to face a crucial limitation of serving the diverse-sized requested blocks, which makes it inefficient for complex and demanding applications.

Buddy systems approach attempts to split the available memory into two same-sized blocks respecting the efficiency issue and increasing the overall performance. This method usually creates fragmented memory parts after extended use of allocation and deallocation processes. In the buddy system, the memory is broken down into power-of-two sized naturally aligned blocks [17]. This approach greatly reduces external fragmentation of memory and helps in allocating bigger continuous blocks of memory aligned to their size. On the other hand, the buddy allocator suffers increased internal fragmentation of memory and is not suitable for general kernel allocations. This purpose is better addressed by the slab allocator.

Slab allocator, creates different sized blocks and matches the requested allocation to the closest one. The majority of memory allocation requests in the kernel is for small, frequently used data structures. The basic idea behind the slab allocator is that commonly used objects are pre-allocated in continuous areas of physical memory called slabs. Whenever an object is to be allocated, the slab allocator returns the first available item from a suitable slab corresponding to the object type. Because the sizes of the requested and allocated block match, the slab allocator significantly reduces internal fragmentation [6]. The advantage of this setup is that during most of the allocations, no global spinlock needs to be held. CAMA [6], which is a research follow-up of slab allocator, has a better performance by splitting and merging the block accordingly.

Two-Level Segregated Fit [1] (TLSF algorithm) seeks to implement a good-fit policy in order to fulfill the most important real-time requirements. The basic segregated fit mechanism uses an array of free lists, with each array holding free blocks within a size class. In order to speed-up the access to the free blocks and also to manage a large set of segregated lists, the array of lists is organized as a two-level array. The first-level array divides free blocks in classes that are a power of two apart (16, 32, 64, 128, etc.); and the second-level sub-divides each first-level class linearly, where the number of divisions is a user configurable parameter. Each array of lists has an associated bitmap used to mark which lists are empty and which ones contain free blocks.


[1]   M. Masmano, I. Ripoll, A. Crespo, and J. Real, “TLSF: A new dynamic memory allocator for real-time systems,” in Real-Time Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on, 2004, pp. 79-88.

[2]   X. Sun, J. Wang, and X. Chen, “An improvement of TLSF algorithm,” in Real-Time Conference, 2007 15th IEEE-NPSS, 2007, pp. 1-5.

[3]   M. Masmano, I. Ripoll, and A. Crespo, “Dynamic storage allocation for real-time embedded systems,” Proc. of Real-Time System Simposium WIP, 2003.

[4]   A. Crespo, I. Ripoll, and M. Masmano, “Dynamic memory management for embedded real-time systems,” in From Model-Driven Design to Resource Management for Distributed Embedded Systems, ed: Springer, 2006, pp. 195-204.

[5]   T. Kani, “Dynamic memory allocation,” ed: U.S. Patent Application 14/396,383, 2012.

[6]   J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator,” in USENIX summer, 1994.

[7]   Y.-H. Yu, J.-Z. Wang, and T.-Y. Sun, “A Novel Defragmemtable Memory Allocating Schema for MMU-Less Embedded System,” in Advances in Intelligent Systems and Applications – Volume 2. vol. 21, J.-S. Pan, C.-N. Yang, and C.-C. Lin, Eds., ed: Springer Berlin Heidelberg, 2013, pp. 751-757.

[8]   M. Stonebraker, U. Çetintemel, and S. Zdonik, “The 8 requirements of real-time stream processing,” ACM SIGMOD Record, vol. 34, pp. 42-47, 2005.

[9]   I. Puaut, “Real-time performance of dynamic memory allocation algorithms,” in Real-Time Systems, 2002. Proceedings. 14th Euromicro Conference on, 2002, pp. 41-49.

[10] P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles, “Dynamic storage allocation: A survey and critical review,” in Memory Management, ed: Springer, 1995, pp. 1-116.

[11] K. Wang, “Memory Management,” in Design and Implementation of the MTX Operating System, ed: Springer, 2015, pp. 215-234.

[12] H. J. Boehm and P. F. Dubois, “Dynamic memory allocation and garbage collection,” Computers in Physics, vol. 9, pp. 297-303, 1995.

[13] W. E. Croft and A. Henderson, “Eliminating memory fragmentation and garbage collection from the process of managing dynamically allocated memory,” ed: Google Patents, 2002.

[14] M. S. Johnstone and P. R. Wilson, “The memory fragmentation problem: solved?,” in ACM SIGPLAN Notices, 1998, pp. 26-36.

[15] D.-B. Koh, “Memory management unit with address translation function,” ed: Google Patents, 1997.

[16] J. E. Zolnowsky, C. L. Whittington, and W. M. Keshlear, “Memory management unit,” ed: Google Patents, 1984.

[17] G. S. Brodal, E. D. Demaine, and J. I. Munro, “Fast allocation and deallocation with an improved buddy system,” Acta Informatica, vol. 41, pp. 273-291, 2005.

[18] G. Barootkoob, M. Sharifi, E. M. Khaneghah, and S. L. Mirtaheri, “Parameters affecting the functionality of memory allocators,” in Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on, 2011, pp. 499-503.

[19] S. Loosemore, U. Drepper, R. M. Stallman, A. Oram, and R. McGrath, The GNU C library reference manual: Free software foundation, 1993.

Disclaimer: The present content may not be used for training artificial intelligence or machine learning algorithms. All other uses, including search, entertainment, and commercial use, are permitted.