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

文件系統(tǒng)實(shí)現(xiàn)112.1文件系統(tǒng)結(jié)構(gòu)操作系統(tǒng)通過文件系統(tǒng)來存儲(chǔ)、定位、提取數(shù)據(jù)，文件系統(tǒng)存在于輔助存儲(chǔ)器中—磁盤文件系統(tǒng)設(shè)計(jì)的兩個(gè)問題如何定義對(duì)用戶的接口。如定義文件及其屬性、文件所允許的操作、組織文件的目錄結(jié)構(gòu)創(chuàng)建數(shù)據(jù)結(jié)構(gòu)和算法來將邏輯文件系統(tǒng)映射到物理外存設(shè)備上文件系統(tǒng)按層組織文件控制塊FCB：由一個(gè)文件的相關(guān)信息組成的存儲(chǔ)結(jié)構(gòu)，如擁有者、許可、文件內(nèi)容的位置2分層設(shè)計(jì)的文件系統(tǒng)設(shè)備驅(qū)動(dòng)程序,中斷處理程序，實(shí)現(xiàn)內(nèi)存與磁盤之間的信息轉(zhuǎn)移向設(shè)備驅(qū)動(dòng)程序發(fā)送命令以對(duì)磁盤上的物理塊進(jìn)行讀寫邏輯地址=>物理地址管理元數(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個(gè)基本名加上一個(gè)“.”和3個(gè)字符擴(kuò)展名。FAT32文件系統(tǒng)（vfat）它是Windows98使用的擴(kuò)展的DOS文件系統(tǒng)，它在MS-DOS文件系統(tǒng)基礎(chǔ)上增加了對(duì)長文件名（最多到256B）支持。NTFS（NT文件系統(tǒng)）它是WindowsNT操作系統(tǒng)使用的文件系統(tǒng)，它具有很強(qiáng)的安全特性和文件系統(tǒng)恢復(fù)功能，可以處理巨大的存儲(chǔ)媒體，支持多種文件系統(tǒng)。S51K/S52K（sysv）

它是AT&TUNIXSV操作系統(tǒng)使用的1KB/2KB文件系統(tǒng)。4文件系統(tǒng)的類型ext2（二級(jí)擴(kuò)展文件系統(tǒng)）它是Linux操作系統(tǒng)使用的高性能磁盤文件系統(tǒng)，它是對(duì)Minux操作系統(tǒng)中使用的文件系統(tǒng)擴(kuò)展（ext）的擴(kuò)展。它支持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é)儲(chǔ)存技術(shù)協(xié)會(huì)（OpticalStorageTechnologyAssociation,OSTA）的通用磁盤格式文件系統(tǒng)規(guī)格1.02版所制定的。它提供了對(duì)UDF格式媒體的只讀訪問（例如DVD光盤）。Windows98提供對(duì)UDF文件系統(tǒng)支持。5三、操作系統(tǒng)(Windows98/NT、Linux)

對(duì)多種文件系統(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ū)動(dòng)程序和盤驅(qū)動(dòng)程序三層，不同的文件系統(tǒng)采用不同的文件系統(tǒng)驅(qū)動(dòng)程序，系統(tǒng)用動(dòng)態(tài)連接庫對(duì)這些文件系統(tǒng)進(jìn)行裝入和卸出并適宜于將來的擴(kuò)展，WindowsNT分層驅(qū)動(dòng)程序如下圖所示。

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

FAT驅(qū)動(dòng)程序

NTFS驅(qū)動(dòng)程序

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

（UFS）,主控文件表

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

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

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

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

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

n

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

block[k]已分配第一個(gè)空閑塊的計(jì)算(一個(gè)字的位數(shù))*(值為0的字?jǐn)?shù))+第一個(gè)值為1的位的偏移3812.5.2鏈表空閑空間鏈表很難獲得連續(xù)空間沒有空間浪費(fèi)FAT有助于提高性能3912.5.3組對(duì)空閑鏈表的一個(gè)改進(jìn)是將n個(gè)空閑塊的地址存在第一個(gè)空閑塊中。這些塊中的前n－1個(gè)為空。而最后一塊包含另外n個(gè)空閑塊的地址4012.5.4計(jì)數(shù)通常有多個(gè)連續(xù)塊需要同時(shí)分配或釋放，尤其是在使用連續(xù)分配和采用簇時(shí)更是如此可以記錄第一塊的地址和緊跟第一塊的連續(xù)的空閑塊的數(shù)量n。空閑空間表的每個(gè)條目包括磁盤地址和數(shù)量。4112.6效率和性能效率取決于磁盤分配和目錄管理算法保留在文件目錄條目中的數(shù)據(jù)類型性能磁盤控制器的板載高速緩存磁盤緩存–一塊獨(dú)立內(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

是一個(gè)用于塊或頁