一種微型嵌入式系統(tǒng)動(dòng)態(tài)內(nèi)存分區(qū)管理機(jī)制的研究

肖蕾　劉克江

摘 要：本文基于現(xiàn)有嵌入式操作系統(tǒng)動(dòng)態(tài)內(nèi)存管理機(jī)制的原理，研究和分析了μC/OS、freeRTOS等多個(gè)微型嵌入式操作系統(tǒng)內(nèi)存管理的優(yōu)缺點(diǎn)，以多平臺(tái)通用、高效率、簡(jiǎn)單易用為目標(biāo)，實(shí)現(xiàn)了一種新的動(dòng)態(tài)內(nèi)存管理機(jī)制，主要適用于不使用操作系統(tǒng)或使用小型操作系統(tǒng)的嵌入式產(chǎn)品中，有效解決了動(dòng)態(tài)內(nèi)存的管理問(wèn)題。

關(guān)鍵詞：嵌入式系統(tǒng)；動(dòng)態(tài)內(nèi)存；內(nèi)存溢出；管理機(jī)制

中圖分類(lèi)號(hào)：TP316.2 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：Based on the principle of existing embedded operating system dynamic memory management mechanism， research and analysis of the advantages and disadvantages of μC/OS，freeRTOS and other micro embedded operating system memory management.In this paper，multi-platform，highly efficient，easy to use as the goal to achieve a new dynamic memory management mechanism， mainly applicable to not use the operating system or the use of small embedded operating system products，the mechanism effectively solves the problem of dynamic memory management.

Keywords：embedded system；dynamic memory；memory overflow；management mechanism

1 引言（Introduction）

嵌入式操作系統(tǒng)內(nèi)核往往提供了動(dòng)態(tài)內(nèi)存分區(qū)管理機(jī)制，基于操作系統(tǒng)移植便可以在應(yīng)用開(kāi)發(fā)時(shí)使用動(dòng)態(tài)內(nèi)存分配，使用動(dòng)態(tài)內(nèi)存分配可避免使用大量?jī)?nèi)存空間，從而使軟件設(shè)計(jì)更加合理。但是有時(shí)由于成本、硬件設(shè)計(jì)或功能需求等因素不需要移植嵌入式操作系統(tǒng)，或者只需使用μC/OS、freeRTOS等微型操作系統(tǒng)內(nèi)核，就會(huì)發(fā)現(xiàn)動(dòng)態(tài)內(nèi)存分區(qū)管理機(jī)制存在著許多不足[1]。μC/OS為了盡可能精簡(jiǎn)代碼和追求更好的實(shí)時(shí)性，其內(nèi)存管理模塊根據(jù)用戶(hù)程序要求把動(dòng)態(tài)內(nèi)存分成多個(gè)分區(qū)，每一個(gè)分區(qū)又分成數(shù)量和大小固定的內(nèi)存塊，內(nèi)存塊數(shù)量和大小在編程時(shí)便已確定不可更改，限制了系統(tǒng)的擴(kuò)展性和靈活性，而且由于μC/OS內(nèi)存管理模塊創(chuàng)建一個(gè)動(dòng)態(tài)內(nèi)存分區(qū)只能提供唯一尺寸的內(nèi)存卡，當(dāng)系統(tǒng)需要不同尺寸時(shí)須創(chuàng)建多個(gè)動(dòng)態(tài)內(nèi)存分區(qū)，這樣便不可避免地加大了系統(tǒng)開(kāi)銷(xiāo)和內(nèi)存浪費(fèi)，且μC/OS不對(duì)回收的內(nèi)存塊進(jìn)行合法性檢查[2，3]。freeRTOS提供的動(dòng)態(tài)內(nèi)存管理方案在動(dòng)態(tài)內(nèi)存回收時(shí)只是將其從小到大排列并不把相鄰的兩塊空閑區(qū)合并成一個(gè)大空閑區(qū)，該方案將可能導(dǎo)致整個(gè)動(dòng)態(tài)內(nèi)存分區(qū)被分割成很多個(gè)細(xì)小的內(nèi)存碎片，同樣，freeRTOS不對(duì)回收的內(nèi)存塊進(jìn)行合法性檢查[4，5]。

針對(duì)上述存在的不足，本文提出一種多平臺(tái)通用、高效率、簡(jiǎn)單易用同時(shí)具有動(dòng)態(tài)內(nèi)存溢出檢測(cè)機(jī)制的微型嵌入式動(dòng)態(tài)內(nèi)存管理機(jī)制HeapManager。

2 HeapManager的實(shí)現(xiàn)（Realization of HeapManager）

本文基于現(xiàn)有嵌入式操作系統(tǒng)動(dòng)態(tài)內(nèi)存管理機(jī)制的原理，研究和分析了多個(gè)微型嵌入式操作系統(tǒng)內(nèi)存管理的優(yōu)缺點(diǎn)，以多平臺(tái)通用、高效率、簡(jiǎn)單易用為目標(biāo)，實(shí)現(xiàn)了一種新的動(dòng)態(tài)內(nèi)存管理機(jī)制方法HeapManager。

2.1 數(shù)據(jù)結(jié)構(gòu)

HeapManager將動(dòng)態(tài)內(nèi)存區(qū)連續(xù)內(nèi)存空間視為一塊空閑分塊，并為每一塊空閑塊建立一個(gè)鏈表節(jié)點(diǎn)以記錄該空閑塊信息，將所有空閑塊鏈表節(jié)點(diǎn)組成一個(gè)空閑分區(qū)鏈表，其鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)類(lèi)型如下：

heapMalloc（）會(huì)檢查自身是否第一次被調(diào)用。在用戶(hù)首次調(diào)用heapMalloc（）時(shí)，heapMalloc（）會(huì)執(zhí)行一次初始化堆分區(qū)建立一個(gè)空閑分區(qū)鏈表。初始化的過(guò)程包括：建立整個(gè)空閑分區(qū)鏈表的起始節(jié)點(diǎn)和終止節(jié)點(diǎn)；將初始節(jié)點(diǎn)的下一個(gè)分區(qū)節(jié)點(diǎn)指向系統(tǒng)動(dòng)態(tài)內(nèi)存堆首地址，初始節(jié)點(diǎn)空閑分區(qū)大小定為0；將終止節(jié)點(diǎn)的下一個(gè)分區(qū)節(jié)點(diǎn)指向NULL，終止節(jié)點(diǎn)空閑分區(qū)大小定為整個(gè)系統(tǒng)動(dòng)態(tài)內(nèi)存堆長(zhǎng)度；建立第一個(gè)空閑分區(qū)節(jié)點(diǎn)并存放于系統(tǒng)動(dòng)態(tài)內(nèi)存堆頂部，將該節(jié)點(diǎn)的下一個(gè)分區(qū)節(jié)點(diǎn)指向終止節(jié)點(diǎn)，定義該節(jié)點(diǎn)空閑分區(qū)大小為整個(gè)系統(tǒng)動(dòng)態(tài)內(nèi)存堆總長(zhǎng)度減去節(jié)點(diǎn)所占空間。

heapMalloc（）被調(diào)用后會(huì)對(duì)參數(shù)wantedSize進(jìn)行檢測(cè)判斷，如果wantedSize不大于系統(tǒng)所剩余空閑空間，則從heapStart指向的空閑空間鏈表開(kāi)始對(duì)比每個(gè)空閑分區(qū)的大小是否大于所申請(qǐng)長(zhǎng)度，直到找到第一個(gè)合適的空閑分區(qū)或者h(yuǎn)eapEnd結(jié)束，再根據(jù)除去用戶(hù)所申請(qǐng)空間的空閑分區(qū)大小決定是否重新創(chuàng)建一個(gè)新空閑分區(qū)節(jié)點(diǎn)，最后更新空閑分區(qū)鏈表并返回所申請(qǐng)內(nèi)存（保留頂部節(jié)點(diǎn)信息）的首地址。

unsigned char heapFree（void*freeBlock）在用戶(hù)程序使用完所申請(qǐng)內(nèi)存空間后釋放該動(dòng)態(tài)內(nèi)存時(shí)被調(diào)用，用戶(hù)調(diào)用時(shí)須傳遞參數(shù)freeBlock指向所釋放內(nèi)存的首地址，函數(shù)結(jié)束后將返回執(zhí)行結(jié)果信息（沒(méi)有錯(cuò)誤返回0）。

heapFree（）被調(diào)用后會(huì)根據(jù)freeBlock指向的地址得到回收空閑分區(qū)的空閑分區(qū)節(jié)點(diǎn)并進(jìn)行檢測(cè)，比較freeBlock所指向的位置是否包含于動(dòng)態(tài)內(nèi)存區(qū)，如果不是則返回錯(cuò)誤，再判斷該空閑分區(qū)節(jié)點(diǎn)結(jié)構(gòu)是否損壞，然后從空閑分區(qū)鏈表heapStart所指向的第一個(gè)空閑分區(qū)開(kāi)始地址對(duì)比，找到該內(nèi)存塊合適的回收位置，進(jìn)行回收操作，在HeapManager中會(huì)根據(jù)回收空間所在位置的不同情況作不同的回收處理。

HeapSizeType heapGetFreeSize（void）函數(shù)被調(diào)用時(shí)返回HeapManager中所?？臻e分區(qū)的總大小，該大小為絕對(duì)空閑區(qū)，即除去空閑分區(qū)節(jié)點(diǎn)所占用后剩下的空間。如果在第一次調(diào)用heapMalloc（）函數(shù)前調(diào)用heapGetFreeSize（）則返回用戶(hù)所設(shè)置的總動(dòng)分區(qū)大小configTotalHeapSize。

2.3 設(shè)置與使用

HeapManager的定位是一個(gè)簡(jiǎn)單易用的微型管理機(jī)制，所以在使用HeapManager時(shí)需要設(shè)置的參數(shù)僅有兩個(gè)，分別是_HEAP_MANAGER_ON_和configTotalHeapSize。

_HEAP_MANAGER_ON_用于定義是否啟用HeapManager。我們將HeapManager的兩個(gè)文件（C文件和H文件）添加到項(xiàng)目工程中，如果將_HEAP_MANAGER_ON_設(shè)置為0則編譯器在編譯時(shí)不會(huì)產(chǎn)生HeapManager代碼，也即關(guān)閉HeapManager。configTotalHeapSize設(shè)置系統(tǒng)用于動(dòng)態(tài)內(nèi)存分區(qū)的總大小。開(kāi)發(fā)人員在使用HeapManager之前須根據(jù)硬件資源為HeapManager劃分一塊configTotalHeapSize大小的內(nèi)存區(qū)作為動(dòng)態(tài)內(nèi)存分區(qū)，該值必須大于一個(gè)空閑分區(qū)節(jié)點(diǎn)的長(zhǎng)度（空閑分區(qū)節(jié)點(diǎn)長(zhǎng)度=平臺(tái)數(shù)據(jù)指針?biāo)伎臻g+HeapSizeType實(shí)際表示空間）。HeapManager會(huì)在用戶(hù)程序申請(qǐng)或釋放動(dòng)態(tài)內(nèi)存空間時(shí)進(jìn)行各種檢測(cè)，如果出現(xiàn)錯(cuò)誤則將該錯(cuò)誤的信息反饋給用戶(hù)程序，開(kāi)發(fā)人員可根據(jù)HeapManager返回的錯(cuò)誤信息在程序中做出相應(yīng)措施。

HeapManager主要以低成本嵌入式產(chǎn)品為應(yīng)用對(duì)象，具有以下特點(diǎn)：簡(jiǎn)單易用，使用HeapManager只需劃分一塊大小合適的內(nèi)存空間即可，只有三個(gè)應(yīng)用接口函數(shù)，全部源代碼不到200行（含注釋?zhuān)?；?dòng)態(tài)內(nèi)存申請(qǐng)采用可變分區(qū)管理的首次適應(yīng)算法，空閑分區(qū)按照地址從低到高排列，每次分配從空閑分區(qū)鏈表的鏈?zhǔn)组_(kāi)始查找滿(mǎn)足要求的分區(qū)；內(nèi)存回收時(shí)對(duì)回收的內(nèi)存塊進(jìn)行嚴(yán)格的合法性檢查，避免了整個(gè)動(dòng)態(tài)內(nèi)存分區(qū)的混亂或崩潰，保證了系統(tǒng)穩(wěn)定性和可靠性；具備將鄰近空閑塊合并成一個(gè)大空閑塊的功能，有利于動(dòng)態(tài)內(nèi)存的高效利用，有效避免了內(nèi)存碎片的產(chǎn)生；HeapManager是一個(gè)完全獨(dú)立的內(nèi)存管理機(jī)制，它可以不依賴(lài)于任何操作系統(tǒng)，獨(dú)立添加到工程中直接調(diào)用接口函數(shù)，也可以通過(guò)修改源代碼代替小型操作系統(tǒng)的內(nèi)存管理機(jī)制；實(shí)現(xiàn)跨平臺(tái)的移植，HeapManager在不同硬件平臺(tái)中使用其空閑鏈表節(jié)點(diǎn)所占的存儲(chǔ)空間會(huì)根據(jù)硬件平臺(tái)自行做出調(diào)整。

3 HeapManager的測(cè)試（Test of HeapManager）

本文以某一應(yīng)用場(chǎng)景為例對(duì)HeapManager進(jìn)行測(cè)試，假設(shè)產(chǎn)品中共運(yùn)行10個(gè)死循環(huán)線程，每個(gè)線程在循環(huán)運(yùn)行過(guò)程中將向動(dòng)態(tài)內(nèi)存區(qū)申請(qǐng)一塊隨機(jī)長(zhǎng)度（1—10個(gè)內(nèi)存單位）的存儲(chǔ)空間，使用完后釋放，另外每個(gè)線程每次運(yùn)行一個(gè)循環(huán)所用時(shí)間也是隨機(jī)的。微處理器或微控制器在同一時(shí)刻只能運(yùn)行一條指令，即同一時(shí)刻只有一個(gè)線程在運(yùn)行，且HeapManager可以在脫離操作系統(tǒng)的基礎(chǔ)上使用。

分析應(yīng)用情景后設(shè)計(jì)的測(cè)試程序如下：定義一個(gè)長(zhǎng)度為10的指針數(shù)組用于存放10個(gè)線程所申請(qǐng)的內(nèi)存塊首地址；從隨機(jī)函數(shù)中取得一個(gè)0—9的隨機(jī)數(shù)，表示現(xiàn)在正在運(yùn)行的其中一個(gè)線程；檢測(cè)對(duì)應(yīng)隨機(jī)數(shù)的指針數(shù)組元素是否已存在申請(qǐng)的內(nèi)存塊首地址，不存在（值為NULL）則表示該線程還沒(méi)申請(qǐng)動(dòng)態(tài)內(nèi)存空間，執(zhí)行步驟4，否則執(zhí)行步驟5；再次從隨機(jī)函數(shù)中取得一個(gè)1—10的隨機(jī)數(shù)作為長(zhǎng)度參數(shù)，并通過(guò)HeapManager提供的接口函數(shù)向動(dòng)態(tài)內(nèi)存區(qū)申請(qǐng)動(dòng)態(tài)內(nèi)存塊，將得到的內(nèi)存塊首地址存放于對(duì)應(yīng)線程的指針數(shù)組中，回步驟2；釋放指針數(shù)組下標(biāo)為所得隨機(jī)數(shù)的元素所對(duì)應(yīng)的內(nèi)存塊，并將該元素值賦為NULL，回步驟2。

測(cè)試結(jié)果表明，HeapManager能實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存管理機(jī)制的所有基本操作，可根據(jù)用戶(hù)程序參數(shù)動(dòng)態(tài)分配合適的空間，具備將相鄰空閑塊合并功能，并且，當(dāng)空閑分區(qū)節(jié)點(diǎn)結(jié)構(gòu)損壞時(shí)，HeapManager可以做出相對(duì)應(yīng)的處理保持系統(tǒng)穩(wěn)定運(yùn)行。

參考文獻(xiàn)（References）

[1] Masmano M，Ripoll I，Real J.Implementation of a Constant-time Dynamic Storage Allocator[J].Software：Practice and Experience，2007，38（10）：995-1026.

[2] 常鐵原.μC/OSII內(nèi)存管理技術(shù)的研究[J].計(jì)算機(jī)工程，2007，33（9）：82-83.

[3] Labrosse J J.邵貝貝，譯.嵌入式實(shí)時(shí)操作系統(tǒng)?C/OS-II（第2版）[M].北京：北京航空航天大學(xué)出版社，2005.

[4] 劉濱.嵌入式操作系統(tǒng)FreeRTOS的原理與實(shí)現(xiàn)[J].單片機(jī)與嵌入式應(yīng)用，2005（7）：8-11.

[5] Richard Barry.USING THE FREERTOS REAL TIME KERNEL[M].2009.