李文浩，方景龍

(杭州電子科技大學計算機學院，浙江 杭州 310018)

0 引 言

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

1 Buddy算法

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

2 無鎖內存分配算法

2.1 LFMA算法

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

由于每一個頁框只能是被分配和空閑兩種情況，因而，可以使用位圖標記每一個頁框的狀態(tài)，位圖中每一位與一個頁框相對應，若某頁框被分配則對應位為0，若頁框空閑則對應位為1，再將位圖結合原子操作以達到無鎖分配。LFMA算法包含一個一級位圖，其中每一位對應當前一個頁框的使用狀態(tài)，其結構如圖1所示。

圖1 LFMA算法結構

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

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

(1)

(2)

Hlock=LAVG×T+OAVG×T

(3)

(4)

Hatomic=AAVG×T+OAVG

(5)

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

2.2 多級位圖的原子操作

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

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

這個問題可以通過加鎖解決，但違背了LFMA算法的無鎖原則，因此LFMA采用了雙判法。即內存申請線程將搜索位圖設置為0后再判斷一次二級位圖中對應切片是否為0，若不為0則重新將搜索位圖中相應位置設為1。

2.3 漸進式重合并算法

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

3 實驗設計與分析

3.1 實驗設計

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

3.2 實驗結果與分析

3.2.1 單線程下的分配效率

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

圖2 LFMA與Buddy的內存分配時間

圖3 向操作系統(tǒng)申請內存的時間

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

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

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

圖4 多線程下LFMA與Buddy的分配時間

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

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

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

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

4 結束語

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