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

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

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

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

目錄實(shí)現(xiàn)11.4

分配方法11.5

空閑空間管理11.6

效率與性能11.7

恢復(fù)11.8

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

NFS11.1

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

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

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

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

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

Control

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

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

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

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

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

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

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

→

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

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

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

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

用于DOS和Windows95，98NTFS

多用于Windows

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

FAT16

FAT32

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

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

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

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

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

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

Windows2000/XP

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

NTFS11.4.3

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

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

磁盤空間的索引分配11.4.3

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

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

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

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

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

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