一种新型嵌入式动态内存分配算法

A new embedded dynamic memory allocation algorithm

针对TLSF算法的不足,提出使用直接分配算法和TLSF算法相结合的方式解决最差分配问题,用自适应算法来解决内存切割带入碎片问题,用新设计的表头检验方法解决内存溢出防护问题。首先,根据当前内存的最大空闲块的大小判断使用何种内存分配算法;然后,在内存使用过程中根据使用内存块的大小计算出最佳切割阈值,同时根据内存块实际物理地址和理论地址的比较来进行内存数据溢出的检测。实验结果表明,相比TLSF算法,新算法内存分配效率最多提高4.98%,内存释放效率在内存使用率较低时提高1.1%,较高时和TLSF算法基本没有差别;在内存使用率较高时,碎片率比TLSF算法最多降低了10.3%,并且能够有效地检测内存数据溢出,提高了安全防护能力。

TLSF（ Two-Level-Segregated Fit） algorithm has three shortages in the aspects of allocations, memory cutting and security. Combining the direct allocation algorithm with TLSF algorithm is to solve the worst allocation. Using the adaptive algorithm is to solve the problem of bringing fragmentations during memory cutting. Designing a new header testing method is to solve the safety problem. First of all, according to the largest free block of the current memory, which memory allocation algorithm should be used was judged. Then in the process of memory usage, according to the size of the used memory block,the optimal cutting threshold was calculated. At the same time, the memory leak was detected by comparing the actual physical address and theoretic addresses of the memory block. The experimental results show that, compared with the TLSF algorithm, the new algorithm increased the efficiency of internal memory allocation by 4. 98% at most; when the rate of memory usage was low, the efficiency for freeing memory was increased by 1. 1%, otherwise there was no difference; and, its memory fragmentation rate was reduced by 10. 3% at most. The new algorithm can detect the data overflow effectively and improve the capability of safety protection.