一、文件系統結構

磁盤的邏輯單元為塊，內存和磁盤之間的I/O傳輸以塊為單位執行。

磁盤的特點

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

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

文件系統需要提供高效快捷磁盤訪問，以便輕松存儲、定位、提取數據。即存儲文件、訪問文件

文件系統有兩個不同的設計問題

訪問問題：如何定義文件系統對用戶的接口

存儲問題：創建數據結構和算法，把邏輯文件系統映射到物理外存設備

文件系統本身通常由許多不同層組成。每層實際利用更低層功能，創建新的功能，以用于更高層的服務。

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

基礎文件系統只需向適當設備驅動程序發送命令。

邏輯文件系統通過文件控制塊維護文件結構。

文件控制塊（FCB）包含有關文件的信息，包括所有者、權限、文件內容的位置等。

大多數操作系統支持多種不同的文件系統，舉例：

CD-ROM ISO9660 文件格式

Unix 文件系統（Unix File System）

Windows文件系統：FAT（File Allocation Table），FAT32, FAT64,NTFS（Windows NT File System）

Linux 文件系統：可擴展文件系統（Extended file system），分布式文件系統（Distributed File System）

二、文件系統實現

1.概述

在磁盤上，文件系統包括的信息有

如何啟動存儲在那里操作系統

總的塊數

空閑塊的數目和位置

目錄結構

各個具體文件 等

上述許多結構會在之后詳細講述。這里簡述如下：

引導控制塊（每個卷）：可以包含從該卷引導操作系統的所需信息。如果磁盤不包括操作系統，則這塊的內容為空。UFS稱為引導塊（boot block），NFS稱為分區引導扇區（partition boot sector）

卷控制塊（每個卷）：包括卷的詳細信息（分區的塊數、塊的大小、空閑塊的數量和指針、空閑

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

每個文件的FCB包含該文件的許多詳細信息。他有一個唯一的標識號，以便與目錄條目相關聯

每個文件系統的目錄結構用于組織文件

內存中的信息用于管理文件系統并通過緩存來提高性能，這些數據在安裝文件裝系統時被加載，在文件系統操作期間被更新，在卸載是被卸載。這些結構類型包括：

每個進程的打開文件表：包括一個指向系統的打開文件表中合適條目的指針和其他信息

整個系統的打開文件表：包括每個打開文件的FCB副本和其他信息

創建一個新文件

應用程序調用邏輯文件系統。邏輯文件系統指導目錄結構的格式，它會分配一個新的FCB

系統將相應的目錄信息讀入內存

更新目錄結構和FCB

將結果寫回磁盤

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

首先搜索整個系統的打開文件表，查看是否已經被打開，如果是，則在該進程的打開文件表創建一個條目，并指向現有整個系統的打開文件表。

否則，根據文件名搜索目錄結構

找到后，它的FCB會復制到內存的整個系統的開放文件表中（該表還存放著打開該文件的進程數量） ，接下來，在該進程的打開文件表創建一個條目，并指向現有整個系統的打開文件表。

Open() 返回值：文件描述符是一個非負整數。它是一進程打開文件表的索引值，指向系統范圍內打開文件表相應條目

2.虛擬文件系統

操作系統如何才能將多個類型的文件系統集成到目錄結構中？用戶如何在訪問文件系統空間時，可以無縫地在文件系統類型間遷移？大多數操作系統采用面向對象的技術來簡化、組織、模塊化實現。

數據結構和程序用于隔離基本的操作系統調用的功能與實現細節。因此，文件系統的實現有三個主要層構成。

第一層為文件系統接口。

第二層為虛擬文件系統（VFS），把文件系統的通用操作和具體實現分開，虛擬文件系統提供了在唯一標識一個文件的機制。VFS基于vnode 的文件表示結構，它包含了一個數值標識符來唯一表示網絡上的一個文件。

VFS能區分不同本地文件系統

VFS能區分本地文件系統和遠程文件系統

三、目錄實現

1.線性列表

采用文件名稱和數據塊指針的線性列表

優點：編程簡單

缺點：因為需要搜索，運行較為費時

2.哈希表

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

優點：減少目錄搜索時間

缺點：兩個文件名哈希到相同的位置時可能發生沖突；因哈希表固定大小，創建文件需要哈希表重建時，比較麻煩。

四、磁盤空間的分配方法

1.連續分配

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

連續分配支持順序訪問和直接訪問

問題：當文件需要擴展，文件大小變大時會無法擴展

解決：找更大的連續空間，復制過去

基于擴展的連續分配方案?用以下參數來定義文件

開始地址

塊兒數

指向下一個擴展塊兒的指針（擴展塊兒可以是多個）

定義格式：

文件【開始地址，塊兒數，指向下一個擴展塊的指針】

2.鏈接分配

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

定義格式：【起始塊，結束塊】

同時，每個磁盤塊都有指向下一個磁盤塊的地址。

優點：沒有磁盤空間浪費

缺點：

不支持文件的直接訪問

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

鏈接分配的一個重要變種是文件分配表

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

目錄條目含有文件首塊號碼，通過這個塊號索引的FAT條目包含文件下一塊的號碼，這個鏈會繼續下去，直到最后一塊，最后一塊的表條目值為文件結束值。

3.索引分配

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

文件用索引塊來定義， 每個文件有其索引塊。

這里有一個問題，索引塊應為多大？

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

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

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

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

五、磁盤空閑空間的管理

1.位向量

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

2.鏈表

所有空閑塊用鏈表鏈接起來，并將指向第一個空閑塊兒的指針保存在特殊位置，同時緩存在內存。

每個塊兒含有下一個塊兒的指針

3.組

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

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

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

例：n=3

4.計數

基于以下事實：

通常有多個連續塊需要同時分配或釋放，尤其是在使用連續分配時。因此記錄

記錄第一塊的地址和緊跟第一塊的連續的空閑塊的數量。

空閑空間表的每個條目包括磁盤地址和數量

例：

六、文件系統的性能和效率

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

磁盤分配和目錄管理算法

保留在文件目錄條目中的數據類型

改善性能的方法：緩存

緩沖區緩存：一塊獨立內存，位于其中的塊是馬上需要使用的

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

板載高速緩存

如果沒有統一緩存，則會由下圖情況發生：

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

采用統一緩沖緩存

統一緩沖緩存：統一使用緩沖器緩存來緩存進程頁和文件數據。

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

文件的讀入或寫出一般是按順序進行。所以，不適合采用LRU算法，因為最近使用的頁面最后才會用甚至根本不會再用。

順序訪問可以通過馬上釋放和預先讀取來加以優化

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

預先讀取（read-ahead）：請求頁之后的下一個頁也一起讀入

七、文件系統的恢復

目錄信息一般事先保存在內存中以加快訪問，有時會導致目錄結構中的數據和磁盤塊中的數據不一致。

解決：

一致性檢查：比較目錄結構中的數據和磁盤塊中的數據，嘗試著去修正不一致

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

基于日志結構的文件系統

文件創建涉及到目錄結構修改，FCB分配，數據塊分配等

所有元數據（meta data）的變化寫入日志上，一旦這些修改寫到日志，就認為已經提交了。

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

當整個提交的事務已經完成時，就從日志中刪除事務條目

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

審核編輯：湯梓紅