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

文　瑾　王宜懷　柏　祥

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)

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

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

0引言

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

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

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

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

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

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

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

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

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

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

MQX固定大小的內(nèi)存管理算法與μC/OS-II類(lèi)似[10]，通過(guò)_partition_create_at函數(shù)來(lái)創(chuàng)建分區(qū)，該函數(shù)傳入三個(gè)參數(shù)：分區(qū)的起始地址、分區(qū)的大小以及分區(qū)中每個(gè)內(nèi)存塊的大小。MQX中地址按照16字節(jié)進(jìn)行對(duì)齊，將函數(shù)傳入地址進(jìn)行16字節(jié)對(duì)齊之后作為內(nèi)存分區(qū)的起始地址。因?yàn)閮?nèi)存塊大小固定，所以只需通過(guò)計(jì)算即可將整塊分區(qū)劃分成塊。在劃分成塊的同時(shí)使用內(nèi)存塊控制信息中的NEXT_BLOCK_PTR指針將所有的內(nèi)存塊連接起來(lá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ò)程中相關(guān)信息。分區(qū)在創(chuàng)建完成之后其可以分配的內(nèi)存塊大小。

固定大小的內(nèi)存分配管理方式在進(jìn)行內(nèi)存塊分配時(shí)調(diào)用_partition_alloc函數(shù)。首先檢查分區(qū)中是否有可用的空閑內(nèi)存塊，沒(mé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)存申請(qǐng)操作應(yīng)當(dāng)在確定的時(shí)間范圍之內(nèi)，即申請(qǐng)內(nèi)存的最差時(shí)間復(fù)雜度也應(yīng)該是確定的。固定大小的內(nèi)存塊管理方式由其內(nèi)存分配特點(diǎn)可知其分配過(guò)程時(shí)間復(fù)雜度為O(1)，具有較好的實(shí)時(shí)性。

固定大小內(nèi)存塊的釋放與申請(qǐng)過(guò)程相反，在釋放時(shí)調(diào)用_partition_free函數(shù)。首先需驗(yàn)證當(dāng)前任務(wù)是否具有釋放指定內(nèi)存的資格，即通過(guò)比較內(nèi)存塊控制信息中的TASK_ID與通過(guò)內(nèi)核數(shù)據(jù)區(qū)獲取的當(dāng)前的任務(wù)ID是否一致判斷該內(nèi)存塊是否屬于當(dāng)前任務(wù)。如果不屬于再判斷該內(nèi)存是否是系統(tǒng)內(nèi)存塊，兩者都不相等意味著當(dāng)前任務(wù)沒(méi)有權(quán)限釋放此內(nèi)存塊，通過(guò)此機(jī)制保證了內(nèi)存管理的安全性。接著將需要釋放的內(nèi)存塊控制信息更新，再將它插入到空閑鏈表FREE_LIST_PTR的頭部。然后將分區(qū)控制信息中空閑內(nèi)存塊鏈表首指針更新為當(dāng)前釋放的內(nèi)存塊地址達(dá)到釋放此內(nèi)存塊的目的。由此過(guò)程可知固定大小的內(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ù)也就固定下來(lái)。如果任務(wù)需要再次申請(qǐng)內(nèi)存時(shí)，假設(shè)任務(wù)需要求的是與上次創(chuàng)建分區(qū)中大小相同的內(nèi)存塊，若前一次創(chuàng)建分區(qū)時(shí)內(nèi)存塊數(shù)目設(shè)置沒(méi)有存在冗余，需要重新調(diào)用_partition_create_at函數(shù)再次創(chuàng)建分區(qū)；若前一次創(chuàng)建分區(qū)時(shí)將內(nèi)存塊數(shù)目設(shè)置較大，又會(huì)造成內(nèi)存的浪費(fèi)。

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

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

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

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

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

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

對(duì)原有固定大小的內(nèi)存管理算法進(jìn)行改進(jìn)，采用哈希索引表對(duì)內(nèi)存分區(qū)池進(jìn)行索引。用戶(hù)在創(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ù)需要申請(qǐng)內(nèi)存時(shí)，首先按照需要申請(qǐng)的內(nèi)存塊大小通過(guò)散列函數(shù)定位到從哪個(gè)分區(qū)進(jìn)行申請(qǐng)，散列函數(shù)MemPoolLocation主要步驟偽代碼如下所示：

MemPoolLocation (size)

1index <- 31

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

3index <- index-1

4index <- index+1-3

5return index

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

在分配內(nèi)存塊時(shí)也對(duì)MQX原有的固定大小的內(nèi)存塊分配算法做了改進(jìn)。當(dāng)發(fā)現(xiàn)當(dāng)前分區(qū)中可用內(nèi)存塊數(shù)目為零時(shí)便通過(guò)分區(qū)控制信息中NEXT成員獲取下一個(gè)分區(qū)的地址，從下一個(gè)內(nèi)存分區(qū)池進(jìn)行申請(qǐng)內(nèi)存塊。由于NEXT指向的內(nèi)存分區(qū)池中內(nèi)存塊的大小是當(dāng)前內(nèi)存分區(qū)池中內(nèi)存塊大小的2倍，內(nèi)存塊大小必定大于當(dāng)前分區(qū)，避免了在某些情況下可能的內(nèi)存泄露問(wèn)題。對(duì)于所引起的內(nèi)部碎片問(wèn)題由于針對(duì)的小塊內(nèi)存的申請(qǐng)，產(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ù)自己需求申請(qǐng)對(duì)應(yīng)內(nèi)存塊，減少了小塊內(nèi)存的平均申請(qǐng)時(shí)間。

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

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

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

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

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

在MQX啟動(dòng)函數(shù)_mqx中調(diào)用_mem_init函數(shù)初始化內(nèi)存池，申請(qǐng)一大塊連續(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;

//申請(qǐng)內(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)存申請(qǐng)

可變大小的內(nèi)存塊申請(qǐng)策略采用的是最先適應(yīng)算法(First Fit)?？臻e內(nèi)存塊按照內(nèi)存地址順序遞增排列，申請(qǐng)內(nèi)存時(shí)要知道需要申請(qǐng)空閑內(nèi)存塊的大小，該內(nèi)存塊所屬任務(wù)及所屬內(nèi)存池。從POOL_FREE_LIST_PTR開(kāi)始尋找合適大小的內(nèi)存塊，合適大小指的就是找到的第一塊內(nèi)存大小大于等于需求內(nèi)存的內(nèi)存塊。如果當(dāng)前找到的內(nèi)存塊大于所需要的內(nèi)存大小時(shí)，就將該塊內(nèi)存分為2部分，一部分供申請(qǐng)的空間的任務(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)存申請(qǐng)流程如圖3所示。

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

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

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

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

(4) 實(shí)時(shí)性問(wèn)題

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

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

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

實(shí)驗(yàn)針對(duì)小塊內(nèi)存的管理策略，將改進(jìn)的固定大小內(nèi)存分管理算法與MQX原有固定大小內(nèi)存管理算法進(jìn)行比較，應(yīng)用于蘇州大學(xué)飛思卡爾嵌入式中心設(shè)計(jì)的SD-FSL-K60-C評(píng)估板進(jìn)行小塊內(nèi)存申請(qǐng)對(duì)比試驗(yàn)。該評(píng)估板以飛思卡爾公司基于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次測(cè)試，每次測(cè)試分別進(jìn)行完全相同的N次(N<1000)內(nèi)存申請(qǐng)及對(duì)應(yīng)釋放操作。操作順序隨機(jī)，每次申請(qǐng)的內(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)存塊申請(qǐng)和釋放所消耗時(shí)間保持平穩(wěn)，保持常數(shù)級(jí)變化，相比于原有的內(nèi)存管理算法并沒(méi)有過(guò)多的增加。

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

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

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

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

4結(jié)語(yǔ)

本文對(duì)MQX固定大小內(nèi)存管理機(jī)制進(jìn)行分析。在其基礎(chǔ)之上提出一種基于哈希索引表和最先匹配策略相結(jié)合的自適應(yīng)內(nèi)存管理算法，并以ARM Cortex-M4內(nèi)核的32位微控制器K60為硬件平臺(tái)，對(duì)改進(jìn)后的算法進(jìn)行驗(yàn)證。實(shí)驗(yàn)表明，改進(jìn)算法在保證原有內(nèi)存分配算法的高效性的同時(shí)，提高了內(nèi)存塊申請(qǐng)的命中率。因此，改進(jìn)后的算法在小塊內(nèi)存申請(qǐng)較為頻繁的嵌入式系統(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。國(guó)家自然科學(xué)基金項(xiàng)目(60871086)；云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目(2011FZ176)；昆明市物聯(lián)網(wǎng)及泛在工程技術(shù)中心開(kāi)放課題(KMIOTKFKT2015001)。文瑾，副教授，主研領(lǐng)域：嵌入式系統(tǒng)，物聯(lián)網(wǎng)技術(shù)。王宜懷，教授。柏祥，碩士生。

中圖分類(lèi)號(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