李文浩，方景龍

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

0 引 言

高速實(shí)時(shí)系統(tǒng)應(yīng)用中，內(nèi)存管理起著十分關(guān)鍵的作用。由于程序運(yùn)行階段的內(nèi)存分配皆由動(dòng)態(tài)內(nèi)存分配算法來(lái)完成，使得動(dòng)態(tài)內(nèi)存分配在內(nèi)存管理上尤其重要。伙伴(Buddy)算法憑借其較高的分配效率與內(nèi)存利用率，成為一種應(yīng)用廣泛的經(jīng)典算法。但是，Buddy算法仍存在一系列不足，特別是在高并發(fā)環(huán)境下，算法效率有較大的下滑。目前，對(duì)Buddy算法的改進(jìn)大都集中在延時(shí)合并以及外碎片方面，對(duì)并發(fā)性的改進(jìn)研究較少。本文針對(duì)高速實(shí)時(shí)系統(tǒng)的高并發(fā)特點(diǎn)，在Buddy算法的基礎(chǔ)上，提出一種無(wú)鎖內(nèi)存分配(Lock Free Memory Allocation, LFMA)算法，并通過(guò)漸進(jìn)式重合并策略實(shí)現(xiàn)了延時(shí)合并及降低外碎率的效果。

1 Buddy算法

Buddy算法在動(dòng)態(tài)內(nèi)存分配相關(guān)文獻(xiàn)中出現(xiàn)頻率較高，Linux內(nèi)核也使用該算法進(jìn)行內(nèi)存分配[1]。Buddy算法維護(hù)多個(gè)空閑隊(duì)列，大小為2m個(gè)頁(yè)的內(nèi)存塊都被鏈入同一個(gè)隊(duì)列中，其中m的最大值為mmax。當(dāng)要分配一個(gè)大小為b頁(yè)(2i-1

2 無(wú)鎖內(nèi)存分配算法

2.1 LFMA算法

單生產(chǎn)者多消費(fèi)者是一種高速實(shí)時(shí)系統(tǒng)的常見(jiàn)模型。如在短波實(shí)時(shí)顯控系統(tǒng)中，信號(hào)采集線(xiàn)程不斷申請(qǐng)內(nèi)存以存儲(chǔ)從硬件采集的信號(hào)數(shù)據(jù)，根據(jù)數(shù)據(jù)類(lèi)型分別交由解析線(xiàn)程池、繪圖線(xiàn)程和存儲(chǔ)線(xiàn)程進(jìn)行處理，隨后在這些線(xiàn)程中釋放內(nèi)存，這給內(nèi)存分配算法帶來(lái)同步問(wèn)題。文獻(xiàn)[10]對(duì)鎖和原子操作的性能進(jìn)行測(cè)試，結(jié)果顯示原子操作的性能約為鎖的2倍，同時(shí)Cache命中率也是關(guān)乎高速實(shí)時(shí)系統(tǒng)性能的一個(gè)重要問(wèn)題，每當(dāng)出現(xiàn)一次Cache miss都要花費(fèi)數(shù)百個(gè)時(shí)鐘周期到內(nèi)存中重新讀入數(shù)據(jù)到高速緩存。Buddy算法采用的鏈表結(jié)構(gòu)無(wú)疑增加了Cache miss的機(jī)率。因此，LFMA采用原子操作做為同步方式，并用位圖這一連續(xù)的數(shù)據(jù)結(jié)構(gòu)降低了Cache miss的概率。

由于每一個(gè)頁(yè)框只能是被分配和空閑兩種情況，因而，可以使用位圖標(biāo)記每一個(gè)頁(yè)框的狀態(tài)，位圖中每一位與一個(gè)頁(yè)框相對(duì)應(yīng)，若某頁(yè)框被分配則對(duì)應(yīng)位為0，若頁(yè)框空閑則對(duì)應(yīng)位為1，再將位圖結(jié)合原子操作以達(dá)到無(wú)鎖分配。LFMA算法包含一個(gè)一級(jí)位圖，其中每一位對(duì)應(yīng)當(dāng)前一個(gè)頁(yè)框的使用狀態(tài)，其結(jié)構(gòu)如圖1所示。

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

類(lèi)似于Buddy算法的空閑隊(duì)列，LFMA維護(hù)了多個(gè)空閑表，每個(gè)空閑表由搜索位圖和二級(jí)位圖構(gòu)成。其中二級(jí)位圖用于標(biāo)識(shí)空閑內(nèi)存塊，如，當(dāng)存在2k大小的空閑內(nèi)存塊時(shí)，第k個(gè)空閑表的二級(jí)位圖中對(duì)應(yīng)該空閑內(nèi)存塊首頁(yè)框的位被標(biāo)記為1。為了加快找到第一個(gè)空閑塊的速度，引入搜索位圖，每一位對(duì)應(yīng)二級(jí)位圖中的一個(gè)位圖切片(每張位圖是一個(gè)整型數(shù)組，而其中的一個(gè)整型稱(chēng)之為位圖切片)，若位圖切片為0，則搜索位圖中對(duì)應(yīng)位為0，否則為1。

在高并發(fā)程序中，臨界區(qū)是影響性能的主要原因，當(dāng)使用鎖做為同步方式時(shí)，由于同一時(shí)刻只有一個(gè)線(xiàn)程可以處于臨界區(qū)，因此，系統(tǒng)在臨界區(qū)的消耗如下：

(1)

(2)

Hlock=LAVG×T+OAVG×T

(3)

(4)

Hatomic=AAVG×T+OAVG

(5)

式中，Hlock為采用鎖同步時(shí)系統(tǒng)在臨界區(qū)的消耗。LAVG為加鎖操作的平均消耗，假設(shè)共加鎖n次，其中m次發(fā)生了Cache miss，第i次發(fā)生Cache miss時(shí)的加鎖消耗為L(zhǎng)cm(i)，未發(fā)生Cahce miss時(shí)的第i次加鎖消耗為L(zhǎng)c(i)，那么平均加鎖消耗可由公式(1)計(jì)算得出，即總耗時(shí)除加鎖次數(shù)n。OAVG為普通指令的平均消耗，假設(shè)臨界區(qū)內(nèi)共有n條普通指令，其中m條執(zhí)行時(shí)發(fā)生了Cache miss，第i次發(fā)生Cache miss時(shí)的消耗為Ocm(i)，未發(fā)生Cache miss的第i次操作消耗為Oc(i)，那么普通指令的平均消耗可由式(2)得到。T為等待在臨界區(qū)的線(xiàn)程數(shù)。當(dāng)使用原子操作時(shí)，在該段臨界區(qū)的消耗可由式(5)表述，其中Hatomic為采用原子操作時(shí)系統(tǒng)在臨界區(qū)的消耗。AAVG為原子操作的平均消耗。若執(zhí)行n次原子操作，其中m次發(fā)生了Cache miss，且第i次發(fā)生Cache miss時(shí)的消耗為Acm(i),未發(fā)生時(shí)為Ac(i)，那么原子操作的平均消耗可由式(4)得出。對(duì)比式(3)和式(5)可以發(fā)現(xiàn)，采用原子操作時(shí)，由于臨界區(qū)可以有多個(gè)線(xiàn)程同時(shí)進(jìn)入，因此普通指令的執(zhí)行可以并發(fā)執(zhí)行，在公式上的體現(xiàn)便是OAVG無(wú)需乘以T。由于LFMA算法采用了連續(xù)的數(shù)據(jù)結(jié)構(gòu)，從而降低了Cache miss概率，又由于原子操作的性能約為鎖的2倍，因此LAVG>2AAVG。綜上所述可知Hlock>Hatomic，即采用原子操作的消耗小于采用鎖做為同步方式的消耗。

2.2 多級(jí)位圖的原子操作

獨(dú)個(gè)原子操作具有原子性，但多個(gè)原子操作卻不一定是原子的。因此，雖然設(shè)置搜索位圖和設(shè)置二級(jí)位圖的操作都是原子的，但兩者組合起來(lái)卻不一定是并發(fā)安全的。比如，當(dāng)出現(xiàn)表1所示的執(zhí)行順序時(shí)，會(huì)導(dǎo)致某個(gè)位圖切片明明不為0，但搜索位圖中的相應(yīng)位卻為0。

表1 造成多級(jí)位圖出現(xiàn)競(jìng)態(tài)問(wèn)題的一種執(zhí)行順序

這個(gè)問(wèn)題可以通過(guò)加鎖解決，但違背了LFMA算法的無(wú)鎖原則，因此LFMA采用了雙判法。即內(nèi)存申請(qǐng)線(xiàn)程將搜索位圖設(shè)置為0后再判斷一次二級(jí)位圖中對(duì)應(yīng)切片是否為0，若不為0則重新將搜索位圖中相應(yīng)位置設(shè)為1。

2.3 漸進(jìn)式重合并算法

在諸如短波實(shí)時(shí)顯控這樣的高速實(shí)時(shí)系統(tǒng)中，其申請(qǐng)內(nèi)存塊的生命期通常較短，導(dǎo)致Buddy算法不斷分裂和合并內(nèi)存塊，文獻(xiàn)[11]提出延遲合并的思想，但并未給出具體實(shí)現(xiàn)，本文針對(duì)這一問(wèn)題，采用漸進(jìn)式重合并策略。LFMA算法中，當(dāng)釋放內(nèi)存后，并不立即進(jìn)行內(nèi)存塊的合并，而是當(dāng)某大小內(nèi)存塊數(shù)量不足時(shí)才進(jìn)行漸進(jìn)式重合并。其合并過(guò)程為一級(jí)位圖的分步搜索過(guò)程，內(nèi)存分配者通過(guò)位運(yùn)算在位圖中從前向后搜索連續(xù)1的個(gè)數(shù)，隨后將這些空閑頁(yè)合并為盡量大的內(nèi)存塊并設(shè)置相應(yīng)的二級(jí)位圖與搜索位圖。每當(dāng)合并出一個(gè)空閑塊，LFMA算法都會(huì)檢查本次合并所花費(fèi)的時(shí)間是否超過(guò)重合并最大時(shí)間限制，若超過(guò)，則記錄本次進(jìn)行到一級(jí)位圖的第幾位，以便下一次合并操作繼續(xù)執(zhí)行。通過(guò)漸進(jìn)式重合并，相較于Buddy算法，LFMA算法不僅減少了在頻繁申請(qǐng)釋放內(nèi)存時(shí)因不斷拆合內(nèi)存塊所帶來(lái)的負(fù)載，還減少了外碎片。

3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證LFMA算法的效率，首先進(jìn)行模擬實(shí)驗(yàn)。模擬實(shí)驗(yàn)選用Buddy算法做為對(duì)照組，并添加了一個(gè)直接向操作系統(tǒng)申請(qǐng)內(nèi)存的實(shí)驗(yàn)組做為參照組。實(shí)驗(yàn)在兩種不同環(huán)境下進(jìn)行，第一種是單線(xiàn)程申請(qǐng)釋放內(nèi)存，第二種是單個(gè)內(nèi)存申請(qǐng)線(xiàn)程和多個(gè)內(nèi)存釋放線(xiàn)程，即單生產(chǎn)者多消費(fèi)者模型。除模擬實(shí)驗(yàn)外，還測(cè)試了LFMA算法與Buddy算法在短波顯控系統(tǒng)中的實(shí)際表現(xiàn)。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 單線(xiàn)程下的分配效率

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

圖2 LFMA與Buddy的內(nèi)存分配時(shí)間

圖3 向操作系統(tǒng)申請(qǐng)內(nèi)存的時(shí)間

根據(jù)圖2可知：在單線(xiàn)程下，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)致效率低下。

3.2.2 單生產(chǎn)者多消費(fèi)者的分配效率

為了模擬高并發(fā)生產(chǎn)環(huán)境，實(shí)驗(yàn)使用一個(gè)線(xiàn)程做為生產(chǎn)者不斷申請(qǐng)內(nèi)存，之后通過(guò)一個(gè)隊(duì)列傳遞給多個(gè)消費(fèi)者線(xiàn)程，消費(fèi)者線(xiàn)程進(jìn)行內(nèi)存的釋放。實(shí)驗(yàn)統(tǒng)計(jì)了在不同消費(fèi)者數(shù)量下，LFMA和Buddy完成一百萬(wàn)次內(nèi)存分配和釋放的時(shí)間，結(jié)果如圖4所示。觀察圖4可以發(fā)現(xiàn)：隨著消費(fèi)者線(xiàn)程的增加，對(duì)鎖的爭(zhēng)搶更加頻繁，導(dǎo)致Buddy算法效率不斷下降，而LFMA采用的是無(wú)鎖數(shù)據(jù)結(jié)構(gòu)，因此隨著線(xiàn)程數(shù)的增加其效率下降相對(duì)平緩，且效率高于Buddy，平均性能提升約27%。

圖4 多線(xiàn)程下LFMA與Buddy的分配時(shí)間

3.2.3 在短波顯控系統(tǒng)中的應(yīng)用

在較為理論化的環(huán)境中進(jìn)行模擬實(shí)驗(yàn)后，將LFMA算法與Buddy算法在實(shí)際生產(chǎn)環(huán)境中進(jìn)行測(cè)試，分別測(cè)試兩者運(yùn)用于短波顯控系統(tǒng)時(shí)系統(tǒng)的實(shí)際效率。在實(shí)際生產(chǎn)中，隨著采集速率的變化，一般通過(guò)調(diào)節(jié)解析模塊線(xiàn)程池的線(xiàn)程數(shù)來(lái)匹配采集速率，采集線(xiàn)程與解析線(xiàn)程池構(gòu)成的單生成者多消費(fèi)者模型是系統(tǒng)的關(guān)鍵瓶頸，為此，實(shí)驗(yàn)記錄了在不同線(xiàn)程數(shù)量下系統(tǒng)解析模塊的性能變化，具體如表2所示。

表2 不同內(nèi)存分配算法與并發(fā)量下的數(shù)據(jù)解析速度 幀/s

觀察表1可以發(fā)現(xiàn)：當(dāng)解析線(xiàn)程池只有3個(gè)線(xiàn)程時(shí)，LFMA算法與Buddy算法對(duì)系統(tǒng)性能的影響并不大，因?yàn)榇藭r(shí)主要瓶頸在于解析速度，線(xiàn)程間內(nèi)存分配釋放的并發(fā)度不高；隨著線(xiàn)程數(shù)量的增加，內(nèi)存釋放的速率加快，對(duì)鎖的爭(zhēng)搶變得密集。由于LFMA算法采用的連續(xù)數(shù)據(jù)結(jié)構(gòu)有著比Buddy算法更低的Cache miss率，所以，采用LFMA算法與Buddy算法的性能差異也隨著并發(fā)度的提高逐漸體現(xiàn)出來(lái)；當(dāng)線(xiàn)程數(shù)增加到30時(shí)，解析線(xiàn)程池的處理能力并沒(méi)有一直增加，這是由于隨著線(xiàn)程的不斷增加，內(nèi)核調(diào)度線(xiàn)程以及線(xiàn)程間競(jìng)爭(zhēng)資源帶來(lái)的代價(jià)也在逐漸增加，因此當(dāng)線(xiàn)程數(shù)超過(guò)某一閾值，系統(tǒng)的處理能力反而有所下降。

4 結(jié)束語(yǔ)

在高速實(shí)時(shí)系統(tǒng)要求快速響應(yīng)、頻繁分配、高并發(fā)的背景下，本文在Buddy算法的基礎(chǔ)上，提出一種無(wú)鎖內(nèi)存分配算法LFMA，通過(guò)漸進(jìn)式重合并算法提高了在頻繁相似大小內(nèi)存分配情況下的分配效率。無(wú)論在單線(xiàn)程還是多線(xiàn)程情況下，LFMA的分配效率都有所提高。但是，本文算法在內(nèi)存總量過(guò)大時(shí)會(huì)造成位圖長(zhǎng)度較大或內(nèi)碎率過(guò)高的問(wèn)題，下一步的研究計(jì)劃是將內(nèi)存進(jìn)行區(qū)塊劃分，在每一個(gè)區(qū)塊上分別調(diào)用LFMA算法來(lái)解決上述問(wèn)題。