大容量內(nèi)存文件系統(tǒng)設(shè)計(jì)及μC/OS下的實(shí)現(xiàn)

摘要：針對某些嵌入式系統(tǒng)中處理數(shù)據(jù)量大和速度要求高的特點(diǎn)，提出一種應(yīng)用于嵌入式系統(tǒng)中的大容量內(nèi)存文件系統(tǒng)的實(shí)現(xiàn)方案。該方案通過在內(nèi)存中建立文件系統(tǒng)，將臨時(shí)數(shù)據(jù)有效組織于內(nèi)存中，既提高訪問速度又節(jié)省外存空間，因而能滿足要求;通過將其移植到μC/OS系統(tǒng)下，便可進(jìn)行性能測試和分析。結(jié)果表明，本內(nèi)存文件系統(tǒng)具有較高的查找效率和內(nèi)存利用率。 關(guān)鍵詞：嵌入式系統(tǒng) 內(nèi)存文件系統(tǒng) 大容量存儲μC/OS 引言 嵌入式系統(tǒng)憑借其特有的功能和資源占用量少的特點(diǎn)，在各個(gè)領(lǐng)域得到了越來越多的應(yīng)用。根據(jù)成本和設(shè)計(jì)的需要，一般的嵌入式系統(tǒng)都配置很少的外部存儲空間甚至不帶外部磁盤。但隨著用戶需求和功能復(fù)雜度的增加，越來越多的嵌入式系統(tǒng)需要處理大容量的數(shù)據(jù)，或者在運(yùn)行過程中會產(chǎn)生大量的臨時(shí)數(shù)據(jù)。一方面這些數(shù)據(jù)處理完后不能立即刪除;另一方面這些臨時(shí)文件不需要長期保存。例如，用來上網(wǎng)沖浪的機(jī)頂盒設(shè)備在用戶瀏覽過程中不斷從互聯(lián)網(wǎng)上接收數(shù)據(jù)，因此用戶訪問后的頁面很可能再次瀏覽，所不能將瀏覽后的網(wǎng)頁立即清除，當(dāng)然，系統(tǒng)不需要也不可能將所有瀏覽過的頁面保存于硬盤中。所以，處理數(shù)據(jù)量的增大給嵌入式系統(tǒng)的設(shè)計(jì)提供了新的要求。 一般來說，嵌入式系統(tǒng)處理大容量臨時(shí)數(shù)據(jù)的有效方法是設(shè)計(jì)一個(gè)內(nèi)存文件系統(tǒng)存儲這些數(shù)據(jù)。內(nèi)存文件系統(tǒng)MFS(Memory File System)是一個(gè)在內(nèi)存中對文件實(shí)行按名存取的底層軟件。和普通磁盤文件系統(tǒng)相比，內(nèi)存文件系統(tǒng)具有存取速度快、可動態(tài)改變文件系統(tǒng)大小和數(shù)據(jù)掉電即丟失的優(yōu)點(diǎn)，因此它適用于高速的臨時(shí)數(shù)據(jù)處理。Linux下的Tmpfs、Proc文件系統(tǒng)以及Freebsd下的MFS都是一種內(nèi)存文件系統(tǒng)。但是，這些通用操作系統(tǒng)上的內(nèi)存文件系統(tǒng)不能夠直接運(yùn)用于到嵌入式系統(tǒng)中：其一，它們都是為資源豐富的通用PC平臺設(shè)計(jì)的，不適用于資源有限的嵌入式系統(tǒng);其二，這些通用內(nèi)存文件系統(tǒng)的設(shè)計(jì)方案一般是利用內(nèi)存來模擬磁盤文件系統(tǒng)，在內(nèi)存中會建立文件系統(tǒng)緩沖區(qū)。這就是說除了文件系統(tǒng)本身占據(jù)了內(nèi)存之外，磁盤緩沖區(qū)又會占所一些內(nèi)存，這些就會導(dǎo)致內(nèi)存的浪費(fèi)和利用率的下降。根據(jù)上述考慮，本文設(shè)計(jì)了一適合于嵌放式大容量數(shù)據(jù)處理的嵌入式內(nèi)存文件系統(tǒng) EMFS(Fmbedded Momory File System)。文中首先闡述了EMFS嵌入式系統(tǒng)的設(shè)計(jì)要點(diǎn)，隨后討論了如果將其移植到μC/OS系統(tǒng)，最后對其性能進(jìn)行了分析和測試。 1 EMFS的設(shè)計(jì) 從前面分析得知，本文設(shè)計(jì)的EMFS不采用通用文件系統(tǒng)的磁盤設(shè)計(jì)方法，如Linux系統(tǒng)的Ext2節(jié)點(diǎn)結(jié)構(gòu)和Windows的FAT結(jié)構(gòu)。EMFS對文件的主要管理方式為： ①文件的各個(gè)屬性單獨(dú)存儲在文件信息表(file status table)中; ②文件數(shù)據(jù)塊用鏈表來分配和管理，文件數(shù)據(jù)塊大小可以動態(tài)改變，這樣可以避免在系統(tǒng)運(yùn)行過程中產(chǎn)生大量的碎片; ③為了提高文件的讀寫和查找速度，設(shè)置一個(gè)全局散列表(Hash表)作為文件的讀寫及查找入口;每個(gè)文件根據(jù)其文件名、文件長度計(jì)算出一個(gè)Hash值;然后在Hash表找到文件對應(yīng)的Hash項(xiàng)，這樣就可以讀出文件的屬性和數(shù)據(jù)。 圖1表示了EMFS在內(nèi)存中的組織結(jié)構(gòu)。

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

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

(2)Hash表的組織和查找 在獲得Hash值后，如何將8個(gè)字節(jié)的Hash值有效地組織在全局Hash表中來獲得最高的查找速度是一個(gè)關(guān)鍵問題。根據(jù)數(shù)據(jù)結(jié)構(gòu)算法理論可知，將 Hash表順序組織為一個(gè)有序表，可以通過折半查找法來獲得最高的查找效率。其比較次數(shù)最多為└log2n┘+1(n為表中的記錄個(gè)數(shù))，其平均查找長度 ASL(Average Search Length)近似為log2(n+1)-1。然而，隨著文件的動態(tài)增加或刪除，每個(gè)文件對應(yīng)的Hash值或大或小，這樣系統(tǒng)的Hash表并不能保證是一個(gè)順序表，因此就不能采用折半查找法。如果首先將無序的Hash表排列為有序表再采用折半法查找，那么即使在最好的情況下，排序操作所需要的時(shí)間復(fù)雜度也為O(nlogn)，同時(shí)還需要其它的輔助存儲，這樣在排序操作上就要花費(fèi)大量的時(shí)間和存儲空間，使整個(gè)系統(tǒng)的查找效率大大降低。針對此不足，本文采用鏈地址法組織全局Hash表，將全局Hash表分為兩部分：其本表和溢出表。其基本思想為：首先分配一個(gè)固定大小(這里假設(shè)取1024項(xiàng))的順序表作為基本表，每個(gè)文件計(jì)算得出的Hash值通過對1024取模得到個(gè)介于0～1023之間的模值。如果此模值在基本表中的對應(yīng)項(xiàng)沒有被占用，那么該項(xiàng)就作為此文件的Hash項(xiàng);如果此模值在基本表中的對應(yīng)項(xiàng)已被其它文件占用，那么就溢出表中申請一個(gè)此文件的Hash項(xiàng)，并將此Hash項(xiàng)鏈接到具有相同模值的鏈表中。通過這種順序表和鏈表相結(jié)合的結(jié)構(gòu)，既會影響查找速度又不會增加額外存儲空間，從而提高EMFS的查找效率而且不增加系統(tǒng)的時(shí)間和空間復(fù)雜度。 1.2 文件狀態(tài)表 文件狀態(tài)表用來存放文件系統(tǒng)中文件的各個(gè)屬性，包括文件名稱、文件大小、讀寫標(biāo)志、創(chuàng)建和修改時(shí)間。同時(shí)，為了提高內(nèi)存空間的利用率，可以對文件進(jìn)行選擇性壓縮存儲，因此文件狀態(tài)表也包括文件壓縮標(biāo)志，壓縮前的原始大小和壓縮后的文件大小。從圖2可以看到，文件狀態(tài)表是和Hash表以及數(shù)據(jù)塊鏈表連在一起的，那么一旦定位到文件對應(yīng)的Hash項(xiàng)，就可以對文件狀態(tài)表進(jìn)行讀寫。 1.3 數(shù)據(jù)塊鏈表 在EMFS中，文件數(shù)據(jù)內(nèi)容保存在內(nèi)存數(shù)據(jù)塊中，內(nèi)存數(shù)據(jù)塊的大小可以在建立文件系統(tǒng)時(shí)動態(tài)設(shè)定。數(shù)據(jù)塊鏈表的作用是對內(nèi)存塊進(jìn)行管理。由于數(shù)據(jù)塊鏈表中每一項(xiàng)對應(yīng)一個(gè)內(nèi)存塊，所以當(dāng)添加文件時(shí)，系統(tǒng)根據(jù)文件大小動態(tài)地從數(shù)據(jù)塊鏈表中申請一定數(shù)量的數(shù)據(jù)塊;當(dāng)刪除文件時(shí)，系統(tǒng)將數(shù)據(jù)塊插入到此鏈表中。 2 EMFS在μC/OS系統(tǒng)下的實(shí)現(xiàn)和性能分析 2.1 EMFS是μC/OS下的實(shí)現(xiàn)流程 μC/OS是一個(gè)多任務(wù)的實(shí)時(shí)性嵌入式操作系統(tǒng)，得到了廣泛的使用。μC/OS公開了它的實(shí)時(shí)性內(nèi)核源碼，同時(shí)提供了內(nèi)存管理的接口和函數(shù)。通過在其實(shí)時(shí)內(nèi)核的基礎(chǔ)上進(jìn)行少量的修改，便可將EMFS移植到μC/OS系統(tǒng)中。圖4是EMFS在μC/OS下的初始化流程。

初始化完畢后，在μC/OS系統(tǒng)中建立EMFS的三主要數(shù)據(jù)結(jié)構(gòu)，隨后就可以向EMFS中讀寫文件并進(jìn)行測試。圖5和圖6分別是讀寫文件的流程。 2.2 EMFS的性能測試與分析 通過將EMFS移植到μC/OS系統(tǒng)，便可以對EMFS的性能進(jìn)行分析。前面提到，EMFS的主要特點(diǎn)是有效高的查找速度和內(nèi)存利用率。現(xiàn)在，從這兩方面分別對EMFS進(jìn)行性能測試和分析比較。 (1)平均查找次數(shù) 通過加入8000個(gè)平均長度為20KB的文件到EMFS中，這可以在對全局Hash表的基本表設(shè)定不同大小的情況下，隨機(jī)地讀出一定數(shù)量的文件來統(tǒng)計(jì) EMFS的平均查找次數(shù)。這里設(shè)定基本表的大小分別為1024和2048，讀出文件數(shù)量分別為500、1000、2000、4000和8000個(gè)，平均查找次數(shù)的統(tǒng)計(jì)結(jié)果具體如表1所列。 讀出文件數(shù) 查找次數(shù)基本表項(xiàng)數(shù) 500 1000 2000 4000 8000 1024 1.204 1.489 1.942 2.974 4.904 2048 1.098 1.231 1.465 1.966 2.95 從表1可以分析出以下幾點(diǎn)： ①8000個(gè)文件全部讀出所需的平均查找次數(shù)最多不到5次;而當(dāng)Hash表采用順序表時(shí)，使用拆半查找法得到的平均查找次數(shù)為 └log28000┘+1=13次，可見EMFS的查找效率非常高，而且它不增加時(shí)間和空間的復(fù)雜度。 ②讀出的文件數(shù)量越少，平均查找次數(shù)越少。因?yàn)槲募请S機(jī)選擇的，故讀出的文件越少，它們對應(yīng)的Hash值在基本表中越分散，因而比較次數(shù)相應(yīng)較少。

③基本表包含的Hash項(xiàng)越多，EMFS的平均查找次數(shù)越少。這是因?yàn)榛颈碓酱?，Hash值取模后落在基本表的概率就越大，因此比較的次數(shù)就越少。

但要注意一點(diǎn)，在實(shí)際應(yīng)用中基本表并不是設(shè)置得越大越好，基本表設(shè)置得越大，相應(yīng)地溢出表就越小。當(dāng)把溢出表項(xiàng)用完之后，基本表可以還沒有用完，但這時(shí)已經(jīng)不能夠再添加文件了，這樣系統(tǒng)效率反而會降低。 (2)內(nèi)存利用率 EMFS的內(nèi)存利用率可以從兩個(gè)方面來表現(xiàn)：一對文件進(jìn)行選擇性壓縮的機(jī)制;二是內(nèi)存數(shù)據(jù)塊大小的選擇。 對文件進(jìn)行壓縮存儲可以提高內(nèi)存利用率，然而文件的壓縮和解壓需要耗費(fèi)一定系統(tǒng)時(shí)間和資源，這在一定程序上會降低系統(tǒng)的性能，因此需對文件進(jìn)行選擇性壓縮。具體方法是對文本等壓縮比例高的文件進(jìn)行壓縮存儲，對數(shù)據(jù)等壓縮比例低的文件，則選擇直接存儲。 另外，對文件數(shù)據(jù)塊大小的選擇也會影響內(nèi)存利用率。在EMFS中，文件數(shù)據(jù)存儲的基本單位是一個(gè)內(nèi)存數(shù)據(jù)真。這樣，每個(gè)文件的最后一個(gè)數(shù)據(jù)塊很可能會用不完，平均來看，每個(gè)文件會浪費(fèi)1/2個(gè)數(shù)據(jù)塊。在文件數(shù)據(jù)塊為1KB和2KB的情況下，我們測試得到內(nèi)存利用率分別為97.4%和94.8%。顯然，前者的利用率更高，這是因?yàn)槲募?shù)據(jù)塊越小，文件浪費(fèi)的空間越少。但是，文件數(shù)據(jù)塊不能設(shè)置得太小，否則系統(tǒng)在運(yùn)行過程中會產(chǎn)生很多碎片，導(dǎo)致系統(tǒng)性能的降低。 3 結(jié)論 本文提出了嵌入式系統(tǒng)下的一種大容量內(nèi)存文件系統(tǒng)的實(shí)現(xiàn)方案，并從文件的平均查找次數(shù)和系統(tǒng)內(nèi)存利用率等方面對文件系統(tǒng)進(jìn)行了測試和性能分析。測試結(jié)果表明，此系統(tǒng)具有較快的查找定位速度和較高的內(nèi)存利用率，所以本系統(tǒng)能夠有效地應(yīng)用于嵌入式系統(tǒng)，尤其是那些產(chǎn)生較多臨時(shí)文件或處理大容量數(shù)據(jù)的嵌入式系統(tǒng)。