發(fā)布時(shí)間：2021-10-12 20:50

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

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

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

【部分圖文】：

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

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

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



本文編號(hào)：3433275