面向高速实时数据处理的无锁内存分配算法

发布时间：2021-10-12 20:50

　　为了提高高并发生产环境下内存分配的效率,针对高速实时数据处理程序的高并发、高频内存分配等特点,采用一种无锁内存分配算法（Lock Free Memory Allocation, LFMA）来提高并发度及内存分配效率。针对伙伴（Buddy）算法的不足,使用位图替代链表,并结合原子操作来达到线程间无锁并发访问,同时降低了缓存未命中的概率。引入多级位图来提高空闲内存块的搜索效率,通过渐进式重合并算法避免Buddy算法频繁拆合带来的效率问题,并降低了外部碎片。实验结果表明,相较于Buddy算法,新算法的分配效率在单线程下提升约31%,在多线程下提升约27%。 

【文章来源】：杭州电子科技大学学报(自然科学版). 2020,40(04)

【文章页数】：6 页

【部分图文】：

LFMA算法结构

3个实验组在单线程下进行n次不断申请和释放内存,每次申请的大小为(0,4]MByte的随机值来模拟短波显控系统中采集数据的大小范围,所消耗的时间总和如图2、图3所示。图3 向操作系统申请内存的时间

图2 LFMA与Buddy的内存分配时间根据图2可知:在单线程下,LFMA的内存分配速度优于Buddy,分配效率提升约31%,这主要有2个原因,一是Buddy算法要不断进行伙伴块的拆分与合并,其中还涉及到链表的插删操作。二是Buddy维护的是一个链表队列,而链表不是连续的存储单元,因此读取缓存行时更容易出现Cache miss。对比图2和图3可以发现:首先向操作系统申请一块内存做为内存池,之后再在应用层调用内存分配算法进一步分配,其效率远远高于频繁的向操作系统申请和释放内存。主要是由于每次向操作系统申请和释放内存都需要进行虚拟地址到物理地址的映射操作,从而导致效率低下。

【参考文献】：
期刊论文
[1]基于线段树的高效内存管理算法及其空间优化[J]. 王冬慧,韩建民,庄嘉琪.  计算机应用. 2015(12)
[2]一种嵌入式系统内存管理的延迟合并伙伴机制[J]. 郭振宇,桑楠,杨霞.  电子科技大学学报. 2007(03)



本文编号：3433275