文件系統(tǒng)實現(xiàn)

文件系統(tǒng)實現(xiàn)112.1文件系統(tǒng)結(jié)構(gòu)操作系統(tǒng)通過文件系統(tǒng)來存儲、定位、提取數(shù)據(jù)，文件系統(tǒng)存在于輔助存儲器中—磁盤文件系統(tǒng)設(shè)計的兩個問題如何定義對用戶的接口。如定義文件及其屬性、文件所允許的操作、組織文件的目錄結(jié)構(gòu)創(chuàng)建數(shù)據(jù)結(jié)構(gòu)和算法來將邏輯文件系統(tǒng)映射到物理外存設(shè)備上文件系統(tǒng)按層組織文件控制塊FCB：由一個文件的相關(guān)信息組成的存儲結(jié)構(gòu)，如擁有者、許可、文件內(nèi)容的位置2分層設(shè)計的文件系統(tǒng)設(shè)備驅(qū)動程序,中斷處理程序，實現(xiàn)內(nèi)存與磁盤之間的信息轉(zhuǎn)移向設(shè)備驅(qū)動程序發(fā)送命令以對磁盤上的物理塊進行讀寫邏輯地址=>物理地址管理元數(shù)據(jù)(目錄結(jié)構(gòu),FCB)3二、文件系統(tǒng)的類型FAT文件系統(tǒng)（MS-DOS文件系統(tǒng)、msdos）

它是MS-DOS操作系統(tǒng)使用的文件系統(tǒng)，它也能由Windows98/NT、linux、SCOUNIX等操作系統(tǒng)訪問。文件地址以FAT表結(jié)構(gòu)存放，文件目錄32B，文件名為8個基本名加上一個“.”和3個字符擴展名。FAT32文件系統(tǒng)（vfat）它是Windows98使用的擴展的DOS文件系統(tǒng)，它在MS-DOS文件系統(tǒng)基礎(chǔ)上增加了對長文件名（最多到256B）支持。NTFS（NT文件系統(tǒng)）它是WindowsNT操作系統(tǒng)使用的文件系統(tǒng)，它具有很強的安全特性和文件系統(tǒng)恢復(fù)功能，可以處理巨大的存儲媒體，支持多種文件系統(tǒng)。S51K/S52K（sysv）

它是AT&TUNIXSV操作系統(tǒng)使用的1KB/2KB文件系統(tǒng)。4文件系統(tǒng)的類型ext2（二級擴展文件系統(tǒng)）它是Linux操作系統(tǒng)使用的高性能磁盤文件系統(tǒng)，它是對Minux操作系統(tǒng)中使用的文件系統(tǒng)擴展（ext）的擴展。它支持256字符的文件名，最大可支持到4TB的文件系統(tǒng)大小。HPFS（高性能文件系統(tǒng)、hpfs）

它是OS/2操作系統(tǒng)使用的文件系統(tǒng)。CD-ROM文件系統(tǒng)(iso9660)它是符合ISO9660標(biāo)準(zhǔn)的支持CD-ROM的文件系統(tǒng)，它有HighsierraCD-ROM和RockRidgeCD-ROM二種類型。UDF通用磁盤格式文件系統(tǒng)

UDF(UniversalDiskFormat)文件系統(tǒng)是依據(jù)光學(xué)儲存技術(shù)協(xié)會（OpticalStorageTechnologyAssociation,OSTA）的通用磁盤格式文件系統(tǒng)規(guī)格1.02版所制定的。它提供了對UDF格式媒體的只讀訪問（例如DVD光盤）。Windows98提供對UDF文件系統(tǒng)支持。5三、操作系統(tǒng)(Windows98/NT、Linux)

對多種文件系統(tǒng)的支持WindowsNT多重文件系統(tǒng)

WindowsNT支持FAT文件系統(tǒng)、NTFS、HPFS、CD-ROM文件系統(tǒng)等多種文件系統(tǒng)。WindowsNT執(zhí)行體內(nèi)I/O系統(tǒng)分成I/O管理程序、文件系統(tǒng)驅(qū)動程序和盤驅(qū)動程序三層，不同的文件系統(tǒng)采用不同的文件系統(tǒng)驅(qū)動程序，系統(tǒng)用動態(tài)連接庫對這些文件系統(tǒng)進行裝入和卸出并適宜于將來的擴展，WindowsNT分層驅(qū)動程序如下圖所示。

WindowsNT磁盤管理器窗口顯示某臺微機硬盤各分區(qū)安裝的多種文件系統(tǒng)如下圖所示，圖中所示硬盤有二個分區(qū)，C盤是FAT文件系統(tǒng)，D盤是NTFS文件系統(tǒng)，E盤是CD-ROM文件系統(tǒng)。6WindowsNT多重文件系統(tǒng)-1WindowsNT分層驅(qū)動程序I/O管理程序

FAT驅(qū)動程序

NTFS驅(qū)動程序

HPFS驅(qū)動程序軟盤驅(qū)動程序硬盤驅(qū)動程序7WindowsNT多重文件系統(tǒng)-28Linux虛擬文件系統(tǒng)VFSLinux采用虛擬文件系統(tǒng)VFS支持許多不同類型的文件系統(tǒng)，VFS是物理系統(tǒng)與服務(wù)之間的一個接口層，它屏蔽各類文件系統(tǒng)的差異，給用戶和程序提供一個統(tǒng)一的接口。Linux支持ext、ext2、msdos、vfat、iso9660、hpfs等多種文件系統(tǒng)。使用命令mkfs創(chuàng)建各類文件系統(tǒng)。VFS是物理文件系統(tǒng)與服務(wù)之間的一個接口，它對Linux的每一個文件系統(tǒng)的所有細節(jié)進行抽象，使得不同的文件系統(tǒng)在Linux內(nèi)核以及系統(tǒng)中運行的其它進程看來都是相同的，嚴(yán)格說來VFS并不上一種實際的文件系統(tǒng)，它只存在于內(nèi)存中，不存在于任何外存空間，VFS在系統(tǒng)啟動時建立，在系統(tǒng)關(guān)閉時消亡。VSF使Linux同時安裝支持不同類型的文件系統(tǒng)成為可能。912.2文件系統(tǒng)實現(xiàn)磁盤結(jié)構(gòu)如何啟動所存儲的操作系統(tǒng)、總的塊數(shù)、空閑塊的數(shù)目和位置、目錄結(jié)構(gòu)以及各個具體文件等。內(nèi)存結(jié)構(gòu)用于文件系統(tǒng)管理和通過緩存來提高性能10磁盤結(jié)構(gòu)引導(dǎo)控制塊,包括系統(tǒng)從該分區(qū)引導(dǎo)操作系統(tǒng)所需要的信息引導(dǎo)塊（UFS）,分區(qū)引導(dǎo)扇區(qū)（NTFS）分區(qū)控制塊包括分區(qū)詳細信息(如塊數(shù),塊的大小，空閑塊的數(shù)量和指針，空閑FCB的數(shù)量和指針等)超級塊

（UFS）,主控文件表

（NTFS）目錄結(jié)構(gòu)：用來組織文件FCB結(jié)構(gòu)索引結(jié)點

（UFS）11一個典型的FCB12內(nèi)存結(jié)構(gòu)內(nèi)存分區(qū)表：包含所有安裝分區(qū)的信息內(nèi)存目錄結(jié)構(gòu)：用來保存近來訪問過的目錄信息系統(tǒng)范圍的打開文件表,包括每個打開文件的FCB拷貝打開數(shù)單個進程的打開文件表,包括

指向系統(tǒng)范圍打開文件表的指針讀寫位置13open系統(tǒng)調(diào)用調(diào)用open將文件名傳給文件系統(tǒng)，當(dāng)打開文件時，根據(jù)給定文件名來搜索目錄結(jié)構(gòu)一旦找到文件，其FCB就復(fù)制到系統(tǒng)范圍的打開文件表在單個進程的打開文件表中會增加一個條目調(diào)用open返回一個指向單個進程的打開文件表中合適條目的指針文件描述符（UNIX）,文件句柄（Windows）14close系統(tǒng)調(diào)用關(guān)閉文件時，刪除一個相應(yīng)的單個進程打開文件表的條目系統(tǒng)范圍內(nèi)打開文件表的打開數(shù)也會遞減當(dāng)打開數(shù)為0時，更新的文件信息會復(fù)制到磁盤的目錄結(jié)構(gòu)中，系統(tǒng)范圍的打開文件表的條目也將刪除15內(nèi)存中的文件系統(tǒng)結(jié)構(gòu)a打開文件b讀文件16分區(qū)與安裝一個磁盤可以分成多個分區(qū)引導(dǎo)信息包括如何啟動一個特定操作系統(tǒng)可以裝多個操作系統(tǒng)雙啟動引導(dǎo)裝入程序,位于引導(dǎo)區(qū),可理解多個文件系統(tǒng)和多個操作系統(tǒng)bootmanagerinOS/2GRUB,LILOinLinux17安裝根分區(qū)：包括操作系統(tǒng)內(nèi)核或其它系統(tǒng)文件，在引導(dǎo)時裝入內(nèi)存。其它分區(qū)根據(jù)不同操作系統(tǒng)可以在引導(dǎo)時自動裝入或在此之后手動裝入裝入表：注明文件系統(tǒng)已裝入和該文件系統(tǒng)的類型。Windows系統(tǒng)將分區(qū)裝入在獨立名稱空間中，名稱用字母和冒號表示邏輯磁盤(e.g.“F:”)Linux可以將文件系統(tǒng)裝在任何目錄上。18虛擬文件系統(tǒng)虛擬文件系統(tǒng)（VFS)提供一個面向?qū)ο蟮奈募到y(tǒng)實現(xiàn)方法，以允許不同文件系統(tǒng)類型可以通過同樣結(jié)構(gòu)來實現(xiàn)VFS允許不同類型的文件系統(tǒng)使用相同的系統(tǒng)調(diào)用接口API作為VFS接口要好于規(guī)定的文件系統(tǒng)類型19VFS示意圖第一層文件系統(tǒng)接口，包括open，read，write和close調(diào)用及文件描述符第二層VFS層，目的：1將文件系統(tǒng)通用操作和具體實現(xiàn)分開2VFS是基于稱為vnode的文件表示結(jié)構(gòu)，該結(jié)構(gòu)包括一個數(shù)值指定者以表示位于整個網(wǎng)絡(luò)范圍內(nèi)的唯一文件。因此，VFS區(qū)分本地文件和遠程文件2012.3目錄實現(xiàn)為了實現(xiàn)用戶對文件的按名存取，系統(tǒng)必須首先利用用戶提供的文件名，對文件目錄進行查詢，找出該文件的文件控制塊FCB，然后根據(jù)找到的FCB中所記錄的文件物理地址，并根據(jù)文件物理組織方式找出文件的盤塊號，進而換算出文件在磁盤上的物理位置（柱面號、磁頭號、扇區(qū)號），最后啟動磁盤驅(qū)動程序，將所需文件讀入內(nèi)存。對目錄查詢的技術(shù)有兩種：線性檢索法和Hash法。21目錄實現(xiàn)線性列表—包括存儲文件名、指向數(shù)據(jù)塊的指針采用線性搜索來查找特定條目，容易編程耗CPU的執(zhí)行時間許多操作系統(tǒng)采用軟件緩存來存儲最近訪問過的目錄信息，緩存命中避免不斷地從磁盤讀取信息哈希表—有著哈希數(shù)據(jù)結(jié)構(gòu)的線性表減少目錄的搜索時間沖突：兩個名字映射到同樣的位置固定大小和哈希函數(shù)對大小的依賴性2212.4分配方法分配方法指出如何為文件分配磁盤塊常用的方法有：連續(xù)分配鏈接分配索引分配23磁盤空間的連續(xù)分配24一、

連續(xù)分配每一個文件占用一個連續(xù)的磁盤塊的集合簡單：只需要起始塊號和長度支持順序訪問和直接訪問為新文件找到空間，動態(tài)存儲分配問題首次適應(yīng)和最佳適應(yīng)外部碎片文件不能擴展文件需要多少空間比較難估計25許多新的文件系統(tǒng)使用一種修正的連續(xù)分配方法首先分配一塊連續(xù)空間，當(dāng)空間不夠時，另一塊被稱為擴展的連續(xù)空間會添加到原來的分配中。文件塊的位置就成為開始地址、塊數(shù)、加上一個指向下一擴展的指針擴展太大內(nèi)部碎片不同大小的擴展的分配和刪除外部碎片26二、鏈接分配每個文件是磁盤塊的鏈表：磁盤塊可以分散在磁盤的任何地方目錄包括文件第一塊的指針和最后一塊的指針pointerblock=27鏈接分配簡單：只需要起始地址優(yōu)點沒有外部碎片，沒有磁盤空間浪費，無需合并磁盤空間缺點無法隨機存取，只能有效的用于文件的順序訪問指針需要空間將多個塊組成簇，并按簇分配。增加了內(nèi)部碎片指針分布在整個磁盤上，可能失去或損壞28鏈接分配文件分配表(FAT)是鏈接分配方法的一個變種FAT–用于MS-DOSandOS/2操作系統(tǒng)每個分區(qū)的開始部分用于存儲該FAT表。每塊都在該表中有一項，該表可通過塊號碼來索引。FAT的使用與鏈表類似FAT可能導(dǎo)致大量的磁頭尋道時間通常對FAT采用緩存(在內(nèi)存中)改善了隨機訪問時間通過讀入FAT信息，磁頭能找到任何塊的位置29文件分配表30三、索引分配將所有指針放在索引塊中邏輯形式索引表塊31索引分配指針目錄條目包括索引塊的地址支持隨機訪問，且沒有外部碎片問題浪費空間:必須分配一個完整的索引塊索引塊應(yīng)為多大？太大會浪費空間，太小不能為大文件存儲足夠多的指針鏈接方案為了處理大文件，可以將多個索引塊鏈接起來。多層索引用第一層索引塊指向一組第二層的索引塊，第二層索引塊再指向文件塊組合方案用于UFS，將索引塊的前15個指針存在文件的inode中。前12個指針指向直接塊，其它3個指針指向間接塊32多層索引outer-indexindextablefiledirectory33組合方案:UNIXinode

(4Kbytesperblock)34性能性能依據(jù)存儲效率數(shù)據(jù)塊訪問時間考慮因素大部分是順序訪問還是隨機訪問?文件大小固定還是可變?filesizevarytoagreatdegree?由于CPU和磁盤速度的不等，就是花費操作系統(tǒng)數(shù)千條指令以節(jié)省一些磁頭移動都是值得的35順序訪問直接訪問不同文件大小空間利用連續(xù)goodgoodbadexternalfragment鏈接goodbadgood索引???somewaste索引分配的性能依賴于索引結(jié)構(gòu)文件大小所需塊的位置3612.5空閑空間管理空閑空間鏈表記錄了所有空閑磁盤空間，將刪除文件的空間用于新文件不同的實現(xiàn)方法位向量鏈表組計數(shù)3712.5.1位向量空閑空間表實現(xiàn)為位圖,或位向量

n

塊，每塊用一位表示…012n-1bit[k]=1block[k]空閑0

block[k]已分配第一個空閑塊的計算(一個字的位數(shù))*(值為0的字數(shù))+第一個值為1的位的偏移3812.5.2鏈表空閑空間鏈表很難獲得連續(xù)空間沒有空間浪費FAT有助于提高性能3912.5.3組對空閑鏈表的一個改進是將n個空閑塊的地址存在第一個空閑塊中。這些塊中的前n－1個為空。而最后一塊包含另外n個空閑塊的地址4012.5.4計數(shù)通常有多個連續(xù)塊需要同時分配或釋放，尤其是在使用連續(xù)分配和采用簇時更是如此可以記錄第一塊的地址和緊跟第一塊的連續(xù)的空閑塊的數(shù)量n?？臻e空間表的每個條目包括磁盤地址和數(shù)量。4112.6效率和性能效率取決于磁盤分配和目錄管理算法保留在文件目錄條目中的數(shù)據(jù)類型性能磁盤控制器的板載高速緩存磁盤緩存–一塊獨立內(nèi)存，位于其中的塊假設(shè)馬上需要使用頁緩存,將文件數(shù)據(jù)作為頁而不是塊來緩存.也稱為統(tǒng)一虛擬內(nèi)存42頁緩存頁緩存使用虛擬內(nèi)存技術(shù)，將文件數(shù)據(jù)作為頁來緩存，比采用物理磁盤塊來緩存更高效內(nèi)存映像I/O使用頁緩沖子程序I/O通過文件系統(tǒng)使用磁盤緩沖區(qū)這種結(jié)果如下圖所示.43無統(tǒng)一緩沖緩存的I/O雙緩存問題44I/OWithoutaUnifiedBufferCache45統(tǒng)一緩沖緩存統(tǒng)一緩沖緩存使用相同頁緩存去緩存內(nèi)存映射頁和不同文件系統(tǒng)I/O46采用了統(tǒng)一緩沖緩存的I/O47不同的磁盤緩存位置板載高速緩存，磁盤緩存，頁緩存，統(tǒng)一虛擬內(nèi)存LRU

是一個用于塊或頁