嵌入式系統中對內存分配（轉帖）

  摘要：實時性、可靠性的要求，使得許多嵌入式應用使用自己的內存管理程序。本文探討嵌入式系統中對內存管理的要求、存在的問題以及可能的解決策略；介紹一種“一次分配，多次使用”的動態內存分配方法，并給出2個例子。

    關鍵詞：嵌入式系統 內存管理 一次分配多次使用

1 嵌入式系統中對內存分配的要求

①快速性。嵌入式系統中對實時性的保證，要求內存分配過程要盡可能地快。因此在嵌入式系統中，不可能采用通用操作系統中復雜而完善的內存分配策略，一般都采用簡單、快速的內存分配方案。當然，對實性要求的程序不同，分配方案也有所不同。例如，VxWorks采用簡單的最先匹配如立即聚合方法；VRTX中采用多個固定尺寸的binning方案。

②可靠性。也就是內存分配的請求必須得到滿足，如果分配失敗可能會帶來災難性的后果。嵌入式系統應用的環境千變萬化，其中有一些是對可靠性要求極高的。比如，汽車的自動駕駛系統中，系統檢測到即將撞車，如果因為內存分配失敗而不能相應的操作，就會發生車毀人亡的事故，這是不能容忍的。

③高效性。內存分配要盡可能地少浪費。不可能為了保證滿足所有的內存分配請求而將內存配置得無限大。一方面，嵌入式系統對成本的要求使得內存在其中只是一種很有限的資源；另一方面，即使不考慮成本的因素，系統有限的空間和有限的板面積決定了可配置的內存容量是很限的。

2 靜態分配與動態分配

究竟應用使用靜態分配還是動態分配，一直是嵌入式系統設計中一個爭論不休的總是。當然，最合適的答案是對于不同的系統采用不同的方案。如果是系統對于實時性和可靠性的要求極高（硬實時系統），不能容忍一點延時或者一次分配失敗，當然需要采用靜態分配方案，也就是在程序編譯時所需要的內存都已經分配好了。例如，火星探測器上面的嵌入式系統就必須采用靜態分配的方案。另外，WindRiver公司的一款專門用于汽車電子和工業自動化領域的實時操作系統OSEKWorks中就不支持內存的動態分配。在這樣的應用場合，成本不支持內存的動態分配。在這樣的應用場合，成本不是優先考慮的對象，實時性和可靠性才是必須保證的。當然，采用靜態分配一個不可避免的總是就是系統失去了靈活性，必須在設計階段就預先知道所需要的內存并對之作出分配；必須在設計階段就預先考慮到所有可能的情況，因為一旦出現沒有考慮到的情況，系統就無法處理。這樣的分配方案必須導致很大的浪費，因為內存分配必須按照最壞情況進行最大的配置，而實際上在運行中可能使用的只是其中的一小部分；而且在硬件平臺不變的情況下，不可能靈活地為系統添加功能，從而使得系統的升級變得困難。

大多數的系統是硬實時系統和軟實時系統的綜合。也就是說，系統中的一部分任務有嚴格的時限要求，而另一部分只是要求完成得越快越好。按照RMS（Rate Monotoin Scheduling）理論，這樣的系統必須采用搶先式任務調度；而在這樣的系統中，就可以采用動態內存分配來滿足那一部分可靠性和實時性要求不那么高的任務。采用動態內存分配的好處就是給設計者很大的靈活性，可以方便地將原來運行于非嵌入式操作系統的程序移植到嵌入式系統中，比如，許多嵌入式系統中使用的網絡協議棧。如果必須采用靜態內存分配，移植這樣的協議棧就會困難得多。另外，采用動態內存分配可以使設計者在不改變基本的硬件平臺的情況下，比較靈活地調整系統的功能，在系統中各個功能之間作出權衡。例如，可以在支持的VLAN數和支持的路由條目數之間作出調整，或者不同的版本支持不同的協議。說到底，動態內存分配給了嵌入式系統的程序設計者在比較少的限制和較大的自由。因此，大多數實時操作系統提供了動態內存分配接口，例如malloc和free函數。

3 RTOS提供的內存分配接口

不同的RTOS由于其不同的定位，采用不同的內存分配策略。例如VRTX中，采用類似于GNU C中由Doug Lea開發的內存分配方案，即Binning算法，系統內存被分成了一些固定尺寸的內存塊的算法，系統內存被分成了一些固定尺寸的內存塊的集合。這種方法的優點是查找速度快而且不會產生內存碎片。但是，它的缺點也很明顯，就是容易造成浪費，因為內存塊的尺寸只有有限個，分配時只能取較大的內存塊來滿足一個較小的需求，累積起來，浪費就很大了；而且操作系統管理這樣一個內存分配表也是一個很大的負擔。

下面詳細介紹一下我們常用的RTOS——美國風河公司（WindRiver）的VxWorks中采用的內存分配策略。VxWorks的前身就是VRTX，據說VxWorks的名稱來自make vrtx work。

VxWorks的內存管理函數存在于2個庫中；memPartLib（緊湊的內存分區管理器）和memLib（完整的內存分區管理器）。前者（memPartLib）提供的工具用于從內存分區中分配內存塊。該庫包含兩類程序，一類是通用工具創建和管理內存分區并從這些分區中分配和管理內存塊；另一類是標準的malloc/free程序提供與內存分區的接口。系統內存分區（其ID為memSysPartId是一個全局變量）在內核初始化時由usrRoot調用memInit創建。其開始地址為RAM中緊接著VxWorks的BSS段之后，大小為所有空閑內存，如圖1所示。

當創建其它分區時，一般需要先調用malloc從系統內存分區中分配一段內存才能創建。內存分區的結構定義為mem_part，包含1個對象標記，1個雙向鏈表管理空閑塊，1個信號量保護該分區及一些統計信息，如總尺寸、最大塊尺寸、調試選項、已分配的塊數、已分配的尺寸等。其語句如下：

typedef struct mem_part {

OBJ_CORE objCore; /*對象標志*/

DL-LIST freeList； /*空閑鏈表*/

SEMAPHORE sem; /*保護分區的信號量*/

Unsigned totalWords； /*分區中字（WORD）數*/

Unsigned minBlockWords; /*以字為單位的最小塊尺寸*/

Unsigned options; /*選項，用于調試或統計*/

/*分配統計*/

unsigned curBlocksAllocated; /*當前分配的塊數*/

unsigned curWorkdAllocated; /*當前分配的字數*/

unsigned cumBlockAllocated； /*累積分配的塊數*/

unsigned cumWordsAllocated； /*累積分配的字數*/

}PARTITION；

一般系統中只有1個內存分區，即系統分區，所有任務所需要的內存直接調用malloc從其中分配。分配采用First-Fit算法（注意這種算法容易導致大量碎片），通過free釋放的內存將被聚合以形成更大的空閑塊。這就是VxWorks的內存分配機理。分配時可以要求一定的對齊格式。注意，不同的CPU架構有不同的對齊要求。為了優化性能，malloc返回的指針是經過對齊的，為此的開銷隨構不同而不同。例如，68K為4字節對齊，開銷8字節；SPARC為8字節對齊，開銷12字節；MIPS為16字節對齊，開銷12字節；I960為16字節對齊，開銷16字節。

MemLib庫中提供了增強的內存分區管理工具，并且增加了一些接口，而且可以設置調試選項。可以檢測2類錯誤：①嘗試分配太大的內存；②釋放內存時發現壞塊。有4種錯誤處理選項，當發生錯誤時記錄消息或掛起任務。

但是，使用動態內存分配malloc/free時要注意到以下幾方面的限制。①因為系統內存分區是一種臨界資源，由信號量保護，使用malloc會導致當前調用掛起，因此它不能用于中斷服務程序；②因為進行內存分配需要執行查找算法，其執行時間與系統當前的內存使用情況相關，是不確定的，因此對于有規定時限的操作它是不適宜的；③由于采用簡單的最先匹配算法，容易導致系統中存在大量的內存碎片，降低內存使用效率和系統性能。

針對這種情況，一般在系統設計時采用靜態分配與動態分配相結合的方法。也就是對于重要的應用，在系統初始化時分配好所需要的內存。在系統運行過程中不再進行內存的分配/釋放，這樣就避免了因內存的分配釋放帶來的總是。而且在系統初始化，因為沒有內存碎片，對于大的內存塊的需求容易滿足。對于其它的應用，在運行時進行動態內存分配。尤其是某些應用所要求的大量固定尺寸的小內存塊，這時就可以采用一次分配多次使用的內存分配方案。下面詳細介紹這種內存分配方案及其應用場合。

4 一次分配多次使用的內存分配方案

在嵌入式系統設計中，經常有一些類似于內存數據庫的應用。這些應用的特點是在內存中管理一些樹，比如以太網交換機中的MAC地址表、VLAN表等，或者路由器中的路由表。這些樹是由許多相同尺寸的節點組成的。這樣，就可以每次分配一個大的緩沖池，比如包含多個內存單元的數組，每個內存單元用于1個節點。我們用一個空閑鏈表來管理該數組中的空閑內存單元。每次程序需要分配內存以創建1個新的節點時，就從空閑鏈表中取1個單元給調用者。程序刪除節點并釋放內存時，將釋放的內存單元返還給空閑鏈表。如果鏈表中的空閑內存單元取空了，就再次調用malloc從系統內存中分配一個大的內存塊作為新的緩沖池。采用這樣一種方案主要有如下優點：①減少了malloc/free的調用次數，從而降低了風險，減少了碎片；②因為從緩沖池中取一個內存單元是時間確定的（當然，如果緩沖池耗盡從而需要重新調用malloc分配除外），因此它可以用于嚴格時限的場合從而保證實時性；③它給用戶以自由來添加一些用于內存分配和釋放的調試函數以及一些統計功能，更好地監測系統中內存的使用情況。

這種方案必然涉及到一個緩沖池的結構。一般緩沖池的結構由以下幾部分組成：單元尺寸、塊尺寸（或者單元數目）、緩沖池指針、空閑鏈表、用于統計和調試的參數等。對緩沖池的操作包括創建緩沖池、釋放緩沖池、從緩沖池中分配1個內存單元、釋放內存單元回緩沖池等。下面舉2個例子說明一下該方案的具體使用情況。

4．1 Intel交換機驅動程序中內存分配

在以Intel的交換芯片為基礎的交換機方案中，因為采用的是軟件地址學習的方式，需要在內存中維護許多數據，如MAC地址表的軟拷貝、VLAN表、靜態單播地址表、組播地址表等。這些表都是由一些樹組成，每個樹由一些固定尺寸的節點組成。一般每個節點幾十個字節，每棵樹的節點數是可增長的，少則幾十，最多可到16K個節點。因此，很適合于采用該方案，具體的實現如下：

（1）緩沖池結構BlockMemMgr

typedef struct{

MemSize data_cell_size; /*數據單元的尺寸*/

MemSize block_size; /*塊尺寸*/

/*下面的變量為預定義的每個管理器最多包含的塊數，如64

MAX_BLOCKS_OF_MEM_SIZE*/

Unsigned short blocks_being_used;/*已使用的塊數*/

Void mem_ptr[PAX_BLOCKS_OF_MEM_SIZE];

/*塊數組*/

SLList free_data_cells_list; /*空閑鏈表*/

}BlockMemMgr;

結構中的參數包括：單元尺寸、塊尺寸、已用塊數、所有塊的地址、空閑鏈表（單向鏈表）。

（2）緩沖池的管理函數

◆block_mem_create：創建塊內存管理器，參數包括內存指針（如為NULL，表示自己分配）、塊尺寸、單元尺寸、返回管理器指針。

過程如下：

①檢驗參數合法性。

②單元尺寸4字節對齊，計算每個塊中的單元數。對內存指針進行4字節對齊或者分配內存指針。

③初始化結構BlockMemMgr，包括單元尺寸和塊尺寸。設置第1個內存塊的指針。如果內存是外來的，設置塊已用標志（已用為0），表示不能增加塊；否則，已用塊數設為1。

④創建空閑鏈表，將塊內所有單元添加到鏈表中，最后一個單元處于鏈表的最前面。

⑤返回BlockMemMgr。

◆block_mem_destroy：解構一個塊內存管理器，釋放它所分配的所有內存，調用者負責外部內存的釋放。參數為BlockMemMgr。返回成功失敗標志。

①參數合法性檢測。

②刪除單向鏈表（設鏈表指針為NULL）。