一、文件系統(tǒng)結(jié)構(gòu)
磁盤的邏輯單元為塊，內(nèi)存和磁盤之間的I/O傳輸以塊為單位執(zhí)行。
磁盤的特點(diǎn)
1可以原地重寫，可以從磁盤上讀一塊兒，修改該塊，并將它寫回到原來的位置
可以直接訪問磁盤上的任意一塊。因此，可以方便地按順序或隨機(jī)訪問文件
文件系統(tǒng)需要提供高效快捷磁盤訪問，以便輕松存儲(chǔ)、定位、提取數(shù)據(jù)。即存儲(chǔ)文件、訪問文件
文件系統(tǒng)有兩個(gè)不同的設(shè)計(jì)問題
訪問問題：如何定義文件系統(tǒng)對(duì)用戶的接口
存儲(chǔ)問題：創(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)通過文件控制塊維護(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)包括的信息有
如何啟動(dòng)存儲(chǔ)在那里操作系統(tǒng)
總的塊數(shù)
空閑塊的數(shù)目和位置
目錄結(jié)構(gòu)
各個(gè)具體文件 等
上述許多結(jié)構(gòu)會(huì)在之后詳細(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稱為超級(jí)塊兒（super block）,NTFS主控文件表（master boot sector）
每個(gè)文件的FCB包含該文件的許多詳細(xì)信息。他有一個(gè)唯一的標(biāo)識(shí)號(hà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)的格式，它會(huì)分配一個(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會(huì)復(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)識(shí)一個(gè)文件的機(jī)制。VFS基于vnode 的文件表示結(jié)構(gòu)，它包含了一個(gè)數(shù)值標(biāo)識(shí)符來唯一表示網(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í)會(huì)無法擴(kuò)展
解決：找更大的連續(xù)空間，復(fù)制過去
基于擴(kuò)展的連續(xù)分配方案 用以下參數(shù)來定義文件
開始地址
塊兒數(shù)
指向下一個(gè)擴(kuò)展塊兒的指針（擴(kuò)展塊兒可以是多個(gè)）
定義格式：
文件【開始地址，塊兒數(shù)，指向下一個(gè)擴(kuò)展塊的指針】
2.鏈接分配
每個(gè)文件是磁盤塊兒的鏈表，磁盤塊分布在磁盤的任何地方，文件有起始?jí)K和結(jié)束塊來定義
定義格式：【起始?jí)K，結(jié)束塊】
同時(shí)，每個(gè)磁盤塊都有指向下一個(gè)磁盤塊的地址。
優(yōu)點(diǎn)：沒有磁盤空間浪費(fèi)
缺點(diǎn)：
不支持文件的直接訪問
需要更多的磁盤空間（來記錄指針）
鏈接分配的一個(gè)重要變種是文件分配表
每個(gè)卷的開始部分用于存儲(chǔ)文件分配表(File Allocation Table)，表中每個(gè)磁盤塊都有一個(gè)FAT條目，并可通過塊號(hào)索引。（未使用的塊為0，使用的塊包含下一個(gè)塊兒號(hào)）
目錄條目含有文件首塊號(hào)碼，通過這個(gè)塊號(hào)索引的FAT條目包含文件下一塊的號(hào)碼，這個(gè)鏈會(huì)繼續(xù)下去，直到最后一塊，最后一塊的表?xiàng)l目值為文件結(jié)束值。
3.索引分配
通過將所有指針放在一起，即索引塊
文件用索引塊來定義， 每個(gè)文件有其索引塊。
這里有一個(gè)問題，索引塊應(yīng)為多大？
每個(gè)文件必須有一個(gè)索引塊，因此索引塊應(yīng)盡可能小，然而不能太小，否則放不下足夠多的指針，為處理這個(gè)問題，有如下一些機(jī)制：
鏈接方案：為了處理大文件，可以將多個(gè)索引塊鏈接起來
多層次索引：用第一層索引塊指向一組第二層的索引塊，第二層索引塊再指向文件塊
組合方案：用于基于UNIX的文件系統(tǒng)，將索引塊的前15個(gè)指針存儲(chǔ)在文件的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)一緩存，則會(huì)由下圖情況發(fā)生：
系統(tǒng)調(diào)用read()和write()會(huì)通過緩沖區(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ū)懗鲆话闶?/span>按順序進(jìn)行。所以，不適合采用LRU算法，因?yàn)樽罱褂玫捻撁孀詈蟛艜?huì)用甚至根本不會(huì)再用。
順序訪問可以通過馬上釋放和預(yù)先讀取來加以優(yōu)化
馬上釋放（free-behind）：請求下一頁時(shí)，馬上釋放上一頁
預(yù)先讀取（read-ahead）：請求頁之后的下一個(gè)頁也一起讀入
七、文件系統(tǒng)的恢復(fù)
目錄信息一般事先保存在內(nèi)存中以加快訪問，有時(shí)會(huì)導(dǎo)致目錄結(jié)構(gòu)中的數(shù)據(jù)和磁盤塊中的數(shù)據(jù)不一致。
解決：
一致性檢查：比較目錄結(jié)構(gòu)中的數(shù)據(jù)和磁盤塊中的數(shù)據(jù)，嘗試著去修正不一致
備份&恢復(fù)：I. 備份（backup）：利用系統(tǒng)程序來備份數(shù)據(jù)到其他的存儲(chǔ)設(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í)行。
文章來源于網(wǎng)絡(luò)。