1 嵌入式系統(tǒng)中對內存分配的要求

　　①快速性。

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

　?、诳煽啃?。

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

　?、鄹咝?。

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

　　2 靜態(tài)分配與動態(tài)分配

　　究竟應用使用靜態(tài)分配還是動態(tài)分配，一直是嵌入式系統(tǒng)設計中一個爭論不休的總是。當然，最合適的答案是對于不同的系統(tǒng)采用不同的方案。如果是系統(tǒng)對于實時性和可靠性的要求極高（硬實時系統(tǒng)），不能容忍一點延時或者一次分配失敗，當然需要采用靜態(tài)分配方案，也就是在程序編譯時所需要的內存都已經(jīng)分配好了。例如，火星探測器上面的嵌入式系統(tǒng)就必須采用靜態(tài)分配的方案。

　　另外，WindRiver公司的一款專門用于汽車電子和工業(yè)自動化領域的實時操作系統(tǒng) OSEKWorks中就不支持內存的動態(tài)分配。在這樣的應用場合，成本不支持內存的動態(tài)分配。在這樣的應用場合，成本不是優(yōu)先考慮的對象，實時性和可靠性才是必須保證的。當然，采用靜態(tài)分配一個不可避免的總是就是系統(tǒng)失去了靈活性，必須在設計階段就預先知道所需要的內存并對之作出分配;必須在設計階段就預先考慮到所有可能的情況，因為一旦出現(xiàn)沒有考慮到的情況，系統(tǒng)就無法處理。

　　這樣的分配方案必須導致很大的浪費，因為內存分配必須按照最壞情況進行最大的配置，而實際上在運行中可能使用的只是其中的一小部分;而且在硬件平臺不變的情況下，不可能靈活地為系統(tǒng)添加功能，從而使得系統(tǒng)的升級變得困難。 大多數(shù)的系統(tǒng)是硬實時系統(tǒng)和軟實時系統(tǒng)的綜合。也就是說，系統(tǒng)中的一部分任務有嚴格的時限要求，而另一部分只是要求完成得越快越好。

　　按照RMS（Rate Monotoin Scheduling）理論，這樣的系統(tǒng)必須采用搶先式任務調度;而在這樣的系統(tǒng)中，就可以采用動態(tài)內存分配來滿足那一部分可靠性和實時性要求不那么高的任務。采用動態(tài)內存分配的好處就是給設計者很大的靈活性，可以方便地將原來運行于非嵌入式操作系統(tǒng)的程序移植到嵌入式系統(tǒng)中，比如，許多嵌入式系統(tǒng)中使用的網(wǎng)絡協(xié)議棧。如果必須采用靜態(tài)內存分配，移植這樣的協(xié)議棧就會困難得多。另外，采用動態(tài)內存分配可以使設計者在不改變基本的硬件平臺的情況下，比較靈活地調整系統(tǒng)的功能，在系統(tǒng)中各個功能之間作出權衡。例如，可以在支持的VLAN數(shù)和支持的路由條目數(shù)之間作出調整，或者不同的版本支持不同的協(xié)議。

　　說到底，動態(tài)內存分配給了嵌入式系統(tǒng)的程序設計者在比較少的限制和較大的自由。因此，大多數(shù)實時操作系統(tǒng)提供了動態(tài)內存分配接口，例如malloc和free 函數(shù)。

　　3 RTOS提供的內存分配接口

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

　　下面詳細介紹一下我們常用的RTOS——美國風河公司（WindRiver）的VxWorks中采用的內存分配策略。

　　VxWorks的前身就是VRTX，據(jù)說VxWorks的名稱來自make vrtx work。 VxWorks的內存管理函數(shù)存在于2個庫中;memPartLib（緊湊的內存分區(qū)管理器）和memLib（完整的內存分區(qū)管理器）。前者 （memPartLib）提供的工具用于從內存分區(qū)中分配內存塊。該庫包含兩類程序，一類是通用工具創(chuàng)建和管理內存分區(qū)并從這些分區(qū)中分配和管理內存塊; 另一類是標準的malloc/free程序提供與內存分區(qū)的接口。系統(tǒng)內存分區(qū)（其ID為memSysPartId是一個全局變量）在內核初始化時由 usrRoot調用memInit創(chuàng)建。其開始地址為RAM中緊接著VxWorks的BSS段之后，大小為所有空閑內存，如圖1所示。

　　當創(chuàng)建其它分區(qū)時，一般需要先調用malloc從系統(tǒng)內存分區(qū)中分配一段內存才能創(chuàng)建。內存分區(qū)的結構定義為mem_part，包含1個對象標記，1個雙向鏈表管理空閑塊，1個信號量保護該分區(qū)及一些統(tǒng)計信息，如總尺寸、最大塊尺寸、調試選項、已分配的塊數(shù)、已分配的尺寸等。其語句如下： typedef struct mem_part { OBJ_CORE objCore; /*對象標志*/ DL-LIST freeList; /*空閑鏈表*/ SEMAPHORE sem; /*保護分區(qū)的信號量*/ Unsigned totalWords; /*分區(qū)中字（WORD）數(shù)*/ Unsigned minBlockWords; /*以字為單位的最小塊尺寸*/ Unsigned options; /*選項，用于調試或統(tǒng)計*/ /*分配統(tǒng)計*/ unsigned curBlocksAllocated; /*當前分配的塊數(shù)*/ unsigned curWorkdAllocated; /*當前分配的字數(shù)*/ unsigned cumBlockAllocated; /*累積分配的塊數(shù)*/ unsigned cumWordsAllocated; /*累積分配的字數(shù)*/ }PARTITION; 一般系統(tǒng)中只有1個內存分區(qū)，即系統(tǒng)分區(qū)，所有任務所需要的內存直接調用malloc從其中分配。

　　分配采用 First-Fit算法（注意這種算法容易導致大量碎片），通過free釋放的內存將被聚合以形成更大的空閑塊。這就是VxWorks的內存分配機理。分配時可以要求一定的對齊格式。注意，不同的 CPU架構有不同的對齊要求。為了優(yōu)化性能，malloc返回的指針是經(jīng)過對齊的，為此的開銷隨構不同而不同。例如，68K為4字節(jié)對齊，開銷8字節(jié);SPARC為8字節(jié)對齊，開銷12字節(jié);MIPS為16字節(jié)對齊，開銷12字節(jié);I960為16字節(jié)對齊，開銷16字節(jié)。

　　MemLib庫中提供了增強的內存分區(qū)管理工具，并且增加了一些接口，而且可以設置調試選項?？梢詸z測2類錯誤：

　?、賴L試分配太大的內存;

　?、卺尫艃却鏁r發(fā)現(xiàn)壞塊。

　　有4種錯誤處理選項，當發(fā)生錯誤時記錄消息或掛起任務。 但是，使用動態(tài)內存分配malloc/free時要注意到以下幾方面的限制。

　?、僖驗橄到y(tǒng)內存分區(qū)是一種臨界資源，由信號量保護，使用malloc會導致當前調用掛起，因此它不能用于中斷服務程序;

　?、谝驗檫M行內存分配需要執(zhí)行查找算法，其執(zhí)行時間與系統(tǒng)當前的內存使用情況相關，是不確定的，因此對于有規(guī)定時限的操作它是不適宜的;

　?、塾捎诓捎煤唵蔚淖钕绕ヅ渌惴?，容易導致系統(tǒng)中存在大量的內存碎片，降低內存使用效率和系統(tǒng)性能。 針對這種情況，一般在系統(tǒng)設計時采用靜態(tài)分配與動態(tài)分配相結合的方法。也就是對于重要的應用，在系統(tǒng)初始化時分配好所需要的內存。在系統(tǒng)運行過程中不再進行內存的分配/釋放，這樣就避免了因內存的分配釋放帶來的總是。而且在系統(tǒng)初始化，因為沒有內存碎片，對于大的內存塊的需求容易滿足。對于其它的應用，在運行時進行動態(tài)內存分配。尤其是某些應用所要求的大量固定尺寸的小內存塊，這時就可以采用一次分配多次使用的內存分配方案。下面詳細介紹這種內存分配方案及其應用場合。

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

　　在嵌入式系統(tǒng)設計中，經(jīng)常有一些類似于內存數(shù)據(jù)庫的應用。這些應用的特點是在內存中管理一些樹，比如以太網(wǎng)交換機中的MAC地址表、VLAN表等，或者路由器中的路由表。這些樹是由許多相同尺寸的節(jié)點組成的。這樣，就可以每次分配一個大的緩沖池，比如包含多個內存單元的數(shù)組，每個內存單元用于1個節(jié)點。我們用一個空閑鏈表來管理該數(shù)組中的空閑內存單元。每次程序需要分配內存以創(chuàng)建1個新的節(jié)點時，就從空閑鏈表中取1個單元給調用者。程序刪除節(jié)點并釋放內存時，將釋放的內存單元返還給空閑鏈表。如果鏈表中的空閑內存單元取空了，就再次調用malloc從系統(tǒng)內存中分配一個大的內存塊作為新的緩沖池。

　　采用這樣一種方案主要有如下優(yōu)點：

　　①減少了malloc/free的調用次數(shù)，從而降低了風險，減少了碎片;

　　②因為從緩沖池中取一個內存單元是時間確定的（當然，如果緩沖池耗盡從而需要重新調用malloc分配除外），因此它可以用于嚴格時限的場合從而保證實時性;

　?、鬯o用戶以自由來添加一些用于內存分配和釋放的調試函數(shù)以及一些統(tǒng)計功能，更好地監(jiān)測系統(tǒng)中內存的使用情況。

　　這種方案必然涉及到一個緩沖池的結構。

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

　　4.1 Intel交換機驅動程序中內存分配

　　在以Intel的交換芯片為基礎的交換機方案中，因為采用的是軟件地址學習的方式，需要在內存中維護許多數(shù)據(jù)，如MAC地址表的軟拷貝、VLAN表、靜態(tài)單播地址表、組播地址表等。這些表都是由一些樹組成，每個樹由一些固定尺寸的節(jié)點組成。一般每個節(jié)點幾十個字節(jié)，每棵樹的節(jié)點數(shù)是可增長的，少則幾十，最多可到16K個節(jié)點。

　　因此，很適合于采用該方案，具體的實現(xiàn)如下：

　?。?）緩沖池結構 BlockMemMgr typedef struct{ MemSize data_cell_size; /*數(shù)據(jù)單元的尺寸*/ MemSize block_size; /*塊尺寸*/ /*下面的變量為預定義的每個管理器最多包含的塊數(shù)，如64 MAX_BLOCKS_OF_MEM_SIZE*/ Unsigned short blocks_being_used;/*已使用的塊數(shù)*/ Void mem_ptr［PAX_BLOCKS_OF_MEM_SIZE］; /*塊數(shù)組*/ SLList free_data_cells_list; /*空閑鏈表*/ }BlockMemMgr; 結構中的參數(shù)包括：單元尺寸、塊尺寸、已用塊數(shù)、所有塊的地址、空閑鏈表（單向鏈表）。

　　（2）緩沖池的管理函數(shù)

　　◆block_mem_create：創(chuàng)建塊內存管理器，參數(shù)包括內存指針（如為NULL，表示自己分配）、塊尺寸、單元尺寸、返回管理器指針。 過程如下：

　　①檢驗參數(shù)合法性。

　?、趩卧叽?字節(jié)對齊，計算每個塊中的單元數(shù)。對內存指針進行4字節(jié)對齊或者分配內存指針。

　?、鄢跏蓟Y構BlockMemMgr，包括單元尺寸和塊尺寸。設置第1個內存塊的指針。如果內存是外來的，設置塊已用標志（已用為0），表示不能增加塊;否則，已用塊數(shù)設為1。

　?、軇?chuàng)建空閑鏈表，將塊內所有單元添加到鏈表中，最后一個單元處于鏈表的最前面。

　?、莘祷谺lockMemMgr。

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

　?、賲?shù)合法性檢測。

　?、趧h除單向鏈表（設鏈表指針為NULL）。

　?、廴绻麎K是動態(tài)分配的，釋放它們。 ④釋放結構BlockMemMgr。

　　◆block_malloc：從塊內存管理器中分配1個單元

　　◆block_malloc：從塊內存管理器中分配1個單元。參數(shù)為BlockMemMgr，返回數(shù)據(jù)單元指針。

　　①參數(shù)合法性檢測。

　　②判斷空閑鏈表是否為空（是否為NULL）。如果為空，判斷是否可以動態(tài)分配塊，如果不能，返回失敗;如果可以動態(tài)分配塊，則分配1個塊，執(zhí)行與 block_mem_create一樣的操作。

　?、蹚目臻e鏈表中分配第1個單元，返回其指針。 注意這里有一個小技巧，即數(shù)據(jù)單元在空閑時其中存放空閑鏈表的節(jié)點信息，而分配后則存放數(shù)據(jù)內容。

　　◆block_free：釋放1個數(shù)據(jù)單元，返回塊內存管理器。小心不要對1個單元釋放2次。參數(shù)為BlockMemMgr和單元指針。 ①參數(shù)合法性檢測。 ②地址比較，判斷數(shù)據(jù)單元屬于哪個塊。 ③判斷數(shù)據(jù)單元的內容是否為空閑鏈表節(jié)點信息（也就是塊內某單元的地址），從而確定是否為2次釋放。 ④將該數(shù)據(jù)單元插入到空閑鏈表的前面。 ⑤引用該單元的指針設為NULL。 內存管理代碼遵守如下約定：①管理的內存是實際可寫的內存;②分配內存是4字節(jié)或32位對齊;③block_malloc、block_free在中斷級調用是部分安全的，除非BLOCK中已經(jīng)沒有空閑CELL，需要重新調用malloc分配新的BLOCK（而malloc和free就不是安全的，因為其中使用了信號量和搜索算法，容易引起中斷服務程序阻塞）。當然，block_mem_create和block_mem_destroy必須在進程級調用。

　　4.2 TMS中的內存分配

　　TMS是WindRiver公司為可管理式交換機推出的開發(fā)包。它用用IDB來管理各種協(xié)議的數(shù)據(jù)，比如STP和GVRP等。為了支持IDB，它建立了自己的緩沖池管理方案，程序在 bufPoolLib.c中。該程序包含用于緩沖池管理的函數(shù)，這些函數(shù)允許從1個池中分配固定數(shù)目和大小的緩沖區(qū)。通過預先分配一定數(shù)目固定大小的緩沖區(qū)，避免了反復的小的內存塊分配/釋放相關聯(lián)的內存碎片和浪費。既然它從1個單一的塊中分配緩沖池，也比對每一個緩沖區(qū)執(zhí)行1 次分配有更高的空間效率。模塊對每個緩沖區(qū)加上1個標記（MAGIC），釋放時會檢查標記。模塊給用戶提供分配和釋放操作定義回調函數(shù)的能力。這樣可以做到自動的對象創(chuàng)建和解構，同時允許由多個緩沖池分配的成員組成的對象做為1個單一的實體刪除。這類似于C++中自動的對象構建和解構，不過是用C語言并且沒有堆棧分配的負擔。模塊既允許從堆棧中分配緩沖池（通過calloc），也可以在用戶分配的空間中創(chuàng)建它們。模塊用1個單向鏈表來維護未分配的緩沖區(qū)，但不跟蹤已分配的緩沖區(qū)。模塊并不是任務安全的，用戶需要用信號時來保護緩沖池。

　　（1）緩沖池結構 typedef struct { ulong_t magic; /*用于一致性檢測的特殊標記*/ Boolean localAlloc; /*內存是否在創(chuàng)建緩沖區(qū)時分配*/ SL_LIST freeList; /*空閑鏈表*/ Void store; /*緩沖區(qū)指向的內存指針*/ STATUS（*createFn）（void*，ulong_t argl）; /*創(chuàng)建緩沖區(qū)時的回調函數(shù)指針*/ STATUS（*destroyFn）（void*，ulong_targl）;/*釋放緩沖區(qū)時的回調函數(shù)指針*/ Ulong_t argVal;/*回調函數(shù)的參數(shù)*/ } buf_pool_t; 結構中的參數(shù)包括檢查標記MAGIC、是否本地分配、空閑鏈表、內存指針、創(chuàng)建緩沖池的回調函數(shù)指針、釋放時的回調函數(shù)指針、回調函數(shù)參數(shù)。

　　（2）相關函數(shù)

　　◆BufPoolInitializeStorage：分配和初始化存儲區(qū)。參數(shù)包括存儲區(qū)地址（如為NULL，則本地分配）、緩沖區(qū)大小、緩沖區(qū)個數(shù)。

　?、俑鶕?jù)緩沖區(qū)大小和個數(shù)獲得所需的內存大小。

　　②如果指針為NULL，則調用calloc分配內存。設置本地分配標志。

　?、鄢跏蓟瘍却鏋?。

　?、艹跏蓟羔?。分配的內存塊最前面為緩沖池結構buf_pool_t。實際的存儲區(qū)緊隨其后。Buf_pool_t包含參數(shù)檢查標記、是否本地分配、存儲區(qū)地址、分配時回調函數(shù)、釋放時回調函數(shù)、回調函數(shù)變量。此時只設置存儲區(qū)指針。

　　◆BufPoolCreate：創(chuàng)建緩沖池。參數(shù)為內存制止。緩沖區(qū)尺寸和個數(shù)，創(chuàng)建時回調函數(shù)、釋放時回調函數(shù)、回調函數(shù)參數(shù)。

　?、俪叽鐚R。

　?、谡{用bufPoolInitializeStorage初始化內存區(qū)和buf_pool_t結構。

　　③用傳入?yún)?shù)填充buf_pool_t結構。 ④將緩沖區(qū)添加到空閑鏈表中，最后的緩沖區(qū)在最前面。

　　◆BufPoolDestroy：刪除緩沖池。參數(shù)為buf_pool_t指針。

　?、贆z查緩沖池結構中的MAGIC字段是否被個性。

　　②如果是本地分配的則翻放內存區(qū)。

　　◆BufPoolAlloc：從緩沖池中分配一個緩沖區(qū)，參數(shù)為緩沖池結構指針。如果存在空閑緩沖區(qū)，則從空閑鏈表中除并提供給調用者，執(zhí)行創(chuàng)建時回調函數(shù)。如果回調函數(shù)返回錯誤，則將緩沖區(qū)返還給空閑鏈表。

　?、贆z查緩沖池結構中的MAGIC標記是否完好。

　?、趶目臻e鏈表中取出頭一個節(jié)點。

　?、廴绻?jié)點不為空，清空節(jié)點，以其地址為參數(shù)調用回調函數(shù)。

　?、苋绻卣{函數(shù)返回錯誤，則將節(jié)點還給空閑鏈表。 ⑤返回得到空閑緩沖區(qū)地址。

　　◆BufPoolFree：將緩沖區(qū)返回給緩沖池。如果定義了回調函數(shù)，將在歸還緩沖之間調用回調函數(shù)。參數(shù)為緩沖池結構和緩沖區(qū)指針。

　?、倬彌_池MAGIC標記是否完好。

　　②如果定義回調函數(shù)、調用之。如果返回錯誤，則設置錯誤號。

　?、蹖⒕彌_區(qū)添加到空閑鏈表中頭部。

　　注意該函數(shù)有2點：

　?、倩卣{函數(shù)返回錯誤，照樣歸還緩沖區(qū)。

　?、跊]有檢查緩沖區(qū)是否二次釋放，這一點與Intel的驅動程序不同。 另外，TMS的緩沖池沒有BLOCK要領，不需要判斷哪個CELL屬于哪個BLOCK，簡化 了操作。

　　5 小結

　　許多嵌入式應用在RTOS提供的malloc/free的基礎上編寫自己的內存管理方案。編寫這樣的內存管理方案，目的無非有兩個：一是減少對 malloc/free的依賴，從而避免由之帶來的內存碎片、時間不確定等總是;另一個是增強程序的查錯能力，送還內存使用錯誤。對于在嵌入式系統(tǒng)中廣泛存在的數(shù)據(jù)庫類型的內存需求，即分配多個固定尺寸的內存單元的要求，“一閃分配，多次使用”的方案無疑是一種很好的解決之道。文中介紹的2個例子很好地體現(xiàn)了它的優(yōu)越性。