文件空間管理主要內(nèi)容一、文件存儲方法二、文件輔存空間管理一、文件存儲方法（1）文件存儲方法指文件的物理存儲結(jié)構(gòu)，有內(nèi)容的磁盤塊的組織方法文件存儲方法1、連續(xù)存儲2、鏈接存儲3、索引存儲4、多級索引存儲一、磁盤信息分區(qū)（2）連續(xù)存儲將文件存放在外存連續(xù)存儲區(qū)中，即為磁盤文件分配一組連續(xù)的塊，文件內(nèi)容的邏輯順序與物理存儲順序一致。1、連續(xù)存儲通過分配連續(xù)塊建立的文件稱為連續(xù)文件。隨著文件的創(chuàng)建和刪除，磁盤連續(xù)分區(qū)被分配和回收，整個磁盤空間被分割為文件區(qū)和空閑區(qū)交替出現(xiàn)的格局；一、磁盤信息分區(qū)（2）系統(tǒng)需要登記各個空閑區(qū)的位置和大小以供分配使用。文件區(qū)的位置和大小需要登記在目錄中以供文件查找訪問。一、磁盤信息分區(qū)（2）連續(xù)存儲示例一、磁盤信息分區(qū)（2）連續(xù)存儲的缺點1、建立文件前需要用戶給出文件長度，以便系統(tǒng)查找和分配滿足要求的連續(xù)存儲區(qū)。而用戶很難確切知道最終創(chuàng)建的文件的大小。不完全解決方法：逐步追加空閑盤塊，不過無法保證追加塊與已分配給文件的塊是連續(xù)的。2、連續(xù)存儲方案對修改、插入和增加文件記錄有困難。一、磁盤信息分區(qū)（2）連續(xù)存儲的優(yōu)點1、連續(xù)存儲的文件存取高效，尋道時間短。2、連續(xù)存儲非常適合文件轉(zhuǎn)儲、備份時的存儲空間分配。一、磁盤信息分區(qū)（2）鏈接存儲有以磁盤塊為單位的鏈接存儲和以簇為單位的鏈接存儲。2、鏈接存儲1）磁盤塊鏈接存儲鏈接存儲是一種非連續(xù)存儲方案，即離散存儲方案，文件允許存放在位置不連續(xù)的磁盤塊中，各個磁盤塊中文件內(nèi)容的邏輯順序采用磁盤塊中的指針來指示。第一塊的磁盤地址只要登記在目錄項中即可通過目錄訪問整個文件。一、磁盤信息分區(qū)（2）鏈接存儲示例一、磁盤信息分區(qū)（2）鏈接存儲的優(yōu)點1、鏈接存儲便于文件內(nèi)容的增加、刪除、修改，創(chuàng)建文件時不需要說明文件大小，無需合并磁盤空間。鏈接存儲的缺點1、指針占據(jù)了一些字節(jié)，要讀取一整塊文件內(nèi)容時，需要讀兩個物理塊并進(jìn)行拼接，增加了I/O操作的復(fù)雜性和開銷。2、鏈接文件所占物理塊分散，尋道操作頻繁，增加I/O尋道時間。一、磁盤信息分區(qū)（2）2）磁盤簇鏈接存儲磁盤簇鏈接存儲以簇為文件空間分配單位，建立簇之間的指針鏈接關(guān)系。一個簇由多個連續(xù)的磁盤塊組成。1、指針在簇中比在塊中占用的磁盤空間百分比降低，磁盤輸入輸出時，磁頭移動頻率降低，空閑簇管理所需空間減少。磁盤簇鏈接存儲的優(yōu)點一、磁盤信息分區(qū)（2）1、簇會造成較大的內(nèi)部碎片。2、可靠性不高，一旦指針損壞或丟失，將無法訪問整個文件。磁盤簇鏈接存儲的缺點一、磁盤信息分區(qū)（2）3）文件分配表（FAT）文件分配表是鏈接存儲方法的變種。FAT將原來分布在文件存儲塊中的指針集中存放在一個單獨的表（FAT）中，每個存儲塊都在該表中占有一項，每項元素以存儲塊號為索引，每項元素值是該項存儲塊的后繼塊的塊號。未使用的塊用0值表示。目錄項中存放文件首塊號碼。文件分配表（FAT）示例一、磁盤信息分區(qū)（2）一、磁盤信息分區(qū)（2）為文件分配空閑塊時，從FAT中找到第一個值為0的FAT表目，用該表目的索引號替換前面的文件結(jié)束值，用文件結(jié)束值替代該表目的元素值0。訪問文件時，從目錄出發(fā)獲得文件首塊號碼，從該號碼出發(fā)遍歷FAT中存放的文件塊鏈，即可訪問文件所在各個存儲塊的內(nèi)容。一、磁盤信息分區(qū)（2）索引存儲為每個文件建立一張索引表，文件各個內(nèi)容存儲塊地址依次記錄在各個表目中，索引表存儲塊地址登記在目錄項中。3、索引存儲訪問文件時，從目錄項出發(fā)獲取索引表，根據(jù)索引表記載的文件塊地址即可訪問文件各部分的內(nèi)容。帶有索引表的文件稱為索引文件。索引表分為無鍵索引和有鍵索引。一、磁盤信息分區(qū)（2）無鍵索引示例一、磁盤信息分區(qū)（2）有鍵索引示例一、磁盤信息分區(qū)（2）索引項分為兩類：一類是稠密索引，即對每個數(shù)據(jù)記錄建立一個索引項；另一類是稀疏索引，對每一組數(shù)據(jù)記錄建立一個索引項。為一組記錄建立一個表項構(gòu)成的索引文件稱為索引順序文件。一、磁盤信息分區(qū)（2）1、便于直接存取，便于文件的增、刪、改。索引存儲的優(yōu)點1、增加了索引表的空間開銷和查找時間。索引存儲的缺點一、磁盤信息分區(qū)（2）當(dāng)索引表很大時，索引表也會占用較多物理塊，可能沒有足夠大的連續(xù)存儲空間用來存儲巨大的索引表，采用離散空間存儲索引表就需要創(chuàng)建索引表的索引表，形成多級索引存儲結(jié)構(gòu)，也稱為多重索引結(jié)構(gòu)。4、多級索引存儲UNIX/Linux采用三級混合索引存儲結(jié)構(gòu)。每個文件的索引表為15個索引項，每項4個字節(jié)，登記一個存放文件信息的物理塊號。一、磁盤信息分區(qū)（2）最前面12項直接存放文件內(nèi)容的物理塊號，稱為直接地址索引項。如果文件大于12塊，則利用第13項指向一個物理塊，該塊中最多可放256個文件物理塊塊號，稱為一次間接地址索引項。對于更大的文件還可利用第14項和第15項作為二次、三次間接地址索引項。UNIX/Linux三級混合索引結(jié)構(gòu)示例一、磁盤信息分區(qū)（2）二、文件空間分配方法文件輔存空間管理記錄空閑物理塊的數(shù)量和位置文件輔存空間管理的一些方法1、位示圖（位向量或字位映象表）2、空閑塊鏈3、空閑區(qū)表4、成組空閑塊鏈系統(tǒng)中的每個磁盤物理塊采用一個二進(jìn)制位（0或1）表示該物理塊是否空閑。1、位示圖（位向量或字位映象表）分配和回收時只需修改二進(jìn)制位值即可。位示圖可以同時對空閑物理塊和已分配物理塊進(jìn)行綜合管理。2、空閑塊鏈空閑塊鏈方法將所有空閑塊鏈接在一起，形成一個鏈表。FAT方法將空閑塊的管理和已分配塊的管理結(jié)合到FAT表中，不需要獨立的空閑塊管理結(jié)構(gòu)。3、空閑區(qū)表一個空閑區(qū)由若干位置連續(xù)的空閑盤塊構(gòu)成?？臻e區(qū)表為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)占一個表項，表項內(nèi)容包括空閑塊位置和連續(xù)空閑的塊數(shù)?？臻e區(qū)也可以鏈表形式組織，形成空閑區(qū)鏈。空閑區(qū)鏈中的一個結(jié)點可以包含多個連續(xù)磁盤塊4、成組空閑塊鏈成組空閑塊鏈的原理思想成組空閑塊鏈將空閑塊分組鏈接，分組加載空閑塊號到內(nèi)存，無需加載整個空閑塊管理結(jié)構(gòu)即可實現(xiàn)文件所需空閑塊的分配與回收，減少內(nèi)存占用。訪問局部的空閑塊管理結(jié)構(gòu)，使用有限的內(nèi)存緩沖區(qū)，集約使用內(nèi)存資源。特點UNIX/Linux成組空閑塊鏈接UNIX/Linux將系統(tǒng)中的所有空閑盤塊分成若干組，每組100個盤塊，每組第一塊登記下一組空閑塊的盤物理塊號和空閑塊總數(shù)，形成成組空閑塊鏈。訪問成組空閑塊鏈進(jìn)行分配操作時，每次僅需裝入其中的一組到內(nèi)存，待該組中登記的盤塊分配完畢后，再從外存裝入下一組空閑盤塊列表到內(nèi)存?？臻e塊的分配成組空閑塊鏈的組成結(jié)構(gòu)回收空閑盤塊時，將空閑盤塊號登記在位于內(nèi)存的空閑盤塊列表中，僅當(dāng)該表滿（達(dá)到100）時，將其加入成組空閑塊鏈中并寫回外存，然后在內(nèi)存中建立一個新的盤塊組并加入成組空閑塊鏈中。空閑塊的回收成組空閑塊