蔡富強(qiáng)，郭兵，沈艷

（1.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都610065；2.電子科技大學(xué)）

蔡富強(qiáng)（碩士生），主要研究方向?yàn)榍度胧綄?shí)時(shí)系統(tǒng)；郭兵（教授），主要研究方向?yàn)榍度胧綄?shí)時(shí)系統(tǒng)、SoC和中間件；沈艷（副教授），主要研究方向?yàn)樘摂M儀器、分布式測(cè)試。

引 言

嵌入式系統(tǒng)是一個(gè)專用的計(jì)算機(jī)系統(tǒng)，它在現(xiàn)實(shí)生活中有著極其廣泛的用途，大到飛機(jī)、宇宙飛船，小到各種手持設(shè)備（如手機(jī)），都是嵌入式系統(tǒng)的具體應(yīng)用?？梢哉f，嵌入式系統(tǒng)已經(jīng)漸漸融入我們的生活，變得不可或缺。這種趨勢(shì)將隨著物聯(lián)網(wǎng)［1］的推廣變得更加明顯。

嵌入式系統(tǒng)的一個(gè)比較關(guān)鍵的技術(shù)就是嵌入式操作系統(tǒng)。目前常用的嵌入式操作系統(tǒng)有 Linux、μC／OS［2］、WinCE、VxWorks、Symbian等，其中μC／OS以其開放源碼、高效而小巧，同時(shí)又兼具實(shí)時(shí)性等特點(diǎn)得到了比較廣泛的應(yīng)用。

μC／OS中只實(shí)現(xiàn)了操作系統(tǒng)的一些基本功能（帶優(yōu)先級(jí)可搶占的進(jìn)程管理和一個(gè)比較簡單的內(nèi)存管理方案），這是它只有幾千行代碼的基本原因。正因?yàn)槿绱?，它并不適用于所有嵌入式應(yīng)用，尤其是面向高端的應(yīng)用。為了拓展μC／OS的應(yīng)用范圍，很多改進(jìn)措施被提出。一些學(xué)者為μC／OS添加功能模塊，以拓展其應(yīng)用，如TCP／ⅠP協(xié)議棧、GUⅠ、文件系統(tǒng)等，參考文獻(xiàn)［3］為μC／OS添加內(nèi)存文件系統(tǒng)，參考文獻(xiàn)［4］為μC／OS添加基于FAT的Flash文件系統(tǒng)；也有學(xué)者改進(jìn)μC／OS的基本模塊，以滿足新的需求，參考文獻(xiàn)［5］改進(jìn)了μC／OS的任務(wù)調(diào)度模塊，參考文獻(xiàn)［6］解決μC／OS消息隊(duì)列數(shù)據(jù)通信安全問題；參考文獻(xiàn)［7］擴(kuò)展μC／OS到可重構(gòu)系統(tǒng)，使其支持軟硬件任務(wù)的統(tǒng)一調(diào)度。

本文也以拓展μC／OS應(yīng)用為目的，為μC／OS添加加載外部可執(zhí)行程序支持，同時(shí)也提出一種內(nèi)存分配方案，以實(shí)現(xiàn)為程序映像和棧高效分配內(nèi)存。由于目前在嵌入式領(lǐng)域應(yīng)用最多的處理器為ARM系列，本功能的實(shí)現(xiàn)針對(duì)ARM平臺(tái)。

1 內(nèi)存分配

μC／OS內(nèi)核實(shí)現(xiàn)的內(nèi)存分配方案支持多種大小的內(nèi)存塊，但不同大小內(nèi)存塊之間獨(dú)立管理，這種實(shí)現(xiàn)使用不方便，不能實(shí)現(xiàn)動(dòng)態(tài)而高效的內(nèi)存分配。本文提出一種獨(dú)立的內(nèi)存管理機(jī)制，以實(shí)現(xiàn)為程序映像和棧高效分配內(nèi)存。

實(shí)現(xiàn)參考了Linux內(nèi)核的分區(qū)頁面管理算法［8］。將全局內(nèi)存劃分為以512字節(jié)為單位的塊，并為每個(gè)內(nèi)存塊建立描述符，通過描述符來管理內(nèi)存塊。內(nèi)存塊按塊數(shù)的幾何級(jí)數(shù)組織成多級(jí)鏈表，第一級(jí)用于分配1個(gè)塊，第二級(jí)用于分配地址連續(xù)的2個(gè)塊，第三級(jí)用于分配地址連續(xù)的4個(gè)塊，依次類推。由連續(xù)內(nèi)存塊的首塊內(nèi)存的描述符參與鏈表鏈接。將實(shí)現(xiàn)下面幾個(gè)函數(shù)，具體描述見1.2小節(jié)。

1.1 數(shù)據(jù)結(jié)構(gòu)定義

實(shí)現(xiàn)該內(nèi)存管理，需要一些全局變量和數(shù)據(jù)結(jié)構(gòu)定義。ⅠNT8U＊pmem指向靜態(tài)分配的全局內(nèi)存。塊描述符的定義如下：

BLOCK＿DESC表示內(nèi)存塊描述符，每個(gè)內(nèi)存塊都有一個(gè)內(nèi)存描述符，并且從前到后一一對(duì)應(yīng)。next和prev用于多級(jí)鏈表的鏈接；order的最高位表示該連續(xù)的內(nèi)存塊序列是否被使用，其余位表示所屬鏈表級(jí)數(shù)。鏈表級(jí)數(shù)根據(jù)全局內(nèi)存大小自動(dòng)調(diào)整，在嵌入式應(yīng)用中一般不超過10（能分配最大512KB的連續(xù)內(nèi)存），用ⅠNT8Ugorder表示鏈表的級(jí)數(shù)。BLOCK＿DESC＊desc＿begin表示塊描述符的首地址。void＊block＿begin表示內(nèi)存塊的首地址。BLOCK＿DESC＊desc＿list［11］用于鏈接多級(jí)鏈表。

1.2 函數(shù)實(shí)現(xiàn)

DescToBlock函數(shù)實(shí)現(xiàn)從內(nèi)存塊描述符地址到內(nèi)存塊地址的轉(zhuǎn)換。由于塊描述符與內(nèi)存塊依次對(duì)應(yīng)，只要有兩者的內(nèi)存首地址，就很容易實(shí)現(xiàn)。具體實(shí)現(xiàn)只需要下面的表達(dá)式：return（char＊）block＿begin＋ （desc－desc＿begin）＜＜9。BlockToDesc函數(shù)功能正好相反，實(shí)現(xiàn)方式類似。

BlockMemⅠnit函數(shù)完成該內(nèi)存管理方案的初始化。首先，根據(jù)提供的全局內(nèi)存的大小確定多級(jí)鏈表級(jí)數(shù)，最多為10級(jí)，并初始化全局變量gorder，內(nèi)存塊數(shù)為size／（512＋sizeof（BLOCK＿DESC））；然后，根據(jù)全局內(nèi)存能夠容納的內(nèi)存塊數(shù)將其分為兩部分，前面用于存儲(chǔ)所有的塊描述符（將塊描述符清零），后面部分就是用于分配的內(nèi)存塊，并初始化全局變量block＿begin和desc＿begin；最后，將內(nèi)存塊按最大化的原則分配于多級(jí)鏈表中，理想情況下所有的內(nèi)存塊都分配于所支持的最大級(jí)鏈表中，大小不滿足的則分配到低級(jí)別的鏈表中（仍須按最大化原則）。

圖1表示初始化后的內(nèi)存布局（虛線表示不一定存在）。

GetBlocks函數(shù)用于分配（1＜＜o(jì)rder）個(gè)連續(xù)的內(nèi)存塊。算法描述如下：

① 檢查參數(shù)order是否有效，無效返回null，有效繼續(xù)；

②檢查order級(jí)鏈表是否有空閑內(nèi)存，沒有轉(zhuǎn)下一步，否則從鏈表中取出第一塊，修改描述符的使用標(biāo)志位，通過函數(shù)DescToBlock獲取內(nèi)存地址并返回；

③ 從更高級(jí)別獲取空閑內(nèi)存，如果獲取失敗，返回null，否則，逐級(jí)分裂直到order級(jí)鏈表，并修改首個(gè)描述符的所屬鏈表級(jí)數(shù)，轉(zhuǎn)第二步。

圖1 初始化后的內(nèi)存布局

FreeBlocks函數(shù)用于釋放指定地址處開始的（1＜＜o(jì)rder）個(gè)連續(xù)的內(nèi)存塊。該函數(shù)是實(shí)現(xiàn)高效內(nèi)存分配的關(guān)鍵，為了保證內(nèi)存不會(huì)被分得過碎，需要迭代檢查釋放內(nèi)存是否可以同相鄰的內(nèi)存合并（看描述符order字段是否相同）。算法描述如下：

①通過函數(shù)BlockToDesc獲取塊描述符的地址，將描述符設(shè)置為未使用；

② 檢查order級(jí)鏈表中是否有與待釋放內(nèi)存相鄰的內(nèi)存（前后都有相鄰的選前面的參與合并）。如果沒有相鄰的，轉(zhuǎn)第③步。否則，將相鄰內(nèi)存的首個(gè)內(nèi)存塊描述符從鏈表中刪除，修改相關(guān)的兩個(gè)塊描述符的order字段（在前面的加1，后面的清零），參數(shù)order加1，繼續(xù)執(zhí)行第②步；

③ 將內(nèi)存插入order級(jí)鏈表中。

2 加載程序

要實(shí)現(xiàn)外部程序加載，需要操作系統(tǒng)和編譯器的密切配合，整個(gè)過程非常復(fù)雜。為了使程序加載器盡可能簡單和高效，采用下面的措施：

① 修改編譯μC／OS內(nèi)核的Makefile文件，使內(nèi)核鏈接地址和加載地址相同，通過NM工具導(dǎo)出內(nèi)核函數(shù)地址表。將地址表以函數(shù)指針的形式組織在頭文件中，另外還須在頭文件中加入內(nèi)核中關(guān)于數(shù)據(jù)類型和結(jié)構(gòu)的定義，供外部程序使用。以本文第一部分中的BlockMemⅠnit函數(shù)為例，假設(shè)函數(shù)地址位于0x00008000，在頭文件中作如下聲明即可：

② 使main函數(shù)的代碼位于程序映像的入口處（為簡單起見，main函數(shù)不支持參數(shù)）。只需采用下面措施即可。編程時(shí)保證main函數(shù)是所在文件中第一個(gè)被實(shí)現(xiàn)的函數(shù)，修改LD鏈接腳本使包含main函數(shù)的目標(biāo)文件的代碼段位于整個(gè)可執(zhí)行程序的開始。

③通過OBJCOPY工具將鏈接生成的ELF格式的可執(zhí)行程序轉(zhuǎn)化為二進(jìn)制映像。

④ 為μC／OS添加函數(shù)void Exec（char＊name），用于加載二進(jìn)制映像，并為其創(chuàng)建進(jìn)程。

通過以上措施，加載器的實(shí)現(xiàn)非常簡單，只需為二進(jìn)制映像分配內(nèi)存并將其加載進(jìn)內(nèi)存，然后調(diào)用函數(shù)OSTaskCreate（二進(jìn)制映像加載地址（main），null，通過函數(shù) GetBlocks分配的?？臻g，優(yōu)先級(jí)）即可，由于ARM平臺(tái)沒有直接內(nèi)存尋址模式，二進(jìn)制映像不需要重定位就可執(zhí)行。圖2為Exec函數(shù)的流程。

圖2 Exec函數(shù)執(zhí)行流程

結(jié) 語

測(cè)試時(shí)采用S3C2440系列開發(fā)板作為目標(biāo)平臺(tái)。首先，修改u－boot，以使其能夠加載μC／OS到指定地址處，并完成內(nèi)核的引導(dǎo)工作；其次，移植μC／OS，使其能夠在S3C2440系列開發(fā)板上運(yùn)行；然后，按參考文獻(xiàn)［3］或［4］中提供的方法為μC／OS實(shí)現(xiàn)文件系統(tǒng)支持；最后，按本文中的方法實(shí)現(xiàn)二進(jìn)制映像加載功能。經(jīng)測(cè)試，該方案是可行的。當(dāng)然，該方案也存在一定的局限性，如只針對(duì)ARM平臺(tái)，內(nèi)存分配方案還不能通用（對(duì)小內(nèi)存塊分配利用率低），又由于μC／OS內(nèi)核不支持保護(hù)模式，安全性也是一個(gè)問題。

［1］王保云.物聯(lián)網(wǎng)技術(shù)研究綜述［J］.電子測(cè)量與儀器學(xué)報(bào)，2009，23（12）：1－7.

［2］Labrosse Jean J.嵌入式實(shí)時(shí)操作系統(tǒng)μC／OS－ⅠⅠ［M］.邵貝貝，等譯.2版.北京航空航天大學(xué)出版社，2003.

［3］張紅兵.大容量內(nèi)存文件系統(tǒng)設(shè)計(jì)及μC／OS下的實(shí)現(xiàn)［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2004（3）：15－20.

［4］王命延.一種加載在μC／OS－ⅠⅠ內(nèi)核上的嵌入式文件系統(tǒng)［J］.南昌大學(xué)學(xué)報(bào)：理科版，2005，29（2）：197－204.

［5］張旭.μC／OS ⅠⅠ內(nèi)核任務(wù)調(diào)度模塊的分析與改進(jìn)［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2005（4）：71－76.

［6］曾蜀芳.μC／OS－ⅠⅠ中消息隊(duì)列通信的數(shù)據(jù)安全問題［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（8）：151－154.

［7］周博.SHUM－UCOS：基于統(tǒng)一多任務(wù)模型可重構(gòu)系統(tǒng)的實(shí)時(shí)操作系統(tǒng)［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（2）：208－218.

［8］Bovet Daniel P，Cesati Marco.深入理解Linux內(nèi)核［M］.陳莉君，等譯.2版.北京：中國電力出版社，2004：223－268.