操作系統(tǒng)課件：文件管理1

文件管理文件系統(tǒng)負(fù)責(zé)管理外存上的文件，并為用戶提供對(duì)文件進(jìn)行存取、共享及保護(hù)的手段。8.1文件系統(tǒng)的概念-8.1.1文件系統(tǒng)文件是具有文件名的一組相關(guān)記錄的集合。文件由若干記錄組成。記錄是一些相關(guān)數(shù)據(jù)項(xiàng)的集合。數(shù)據(jù)項(xiàng)是數(shù)據(jù)組織中可以命名的最小邏輯單位。文件系統(tǒng)filesystem文件系統(tǒng)：操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)的集合。它由管理文件所需的數(shù)據(jù)結(jié)構(gòu)、相應(yīng)的管理軟件和被管理的文件構(gòu)成。文件系統(tǒng)的主要功能實(shí)現(xiàn)文件的按名存取為用戶提供接口實(shí)施對(duì)文件和目錄的管理文件存儲(chǔ)空間的分配及回收文件的共享及保護(hù)文件系統(tǒng)的層次結(jié)構(gòu)文件系統(tǒng)的層次結(jié)構(gòu)包含四層：基本I/O控制層基本文件系統(tǒng)層基本I/O管理程序?qū)舆壿嬑募到y(tǒng)層不同操作系統(tǒng)中，文件系統(tǒng)的組成方法不一樣，但這種組成具有代表性?；綢/O控制層基本I/O控制層（Basic

I/Ocontrollevel）又稱設(shè)備驅(qū)動(dòng)程序?qū)?，該層主要由?qū)動(dòng)程序組成，負(fù)責(zé)啟動(dòng)設(shè)備I/O操作及對(duì)設(shè)備發(fā)來(lái)的中斷信號(hào)進(jìn)行處理?；疚募到y(tǒng)層基本文件系統(tǒng)層（Basicfilesystemlevel）又稱物理I/O層，該層負(fù)責(zé)處理內(nèi)存和外存之間的數(shù)據(jù)塊交換。它關(guān)心數(shù)據(jù)塊在外存和在緩沖區(qū)中的位置，無(wú)須了解傳送數(shù)據(jù)塊的內(nèi)容或文件結(jié)構(gòu)。基本I/O管理程序?qū)踊綢/O管理程序?qū)佑址Q文件組織模塊層（File-organizationmodule

level），負(fù)責(zé)所有文件I/O的初始化和終止。該層完成的工作包括選擇文件所在的設(shè)備、進(jìn)行文件邏輯塊號(hào)到物理塊號(hào)的轉(zhuǎn)換、優(yōu)化磁盤(pán)調(diào)度的性能、對(duì)文件空閑存儲(chǔ)空間進(jìn)行管理等。邏輯文件系統(tǒng)層邏輯文件系統(tǒng)層（Thelogicalfilesystemlevel）負(fù)責(zé)處理文件及記錄的相關(guān)操作。如允許用戶利用文件名訪問(wèn)文件及其中的記錄、實(shí)現(xiàn)對(duì)文件及記錄的保護(hù)、實(shí)現(xiàn)目錄操作等。文件系統(tǒng)的層次結(jié)構(gòu)圖邏輯文件系統(tǒng)層基本I/O管理程序?qū)踊疚募到y(tǒng)層基本I/O控制層文件系統(tǒng)接口物理磁盤(pán)8.1.2文件分類為了便于管理和控制文件，將文件分為若干類型。不同系統(tǒng)對(duì)文件的管理方式不同，因而對(duì)文件的分類方法也有很大差異。常見(jiàn)的文件分類方法有：1.按用途分類按用途可以將文件分為：系統(tǒng)文件：系統(tǒng)軟件構(gòu)成的文件。庫(kù)文件：系統(tǒng)提供給用戶使用的各種標(biāo)準(zhǔn)過(guò)程、函數(shù)和應(yīng)用程序。用戶文件：用戶委托文件系統(tǒng)保存的文件。2.按保護(hù)級(jí)別分類按保護(hù)級(jí)別可將文件分為：只讀文件：允許所有者或授權(quán)用戶對(duì)其進(jìn)行讀，但不允許寫(xiě)。讀寫(xiě)文件：允許所有者或授權(quán)用戶對(duì)其進(jìn)行讀寫(xiě)，但禁止未核準(zhǔn)用戶讀寫(xiě)。執(zhí)行文件：允許核準(zhǔn)用戶調(diào)用執(zhí)行，但不允許對(duì)其進(jìn)行讀寫(xiě)。不保護(hù)文件：不加任何訪問(wèn)限制的文件。3.按信息流向分類按信息流向可以將文件分為：輸入文件：來(lái)自輸入設(shè)備的文件，如來(lái)自鍵盤(pán)的輸入文件。輸出文件：寫(xiě)向輸出設(shè)備的文件，如寫(xiě)向打印機(jī)的輸出文件。輸入輸出文件：如磁盤(pán)上的文件，既可以讀又可以寫(xiě)。4.按數(shù)據(jù)形式分類按數(shù)據(jù)形式可以將文件分為：源文件：由源程序和數(shù)據(jù)構(gòu)成的文件。目標(biāo)文件：源程序經(jīng)過(guò)編譯程序編譯，但尚未鏈接成可執(zhí)行代碼的目標(biāo)代碼文件。可執(zhí)行文件：由鏈接程序鏈接后形成的可以運(yùn)行的文件。8.2文件結(jié)構(gòu)及存儲(chǔ)設(shè)備文件結(jié)構(gòu)指文件的組織形式，文件有兩種形式的結(jié)構(gòu)：邏輯結(jié)構(gòu)：又稱文件組織，是從用戶觀點(diǎn)出發(fā)所看到的文件組織形式。物理結(jié)構(gòu)：又稱文件的存儲(chǔ)結(jié)構(gòu)，是文件在外存上的存儲(chǔ)組織形式。它與存儲(chǔ)設(shè)備特性、外存分配方式有關(guān)。8.2.1文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)可分為兩類：記錄式文件：是一種有結(jié)構(gòu)文件，由一組相關(guān)記錄組成。又分為：等長(zhǎng)記錄文件：又稱定長(zhǎng)記錄文件，是指文件中所有記錄的長(zhǎng)度相等。變長(zhǎng)記錄文件：是指文件中各記錄長(zhǎng)度不相等。流式文件：是一種無(wú)結(jié)構(gòu)文件，由字符序列構(gòu)成。記錄式文件的組織方式根據(jù)用戶和系統(tǒng)管理的需要，可以采用多種方式來(lái)組織記錄式文件：順序文件：一組記錄按關(guān)鍵字的大小順序排列所形成的文件。其中的記錄通常是定長(zhǎng)的。索引文件：為文件設(shè)置一個(gè)索引表，文件中的每個(gè)記錄在索引表中有一個(gè)表項(xiàng)，用于存放記錄的存放地址及長(zhǎng)度。索引順序文件：是前兩者的結(jié)合。它將順序文件中的所有記錄分成若干組，為順序文件建立一張索引表，為每組中的第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指向該記錄的指針。8.2.2文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)與存儲(chǔ)介質(zhì)的存儲(chǔ)特性及外存分配方式有關(guān)。文件存儲(chǔ)設(shè)備通常劃分為大小相等的物理塊，物理塊是分配及傳輸信息的基本單位。物理塊的大小與設(shè)備有關(guān)，但與邏輯記錄的大小無(wú)關(guān)，因此一個(gè)物理塊中可以存放若干個(gè)邏輯記錄，一個(gè)邏輯記錄也可以存放在若干個(gè)物理塊中。為有效地利用外存設(shè)備和便于系統(tǒng)管理，一般也把文件信息劃分為與物理存儲(chǔ)塊大小相等的邏輯塊。物理結(jié)構(gòu)類型常見(jiàn)的文件物理結(jié)構(gòu)有以下幾種形式：順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)又稱連續(xù)結(jié)構(gòu)，它將一個(gè)在邏輯上連續(xù)的信息存放在外存連續(xù)的物理塊中。以順序結(jié)構(gòu)存放的文件稱為順序文件或連續(xù)文件。特點(diǎn)：順序存取速度較快；對(duì)等長(zhǎng)記錄文件支持隨機(jī)訪問(wèn)。但因要求連續(xù)存放，會(huì)產(chǎn)生碎片，同時(shí)也不利于文件的動(dòng)態(tài)擴(kuò)充。鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)又稱串聯(lián)結(jié)構(gòu)，它將一個(gè)邏輯文件的信息存放在外存不連續(xù)物理塊中，且在每個(gè)物理塊中設(shè)置一個(gè)指向下一個(gè)物理塊的指針。采用鏈接結(jié)構(gòu)存放的文件稱為鏈接文件或串聯(lián)文件。特點(diǎn)：可解決碎片問(wèn)題，便于文件動(dòng)態(tài)增長(zhǎng)。但只能順序訪問(wèn)，因而查找效率較低，指針占用存儲(chǔ)空間。索引結(jié)構(gòu)索引結(jié)構(gòu)：將一個(gè)邏輯文件的信息存放于外存的若干個(gè)物理塊中，并為每個(gè)文件建立一個(gè)索引表，其中的每個(gè)表目存放文件信息所在的邏輯塊號(hào)和與之對(duì)應(yīng)的物理塊號(hào)。采用索引結(jié)構(gòu)存放的文件稱為索引文件。特點(diǎn)：既可以順序訪問(wèn)也可以隨機(jī)訪問(wèn)，但增加了存儲(chǔ)空間開(kāi)銷，且要兩次訪問(wèn)外存。8.2.3文件存取方法常用的文件存取方法（AccessMethods）有：順序存取法SequentialAccess直接存取法DirectAccess按鍵存取法1.順序存取法順序存取法是按照文件信息的邏輯順序依次存取。在記錄式文件中，順序存取反映為按記錄的排列順序來(lái)存??；在流式文件中，順序存取反映為當(dāng)前讀寫(xiě)指針的變化。對(duì)定長(zhǎng)記錄的順序文件，若知道當(dāng)前記錄地址，則很易確定下一個(gè)記錄地址。

rptr＝rptr＋L其中L為文件記錄的長(zhǎng)度，rptr為讀寫(xiě)指針。2.直接存取法直接存取法又稱隨機(jī)存取法，允許按任意順序存取文件中的任何一個(gè)物理記錄。對(duì)于定長(zhǎng)記錄的順序文件，若知道文件的起始地址和記錄長(zhǎng)度，則第i個(gè)記錄（i＝0，1，2，…）的首地址為

rptr＝addr＋i×L其中addr是該文件的首地址，L為記錄長(zhǎng)度。3.按鍵存取法按鍵存取法實(shí)質(zhì)上也是直接存取法，它根據(jù)文件記錄中數(shù)據(jù)項(xiàng)（通常稱為鍵），經(jīng)過(guò)某種方法計(jì)算處理，轉(zhuǎn)換成相應(yīng)的物理地址后進(jìn)行存取。8.2.4文件存儲(chǔ)設(shè)備-1文件的存儲(chǔ)設(shè)備主要有磁帶、磁盤(pán)、光盤(pán)等。存儲(chǔ)設(shè)備的特性可以決定文件的存取方法。下面介紹以磁帶為代表的順序存取設(shè)備和以磁盤(pán)為代表的直接存取設(shè)備。磁帶Magnetictape磁帶是一種典型的順序存取設(shè)備。由于磁帶機(jī)的啟動(dòng)和停止要花費(fèi)一定的時(shí)間，因此在磁帶的相鄰物理塊之間設(shè)計(jì)有一段間隙將它們隔開(kāi)，如下所示。磁帶…

間隙第i塊間隙第i＋1塊間隙…磁帶（續(xù)）磁帶的存取速度與信息密度（字符數(shù)/英寸）、磁帶帶速（英寸/秒）和塊間間隙有關(guān)。如果帶速高、信息密度大且所需塊間隙（磁頭啟動(dòng)和停止時(shí)間）小，則磁帶存取速度高。反之，若磁帶帶速低、信息密度小且所需塊間隙（磁帶啟動(dòng)和停止時(shí)間）大，則磁帶存取速度低。磁盤(pán)磁盤(pán)是典型的直接存取設(shè)備。磁盤(pán)一般由若干磁盤(pán)片組成，可沿一個(gè)固定方向高速旋轉(zhuǎn)。每個(gè)盤(pán)面對(duì)應(yīng)一個(gè)磁頭，磁臂可沿半徑方向移動(dòng)。磁盤(pán)上的一系列同心圓稱為磁道（track），磁道沿徑向又分成大小相等的多個(gè)扇區(qū)（sector），與盤(pán)片中心有一定距離的所有磁道組成一個(gè)柱面（cylinder）。磁盤(pán)上的每個(gè)物理塊可用柱面號(hào)，磁頭號(hào)和扇區(qū)號(hào)表示。磁盤(pán)數(shù)據(jù)組織和格式示意圖磁臂磁頭3

01234567磁道第i扇區(qū)…間隙標(biāo)識(shí)字段間隙數(shù)據(jù)字段間隙…邏輯扇區(qū)將一個(gè)磁盤(pán)上的扇區(qū)從0柱面開(kāi)始，按柱面順序依次編號(hào)，所得到的編號(hào)成為邏輯扇區(qū)號(hào)。邏輯扇區(qū)號(hào)=柱面號(hào)*每柱面扇區(qū)數(shù)+

磁頭號(hào)*每磁頭扇區(qū)數(shù)+

扇區(qū)號(hào)其中，柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)都從0開(kāi)始磁盤(pán)訪問(wèn)時(shí)間磁盤(pán)訪問(wèn)時(shí)間由三部分組成：尋道時(shí)間（seektime）：指將磁頭從當(dāng)前位置移動(dòng)到指定磁道所經(jīng)歷的時(shí)間。由啟動(dòng)磁臂時(shí)間和磁頭移動(dòng)多條磁道的時(shí)間構(gòu)成。旋轉(zhuǎn)延遲時(shí)間（rotationallatency）：指扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。平均旋轉(zhuǎn)延遲時(shí)間是每轉(zhuǎn)所需時(shí)間的一半。傳輸時(shí)間（tranfertime）：指從磁盤(pán)上讀出數(shù)據(jù)或向磁盤(pán)寫(xiě)入數(shù)據(jù)所經(jīng)歷的時(shí)間。由于這三部分操作均涉及機(jī)械運(yùn)動(dòng)，故磁盤(pán)塊的訪問(wèn)時(shí)間約為0.01～0.1s之間，其中尋道時(shí)間所占的比例最大。2.存儲(chǔ)設(shè)備、存取方法和物理結(jié)構(gòu)的關(guān)系1文件的物理結(jié)構(gòu)與文件存儲(chǔ)器的特性和存取方法密切相關(guān)。磁帶是一種順序存取設(shè)備，適合采用順序結(jié)構(gòu)存放文件，相應(yīng)的存取方法通常是順序存取法。若采用其他文件結(jié)構(gòu)或采用直接存取方式都不太合適。存儲(chǔ)設(shè)備、存取方法和物理結(jié)構(gòu)的關(guān)系2磁盤(pán)屬于直接存取存儲(chǔ)設(shè)備，前述的幾種物理結(jié)構(gòu)都可以采用。存取方法也可以多種多樣。如果采用順序存取法則前述的幾種文件結(jié)構(gòu)都可以采用。如果采用直接存取法，則索引文件效率最高，順序文件效率居中，串聯(lián)文件效率最低。存儲(chǔ)設(shè)備、存取方法和物理結(jié)構(gòu)間的關(guān)系

3存儲(chǔ)設(shè)備磁盤(pán)磁帶物理結(jié)構(gòu)順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)順序結(jié)構(gòu)存取方法順序、直接順序順序、直接順序3.磁盤(pán)調(diào)度算法磁盤(pán)是可以被多個(gè)進(jìn)程共享的設(shè)備。當(dāng)有多個(gè)進(jìn)程都請(qǐng)求訪問(wèn)磁盤(pán)時(shí)，應(yīng)采用一種適當(dāng)?shù)恼{(diào)度算法，以使各進(jìn)程對(duì)磁盤(pán)的平均訪問(wèn)時(shí)間（主要是尋道時(shí)間）最短。下面介紹幾種磁盤(pán)調(diào)度（DiskScheduling）算法。先來(lái)先服務(wù)--FCFS先來(lái)先服務(wù)算法按進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度。特點(diǎn)：簡(jiǎn)單合理，但未對(duì)尋道進(jìn)行優(yōu)化。先來(lái)先服務(wù)算法例平均尋道長(zhǎng)度為：55.314618410150112387016072902118193935845移動(dòng)距離55下一磁道號(hào)從100號(hào)磁道開(kāi)始，磁盤(pán)訪問(wèn)請(qǐng)求為：55、58、39、18、90、160、150、38、184最短尋道時(shí)間優(yōu)先--SSTF最短尋道時(shí)間優(yōu)先（Shortest-Seek-Time-First）算法選擇與當(dāng)前磁頭所在磁道距離最近的請(qǐng)求作為下一次服務(wù)的對(duì)象。特點(diǎn)：尋道性能比FCFS好，但不能保證平均尋道時(shí)間最短，還可能會(huì)使某些請(qǐng)求總也得不到服務(wù)。最短尋道時(shí)間優(yōu)先算法例平均尋道長(zhǎng)度為：27.6241841321501016020181381639355325810移動(dòng)距離90下一磁道號(hào)從100號(hào)磁道開(kāi)始，磁盤(pán)訪問(wèn)請(qǐng)求為：55、58、39、18、90、160、150、38、184掃描算法--SCAN進(jìn)程饑餓：進(jìn)程的請(qǐng)求總也得不到服務(wù)。SCAN算法在磁頭當(dāng)前移動(dòng)方向上選擇與當(dāng)前磁頭所在磁道距離最近的請(qǐng)求作為下一次服務(wù)的對(duì)象。因這種算法中磁頭移動(dòng)規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。特點(diǎn)：具有較好的尋道性能，能避免進(jìn)程饑餓，但不利于兩端磁道的請(qǐng)求。掃描算法例平均尋道長(zhǎng)度為：27.82018163913835532589490241841016050移動(dòng)距離150下一磁道號(hào)從100號(hào)磁道開(kāi)始，向磁道號(hào)增加方向移動(dòng)。磁盤(pán)訪問(wèn)請(qǐng)求為：55、58、39、18、90、160、150、38、184循環(huán)掃描算法CSCANC（circular）SCAN算法是SCAN算法的改良，它規(guī)定磁頭單向移動(dòng)。例如，自里向外移動(dòng)，當(dāng)磁頭移到最外磁道時(shí)立即又返回到最里磁道，如此循環(huán)進(jìn)行掃描。特點(diǎn)：該算法消除了對(duì)兩端磁道請(qǐng)求的不公平。循環(huán)掃描算法例平均尋道長(zhǎng)度為：35.832901655358139203816618241841016050移動(dòng)距離150下一磁道號(hào)從100號(hào)磁道開(kāi)始，向磁道號(hào)增加方向移動(dòng)。磁盤(pán)訪問(wèn)請(qǐng)求為：55、58、39、18、90、160、150、38、184N-Step-SCAN若多個(gè)進(jìn)程反復(fù)請(qǐng)求對(duì)某一磁道的訪問(wèn)，則磁臂可能停留在某處不動(dòng)，這一現(xiàn)象稱為磁臂粘著。N-Step-SCAN算法：將磁盤(pán)請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為N的子隊(duì)列，磁盤(pán)調(diào)度按FCFS算法依次處理這些子隊(duì)列，而處理每個(gè)隊(duì)列時(shí)按SCAN算法進(jìn)行，一個(gè)隊(duì)列處理完后，再處理其他隊(duì)列。FSCAN算法FSCAN算法是N-Step-SCAN算法的簡(jiǎn)化，它只將磁盤(pán)請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列。一個(gè)是當(dāng)前所有請(qǐng)求磁盤(pán)I/O的進(jìn)程形成的隊(duì)列，由磁盤(pán)調(diào)度按SCAN算法進(jìn)行處理，另一個(gè)隊(duì)列則是在掃描期間新出現(xiàn)的磁盤(pán)請(qǐng)求。8.3文件存儲(chǔ)空間的分配及管理為了實(shí)現(xiàn)文件系統(tǒng)，必須解決文件存儲(chǔ)空間的分配和回收問(wèn)題，還應(yīng)對(duì)文件存儲(chǔ)空間進(jìn)行有效的管理。8.3.1文件存儲(chǔ)空間的分配文件存儲(chǔ)空間的分配常采用兩種方式：靜態(tài)分配：在文件建立時(shí)一次分配所需的全部空間。動(dòng)態(tài)分配：根據(jù)需要進(jìn)行分配。在分配區(qū)域大小上，也可以采用不同方法?？梢詾槲募峙湟粋€(gè)連續(xù)區(qū)域，但文件存儲(chǔ)空間的分配通常以塊或簇（幾個(gè)連續(xù)物理塊稱為簇，一般是固定大?。閱挝弧３Ｓ猛獯娣峙浞椒ǔＳ玫耐獯娣峙浞绞接校哼B續(xù)分配鏈接分配索引分配1.連續(xù)分配ContinuousAllocation連續(xù)分配：為文件分配連續(xù)的磁盤(pán)空間。在這種分配方法中，用戶必須在分配前說(shuō)明待創(chuàng)建文件所需的存儲(chǔ)空間大小。然后系統(tǒng)查找空閑區(qū)管理表格，若有就給文件分配所需的存儲(chǔ)空間，否則文件不能建立。連續(xù)分配示意圖

0

1

2

3

4

5

6

7

8910111213141516171819202122232425262728293031323334文件A目錄文件名起始?jí)K號(hào)長(zhǎng)度A23B95C188文件B文件C3536373839連續(xù)分配的特點(diǎn)連續(xù)分配的特點(diǎn)是：順序訪問(wèn)容易且速度快，目錄中文件存儲(chǔ)位置信息簡(jiǎn)單；但容易產(chǎn)生碎片，需要定期對(duì)磁盤(pán)空間進(jìn)行整理。2.鏈接分配LinkedAllocation鏈接分配有兩種實(shí)現(xiàn)方案：以扇區(qū)為單位的鏈接分配以區(qū)段（或簇）為單位的鏈接分配以扇區(qū)為單位的鏈接分配以扇區(qū)為單位的鏈接分配：按文件的要求分配若干個(gè)磁盤(pán)扇區(qū)，屬于同一文件的各扇區(qū)按文件記錄的邏輯次序用鏈接指針鏈接起來(lái)。當(dāng)文件增長(zhǎng)時(shí)就為文件分配新的空閑扇區(qū)，并將其鏈接到文件鏈上；同樣當(dāng)文件縮短時(shí)將釋放的扇區(qū)歸還給系統(tǒng)。特點(diǎn)：消除了碎片，不需要壓縮。但查找慢，鏈接指針的存儲(chǔ)及維護(hù)有一些開(kāi)銷。鏈接分配示意圖

0

1

2

3

4

5

6

7

8910111213141516171819202122232425262728293031323334文件B目錄文件名起始?jí)K號(hào)長(zhǎng)度………B15………3536373839以區(qū)段（或簇）為單位分配以區(qū)段（或簇）為單位分配：是連續(xù)分配和非連續(xù)分配的結(jié)合，現(xiàn)廣為使用。區(qū)段由若干個(gè)連續(xù)扇區(qū)組成，文件所屬各區(qū)段可以用鏈接指針、索引表等方法來(lái)管理。此策略的優(yōu)點(diǎn)是對(duì)輔存的管理效率較高，并減少了文件訪問(wèn)的查尋時(shí)間。文件分配表FileAllocationTable文件分配表FAT是以鏈接方式存儲(chǔ)文件的系統(tǒng)中記錄磁盤(pán)分配和跟蹤空白盤(pán)塊的數(shù)據(jù)結(jié)構(gòu)。該表整個(gè)文件系統(tǒng)僅設(shè)一張，其結(jié)構(gòu)如下所示。表的序號(hào)是物理塊號(hào)，從0開(kāi)始直至N－1（N為盤(pán)塊總數(shù)）。每個(gè)表項(xiàng)中的內(nèi)容為存放文件數(shù)據(jù)的下一個(gè)盤(pán)塊號(hào)。文件的首地址（第一個(gè)盤(pán)塊號(hào)）存放在目錄中。因此，從目錄中找到文件的首地址后，就能找到文件在磁盤(pán)上的所有存放地址。文件分配表示意圖FCB

0451…

2FAT物理塊號(hào)012345…文件分配表例1假定磁盤(pán)塊的大小為1KB，對(duì)于1.2MB的軟盤(pán)，其文件分配表FAT需要占用多少存儲(chǔ)空間？若硬盤(pán)容量為200MB時(shí)，F(xiàn)AT需要占用多少空間？文件分配表例2軟盤(pán)大小為1.2MB，磁盤(pán)塊的大小為1KB，所以該軟盤(pán)共有盤(pán)塊：1.2M/1K=1.2K（個(gè)）又1K＜1.2K＜2K，故1.2K個(gè)盤(pán)塊號(hào)要用11位二進(jìn)制表示，為了方便存取，每個(gè)盤(pán)塊號(hào)用12位二進(jìn)制描述，即文件分配表的每個(gè)表目為1.5個(gè)字節(jié)。FAT要占用的存儲(chǔ)空間總數(shù)為：1.5×1.2K=1.8KB文件分配表例3若硬盤(pán)大小為200MB，硬盤(pán)共有盤(pán)塊：200M/1K=200K又128K＜200K＜256K，故200K個(gè)盤(pán)塊號(hào)要用18位二進(jìn)制表示。為方便文件分配表的存取，每個(gè)表目用20位二進(jìn)制表示，即文件分配表的每個(gè)表目大小為2.5個(gè)字節(jié)。FAT要占用的存儲(chǔ)空間總數(shù)為：2.5×200K=500KB3.索引分配indexedallocation

鏈接分配方式雖解決了連續(xù)分配方式中存在的問(wèn)題，但又出現(xiàn)了新的問(wèn)題：不支持隨機(jī)存取鏈接指針要占用一定數(shù)量的磁盤(pán)空間在索引分配方法中，系統(tǒng)為每個(gè)文件分配一個(gè)索引塊，索引塊中存放索引表，索引表中的每個(gè)表項(xiàng)對(duì)應(yīng)分配給文件的一個(gè)物理塊。索引分配示意圖

0

1

2

3

4

5

6

7

8910111213141516171819202122232425262728293031323334文件B目錄文件名索引地址……B24……18314283536373839索引分配的特點(diǎn)索引分配方法支持直接訪問(wèn)，不會(huì)產(chǎn)生外部碎片；但索引塊要占用一定的存儲(chǔ)空間，存取文件需要兩次訪問(wèn)外存。二級(jí)索引和多級(jí)索引 當(dāng)文件很大，其索引表的大小超過(guò)了一個(gè)物理塊時(shí)，可以將索引表本身作為一個(gè)文件，再為其建立一個(gè)“索引表”，該“索引表”是文件索引的索引，從而構(gòu)成了二級(jí)索引。第一級(jí)索引表的表目指向第二級(jí)索引，第二級(jí)索引表的表目指向文件信息所在的物理塊號(hào)。以此類推可再逐級(jí)建立索引，進(jìn)而構(gòu)成多級(jí)索引。兩級(jí)索引分配示意圖第二級(jí)索引磁盤(pán)空間主索引┇┇┇┇┇360740┇1125┇

105106254┇012┇105106254┇356357┇985

356357

740

985

┇1125360兩級(jí)索引分配允許的文件最大長(zhǎng)度在兩級(jí)索引分配方式下，如果每個(gè)盤(pán)塊的大小為1KB，每個(gè)盤(pán)塊號(hào)占4字節(jié)，則：一個(gè)索引塊中可以存放：1KB/4B=256個(gè)盤(pán)塊號(hào)兩級(jí)索引最多可以存放的盤(pán)塊數(shù)為：256×256=64K個(gè)盤(pán)塊號(hào)因此可以允許的最大文件長(zhǎng)度為：64K×1KB=64MB混合索引分配方式混合索引分配方式是將多種索引分配方式相結(jié)合而形成的一種分配方式。這種方式已用于UNIX、Linux等系統(tǒng)中。在UNIXSystemⅤ中，共設(shè)有13個(gè)地址項(xiàng)，包括10個(gè)直接地址項(xiàng)、一個(gè)一次間接地址項(xiàng)、一個(gè)二次間接地址項(xiàng)和一個(gè)三次間接地址項(xiàng)?；旌纤饕绞绞疽鈭Daddr[0]addr[1]addr[2]addr[3]addr[4]addr[5]addr[6]addr[7]addr[8]addr[9]addr[10]addr[11]addr[12]

……

…

………一次間接塊三次間接塊二次間接塊索引節(jié)點(diǎn)數(shù)據(jù)塊

…

…

…直接地址為了提高對(duì)文件的檢索速度，在索引節(jié)點(diǎn)中建立了10個(gè)直接地址項(xiàng)，每個(gè)地址項(xiàng)中存放相應(yīng)文件所在的盤(pán)塊號(hào)。假定一個(gè)盤(pán)塊的大小為4KB，當(dāng)文件長(zhǎng)度不大于40KB時(shí)，可以直接從索引節(jié)點(diǎn)中得到文件存儲(chǔ)的所有盤(pán)塊號(hào)。一次間接地址一次間接地址項(xiàng)中存放的不是存儲(chǔ)文件數(shù)據(jù)的盤(pán)塊號(hào)，而是先將多個(gè)盤(pán)塊號(hào)存放在一個(gè)磁盤(pán)塊中，再將該磁盤(pán)塊的塊號(hào)存放在一次間接地址項(xiàng)中。若盤(pán)塊大小為4KB，一個(gè)盤(pán)塊號(hào)占4字節(jié)，則一個(gè)盤(pán)塊中可以存放下：4KB/4B=1K個(gè)磁盤(pán)塊號(hào)。一次間接地址項(xiàng)尋址范圍為：1K×4KB=4MB。多次間接地址該地址結(jié)構(gòu)中還有二次間接地址和三次間接地址。二次間接地址的尋址范圍是：1K×1K×4KB=4GB。三次間接地址的尋址范圍是：1K×1K×1K×4KB=4TB。8.3.2空閑存儲(chǔ)空間的管理為了實(shí)現(xiàn)文件存儲(chǔ)空間的分配，首先應(yīng)記住空閑存儲(chǔ)空間的情況。常用的空閑存儲(chǔ)空間管理（Free-SpaceManagement）方法有：空閑文件目錄空閑塊鏈位示圖空閑文件目錄文件存儲(chǔ)設(shè)備上的一個(gè)連續(xù)空閑區(qū)可以看作一個(gè)空閑文件，又稱空白文件或自由文件?？臻e文件目錄方法為所有空閑文件建立一個(gè)目錄，每個(gè)空閑文件在該目錄中占一個(gè)表目，其中至少包括：空閑區(qū)序號(hào)、第一個(gè)空閑塊塊號(hào)、空閑塊數(shù)目等信息?？臻e文件目錄示例下面給出了一個(gè)空閑目錄的例子。序號(hào)第一個(gè)空閑塊號(hào)空閑塊個(gè)數(shù)物理塊號(hào)153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4------空閑文件目錄法的空閑空間管理當(dāng)請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)依次掃描空閑文件目錄，直到找到一個(gè)能滿足要求的空閑文件為止。若該文件大小大于申請(qǐng)空間量則還要進(jìn)行劃分。當(dāng)回收存儲(chǔ)空間時(shí)，也需要順序掃描空閑文件目錄，尋找一個(gè)空表目，并將釋放空間的第一個(gè)物理塊號(hào)以及釋放空間的塊數(shù)填到這個(gè)表目中。若釋放空間與已有空閑文件鄰接，則需進(jìn)行合并?？臻e文件目錄法的特點(diǎn)顯然，只要將動(dòng)態(tài)分區(qū)管理方法中的算法稍作修改，即可用于空閑文件目錄方法。特點(diǎn)：僅當(dāng)文件存儲(chǔ)空間中只有少量空閑文件時(shí)該方法有比較好的效果，否則空閑目錄變大導(dǎo)致其效率下降。該方法僅適用于連續(xù)文件。2.空閑塊鏈空閑塊鏈方法（LinkedFreeSpaceList）將文件存儲(chǔ)設(shè)備上的所有空閑塊鏈接起來(lái)，并設(shè)置一個(gè)頭指針指向空閑塊鏈的第一個(gè)物理塊。當(dāng)申請(qǐng)分配存儲(chǔ)空間時(shí)，就按需要從鏈?zhǔn)滓来稳∠聨讉€(gè)物理塊分配給文件。當(dāng)回收存儲(chǔ)空間時(shí)，將回收的空閑塊依次鏈入空閑塊鏈中?？臻e塊鏈的特點(diǎn)及改進(jìn)特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單但工作效率低，因?yàn)樵诳臻e塊鏈上增加或移去空閑塊時(shí)要進(jìn)行鏈表操作。一種改進(jìn)方法是將空閑塊分成若干組，再用指針將組與組鏈接起來(lái)，將這種管理空閑塊的方法稱為成組鏈接法。成組鏈接法在進(jìn)行空閑塊的分配與回收時(shí)要比空閑塊鏈方法節(jié)省時(shí)間。成組鏈接法UNIX系統(tǒng)采用成組鏈接法對(duì)空閑盤(pán)塊加以組織?？臻e盤(pán)塊的組織：將若干個(gè)空閑盤(pán)塊劃歸一組，將每組中的所有盤(pán)塊號(hào)存放在其前一組的第一個(gè)空閑盤(pán)塊號(hào)指示的盤(pán)塊中，而將第一組中的所有空閑盤(pán)塊號(hào)放入超級(jí)塊的空閑盤(pán)塊號(hào)表中。成組鏈接法示意圖10910610310095超級(jí)塊空閑盤(pán)塊號(hào)表211208205…112109310307304…214211409406403…313310空閑盤(pán)塊的分配當(dāng)要分配一個(gè)盤(pán)塊時(shí)，首先將超級(jí)塊空閑盤(pán)塊號(hào)表中下一個(gè)可用盤(pán)塊分配出去；如果所分配盤(pán)塊號(hào)是超級(jí)塊中最后一個(gè)可用盤(pán)塊號(hào)，則先將該盤(pán)塊中的內(nèi)容讀入超級(jí)塊空閑盤(pán)塊號(hào)表中，然后才將該盤(pán)塊分配出去。分配超級(jí)塊中最后一個(gè)盤(pán)塊號(hào)例分配前分配后109超級(jí)塊空閑盤(pán)塊號(hào)表211208205…112109310307304…214211409406403…313310超級(jí)塊空閑盤(pán)塊號(hào)表211208205…