Dynamic Memory Allocation

Dynamic memory allocation is a process that allows a program to distribute efficiently its memory space in situations of unpredictable events that need to be stored in memory due to unknown inputs[10].

Using dynamic memory allocation, while a program is running, provides the ability to request more memory from the system. If there is enough memory available, the system will grant the program the right to use the amount it requests. However, as it previously mentioned, in some situations due to multiple allocation and deallocation actions with different sizes, dynamic memory allocation leads to some critical side effects such as internal and external fragmentation.  Resulting in unexpected memory failures of the system even if the total available space is sufficiently large to fulfill the requirement[5, 11]. Both internal and external fragmentation forms are usually referenced as wasted memory [1, 10]. However, it is worthy to analyze the difference between those two.

Internal fragmentation is a form of fragmentation that arises when allocations of memory are made only in multiples of a subunit. A request of arbitrary size must be met by rounding up to the next highest multiple of the subunit, leaving a small amount of memory that is allocated but not in use. Internal fragmentation is decreased by reducing the size of the subunit; such a reduction increases external fragmentation. In contrast, external fragmentation is a form of fragmentation that arises when memory is allocated in units of arbitrary size. When a large amount of memory is released, part of it may be used to meet a subsequent request, leaving an unused part that is too small to meet any further requests[12, 13].

The figure below, illustrates three different fragmentation states that could be occurred in a system using dynamic allocations. In the first one (a), a best case scenario is presented where there is no memory fragmentation, however in the second use case (b) , it is easily observed that a sort of fragmentation is occurred in the heap memory section. Finally, the last use case (c) presents a memory failure due to unavailable free memory space occurred by fragmentation which is defined as a serious issue in modern embedded systems development. However as it is showed in Johnstone et al [14], fragmentation problems can be efficiently managed by well-designed allocators.

Usually, an approach for avoiding memory fragmentations of the system with such a tendency is the use of system equipped with a memory management unit (MMU) alongside with a dynamic memory management algorithm.

A memory management unit is a hardware component that handles all memory operations associated with the virtual memory handling [7]. The foremost goal of memory management unit is to provide a convenient abstraction using virtual addresses to ensure the availability of adequate memory resources. In other words, MMU is a hardware part that translates a virtual address to physical address [15, 16].

MMU-equipped embedded systems can remap the fragmented memory spaces into a whole large block or even perform defragment operations to merge those pieces into a continuous physical block. Therefore, fragmentation problems only cause performance issues [15]. However, on MMU-less embedded systems this issue is complicated due to the limitation of a non-existence of virtual addresses, hence remapping [7].

Read More

This algorithm was used in:
https://devcoons.com/pentapod-robot-stretching-using-ik-algorithm/

References

[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.