嵌入式實(shí)時(shí)系統(tǒng)內(nèi)存池技術(shù)分析

摘要：在嵌入式實(shí)時(shí)系統(tǒng)中，內(nèi)存資源的使用通常要求較小的響應(yīng)時(shí)間，并減少內(nèi)存碎片的產(chǎn)生。為滿足這些要求，開發(fā)者普遍采用內(nèi)存池技術(shù)。通過內(nèi)存池技術(shù)，申請(qǐng)和釋放內(nèi)存的過程無需系統(tǒng)調(diào)用的介入，這提高了執(zhí)行效率，因此在嵌入式實(shí)時(shí)系統(tǒng)中被廣泛應(yīng)用。本文詳細(xì)分析了常用的內(nèi)存池資源管理技術(shù)的原理，并探討了它們?cè)趯?shí)踐中采用的實(shí)現(xiàn)方法。同時(shí)，總結(jié)了它們的優(yōu)缺點(diǎn)，并根據(jù)各自的特點(diǎn)提出了一些有效的改進(jìn)思路，以改善系統(tǒng)的響應(yīng)速度并減少內(nèi)存碎片的生成。

關(guān)鍵字：內(nèi)存池；響應(yīng)時(shí)間；內(nèi)存碎片

在嵌入式系統(tǒng)應(yīng)用軟件設(shè)計(jì)中，經(jīng)常需要管理和利用內(nèi)存資源。動(dòng)態(tài)內(nèi)存由于可以在系統(tǒng)運(yùn)行過程中按需獲取而減少了浪費(fèi)，在嵌入式軟件中得到了廣泛使用。然而，頻繁地通過系統(tǒng)調(diào)用申請(qǐng)釋放內(nèi)存會(huì)產(chǎn)生較大的時(shí)間開銷，而嵌入式實(shí)時(shí)系統(tǒng)對(duì)時(shí)間開銷要求較高。因此，通過系統(tǒng)調(diào)用的方式獲取內(nèi)存并不適合實(shí)時(shí)系統(tǒng)。嵌入式實(shí)時(shí)系統(tǒng)一般采用內(nèi)存池方案，在系統(tǒng)初始化時(shí)分配一塊內(nèi)存，由開發(fā)者自行管理內(nèi)存的分配，避免系統(tǒng)調(diào)用，可以有效地提升內(nèi)存申請(qǐng)釋放的響應(yīng)速度[1]。本文研究了幾種常用的內(nèi)存池資源分配技術(shù)，分析了它們的優(yōu)缺點(diǎn)，并根據(jù)相應(yīng)的缺點(diǎn)提出了一些改進(jìn)措施。

一、內(nèi)存池基本原理

在系統(tǒng)初始化階段，用戶向系統(tǒng)申請(qǐng)一塊內(nèi)存區(qū)域，或者指定一塊DDR區(qū)域作為內(nèi)存池，在運(yùn)行期間供用戶使用。通過采用特定的管理方式，可以有效管理這塊內(nèi)存區(qū)域。在用戶申請(qǐng)內(nèi)存時(shí)，從這塊內(nèi)存池中取出指定大小的內(nèi)存塊，并將其分配給用戶使用。當(dāng)用戶釋放內(nèi)存時(shí)，將釋放的內(nèi)存塊合并回內(nèi)存池。這個(gè)過程只需在用戶態(tài)操作，無需轉(zhuǎn)化到內(nèi)核態(tài)，能有效減少時(shí)間開銷。使用內(nèi)存池對(duì)內(nèi)存進(jìn)行管理的步驟如下[2]：

①初始時(shí)刻，內(nèi)存池中的內(nèi)存是一整塊內(nèi)存區(qū)域，這塊區(qū)域可以通過系統(tǒng)調(diào)用向系統(tǒng)申請(qǐng)獲取，或者指定某一段DDR空間作為內(nèi)存池使用。

②首次申請(qǐng)內(nèi)存時(shí)，直接從初始內(nèi)存塊中取出一部分使用。

③當(dāng)需要釋放內(nèi)存時(shí)，需要考慮釋放的內(nèi)存區(qū)域是否可以與內(nèi)存池中相鄰的內(nèi)存區(qū)域合并。

④如果內(nèi)存池中有空閑內(nèi)存區(qū)域，再次申請(qǐng)內(nèi)存時(shí)需要尋找合適的內(nèi)存區(qū)域，該步驟涉及一些選取內(nèi)存區(qū)域的策略。

在實(shí)際設(shè)計(jì)內(nèi)存池時(shí)，需要考慮一些關(guān)鍵問題，包括搜索可用內(nèi)存區(qū)域的速度、內(nèi)存碎片的情況，以及采用合適的數(shù)據(jù)結(jié)構(gòu)管理和維護(hù)空閑內(nèi)存。此外，為了在發(fā)生內(nèi)存問題時(shí)能夠高效地定位問題，設(shè)計(jì)者需要添加一些維護(hù)信息以提升系統(tǒng)的可維護(hù)性。接下來，文章將結(jié)合具體的算法描述這些問題的解決思路。

二、內(nèi)存池資源分配技術(shù)

本節(jié)詳細(xì)分析首次適配、最佳適配和TLSF三種內(nèi)存池資源分配技術(shù)。

（一）首次適配

首次適配的思想較為簡單，搜索系統(tǒng)中的空閑內(nèi)存區(qū)域，返回第一個(gè)滿足條件的空閑內(nèi)存區(qū)域。如圖1所示，淺色區(qū)域?yàn)榭臻e內(nèi)存區(qū)，深色區(qū)域?yàn)槭褂弥械膬?nèi)存區(qū)，如果需要申請(qǐng)2字節(jié)內(nèi)存，就可以從左到右遍歷空閑內(nèi)存區(qū)域，找到第一個(gè)不小于2字節(jié)的空閑區(qū)域，圖中場景該方案將返回大小為2.5字節(jié)內(nèi)存區(qū)域的首地址。

圖1 首次適配區(qū)域圖

由于該算法不關(guān)心空閑節(jié)點(diǎn)和所需內(nèi)存大小的適配程度，所以容易產(chǎn)生內(nèi)存碎片，產(chǎn)生的內(nèi)存碎片需要使用一定的方法進(jìn)行管理，否則會(huì)對(duì)后續(xù)內(nèi)存申請(qǐng)效率產(chǎn)生影響。因此，內(nèi)存碎片也是嵌入式系統(tǒng)內(nèi)存管理中需要關(guān)注的一個(gè)重要問題[3]。

（二）最佳適配

最佳適配和首次適配類似，都需要搜索空閑內(nèi)存區(qū)域。不同的是，兩者搜索方式不同。最佳適配需要找到滿足條件的最小空閑內(nèi)存區(qū)域，因此響應(yīng)速度一般慢于首次適配，但它完整地遍歷了內(nèi)存池，考慮了目標(biāo)內(nèi)存區(qū)域和所需內(nèi)存大小的適配程度，不僅減少了內(nèi)存碎片問題，還提高了內(nèi)存空間的利用率。圖1中如果使用最佳適配則會(huì)返回最后一個(gè)空閑區(qū)域。當(dāng)然，在最差情況下，即需要遍歷整個(gè)空閑內(nèi)存區(qū)域的情況下，首次適配和最佳適配的響應(yīng)時(shí)間是相同的。

接下來是這兩種方案的實(shí)現(xiàn)細(xì)節(jié)：

考慮到兩種算法都需要遍歷空閑內(nèi)存區(qū)域，可以使用雙鏈表結(jié)構(gòu)管理空閑內(nèi)存區(qū)域，鏈表節(jié)點(diǎn)為空閑內(nèi)存區(qū)域的控制信息，這樣就可以通過遍歷鏈表尋找可用內(nèi)存區(qū)域，效率較高實(shí)現(xiàn)也較為容易。鏈表節(jié)點(diǎn)可以設(shè)計(jì)成如下形式：

struct NodeInfo {

NodeInfo *prev; // 空閑節(jié)點(diǎn)鏈表中的前一個(gè)節(jié)點(diǎn)

NodeInfo *next; // 空閑節(jié)點(diǎn)鏈表中的后一個(gè)節(jié)點(diǎn)

NodeInfo *preNode; // 指向前一個(gè)結(jié)點(diǎn)，該字段在合并內(nèi)存時(shí)使用

uint32_t sizeAndFlag; // 存儲(chǔ)內(nèi)存結(jié)點(diǎn)的大小和使用標(biāo)記

}

上述結(jié)構(gòu)中的prev和next指針成員只有在空閑節(jié)點(diǎn)中才有效，因此對(duì)于已被使用的節(jié)點(diǎn)，這兩個(gè)字段可以用來存儲(chǔ)其他信息，如申請(qǐng)內(nèi)存的任務(wù)ID、內(nèi)存申請(qǐng)函數(shù)的調(diào)用者地址（可通過LR寄存器獲取）等。sizeAndFlag字段是用來記錄內(nèi)存節(jié)點(diǎn)大小以及是否被使用的標(biāo)記，可以在發(fā)生內(nèi)存問題時(shí)用于分析內(nèi)存映像。preNode字段在釋放內(nèi)存節(jié)點(diǎn)后用于合并空閑節(jié)點(diǎn)。

無論是首次適配還是最佳適配，直接遍歷空閑內(nèi)存節(jié)點(diǎn)鏈表的效率都不高。為了降低遍歷鏈表帶來的時(shí)間開銷，在實(shí)現(xiàn)過程中可以分組管理空閑內(nèi)存節(jié)點(diǎn)。如圖2所示，構(gòu)建一個(gè)數(shù)組存儲(chǔ)雙向鏈表的表頭，每一個(gè)數(shù)組元素中只存儲(chǔ)某個(gè)大小范圍內(nèi)的空閑內(nèi)存節(jié)點(diǎn)，如下標(biāo)為m的元素存儲(chǔ)的節(jié)點(diǎn)大小都在2m到2m+1之間。當(dāng)需要申請(qǐng)大小為n字節(jié)的內(nèi)存空間時(shí)，直接在?log2n?個(gè)雙向鏈表中搜索即可，這樣就可以進(jìn)一步提升搜索效率。

采用圖2中的形式管理內(nèi)存的首次/最佳分配算法描述如下：

當(dāng)用戶釋放內(nèi)存時(shí)，可以將釋放的內(nèi)存插入對(duì)應(yīng)的空閑內(nèi)存節(jié)點(diǎn)鏈表中，并將節(jié)點(diǎn)狀態(tài)改為空閑。由于這些內(nèi)存節(jié)點(diǎn)在空間中是連續(xù)的，所以當(dāng)釋放節(jié)點(diǎn)時(shí)，可以檢查地址p+k是否在內(nèi)存池中。如果p+k指向的地址是另一個(gè)空閑節(jié)點(diǎn)，那么可以將該節(jié)點(diǎn)與用戶釋放的節(jié)點(diǎn)進(jìn)行合并，從而整理內(nèi)存。

對(duì)于首次適配和最佳適配這類需要遍歷空閑內(nèi)存節(jié)點(diǎn)的方案，它們的搜索時(shí)間依賴空閑節(jié)點(diǎn)的數(shù)量，這類方案的響應(yīng)時(shí)間不確定，這種不確定性導(dǎo)致這些方案在嵌入式實(shí)時(shí)系統(tǒng)中使用時(shí)可能造成問題[4]。

（三）TLSF

TLSF，即Two-Level Segregated Fit，也是一種內(nèi)存分配算法，與上文中提到的方案相比具有響應(yīng)時(shí)間上界較小且波動(dòng)不大的特點(diǎn)。該算法的設(shè)計(jì)目標(biāo)是降低最壞情況下的內(nèi)存分配時(shí)間、縮短任意內(nèi)存分配時(shí)間以及減少內(nèi)存碎片和浪費(fèi)[5]。

TLSF算法通過使用兩級(jí)數(shù)組來管理空閑節(jié)點(diǎn)。第一級(jí)數(shù)組將空閑節(jié)點(diǎn)按照指數(shù)大小進(jìn)行劃分，每個(gè)桶表示一組不同大小的空閑節(jié)點(diǎn)。第二級(jí)數(shù)組將每個(gè)桶內(nèi)的空閑節(jié)點(diǎn)按照線性大小進(jìn)行劃分，以進(jìn)一步細(xì)分大小。其基本結(jié)構(gòu)如圖3所示。

圖3中Free nodes中的第一個(gè)鏈表節(jié)點(diǎn)大小在24到24+4之間，第二個(gè)鏈表節(jié)點(diǎn)大小在214+212到214+2×212之間。在該算法中維護(hù)兩級(jí)bitmap，用于指示空閑內(nèi)存節(jié)點(diǎn)所在的位置，用于提高搜索效率。

使用這種結(jié)構(gòu)可以快速計(jì)算出所需空閑節(jié)點(diǎn)的位置，并且可以根據(jù)Bitmap的值確定對(duì)應(yīng)位置是否存在空閑節(jié)點(diǎn)可用。假設(shè)用戶需要申請(qǐng)size字節(jié)內(nèi)存空間，Second level中將內(nèi)存結(jié)點(diǎn)大小按照2SLI間隔進(jìn)行劃分，可以快速計(jì)算出空閑結(jié)點(diǎn)的First level索引為f=?log2size?，Second level索引為（size-2f）×2SLI/2f，根據(jù)設(shè)計(jì)，對(duì)應(yīng)鏈表中的節(jié)點(diǎn)都滿足條件，因此直接返回第一個(gè)節(jié)點(diǎn)的首地址，和前文中的首次適配和最佳適配算法一樣，如果節(jié)點(diǎn)太大，則需要分割節(jié)點(diǎn)，剩下的那部分空間，計(jì)算其First level和Second level索引值，然后直接插入對(duì)應(yīng)鏈表。TLSF算法步驟如表2所示。

對(duì)于TLSF算法，也可以將內(nèi)存節(jié)點(diǎn)的結(jié)構(gòu)設(shè)計(jì)成上節(jié)最佳適配中的形式，維護(hù)相鄰空閑節(jié)點(diǎn)指針以及指向前一個(gè)內(nèi)存節(jié)點(diǎn)的指針。用戶釋放內(nèi)存時(shí)，根據(jù)實(shí)際情況將釋放的內(nèi)存和內(nèi)存池中的內(nèi)存節(jié)點(diǎn)進(jìn)行合并，由于節(jié)點(diǎn)中存儲(chǔ)了節(jié)點(diǎn)大小，節(jié)點(diǎn)首地址加上節(jié)點(diǎn)大小就可以獲取下一個(gè)相鄰內(nèi)存節(jié)點(diǎn)，同時(shí)使用節(jié)點(diǎn)結(jié)構(gòu)中的前一個(gè)節(jié)點(diǎn)指針也可以獲取前一個(gè)節(jié)點(diǎn)信息，如果前一個(gè)或后一個(gè)節(jié)點(diǎn)是空閑的，就可以執(zhí)行節(jié)點(diǎn)合并操作。申請(qǐng)和釋放內(nèi)存時(shí)可以通過計(jì)算直接獲取節(jié)點(diǎn)位置，因此TLSF算法的時(shí)間復(fù)雜度O （1），優(yōu)于首次適配和最佳適配。TLSF算法擁有較小的響應(yīng)時(shí)間上界，更適合實(shí)時(shí)系統(tǒng)。

在上文描述的算法中，可能會(huì)產(chǎn)生較大的內(nèi)存碎片，如果要使內(nèi)存碎片最小，則需進(jìn)行遍歷鏈表的操作，但這樣會(huì)增加時(shí)間開銷。TLSF算法可以針對(duì)特殊的應(yīng)用場景做出優(yōu)化，例如圖形控件場景或者實(shí)時(shí)視頻處理場景，所需的內(nèi)存大小往往只有幾種特定尺寸，在進(jìn)行二級(jí)數(shù)組劃分時(shí)，可以不采用等值劃分，而是以某些大小的集合進(jìn)行劃分，這樣可以有效減少內(nèi)存分割和合并的次數(shù)，從而減少響應(yīng)時(shí)間。

三、結(jié)束語

本文詳細(xì)分析了嵌入式系統(tǒng)中常用的內(nèi)存池資源分配技術(shù)的特點(diǎn)，并對(duì)各類方法的實(shí)現(xiàn)細(xì)節(jié)做了具體分析。針對(duì)這些方法的特點(diǎn)，也提出了一些改進(jìn)思路以減少響應(yīng)時(shí)間和內(nèi)存碎片的產(chǎn)生。目前各種常用方案都可以根據(jù)具體應(yīng)用做出適當(dāng)?shù)男薷囊越鉀Q內(nèi)存碎片問題和響應(yīng)時(shí)間。但在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況對(duì)方案進(jìn)行修正。

作者單位：羅浩 航空工業(yè)西安航空計(jì)算技術(shù)研究所

參考文獻(xiàn)

[1] 李濤，李慧，谷建華，等.基于ACE的并發(fā)編程模式和池式內(nèi)存分配的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006（01）：26-28.

[2] M. Masmano， I. Ripoll， A. Crespo ，et. TLSF： a new dynamic memory allocator for real-time systems[A]， Proceedings.16th Euromicro Conference on Real-Time Systems[C]. Catania， Italy， 2004： 79-88.

[3] Mark S. Johnstone and Paul R. Wilson. The memory fragmentation problem： solved？[A]. In Proceedings of the 1st international symposium on Memory management （ISMM ‘98）[C]. Association for Computing Machinery， New York， NY， USA， 1998： 26–36.

[4] C. J. Stephenson. New Methods for Dynamic Storage Allocation （Fast Fits）[A]. In Proceedings of the ninth ACM symposium on Operating systems principles[C]. ACM Press. 1983： 30-32.

[5] 王秀虎，張昕偉.基于uCOS-II的TLSF動(dòng)態(tài)內(nèi)存分配算法的應(yīng)用與仿真[J].微型機(jī)與應(yīng)用，2013，32（5）：4-7.