文　瑾　王宜懷　柏　祥

1(昆明學(xué)院信息技術(shù)學(xué)院　云南 昆明 650214)2(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　江蘇 蘇州 215006)

?

嵌入式操作系統(tǒng)MQX內(nèi)存管理機(jī)制分析與改進(jìn)

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

1(昆明學(xué)院信息技術(shù)學(xué)院云南 昆明 650214)2(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院江蘇 蘇州 215006)

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

關(guān)鍵詞實(shí)時(shí)操作系統(tǒng)MQX內(nèi)存管理哈希索引表最先適應(yīng)策略

0引言

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

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

(1) 穩(wěn)定性，任務(wù)的內(nèi)存申請請求應(yīng)當(dāng)盡可能被滿足[6]；

(2) 實(shí)時(shí)性，內(nèi)存的申請或者釋放都應(yīng)該保持在確定的時(shí)間范圍之內(nèi)；

(3) 安全性[7]，內(nèi)存應(yīng)該由申請它的任務(wù)負(fù)責(zé)，不能對不是由自己申請的內(nèi)存進(jìn)行釋放或者其他操作。

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

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

1MQX內(nèi)存管理機(jī)制分析

圖1　系統(tǒng)架構(gòu)圖

MQX從系統(tǒng)架構(gòu)上分為三層：用戶層、內(nèi)核層以及物理層。以內(nèi)存申請為例，任務(wù)調(diào)用用戶層接口_partition_alloc申請內(nèi)存塊，_partition_alloc再其內(nèi)部調(diào)用內(nèi)核層接口_partition_alloc_internal從空閑內(nèi)存塊鏈表中申請空閑內(nèi)存，空閑內(nèi)存塊鏈表順序不一定按照內(nèi)存的物理地址順序。程序架構(gòu)如圖1所示。

MQX固定大小的內(nèi)存管理算法與μC/OS-II類似[10]，通過_partition_create_at函數(shù)來創(chuàng)建分區(qū)，該函數(shù)傳入三個(gè)參數(shù)：分區(qū)的起始地址、分區(qū)的大小以及分區(qū)中每個(gè)內(nèi)存塊的大小。MQX中地址按照16字節(jié)進(jìn)行對齊，將函數(shù)傳入地址進(jìn)行16字節(jié)對齊之后作為內(nèi)存分區(qū)的起始地址。因?yàn)閮?nèi)存塊大小固定，所以只需通過計(jì)算即可將整塊分區(qū)劃分成塊。在劃分成塊的同時(shí)使用內(nèi)存塊控制信息中的NEXT_BLOCK_PTR指針將所有的內(nèi)存塊連接起來構(gòu)成空閑內(nèi)存塊鏈表。因系統(tǒng)中可能存在多個(gè)分區(qū)，還需將分區(qū)加入到分區(qū)鏈表中，分區(qū)鏈表在內(nèi)核數(shù)據(jù)區(qū)中進(jìn)行維護(hù)，內(nèi)核數(shù)據(jù)區(qū)負(fù)責(zé)維護(hù)MQX在運(yùn)行過程中相關(guān)信息。分區(qū)在創(chuàng)建完成之后其可以分配的內(nèi)存塊大小。

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

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

2改進(jìn)算法的提出及實(shí)現(xiàn)

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

(1) 分區(qū)大小的確定

任務(wù)在創(chuàng)建分區(qū)時(shí)根據(jù)自己需求的大小創(chuàng)建內(nèi)存池，定義其中內(nèi)存塊的大小以及內(nèi)存塊的數(shù)目。當(dāng)創(chuàng)建完內(nèi)存分區(qū)池之后這些參數(shù)也就固定下來。如果任務(wù)需要再次申請內(nèi)存時(shí)，假設(shè)任務(wù)需要求的是與上次創(chuàng)建分區(qū)中大小相同的內(nèi)存塊，若前一次創(chuàng)建分區(qū)時(shí)內(nèi)存塊數(shù)目設(shè)置沒有存在冗余，需要重新調(diào)用_partition_create_at函數(shù)再次創(chuàng)建分區(qū)；若前一次創(chuàng)建分區(qū)時(shí)將內(nèi)存塊數(shù)目設(shè)置較大，又會(huì)造成內(nèi)存的浪費(fèi)。

(2) 分區(qū)之間相對孤立

當(dāng)任務(wù)在申請內(nèi)存塊時(shí)只會(huì)在指定分區(qū)申請空閑內(nèi)存塊。雖然各個(gè)內(nèi)存池被內(nèi)存分區(qū)池控制信息中的成員NEXT和PREV連接起來，但是在進(jìn)行內(nèi)存的申請釋放等操作時(shí)各個(gè)分區(qū)之間是沒有聯(lián)系的。當(dāng)任務(wù)的內(nèi)存塊申請得不到滿足時(shí)，若該系統(tǒng)對于內(nèi)存管理的穩(wěn)定性要求較高，可能會(huì)引起災(zāi)難性的后果。

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

固定大小的內(nèi)存管理策略對于小塊內(nèi)存的申請比較合適，但是由于嵌入式系統(tǒng)中可用內(nèi)存是有限的。對于大塊內(nèi)存創(chuàng)建內(nèi)存分區(qū)池受到限制，會(huì)導(dǎo)致內(nèi)存利用率較低，申請的內(nèi)存塊越大，利用率越低，因此針對大塊內(nèi)存的管理需要采用另外的解決方案。

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

2.1小塊內(nèi)存管理策略

對原有固定大小的內(nèi)存管理算法進(jìn)行改進(jìn)，采用哈希索引表對內(nèi)存分區(qū)池進(jìn)行索引。用戶在創(chuàng)建調(diào)用_partition_create_at創(chuàng)建分區(qū)時(shí)首先創(chuàng)建8個(gè)區(qū)存，每個(gè)分區(qū)的塊大小分別定為8 B、16 B、32 B依次增加至1 KB。每個(gè)內(nèi)存池中內(nèi)存塊的數(shù)目從512按2的冪次遞減，8個(gè)內(nèi)存分區(qū)池共占內(nèi)存32 KB，初始化之后的分區(qū)池結(jié)構(gòu)如圖2所示。

圖2　分區(qū)池結(jié)構(gòu)圖

8個(gè)內(nèi)存分區(qū)池的首地址存放在指針數(shù)組PARTPOOL_STRUCT_PTR MemPool[8]中。當(dāng)任務(wù)需要申請內(nèi)存時(shí)，首先按照需要申請的內(nèi)存塊大小通過散列函數(shù)定位到從哪個(gè)分區(qū)進(jìn)行申請，散列函數(shù)MemPoolLocation主要步驟偽代碼如下所示：

MemPoolLocation (size)

1index <- 31

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

3index <- index-1

4index <- index+1-3

5return index

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

在分配內(nèi)存塊時(shí)也對MQX原有的固定大小的內(nèi)存塊分配算法做了改進(jìn)。當(dāng)發(fā)現(xiàn)當(dāng)前分區(qū)中可用內(nèi)存塊數(shù)目為零時(shí)便通過分區(qū)控制信息中NEXT成員獲取下一個(gè)分區(qū)的地址，從下一個(gè)內(nèi)存分區(qū)池進(jìn)行申請內(nèi)存塊。由于NEXT指向的內(nèi)存分區(qū)池中內(nèi)存塊的大小是當(dāng)前內(nèi)存分區(qū)池中內(nèi)存塊大小的2倍，內(nèi)存塊大小必定大于當(dāng)前分區(qū)，避免了在某些情況下可能的內(nèi)存泄露問題。對于所引起的內(nèi)部碎片問題由于針對的小塊內(nèi)存的申請，產(chǎn)生內(nèi)部碎片較小。改進(jìn)的小塊內(nèi)存管理策略有以下優(yōu)點(diǎn)：

(1) 分區(qū)大小固定。任務(wù)不需要多次調(diào)用內(nèi)存池創(chuàng)建函數(shù)，以增加初始化分區(qū)時(shí)間為代價(jià)。創(chuàng)建完成后任務(wù)可以根據(jù)自己需求申請對應(yīng)內(nèi)存塊，減少了小塊內(nèi)存的平均申請時(shí)間。

(2) 增強(qiáng)各個(gè)內(nèi)存分區(qū)池之間聯(lián)系。當(dāng)前內(nèi)存分區(qū)池不存在可用內(nèi)存塊時(shí)從下一個(gè)內(nèi)存分區(qū)池申請空間，提高了分配策略的靈活性，以較小的內(nèi)碎片為代價(jià)，換來系統(tǒng)的穩(wěn)定高效運(yùn)行。

(3) 通過構(gòu)造哈希表以及散列函數(shù)實(shí)現(xiàn)根據(jù)申請內(nèi)存塊大小快速定位到對應(yīng)分區(qū)，保持了MQX原有固定大小內(nèi)存分配的高實(shí)時(shí)性。

2.2大塊內(nèi)存管理策略

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

(1) 內(nèi)存池的創(chuàng)建

在MQX啟動(dòng)函數(shù)_mqx中調(diào)用_mem_init函數(shù)初始化內(nèi)存池，申請一大塊連續(xù)內(nèi)存作為內(nèi)存池。創(chuàng)建內(nèi)存池時(shí)會(huì)為每個(gè)內(nèi)存池創(chuàng)建內(nèi)存池控制信息結(jié)構(gòu)體MEM_POOL_STRUCT，其結(jié)構(gòu)如下：

typedef volatile struct mem_pool_struct

{

void *POOL_ALLOC_START_PTR;

//內(nèi)存池的起始地址

void *POOL_ALLOC_END_PTR;

//內(nèi)存池的結(jié)束地址

void *POOL_FREE_LIST_PTR;

//空閑內(nèi)存塊鏈表

void *POOL_ALLOC_PTR;

//申請內(nèi)存塊時(shí)用于遍歷的指針

void *POOL_FREE_PTR;

//釋放內(nèi)存塊時(shí)用于遍歷的指針

} MEM_POOL_STRUCT, * MEM_POOL_STRUCT_PTR;

內(nèi)存池中的空閑鏈表使用單向鏈表進(jìn)行管理，在內(nèi)存池控制信息結(jié)構(gòu)體中成員POOL_FREE_LIST_PTR指向這個(gè)空閑鏈表的第一個(gè)節(jié)點(diǎn)。在每個(gè)空閑內(nèi)存塊的內(nèi)存塊控制信息結(jié)構(gòu)體中成員NEXTBLOCK指向下一個(gè)空閑內(nèi)存塊的地址。

(2) 可變大小內(nèi)存申請

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

圖3　內(nèi)存申請流程圖

(3) 可變大小內(nèi)存釋放

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

圖4　內(nèi)存釋放流程圖

(4) 實(shí)時(shí)性問題

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

3測試結(jié)果與分析

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

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

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

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

圖5　算法改進(jìn)前后申請和釋放N次內(nèi)存的時(shí)間消耗對比

表1是測試過程中統(tǒng)計(jì)每種類型的內(nèi)存塊申請次數(shù)和失敗次數(shù)，得到各種類型的內(nèi)存塊申請命中率進(jìn)行對比。

表1　算法改進(jìn)前后內(nèi)存申請命中率對比

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

4結(jié)語

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

參考文獻(xiàn)

[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ī)制分析與中斷程序框架設(shè)計(jì)[J].計(jì)算機(jī)科學(xué),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] 王振江,武成崗,張兆慶.提高堆數(shù)據(jù)局部性的動(dòng)態(tài)池分配技術(shù)[J].計(jì)算機(jī)學(xué)報(bào),2011,34(4):665-675.

[6] 孫曉輝,王勁林,陳曉.實(shí)時(shí)系統(tǒng)中的動(dòng)態(tài)內(nèi)存分配算法[J].計(jì)算機(jī)工程,2008,34(8):80-81.

[7] 王麗杰,熊光澤,羅蕾.嵌入式RTOS安全保護(hù)機(jī)制的研究與實(shí)現(xiàn)[J].電子科技大學(xué)學(xué)報(bào),2006,34(5):650-653.

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

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

[10] 常鐵原,孫學(xué)儒.TBS算法在μC/OS-Ⅱ內(nèi)存管理中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,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。國家自然科學(xué)基金項(xiàng)目(60871086)；云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目(2011FZ176)；昆明市物聯(lián)網(wǎng)及泛在工程技術(shù)中心開放課題(KMIOTKFKT2015001)。文瑾，副教授，主研領(lǐng)域：嵌入式系統(tǒng)，物聯(lián)網(wǎng)技術(shù)。王宜懷，教授。柏祥，碩士生。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼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