文件系統(tǒng)的結(jié)構(gòu)及實(shí)現(xiàn)

Word文件系統(tǒng)的結(jié)構(gòu)及實(shí)現(xiàn)一、文件系統(tǒng)結(jié)構(gòu)

磁盤(pán)的邏輯單元為塊，內(nèi)存和磁盤(pán)之間的I/O傳輸以塊為單位執(zhí)行。

磁盤(pán)的特點(diǎn)

1可以原地重寫(xiě)，可以從磁盤(pán)上讀一塊兒，修改該塊，并將它寫(xiě)回到原來(lái)的位置

可以直接訪問(wèn)磁盤(pán)上的任意一塊。因此，可以方便地按順序或隨機(jī)訪問(wèn)文件

文件系統(tǒng)需要提供高效快捷磁盤(pán)訪問(wèn)，以便輕松存儲(chǔ)、定位、提取數(shù)據(jù)。即存儲(chǔ)文件、訪問(wèn)文件

文件系統(tǒng)有兩個(gè)不同的設(shè)計(jì)問(wèn)題

訪問(wèn)問(wèn)題：如何定義文件系統(tǒng)對(duì)用戶(hù)的接口

存儲(chǔ)問(wèn)題：創(chuàng)建數(shù)據(jù)結(jié)構(gòu)和（算法），把邏輯文件系統(tǒng)映射到物理外存設(shè)備

文件系統(tǒng)本身通常由許多不同層組成。每層實(shí)際利用更低層功能，創(chuàng)建新的功能，以用于更高層的服務(wù)。

設(shè)備驅(qū)動(dòng)程序可以作為翻譯器，他的輸入作為高級(jí)指令，輸出由底層的、（硬件）特定指令組成。

基礎(chǔ)文件系統(tǒng)只需向適當(dāng)設(shè)備驅(qū)動(dòng)程序發(fā)送命令。

邏輯文件系統(tǒng)通過(guò)文件控制塊維護(hù)文件結(jié)構(gòu)。

文件控制塊（FCB）包含有關(guān)文件的信息，包括所有者、權(quán)限、文件內(nèi)容的位置等。

大多數(shù)操作系統(tǒng)支持多種不同的文件系統(tǒng)，舉例：

CD-（ROM）ISO9660文件格式

Unix文件系統(tǒng)（UnixFileSystem）

Windows文件系統(tǒng)：FAT（FileAlloca（ti）onTable），F(xiàn)AT32,FAT64,NTFS（WindowsNTFileSystem）

（Linux）文件系統(tǒng)：可擴(kuò)展文件系統(tǒng)（Ex（te）ndedfilesystem），分布式文件系統(tǒng)（DistributedFileSystem）

二、文件系統(tǒng)實(shí)現(xiàn)

1.概述

在磁盤(pán)上，文件系統(tǒng)包括的信息有

如何啟動(dòng)存儲(chǔ)在那里（操作系統(tǒng)）

總的塊數(shù)

空閑塊的數(shù)目和位置

目錄結(jié)構(gòu)

各個(gè)具體文件等

上述許多結(jié)構(gòu)會(huì)在之后詳細(xì)講述。這里簡(jiǎn)述如下：

引導(dǎo)控制塊（每個(gè)卷）：可以包含從該卷引導(dǎo)操作系統(tǒng)的所需信息。如果磁盤(pán)不包括操作系統(tǒng)，則這塊的內(nèi)容為空。UFS稱(chēng)為引導(dǎo)塊（bootblock），NFS稱(chēng)為分區(qū)引導(dǎo)扇區(qū)（partitionbootsector）

卷控制塊（每個(gè)卷）：包括卷的詳細(xì)信息（分區(qū)的塊數(shù)、塊的大小、空閑塊的數(shù)量和指針、空閑

FCB的數(shù)量和指針等）。UFS稱(chēng)為超級(jí)塊兒（superblock）,NTFS主控文件表（masterbootsector）

每個(gè)文件的FCB包含該文件的許多詳細(xì)信息。他有一個(gè)唯一的標(biāo)識(shí)號(hào)，以便與目錄條目相關(guān)聯(lián)

每個(gè)文件系統(tǒng)的目錄結(jié)構(gòu)用于組織文件

內(nèi)存中的信息用于管理文件系統(tǒng)并通過(guò)緩存來(lái)提高性能，這些數(shù)據(jù)在安裝文件裝系統(tǒng)時(shí)被加載，在文件系統(tǒng)操作期間被更新，在卸載是被卸載。這些結(jié)構(gòu)類(lèi)型包括：

每個(gè)進(jìn)程的打開(kāi)文件表：包括一個(gè)指向系統(tǒng)的打開(kāi)文件表中合適條目的指針和其他信息

整個(gè)系統(tǒng)的打開(kāi)文件表：包括每個(gè)打開(kāi)文件的FCB副本和其他信息

創(chuàng)建一個(gè)新文件

應(yīng)用程序調(diào)用邏輯文件系統(tǒng)。邏輯文件系統(tǒng)指導(dǎo)目錄結(jié)構(gòu)的格式，它會(huì)分配一個(gè)新的FCB

系統(tǒng)將相應(yīng)的目錄信息讀入內(nèi)存

更新目錄結(jié)構(gòu)和FCB

將結(jié)果寫(xiě)回磁盤(pán)

一旦文件被創(chuàng)建，就能用于I/O，不過(guò)，首先他要被打開(kāi)。系統(tǒng)調(diào)用open()將文件名傳到邏輯文件系統(tǒng)，系統(tǒng)調(diào)用open()：

首先搜索整個(gè)系統(tǒng)的打開(kāi)文件表，查看是否已經(jīng)被打開(kāi)，如果是，則在該進(jìn)程的打開(kāi)文件表創(chuàng)建一個(gè)條目，并指向現(xiàn)有整個(gè)系統(tǒng)的打開(kāi)文件表。

否則，根據(jù)文件名搜索目錄結(jié)構(gòu)

找到后，它的FCB會(huì)復(fù)制到內(nèi)存的整個(gè)系統(tǒng)的開(kāi)放文件表中（該表還存放著打開(kāi)該文件的進(jìn)程數(shù)量），接下來(lái)，在該進(jìn)程的打開(kāi)文件表創(chuàng)建一個(gè)條目，并指向現(xiàn)有整個(gè)系統(tǒng)的打開(kāi)文件表。

Open()返回值：文件描述符是一個(gè)非負(fù)整數(shù)。它是一進(jìn)程打開(kāi)文件表的索引值，指向系統(tǒng)范圍內(nèi)打開(kāi)文件表相應(yīng)條目

2.虛擬文件系統(tǒng)

操作系統(tǒng)如何才能將多個(gè)類(lèi)型的文件系統(tǒng)集成到目錄結(jié)構(gòu)中？用戶(hù)如何在訪問(wèn)文件系統(tǒng)空間時(shí)，可以無(wú)縫地在文件系統(tǒng)類(lèi)型間遷移？大多數(shù)操作系統(tǒng)采用面向?qū)ο蟮募夹g(shù)來(lái)簡(jiǎn)化、組織、模塊化實(shí)現(xiàn)。

數(shù)據(jù)結(jié)構(gòu)和程序用于隔離基本的操作系統(tǒng)調(diào)用的功能與實(shí)現(xiàn)細(xì)節(jié)。因此，文件系統(tǒng)的實(shí)現(xiàn)有三個(gè)主要層構(gòu)成。

第一層為文件系統(tǒng)接口。

第二層為虛擬文件系統(tǒng)（VFS），把文件系統(tǒng)的通用操作和具體實(shí)現(xiàn)分開(kāi)，虛擬文件系統(tǒng)提供了在唯一標(biāo)識(shí)一個(gè)文件的機(jī)制。VFS基于vnode的文件表示結(jié)構(gòu)，它包含了一個(gè)數(shù)值標(biāo)識(shí)符來(lái)唯一表示（網(wǎng)絡(luò)）上的一個(gè)文件。

VFS能區(qū)分不同本地文件系統(tǒng)

VFS能區(qū)分本地文件系統(tǒng)和遠(yuǎn)程文件系統(tǒng)

三、目錄實(shí)現(xiàn)

1.線性列表

采用文件名稱(chēng)和數(shù)據(jù)塊指針的線性列表

優(yōu)點(diǎn)：（編程）簡(jiǎn)單

缺點(diǎn)：因?yàn)樾枰阉?，運(yùn)行較為費(fèi)時(shí)

2.哈希表

哈希表根據(jù)文件名得到一個(gè)值，并返回一個(gè)指向線性列表中元素的指針

優(yōu)點(diǎn)：減少目錄搜索時(shí)間

缺點(diǎn)：兩個(gè)文件名哈希到相同的位置時(shí)可能發(fā)生沖突；因哈希表固定大小，創(chuàng)建文件需要哈希表重建時(shí)，比較麻煩。

四、磁盤(pán)空間的分配方法

1.連續(xù)分配

每個(gè)文件在磁盤(pán)上占有一組連續(xù)的塊。

文件的連續(xù)分配可以用文件第一塊的磁盤(pán)地址和連續(xù)塊的數(shù)量（即長(zhǎng)度）來(lái)定義

連續(xù)分配支持順序訪問(wèn)和直接訪問(wèn)

問(wèn)題：當(dāng)文件需要擴(kuò)展，文件大小變大時(shí)會(huì)無(wú)法擴(kuò)展

解決：找更大的連續(xù)空間，復(fù)制過(guò)去

基于擴(kuò)展的連續(xù)分配方案

用以下參數(shù)來(lái)定義文件

開(kāi)始地址

塊兒數(shù)

指向下一個(gè)擴(kuò)展塊兒的指針（擴(kuò)展塊兒可以是多個(gè)）

定義格式：

文件【開(kāi)始地址，塊兒數(shù)，指向下一個(gè)擴(kuò)展塊的指針】

2.鏈接分配

每個(gè)文件是磁盤(pán)塊兒的鏈表，磁盤(pán)塊分布在磁盤(pán)的任何地方，文件有起始?jí)K和結(jié)束塊來(lái)定義

定義格式：【起始?jí)K，結(jié)束塊】

同時(shí)，每個(gè)磁盤(pán)塊都有指向下一個(gè)磁盤(pán)塊的地址。

優(yōu)點(diǎn)：沒(méi)有磁盤(pán)空間浪費(fèi)

缺點(diǎn)：

不支持文件的直接訪問(wèn)

需要更多的磁盤(pán)空間（來(lái)記錄指針）

鏈接分配的一個(gè)重要變種是文件分配表

每個(gè)卷的開(kāi)始部分用于存儲(chǔ)文件分配表(FileAllocationTable)，表中每個(gè)磁盤(pán)塊都有一個(gè)FAT條目，并可通過(guò)塊號(hào)索引。（未使用的塊為0，使用的塊包含下一個(gè)塊兒號(hào)）

目錄條目含有文件首塊號(hào)碼，通過(guò)這個(gè)塊號(hào)索引的FAT條目包含文件下一塊的號(hào)碼，這個(gè)鏈會(huì)繼續(xù)下去，直到最后一塊，最后一塊的表?xiàng)l目值為文件結(jié)束值。

3.索引分配

通過(guò)將所有指針?lè)旁谝黄?，即索引塊

文件用索引塊來(lái)定義，每個(gè)文件有其索引塊。

這里有一個(gè)問(wèn)題，索引塊應(yīng)為多大？

每個(gè)文件必須有一個(gè)索引塊，因此索引塊應(yīng)盡可能小，然而不能太小，否則放不下足夠多的指針，為處理這個(gè)問(wèn)題，有如下一些機(jī)制：

鏈接方案：為了處理大文件，可以將多個(gè)索引塊鏈接起來(lái)

多層次索引：用第一層索引塊指向一組第二層的索引塊，第二層索引塊再指向文件塊

組合方案：用于基于UNIX的文件系統(tǒng)，將索引塊的前15個(gè)指針存儲(chǔ)在文件的i-node中。其中，前12個(gè)指針指向直接塊，剩下3個(gè)指針指向間接塊

五、磁盤(pán)空閑空間的管理

1.位向量

空閑空間表實(shí)現(xiàn)為位圖,或位向量，每塊用一位（bit）表示。1表示塊空閑；0表示塊已分配

2.鏈表

所有空閑塊用鏈表鏈接起來(lái)，并將指向第一個(gè)空閑塊兒的指針保存在特殊位置，同時(shí)緩存在內(nèi)存。

每個(gè)塊兒含有下一個(gè)塊兒的指針

3.組

將n個(gè)空閑塊的地址保存在第一個(gè)空閑塊中。

這些空閑塊中的前n－1個(gè)為空，而最后一塊包含另外n個(gè)空閑塊的地址。

比鏈表好的是空閑塊的地址可以很快找到，而且可以明確一段連續(xù)空閑塊空間

例：n=3

4.計(jì)數(shù)

基于以下事實(shí)：

通常有多個(gè)連續(xù)塊需要同時(shí)分配或釋放，尤其是在使用連續(xù)分配時(shí)。因此記錄

記錄第一塊的地址和緊跟第一塊的連續(xù)的空閑塊的數(shù)量。

空閑空間表的每個(gè)條目包括磁盤(pán)地址和數(shù)量

例：

六、文件系統(tǒng)的性能和效率

磁盤(pán)空間的有效使用（效率），取決于

磁盤(pán)分配和目錄管理算法

保留在文件目錄條目中的數(shù)據(jù)類(lèi)型

改善性能的方法：緩存

緩沖區(qū)緩存：一塊獨(dú)立內(nèi)存，位于其中的塊是馬上需要使用的

頁(yè)面緩存：將文件數(shù)據(jù)作為頁(yè)而不是塊來(lái)緩存。頁(yè)面緩存使用虛擬內(nèi)存技術(shù)，將文件數(shù)據(jù)作為頁(yè)來(lái)緩存，比采用物理磁盤(pán)塊來(lái)緩存更高效

板載高速緩存

如果沒(méi)有統(tǒng)一緩存，則會(huì)由下圖情況發(fā)生：

系統(tǒng)調(diào)用re（ad）()和write()會(huì)通過(guò)緩沖區(qū)緩存，然而，內(nèi)存映射調(diào)用需要使用兩個(gè)緩存，即頁(yè)面緩存和緩沖區(qū)緩存。內(nèi)存映射先從文件系統(tǒng)中讀入磁盤(pán)塊,并放入緩沖區(qū)緩存，由于虛擬內(nèi)存系統(tǒng)沒(méi)有緩沖區(qū)緩存接口，緩沖緩存內(nèi)的文件必須復(fù)制到頁(yè)面緩存中。

采用統(tǒng)一緩沖緩存

統(tǒng)一緩沖緩存：統(tǒng)一使用緩沖器緩存來(lái)緩存進(jìn)程頁(yè)和文件數(shù)據(jù)。

無(wú)論是緩存塊還是頁(yè)面都有置換問(wèn)題，

文件的讀入或?qū)懗鲆话闶前错樞蜻M(jìn)行。所以，不適合采用LRU算法，因?yàn)樽罱褂玫捻?yè)面最后才會(huì)用甚至根本不會(huì)再用。

順序訪問(wèn)可以通過(guò)馬上釋放和預(yù)先讀取來(lái)加以?xún)?yōu)化

馬上釋放（free-behind）：請(qǐng)求下一頁(yè)時(shí)，馬上釋放上一頁(yè)

預(yù)先讀取（read-ahead）：請(qǐng)求頁(yè)之后的下一個(gè)頁(yè)也一起讀入

七、文件系統(tǒng)的恢復(fù)

目錄信息一般事先保存在內(nèi)存中以加快訪問(wèn)，有時(shí)會(huì)導(dǎo)致目錄結(jié)構(gòu)中的數(shù)據(jù)和磁盤(pán)塊中的數(shù)據(jù)不一致。

解決：

一致性檢查：比較目錄結(jié)構(gòu)中的數(shù)據(jù)和磁盤(pán)塊中的數(shù)據(jù)，嘗試著去修正不一致

備份&恢復(fù)：I.備份（backup）：利用系統(tǒng)程序來(lái)備份數(shù)據(jù)到其他的存儲(chǔ)設(shè)備。軟盤(pán)，磁帶II.恢復(fù)（recovery）：通過(guò)從備份來(lái)恢復(fù)丟失的文件或磁盤(pán)

基于日志結(jié)構(gòu)的文件系統(tǒng)