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

一、文件系統(tǒng)結(jié)構(gòu)

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

磁盤的特點(diǎn)

1可以原地重寫，可以從磁盤上讀一塊兒，修改該塊，并將它寫回到原來的位置

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

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

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

訪問問題：如何定義文件系統(tǒng)對用戶的接口

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

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

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

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

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

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

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

CD-ROM ISO9660 文件格式

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

Windows文件系統(tǒng)：FAT（File Allocation Table），F(xiàn)AT32, FAT64,NTFS（Windows NT File System）

Linux 文件系統(tǒng)：可擴(kuò)展文件系統(tǒng)（Extended file system），分布式文件系統(tǒng)（Distributed File System）

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

1.概述

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

如何啟動存儲在那里操作系統(tǒng)

總的塊數(shù)

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

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

各個(gè)具體文件 等

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

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

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

FCB 的數(shù)量和指針等）。UFS稱為超級塊兒（super block）,NTFS主控文件表（master boot sector）

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

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

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

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

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

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

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

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

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

將結(jié)果寫回磁盤

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

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

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

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

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

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

操作系統(tǒng)如何才能將多個(gè)類型的文件系統(tǒng)集成到目錄結(jié)構(gòu)中？用戶如何在訪問文件系統(tǒng)空間時(shí)，可以無縫地在文件系統(tǒng)類型間遷移？大多數(shù)操作系統(tǒng)采用面向?qū)ο蟮募夹g(shù)來簡化、組織、模塊化實(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)分開，虛擬文件系統(tǒng)提供了在唯一標(biāo)識一個(gè)文件的機(jī)制。VFS基于vnode 的文件表示結(jié)構(gòu)，它包含了一個(gè)數(shù)值標(biāo)識符來唯一表示網(wǎng)絡(luò)上的一個(gè)文件。

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

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

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

1.線性列表

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

優(yōu)點(diǎ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í)，比較麻煩。

四、磁盤空間的分配方法

1.連續(xù)分配

每個(gè)文件在磁盤上占有一組連續(xù)的塊。?文件的連續(xù)分配可以用文件第一塊的磁盤地址和連續(xù)塊的數(shù)量（即長度）來定義

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

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

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

基于擴(kuò)展的連續(xù)分配方案?用以下參數(shù)來定義文件

開始地址

塊兒數(shù)

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

定義格式：

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

2.鏈接分配

每個(gè)文件是磁盤塊兒的鏈表，磁盤塊分布在磁盤的任何地方，文件有起始塊和結(jié)束塊來定義

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

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

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

缺點(diǎn)：

不支持文件的直接訪問

需要更多的磁盤空間（來記錄指針）

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

每個(gè)卷的開始部分用于存儲文件分配表(File Allocation Table)，表中每個(gè)磁盤塊都有一個(gè)FAT條目，并可通過塊號索引。（未使用的塊為0，使用的塊包含下一個(gè)塊兒號）

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

3.索引分配

通過將所有指針放在一起，即索引塊

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

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

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

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

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

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

五、磁盤空閑空間的管理

1.位向量

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

2.鏈表

所有空閑塊用鏈表鏈接起來，并將指向第一個(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è)條目包括磁盤地址和數(shù)量

例：

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

磁盤空間的有效使用（效率），取決于

磁盤分配和目錄管理算法

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

改善性能的方法：緩存

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

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

板載高速緩存

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

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

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

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

無論是緩存塊還是頁面都有置換問題，

文件的讀入或?qū)懗鲆话闶前错樞蜻M(jìn)行。所以，不適合采用LRU算法，因?yàn)樽罱褂玫捻撁孀詈蟛艜蒙踔粮静粫儆谩?/p>

順序訪問可以通過馬上釋放和預(yù)先讀取來加以優(yōu)化

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

預(yù)先讀?。╮ead-ahead）：請求頁之后的下一個(gè)頁也一起讀入

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

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

解決：

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

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

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

文件創(chuàng)建涉及到目錄結(jié)構(gòu)修改，F(xiàn)CB分配，數(shù)據(jù)塊分配等

所有元數(shù)據(jù)（meta data）的變化寫入日志上，一旦這些修改寫到日志，就認(rèn)為已經(jīng)提交了。

提交了的事務(wù)，并不一定馬上完成操作

當(dāng)整個(gè)提交的事務(wù)已經(jīng)完成時(shí)，就從日志中刪除事務(wù)條目

如果系統(tǒng)崩潰，日志文件可能還存在事務(wù)，它包含的任何事務(wù)雖然已經(jīng)由操作系統(tǒng)提交了，但還沒有完成到文件系統(tǒng)，必須重新執(zhí)行。

審核編輯：湯梓紅