一種嵌入式應用的內存分配算法

程知敬

摘要??? 傳統嵌入式系統為保障系統的可靠性和實時性，大多采用靜態分配內存的方式，導致應用開發的效率低下。本文提出了一種嵌入式應用的內存分配算法，在經典深度優先搜索算法的基礎上，結合自研的內存復用算法——間隔復用法，實現自動化的應用內存分配，且使得內存利用率得以提升。最后，通過工程實例驗證了其正確性及有效性。

【關鍵詞】嵌入式系統 內存分配算法

1 引言

傳統嵌入式軟件的開發流程是基于嵌入式集成開發環境完成實時處理軟件設計、編碼、編譯，將編譯后的可執行文件下載到嵌入式設備上進行調試驗證。該過程涉及軟、硬件的資源分配，對軟件設計人員提出了較高要求。

為提高軟件開發效率，基于模型的設計方法開始受到廣泛推崇。它始于20世紀90年代初的汽車制造和航空航天工業;90年代中期，自動代碼生成技術使模型化設計方法有了實用價值;1984年隨著MathWorks公司的成立，旗下的Simulink/Stateflow、EmbeddedMatlab等產品融合了建模、仿真和分析工具，將軟件開發流程方式徹底轉變為在一個可視化的交互開發平臺上進行軟件設計和開發，并通過直觀的系統模型進行可視化處理。

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

本文提供一種嵌入式應用的內存分配算法，實現軟件各應用模塊在嵌入式設備內存空間分配的自動化，并確保板卡內存的高利用率和高復用率。

2 嵌入式內存分配的要求

嵌入式應用的拓撲結構滿足有向無環圖（DAG，Directed Acyclic Graph），應用即為圖的頂點，應用的執行順序是有方向的，且應用之間不會形成圈。

約束條件有二種：

（1）應用的內存占比，即單一板卡上所有應用所需的內存（包含運算內存和通信內存）之和不超過板卡的總內存，

（2）應用的通過率，即所有應用所占的時間耗時之和不超過系統要求的總通過率。所以該圖還是一個有權圖。

經典的圖遍歷算法有深度優先搜索和廣度優先搜索。

深度優先搜索算法（DFS，Depth-FirstSearch）是對先序遍歷的推廣。它是指從圖中某個未被訪問過的初始頂點v出發，首先訪問初始頂點v，然后選擇一個與頂點v相鄰且沒被訪問過的頂點w為初始頂點，再從w出發進行深度優先搜索，直到圖中與當前頂點v鄰接的所有頂點都被訪問過為止。若此時還有其他未被訪問的頂點，重復上述過程，直到圖中所有頂點都被訪問到為止。

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

對于嵌入式應用拓撲圖而言，DFS的優點在于可以減少應用之間的通信鏈路開銷，但因為會快速達到通過率上限而浪費過多的存儲內存;BFS的優點在于能最大限度利用板卡內的內存空間，但多個鄰接點分支將導致通信鏈路的開銷加大。

因此本算法考慮的內存分配目標是：

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

（2）高復用率。考慮各應用模塊的內存能夠盡可能的復用。但硬實時系統不具備資源隔離功能，因此復用時必須考慮清楚各模塊的內存狀態以免發生內存意外改寫。

3 通信內存的間隔復用法

應用的內存按其作用分為兩類，一類是用于通信收發的內存，包括應用輸入數據的緩存區和輸出數據的緩存區，另一類是用于應用執行過程中用到的計算處理內存。后者可能涉及到迭代等需要歷史數據的計算，所以不便考慮內存復用。因此，本算法只考慮通信內存的復用。

為簡化分析過程，上一級的輸出緩存區和下一級的輸入緩存區看作一個整體，即圖1中應用1使用通信緩存分區1輸出數據，且應用2同樣使用分區1輸入數據。

先考慮最簡單的串行處理流程，如圖1（a）所示。某包數據首先進入應用1處理，處理完畢后經由分區1發往應用2處理，應用2處理完畢后經由分區2發往應用3，此時分區1處在空余狀態，因此應用3發往應用4時可以復用緩存分區1。從圖上可以直觀看出，對于串行結構，可以每間隔兩個應用就可以復用同一個緩存分區，因此將該算法命名為間隔復用法。

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

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

如果應用模塊A有相連的前一級應用模塊B，模塊B有相連的前一級應用模塊C，且模塊B的輸入滿足：

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

（2）該輸入不會發送給模塊A的下一級模塊;

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

則應用模塊A的輸出內存區可以復用其前一級應用模塊B的輸入內存區。

4 嵌入式內存分配算法

依據上述嵌入式內存分配的要求，本算法考慮在DFS的基礎上，結合內存復用算法實現內存的高利用率和復用率。算法描述如下（圖2）：

步驟一，通過DFS搜索應用拓撲圖，其約束為：

（1）已搜索到的應用的總通過率不超過系統通過率;

（2）已搜索到的應用的占用內存之和不超過單一板卡的總內存。

如果本次搜索后有新增應用，轉到步驟二;否則算法結束。

步驟二，使用間隔復用法對步驟一分配后的應用進行判定，如有可復用的內存，轉到步驟一在原應用分配的基礎上繼續進行DFS搜索;否則算法結束。

5 應用

假設一塊板卡總的用戶可用內存為210M，系統要求的總通過率為11s。應用拓撲圖如圖3所示，圖中每個應用占用內存20M，其中運算內存16M，通信內存4M，所以如果直接分配，最多可以在該板卡上分配10個應用;應用中標明的數字表示各自的通過率，本例中即便在板卡上分配所有應用，總的通過率仍滿足系統要求;各應用之間的連接符，如果有以數字標明區別，表示輸出的數據內容不同。

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

由本例可見，該算法在傳統DFS搜索結果的基礎上進行優化，使得單板可分配的應用數從10個增長到11個。對于通信數據龐大的應用而言，能夠復用的空間更多，效果更佳。

6 結束語

本文提出了一種嵌入式應用的內存分配算法，結合深度優先搜素算法和通信內存的間隔復用算法，解決了軟件各應用模塊在嵌入式設備內存空間分配的自動化問題，并確保板卡內存的高利用率和高復用率。但如果想達到靜態分配方法的最優解，還需要解決運算內存的復用問題。

參考文獻

[1]劉杰.基于模型的設計及其嵌入式實現[D].北京航空航天大學出版社，2010.

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

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

[4]柴繼國.嵌入式系統內存管理的研究與實現[D].成都：電子科技大學，2006.