為了提高高并發(fā)生產(chǎn)環(huán)境下內(nèi)存分配的效率,針對高速實(shí)時數(shù)據(jù)處理程序的高并發(fā)、高頻內(nèi)存分配等特點(diǎn),采用一種無鎖內(nèi)存分配算法（Lock Free Memory Allocation, LFMA）來提高并發(fā)度及內(nèi)存分配效率。針對伙伴（Buddy）算法的不足,使用位圖替代鏈表,并結(jié)合原子操作來達(dá)到線程間無鎖并發(fā)訪問,同時降低了緩存未命中的概率。引入多級位圖來提高空閑內(nèi)存塊的搜索效率,通過漸進(jìn)式重合并算法避免Buddy算法頻繁拆合帶來的效率問題,并降低了外部碎片。實(shí)驗(yàn)結(jié)果表明,相較于Buddy算法,新算法的分配效率在單線程下提升約31%,在多線程下提升約27%。 

【文章來源】：杭州電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版). 2020,40(04)

【文章頁數(shù)】：6 頁

【部分圖文】：

LFMA算法結(jié)構(gòu)

3個實(shí)驗(yàn)組在單線程下進(jìn)行n次不斷申請和釋放內(nèi)存,每次申請的大小為(0,4]MByte的隨機(jī)值來模擬短波顯控系統(tǒng)中采集數(shù)據(jù)的大小范圍,所消耗的時間總和如圖2、圖3所示。圖3 向操作系統(tǒng)申請內(nèi)存的時間

圖2 LFMA與Buddy的內(nèi)存分配時間根據(jù)圖2可知:在單線程下,LFMA的內(nèi)存分配速度優(yōu)于Buddy,分配效率提升約31%,這主要有2個原因,一是Buddy算法要不斷進(jìn)行伙伴塊的拆分與合并,其中還涉及到鏈表的插刪操作。二是Buddy維護(hù)的是一個鏈表隊(duì)列,而鏈表不是連續(xù)的存儲單元,因此讀取緩存行時更容易出現(xiàn)Cache miss。對比圖2和圖3可以發(fā)現(xiàn):首先向操作系統(tǒng)申請一塊內(nèi)存做為內(nèi)存池,之后再在應(yīng)用層調(diào)用內(nèi)存分配算法進(jìn)一步分配,其效率遠(yuǎn)遠(yuǎn)高于頻繁的向操作系統(tǒng)申請和釋放內(nèi)存。主要是由于每次向操作系統(tǒng)申請和釋放內(nèi)存都需要進(jìn)行虛擬地址到物理地址的映射操作,從而導(dǎo)致效率低下。

【參考文獻(xiàn)】：
期刊論文
[1]基于線段樹的高效內(nèi)存管理算法及其空間優(yōu)化[J]. 王冬慧,韓建民,莊嘉琪.  計(jì)算機(jī)應(yīng)用. 2015(12)
[2]一種嵌入式系統(tǒng)內(nèi)存管理的延遲合并伙伴機(jī)制[J]. 郭振宇,桑楠,楊霞.  電子科技大學(xué)學(xué)報(bào). 2007(03)



本文編號：3433275