[發明專利]嵌入式系統靜態內存池的分配方法

有效

• 申請號: 201510332442.0
• 申請日: 2015-06-16
• 公開（公告）號: CN104965795B
• 公開（公告）日: 2018-02-27
• 發明（設計）人: 吳廣富;王俊偉;李云;曹儐
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 重慶市恒信知識產權代理有限公司50102
• 代理人: 劉小紅

技術領域

本發明涉及一種靜態內存分配方法，尤其是一種應用于移動終端系統靜態內存池的分配方法。

背景技術

當前嵌入式系統的應用非常廣泛，嵌入式系統受體積、功耗等限制，所集成的內存往往較小，因此在嵌入式系統設計中如何提高內存使用效率成為人們非常關心問題。嵌入式系統一般使用在實時性比較高的場合，一般情況下會集成一個實時操作系統，下面以應用于移動終端(手機終端或衛星終端)的操作系統Nucleus Plus為例進行說明。

Nucleus Plus操作系統是對物理內存進行管理，內存分配分為動態內存分配和靜態內存分配。動態內存分配是從一塊足夠大的內存中動態地分配或回收請求大小內存塊；而靜態內存分配是從已分配好的內存池的單塊內存(各單塊內存大小相等)中的申請一塊內存。在系統初始化過程中，需要根據系統申請靜態內存的情況來確定初始內存池個數M、內存池的單塊內存大小Y以及單塊內存個數L。初始內存池個數越多，內存碎片越少，內存管理也越復雜。在實際嵌入式操作系統中，通常為了靜態內存管理方便，而嚴格控制初始內存池個數，從而造成大量靜態內存碎片，因此需要采用靜態內存池分配算法將系統總內存碎片控制在一定范圍內。

靜態內存池分配方法評估準則為：在內存池個數一定情況下，總內存碎片是否最小。當前靜態內存池分配方法為枚舉法和矢量量化法。枚舉法是：對申請的靜態內存塊X按照從小到大順序排序；根據內存塊X的最小、最大值確定內存池單塊內存大小所有可能值Y，共N個；計算在N個值中取M個內存池的所有組合數；每個組合數可以確定1組內存池，將申請的靜態內存塊X根據在該組內存池按照其單塊內存池大小進行分組，計算各內存池的總內存碎片；當總內存碎片最小時，其對應組合數所確定的M個內存池為最優內存池分配。其計算復雜度為其中N！表示N的階乘。

矢量量化法是首先在申請的靜態內存塊X的最小、最大值之間，隨機選取M個值G，將申請內存塊X按照與G之間距離最小，分為M個內存池；計算每個內存池內所有內存塊與其均值的均方誤差并求和；用各內存池的內存塊均值更新G并再次進行上述計算；當最近兩次迭代得到的內存塊均方誤差和之間的誤差足夠小時，則由G確定的M個內存池作為最終分配的內存池。其計算復雜度與迭代次數有關。

使用枚舉法進行靜態內存池分配可以得到最小的內存碎片值，然而當靜態內存塊X的最大值較大(大于10⁵字節)，內存池個數M較大(大于20)時，其計算復雜度為幾乎不可計算值。使用矢量量化法進行靜態內存分配很難得到較小的總內存碎片值，該方法精度與初始M個內存池分布有關，并且該方法收斂性不好，因此算法精度很難提高。

發明內容

鑒于以上問題，本發明的目的在于提供一種適應于移動終端系統的嵌入式系統靜態內存池分配方法。本方法采用內存池裂變思想進行內存池分配，即通過內存池的逐次裂變，根據內存池的不同裂變方式下總內存碎片最小，選擇最佳的內存池裂變方式，由此將原內存池中的一個內存池裂變為兩個內存池。依次按照上述方式進行內存池裂變，內存池的每次裂變引入一個新內存池，當引入的內存池個數滿足嵌入式系統即終止內存池裂變。本發明算法精度顯著高于矢量量化法，而其算法復雜度僅為O(NM)。

本發明提供的靜態內存池的分配方法為遞推過程，包含以下主要過程：

A.利用嵌入式操作系統統計，當前系統中靜態內存塊個數I及每個靜態內存塊大小X(i)，同時初始化內存池個數M；

B.計算內存池的所有可能邊界值；

C.計算第1個內存池的邊界值；

D.將所述第1個內存池裂變為兩個，并確定第2個內存池的邊界值；

E.將D中得到的所述兩個內存池裂變為三個，并確定第3個內存池的邊界值；

F.逐次進行上述內存池裂變過程，當總內存池個數為M時，則靜態內存池分配過程結束。

進一步的，所述計算內存池的所有可能邊界值，具體為：假定內存池分配的最小單位值為S(其取值范圍為字或字的整數倍)；則內存池的最小邊界值為其中表示向下取整，其最大邊界值為其中表示向上取整；在內存池的最小和最大邊界值之間，以步長S為間隔的所有內存值為內存池的所有可能邊界值，見公式(1)。內存池則由其單塊內存的最大邊界值唯一決定。X(1)表示靜態內存塊大小。

進一步的，所述計算第一個內存池的邊界值，具體為：最大邊界值為第一個內存池的最大邊界值，即所有申請的靜態內存塊都小于或等于該最大邊界值。按照公式(2)計算此時總內存碎片值，即所有申請的靜態內存塊與最大邊界值之差的絕對值并累加。