文件管理文件系統負責管理外存上的文件，并為用戶提供對文件進行存取、共享及保護的手段。8.1文件系統的概念-8.1.1文件系統文件是具有文件名的一組相關記錄的集合。文件由若干記錄組成。記錄是一些相關數據項的集合。數據項是數據組織中可以命名的最小邏輯單位。文件系統filesystem文件系統：操作系統中與管理文件有關的軟件和數據的集合。它由管理文件所需的數據結構、相應的管理軟件和被管理的文件構成。文件系統的主要功能實現文件的按名存取為用戶提供接口實施對文件和目錄的管理文件存儲空間的分配及回收文件的共享及保護文件系統的層次結構文件系統的層次結構包含四層：基本I/O控制層基本文件系統層基本I/O管理程序層邏輯文件系統層不同操作系統中，文件系統的組成方法不一樣，但這種組成具有代表性。基本I/O控制層基本I/O控制層（Basic

I/Ocontrollevel）又稱設備驅動程序層，該層主要由驅動程序組成，負責啟動設備I/O操作及對設備發來的中斷信號進行處理。基本文件系統層基本文件系統層（Basicfilesystemlevel）又稱物理I/O層，該層負責處理內存和外存之間的數據塊交換。它關心數據塊在外存和在緩沖區中的位置，無須了解傳送數據塊的內容或文件結構。基本I/O管理程序層基本I/O管理程序層又稱文件組織模塊層（File-organizationmodule

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

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

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

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

01234567磁道第i扇區…間隙標識字段間隙數據字段間隙…邏輯扇區將一個磁盤上的扇區從0柱面開始，按柱面順序依次編號，所得到的編號成為邏輯扇區號。邏輯扇區號=柱面號*每柱面扇區數+

磁頭號*每磁頭扇區數+

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

3存儲設備磁盤磁帶物理結構順序結構鏈接結構索引結構順序結構存取方法順序、直接順序順序、直接順序3.磁盤調度算法磁盤是可以被多個進程共享的設備。當有多個進程都請求訪問磁盤時，應采用一種適當的調度算法，以使各進程對磁盤的平均訪問時間（主要是尋道時間）最短。下面介紹幾種磁盤調度（DiskScheduling）算法。先來先服務--FCFS先來先服務算法按進程請求訪問磁盤的先后次序進行調度。特點：簡單合理，但未對尋道進行優化。先來先服務算法例平均尋道長度為：55.314618410150112387016072902118193935845移動距離55下一磁道號從100號磁道開始，磁盤訪問請求為：55、58、39、18、90、160、150、38、184最短尋道時間優先--SSTF最短尋道時間優先（Shortest-Seek-Time-First）算法選擇與當前磁頭所在磁道距離最近的請求作為下一次服務的對象。特點：尋道性能比FCFS好，但不能保證平均尋道時間最短，還可能會使某些請求總也得不到服務。最短尋道時間優先算法例平均尋道長度為：27.6241841321501016020181381639355325810移動距離90下一磁道號從100號磁道開始，磁盤訪問請求為：55、58、39、18、90、160、150、38、184掃描算法--SCAN進程饑餓：進程的請求總也得不到服務。SCAN算法在磁頭當前移動方向上選擇與當前磁頭所在磁道距離最近的請求作為下一次服務的對象。因這種算法中磁頭移動規律頗似電梯的運行，故又稱為電梯調度算法。特點：具有較好的尋道性能，能避免進程饑餓，但不利于兩端磁道的請求。掃描算法例平均尋道長度為：27.82018163913835532589490241841016050移動距離150下一磁道號從100號磁道開始，向磁道號增加方向移動。磁盤訪問請求為：55、58、39、18、90、160、150、38、184循環掃描算法CSCANC（circular）SCAN算法是SCAN算法的改良，它規定磁頭單向移動。例如，自里向外移動，當磁頭移到最外磁道時立即又返回到最里磁道，如此循環進行掃描。特點：該算法消除了對兩端磁道請求的不公平。循環掃描算法例平均尋道長度為：35.832901655358139203816618241841016050移動距離150下一磁道號從100號磁道開始，向磁道號增加方向移動。磁盤訪問請求為：55、58、39、18、90、160、150、38、184N-Step-SCAN若多個進程反復請求對某一磁道的訪問，則磁臂可能停留在某處不動，這一現象稱為磁臂粘著。N-Step-SCAN算法：將磁盤請求隊列分成若干個長度為N的子隊列，磁盤調度按FCFS算法依次處理這些子隊列，而處理每個隊列時按SCAN算法進行，一個隊列處理完后，再處理其他隊列。FSCAN算法FSCAN算法是N-Step-SCAN算法的簡化，它只將磁盤請求隊列分成兩個子隊列。一個是當前所有請求磁盤I/O的進程形成的隊列，由磁盤調度按SCAN算法進行處理，另一個隊列則是在掃描期間新出現的磁盤請求。8.3文件存儲空間的分配及管理為了實現文件系統，必須解決文件存儲空間的分配和回收問題，還應對文件存儲空間進行有效的管理。8.3.1文件存儲空間的分配文件存儲空間的分配常采用兩種方式：靜態分配：在文件建立時一次分配所需的全部空間。動態分配：根據需要進行分配。在分配區域大小上，也可以采用不同方法。可以為文件分配一個連續區域，但文件存儲空間的分配通常以塊或簇（幾個連續物理塊稱為簇，一般是固定大小）為單位。常用外存分配方法常用的外存分配方式有：連續分配鏈接分配索引分配1.連續分配ContinuousAllocation連續分配：為文件分配連續的磁盤空間。在這種分配方法中，用戶必須在分配前說明待創建文件所需的存儲空間大小。然后系統查找空閑區管理表格，若有就給文件分配所需的存儲空間，否則文件不能建立。連續分配示意圖

0

1

2

3

4

5

6

7

8910111213141516171819202122232425262728293031323334文件A目錄文件名起始塊號長度A23B95C188文件B文件C3536373839連續分配的特點連續分配的特點是：順序訪問容易且速度快，目錄中文件存儲位置信息簡單；但容易產生碎片，需要定期對磁盤空間進行整理。2.鏈接分配LinkedAllocation鏈接分配有兩種實現方案：以扇區為單位的鏈接分配以區段（或簇）為單位的鏈接分配以扇區為單位的鏈接分配以扇區為單位的鏈接分配：按文件的要求分配若干個磁盤扇區，屬于同一文件的各扇區按文件記錄的邏輯次序用鏈接指針鏈接起來。當文件增長時就為文件分配新的空閑扇區，并將其鏈接到文件鏈上；同樣當文件縮短時將釋放的扇區歸還給系統。特點：消除了碎片，不需要壓縮。但查找慢，鏈接指針的存儲及維護有一些開銷。鏈接分配示意圖

0

1

2

3

4

5

6

7

8910111213141516171819202122232425262728293031323334文件B目錄文件名起始塊號長度………B15………3536373839以區段（或簇）為單位分配以區段（或簇）為單位分配：是連續分配和非連續分配的結合，現廣為使用。區段由若干個連續扇區組成，文件所屬各區段可以用鏈接指針、索引表等方法來管理。此策略的優點是對輔存的管理效率較高，并減少了文件訪問的查尋時間。文件分配表FileAllocationTable文件分配表FAT是以鏈接方式存儲文件的系統中記錄磁盤分配和跟蹤空白盤塊的數據結構。該表整個文件系統僅設一張，其結構如下所示。表的序號是物理塊號，從0開始直至N－1（N為盤塊總數）。每個表項中的內容為存放文件數據的下一個盤塊號。文件的首地址（第一個盤塊號）存放在目錄中。因此，從目錄中找到文件的首地址后，就能找到文件在磁盤上的所有存放地址。文件分配表示意圖FCB

0451…

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

鏈接分配方式雖解決了連續分配方式中存在的問題，但又出現了新的問題：不支持隨機存取鏈接指針要占用一定數量的磁盤空間在索引分配方法中，系統為每個文件分配一個索引塊，索引塊中存放索引表，索引表中的每個表項對應分配給文件的一個物理塊。索引分配示意圖

0

1

2

3

4

5

6

7

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

105106254┇012┇105106254┇356357┇985

356357

740

985

┇1125360兩級索引分配允許的文件最大長度在兩級索引分配方式下，如果每個盤塊的大小為1KB，每個盤塊號占4字節，則：一個索引塊中可以存放：1KB/4B=256個盤塊號兩級索引最多可以存放的盤塊數為：256×256=64K個盤塊號因此可以允許的最大文件長度為：64K×1KB=64MB混合索引分配方式混合索引分配方式是將多種索引分配方式相結合而形成的一種分配方式。這種方式已用于UNIX、Linux等系統中。在UNIXSystemⅤ中，共設有13個地址項，包括10個直接地址項、一個一次間接地址項、一個二次間接地址項和一個三次間接地址項。混合索引方式示意圖addr[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]

……

…

………一次間接塊三次間接塊二次間接塊索引節點數據塊

…

…

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