2013os第11章文件系統(tǒng)實現(xiàn)

第11章文件系統(tǒng)的實現(xiàn)11.1

文件系統(tǒng)結(jié)構11.2

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

目錄實現(xiàn)11.4

分配方法11.5

空閑空間管理11.6

效率與性能11.7

恢復11.8

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

NFS11.1

文件系統(tǒng)結(jié)構利用磁盤作為外存來存儲文件系統(tǒng)中的眾多文件磁盤可以原地重寫可以直接訪問磁盤上的任意一塊信息為了提供對磁盤的高效且便捷的訪問，操作系統(tǒng) 通過文件系統(tǒng)來輕松地存儲、定位、提取數(shù)據(jù)。文件系統(tǒng)的兩個設計問題如何定義文件系統(tǒng)對用戶的接口如何將邏輯文件系統(tǒng)映射到物理外存設備上文件系統(tǒng)按層來組織（見下頁）P353圖11.1

分層設計的文件系統(tǒng)I/O控制：由設備驅(qū)動程序和中斷處理程序組成實現(xiàn)內(nèi)存與磁盤之間的信息轉(zhuǎn)移基本文件系統(tǒng)：向設備驅(qū)動程序發(fā)送命令對磁盤的物理塊進行讀寫物理地址：驅(qū)動器，柱面，磁道，扇區(qū)文件組織模塊：知道文件及其邏輯塊和物理塊(地址映射)空閑空間管理邏輯文件系統(tǒng)管理元數(shù)據(jù)：文件系統(tǒng)的所有結(jié)構數(shù)據(jù)，而不包括實際數(shù)據(jù)（或文件內(nèi)容）根據(jù)給定符號文件名來管理目錄結(jié)構邏輯文件系統(tǒng)通過文件控制塊(FCB)來維護文件結(jié)構P35311.2

文件系統(tǒng)實現(xiàn)在磁盤上，文件系統(tǒng)可能包括如下信息：如何啟動所存儲的操作系統(tǒng)總的塊數(shù)空閑塊的數(shù)目和位置目錄結(jié)構以及各個具體文件等11.2

文件系統(tǒng)實現(xiàn)磁盤結(jié)構包括引導控制塊通常為分區(qū)的第一塊。如果該分區(qū)沒有OS，則為空。（其他名稱：引導塊（Linux）、分區(qū)引導扇區(qū)（WindowsNT））分區(qū)控制塊 包括分區(qū)詳細信息，如分區(qū)的塊數(shù)、塊的大小、空閑塊的數(shù)量和指針、空閑FCB的數(shù)量和指針等（亦稱為超級塊（Linux）、主控文件表（WindowsNT））目錄結(jié)構用來組織文件文件控制塊（FCB） 包括很多文件信息，如文件許可、擁有者、大小和數(shù)據(jù)塊的位置等圖11.2

一個典型的文件控制塊文件權限文件日期（創(chuàng)建、訪問、寫）文件所有者，組，ACL（Access

Control

Level）文件大小文件數(shù)據(jù)塊11.2

文件系統(tǒng)實現(xiàn)內(nèi)存中的結(jié)構內(nèi)存分區(qū)表：包含所有安裝分區(qū)的信息內(nèi)存目錄結(jié)構：保存近來訪問過的目錄信息系統(tǒng)范圍的打開文件表：包括每個打開文件的FCB拷貝和其他信息 單個進程的打開文件表：包括一個指向系統(tǒng)范圍內(nèi)已打開文件表中合適條目和其他信息的指針文件描述符（

Linux/UNIX）文件句柄（Windows）圖11.3

內(nèi)存中的文件系統(tǒng)結(jié)構11.3

目錄實現(xiàn)線性列表目錄文件是由目錄項構成的一個線性表，每個目錄項包括文件名和指向數(shù)據(jù)塊的指針當需要創(chuàng)建一個新文件時，系統(tǒng)必須首先搜索目錄文件以確定有沒有同名的文件存在，然后把新文件的目錄項添加到目錄末尾當刪除一個文件時，系統(tǒng)根據(jù)給定的文件名來搜索文件目錄。找到該文件所在目錄項后，釋放分配給該文件的磁盤空間，并將相應的目錄項刪除11.3

目錄實現(xiàn)哈希表◆為了降低了目錄搜索時間，并使插入和刪除更方便，采用哈希表實現(xiàn)目錄哈希表將根據(jù)文件名計算出一個哈希值，并返回一個指向線性列表中元素的指針需要一些措施來避免沖突(兩個不同的文件名具有相同的哈希值)哈希表的最大困難在于其大小通常是固定的，而且哈希函數(shù)也依賴于哈希表的大小11.4

分配方式分配方法指的是如何為文件分配磁盤塊常用的分配方法有以下三類連續(xù)分配→基于擴展的連續(xù)分配鏈接分配→文件分配表FAT索引分配

→

鏈接方案，多層索引方案，組合方案11.4.1

連續(xù)分配為每個文件分配一組相鄰接的盤塊(常用首次適應和最佳適應)目錄項記錄了文件第一個記錄的盤塊號和文件長度外存的碎片可以采用緊湊技術連續(xù)分配方式的優(yōu)缺點優(yōu)點：①順序訪問容易②順序訪問速度快：文件位于同一磁道或相鄰幾個磁道缺點：①要求有連續(xù)的存儲空間，不便于動態(tài)增長②

必須事先知道文件長度基于擴展的連續(xù)分配方式許多新的文件系統(tǒng)采用一種修正的連續(xù)分配方法該方法開始分配一塊連續(xù)空間，當空間不夠時， 另一塊被稱為擴展的連續(xù)空間會添加到原來的分 配中。文件塊的位置就成為開始地址、塊數(shù)、加上一個 指向下一擴展的指針。11.4.2

鏈接分配目錄中含有指向鏈接文件指向第一個盤塊和最后一個盤塊的指針問題：不適宜隨機訪問，塊內(nèi)增加了指針(可改進：按簇分配，又增加了內(nèi)碎片)一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊◆每個盤塊中都含有指向下一個盤塊的指針鏈接分配的優(yōu)缺點優(yōu)點：①提高磁盤空間利用率②不存在外部碎片③有利于文件插入和刪除④有利于文件動態(tài)擴充缺點：①存取速度慢，不適于隨機存?、诳煽啃詥栴}，如指針出錯③更多的尋道次數(shù)和尋道時間④鏈接指針占用一定的空間鏈接結(jié)構的一個變形:文件分配表FAT文件分配表FAT連接文件各物理塊的指針都存放在分區(qū)開始部分的一張鏈接表中(文件分配表FAT，需要內(nèi)存緩存)FAT表中每個表項存放指向下一個盤塊的鏈接指針文件控制塊FCB中存放文件的第一個盤塊號考慮：如何為文件分配一個新的塊增加：FATFAT

用于DOS和Windows95，98NTFS

多用于Windows

NT，2000，xpFAT文件系統(tǒng)將物理磁盤劃分為多個邏輯磁盤(卷、分區(qū))FAT12

FAT16

FAT32

NTFS增加：FAT12以盤塊為基本分配單位早期的MS-DOS是FAT12文件系統(tǒng)（12位）FAT12的每個盤塊(一個扇區(qū))為512字節(jié)，則所允許的最大磁盤容量為8MB每個FAT表項為12位，則最多有212個表項，每個表項對應一個盤塊512B，則每個邏輯分區(qū)為2MB，共有

4個邏輯分區(qū)，則一個物理磁盤的最大容量為8MB磁盤最大容量太小，引入“簇”來進行磁盤分配增加：FAT122）簇的基本概念簇是一組連續(xù)的扇區(qū)一個簇應包含的扇區(qū)數(shù)量與磁盤容量的大小有關如一個簇包含2個扇區(qū)，則最大容量為16MB如一個簇包含8個扇區(qū)，則最大容量為64MB簇分配的好處：能適應磁盤容量不斷增長的情況簇分配的壞處：會帶來很大的簇內(nèi)碎片增加：FAT123）FAT12存在的問題對所允許的磁盤容量存在嚴重的限制雖然簇分配可提高容量，但會產(chǎn)生簇內(nèi)碎片F(xiàn)AT12只支持8+3的文件名增加：FAT16將FAT表表項的寬度增加到16位，則可表示216個簇FAT16中一個簇最多包含64個扇區(qū)，則最大容量為

216*64*512=2G簇最大則產(chǎn)生的簇內(nèi)碎片也越大，一個簇只能給一個文件用，對于小文件，很浪費空間FAT16也不支持長文件名，采用8+3格式文件名（win3.x

win95）增加：FAT32將FAT表表項的寬度增加到32位，則可表示232個簇FAT32中一個簇一般包含8個扇區(qū)，則最大容量為

232*8*512=2T FAT32支持更大的磁盤容量和更小的簇，大大減少了磁盤空間的浪費FAT32支持長文件名(win98以后的產(chǎn)品)FAT32的不足：①因文件分配表大，所以運行速度比FAT16慢②有最小管理空間限制，要求分區(qū)必須有216個簇③單個文件長度不能大于4G④FAT32不能向下兼容增加：NTFS NTFS(NewTechnologyFileSystem)是一個專門為Windows

NT開發(fā)的、全新的文件系統(tǒng)，并適用于

Windows2000/XP

及以后系列64位磁盤地址支持長文件名提供容錯功能提供數(shù)據(jù)一致性、文件加密、文件壓縮功能NTFS與FAT文件系統(tǒng)缺乏兼容性(win98文件能被windowsNT識別，反之不能)FAT32

NTFS11.4.3

索引分配鏈接分配解決了外碎片，但不支持直接訪問，而且

FAT表占用較大內(nèi)存空間引入索引分配解決索引表：(邏輯塊號，物理塊號)優(yōu)點：無外碎片，便于動態(tài)增長，可隨機存取缺點：索引表占空間，需要先訪問索引表，而后訪問文件內(nèi)容塊（2次訪問外存）(文件較大時，索引分配優(yōu)于鏈接分配，文件小時，索引塊利用率低)圖11.8

磁盤空間的索引分配11.4.3

索引分配大的文件，可能需要多個索引塊 鏈接方案：一個索引塊通常為一個磁盤塊。對于大文件，可以將多個索引塊鏈接起來 多層索引：類似于內(nèi)存的間接尋址方式（一級、二級間接…）組合方案：如Unix的inode多層索引方案索引表的大小超過一個物理塊時，用多重索引(間接索引)混合索引方案Unix采用混合索引分配①直接尋址方式②單級索引③二級索引④三級索引11.5

空閑空間管理為了記錄空閑磁盤空間，系統(tǒng)需要維護一個空閑 空間數(shù)據(jù)結(jié)構，它記錄了所有空閑磁盤空間，即 未分配給文件或目錄的空間位向量（位示圖法）鏈表（空閑鏈表法）組（成組鏈接法）計數(shù)（空閑文件目錄法）11.5.1

位向量（位示圖） 系統(tǒng)建立一張位示圖。位為“1”，則表示對應的塊是空閑塊；位為“0”，則表示對應的塊已被分配出去。優(yōu)點：①位示圖對空間分配情況的描述能力強，一個二進位就描述一個物理塊的狀態(tài)②位示圖占用空間較小，因此可以復制到內(nèi)存，使查找既方便又快速③位示圖適用于各種文件物理結(jié)構的文件系統(tǒng)11.5.2

鏈表（空閑鏈表法）◆把磁盤上所有空閑塊鏈接在一起，包括：①空閑盤塊鏈 ②空閑盤區(qū)鏈 1.空閑盤塊鏈：(按釋放先后順序鏈接)分配時從鏈頭開始分配幾個空閑盤塊，回收時掛在鏈尾（分配回收快，但可能多次）2.空閑盤區(qū)鏈：（按空閑區(qū)大小順序或地址順序鏈接）分配時類似于內(nèi)存動態(tài)分區(qū)分配，常采用首次適應算法或最佳適應算法，回收時可能要合并空閑分區(qū)11.5.3

組（成組鏈接法）◆成組鏈接法：（unix采用）首先把所有空閑塊按50塊劃分為一組每組的第一塊用來存放前一組中各塊的塊號和總塊數(shù) 第一組的塊數(shù)為49塊，中間組的塊數(shù)為50塊，最后一組可能不足50塊 最后一組的物理塊號與總塊數(shù)放在管理文件存儲設備用的文件資源表中11.5.4

計數(shù)（空閑文件目錄法）相當于內(nèi)存的動態(tài)分配方式，采用首次適應和最佳適應算法序號第個空閑塊號空閑塊個數(shù)物理塊號雖是連續(xù)分配方式，但分配速度快，可減少訪問磁