肖蕾　劉克江

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 設(shè)置與使用

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

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

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

3 HeapManager的測試（Test of HeapManager）

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

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

測試結(jié)果表明，HeapManager能實現(xiàn)動態(tài)內(nèi)存管理機(jī)制的所有基本操作，可根據(jù)用戶程序參數(shù)動態(tài)分配合適的空間，具備將相鄰空閑塊合并功能，并且，當(dāng)空閑分區(qū)節(jié)點結(jié)構(gòu)損壞時，HeapManager可以做出相對應(yīng)的處理保持系統(tǒng)穩(wě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ī)工程，2007，33（9）：82-83.

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

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

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