嵌入式系統(tǒng)內(nèi)存分配的2個(gè)例子資料下載

?1 嵌入式系統(tǒng)中對內(nèi)存分配的要求 ??①快速性。 ??嵌入式系統(tǒng)中對實(shí)時(shí)性的保證，要求內(nèi)存分配過程要盡可能地快。因此在嵌入式系統(tǒng)中，不可能采用通用操作系統(tǒng)中復(fù)雜而完善的內(nèi)存分配策略，一般都采用簡單、快速的內(nèi)存分配方案。當(dāng)然，對實(shí)性要求的程序不同，分配方案也有所不同。例如，VxWorks采用簡單的最先匹配如立即聚合方法;VRTX中采用多個(gè)固定尺寸的binning方案。 ??②可靠性。 ??也就是內(nèi)存分配的請求必須得到滿足，如果分配失敗可能會(huì)帶來災(zāi)難性的后果。嵌入式系統(tǒng)應(yīng)用的環(huán)境千變?nèi)f化，其中有一些是對可靠性要求極高的。比如，汽車的自動(dòng)駕駛系統(tǒng)中，系統(tǒng)檢測到即將撞車，如果因?yàn)閮?nèi)存分配失敗而不能相應(yīng)的操作，就會(huì)發(fā)生車毀人亡的事故，這是不能容忍的。 ??③高效性。 ??內(nèi)存分配要盡可能地少浪費(fèi)。不可能為了保證滿足所有的內(nèi)存分配請求而將內(nèi)存配置得無限大。一方面，嵌入式系統(tǒng)對成本的要求使得內(nèi)存在其中只是一種很有限的資源;另一方面，即使不考慮成本的因素，系統(tǒng)有限的空間和有限的板面積決定了可配置的內(nèi)存容量是很限的。 ??2 靜態(tài)分配與動(dòng)態(tài)分配 ??究竟應(yīng)用使用靜態(tài)分配還是動(dòng)態(tài)分配，一直是嵌入式系統(tǒng)設(shè)計(jì)中一個(gè)爭論不休的總是。當(dāng)然，最合適的答案是對于不同的系統(tǒng)采用不同的方案。如果是系統(tǒng)對于實(shí)時(shí)性和可靠性的要求極高（硬實(shí)時(shí)系統(tǒng)），不能容忍一點(diǎn)延時(shí)或者一次分配失敗，當(dāng)然需要采用靜態(tài)分配方案，也就是在程序編譯時(shí)所需要的內(nèi)存都已經(jīng)分配好了。例如，火星探測器上面的嵌入式系統(tǒng)就必須采用靜態(tài)分配的方案。 ??另外，WindRiver公司的一款專門用于汽車電子和工業(yè)自動(dòng)化領(lǐng)域的實(shí)時(shí)操作系統(tǒng) OSEKWorks中就不支持內(nèi)存的動(dòng)態(tài)分配。在這樣的應(yīng)用場合，成本不支持內(nèi)存的動(dòng)態(tài)分配。在這樣的應(yīng)用場合，成本不是優(yōu)先考慮的對象，實(shí)時(shí)性和可靠性才是必須保證的。當(dāng)然，采用靜態(tài)分配一個(gè)不可避免的總是就是系統(tǒng)失去了靈活性，必須在設(shè)計(jì)階段就預(yù)先知道所需要的內(nèi)存并對之作出分配;必須在設(shè)計(jì)階段就預(yù)先考慮到所有可能的情況，因?yàn)橐坏┏霈F(xiàn)沒有考慮到的情況，系統(tǒng)就無法處理。 ??這樣的分配方案必須導(dǎo)致很大的浪費(fèi)，因?yàn)閮?nèi)存分配必須按照最壞情況進(jìn)行最大的配置，而實(shí)際上在運(yùn)行中可能使用的只是其中的一小部分;而且在硬件平臺(tái)不變的情況下，不可能靈活地為系統(tǒng)添加功能，從而使得系統(tǒng)的升級(jí)變得困難。 大多數(shù)的系統(tǒng)是硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)的綜合。也就是說，系統(tǒng)中的一部分任務(wù)有嚴(yán)格的時(shí)限要求，而另一部分只是要求完成得越快越好。 ??按照RMS（Rate Monotoin Scheduling）理論，這樣的系統(tǒng)必須采用搶先式任務(wù)調(diào)度;而在這樣的系統(tǒng)中，就可以采用動(dòng)態(tài)內(nèi)存分配來滿足那一部分可靠性和實(shí)時(shí)性要求不那么高的任務(wù)。采用動(dòng)態(tài)內(nèi)存分配的好處就是給設(shè)計(jì)者很大的靈活性，可以方便地將原來運(yùn)行于非嵌入式操作系統(tǒng)的程序移植到嵌入式系統(tǒng)中，比如，許多嵌入式系統(tǒng)中使用的網(wǎng)絡(luò)協(xié)議棧。如果必須采用靜態(tài)內(nèi)存分配，移植這樣的協(xié)議棧就會(huì)困難得多。另外，采用動(dòng)態(tài)內(nèi)存分配可以使設(shè)計(jì)者在不改變基本的硬件平臺(tái)的情況下，比較靈活地調(diào)整系統(tǒng)的功能，在系統(tǒng)中各個(gè)功能之間作出權(quán)衡。例如，可以在支持的VLAN數(shù)和支持的路由條目數(shù)之間作出調(diào)整，或者不同的版本支持不同的協(xié)議。 ??說到底，動(dòng)態(tài)內(nèi)存分配給了嵌入式系統(tǒng)的程序設(shè)計(jì)者在比較少的限制和較大的自由。因此，大多數(shù)實(shí)時(shí)操作系統(tǒng)提供了動(dòng)態(tài)內(nèi)存分配接口，例如malloc和free 函數(shù)。 ??3 RTOS提供的內(nèi)存分配接口 ??不同的RTOS由于其不同的定位，采用不同的內(nèi)存分配策略。例如VRTX中，采用類似于GNU C中由Doug Lea開發(fā)的內(nèi)存分配方案，即Binning算法，系統(tǒng)內(nèi)存被分成了一些固定尺寸的內(nèi)存塊的算法，系統(tǒng)內(nèi)存被分成了一些固定尺寸的內(nèi)存塊的集合。這種方法的優(yōu)點(diǎn)是查找速度快而且不會(huì)產(chǎn)生內(nèi)存碎片。但是，它的缺點(diǎn)也很明顯，就是容易造成浪費(fèi)，因?yàn)閮?nèi)存塊的尺寸只有有限個(gè)，分配時(shí)只能取較大的內(nèi)存塊來滿足一個(gè)較小的需求，累積起來，浪費(fèi)就很大了;而且操作系統(tǒng)管理這樣一個(gè)內(nèi)存分配表也是一個(gè)很大的負(fù)擔(dān)。 ??下面詳細(xì)介紹一下我們常用的RTOS——美國風(fēng)河公司（WindRiver）的VxWorks中采用的內(nèi)存分配策略。 ??VxWorks的前身就是VRTX，據(jù)說VxWorks的名稱來自make vrtx work。 VxWorks的內(nèi)存管理函數(shù)存在于2個(gè)庫中;memPartLib（緊湊的內(nèi)存分區(qū)管理器）和memLib（完整的內(nèi)存分區(qū)管理器）。前者 （memPartLib）提供的工具用于從內(nèi)存分區(qū)中分配內(nèi)存塊。該庫包含兩類程序，一類是通用工具創(chuàng)建和管理內(nèi)存分區(qū)并從這些分區(qū)中分配和管理內(nèi)存塊; 另一類是標(biāo)準(zhǔn)的malloc/free程序提供與內(nèi)存分區(qū)的接口。系統(tǒng)內(nèi)存分區(qū)（其ID為memSysPartId是一個(gè)全局變量）在內(nèi)核初始化時(shí)由 usrRoot調(diào)用memInit創(chuàng)建。其開始地址為RAM中緊接著VxWorks的BSS段之后，大小為所有空閑內(nèi)存，如圖1所示。 ??當(dāng)創(chuàng)建其它分區(qū)時(shí)，一般需要先調(diào)用malloc從系統(tǒng)內(nèi)存分區(qū)中分配一段內(nèi)存才能創(chuàng)建。內(nèi)存分區(qū)的結(jié)構(gòu)定義為mem_part，包含1個(gè)對象標(biāo)記，1個(gè)雙向鏈表管理空閑塊，1個(gè)信號(hào)量保護(hù)該分區(qū)及一些統(tǒng)計(jì)信息，如總尺寸、最大塊尺寸、調(diào)試選項(xiàng)、已分配的塊數(shù)、已分配的尺寸等。其語句如下： typedef struct mem_part { OBJ_CORE objCore; /*對象標(biāo)志*/ DL-LIST freeList; /*空閑鏈表*/ SEMAPHORE sem; /*保護(hù)分區(qū)的信號(hào)量*/ Unsigned totalWords; /*分區(qū)中字（WORD）數(shù)*/ Unsigned minBlockWords; /*以字為單位的最小塊尺寸*/ Unsigned options; /*選項(xiàng)，用于調(diào)試或統(tǒng)計(jì)*/ /*分配統(tǒng)計(jì)*/ unsigned curBlocksAllocated; /*當(dāng)前分配的塊數(shù)*/ unsigned curWorkdAllocated; /*當(dāng)前分配的字?jǐn)?shù)*/ unsigned cumBlockAllocated; /*累積分配的塊數(shù)*/ unsigned cumWordsAllocated; /*累積分配的字?jǐn)?shù)*/ }PARTITION; 一般系統(tǒng)中只有1個(gè)內(nèi)存分區(qū)，即系統(tǒng)分區(qū)，所有任務(wù)所需要的內(nèi)存直接調(diào)用malloc從其中分配。 ??分配采用 First-Fit算法（注意這種算法容易導(dǎo)致大量碎片），通過free釋放的內(nèi)存將被聚合以形成更大的空閑塊。這就是VxWorks的內(nèi)存分配機(jī)理。分配時(shí)可以要求一定的對齊格式。注意，不同的 CPU架構(gòu)有不同的對齊要求。為了優(yōu)化性能，malloc返回的指針是經(jīng)過對齊的，為此的開銷隨構(gòu)不同而不同。例如，68K為4字節(jié)對齊，開銷8字節(jié);SPARC為8字節(jié)對齊，開銷12字節(jié);MIPS為16字節(jié)對齊，開銷12字節(jié);I960為16字節(jié)對齊，開銷16字節(jié)。 ?MemLib庫中提供了增強(qiáng)的內(nèi)存分區(qū)管理工具，并且增加了一些接口，而且可以設(shè)置調(diào)試選項(xiàng)?？梢詸z測2類錯(cuò)誤： ??①嘗試分配太大的內(nèi)存; ??②釋放內(nèi)存時(shí)發(fā)現(xiàn)壞塊。 ??有4種錯(cuò)誤處理選項(xiàng)，當(dāng)發(fā)生錯(cuò)誤時(shí)記錄消息或掛起任務(wù)。 但是，使用動(dòng)態(tài)內(nèi)存分配malloc/free時(shí)要注意到以下幾方面的限制。 ??①因?yàn)橄到y(tǒng)內(nèi)存分區(qū)是一種臨界資源，由信號(hào)量保護(hù)，使用malloc會(huì)導(dǎo)致當(dāng)前調(diào)用掛起，因此它不能用于中斷服務(wù)程序; ??②因?yàn)檫M(jìn)行內(nèi)存分配需要執(zhí)行查找算法，其執(zhí)行時(shí)間與系統(tǒng)當(dāng)前的內(nèi)存使用情況相關(guān)，是不確定的，因此對于有規(guī)定時(shí)限的操作它是不適宜的; ??③由于采用簡單的最先匹配算法，容易導(dǎo)致系統(tǒng)中存在大量的內(nèi)存碎片，降低內(nèi)存使用效率和系統(tǒng)性能。 針對這種情況，一般在系統(tǒng)設(shè)計(jì)時(shí)采用靜態(tài)分配與動(dòng)態(tài)分配相結(jié)合的方法。也就是對于重要的應(yīng)用，在系統(tǒng)初始化時(shí)分配好所需要的內(nèi)存。在系統(tǒng)運(yùn)行過程中不再進(jìn)行內(nèi)存的分配/釋放，這樣就避免了因內(nèi)存的分配釋放帶來的總是。而且在系統(tǒng)初始化，因?yàn)闆]有內(nèi)存碎片，對于大的內(nèi)存塊的需求容易滿足。對于其它的應(yīng)用，在運(yùn)行時(shí)進(jìn)行動(dòng)態(tài)內(nèi)存分配。尤其是某些應(yīng)用所要求的大量固定尺寸的小內(nèi)存塊，這時(shí)就可以采用一次分配多次使用的內(nèi)存分配方案。下面詳細(xì)介紹這種內(nèi)存分配方案及其應(yīng)用場合。 ??4 一次分配多次使用的內(nèi)存分配方案 ??在嵌入式系統(tǒng)設(shè)計(jì)中，經(jīng)常有一些類似于內(nèi)存數(shù)據(jù)庫的應(yīng)用。這些應(yīng)用的特點(diǎn)是在內(nèi)存中管理一些樹，比如以太網(wǎng)交換機(jī)中的MAC地址表、VLAN表等，或者路由器中的路由表。這些樹是由許多相同尺寸的節(jié)點(diǎn)組成的。這樣，就可以每次分配一個(gè)大的緩沖池，比如包含多個(gè)內(nèi)存單元的數(shù)組，每個(gè)內(nèi)存單元用于1個(gè)節(jié)點(diǎn)。我們用一個(gè)空閑鏈表來管理該數(shù)組中的空閑內(nèi)存單元。每次程序需要分配內(nèi)存以創(chuàng)建1個(gè)新的節(jié)點(diǎn)時(shí)，就從空閑鏈表中取1個(gè)單元給調(diào)用者。程序刪除節(jié)點(diǎn)并釋放內(nèi)存時(shí)，將釋放的內(nèi)存單元返還給空閑鏈表。如果鏈表中的空閑內(nèi)存單元取空了，就再次調(diào)用malloc從系統(tǒng)內(nèi)存中分配一個(gè)大的內(nèi)存塊作為新的緩沖池。 ??采用這樣一種方案主要有如下優(yōu)點(diǎn)： ??①減少了malloc/free的調(diào)用次數(shù)，從而降低了風(fēng)險(xiǎn)，減少了碎片; ??②因?yàn)閺木彌_池中取一個(gè)內(nèi)存單元是時(shí)間確定的（當(dāng)然，如果緩沖池耗盡從而需要重新調(diào)用malloc分配除外），因此它可以用于嚴(yán)格時(shí)限的場合從而保證實(shí)時(shí)性; ??③它給用戶以自由來添加一些用于內(nèi)存分配和釋放的調(diào)試函數(shù)以及一些統(tǒng)計(jì)功能，更好地監(jiān)測系統(tǒng)中內(nèi)存的使用情況。 ??這種方案必然涉及到一個(gè)緩沖池的結(jié)構(gòu)。 ??一般緩沖池的結(jié)構(gòu)由以下幾部分組成：單元尺寸、塊尺寸（或者單元數(shù)目）、緩沖池指針、空閑鏈表、用于統(tǒng)計(jì)和調(diào)試的參數(shù)等。對緩沖池的操作包括創(chuàng)建緩沖池、釋放緩沖池、從緩沖池中分配1個(gè)內(nèi)存單元、釋放內(nèi)存單元回緩沖池等。下面舉2個(gè)例子說明一下該方案的具體使用情況。 ??4.1 Intel交換機(jī)驅(qū)動(dòng)程序中內(nèi)存分配 ??在以Intel的交換芯片為基礎(chǔ)的交換機(jī)方案中，因?yàn)椴捎玫氖擒浖刂穼W(xué)習(xí)的方式，需要在內(nèi)存中維護(hù)許多數(shù)據(jù)，如MAC地址表的軟拷貝、VLAN表、靜態(tài)單播地址表、組播地址表等。這些表都是由一些樹組成，每個(gè)樹由一些固定尺寸的節(jié)點(diǎn)組成。一般每個(gè)節(jié)點(diǎn)幾十個(gè)字節(jié)，每棵樹的節(jié)點(diǎn)數(shù)是可增長的，少則幾十，最多可到16K個(gè)節(jié)點(diǎn)。 ??因此，很適合于采用該方案，具體的實(shí)現(xiàn)如下： ??（1）緩沖池結(jié)構(gòu) BlockMemMgr typedef struct{ MemSize data_cell_size; /*數(shù)據(jù)單元的尺寸*/ MemSize block_size; /*塊尺寸*/ /*下面的變量為預(yù)定義的每個(gè)管理器最多包含的塊數(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; 結(jié)構(gòu)中的參數(shù)包括：單元尺寸、塊尺寸、已用塊數(shù)、所有塊的地址、空閑鏈表（單向鏈表）。 ??（2）緩沖池的管理函數(shù) ??◆block_mem_create：創(chuàng)建塊內(nèi)存管理器，參數(shù)包括內(nèi)存指針（如為NULL，表示自己分配）、塊尺寸、單元尺寸、返回管理器指針。 過程如下： ??①檢驗(yàn)參數(shù)合法性。 ??②單元尺寸4字節(jié)對齊，計(jì)算每個(gè)塊中的單元數(shù)。對內(nèi)存指針進(jìn)行4字節(jié)對齊或者分配內(nèi)存指針。 ??③初始化結(jié)構(gòu)BlockMemMgr，包括單元尺寸和塊尺寸。設(shè)置第1個(gè)內(nèi)存塊的指針。如果內(nèi)存是外來的，設(shè)置塊已用標(biāo)志（已用為0），表示不能增加塊;否則，已用塊數(shù)設(shè)為1。 ??④創(chuàng)建空閑鏈表，將塊內(nèi)所有單元添加到鏈表中，最后一個(gè)單元處于鏈表的最前面。 ??⑤返回BlockMemMgr。 ??◆block_mem_destroy：解構(gòu)一個(gè)塊內(nèi)存管理器，釋放它所分配的所有內(nèi)存，調(diào)用者負(fù)責(zé)外部內(nèi)存的釋放。參數(shù)為BlockMemMgr。返回成功失敗標(biāo)志。 ??①參數(shù)合法性檢測。 ??②刪除單向鏈表（設(shè)鏈表指針為NULL）。 ??③如果塊是動(dòng)態(tài)分配的，釋放它們。 ④釋放結(jié)構(gòu)BlockMemMgr。 ??◆block_malloc：從塊內(nèi)存管理器中分配1個(gè)單元