1、第8章 文件管理n 文件系統(tǒng)負責管理外存上的文件，并為用戶提供對文件進行存取、共享及保護的手段。8.1文件系統(tǒng)的概念-8.1.1文件系統(tǒng)n 文件是具有文件名的一組相關(guān)記錄的集合。文件由若干記錄組成。n 記錄是一些相關(guān)數(shù)據(jù)項的集合。n 數(shù)據(jù)項是數(shù)據(jù)組織中可以命名的最小邏輯單位。文件系統(tǒng) file systemn 文件系統(tǒng)：操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)的集合。n 它由管理文件所需的數(shù)據(jù)結(jié)構(gòu)、相應的管理軟件和被管理的文件構(gòu)成。文件系統(tǒng)的主要功能n 實現(xiàn)文件的按名存取n 為用戶提供接口n 實施對文件和目錄的管理n 文件存儲空間的分配及回收n 文件的共享及保護文件系統(tǒng)的層次結(jié)構(gòu)n 文件系統(tǒng)的層次

2、結(jié)構(gòu)包含四層：基本I/O控制層基本文件系統(tǒng)層基本I/O管理程序?qū)舆壿嬑募到y(tǒng)層n 不同操作系統(tǒng)中，文件系統(tǒng)的組成方法不一樣，但這種組成具有代表性?；綢/O控制層n 基本I/O控制層（I/O control level）Basic又稱設(shè)備驅(qū)動程序?qū)?，該層主要由?qū)動程序組成，負責啟動設(shè)備I/O操作及對設(shè)備發(fā)來的中斷信號進行處理。基本文件系統(tǒng)層n 基本文件系統(tǒng)層（）Basic file system level又稱物理I/O層，該層負責處理內(nèi)存和外存之間的數(shù)據(jù)塊交換。n 它關(guān)心數(shù)據(jù)塊在外存和在緩沖區(qū)中的位置，無須了解傳送數(shù)據(jù)塊的內(nèi)容或文件結(jié)構(gòu)?；綢/O管理程序?qū)觧 基本I/O管理程序?qū)佑址Q文件組

3、織模塊層File-organization modulelevel），負責所（有文件I/O的初始化和終止。n 該層完成的工作包括選擇文件所在的設(shè)備、進行文件邏輯塊號到物理塊號的轉(zhuǎn)換、優(yōu)化磁盤調(diào)度的性能、對文件空閑存儲空間進行管理等。邏輯文件系統(tǒng)層n 邏輯文件系統(tǒng)層（Thelogicalfilesystemlevel）負責處理文件及記錄的相關(guān)操作。n 如允許用戶利用文件名訪問文件及其中的記錄、實現(xiàn)對文件及記錄的保護、實現(xiàn)目錄操作等。文件系統(tǒng)的層次結(jié)構(gòu)圖物理磁盤邏輯文件系統(tǒng)層基本I/O管理程序?qū)踊疚募到y(tǒng)層基本I/O控制層文件系統(tǒng)接口8.1.2 文件分類n 為了便于管理和控制文件，將文件分為若干

4、類型。不同系統(tǒng)對文件的管理方式不同，因而對文件的分類方法也有很大差異。n 常見的文件分類方法有：1. 按用途分類n 按用途可以將文件分為：n 系統(tǒng)文件：系統(tǒng)軟件構(gòu)成的文件。n 庫文件：系統(tǒng)提供給用戶使用的各種標準過程、函數(shù)和應用程序。n 用戶文件：用戶委托文件系統(tǒng)保存的文件。2. 按保護級別分類n 按保護級別可將文件分為：n 只讀文件：允許所有者或授權(quán)用戶對其進行讀，但不允許寫。n 讀寫文件：允許所有者或授權(quán)用戶對其進行讀寫，但禁止未核準用戶讀寫。n 執(zhí)行文件：允許核準用戶調(diào)用執(zhí)行，但不允許對其進行讀寫。n 不保護文件：不加任何訪問限制的文件。3. 按信息流向分類n 按信息流向可以將文件分為：

5、n 輸入文件：來自輸入設(shè)備的文件，如來自鍵盤的輸入文件。n 輸出文件：寫向輸出設(shè)備的文件，如寫向打印機的輸出文件。n 輸入輸出文件：如磁盤上的文件，既可以讀又可以寫。4. 按數(shù)據(jù)形式分類n 按數(shù)據(jù)形式可以將文件分為：n 源文件：由源程序和數(shù)據(jù)構(gòu)成的文件。n 目標文件：源程序經(jīng)過編譯程序編譯，但尚未鏈接成可執(zhí)行代碼的目標代碼文件。n 可執(zhí)行文件：由鏈接程序鏈接后形成的可以運行的文件。8.2文件結(jié)構(gòu)及存儲設(shè)備n 文件結(jié)構(gòu)指文件的組織形式，文件有兩種形式的結(jié)構(gòu)：n 邏輯結(jié)構(gòu)：又稱文件組織，是從用戶觀點出發(fā)所看到的文件組織形式。n 物理結(jié)構(gòu)：又稱文件的存儲結(jié)構(gòu)，是文件在外存上的存儲組織形式。它與存儲設(shè)

6、備特性、外存分配方式有關(guān)。8.2.1 文件的邏輯結(jié)構(gòu)n 文件的邏輯結(jié)構(gòu)可分為兩類：n 記錄式文件：是一種有結(jié)構(gòu)文件，由一組相關(guān)記錄組成。又分為：n 等長記錄文件：又稱定長記錄文件，是指文件中所有記錄的長度相等。n 變長記錄文件：是指文件中各記錄長度不相等。n 流式文件：是一種無結(jié)構(gòu)文件，由字符序列構(gòu)成。記錄式文件的組織方式n 根據(jù)用戶和系統(tǒng)管理的需要，可以采用多種方式來組織記錄式文件：n 順序文件：一組記錄按關(guān)鍵字的大小順序排列所形成的文件。其中的記錄通常是定長的。n 索引文件：為文件設(shè)置一個索引表，文件中的每個記錄在索引表中有一個表項，用于存放記錄的存放地址及長度。n 索引順序文件：是前兩者

7、的結(jié)合。它將順序文件中的所有記錄分成若干組，為順序文件建立一張索引表， 為每組中的第一個記錄建立一個索引項，其中含有該記錄的鍵值和指向該記錄的指針。8.2.2 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)與存儲介質(zhì)的存儲特性及外存分配方式有關(guān)。文件存儲設(shè)備通常劃分為大小相等的物理塊，物理塊是分配及傳輸信息的基本單位。物理塊的大小與設(shè)備有關(guān)，但與邏輯記錄的大小無關(guān)，因此一個物理塊中可以存放若干個邏輯記錄，一個邏輯記錄也可以存放在若干個物理塊中。為有效地利用外存設(shè)備和便于系統(tǒng)管理，一般也把文件信息劃分為與物理存儲塊大小相等的邏輯塊。物理結(jié)構(gòu)類型n 常見的文件物理結(jié)構(gòu)有以下幾種形式：n 順序結(jié)構(gòu)n 鏈接結(jié)構(gòu)n 索引

8、結(jié)構(gòu)順序結(jié)構(gòu)n 順序結(jié)構(gòu)又稱連續(xù)結(jié)構(gòu)，它將一個在邏輯上連續(xù)的信息存放在外存連續(xù)的物理塊中。n 以順序結(jié)構(gòu)存放的文件稱為順序文件或連續(xù)文件。n 特點：順序存取速度較快；對等長記錄文件支持隨機訪問。但因要求連續(xù)存放，會產(chǎn)生碎片，同時也不利于文件的動態(tài)擴充。鏈接結(jié)構(gòu)n 鏈接結(jié)構(gòu)又稱串聯(lián)結(jié)構(gòu)，它將一個邏輯文件的信息存放在外存不連續(xù)物理塊中，且在每個物理塊中設(shè)置一個指向下一個物理塊的指針。n 采用鏈接結(jié)構(gòu)存放的文件稱為鏈接文件或串聯(lián)文件。n 特點：可解決碎片問題，便于文件動態(tài)增長。但只能順序訪問，因而查找效率較低，指針占用存儲空間。索引結(jié)構(gòu)n 索引結(jié)構(gòu)：將一個邏輯文件的信息存放于外存的若干個物理塊中，并

9、為每個文件建立一個索引表，其中的每個表目存放文件信息所在的邏輯塊號和與之對應的物理塊號。n 采用索引結(jié)構(gòu)存放的文件稱為索引文件。n 特點：既可以順序訪問也可以隨機訪問，但增加了存儲空間開銷，且要兩次訪問外存。8.2.3 文件存取方法n 常用的文件存取方法（ Access Methodsn 順序存取法 Sequential Accessn 直接存取法 Direct Accessn 按鍵存取法）有：1.順序存取法n 順序存取法是按照文件信息的邏輯順序依次存取。n 在記錄式文件中，順序存取反映為按記錄的排列順序來存?。辉诹魇轿募校樞虼嫒》从碁楫斍白x寫指針的變化。n 對定長記錄的順序文件，若知道當

10、前記錄地址，則很易確定下一個記錄地址。rptrrptrLn 其中L為文件記錄的長度，rptr為讀寫指針。2.直接存取法n 直接存取法又稱隨機存取法，允許按任意順序存取文件中的任何一個物理記錄。n 對于定長記錄的順序文件，若知道文件的起始地址和記錄長度，則第i個記錄（i0，1，2，）的首地址為rptraddriLn 其中addr是該文件的首地址，L為記錄長度。3.按鍵存取法n 按鍵存取法實質(zhì)上也是直接存取法，它根據(jù)文件記錄中數(shù)據(jù)項（通常稱為鍵），經(jīng)過某種方法計算處理，轉(zhuǎn)換成相應的物理地址后進行存取。8.2.4 文件存儲設(shè)備-1n 文件的存儲設(shè)備主要有磁帶、磁盤、光盤等。n 存儲設(shè)備的特性可以決定

11、文件的存取方法。n 下面介紹以磁帶為代表的順序存取設(shè)備和以磁盤為代表的直接存取設(shè)備。磁帶 Magnetic tapen 磁帶是一種典型的順序存取設(shè)備。由于磁帶機的啟動和停止要花費一定的時間， 因此在磁帶的相鄰物理塊之間設(shè)計有一段間隙將它們隔開，如下所示。磁帶間隙第i塊間隙第i1塊間隙磁帶（續(xù)）n 磁帶的存取速度與信息密度（字符數(shù)/英寸）、磁帶帶速（英寸/秒）和塊間間隙有關(guān)。n 如果帶速高、信息密度大且所需塊間隙（磁頭啟動和停止時間）小，則磁帶存取速度高。反之，若磁帶帶速低、信息密度小且所需塊間隙（磁帶啟動和停止時間）大，則磁帶存取速度低。磁盤磁盤是典型的直接存取設(shè)備。磁盤一般由若干磁盤片組成，

12、可沿一個固定方向高速旋轉(zhuǎn)。每個盤面對應一個磁頭，磁臂可沿半徑方向移動。磁盤上的一系列同心圓稱為磁道（track），磁道沿徑向又分成大小相等的多個扇區(qū)（sector），與盤片中心有一定距離的所有磁道組成一個柱面（cylinder）。磁盤上的每個物理塊可用柱面號，磁頭號和扇區(qū)號表示。磁盤數(shù)據(jù)組織和格式示意圖07磁臂46315243磁頭磁道 第i扇區(qū)間隙標識字段間隙數(shù)據(jù)字段間隙邏輯扇區(qū)n 將一個磁盤上的扇區(qū)從0柱面開始，按柱面順序依次編號，所得到的編號成為邏輯扇區(qū)號。n 邏輯扇區(qū)號=柱面號*每柱面扇區(qū)數(shù)+磁頭號*每磁頭扇區(qū)數(shù)+ 扇區(qū)號其中，柱面號、磁頭號、扇區(qū)號都從0開始磁盤訪問時間n 磁盤訪問時間

13、由三部分組成：n 尋道時間（seek time）：指將磁頭從當前位置移動到指定磁道所經(jīng)歷的時間。由啟動磁臂時間和磁頭移動多條磁道的時間構(gòu)成。n 旋轉(zhuǎn)延遲時間（rotationallatency）：指扇區(qū)移動到磁頭下面所經(jīng)歷的時間。平均旋轉(zhuǎn)延遲時間是每轉(zhuǎn)所需時間的一半。n 傳輸時間（tranfertime）：指從磁盤上讀出數(shù)據(jù)或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時間。n 由于這三部分操作均涉及機械運動，故磁盤塊的訪問時間約為0.010.1s之間，其中尋道時間所占的比例最大。2.存儲設(shè)備、存取方法和物理結(jié)構(gòu)的關(guān)系1n 文件的物理結(jié)構(gòu)與文件存儲器的特性和存取方法密切相關(guān)。n 磁帶是一種順序存取設(shè)備，適合采用順序

14、結(jié)構(gòu)存放文件，相應的存取方法通常是順序存取法。若采用其他文件結(jié)構(gòu)或采用直接存取方式都不太合適。存儲設(shè)備、存取方法和物理結(jié)構(gòu)的關(guān)系2n 磁盤屬于直接存取存儲設(shè)備，前述的幾種物理結(jié)構(gòu)都可以采用。存取方法也可以多種多樣。n 如果采用順序存取法則前述的幾種文件結(jié)構(gòu)都可以采用。如果采用直接存取法，則索引文件效率最高，順序文件效率居中，串聯(lián)文件效率最低。存儲設(shè)備、存取方法和物理結(jié)構(gòu)間的關(guān)系 3存儲設(shè)備磁 盤磁 帶物理結(jié)構(gòu)順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)順序結(jié)構(gòu)存取方法順序、直接順序順序、直接順序3. 磁盤調(diào)度算法n 磁盤是可以被多個進程共享的設(shè)備。當有多個進程都請求訪問磁盤時，應采用一種適當?shù)恼{(diào)度算法，以使各進程

15、對磁盤的平均訪問時間（主要是尋道時間） 最短。 下面介紹幾種磁盤調(diào)度（ DiskScheduling ）算法。先來先服務-FCFSn 先來先服務算法按進程請求訪問磁盤的先后次序進行調(diào)度。n 特點：簡單合理，但未對尋道進行優(yōu)化。先來先服務算法例從100號磁道開始，磁盤訪問請求為：55、58、39、18、90、160、150、38、184平均尋道長度為：55.3下一磁道號移動距離5545583391918219072160701501038112184146最短尋道時間優(yōu)先-SSTFn 最 短 尋 道 時 間 優(yōu) 先 （ Shortest-Seek- Time-First）算法選擇與當前磁頭所在磁

16、道距離最近的請求作為下一次服務的對象。n 特點：尋道性能比FCFS好，但不能保證平均尋道時間最短，還可能會使某些請求總也得不到服務。最短尋道時間優(yōu)先算法例從100號磁道開始，磁盤訪問請求為：55、58、39、18、90、160、150、38、184平均尋道長度為：27.6下一磁道號移動距離90105832553391638118201501321601018424掃描算法-SCANn 進程饑餓：進程的請求總也得不到服務。n SCAN算法在磁頭當前移動方向上選擇與當前磁頭所在磁道距離最近的請求作為下一次服務的對象。因這種算法中磁頭移動規(guī)律頗似電梯的運行，故又稱為電梯調(diào)度算法。n 特點：具有較好的

17、尋道性能，能避免進程饑餓，但不利于兩端磁道的請求。掃描算法例從100號磁道開始，向磁道號增加方向移動。磁盤訪問請求為：55、58、39、18、90、160、150、38、184平均尋道長度為：27.8下一磁道號移動距離1505016010184249094583255339163811820循環(huán)掃描算法CSCANn C（circular）SCAN算法是SCAN算法的改良，它規(guī)定磁頭單向移動。例如，自里向外移動，當磁頭移到最外磁道時立即又返回到最里磁道，如此循環(huán)進行掃描。n 特點：該算法消除了對兩端磁道請求的不公平。循環(huán)掃描算法例從100號磁道開始，向磁道號增加方向移動。磁盤訪問請求為：55、5

18、8、39、18、90、160、150、38、184平均尋道長度為：35.8下一磁道號移動距離15050160101842418166382039155165839032N-Step-SCANn 若多個進程反復請求對某一磁道的訪問，則磁臂可能停留在某處不動，這一現(xiàn)象稱為磁臂粘著。n N-Step-SCAN算法：將磁盤請求隊列分成若干個長度為N的子隊列， 磁盤調(diào)度按FCFS算法依次處理這些子隊列，而處理每個隊列時按SCAN算法進行，一個隊列處理完后，再處理其他隊列。FSCAN算法n FSCAN 算法是N-Step-SCAN 算法的簡化， 它只將磁盤請求隊列分成兩個子隊列。一個是當前所有請求磁盤I/

19、O的進程形成的隊列，由磁盤調(diào)度按SCAN算法進行處理，另一個隊列則是在掃描期間新出現(xiàn)的磁盤請求。8.3 文件存儲空間的分配及管理n 為了實現(xiàn)文件系統(tǒng)，必須解決文件存儲空間的分配和回收問題，還應對文件存儲空間進行有效的管理。8.3.1 文件存儲空間的分配n 文件存儲空間的分配常采用兩種方式：n 靜態(tài)分配：在文件建立時一次分配所需的全部空間。n 動態(tài)分配：根據(jù)需要進行分配。n 在分配區(qū)域大小上，也可以采用不同方法?？梢詾槲募峙湟粋€連續(xù)區(qū)域，但文件存儲空間的分配通常以塊或簇（幾個連續(xù)物理塊稱為簇，一般是固定大小）為單位。常用外存分配方法n 常用的外存分配方式有：n 連續(xù)分配n 鏈接分配n 索引分配

20、1. 連續(xù)分配 Continuous Allocationn 連續(xù)分配：為文件分配連續(xù)的磁盤空間。n 在這種分配方法中，用戶必須在分配前說明待創(chuàng)建文件所需的存儲空間大小。然后系統(tǒng)查找空閑區(qū)管理表格，若有就給文件分配所需的存儲空間，否則文件不能建立。連續(xù)分配示意圖文件A012345目錄6789文件B1011121314文件C15161718192021222324252627282930313233343536373839文件名起始塊號長度A23B95C188連續(xù)分配的特點n 連續(xù)分配的特點是：n 順序訪問容易且速度快，目錄中文件存儲位置信息簡單；n 但容易產(chǎn)生碎片，需要定期對磁盤空間進行整理。

21、2. 鏈接分配 Linked Allocationn 鏈接分配有兩種實現(xiàn)方案：n 以扇區(qū)為單位的鏈接分配n 以區(qū)段（或簇）為單位的鏈接分配以扇區(qū)為單位的鏈接分配n 以扇區(qū)為單位的鏈接分配：按文件的要求分配若干個磁盤扇區(qū)，屬于同一文件的各扇區(qū)按文件記錄的邏輯次序用鏈接指針鏈接起來。n 當文件增長時就為文件分配新的空閑扇區(qū)，并將其鏈接到文件鏈上；同樣當文件縮短時將釋放的扇區(qū)歸還給系統(tǒng)。n 特點：消除了碎片，不需要壓縮。但查找慢，鏈接指針的存儲及維護有一些開銷。鏈接分配示意圖文件B01234目錄56789101112131415161718192021222324252627282930313233

22、343536373839文件名起始塊號長度B15以區(qū)段（或簇）為單位分配n 以區(qū)段（或簇）為單位分配：是連續(xù)分配和非連續(xù)分配的結(jié)合，現(xiàn)廣為使用。區(qū)段由若干個連續(xù)扇區(qū)組成，文件所屬各區(qū)段可以用鏈接指針、索引表等方法來管理。n 此策略的優(yōu)點是對輔存的管理效率較高， 并減少了文件訪問的查尋時間。文件分配表File Allocation Tablen 文件分配表FAT是以鏈接方式存儲文件的系統(tǒng)中記錄磁盤分配和跟蹤空白盤塊的數(shù)據(jù)結(jié)構(gòu)。n 該表整個文件系統(tǒng)僅設(shè)一張，其結(jié)構(gòu)如下所示。表的序號是物理塊號，從0開始直至N1（N為盤塊總數(shù)）。n 每個表項中的內(nèi)容為存放文件數(shù)據(jù)的下一個盤塊的首地址（第一個盤塊號）存

23、放在目錄中。因此，從目錄中找到文件的首地址后，就能找到文件在磁盤上的所有存放地址。文件分配表示意圖FAT物理塊號FCB01234504512文件分配表例1n 假定磁盤塊的大小為1KB，對于1.2MB的軟盤，其文件分配表FAT需要占用多少存儲空間？n 若硬盤容量為200MB時，F(xiàn)AT需要占用多少空間？文件分配表例2n 軟盤大小為1.2MB，磁盤塊的大小為1KB，所以該軟盤共有盤塊：1.2M/1K=1.2K（個）1K1.2K2K，n 又n 故1.2K個盤塊號要用11位二進制表示，為了方便存取，每個盤塊號用12位二進制描述，即文件分配表的每個表目為1.5個字節(jié)。n FAT要占用的存儲空間總數(shù)為：1.

24、51.2K=1.8KB文件分配表例3n 若硬盤大小為200MB，硬盤共有盤塊：200M/1K=200Kn 又 128K200K256K，n 故200K個盤塊號要用18位二進制表示。為方便文件分配表的存取，每個表目用20位二進制表示，即文件分配表的每個表目大小為2.5個字節(jié)。n FAT要占用的存儲空間總數(shù)為： 2.5200K=500KB3. 索引分配 indexed allocationn 鏈接分配方式雖解決了連續(xù)分配方式中存在的問題，但又出現(xiàn)了新的問題：n 不支持隨機存取n 鏈接指針要占用一定數(shù)量的磁盤空間n 在索引分配方法中，系統(tǒng)為每個文件分配一個索引塊，索引塊中存放索引表，索引表中的每個表

25、項對應分配給文件的一個物理塊。索引分配示意圖文件B01234目錄567891011121314151617181920212223242526272829303132333435363738391831428文件名索引地址B24索引分配的特點n 索引分配方法支持直接訪問，不會產(chǎn)生外部碎片；n 但索引塊要占用一定的存儲空間，存取文件需要兩次訪問外存。二級索引和多級索引當文件很大，其索引表的大小超過了一個物理塊時，可以將索引表本身作為一個文件，再為其建立一個“索引表”，該“索引表”是文件索引的索引，從而構(gòu)成了二級索引。第一級索引表的表目指向第二級索引，第二級索引表的表目指向文件信息所在的物理塊號。

26、以此類推可再逐級建立索引，進而構(gòu)成多級索引。兩級索引分配示意圖第二級索引360012740105106254356357985主索引1125磁盤空間9853563573607401125105106254兩級索引分配允許的文件最大長度n 在兩級索引分配方式下，如果每個盤塊的大小為1KB，每個盤塊號占4字節(jié)，則：n 一個索引塊中可以存放：1KB/4B=256個盤塊號n 兩級索引最多可以存放的盤塊數(shù)為：256256=64K個盤塊號n 因此可以允許的最大文件長度為：64K1KB=64MB混合索引分配方式n 混合索引分配方式是將多種索引分配方式相結(jié)合而形成的一種分配方式。這種方式已用于UNIX、Lin

27、ux等系統(tǒng)中。n 在UNIX System 設(shè)有13個地址項，包括10個直接地址項、一個一次間接地址項、一個二次間接地址項和一個三次間接地址項。混合索引方式示意圖數(shù)據(jù)塊索引節(jié)點addr 0 addr1 addr2 addr3 addr4 addr5 addr6 addr7 addr8 addr9 addr10 addr11 addr12一次間接塊二次間接塊三次間接塊直接地址n 為了提高對文件的檢索速度，在索引節(jié)點中建立了10個直接地址項，每個地址項中存放相應文件所在的盤塊號。n 假定一個盤塊的大小為4KB，當文件長度不大于40KB時，可以直接從索引節(jié)點中得到文件存儲的所有盤塊號。一次間接地址n

28、 一次間接地址項中存放的不是存儲文件數(shù)據(jù)的盤塊號，而是先將多個盤塊號存放在一個磁盤塊中，再將該磁盤塊的塊號存放在一次間接地址項中。n 若盤塊大小為4KB，一個盤塊號占4字節(jié)，則一個盤塊中可以存放下：4KB/4B=1K個磁盤塊號。n 一次間接地址項尋址范圍為：1K4KB=4MB。多次間接地址n 該地址結(jié)構(gòu)中還有二次間接地址和三次間接地址。n 二次間接地址的尋址范圍是：1K1K4KB=4GB。n 三次間接地址的尋址范圍是：1K1K1K4KB=4TB。8.3.2 空閑存儲空間的管理n 為了實現(xiàn)文件存儲空間的分配，首先應記住空閑存儲空間的情況。n 常用的空閑存儲空間管理（ Free-Space Man

29、agement）方法有：n 空閑文件目錄n 空閑塊鏈n 位示圖空閑文件目錄n 文件存儲設(shè)備上的一個連續(xù)空閑區(qū)可以看作一個空閑文件，又稱空白文件或自由文件。n 空閑文件目錄方法為所有空閑文件建立一個目錄，每個空閑文件在該目錄中占一個表目，其中至少包括：空閑區(qū)序號、第一個空閑塊塊號、空閑塊數(shù)目等信息?？臻e文件目錄示例n 下面給出了一個空閑目錄的例子。序號第一個空閑塊號空閑塊個數(shù)物理塊號153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-空閑文件目錄法的空閑空間管理n 當請求分配存儲空間時，系統(tǒng)依次掃描空閑文件目錄，直到找到一個能滿足要求的空

30、閑文件為止。若該文件大小大于申請空間量則還要進行劃分。n 當回收存儲空間時，也需要順序掃描空閑文件目錄，尋找一個空表目，并將釋放空間的第一個物理塊號以及釋放空間的塊數(shù)填到這個表目中。若釋放空間與已有空閑文件鄰接，則需進行合并。空閑文件目錄法的特點n 顯然，只要將動態(tài)分區(qū)管理方法中的算法稍作修改，即可用于空閑文件目錄方法。n 特點：僅當文件存儲空間中只有少量空閑文件時該方法有比較好的效果，否則空閑目錄變大導致其效率下降。該方法僅適用于連續(xù)文件。2. 空閑塊鏈inkedFreeSpaceList）n 空閑塊鏈方將文件存儲設(shè)備上的所有空閑塊鏈接起來，并設(shè)置一個頭指針指向空閑塊鏈的第一個物理塊。n 當申請分配存儲空間時，就按需要從鏈首依次取下幾個物理塊分配給文件。當回收存儲空間時，將回收的空閑塊依次鏈入空閑塊鏈中?？臻e塊鏈的特點及改進n 特點：實現(xiàn)簡單但工作效率低，因為在空閑塊鏈上增加或移去空閑塊時要進行鏈表操作。n 一種改進方法是將空閑塊分成若干組，再用指針將組與組鏈接起來，將這種管理空閑塊的方法稱為成組鏈接法。成組鏈接法在進行空閑塊的分配與回收時要比空閑塊鏈方法節(jié)省時間。成組鏈接法n UNIX系統(tǒng)采用成組鏈接法對空閑盤塊加以組織。n 空閑盤塊的組織：將若干個空閑盤塊劃歸一組，將每組中的所有盤塊號存放在其前一組的第一個空閑盤塊號指示的盤塊中， 而