嵌入式實時系統內存池技術分析

摘要：在嵌入式實時系統中，內存資源的使用通常要求較小的響應時間，并減少內存碎片的產生。為滿足這些要求，開發者普遍采用內存池技術。通過內存池技術，申請和釋放內存的過程無需系統調用的介入，這提高了執行效率，因此在嵌入式實時系統中被廣泛應用。本文詳細分析了常用的內存池資源管理技術的原理，并探討了它們在實踐中采用的實現方法。同時，總結了它們的優缺點，并根據各自的特點提出了一些有效的改進思路，以改善系統的響應速度并減少內存碎片的生成。

關鍵字：內存池；響應時間；內存碎片

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

一、內存池基本原理

在系統初始化階段，用戶向系統申請一塊內存區域，或者指定一塊DDR區域作為內存池，在運行期間供用戶使用。通過采用特定的管理方式，可以有效管理這塊內存區域。在用戶申請內存時，從這塊內存池中取出指定大小的內存塊，并將其分配給用戶使用。當用戶釋放內存時，將釋放的內存塊合并回內存池。這個過程只需在用戶態操作，無需轉化到內核態，能有效減少時間開銷。使用內存池對內存進行管理的步驟如下[2]：

①初始時刻，內存池中的內存是一整塊內存區域，這塊區域可以通過系統調用向系統申請獲取，或者指定某一段DDR空間作為內存池使用。

②首次申請內存時，直接從初始內存塊中取出一部分使用。

③當需要釋放內存時，需要考慮釋放的內存區域是否可以與內存池中相鄰的內存區域合并。

④如果內存池中有空閑內存區域，再次申請內存時需要尋找合適的內存區域，該步驟涉及一些選取內存區域的策略。

在實際設計內存池時，需要考慮一些關鍵問題，包括搜索可用內存區域的速度、內存碎片的情況，以及采用合適的數據結構管理和維護空閑內存。此外，為了在發生內存問題時能夠高效地定位問題，設計者需要添加一些維護信息以提升系統的可維護性。接下來，文章將結合具體的算法描述這些問題的解決思路。

二、內存池資源分配技術

本節詳細分析首次適配、最佳適配和TLSF三種內存池資源分配技術。

（一）首次適配

首次適配的思想較為簡單，搜索系統中的空閑內存區域，返回第一個滿足條件的空閑內存區域。如圖1所示，淺色區域為空閑內存區，深色區域為使用中的內存區，如果需要申請2字節內存，就可以從左到右遍歷空閑內存區域，找到第一個不小于2字節的空閑區域，圖中場景該方案將返回大小為2.5字節內存區域的首地址。

圖1 首次適配區域圖

由于該算法不關心空閑節點和所需內存大小的適配程度，所以容易產生內存碎片，產生的內存碎片需要使用一定的方法進行管理，否則會對后續內存申請效率產生影響。因此，內存碎片也是嵌入式系統內存管理中需要關注的一個重要問題[3]。

（二）最佳適配

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

接下來是這兩種方案的實現細節：

考慮到兩種算法都需要遍歷空閑內存區域，可以使用雙鏈表結構管理空閑內存區域，鏈表節點為空閑內存區域的控制信息，這樣就可以通過遍歷鏈表尋找可用內存區域，效率較高實現也較為容易。鏈表節點可以設計成如下形式：

struct NodeInfo {

NodeInfo *prev; // 空閑節點鏈表中的前一個節點

NodeInfo *next; // 空閑節點鏈表中的后一個節點

NodeInfo *preNode; // 指向前一個結點，該字段在合并內存時使用

uint32_t sizeAndFlag; // 存儲內存結點的大小和使用標記

}

上述結構中的prev和next指針成員只有在空閑節點中才有效，因此對于已被使用的節點，這兩個字段可以用來存儲其他信息，如申請內存的任務ID、內存申請函數的調用者地址（可通過LR寄存器獲取）等。sizeAndFlag字段是用來記錄內存節點大小以及是否被使用的標記，可以在發生內存問題時用于分析內存映像。preNode字段在釋放內存節點后用于合并空閑節點。

無論是首次適配還是最佳適配，直接遍歷空閑內存節點鏈表的效率都不高。為了降低遍歷鏈表帶來的時間開銷，在實現過程中可以分組管理空閑內存節點。如圖2所示，構建一個數組存儲雙向鏈表的表頭，每一個數組元素中只存儲某個大小范圍內的空閑內存節點，如下標為m的元素存儲的節點大小都在2m到2m+1之間。當需要申請大小為n字節的內存空間時，直接在?log2n?個雙向鏈表中搜索即可，這樣就可以進一步提升搜索效率。

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

當用戶釋放內存時，可以將釋放的內存插入對應的空閑內存節點鏈表中，并將節點狀態改為空閑。由于這些內存節點在空間中是連續的，所以當釋放節點時，可以檢查地址p+k是否在內存池中。如果p+k指向的地址是另一個空閑節點，那么可以將該節點與用戶釋放的節點進行合并，從而整理內存。

對于首次適配和最佳適配這類需要遍歷空閑內存節點的方案，它們的搜索時間依賴空閑節點的數量，這類方案的響應時間不確定，這種不確定性導致這些方案在嵌入式實時系統中使用時可能造成問題[4]。

（三）TLSF

TLSF，即Two-Level Segregated Fit，也是一種內存分配算法，與上文中提到的方案相比具有響應時間上界較小且波動不大的特點。該算法的設計目標是降低最壞情況下的內存分配時間、縮短任意內存分配時間以及減少內存碎片和浪費[5]。

TLSF算法通過使用兩級數組來管理空閑節點。第一級數組將空閑節點按照指數大小進行劃分，每個桶表示一組不同大小的空閑節點。第二級數組將每個桶內的空閑節點按照線性大小進行劃分，以進一步細分大小。其基本結構如圖3所示。

圖3中Free nodes中的第一個鏈表節點大小在24到24+4之間，第二個鏈表節點大小在214+212到214+2×212之間。在該算法中維護兩級bitmap，用于指示空閑內存節點所在的位置，用于提高搜索效率。

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

對于TLSF算法，也可以將內存節點的結構設計成上節最佳適配中的形式，維護相鄰空閑節點指針以及指向前一個內存節點的指針。用戶釋放內存時，根據實際情況將釋放的內存和內存池中的內存節點進行合并，由于節點中存儲了節點大小，節點首地址加上節點大小就可以獲取下一個相鄰內存節點，同時使用節點結構中的前一個節點指針也可以獲取前一個節點信息，如果前一個或后一個節點是空閑的，就可以執行節點合并操作。申請和釋放內存時可以通過計算直接獲取節點位置，因此TLSF算法的時間復雜度O （1），優于首次適配和最佳適配。TLSF算法擁有較小的響應時間上界，更適合實時系統。

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

三、結束語

本文詳細分析了嵌入式系統中常用的內存池資源分配技術的特點，并對各類方法的實現細節做了具體分析。針對這些方法的特點，也提出了一些改進思路以減少響應時間和內存碎片的產生。目前各種常用方案都可以根據具體應用做出適當的修改以解決內存碎片問題和響應時間。但在實際應用中，應根據具體情況對方案進行修正。

作者單位：羅浩 航空工業西安航空計算技術研究所

參考文獻

[1] 李濤，李慧，谷建華，等.基于ACE的并發編程模式和池式內存分配的研究[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動態內存分配算法的應用與仿真[J].微型機與應用，2013，32（5）：4-7.