大容量?jì)却嫖募到y設計及μC/OS下的實(shí)現

關(guān)鍵詞：嵌入式系統 內存文件系統 大容量存儲μC/OS

引言

嵌入式系統憑借其特有的功能和資源占用量少的特點(diǎn)，在各個(gè)領(lǐng)域得到了越來(lái)越多的應用。根據成本和設計的需要，一般的嵌入式系統都配置很少的外部存儲空間甚至不帶外部磁盤(pán)。但隨著(zhù)用戶(hù)需求和功能復雜度的增加，越來(lái)越多的嵌入式系統需要處理大容量的數據，或者在運行過(guò)程中會(huì )產(chǎn)生大量的臨時(shí)數據。一方面這些數據處理完后不能立即刪除；另一方面這些臨時(shí)文件不需要長(cháng)期保存。例如，用來(lái)上網(wǎng)沖浪的機頂盒設備在用戶(hù)瀏覽過(guò)程中不斷從互聯(lián)網(wǎng)上接收數據，因此用戶(hù)訪(fǎng)問(wèn)后的頁(yè)面很可能再次瀏覽，所不能將瀏覽后的網(wǎng)頁(yè)立即清除，當然，系統不需要也不可能將所有瀏覽過(guò)的頁(yè)面保存于硬盤(pán)中。所以，處理數據量的增大給嵌入式系統的設計提供了新的要求。

一般來(lái)說(shuō)，嵌入式系統處理大容量臨時(shí)數據的有效方法是設計一個(gè)內存文件系統存儲這些數據。內存文件系統MFS（Memory File System）是一個(gè)在內存中對文件實(shí)行按名存取的底層軟件。和普通磁盤(pán)文件系統相比，內存文件系統具有存取速度快、可動(dòng)態(tài)改變文件系統大小和數據掉電即丟失的優(yōu)點(diǎn)，因此它適用于高速的臨時(shí)數據處理。Linux下的Tmpfs、Proc文件系統以及Freebsd下的MFS都是一種內存文件系統。但是，這些通用操作系統上的內存文件系統不能夠直接運用于到嵌入式系統中：其一，它們都是為資源豐富的通用PC平臺設計的，不適用于資源有限的嵌入式系統；其二，這些通用內存文件系統的設計方案一般是利用內存來(lái)模擬磁盤(pán)文件系統，在內存中會(huì )建立文件系統緩沖區。這就是說(shuō)除了文件系統本身占據了內存之外，磁盤(pán)緩沖區又會(huì )占所一些內存，這些就會(huì )導致內存的浪費和利用率的下降。根據上述考慮，本文設計了一適合于嵌放式大容量數據處理的嵌入式內存文件系統EMFS（Fmbedded Momory File System）。文中首先闡述了EMFS嵌入式系統的設計要點(diǎn)，隨后討論了如果將其移植到μC/OS系統，最后對其性能進(jìn)行了分析和測試。

1 EMFS的設計

從前面分析得知，本文設計的EMFS不采用通用文件系統的磁盤(pán)設計方法，如Linux系統的Ext2節點(diǎn)結構和Windows的FAT結構。EMFS對文件的主要管理方式為：

①文件的各個(gè)屬性單獨存儲在文件信息表（file status table）中；

②文件數據塊用鏈表來(lái)分配和管理，文件數據塊大小可以動(dòng)態(tài)改變，這樣可以避免在系統運行過(guò)程中產(chǎn)生大量的碎片；

③為了提高文件的讀寫(xiě)和查找速度，設置一個(gè)全局散列表（Hash表）作為文件的讀寫(xiě)及查找入口；每個(gè)文件根據其文件名、文件長(cháng)度計算出一個(gè)Hash值；然后在Hash表找到文件對應的Hash項，這樣就可以讀出文件的屬性和數據。

圖1表示了EMFS在內存中的組織結構。

每一個(gè)存儲于EMFS的文件在全局Hash表都有個(gè)對應的入口項。其文件屬性和文件名、文件長(cháng)度、創(chuàng )建時(shí)間等存入文件狀態(tài)表，文件內容存儲于從空閑塊鏈表申請到的數據塊中。文件的Hash表、狀態(tài)表和數據塊通過(guò)指針鏈接起來(lái)，如圖2所示，下面分別介紹文件系統的Hash表、狀態(tài)表和數據塊鏈表。

1.1 全局Hash表

（1）Hash值的產(chǎn)生

從圖2可看出，Hash表是整個(gè)文件系統讀寫(xiě)和查找的入口，通過(guò)計算文件的Hash值來(lái)找到其在Hash表中的位置，從而訪(fǎng)問(wèn)文件狀態(tài)表和數據塊。因此文件系統的查找效率主體現在，如何通過(guò)文件信息計算其對應的Hash值以及如何有效地組織Hash表。圖3表示了EMFS系統中Hash表的構成情況，每個(gè)文件對應8字節的Hash值。其中前2個(gè)字節是文件名長(cháng)度和文件名第一個(gè)字節的ASCII碼值，接下來(lái)的2個(gè)字節是文件名的16CRC（循環(huán)冗余校驗編碼），最后4個(gè)字節文件名的32CRC編碼。這里為了減少同文件對應相同Hash值的概率，文件名的Hash值中既包含了文件名的16CRC編碼又包含了32CRC編碼。

（2）Hash表的組織和查找

在獲得Hash值后，如何將8個(gè)字節的Hash值有效地組織在全局Hash表中來(lái)獲得最高的查找速度是一個(gè)關(guān)鍵問(wèn)題。根據數據結構算法理論可知，將Hash表順序組織為一個(gè)有序表，可以通過(guò)折半查找法來(lái)獲得最高的查找效率。其比較次數最多為└log2n┘+1（n為表中的記錄個(gè)數），其平均查找長(cháng)度ASL（Average Search Length）近似為log2(n+1)-1。然而，隨著(zhù)文件的動(dòng)態(tài)增加或刪除，每個(gè)文件對應的Hash值或大或小，這樣系統的Hash表并不能保證是一個(gè)順序表，因此就不能采用折半查找法。如果首先將無(wú)序的Hash表排列為有序表再采用折半法查找，那么即使在最好的情況下，排序操作所需要的時(shí)間復雜度也為O（nlogn），同時(shí)還需要其它的輔助存儲，這樣在排序操作上就要花費大量的時(shí)間和存儲空間，使整個(gè)系統的查找效率大大降低。針對此不足，本文采用鏈地址法組織全局Hash表，將全局Hash表分為兩部分：其本表和溢出表。其基本思想為：首先分配一個(gè)固定大?。ㄟ@里假設取1024項）的順序表作為基本表，每個(gè)文件計算得出的Hash值通過(guò)對1024取模得到個(gè)介于0～1023之間的模值。如果此模值在基本表中的對應項沒(méi)有被占用，那么該項就作為此文件的Hash項；如果此模值在基本表中的對應項已被其它文件占用，那么就溢出表中申請一個(gè)此文件的Hash項，并將此Hash項鏈接到具有相同模值的鏈表中。通過(guò)這種順序表和鏈表相結合的結構，既會(huì )影響查找速度又不會(huì )增加額外存儲空間，從而提高EMFS的查找效率而且不增加系統的時(shí)間和空間復雜度。

1.2 文件狀態(tài)表

文件狀態(tài)表用來(lái)存放文件系統中文件的各個(gè)屬性，包括文件名稱(chēng)、文件大小、讀寫(xiě)標志、創(chuàng )建和修改時(shí)間。同時(shí)，為了提高內存空間的利用率，可以對文件進(jìn)行選擇性壓縮存儲，因此文件狀態(tài)表也包括文件壓縮標志，壓縮前的原始大小和壓縮后的文件大小。從圖2可以看到，文件狀態(tài)表是和Hash表以及數據塊鏈表連在一起的，那么一旦定位到文件對應的Hash項，就可以對文件狀態(tài)表進(jìn)行讀寫(xiě)。

1.3 數據塊鏈表

在EMFS中，文件數據內容保存在內存數據塊中，內存數據塊的大小可以在建立文件系統時(shí)動(dòng)態(tài)設定。數據塊鏈表的作用是對內存塊進(jìn)行管理。由于數據塊鏈表中每一項對應一個(gè)內存塊，所以當添加文件時(shí)，系統根據文件大小動(dòng)態(tài)地從數據塊鏈表中申請一定數量的數據塊；當刪除文件時(shí)，系統將數據塊插入到此鏈表中。

2 EMFS在μC/OS系統下的實(shí)現和性能分析

2.1 EMFS是μC/OS下的實(shí)現流程

μC/OS是一個(gè)多任務(wù)的實(shí)時(shí)性嵌入式操作系統，得到了廣泛的使用。μC/OS公開(kāi)了它的實(shí)時(shí)性?xún)群嗽创a，同時(shí)提供了內存管理的接口和函數。通過(guò)在其實(shí)時(shí)內核的基礎上進(jìn)行少量的修改，便可將EMFS移植到μC/OS系統中。圖4是EMFS在μC/OS下的初始化流程。

初始化完畢后，在μC/OS系統中建立EMFS的三主要數據結構，隨后就可以向EMFS中讀寫(xiě)文件并進(jìn)行測試。圖5和圖6分別是讀寫(xiě)文件的流程。

2.2 EMFS的性能測試與分析

通過(guò)將EMFS移植到μC/OS系統，便可以對EMFS的性能進(jìn)行分析。前面提到，EMFS的主要特點(diǎn)是有效高的查找速度和內存利用率?，F在，從這兩方面分別對EMFS進(jìn)行性能測試和分析比較。

（1）平均查找次數

通過(guò)加入8000個(gè)平均長(cháng)度為20KB的文件到EMFS中，這可以在對全局Hash表的基本表設定不同大小的情況下，隨機地讀出一定數量的文件來(lái)統計EMFS的平均查找次數。這里設定基本表的大小分別為1024和2048，讀出文件數量分別為500、1000、2000、4000和8000個(gè)，平均查找次數的統計結果具體如表1所列。

從表1可以分析出以下幾點(diǎn)：

①8000個(gè)文件全部讀出所需的平均查找次數最多不到5次；而當Hash表采用順序表時(shí)，使用拆半查找法得到的平均查找次數為└log28000┘+1=13次，可見(jiàn)EMFS的查找效率非常高，而且它不增加時(shí)間和空間的復雜度。

②讀出的文件數量越少，平均查找次數越少。因為文件是隨機選擇的，故讀出的文件越少，它們對應的Hash值在基本表中越分散，因而比較次數相應較少。

③基本表包含的Hash項越多，EMFS的平均查找次數越少。這是因為基本表越大，Hash值取模后落在基本表的概率就越大，因此比較的次數就越少。但要注意一點(diǎn)，在實(shí)際應用中基本表并不是設置得越大越好，基本表設置得越大，相應地溢出表就越小。當把溢出表項用完之后，基本表可以還沒(méi)有用完，但這時(shí)已經(jīng)不能夠再添加文件了，這樣系統效率反而會(huì )降低。

（2）內存利用率

EMFS的內存利用率可以從兩個(gè)方面來(lái)表現：一對文件進(jìn)行選擇性壓縮的機制；二是內存數據塊大小的選擇。

對文件進(jìn)行壓縮存儲可以提高內存利用率，然而文件的壓縮和解壓需要耗費一定系統時(shí)間和資源，這在一定程序上會(huì )降低系統的性能，因此需對文件進(jìn)行選擇性壓縮。具體方法是對文本等壓縮比例高的文件進(jìn)行壓縮存儲，對數據等壓縮比例低的文件，則選擇直接存儲。

另外，對文件數據塊大小的選擇也會(huì )影響內存利用率。在EMFS中，文件數據存儲的基本單位是一個(gè)內存數據真。這樣，每個(gè)文件的最后一個(gè)數據塊很可能會(huì )用不完，平均來(lái)看，每個(gè)文件會(huì )浪費1/2個(gè)數據塊。在文件數據塊為1KB和2KB的情況下，我們測試得到內存利用率分別為97.4%和94.8%。顯然，前者的利用率更高，這是因為文件數據塊越小，文件浪費的空間越少。但是，文件數據塊不能設置得太小，否則系統在運行過(guò)程中會(huì )產(chǎn)生很多碎片，導致系統性能的降低。

3 結論

本文提出了嵌入式系統下的一種大容量?jì)却嫖募到y的實(shí)現方案，并從文件的平均查找次數和系統內存利用率等方面對文件系統進(jìn)行了測試和性能分析。測試結果表明，此系統具有較快的查找定位速度和較高的內存利用率，所以本系統能夠有效地應用于嵌入式系統，尤其是那些產(chǎn)生較多臨時(shí)文件或處理大容量數據的嵌入式系統。