嵌入式操作系統MQX內存管理機制分析與改進

文　瑾　王宜懷　柏　祥

1(昆明學院信息技術學院　云南 昆明 650214)2(蘇州大學計算機科學與技術學院　江蘇 蘇州 215006)

?

嵌入式操作系統MQX內存管理機制分析與改進

文瑾1,2王宜懷2*柏祥2

1(昆明學院信息技術學院云南 昆明 650214)2(蘇州大學計算機科學與技術學院江蘇 蘇州 215006)

摘要針對嵌入式實時操作系統MQX(Message Queue eXecutive)中內存管理不夠靈活等問題，提出一種基于哈希索引表和最先匹配策略相結合的自適應內存管理算法，針對不同大小的內存采用不同的內存管理策略。對于小塊內存采用哈希索引表組織，實現內存分區池的常數級定位，并且通過雙向鏈表將分區池緊密聯系提高內存申請的魯棒性；對于大塊內存采用最先適應策略，減少內部碎片的產生，提高內存的利用率。實驗結果表明，改進后的算法在保證MQX原有內存管理算法較高實時性的同時，提高了內存申請的命中率以及內存管理的可靠性。

關鍵詞實時操作系統MQX內存管理哈希索引表最先適應策略

0引言

MQX是飛思卡爾半導體公司在2009年推出的一款其內核精簡、源代碼開放、可裁剪性較強的嵌入式實時操作系統RTOS(Real Time Operating System)[1]，并將MQX移植到其公司推出的CodeFire、Kinetis等系列微控制器中。MQX從1989年誕生至今，已經走過了二十多年的發展歷程。由于支持多任務調度、優先級搶占、快速中斷響應[2]等特點，被廣泛應用于醫療電子、工業控制等領域。

在嵌入式實時操作系統中，內存資源是十分寶貴的，因此必須提供有效的內存管理機制對內存資源進行合理高效的管理，才能提高內存資源的利用率。內存分配的方法主要有兩種：靜態分配和動態分配，考慮到靜態分配相對簡單，靈活性相對于動態分配較差，動態分配因其按需分配的靈活性使得眾多學者對其進行深入研究[3,4]，在現在程序中也被廣泛使用[5]。嵌入式實時操作系統對內存管理的要求主要有以下幾點：

(1) 穩定性，任務的內存申請請求應當盡可能被滿足[6]；

(2) 實時性，內存的申請或者釋放都應該保持在確定的時間范圍之內；

(3) 安全性[7]，內存應該由申請它的任務負責，不能對不是由自己申請的內存進行釋放或者其他操作。

若內存管理存在不足則會導致大量內存碎片的產生，內存碎片分為內部碎片和外部碎片[8]。內部碎片是指已經被分配出去(明確屬于某個任務)卻不能被利用的內存空間，直到此塊內存被該任務釋放系統才可能重新利用此塊內存空間；外部碎片指的是還沒有被分配出去(不屬于任何任務)，但由于太小無法分配給申請內存空間的新任務的內存空閑區域。所以在內存管理中需要對內存碎片進行控制，使得其對內存申請和釋放的干擾降到最低。

在對MQX固定大小的內存管理機制進行剖析的基礎上，針對其內存分配算法存在的問題，提出一種基于哈希索引表和最先匹配策略相結合的自適應內存管理算法，針對不同大小的內存采用不同的內存管理策略。對于小塊內存采用哈希索引表組織，實現內存分區池的常數級定位，并且通過雙向鏈表將分區池緊密聯系提高內存申請的魯棒性；對于大塊內存采用最先適應策略，減少內部碎片的產生，提高內存的利用率，并以飛思卡爾公司基于ARM Cortex-M4內核的32位微控制器MK60N512 VMD100(簡稱K60)為硬件平臺，對改進后算法的有效性進行驗證。

1MQX內存管理機制分析

圖1　系統架構圖

MQX從系統架構上分為三層：用戶層、內核層以及物理層。以內存申請為例，任務調用用戶層接口_partition_alloc申請內存塊，_partition_alloc再其內部調用內核層接口_partition_alloc_internal從空閑內存塊鏈表中申請空閑內存，空閑內存塊鏈表順序不一定按照內存的物理地址順序。程序架構如圖1所示。

MQX固定大小的內存管理算法與μC/OS-II類似[10]，通過_partition_create_at函數來創建分區，該函數傳入三個參數：分區的起始地址、分區的大小以及分區中每個內存塊的大小。MQX中地址按照16字節進行對齊，將函數傳入地址進行16字節對齊之后作為內存分區的起始地址。因為內存塊大小固定，所以只需通過計算即可將整塊分區劃分成塊。在劃分成塊的同時使用內存塊控制信息中的NEXT_BLOCK_PTR指針將所有的內存塊連接起來構成空閑內存塊鏈表。因系統中可能存在多個分區，還需將分區加入到分區鏈表中，分區鏈表在內核數據區中進行維護，內核數據區負責維護MQX在運行過程中相關信息。分區在創建完成之后其可以分配的內存塊大小。

固定大小的內存分配管理方式在進行內存塊分配時調用_partition_alloc函數。首先檢查分區中是否有可用的空閑內存塊，沒有可用內存塊則返回錯誤，若存在可用內存塊，則獲取分區控制信息中的空閑內存塊鏈表首指針FREE_LIST_PTR將空閑內存塊鏈表中第一個空閑內存塊的地址返回。再將FREE_LIST_PTR更新為內存塊控制信息中指向的下一個空閑內存塊，內存管理的實時性要求內存申請操作應當在確定的時間范圍之內，即申請內存的最差時間復雜度也應該是確定的。固定大小的內存塊管理方式由其內存分配特點可知其分配過程時間復雜度為O(1)，具有較好的實時性。

固定大小內存塊的釋放與申請過程相反，在釋放時調用_partition_free函數。首先需驗證當前任務是否具有釋放指定內存的資格，即通過比較內存塊控制信息中的TASK_ID與通過內核數據區獲取的當前的任務ID是否一致判斷該內存塊是否屬于當前任務。如果不屬于再判斷該內存是否是系統內存塊，兩者都不相等意味著當前任務沒有權限釋放此內存塊，通過此機制保證了內存管理的安全性。接著將需要釋放的內存塊控制信息更新，再將它插入到空閑鏈表FREE_LIST_PTR的頭部。然后將分區控制信息中空閑內存塊鏈表首指針更新為當前釋放的內存塊地址達到釋放此內存塊的目的。由此過程可知固定大小的內存塊管理方式中內存塊釋放時間復雜度也為O(1)。

2改進算法的提出及實現

MQX固定大小的內存塊管理方案內存塊分配釋放速度較快，但是存在以下不足：

(1) 分區大小的確定

任務在創建分區時根據自己需求的大小創建內存池，定義其中內存塊的大小以及內存塊的數目。當創建完內存分區池之后這些參數也就固定下來。如果任務需要再次申請內存時，假設任務需要求的是與上次創建分區中大小相同的內存塊，若前一次創建分區時內存塊數目設置沒有存在冗余，需要重新調用_partition_create_at函數再次創建分區；若前一次創建分區時將內存塊數目設置較大，又會造成內存的浪費。

(2) 分區之間相對孤立

當任務在申請內存塊時只會在指定分區申請空閑內存塊。雖然各個內存池被內存分區池控制信息中的成員NEXT和PREV連接起來，但是在進行內存的申請釋放等操作時各個分區之間是沒有聯系的。當任務的內存塊申請得不到滿足時，若該系統對于內存管理的穩定性要求較高，可能會引起災難性的后果。

(3) 大塊內存管理效率低

固定大小的內存管理策略對于小塊內存的申請比較合適，但是由于嵌入式系統中可用內存是有限的。對于大塊內存創建內存分區池受到限制，會導致內存利用率較低，申請的內存塊越大，利用率越低，因此針對大塊內存的管理需要采用另外的解決方案。

為了解決上述問題，對不同大小的內存塊請求采用不同的策略，內存塊大小以1 KB為界限，小塊內存代表小于等于1 KB的內存塊，大塊內存代表大于1 KB的內存塊。

2.1小塊內存管理策略

對原有固定大小的內存管理算法進行改進，采用哈希索引表對內存分區池進行索引。用戶在創建調用_partition_create_at創建分區時首先創建8個區存，每個分區的塊大小分別定為8 B、16 B、32 B依次增加至1 KB。每個內存池中內存塊的數目從512按2的冪次遞減，8個內存分區池共占內存32 KB，初始化之后的分區池結構如圖2所示。

圖2　分區池結構圖

8個內存分區池的首地址存放在指針數組PARTPOOL_STRUCT_PTR MemPool[8]中。當任務需要申請內存時，首先按照需要申請的內存塊大小通過散列函數定位到從哪個分區進行申請，散列函數MemPoolLocation主要步驟偽代碼如下所示：

MemPoolLocation (size)

1index <- 31

2while(!(size & (1 << index)) && (index >= 0))

3index <- index-1

4index <- index+1-3

5return index

通過計算得出左數第一個1的位置，從而獲得所需內存塊數量級。接著得到對應數量級內存塊所在分區的首地址在指針數組MemPool中的位置。使用該方法可以在O(1)時間內確定從哪個內存分區池中申請內存塊。

在分配內存塊時也對MQX原有的固定大小的內存塊分配算法做了改進。當發現當前分區中可用內存塊數目為零時便通過分區控制信息中NEXT成員獲取下一個分區的地址，從下一個內存分區池進行申請內存塊。由于NEXT指向的內存分區池中內存塊的大小是當前內存分區池中內存塊大小的2倍，內存塊大小必定大于當前分區，避免了在某些情況下可能的內存泄露問題。對于所引起的內部碎片問題由于針對的小塊內存的申請，產生內部碎片較小。改進的小塊內存管理策略有以下優點：

(1) 分區大小固定。任務不需要多次調用內存池創建函數，以增加初始化分區時間為代價。創建完成后任務可以根據自己需求申請對應內存塊，減少了小塊內存的平均申請時間。

(2) 增強各個內存分區池之間聯系。當前內存分區池不存在可用內存塊時從下一個內存分區池申請空間，提高了分配策略的靈活性，以較小的內碎片為代價，換來系統的穩定高效運行。

(3) 通過構造哈希表以及散列函數實現根據申請內存塊大小快速定位到對應分區，保持了MQX原有固定大小內存分配的高實時性。

2.2大塊內存管理策略

固定大小的內存管理策略對于小塊內存是合適的，但是針對大塊內存則存在著明顯的不足，會造成內存碎片較大，利用率較低。雖然頻繁對內存進行劃分會對內存分配時間產生影響，但在嵌入式系統中大塊內存的申請并不是很頻繁。因此權衡利弊后針對大塊內存的管理采用可變大小的內存分配策略。

(1) 內存池的創建

在MQX啟動函數_mqx中調用_mem_init函數初始化內存池，申請一大塊連續內存作為內存池。創建內存池時會為每個內存池創建內存池控制信息結構體MEM_POOL_STRUCT，其結構如下：

typedef volatile struct mem_pool_struct

{

void *POOL_ALLOC_START_PTR;

//內存池的起始地址

void *POOL_ALLOC_END_PTR;

//內存池的結束地址

void *POOL_FREE_LIST_PTR;

//空閑內存塊鏈表

void *POOL_ALLOC_PTR;

//申請內存塊時用于遍歷的指針

void *POOL_FREE_PTR;

//釋放內存塊時用于遍歷的指針

} MEM_POOL_STRUCT, * MEM_POOL_STRUCT_PTR;

內存池中的空閑鏈表使用單向鏈表進行管理，在內存池控制信息結構體中成員POOL_FREE_LIST_PTR指向這個空閑鏈表的第一個節點。在每個空閑內存塊的內存塊控制信息結構體中成員NEXTBLOCK指向下一個空閑內存塊的地址。

(2) 可變大小內存申請

可變大小的內存塊申請策略采用的是最先適應算法(First Fit)。空閑內存塊按照內存地址順序遞增排列，申請內存時要知道需要申請空閑內存塊的大小，該內存塊所屬任務及所屬內存池。從POOL_FREE_LIST_PTR開始尋找合適大小的內存塊，合適大小指的就是找到的第一塊內存大小大于等于需求內存的內存塊。如果當前找到的內存塊大于所需要的內存大小時，就將該塊內存分為2部分，一部分供申請的空間的任務使用，被標記為已使用內存塊，剩下的還是作為空閑內存塊鏈接到空閑鏈表中。如果找到的空閑塊是在POOL_FREE_LIST_PTR前面，那么需要重新定義POOL_FREE_LIST_PTR。采用這種方案雖然快，但是這會導致系統在后面不能分配出大塊的內存供其他任務使用。內存申請流程如圖3所示。

圖3　內存申請流程圖

(3) 可變大小內存釋放

可變大小內存釋放的過程比申請過程復雜一些，內存塊釋放流程圖如圖4所示。在釋放時，首先界限內存保護檢查，也就是查看該內存是否屬于當前任務。接著根據該內存塊的地址來決定插入空閑鏈表的具體位置。在插入之前還需要判斷該內存塊前后是否有相鄰的空閑內存塊，按照“先后再前”的原則進行判斷是否需要合并，如果需要合并，則對內存塊控制信息進行更新；如果不需要合并則只需要將該塊插入空閑鏈表中free_list_ptr之后。

圖4　內存釋放流程圖

(4) 實時性問題

在申請和釋放內存塊的操作中是禁止中斷的，但是在申請和釋放內存塊的操作中都需要對空閑鏈表進行遍歷。若存在較多空閑內存塊，遍歷空閑鏈表的時間開銷就顯得比較可觀了。為了保證MQX的高實時性，避免這種情況的發生，在申請內存塊時，在遍歷空閑鏈表的循環中，在每查找完一個空閑塊之后就開中斷查看是否有高優先級的任務需要切換。使用內存池控制信息結構體中的成員變量POOL_ALLOC_PTR保存當前查找位置，切換回來之后將POOL_ALLOC_PTR里面的值重新加載回去繼續執行。從高優先級任務切換回低優先級任務時恢復遍歷位置時重新從空閑鏈表頭開始。在釋放內存塊時操作類似，使用內存池控制信息結構體中的成員變量POOL_FREE_PTR來存儲當前遍歷位置，通過上述方法保證了MQX的高實時性。

3測試結果與分析

在嵌入式系統當中，大部分內存申請都是小塊內存的申請，所以對于小塊內存更具有實時性可靠性的要求。大塊內存的分配釋放時間取決于空閑鏈表的長度，相比于固定內存管理較長，但是其內存利用率較高，而且在嵌入式系統中大塊內存的申請較少，因此可以滿足系統的需求。

實驗針對小塊內存的管理策略，將改進的固定大小內存分管理算法與MQX原有固定大小內存管理算法進行比較，應用于蘇州大學飛思卡爾嵌入式中心設計的SD-FSL-K60-C評估板進行小塊內存申請對比試驗。該評估板以飛思卡爾公司基于ARM Cortex-M4內核的32位微控制器K60[11]作為主控芯片，CPU運行主頻高達100 MHz，擁有512 KB的Flash和128 KB的RAM。

根據改進前后內存管理算進行了400次測試，每次測試分別進行完全相同的N次(N<1000)內存申請及對應釋放操作。操作順序隨機，每次申請的內存塊大小是64 B、128 B、256 B、512 B和1 KB中隨機一種。

圖5(a)是改進后內存管理算法的時間消耗，圖5(b)是MQX原內存管理算法的時間消耗。從圖5可以看出改進后內存管理算法的內存塊申請和釋放所消耗時間保持平穩，保持常數級變化，相比于原有的內存管理算法并沒有過多的增加。

圖5　算法改進前后申請和釋放N次內存的時間消耗對比

表1是測試過程中統計每種類型的內存塊申請次數和失敗次數，得到各種類型的內存塊申請命中率進行對比。

表1　算法改進前后內存申請命中率對比

內存申請的快速性與分配時間呈負相關，可靠性與內存申請命中率是正相關的。由表1中的數據可以看出，在可用內存完全一致的情況下，相比MQX原有的固定大小內存管理算法，改進后的算法在內存塊分配及釋放的時間上與MQX原有內存管理算法并沒有顯著的增加。在保證了內存申請和釋放實時性的同時，使得內存申請命中率得到了很大的提高，提高了內存分配的可靠性。

4結語

本文對MQX固定大小內存管理機制進行分析。在其基礎之上提出一種基于哈希索引表和最先匹配策略相結合的自適應內存管理算法，并以ARM Cortex-M4內核的32位微控制器K60為硬件平臺，對改進后的算法進行驗證。實驗表明，改進算法在保證原有內存分配算法的高效性的同時，提高了內存塊申請的命中率。因此，改進后的算法在小塊內存申請較為頻繁的嵌入式系統中可以得到更好的應用。

參考文獻

[1] Freescale MQX real-time operating system user’s guide Rev.3[EB/OL].http://cache.freescale.com/files/32bit/doc/user_guide/MQXUG.pdf.

[2] 石晶,王宜懷,蘇勇,等.基于ARM Cortex-M4的MQX中斷機制分析與中斷程序框架設計[J].計算機科學,2013,40(6):12-19.

[3] Dominguez A,Udayakumaran S Barua.Heap data allocation to scratch-pad memory in embedded systems[J].Journal of Embedded Computing,2005,1(4):521-540.

[4] Risco-Martin,Jose L,David Atienza,et al.A parallel evolutionary algorithm to optimize dynamic memory managers in embedded systems[J].Parallel Computing,2010,36(10):572-590.

[5] 王振江,武成崗,張兆慶.提高堆數據局部性的動態池分配技術[J].計算機學報,2011,34(4):665-675.

[6] 孫曉輝,王勁林,陳曉.實時系統中的動態內存分配算法[J].計算機工程,2008,34(8):80-81.

[7] 王麗杰,熊光澤,羅蕾.嵌入式RTOS安全保護機制的研究與實現[J].電子科技大學學報,2006,34(5):650-653.

[8] 朱沿旭,尹俊文.一種減少碎片的伙伴算法的改進[J].計算機工程與科學,2008,28(A2):175-176.

[9] Cormen T H,Leiserson C E Rivest,et al.Introduction to algorithms[M].Cambridge:MIT press,2001.

[10] 常鐵原,孫學儒.TBS算法在μC/OS-Ⅱ內存管理中的應用[J].計算機應用與軟件,2012,29(9):261-264.

[11] Freescale.K60 Sub-Family Reference Manual Rev.6[EB/OL].http://cache.freescale.com/files/32 bit/doc/ref_manual/K60P144M 100SF2V2RM.pdf.

收稿日期：2015-01-28。國家自然科學基金項目(60871086)；云南省應用基礎研究計劃項目(2011FZ176)；昆明市物聯網及泛在工程技術中心開放課題(KMIOTKFKT2015001)。文瑾，副教授，主研領域：嵌入式系統，物聯網技術。王宜懷，教授。柏祥，碩士生。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.055

ANALYSIS AND IMPROVEMENT OF MEMORY MANAGEMENT MECHANISM IN EMBEDDED OPERATING SYSTEM MQX

Wen Jin1,2Wang Yihuai2*Bai Xiang2

1(SchoolofInformationTechnology,KunmingUniversity,Kunming650214,Yunnan,China)2(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)

AbstractAiming at the inflexibility of memory management in embedded real-time operating system MQX(Message Queue eXecutive), we propose a self-adaptive memory management algorithm which is based on the combination of hash index table and first-fit strategy, in it different memory management strategies will be applied for different memory size. For memories in small block the hash index table will be adopted to organise them so as to realise constant level positioning of the memory partition pools, and through doubly linked list the partition pools are closely connected to improve the robustness of memory application; For memories in big block the first-fit strategy is adopted to decrease the occurrence of internal fragments and to improve the utilisation of memory. Experimental results show that the improved algorithm improves the hit rate for memory application and the reliability of memory management while maintaining the high real-time property of MQX’s original memory management algorithm.

KeywordsReal-time operating systemMQXMemory managementHash index tableFirst-fit strategy