- 相關(guān)推薦
大容量?jī)?nèi)存文件系統(tǒng)設(shè)計(jì)及μC/OS下的實(shí)現(xiàn)
摘要：針對(duì)某些嵌入式系統(tǒng)中處理數(shù)據(jù)量大和速度要求高的特點(diǎn)，提出一種應(yīng)用于嵌入式系統(tǒng)中的大容量?jī)?nèi)存文件系統(tǒng)的實(shí)現(xiàn)方案。該方案通過(guò)在內(nèi)存中建立文件系統(tǒng)，將臨時(shí)數(shù)據(jù)有效組織于內(nèi)存中，既提高訪問(wèn)速度又節(jié)省外存空間，因而能滿足要求；通過(guò)將其移植到μC/OS系統(tǒng)下，便可進(jìn)行性能測(cè)試和分析。結(jié)果表明，本內(nèi)存文件系統(tǒng)具有較高的查找效率和內(nèi)存利用率。引言
嵌入式系統(tǒng)憑借其特有的功能和資源占用量少的特點(diǎn)，在各個(gè)領(lǐng)域得到了越來(lái)越多的應(yīng)用。根據(jù)成本和設(shè)計(jì)的需要，一般的嵌入式系統(tǒng)都配置很少的外部存儲(chǔ)空間甚至不帶外部磁盤。但隨著用戶需求和功能復(fù)雜度的增加，越來(lái)越多的嵌入式系統(tǒng)需要處理大容量的數(shù)據(jù)，或者在運(yùn)行過(guò)程中會(huì)產(chǎn)生大量的臨時(shí)數(shù)據(jù)。一方面這些數(shù)據(jù)處理完后不能立即刪除；另一方面這些臨時(shí)文件不需要長(zhǎng)期保存。例如，用來(lái)上網(wǎng)沖浪的機(jī)頂盒設(shè)備在用戶瀏覽過(guò)程中不斷從互聯(lián)網(wǎng)上接收數(shù)據(jù)，因此用戶訪問(wèn)后的頁(yè)面很可能再次瀏覽，所不能將瀏覽后的網(wǎng)頁(yè)立即清除，當(dāng)然，系統(tǒng)不需要也不可能將所有瀏覽過(guò)的頁(yè)面保存于硬盤中。所以，處理數(shù)據(jù)量的增大給嵌入式系統(tǒng)的設(shè)計(jì)提供了新的要求。
一般來(lái)說(shuō)，嵌入式系統(tǒng)處理大容量臨時(shí)數(shù)據(jù)的有效方法是設(shè)計(jì)一個(gè)內(nèi)存文件系統(tǒng)存儲(chǔ)這些數(shù)據(jù)。內(nèi)存文件系統(tǒng)MFS（Memory File System）是一個(gè)在內(nèi)存中對(duì)文件實(shí)行按名存取的底層軟件。和普通磁盤文件系統(tǒng)相比，內(nèi)存文件系統(tǒng)具有存取速度快、可動(dò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平臺(tái)設(shè)計(jì)的，不適用于資源有限的嵌入式系統(tǒng)；其二，這些通用內(nèi)存文件系統(tǒng)的設(shè)計(jì)方案一般是利用內(nèi)存來(lái)模擬磁盤文件系統(tǒng)，在內(nèi)存中會(huì)建立文件系統(tǒng)緩沖區(qū)。這就是說(shuō)除了文件系統(tǒng)本身占據(jù)了內(nèi)存之外，磁盤緩沖區(qū)又會(huì)占所一些內(nèi)存，這些就會(huì)導(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)，最后對(duì)其性能進(jìn)行了分析和測(cè)試。
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對(duì)文件的主要管理方式為：
①文件的各個(gè)屬性單獨(dú)存儲(chǔ)在文件信息表（file status table）中；
②文件數(shù)據(jù)塊用鏈表來(lái)分配和管理，文件數(shù)據(jù)塊大小可以動(dòng)態(tài)改變，這樣可以避免在系統(tǒng)運(yùn)行過(guò)程中產(chǎn)生大量的碎片；
③為了提高文件的讀寫和查找速度，設(shè)置一個(gè)全局散列表（Hash表）作為文件的讀寫及查找入口；每個(gè)文件根據(jù)其文件名、文件長(zhǎng)度計(jì)算出一個(gè)Hash值；然后在Hash表找到文件對(duì)應(yīng)的Hash項(xiàng)，這樣就可以讀出文件的屬性和數(shù)據(jù)。
圖1表示了EMFS在內(nèi)存中的組織結(jié)構(gòu)。
每一個(gè)存儲(chǔ)于EMFS的文件在全局Hash表都有個(gè)對(duì)應(yīng)的入口項(xiàng)。其文件屬性和文件名、文件長(zhǎng)度、創(chuàng)建時(shí)間等存入文件狀態(tài)表，文件內(nèi)容存儲(chǔ)于從空閑塊鏈表申請(qǐng)到的數(shù)據(jù)塊中。文件的Hash表、狀態(tài)表和數(shù)據(jù)塊通過(guò)指針鏈接起來(lái)，如圖2所示，下面分別介紹文件系統(tǒng)的Hash表、狀態(tài)表和數(shù)據(jù)塊鏈表。
1.1 全局Hash表
（1）Hash值的產(chǎn)生
從圖2可看出，Hash表是整個(gè)文件系統(tǒng)讀寫和查找的入口，通過(guò)計(jì)算文件的Hash值來(lái)找到其在Hash表中的位置，從而訪問(wèn)文件狀態(tài)表和數(shù)據(jù)塊。因此文件系統(tǒng)的查找效率主體現(xiàn)在，如何通過(guò)文件信息計(jì)算其對(duì)應(yīng)的Hash值以及如何有效地組織Hash表。圖3表示了EMFS系統(tǒng)中Hash表的構(gòu)成情況，每個(gè)文件對(duì)應(yīng)8字節(jié)的Hash值。其中前2個(gè)字節(jié)是文件名長(zhǎng)度和文件名第一個(gè)字節(jié)的ASCII碼值，接下來(lái)的2個(gè)字節(jié)是文件名的16CRC（循環(huán)冗余校驗(yàn)編碼），最后4個(gè)字節(jié)文件名的32CRC編碼。這里為了減少同文件對(duì)應(yīng)相同Hash值的概率，文件名的Hash值中既包含了文件名的16CRC編碼又包含了32CRC編碼。
（2）Hash表的組織和查找
在獲得Hash值后，如何將8個(gè)字節(jié)的Hash值有效地組織在全局Hash表中來(lái)獲得最高的查找速度是一個(gè)關(guān)鍵問(wèn)題。根據(jù)數(shù)據(jù)結(jié)構(gòu)算法理論可知，將Hash表順序組織為一個(gè)有序表，可以通過(guò)折半查找法來(lái)獲得最高的查找效率。其比較次數(shù)最多為└log2n┘ 1（n為表中的記錄個(gè)數(shù)），其平均查找長(zhǎng)度ASL（Average Search Length）近似為log2(n 1)-1。然而，隨著文件的動(dòng)態(tài)增加或刪除，每個(gè)文件對(duì)應(yīng)的Hash值或大或小，這樣系統(tǒng)的Hash表并不能保證是一個(gè)順序表，因此就不能采用折半查找法。如果首先將無(wú)序的Hash表排列為有序表再采用折半法查找，那么即使在最好的情況下，排序操作所需要的時(shí)間復(fù)雜度也為O（nlogn），同時(shí)還需要其它的輔助存儲(chǔ)，這樣在排序操作上就要花費(fèi)大量的時(shí)間和存儲(chǔ)空間，使整個(gè)系統(tǒng)的查找效率大大降低。針對(duì)此不足，本文采用鏈地址法組織全局Hash表，將全局Hash表分為兩部分：其本表和溢出表。其基本思想為：首先分配一個(gè)固定大�。ㄟ@里假設(shè)取1024項(xiàng)）的順序表作為基本表，每個(gè)文件計(jì)算得出的Ha
【大容量?jī)?nèi)存文件系統(tǒng)設(shè)計(jì)及μC/OS下的實(shí)現(xiàn)】相關(guān)文章：
基于μC／OS-II的光盤伺服控制系統(tǒng)的設(shè)計(jì)03-18
大容量Flash存儲(chǔ)設(shè)備在水文遙測(cè)系統(tǒng)中的實(shí)現(xiàn)03-07
基于μC/OS-Ⅱ的變頻器變結(jié)構(gòu)控制系統(tǒng)設(shè)計(jì)03-18
256×32大容量中文矩陣系統(tǒng)的設(shè)計(jì)03-18
基于閃存的星載大容量存儲(chǔ)器的研究和實(shí)現(xiàn)03-18
基于μC/os-II的嵌入式多功能信號(hào)源的設(shè)計(jì)03-07
B2C 電子商務(wù)網(wǎng)站的設(shè)計(jì)與實(shí)現(xiàn)03-01