一種嵌入式應(yīng)用的內(nèi)存分配算法

程知敬

摘要??? 傳統(tǒng)嵌入式系統(tǒng)為保障系統(tǒng)的可靠性和實(shí)時(shí)性，大多采用靜態(tài)分配內(nèi)存的方式，導(dǎo)致應(yīng)用開發(fā)的效率低下。本文提出了一種嵌入式應(yīng)用的內(nèi)存分配算法，在經(jīng)典深度優(yōu)先搜索算法的基礎(chǔ)上，結(jié)合自研的內(nèi)存復(fù)用算法——間隔復(fù)用法，實(shí)現(xiàn)自動(dòng)化的應(yīng)用內(nèi)存分配，且使得內(nèi)存利用率得以提升。最后，通過工程實(shí)例驗(yàn)證了其正確性及有效性。

【關(guān)鍵詞】嵌入式系統(tǒng) 內(nèi)存分配算法

1 引言

傳統(tǒng)嵌入式軟件的開發(fā)流程是基于嵌入式集成開發(fā)環(huán)境完成實(shí)時(shí)處理軟件設(shè)計(jì)、編碼、編譯，將編譯后的可執(zhí)行文件下載到嵌入式設(shè)備上進(jìn)行調(diào)試驗(yàn)證。該過程涉及軟、硬件的資源分配，對(duì)軟件設(shè)計(jì)人員提出了較高要求。

為提高軟件開發(fā)效率，基于模型的設(shè)計(jì)方法開始受到廣泛推崇。它始于20世紀(jì)90年代初的汽車制造和航空航天工業(yè);90年代中期，自動(dòng)代碼生成技術(shù)使模型化設(shè)計(jì)方法有了實(shí)用價(jià)值;1984年隨著MathWorks公司的成立，旗下的Simulink/Stateflow、EmbeddedMatlab等產(chǎn)品融合了建模、仿真和分析工具，將軟件開發(fā)流程方式徹底轉(zhuǎn)變?yōu)樵谝粋€(gè)可視化的交互開發(fā)平臺(tái)上進(jìn)行軟件設(shè)計(jì)和開發(fā)，并通過直觀的系統(tǒng)模型進(jìn)行可視化處理。

但對(duì)于有高性能要求的嵌入式軟件，模型仿真不能替代真實(shí)的應(yīng)用場(chǎng)景，因?yàn)榉抡骐y以達(dá)到實(shí)物板卡的運(yùn)行性能。因此，在模型化開發(fā)生成軟件代碼之后，仍必須編譯下載到硬件板卡上運(yùn)行。在嵌入式實(shí)時(shí)系統(tǒng)中運(yùn)行應(yīng)用，其內(nèi)存分配是一個(gè)重點(diǎn)問題。為給系統(tǒng)提供最好的可靠性與實(shí)時(shí)性，在以VxWorks為代表的硬實(shí)時(shí)系統(tǒng)中，一般遵循靜態(tài)內(nèi)存分配的原則，比如預(yù)先申明變量、數(shù)組的內(nèi)存空間等。然而傳統(tǒng)的人工分配方式必然導(dǎo)致整個(gè)系統(tǒng)的開發(fā)效率和自動(dòng)化水平被拉低。

本文提供一種嵌入式應(yīng)用的內(nèi)存分配算法，實(shí)現(xiàn)軟件各應(yīng)用模塊在嵌入式設(shè)備內(nèi)存空間分配的自動(dòng)化，并確保板卡內(nèi)存的高利用率和高復(fù)用率。

2 嵌入式內(nèi)存分配的要求

嵌入式應(yīng)用的拓?fù)浣Y(jié)構(gòu)滿足有向無(wú)環(huán)圖（DAG，Directed Acyclic Graph），應(yīng)用即為圖的頂點(diǎn)，應(yīng)用的執(zhí)行順序是有方向的，且應(yīng)用之間不會(huì)形成圈。

約束條件有二種：

（1）應(yīng)用的內(nèi)存占比，即單一板卡上所有應(yīng)用所需的內(nèi)存（包含運(yùn)算內(nèi)存和通信內(nèi)存）之和不超過板卡的總內(nèi)存，

（2）應(yīng)用的通過率，即所有應(yīng)用所占的時(shí)間耗時(shí)之和不超過系統(tǒng)要求的總通過率。所以該圖還是一個(gè)有權(quán)圖。

經(jīng)典的圖遍歷算法有深度優(yōu)先搜索和廣度優(yōu)先搜索。

深度優(yōu)先搜索算法（DFS，Depth-FirstSearch）是對(duì)先序遍歷的推廣。它是指從圖中某個(gè)未被訪問過的初始頂點(diǎn)v出發(fā)，首先訪問初始頂點(diǎn)v，然后選擇一個(gè)與頂點(diǎn)v相鄰且沒被訪問過的頂點(diǎn)w為初始頂點(diǎn)，再?gòu)膚出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問過為止。若此時(shí)還有其他未被訪問的頂點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。

廣度優(yōu)先搜索算法（BFS，Breadth-First Search）是指從圖中某個(gè)未被訪問過的初始頂點(diǎn)v出發(fā)，首先訪問v的各個(gè)未被訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)還有其他未被訪問的頂點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。

對(duì)于嵌入式應(yīng)用拓?fù)鋱D而言，DFS的優(yōu)點(diǎn)在于可以減少應(yīng)用之間的通信鏈路開銷，但因?yàn)闀?huì)快速達(dá)到通過率上限而浪費(fèi)過多的存儲(chǔ)內(nèi)存;BFS的優(yōu)點(diǎn)在于能最大限度利用板卡內(nèi)的內(nèi)存空間，但多個(gè)鄰接點(diǎn)分支將導(dǎo)致通信鏈路的開銷加大。

因此本算法考慮的內(nèi)存分配目標(biāo)是：

（1）高利用率。對(duì)于嵌入式設(shè)備有限的空間和有限的板面積而言，可配置的內(nèi)存是有限的，因此必須內(nèi)存分配的首要目標(biāo)是保證足夠高的內(nèi)存的利用率，即在有限的硬件資源里運(yùn)行盡可能多的應(yīng)用模塊。

（2）高復(fù)用率?？紤]各應(yīng)用模塊的內(nèi)存能夠盡可能的復(fù)用。但硬實(shí)時(shí)系統(tǒng)不具備資源隔離功能，因此復(fù)用時(shí)必須考慮清楚各模塊的內(nèi)存狀態(tài)以免發(fā)生內(nèi)存意外改寫。

3 通信內(nèi)存的間隔復(fù)用法

應(yīng)用的內(nèi)存按其作用分為兩類，一類是用于通信收發(fā)的內(nèi)存，包括應(yīng)用輸入數(shù)據(jù)的緩存區(qū)和輸出數(shù)據(jù)的緩存區(qū)，另一類是用于應(yīng)用執(zhí)行過程中用到的計(jì)算處理內(nèi)存。后者可能涉及到迭代等需要?dú)v史數(shù)據(jù)的計(jì)算，所以不便考慮內(nèi)存復(fù)用。因此，本算法只考慮通信內(nèi)存的復(fù)用。

為簡(jiǎn)化分析過程，上一級(jí)的輸出緩存區(qū)和下一級(jí)的輸入緩存區(qū)看作一個(gè)整體，即圖1中應(yīng)用1使用通信緩存分區(qū)1輸出數(shù)據(jù)，且應(yīng)用2同樣使用分區(qū)1輸入數(shù)據(jù)。

先考慮最簡(jiǎn)單的串行處理流程，如圖1（a）所示。某包數(shù)據(jù)首先進(jìn)入應(yīng)用1處理，處理完畢后經(jīng)由分區(qū)1發(fā)往應(yīng)用2處理，應(yīng)用2處理完畢后經(jīng)由分區(qū)2發(fā)往應(yīng)用3，此時(shí)分區(qū)1處在空余狀態(tài)，因此應(yīng)用3發(fā)往應(yīng)用4時(shí)可以復(fù)用緩存分區(qū)1。從圖上可以直觀看出，對(duì)于串行結(jié)構(gòu)，可以每間隔兩個(gè)應(yīng)用就可以復(fù)用同一個(gè)緩存分區(qū)，因此將該算法命名為間隔復(fù)用法。

但串并混合的情況下，間隔復(fù)用法有一定限制，如圖1（b）所示。此時(shí)應(yīng)用2輸出兩種不同的內(nèi)容，一種仍是通過分區(qū)2發(fā)往應(yīng)用3，另一種則是經(jīng)過分區(qū)3分別發(fā)給應(yīng)用5和應(yīng)用6。根據(jù)圖中的鏈接關(guān)系可知，應(yīng)用6開始處理數(shù)據(jù)的時(shí)間必然在應(yīng)用2和應(yīng)用5的處理之后。因此對(duì)于分區(qū)3的一發(fā)多收情況，不能使用間隔復(fù)用。

綜合考慮各種鏈路分支情況，間隔復(fù)用算法的規(guī)則定義如下：

如果應(yīng)用模塊A有相連的前一級(jí)應(yīng)用模塊B，模塊B有相連的前一級(jí)應(yīng)用模塊C，且模塊B的輸入滿足：

（1）該輸入不是模塊C的多個(gè)相同的輸出分支之一;

（2）該輸入不會(huì)發(fā)送給模塊A的下一級(jí)模塊;

（3）該輸入不被用于其他與模塊A相連的前一級(jí)模塊的輸出。

則應(yīng)用模塊A的輸出內(nèi)存區(qū)可以復(fù)用其前一級(jí)應(yīng)用模塊B的輸入內(nèi)存區(qū)。

4 嵌入式內(nèi)存分配算法

依據(jù)上述嵌入式內(nèi)存分配的要求，本算法考慮在DFS的基礎(chǔ)上，結(jié)合內(nèi)存復(fù)用算法實(shí)現(xiàn)內(nèi)存的高利用率和復(fù)用率。算法描述如下（圖2）：

步驟一，通過DFS搜索應(yīng)用拓?fù)鋱D，其約束為：

（1）已搜索到的應(yīng)用的總通過率不超過系統(tǒng)通過率;

（2）已搜索到的應(yīng)用的占用內(nèi)存之和不超過單一板卡的總內(nèi)存。

如果本次搜索后有新增應(yīng)用，轉(zhuǎn)到步驟二;否則算法結(jié)束。

步驟二，使用間隔復(fù)用法對(duì)步驟一分配后的應(yīng)用進(jìn)行判定，如有可復(fù)用的內(nèi)存，轉(zhuǎn)到步驟一在原應(yīng)用分配的基礎(chǔ)上繼續(xù)進(jìn)行DFS搜索;否則算法結(jié)束。

5 應(yīng)用

假設(shè)一塊板卡總的用戶可用內(nèi)存為210M，系統(tǒng)要求的總通過率為11s。應(yīng)用拓?fù)鋱D如圖3所示，圖中每個(gè)應(yīng)用占用內(nèi)存20M，其中運(yùn)算內(nèi)存16M，通信內(nèi)存4M，所以如果直接分配，最多可以在該板卡上分配10個(gè)應(yīng)用;應(yīng)用中標(biāo)明的數(shù)字表示各自的通過率，本例中即便在板卡上分配所有應(yīng)用，總的通過率仍滿足系統(tǒng)要求;各應(yīng)用之間的連接符，如果有以數(shù)字標(biāo)明區(qū)別，表示輸出的數(shù)據(jù)內(nèi)容不同。

按照算法流程，首先按照DFS搜索拓?fù)鋱D，搜索到的應(yīng)用順序?yàn)椋?-2-3-7-8-9-6-10-5-4，如圖4（a）所示，此時(shí)用戶內(nèi)存只余10M，不足以再分配給其他應(yīng)用，DFS搜索結(jié)束;其次，采用分隔復(fù)用法對(duì)圖4（a）中應(yīng)用的通信內(nèi)存進(jìn)行復(fù)用，結(jié)果如圖4（b）所示，復(fù)用了2次分區(qū)1、1次分區(qū)2、1次分區(qū)5，共節(jié)省通信內(nèi)存16M;然后，由于此時(shí)空余內(nèi)存共計(jì)26M，支持再分配一個(gè)應(yīng)用，因此將搜索到的應(yīng)用11加入到分配列表中;最后，對(duì)應(yīng)用11所使用的通信內(nèi)存進(jìn)行復(fù)用考慮，但應(yīng)用11本來(lái)就與應(yīng)用5公用分區(qū)4，不符合間隔復(fù)用條件，結(jié)果如圖4（c）所示，算法結(jié)束。至此，拓?fù)鋱D的11個(gè)應(yīng)用都部署在了同一塊板卡。

由本例可見，該算法在傳統(tǒng)DFS搜索結(jié)果的基礎(chǔ)上進(jìn)行優(yōu)化，使得單板可分配的應(yīng)用數(shù)從10個(gè)增長(zhǎng)到11個(gè)。對(duì)于通信數(shù)據(jù)龐大的應(yīng)用而言，能夠復(fù)用的空間更多，效果更佳。

6 結(jié)束語(yǔ)

本文提出了一種嵌入式應(yīng)用的內(nèi)存分配算法，結(jié)合深度優(yōu)先搜素算法和通信內(nèi)存的間隔復(fù)用算法，解決了軟件各應(yīng)用模塊在嵌入式設(shè)備內(nèi)存空間分配的自動(dòng)化問題，并確保板卡內(nèi)存的高利用率和高復(fù)用率。但如果想達(dá)到靜態(tài)分配方法的最優(yōu)解，還需要解決運(yùn)算內(nèi)存的復(fù)用問題。

參考文獻(xiàn)

[1]劉杰.基于模型的設(shè)計(jì)及其嵌入式實(shí)現(xiàn)[D].北京航空航天大學(xué)出版社，2010.

[2]劉小軍，李秀娟.嵌入式操作系統(tǒng)VxWorks的內(nèi)存管理技術(shù)研究[J].電子科技，2008，21（06）：62-65.

[3]Mark Allen Weiss.Data Structures and Algorithm Analysis in C[D].機(jī)械工業(yè)出版社，2013.

[4]柴繼國(guó).嵌入式系統(tǒng)內(nèi)存管理的研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2006.