摘要：文章探討了基于嵌入式文件系統(tǒng)的記錄數(shù)據(jù)存儲(chǔ)和檢索的設(shè)計(jì)方法，首先簡(jiǎn)單介紹了嵌入式文件系統(tǒng)的基本知識(shí)和實(shí)現(xiàn)原理，接著簡(jiǎn)要概述Nor Flash和Nand Flash區(qū)別，針對(duì)嵌入式系統(tǒng)中對(duì)文件系統(tǒng)的可靠性以及訪問(wèn)存儲(chǔ)速度的特殊要求，重點(diǎn)介紹本研究課題的整體設(shè)計(jì)方案、映射表原理和鏈表原理，以及利用映射表和鏈表來(lái)實(shí)現(xiàn)記錄數(shù)據(jù)快速存儲(chǔ)和檢索的設(shè)計(jì)原理。

關(guān)鍵詞：快速存儲(chǔ)；快速檢索；文件系統(tǒng)；嵌入式系統(tǒng)；映射表

中圖分類號(hào)：TP317 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-2374（2012）04-0109-03

隨著嵌入式技術(shù)的發(fā)展以及在各種電子產(chǎn)品中的廣泛應(yīng)用，數(shù)據(jù)存儲(chǔ)管理已經(jīng)成為嵌入式系統(tǒng)中一個(gè)重

要而深遠(yuǎn)的研究課題，由此誕生了嵌入式文件系統(tǒng)。

嵌入式文件系統(tǒng)是嵌入式系統(tǒng)中重要組成部分，它構(gòu)成了嵌入式系統(tǒng)上所有數(shù)據(jù)基礎(chǔ)，是系統(tǒng)中龐大復(fù)雜且又是最為基本和重要的資源。那么如何在文件系統(tǒng)上實(shí)現(xiàn)用戶記錄數(shù)據(jù)的快速可靠存儲(chǔ)與檢索是本文的研究重點(diǎn)。

一、文件系統(tǒng)定義

文件系統(tǒng)（File System）是系統(tǒng)的一個(gè)重要組成部分，通過(guò)對(duì)所管理的存儲(chǔ)空間的抽象，向用戶提供統(tǒng)一的、對(duì)象化的訪問(wèn)接口，屏蔽對(duì)物理設(shè)備的直接操作和資源管理。從系統(tǒng)角度來(lái)看，文件系統(tǒng)是對(duì)文件存儲(chǔ)器空間進(jìn)行組織和分配，負(fù)責(zé)文件的存儲(chǔ)并對(duì)存入的文件進(jìn)行保護(hù)和檢索的系統(tǒng)。具體地說(shuō)，它負(fù)責(zé)

為用戶建立文件，存入、讀出、修改、轉(zhuǎn)儲(chǔ)文件，控制文件的存取，當(dāng)用戶不再使用時(shí)刪除文件等。

二、嵌入式文件系統(tǒng)

嵌入式文件系統(tǒng)中，F(xiàn)lash作為一種流行的存儲(chǔ)設(shè)備，F(xiàn)lash存儲(chǔ)器具有速度快、容量大、成本低等很多優(yōu)點(diǎn)，因此大部分嵌入式系統(tǒng)都是把文件系統(tǒng)建立在Flash存儲(chǔ)器之上。

Flash存儲(chǔ)器主要有Nor Flash和Nand Flash兩種類型。目前，針對(duì)Nor Flash設(shè)計(jì)的文件系統(tǒng)JFFS/JFFS2在嵌入式系統(tǒng)中已得到廣泛的應(yīng)用；隨著Nand作為大容量存儲(chǔ)介質(zhì)的普及，基于Nand閃存的文件系統(tǒng)YAFFS(Yet Another Flash File System)正逐漸被應(yīng)用到嵌入式系統(tǒng)中。

Nor屬于芯片內(nèi)執(zhí)行(XIP, eXecute In Place)的讀取，和我們常見(jiàn)的SDRAM的讀取是一樣，用戶可以直接運(yùn)行裝載在Nor Flash里面的代碼，Nand Flash沒(méi)有采取內(nèi)存的隨機(jī)讀取技術(shù)，它的讀取是以一次讀取一塊的形式來(lái)進(jìn)行的，通常是一次讀取512個(gè)字節(jié)，采用這種技術(shù)的Flash比較廉價(jià)，用戶不能直接運(yùn)行Nand Flash上的代碼。

針對(duì)Flash的特點(diǎn)，文件系統(tǒng)設(shè)計(jì)時(shí)還需要重點(diǎn)考慮Flash的損耗平衡、糾錯(cuò)和壞塊處理問(wèn)題。通常Nand中每個(gè)塊的最大擦寫(xiě)次數(shù)是一百萬(wàn)次，而Nor的擦寫(xiě)次數(shù)是十萬(wàn)次。如果某塊擦除次數(shù)超過(guò)壽命次數(shù)，容易導(dǎo)致壞塊。所謂壞塊并不是整個(gè)塊都?jí)牧?，可能只是塊中一位或某幾位損壞。Nand器件中的壞塊在出廠就有，且是隨機(jī)分布的。Nor正常不存在該問(wèn)題。Nand器件需要對(duì)介質(zhì)進(jìn)行初始化掃描以發(fā)現(xiàn)壞塊，并將壞塊標(biāo)記為不可用。所有Flash器件都受位交換現(xiàn)象的困擾，一位的變化可能不很明顯，但是如果發(fā)生在一個(gè)關(guān)鍵文件上，這個(gè)小小的故障可能導(dǎo)致系統(tǒng)停機(jī)。理論上Nand比Nor更容易受到影響。

由于這些特殊性，所以在Flash這樣的設(shè)備上建立文件系統(tǒng)以及在文件系統(tǒng)上實(shí)現(xiàn)記錄數(shù)據(jù)存儲(chǔ)和檢索的方法將直接影響嵌入式系統(tǒng)的運(yùn)行性能和客戶體驗(yàn)，具有深遠(yuǎn)的研究意義。

三、設(shè)計(jì)方案

（一）設(shè)計(jì)說(shuō)明

文件系統(tǒng)操作是以文件為單位，從系統(tǒng)角度來(lái)看，文件系統(tǒng)是對(duì)文件存儲(chǔ)器空間進(jìn)行組織和分配，負(fù)責(zé)文件存儲(chǔ)并對(duì)存入的文件進(jìn)行保護(hù)和檢索的系統(tǒng)。具體地說(shuō)，它負(fù)責(zé)為用戶建立文件，存入、讀出、修改、轉(zhuǎn)儲(chǔ)文件，控制文件的存取，當(dāng)用戶不再使用時(shí)刪除文件等操作。

根據(jù)文件系統(tǒng)的以上原理，本設(shè)計(jì)以文件為存儲(chǔ)體對(duì)象，同時(shí)分配有一個(gè)與文件長(zhǎng)度相等的映射內(nèi)存，在映射內(nèi)存上構(gòu)建記錄的存儲(chǔ)結(jié)構(gòu)，所有存儲(chǔ)、檢索、刪除等操作首要都是在映射內(nèi)存中完成，只有在需要更新時(shí)候才需要將部分?jǐn)?shù)據(jù)更新到文件，避免頻繁且大數(shù)據(jù)量讀寫(xiě)文件，實(shí)現(xiàn)記錄數(shù)據(jù)的快速存儲(chǔ)與檢索。

（二）結(jié)構(gòu)圖

（三）存儲(chǔ)結(jié)構(gòu)

記錄的存儲(chǔ)是以文件為存儲(chǔ)體對(duì)象，因此需要在文件的映射內(nèi)存中構(gòu)建存儲(chǔ)結(jié)構(gòu)，如圖1所示，存儲(chǔ)結(jié)構(gòu)包括：頭信息、映射表和記錄區(qū)組成。頭信息主要用來(lái)存儲(chǔ)記錄相關(guān)信息，如總記錄容量、已存記錄數(shù)，剩余記錄容量，鏈表信息等信息；映射表主要是描述記錄與位置編號(hào)之間的關(guān)系；記錄區(qū)就是用來(lái)存儲(chǔ)真正的記錄數(shù)據(jù)。

（四）頭信息

頭信息主要用來(lái)存儲(chǔ)記錄相關(guān)信息，如文件大小、總記錄容量、已存記錄數(shù)、剩余記錄容量、記錄域信息、記錄鏈表信息、空閑鏈表信息等信息，如圖2所示。通過(guò)頭信息可以快速獲取當(dāng)前記錄文件的信息，以便快速統(tǒng)計(jì)和存儲(chǔ)操作。

（五）映射表和鏈表

映射表主要是描述記錄與位置編號(hào)之間的關(guān)系，以及通過(guò)鏈表的方式構(gòu)建記錄與記錄編號(hào)之間的關(guān)系，如圖3所示，映射表是以鏈表節(jié)點(diǎn)為單位組成的，鏈表節(jié)點(diǎn)通過(guò)鏈表的方式串接起來(lái)。

鏈表主要用于管理記錄數(shù)據(jù)，每一個(gè)記錄就是一個(gè)小數(shù)據(jù)塊單元，用鏈表將這些單元串接起來(lái)。鏈表有鏈表節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)對(duì)應(yīng)一個(gè)記錄位置編號(hào)，每個(gè)節(jié)點(diǎn)信息分為2部分，包含前向指針和后向指針，前向指針填充當(dāng)前節(jié)點(diǎn)的前一個(gè)記錄位置編號(hào)，后向指針填充當(dāng)前節(jié)點(diǎn)的后一個(gè)記錄位置編號(hào)（這里所指的前一個(gè)和后一個(gè)是邏輯上意義，非物理上排列）。

記錄位置編號(hào)：是指記錄區(qū)各個(gè)記錄的位置編號(hào)，如有N個(gè)記錄，從編號(hào)從1-N。

鏈表節(jié)點(diǎn)編號(hào)：鏈表節(jié)點(diǎn)編號(hào)與記錄位置編號(hào)一樣，是一一對(duì)應(yīng)的。

記錄編號(hào)：是指一個(gè)記錄在鏈表中的邏輯位置，也就是該記錄屬于記錄鏈表的從鏈表頭開(kāi)始的第幾個(gè)節(jié)點(diǎn)。

從頭信息可以看出，有2個(gè)鏈表信息（即2條鏈表）：記錄鏈表信息和空閑鏈表信息，記錄鏈表是將已存儲(chǔ)的記錄串接起來(lái)，空閑鏈表是將空閑的記錄串接起來(lái)；記錄鏈表信息的前向指針指向0，后項(xiàng)指針指向第1個(gè)記錄編號(hào)的記錄位置編號(hào)（鏈表節(jié)點(diǎn)編號(hào)），該鏈表節(jié)點(diǎn)編號(hào)所對(duì)應(yīng)鏈表節(jié)點(diǎn)信息的后項(xiàng)指針又指向下一個(gè)記錄位置編號(hào)（鏈表節(jié)點(diǎn)編號(hào)），直到結(jié)束；空閑鏈表信息的前向指針指向0，后項(xiàng)指針指向第1個(gè)空閑記錄編號(hào)的記錄位置編號(hào)（鏈表節(jié)點(diǎn)編號(hào)），該鏈表節(jié)點(diǎn)編號(hào)所對(duì)應(yīng)鏈表節(jié)點(diǎn)信息的后項(xiàng)指針又指向下一個(gè)記錄位置編號(hào)（鏈表節(jié)點(diǎn)編號(hào)），直到結(jié)束；。

計(jì)算記錄在映射內(nèi)存中的地址：根據(jù)記錄編號(hào)去推算記錄鏈表信息后項(xiàng)指針，得到記錄位置編號(hào)，根據(jù)（（記錄位置編號(hào)-1）×記錄長(zhǎng)度）得到記錄地址偏移量，（記錄地址偏移量+映射內(nèi)存地址）得到記錄在映射內(nèi)存中的地址。

（六）記錄區(qū)和域信息

記錄區(qū)就是用來(lái)存儲(chǔ)真正的記錄數(shù)據(jù)，因此記錄區(qū)將劃分成等分的記錄單元，每個(gè)記錄單元存儲(chǔ)一個(gè)記錄數(shù)據(jù)，每個(gè)記錄數(shù)據(jù)可由多個(gè)數(shù)據(jù)域組成，如排序域等，通過(guò)排序域，可以將記錄按照指定的規(guī)則進(jìn)行排序，具體由頭信息字段中域信息決定，如圖4

所示。

域信息包括：域個(gè)數(shù)和各域描述：

域個(gè)數(shù)：用于表示記錄所組成的域個(gè)數(shù)；

域描述：用于描述記錄的各域組成，以及每個(gè)域的屬性和最大長(zhǎng)度；域?qū)傩钥蓞⒖紙D5所示位圖表示。

（七）記錄操作

通過(guò)以上原理介紹,可以快速進(jìn)行記錄數(shù)據(jù)的存儲(chǔ)、刪除、查找等操作，因?yàn)橛涗洈?shù)據(jù)是通過(guò)映射表和鏈表來(lái)管理，通過(guò)映射表和鏈表檢索就可以快速定位記錄數(shù)據(jù)，無(wú)需去讀取實(shí)際記錄數(shù)據(jù)，考慮到數(shù)據(jù)存取的效率，每一個(gè)記錄文件都對(duì)應(yīng)有一個(gè)與之大小相等映射內(nèi)存，文件中的數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)是同

步的。

當(dāng)讀取一個(gè)記錄數(shù)據(jù)時(shí)，可以直接訪問(wèn)內(nèi)存中的內(nèi)容，而無(wú)需去訪問(wèn)文件，提高數(shù)據(jù)讀取效率。

當(dāng)存儲(chǔ)一個(gè)記錄數(shù)據(jù)時(shí)，只需要通過(guò)空閑鏈表獲取一個(gè)空閑記錄位置編號(hào)，根據(jù)記錄位置編號(hào)計(jì)算記錄所在映射內(nèi)存中地址，將數(shù)據(jù)存儲(chǔ)到所在地址，接著將該鏈表節(jié)點(diǎn)掛接到記錄鏈表中，并支持按指定的域排序，更新記錄數(shù)，最后將內(nèi)存中的數(shù)據(jù)更新到文件中，當(dāng)然無(wú)需將整個(gè)內(nèi)存數(shù)據(jù)更新到文件中，只需要更新頭信息、映射表和該記錄數(shù)據(jù)，大大提高文件更新速度，同時(shí)降低Flash存儲(chǔ)器的擦寫(xiě)次數(shù)，延長(zhǎng)產(chǎn)品的壽命。

當(dāng)刪除一個(gè)記錄數(shù)據(jù)時(shí)，只需要通過(guò)記錄鏈表查找到鏈表節(jié)點(diǎn)，刪除記錄鏈表中該記錄節(jié)點(diǎn)，接著掛接到空閑鏈表中，更新記錄數(shù)，最后將內(nèi)存中的數(shù)據(jù)更新到文件中，當(dāng)然無(wú)需將整個(gè)內(nèi)存數(shù)據(jù)更新到文件中，只需要更新頭信息、映射表，大大提高文件更新速度，同時(shí)降低Flash存儲(chǔ)器的擦寫(xiě)次數(shù)，延長(zhǎng)產(chǎn)品的壽命。

當(dāng)檢索一個(gè)記錄數(shù)據(jù)時(shí)，只需要通過(guò)記錄鏈表查找到鏈表節(jié)點(diǎn)，獲取記錄位置編號(hào)，根據(jù)記錄位置編號(hào)計(jì)算記錄所在地址，接著根據(jù)域信息，判斷該記錄是否為符合要求的記錄，如此將可快速找到需要的記錄。

四、軟件架構(gòu)

數(shù)據(jù)庫(kù)式存儲(chǔ)驅(qū)動(dòng)模塊實(shí)現(xiàn)結(jié)構(gòu)化的數(shù)據(jù)記錄在文件系統(tǒng)上的存取，并在此基礎(chǔ)上實(shí)現(xiàn)數(shù)據(jù)記錄的排序、插入、增加以及刪除等功能，該程序模塊的軟件框圖如下圖6所示。每種數(shù)據(jù)庫(kù)占用一個(gè)文件，每一個(gè)文件都對(duì)應(yīng)有一個(gè)與之大小相等映射內(nèi)存，文件中的數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)是同步的，當(dāng)應(yīng)用層需讀/寫(xiě)數(shù)據(jù)庫(kù)文件時(shí)，均要通過(guò)映射內(nèi)存進(jìn)行中轉(zhuǎn)；即寫(xiě)數(shù)據(jù)庫(kù)文件前需先將數(shù)據(jù)保存在映射內(nèi)存中，再?gòu)挠成鋬?nèi)存寫(xiě)回?cái)?shù)據(jù)庫(kù)文件；反之，讀數(shù)據(jù)記錄時(shí)只需要讀取映射內(nèi)存中的數(shù)據(jù)。

驅(qū)動(dòng)對(duì)上層應(yīng)用程序提供了增加記錄、刪除記錄、插入記錄等API接口，屏蔽驅(qū)動(dòng)實(shí)現(xiàn)細(xì)節(jié)，同時(shí)上層應(yīng)用程序可以通過(guò)數(shù)據(jù)庫(kù)注冊(cè)信息表注冊(cè)多個(gè)文件及文件信息，底層驅(qū)動(dòng)通過(guò)數(shù)據(jù)庫(kù)注冊(cè)模塊獲取應(yīng)用層注冊(cè)的文件信息來(lái)實(shí)現(xiàn)多個(gè)文件管理。

五、結(jié)語(yǔ)

本研究課題提供了一種嵌入式系統(tǒng)中數(shù)據(jù)存儲(chǔ)和管理的方法，該方法不僅適用于以文件系統(tǒng)文件為存儲(chǔ)對(duì)象的嵌入式系統(tǒng)，對(duì)于直接以Flash存儲(chǔ)器為存儲(chǔ)對(duì)象的嵌入式系統(tǒng)也具有較高指導(dǎo)意義，只要將對(duì)文件讀寫(xiě)操作更換為對(duì)Flash的讀寫(xiě)操作。

參考文獻(xiàn)

[1] 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [M]．清華大學(xué)出版社，2011．

[2] 杜春雷．ARM體系結(jié)構(gòu)與編程[M]．清華大學(xué)出版社，2010．

[3] JEAN J.ABROSSE著，邵貝貝譯．UC/OS-II源碼公開(kāi)的實(shí)時(shí)嵌入式操作系統(tǒng)[M]．中國(guó)電力出版社，2001．

[4]SST公司Nor Flash芯片手冊(cè)．SST Nor Flash Datasheet．

[5]SUMSUNG公司Nand Flash芯片手冊(cè)，Sumsung Nand Flash Datasheet．

作者簡(jiǎn)介：葉德焰，廈門雅迅網(wǎng)絡(luò)股份有限公司中級(jí)工程師，研究方向：嵌入式文件系統(tǒng)。

（責(zé)任編輯：劉 艷）