- 相關推薦
大容量內存文件系統設計及μC/OS下的實現
摘要：針對某些嵌入式系統中處理數據量大和速度要求高的特點，提出一種應用于嵌入式系統中的大容量內存文件系統的實現方案。該方案通過在內存中建立文件系統，將臨時數據有效組織于內存中，既提高訪問速度又節省外存空間，因而能滿足要求；通過將其移植到μC/OS系統下，便可進行性能測試和分析。結果表明，本內存文件系統具有較高的查找效率和內存利用率。關鍵詞：嵌入式系統內存文件系統大容量存儲μC/OS
引言
嵌入式系統憑借其特有的功能和資源占用量少的特點，在各個領域得到了越來越多的應用。根據成本和設計的需要，一般的嵌入式系統都配置很少的外部存儲空間甚至不帶外部磁盤。但隨著用戶需求和功能復雜度的增加，越來越多的嵌入式系統需要處理大容量的數據，或者在運行過程中會產生大量的臨時數據。一方面這些數據處理完后不能立即刪除；另一方面這些臨時文件不需要長期保存。例如，用來上網沖浪的機頂盒設備在用戶瀏覽過程中不斷從互聯網上接收數據，因此用戶訪問后的頁面很可能再次瀏覽，所不能將瀏覽后的網頁立即清除，當然，系統不需要也不可能將所有瀏覽過的頁面保存于硬盤中。所以，處理數據量的增大給嵌入式系統的設計提供了新的要求。
一般來說，嵌入式系統處理大容量臨時數據的有效方法是設計一個內存文件系統存儲這些數據。內存文件系統MFS（MemoryFileSystem）是一個在內存中對文件實行按名存取的底層軟件。和普通磁盤文件系統相比，內存文件系統具有存取速度快、可動態改變文件系統大小和數據掉電即丟失的優點，因此它適用于高速的臨時數據處理。Linux下的Tmpfs、Proc文件系統以及Freebsd下的MFS都是一種內存文件系統。但是，這些通用操作系統上的內存文件系統不能夠直接運用于到嵌入式系統中：其一，它們都是為資源豐富的通用PC平臺設計的，不適用于資源有限的嵌入式系統；其二，這些通用內存文件系統的設計方案一般是利用內存來模擬磁盤文件系統，在內存中會建立文件系統緩沖區。這就是說除了文件系統本身占據了內存之外，磁盤緩沖區又會占所一些內存，這些就會導致內存的浪費和利用率的下降。根據上述考慮，本文設計了一適合于嵌放式大容量數據處理的嵌入式內存文件系統EMFS（FmbeddedMomoryFileSystem）。文中首先闡述了EMFS嵌入式系統的設計要點，隨后討論了如果將其移植到μC/OS系統，最后對其性能進行了分析和測試。
1EMFS的設計
從前面分析得知，本文設計的EMFS不采用通用文件系統的磁盤設計方法，如Linux系統的Ext2節點結構和Windows的FAT結構。EMFS對文件的主要管理方式為：
①文件的各個屬性單獨存儲在文件信息表（filestatustable）中；
②文件數據塊用鏈表來分配和管理，文件數據塊大小可以動態改變，這樣可以避免在系統運行過程中產生大量的碎片；
③為了提高文件的讀寫和查找速度，設置一個全局散列表（Hash表）作為文件的讀寫及查找入口；每個文件根據其文件名、文件長度計算出一個Hash值；然后在Hash表找到文件對應的Hash項，這樣就可以讀出文件的屬性和數據。
圖1表示了EMFS在內存中的組織結構。
每一個存儲于EMFS的文件在全局Hash表都有個對應的入口項。其文件屬性和文件名、文件長度、創建時間等存入文件狀態表，文件內容存儲于從空閑塊鏈表申請到的數據塊中。文件的Hash表、狀態表和數據塊通過指針鏈接起來，如圖2所示，下面分別介紹文件系統的Hash表、狀態表和數據塊鏈表。
1.1全局Hash表
（1）Hash值的產生
從圖2可看出，Hash表是整個文件系統讀寫和查找的入口，通過計算文件的Hash值來找到其在Hash表中的位置，從而訪問文件狀態表和數據塊。因此文件系統的查找效率主體現在，如何通過文件信息計算其對應的Hash值以及如何有效地組織Hash表。圖3表示了EMFS系統中Hash表的構成情況，每個文件對應8字節的Hash值。其中前2個字節是文件名長度和文件名第一個字節的ASCII碼值，接下來的2個字節是文件名的16CRC（循環冗余校驗編碼），最后4個字節文件名的32CRC編碼。這里為了減少同文件對應相同Hash值的概率，文件名的Hash值中既包含了文件名的16CRC編碼又包含了32CRC編碼。
（2）Hash表的組織和查找
在獲得Hash值后，如何將8個字節的Hash值有效地組織在全局Hash表中來獲得最高的查找速度是一個關鍵問題。根據數據結構算法理論可知，將Hash表順序組織為一個有序表，可以通過折半查找法來獲得最高的查找效率。其比較次數最多為└log2n┘+1（n為表中的記錄個數），其平均查找長度ASL（AverageSearchLength）近似為log2(n+1)-1。然而，隨著文件的動態增加或刪除，每個文件對應的Hash值或大或小，這樣系統的Hash表并不能保證是一個順序表，因此就不能采用折半查找法。如果首先將無序的Hash表排列為有序表再采用折半法查找，那么即使在最好的情況下，排序操作所需要的時間復雜度也為O（nlogn），同時還需要其它的輔助存儲，這樣在排序操作上就要花費大量的時間和存儲空間，使整個系統的查找效率大大降低。針對此不足，本文采用鏈地址法組織全局Hash表，將全局Hash表分為兩部分：其本表和溢出表。其基本思想為：首先分配一個固定大小（這里假設取1024項）的順序表作為基本表，每個文件計算得出的Hash值通過對1024取模得到個介于0～1023之間的模值。如果此模值在基本表中的對應項沒有被占用，那么該項就作為此文件的Hash項；如果此模值在基本表中的對應項已被其它文件占用，那么就溢出表中申請一個此文件的Hash項，并將此Hash項鏈接到具有相同模值的鏈表中。通過這種順序表和鏈表相結合的結構，既會影響查找速度又不會增加額外存儲空間，從而提高EMFS的查找效率而且不增加系統的時間和空間復雜度。
1.2文件狀態表
文件狀態表用來存放文件系統中文件的各個屬性，包括文件名稱、文件大小、讀寫標志、創建和修改時間。同時，為了提高內存空間的利用率，可以對文件進行選擇性壓縮存儲，因此文件狀態表也包括文件壓縮標志，壓縮前的原始大小和壓縮后的文件大小。從圖2可以看到，文件狀態表是和Hash表以及數據塊鏈表連在一起的，那么一旦定位到文件對應的Hash項，就可以對文件狀態表進行讀寫。
1.3數據塊鏈表
在EMFS中，文件數據內容保存在內存數據塊中，內存數據塊的大小可以在建立文件系統時動態設定。數據塊鏈表的作用是對內存塊進行管理。由于數據塊鏈表中每一項對應一個內存塊，所以當添加文件時，系統根據文件大小動態地從數據塊鏈表中申請一定數量的數據塊；當刪除文件時，系統將數據塊插入到此鏈表中。
2EMFS在μC/OS系統下的實現和性能分析
2.1EMFS是μC/OS下的實現流程
μC/OS是一個多任務的實時性嵌入式操作系統，得到了廣泛的使用。μC/OS公開了它的實時性內核源碼，同時提供了內存管理的接口和函數。通過在其實時內核的基礎上進行少量的修改，便可將EMFS移植到μC/OS系統中。圖4是EMFS在μC/OS下的初始化流程。
初始化完畢后，在μC/OS系統中建立EMFS的三主要數據結構，隨后就可以向EMFS中讀寫文件并進行測試。圖5和圖6分別是讀寫文件的流程。
2.2EMFS的性能測試與分析
通過將EMFS移植到μC/OS系統，便可以對EMFS的性能進行分析。前面提到，EMFS的主要特點是有效高的查找速度和內存利用率。現在，從這兩方面分別對EMFS進行性能測試和分析比較。
（1）平均查找次數
通過加入8000個平均長度為20KB的文件到EMFS中，這可以在對全局Hash表的基本表設定不同大小的情況下，隨機地讀出一定數量的文件來統計EMFS的平均查找次數。這里設定基本表的大小分別為1024和2048，讀出文件數量分別為500、1000、2000、4000和8000個，平均查找次數的統計結果具體如表1所列。
讀出文件數
查找次數
基本表項數500100020004000800010241.2041.4891.9422.9744.90420481.0981.2311.4651.9662.95
從表1可以分析出以下幾點：
①8000個文件全部讀出所需的平均查找次數最多不到5次；而當Hash表采用順序表時，使用拆半查找法得到的平均查找次數為└log28000┘+1=13次，可見EMFS的查找效率非常高，而且它不增加時間和空間的復雜度。
②讀出的文件數量越少，平均查找次數越少。因為文件是隨機選擇的，故讀出的文件越少，它們對應的Hash值在基本表中越分散，因而比較次數相應較少。
③基本表包含的Hash項越多，EMFS的平均查找次數越少。這是因為基本表越大，Hash值取模后落在基本表的概率就越大，因此比較的次數就越少。但要注意一點，在實際應用中基本表并不是設置得越大越好，基本表設置得越大，相應地溢出表就越小。當把溢出表項用完之后，基本表可以還沒有用完，但這時已經不能夠再添加文件了，這樣系統效率反而會降低。
（2）內存利用率
EMFS的內存利用率可以從兩個方面來表現：一對文件進行選擇性壓縮的機制；二是內存數據塊大小的選擇。
對文件進行壓縮存儲可以提高內存利用率，然而文件的壓縮和解壓需要耗費一定系統時間和資源，這在一定程序上會降低系統的性能，因此需對文件進行選擇性壓縮。具體方法是對文本等壓縮比例高的文件進行壓縮存儲，對數據等壓縮比例低的文件，則選擇直接存儲。
另外，對文件數據塊大小的選擇也會影響內存利用率。在EMFS中，文件數據存儲的基本單位是一個內存數據真。這樣，每個文件的最后一個數據塊很可能會用不完，平均來看，每個文件會浪費1/2個數據塊。在文件數據塊為1KB和2KB的情況下，我們測試得到內存利用率分別為97.4%和94.8%。顯然，前者的利用率更高，這是因為文件數據塊越小，文件浪費的空間越少。但是，文件數據塊不能設置得太小，否則系統在運行過程中會產生很多碎片，導致系統性能的降低。
3結論
本文提出了嵌入式系統下的一種大容量內存文件系統的實現方案，并從文件的平均查找次數和系統內存利用率等方面對文件系統進行了測試和性能分析。測試結果表明，此系統具有較快的查找定位速度和較高的內存利用率，所以本系統能夠有效地應用于嵌入式系統，尤其是那些產生較多臨時文件或處理大容量數據的嵌入式系統。
【大容量內存文件系統設計及μC/OS下的實現】相關文章：
MicroC/OS-II在80C196上的移植實現08-19
基于閃存的星載大容量存儲器的研究和實現08-06
256×32大容量中文矩陣系統的設計08-06
基于μC/OS的嵌入式系統應用開發研究08-19