操作系統(tǒng)概念中文版-chapter

操作系統(tǒng)概念第十二章：文件系統(tǒng)實(shí)現(xiàn)2本章主要內(nèi)容文件系統(tǒng)結(jié)構(gòu)文件系統(tǒng)實(shí)現(xiàn)目錄實(shí)現(xiàn)分配方法空閑空間管理恢復(fù)312.1文件系統(tǒng)結(jié)構(gòu)磁盤提供大量的外存空間來維持文件系統(tǒng)，磁盤的兩個(gè)特點(diǎn)，使其成為存儲(chǔ)多個(gè)文件的方便媒介可以原地重寫；可以從磁盤上讀一塊，修改該塊，并將它寫回到原來的位置可以直接訪問磁盤上的任意一塊信息。（隨機(jī)或順序方式）為了提供對(duì)磁盤的高效且便捷的訪問，操作系統(tǒng)通過文件系統(tǒng)來輕松地存儲(chǔ)、定位、提取數(shù)據(jù)。文件系統(tǒng)的兩個(gè)設(shè)計(jì)問題如何定義文件系統(tǒng)對(duì)用戶的接口創(chuàng)建數(shù)據(jù)結(jié)構(gòu)和算法來將邏輯文件系統(tǒng)映射到物理外存設(shè)備上文件系統(tǒng)按層來組織（見下頁）4分層設(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)行讀寫文件組織模塊知道文件及其邏輯塊和物理塊?？臻e空間管理器邏輯文件系統(tǒng)管理元數(shù)據(jù)：文件系統(tǒng)的所有結(jié)構(gòu)數(shù)據(jù)，而不包括實(shí)際數(shù)據(jù)（或文件內(nèi)容）根據(jù)給定符號(hào)文件名來管理目錄結(jié)構(gòu)邏輯文件系統(tǒng)通過文件控制塊(FCB)來維護(hù)文件結(jié)構(gòu)512.2文件系統(tǒng)實(shí)現(xiàn)本節(jié)深入分析用于實(shí)現(xiàn)文件系統(tǒng)的結(jié)構(gòu)和操作6磁盤結(jié)構(gòu)在磁盤上，文件系統(tǒng)可能包括如下信息：如何啟動(dòng)所存儲(chǔ)的操作系統(tǒng)總的塊數(shù)空閑塊的數(shù)目和位置目錄結(jié)構(gòu)以及各個(gè)具體文件等磁盤結(jié)構(gòu)包括引導(dǎo)控制塊（bootcontrolblock）：通常為分區(qū)的第一塊。如果該分區(qū)沒有OS，則為空。（其他名稱：引導(dǎo)塊（Linux）、分區(qū)引導(dǎo)扇區(qū)（WindowsNT））分區(qū)控制塊（partitioncontrolblock）：包括分區(qū)詳細(xì)信息，如分區(qū)的塊數(shù)、塊的大小、空閑塊的數(shù)量和指針、空閑FCB的數(shù)量和指針等（亦稱為超級(jí)塊（Linux）、主控文件表（WindowsNT））目錄結(jié)構(gòu)：用來組織文件文件控制塊（FCB）：包括很多文件信息，如文件許可、擁有者、大小和數(shù)據(jù)塊的位置等7一個(gè)典型的文件控制塊文件權(quán)限文件日期（創(chuàng)建、訪問、寫）文件所有者，組，ACL（AccessControlLevel）文件大小文件數(shù)據(jù)塊8內(nèi)存中的結(jié)構(gòu)內(nèi)存分區(qū)表：包含所有安裝分區(qū)的信息內(nèi)存目錄結(jié)構(gòu)：保存近來訪問過的目錄信息（對(duì)安裝分區(qū)的目錄，可以包括一個(gè)指向分區(qū)表的指針）系統(tǒng)范圍的打開文件表：包括每個(gè)打開文件的FCB拷貝和其他信息單個(gè)進(jìn)程的打開文件表：包括一個(gè)指向系統(tǒng)范圍內(nèi)已打開文件表中合適條目和其他信息的指針文件描述符（filedescriptor,Linux/UNIX）文件句柄（filehandle,Windows）9內(nèi)存中的文件系統(tǒng)結(jié)構(gòu)10分區(qū)與安裝分區(qū)可以是“生的”（raw），即沒有文件系統(tǒng)，或是“熟的”（cooked）即含有文件系統(tǒng)。生的分區(qū)用于沒有合適文件系統(tǒng)的地方。如：Unix中的交換區(qū)引導(dǎo)信息能存在各個(gè)分區(qū)中，并且有自己的格式。它通常為一組有序塊，作為二進(jìn)制文件讀入內(nèi)存。引導(dǎo)信息除了包括如何啟動(dòng)一個(gè)特定操作系統(tǒng)外，還可以有其他指令。（如BootManagerbootstar8.3，LinuxGRUB,GRUB-GRandUnifiedBootloader）根分區(qū)（rootpartition）包括操作系統(tǒng)內(nèi)核或其他系統(tǒng)文件，在引導(dǎo)時(shí)裝入內(nèi)存。其他分區(qū)根據(jù)不同操作系統(tǒng)可以在引導(dǎo)時(shí)自動(dòng)裝入或在此之后手動(dòng)裝入。/root,/boot文件系統(tǒng)安裝表（filesystemmounttable）11虛擬文件系統(tǒng)虛擬文件系統(tǒng)(VFS)提供了一種面向?qū)ο蟮姆椒▉韺?shí)現(xiàn)文件系統(tǒng)VFS允許在不同類型的文件系統(tǒng)上采用同樣的系統(tǒng)調(diào)用接口（API）API是針對(duì)VFS的接口，而非對(duì)任何特定類型的文件系統(tǒng)12虛擬文件系統(tǒng)示意圖1312.3目錄實(shí)現(xiàn)最為簡單的目錄實(shí)現(xiàn)方法是使用存儲(chǔ)文件名和數(shù)據(jù)塊指針的線性列表（數(shù)組、鏈表等）容易實(shí)現(xiàn)但運(yùn)行費(fèi)時(shí)采用線性搜索來查找特定條目（缺點(diǎn)）許多操作系統(tǒng)采用軟件緩存來存儲(chǔ)最近訪問過的目錄信息Hash表：采用Hash數(shù)據(jù)結(jié)構(gòu)的線性表減少了目錄搜索時(shí)間碰撞：兩個(gè)文件名哈希到相同的位置哈希表的最大困難是其通常固定的大小和哈希函數(shù)對(duì)大小的依賴性1412.4分配方法分配方法指的是如何為文件分配磁盤塊，常用的分配方法有以下三類連續(xù)分配鏈接分配索引分配15(一)連續(xù)分配(contiguousallocation)每個(gè)文件占據(jù)磁盤上的一組連續(xù)的塊特點(diǎn)：簡單－只需要記錄文件的起始位置（塊號(hào)）及長度。訪問文件很容易，所需的尋道時(shí)間也最少存在的問題為新文件找空間比較困難（類似于內(nèi)存分配中分配方式）文件很難增長16磁盤空間的連續(xù)分配示例17基于擴(kuò)展的連續(xù)分配方法許多新的文件系統(tǒng)采用一種修正的連續(xù)分配方法該方法開始分配一塊連續(xù)空間，當(dāng)空間不夠時(shí)，另一塊被稱為擴(kuò)展的連續(xù)空間會(huì)添加到原來的分配中。文件塊的位置就成為開始地址、塊數(shù)、加上一個(gè)指向下一擴(kuò)展的指針。18(二)鏈接分配(linkedallocation)每個(gè)文件是磁盤塊的鏈表；磁盤塊分布在磁盤的任何地方。優(yōu)點(diǎn)：簡單－只需起始位置文件創(chuàng)建與增長容易缺點(diǎn)：不能隨機(jī)訪問塊與塊之間的鏈接指針需要占用空間簇：將多個(gè)連續(xù)塊組成簇，磁盤以簇為單位進(jìn)行分配存在可靠性問題19

20鏈接分配方法的變種-文件分配表(FAT)每個(gè)分區(qū)的開始部分用于存儲(chǔ)該FAT表。每個(gè)磁盤塊在該表中有一項(xiàng)，該表可以通過塊號(hào)來索引。目錄條目中含有文件首塊的塊號(hào)碼。根據(jù)塊號(hào)碼索引的FAT條目包含文件下一塊的地號(hào)碼。這種鏈會(huì)一直繼續(xù)到最后一塊，該塊對(duì)應(yīng)FAT條目的值為文件結(jié)束值。未使用的塊用0值來表示。為文件分配一個(gè)新的塊只要簡單地找到第一個(gè)值為０的FAT條目，用新塊的地址替換前面文件結(jié)束值，用文件結(jié)束值替代0。如果不對(duì)FAT采用緩存，F(xiàn)AT分配方案可能導(dǎo)致大量的磁頭尋道時(shí)間。但通過讀入FAT信息，磁盤能找到任何塊的位置，從而實(shí)現(xiàn)隨機(jī)訪問。21

22(三)索引分配(indexedallocation)將所有的數(shù)據(jù)塊指針集中到索引塊中索引塊中的第i個(gè)條目指向文件的第i塊。目錄條目包括索引塊的地址索引分配支持直接訪問，且沒有外部碎片問題索引塊本身可能會(huì)浪費(fèi)空間鏈接方案：一個(gè)索引塊通常為一個(gè)磁盤塊。對(duì)于大文件，可以將多個(gè)索引塊鏈接起來。多層索引：類似于內(nèi)存的間接尋址方式（一級(jí)、二級(jí)間接…）組合方案：如Unix的inode23索引分配實(shí)例24UNIX的inode(4Kbytesperblock)2512.5空閑空間管理為了記錄空閑磁盤空間，系統(tǒng)需要維護(hù)一個(gè)空閑空間鏈表，它記錄了所有空閑磁盤空間，即未分配給文件或目錄的空間。（不一定以鏈表的方式實(shí)現(xiàn)）位向量（n塊）bit[i]=0block[i]空閑bit[i]=1block[i]被占用空閑塊數(shù)計(jì)算一個(gè)字的位數(shù)×值為0的字?jǐn)?shù)＋第一個(gè)值為1的位的偏移26(續(xù))位向量需要額外的空間設(shè)塊大小為212字