有趣

有用

有態(tài)

設(shè)計(jì)文件系統(tǒng)思路

這一篇文章是帶大家思考，fatfs文件系統(tǒng)是怎樣逐步發(fā)展而來(lái)的，如果你是文件系統(tǒng)的設(shè)計(jì)者，你會(huì)怎么設(shè)計(jì)?希望從這個(gè)思考的過(guò)程，幫助大家掌握f(shuō)atfs里面的一些基本概念。

要設(shè)計(jì)一種文件系統(tǒng)，說(shuō)白了就是要實(shí)現(xiàn)一種文件名與文件數(shù)據(jù)的映射，也就是給定一個(gè)文件名后，就能找到它所對(duì)應(yīng)的映射。這看似簡(jiǎn)單，事實(shí)上卻不簡(jiǎn)單。要考慮的問(wèn)題很多，比如數(shù)據(jù)的不連續(xù)存儲(chǔ)、存儲(chǔ)空間的有效利用等等。

這里我們從簡(jiǎn)單的實(shí)現(xiàn)算法開始思考，一步步逼近fatfs的設(shè)計(jì)思想。

原始文件系統(tǒng)

存儲(chǔ)設(shè)備(flsh、軟盤、硬盤)上面是由很多順序分布的扇區(qū)所構(gòu)成的，文件里面的內(nèi)容就存儲(chǔ)在這些扇區(qū)上面，最簡(jiǎn)單的算法，就是在先在扇區(qū)里面存儲(chǔ)文件名，然后在文件名的后面存儲(chǔ)對(duì)應(yīng)數(shù)據(jù)。其他文件用同樣的方法依次存儲(chǔ)，最終文件系統(tǒng)里面的的布局如下圖所示:

這種儲(chǔ)存文件的方法，有一定的優(yōu)點(diǎn)，比如說(shuō)算法簡(jiǎn)單，沒(méi)有任何的空間浪費(fèi)，數(shù)據(jù)的儲(chǔ)存十分緊湊等等。但是致命的缺點(diǎn)就是文件的搜索效率太低，每次查找文件的時(shí)候，遍歷全部的扇區(qū)顯然是非常愚蠢的辦法。

改進(jìn)方案一

把文件名全部保存在扇區(qū)的起始位置，這樣就能避免對(duì)整個(gè)扇區(qū)的搜索了，如下圖

可以看到，這里已經(jīng)出現(xiàn)了一些內(nèi)存空間的浪費(fèi)，但這個(gè)是必然會(huì)存在的，空間換時(shí)間。另外的一個(gè)缺點(diǎn)是，現(xiàn)在文件的保存只能在連續(xù)的扇區(qū)保存，一旦小文件被刪除之后，它騰出來(lái)的內(nèi)存空間將不足以用來(lái)儲(chǔ)存其他一些大文件。我們可以把它理解為"磁盤碎片"

改進(jìn)方案二

要讓數(shù)據(jù)可以跨扇區(qū)儲(chǔ)存，又要知道各部分?jǐn)?shù)據(jù)的具體存儲(chǔ)位置，該如何實(shí)現(xiàn)呢?這時(shí)候我們應(yīng)該想起鏈表這種數(shù)據(jù)結(jié)構(gòu)，因?yàn)殒湵砭褪菍ｉT針對(duì)非連續(xù)空間存儲(chǔ)的。我們可以在每個(gè)扇區(qū)的頭部都設(shè)置一個(gè)專門的字段來(lái)記錄扇區(qū)所屬文件以及下一個(gè)扇區(qū)的地址，這樣讀取某一個(gè)扇區(qū)之后，就能知道下一個(gè)扇區(qū)在什么位置了。

這樣，就能把"磁盤碎片"空間也拼湊起來(lái)使用了。只是現(xiàn)在我們定位一個(gè)文件的時(shí)候，還是得逐個(gè)扇區(qū)地讀一下文件名，效率依然很低。

改進(jìn)方案三

我們要解決遍歷扇區(qū)的"惡夢(mèng)"，就必須把文件名剝離出來(lái)，不能讓隨意地保存在扇區(qū)里面。否則永遠(yuǎn)擺脫不了遍歷扇區(qū)的結(jié)局。我們現(xiàn)在回想一下，之所要把文件名保存在扇區(qū)上，無(wú)非是因?yàn)樾枰课募麕椭覀兌ㄎ坏轿募奈恢谩?

這其實(shí)跟我們看書非常相類似，我們拿到一本書，如果想找到某一個(gè)章節(jié)的內(nèi)容，一個(gè)笨方法就是逐頁(yè)地翻書，直到我們找到這個(gè)章節(jié)的名字。只不過(guò)這個(gè)笨方法我們都不喜歡用，我們直接通過(guò)書本前幾頁(yè)的目錄就能得到目標(biāo)章節(jié)的位置了。

我們模仿書的目錄一樣，拿出一些扇區(qū)專門用來(lái)記錄文件名和它對(duì)應(yīng)的數(shù)據(jù)其實(shí)位置。這樣一來(lái)，當(dāng)我們想到查找某些文件內(nèi)容時(shí)，就查一下這個(gè)"目錄"就可以了。這個(gè)"目錄"我們把它叫做文件索引表。如下圖:

改進(jìn)方案四

現(xiàn)在每個(gè)扇區(qū)的頭部還有一個(gè)專門的字段來(lái)記錄扇區(qū)所屬文件以及下一個(gè)扇區(qū)的地址，這個(gè)字段我們也把它剝離出來(lái)集中管理，像文件索引表一樣，也用一些扇區(qū)來(lái)保存，這樣子會(huì)顯得整個(gè)文件系統(tǒng)，架構(gòu)更加的清晰，管理更加方便。這些用來(lái)保扇區(qū)關(guān)系的扇區(qū)，在fatfs里面就叫做FAT(File Allocation Table)表，如下圖:

改進(jìn)方案五

當(dāng)磁盤里面的扇區(qū)數(shù)量非常多的時(shí)候，它們之間的鏈?zhǔn)疥P(guān)系會(huì)非常復(fù)雜，F(xiàn)AT表需要白白消耗很多內(nèi)存來(lái)儲(chǔ)存它們，為了減小扇區(qū)間鏈?zhǔn)疥P(guān)系的復(fù)雜度，我們可以把多個(gè)扇區(qū)合并成一個(gè)新的儲(chǔ)存單位。這樣一來(lái)，新的儲(chǔ)存單位間的鏈?zhǔn)疥P(guān)系就會(huì)簡(jiǎn)化很多。在fat32文件系統(tǒng)里面，這種新的儲(chǔ)存單位稱為簇。

總結(jié)

到這里，通過(guò)一個(gè)對(duì)文件系統(tǒng)不斷迭代優(yōu)化的過(guò)程，就把fatfs的基本概念，通俗易懂地介紹給大家了。希望大家能夠深刻理解下面這幾個(gè)概念的含義:

• 文件索引表
• FAT表
• 簇