計算機操作系統（第3版）課件 第11章 文件系統實現

第11章文件系統實現

FileSystemImplementation本章目標CHAPTEROBJECTIVES描述本地文件系統及目錄實現Todescribethedetailsofimplementinglocalfilesystemsanddirectorystructure討論塊分配、空閑塊算法Todiscussblockallocationandfree-blockalgorithms11.1文件系統結構

File-SystemStructure

磁盤的兩個特點，使其成為存儲多個文件的方便媒介。Diskshavetwocharacteristicsthatmakethemaconvenientmediumforstoringmultiplefiles.可以原地重寫；canbewritteninplace可以直接訪問磁盤上的任意一塊信息。Canaccessdirectlyanygivenblockofinformationitcontains.分層文件系統

LayeredFileSystem文件系統按層組織Filesystemorganizedintolayers.I/O控制層基本文件系統層文件組織模塊層邏輯文件系統層不同操作系統中，文件系統的組成方法不一樣，但這種組成具有代表性。

分層文件系統示意圖I/O控制層由驅動程序和中斷處理程序組成，實現內存與磁盤之間的信息傳輸。基本I/O控制層又稱設備驅動程序層，該層主要由驅動程序組成，負責啟動設備I/O操作及對設備發來的中斷信號進行處理。基本文件系統層向合適的設備驅動程序發送一般命令就可對磁盤上的物理塊進行讀寫。基本文件系統層又稱物理I/O層，負責處理內存和外存之間的數據塊交換。它關心數據塊在外存和在緩沖區中的位置，無須了解傳送數據塊的內容或文件結構。文件組織模塊層將邏輯塊轉換為物理塊，空閑空間管理器。文件組織模塊層又稱基本I/O管理程序層，負責所有文件I/O的初始化和終止。該層完成的工作包括選擇文件所在的設備、進行文件邏輯塊號到物理塊號的轉換、優化磁盤調度的性能、對文件空閑存儲空間進行管理等。邏輯文件系統層管理元數據信息，管理目錄結構，通過文件控制塊來維護文件結構。邏輯文件系統層負責處理文件及記錄的相關操作。如允許用戶利用文件名訪問文件及其中的記錄、實現對文件及記錄的保護、實現目錄操作等。實例ExampleUnix:UNIXfilesystem(UFS)WindowsNT:FAT,FAT32,NTFSLinux:ext2、ext3、msdos、vfat、iso9660、hpfs等多種文件系統。11.2文件系統實現

FileSystemImplementation本節深入分析用于實現文件系統的結構和操作。Inthissection，wedelveintothestructuresandoperationsusedtoimplementfile-systemoperations.11.2.1概述Overview在磁盤上，文件系統可能包括如下信息：Ondisk，thefilesystemmaycontain：引導控制塊：包括從該卷引導操作系統所需的信息Bootcontrolblock：containinformationneededbythesystemtobootanOSfromthatvolume.卷控制塊：包含卷的詳細信息。如塊數、塊大小Volumecontrolblock：containvolumedetails，suchasBlocknumbers,blocksize每個文件系統的目錄結構directorystructure每個文件的文件控制塊Filecontrolblock用于文件系統管理的內存信息In-memoryinformationusedforfile-systemmanagement內存安裝表：包含所有安裝卷的信息In-memorymounttable：containinginformationabouteachmountedvolume.內存目錄結構：保存近來訪問過的目錄信息In-memorydirectorystructurescontainingthedirectoryinformationofrecentlyaccesseddirectories.用于文件系統管理的內存信息2系統打開文件表：包括每個打開文件的FCB拷貝和其他信息System-wideopen-filetablecontainingacopyoftheFCBofeachopenfileaswellasotherinformation.進程打開文件表：包括指向系統打開文件表中合適條目和其他信息的指針Per-processopenfile-tablescontainingapointertotheappropriateentryinthesystem-wideopen-filetable,aswellasotherinformation.一個典型的文件控制塊內存中的文件系統結構FileopenFileread11.2.2分區與掛載

partitionsandmounting分區與磁盤一個磁盤可以分為多個分區一個分區可以橫跨多個磁盤分區可以是生的或熟的生分區

沒有文件系統用于交換空間或數據庫熟分區有文件系統引導信息引導信息能保存在各個分區中，并且有自己的格式。它通常為一組有序塊，作為二進制文件讀入內存。引導信息除了包括如何啟動一個特定操作系統外，還可以有其他指令。根分區（rootpartition）包括操作系統內核或其他系統文件，在引導時裝入內存。其他分區根據操作系統不同可以在引導時自動裝入或在此之后手動裝入。掛載分區mountapartition使用文件系統前應掛載分區TomountapartitionbeforeusingitsFSHowtomountapartitionToreadinthesuperblockviaitsdevicedriverToverifyitsconsistencyTorepairitifnecessary(fsck)Toaddanentryinthein-memorymounttablestructure.11.2.3虛擬文件系統

VirtualFileSystems虛擬文件系統提供一個面向對象的文件系統實現方法VirtualFileSystems(VFS)provideanobject-orientedwayofimplementingfilesystems.VFS允許不同類型的文件系統使用相同的系統調用接口VFSallowsthesamesystemcallinterface(theAPI)tobeusedfordifferenttypesoffilesystems(API).API是針對VFS的接口，而非對任何特定類型的文件系統TheAPIistotheVFSinterface,ratherthananyspecifictypeoffilesystem.虛擬文件系統實現的三個層次頂層：文件系統接口Open,read,write,andcloseandfiledescriptors中間層：VFS通過定義清晰的VFS接口，將文件系統的通用操作與實現分開VFS基于稱為Vnode的文件表示結構，該結構包含一個數值標識符以表示網絡范圍內的唯一文件底層不同文件系統實現，如ext3、NFS虛擬文件系統示意圖11.3目錄實現

DirectoryImplementation目錄分配和管理算法的選擇對文件系統的效率、性能和可靠性有很大影響。Theselectionofdirectory-allocationanddirectory-managementalgorithmssignificantlyaffectstheefficiency，performance，andreliabilityofthefilesystem.11.3.1線性表Linearlist

最簡單的目錄實現方法是使用存儲文件名和數據塊指針的線性表。這種方法容易實現，但查找文件費時。許多操作系統采用軟件緩存來存儲最近訪問過的目錄信息。11.3.2哈希表HashTable

哈希表：使用線性表來存儲目錄項，使用哈希表來快速找出給定文件名的目錄項哈希表根據文件名得到一個值，并返回一個指向線性表中元素的指針。減少了目錄搜索時間，但要避免沖突。最大困難是其通常固定的大小和哈希函數對大小的依賴性。11.4分配方法分配方法指如何為文件分配磁盤塊常用的磁盤空間分配方法有以下三類：

連續分配Contiguousallocation 鏈接分配Linkedallocation 索引分配Indexedallocation 文件存儲空間的分配文件存儲空間的分配常采用兩種方式：靜態分配：在文件建立時一次分配所需的全部空間。動態分配：根據需要進行分配。在分配區域大小上，也可以采用不同方法。可以為文件分配一個連續區域，但文件存儲空間的分配通常以塊或簇（幾個連續物理塊稱為簇，一般是固定大小）為單位。11.4.1連續分配連續分配方法要求每個文件在磁盤上占有一組連續的塊。文件目錄只需其起始位置（塊號）及長度。支持順序及隨機訪問，但有外部碎片。磁盤空間的連續分配連續分配續在這種分配方法中，用戶必須在分配前說明待創建文件所需的存儲空間大小。然后系統查找空閑區管理表格，若有就給文件分配所需的存儲空間，否則文件不能建立。連續分配的特點是：順序訪問容易且速度快，目錄中文件存儲位置信息簡單；但容易產生碎片，需要定期對磁盤空間進行整理。存在的問題為新文件找空間比較困難文件很難增長基于擴展的系統許多新的文件系統采用一種修正的連續分配方法該方法開始分配一塊連續空間，當空間不夠時，另一塊被稱為擴展的連續空間會添加到原來的分配中。文件塊的位置就成為開始地址、塊數、加上一個指向下一擴展的指針。11.4.2鏈接分配鏈接分配有兩種實現方案：以扇區為單位的鏈接分配以區段（或簇）為單位的鏈接分配以扇區為單位的鏈接分配每個文件是磁盤塊的鏈表；磁盤塊分布在磁盤的任何地方。文件目錄包含第一塊的指針及最后一塊的指針。pointerblock=磁盤空間的鏈接分配特點優點：簡單－只需起始位置文件創建與增長容易缺點：不能隨機訪問塊與塊之間的鏈接指針需要占用空間存在可靠性問題，如指針損壞以區段（或簇）為單位分配以區段（或簇）為單位分配：是連續分配和非連續分配的結合，現廣為使用。區段由若干個連續扇區組成，文件所屬各區段可以用鏈接指針、索引表等方法來管理。此策略的優點是對輔存的管理效率較高，并減少了文件訪問的查尋時間。文件分配表文件分配表FAT是以鏈接方式存儲文件的系統中記錄磁盤分配和跟蹤空白盤塊的數據結構。該表整個文件系統僅設一張，其結構如下所示。表的序號是物理塊號，從0開始直至N－1（N為盤塊總數）。每個表項中的內容為存放文件數據的下一個盤塊號。文件的首地址（第一個盤塊號）存放在目錄中。因此，從目錄中找到文件的首地址后，就能找到文件在磁盤上的所有存放地址。文件分配表示意圖文件分配表例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=500KB11.4.3索引分配鏈接分配方式雖解決了連續分配方式中存在的問題，但又出現了新的問題：不支持隨機存取鏈接指針要占用一定數量的磁盤空間索引分配2IndexedAllocation在索引分配方法中，系統為每個文件分配一個索引塊，索引塊中存放索引表，索引表中的每個表項對應分配給文件的一個物理塊。文件目錄包含索引塊地址。indextable索引分配示意圖索引分配的特點索引分配方法支持直接訪問，不會產生外部碎片；但索引塊要占用一定的存儲空間，存取文件需要兩次訪問外存。二級索引和多級索引 當文件很大，其索引表的大小超過了一個物理塊時，可以將索引表本身作為一個文件，再為其建立一個“索引表”，該“索引表”是文件索引的索引，從而構成了二級索引。第一級索引表的表目指向第二級索引，第二級索引表的表目指向文件信息所在的物理塊號。以此類推可再逐級建立索引，進而構成多級索引。兩級索引分配示意圖第二級索引磁盤空間主索引┇┇┇┇┇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。11.5空閑空間管理為了實現文件存儲空間的分配，首先應記住空閑存儲空間的情況。常用的空閑存儲空間管理方法有：空閑文件目錄空閑塊鏈位示圖11.5.1位向量/位示圖在位示圖中，每個物理塊用一個二進制位表示，當某位為1時表示該塊已分配，當某位為0時表示該塊空閑。110011011101111100001111100000011111110111100000…0123456789101112131415

01234┆盤塊的分配在位示圖方法中，盤塊分配分為三步：系統順序掃描位示圖，從中找出一個（組）值為0的二進制位。再經過換算得到相應的盤塊地址：盤塊號=行號*每行二進制位數+列號修改位示圖，將相應位置1。盤塊的回收盤塊回收分兩步：將回收的盤塊號轉換成圖中的行號、列號。行號=盤塊號/每行二進制位數列號=盤塊號%每行二進制位數修改位示圖，將相應位清0。：特點：因位示圖比較小，可以保存在主存中，因此空間的分配與回收較快；但需要進行位示圖中二進制所在位置與盤塊號之間的轉換。11.5.2空閑塊鏈空閑塊鏈方法將文件存儲設備上的所有空閑塊鏈接起來，并設置一個頭指針指向空閑塊鏈的第一個物理塊。當申請分配存儲空間時，就按需要從鏈首依次取下幾個物理塊分配給文件。當回收存儲空間時，將回收的空閑塊依次鏈入空閑塊鏈中。LinkedFreeSpaceListonDisk空閑塊鏈的特點及改進特點：實現簡單但工作效率低，因為在空閑塊鏈上增加或移去空閑塊時要進行鏈表操作。一種改進方法是將空閑塊分成若干組，再用指針將組與組鏈接起來，將這種管理空閑塊的方法稱為成組鏈接法。成組鏈接法在進行空閑塊的分配與回收時要比空閑塊鏈方法節省時間。成組鏈接法UNIX系統采用成組鏈接法對空閑盤塊加以組織。空閑盤塊的組織：將若干個空閑盤塊劃歸一組，將每組中的所有盤塊號存放在其前一組的第一個空閑盤塊號指示的盤塊中，而將第一組中的所有空閑盤塊號放入超級塊的空閑盤塊號表中。成組鏈接法示意圖10910610310095超級塊空閑盤塊號表211208205…112109310307304…214211409406403…313310空閑盤塊的分配當要分配一個盤塊時，首先將超級塊空閑盤塊號表中下一個可用盤塊分配出去；如果所分配盤塊號是超級塊中最后一個可用盤塊號，則先將該盤塊中的內容讀入超級塊空閑盤塊號表中，然后才將該盤塊分配出去。分配超級塊中最后一個盤塊號例分配前分配后109超級塊空閑盤塊號表211208205…112109310307304…214211409406403…313310超級塊空閑盤塊號表211208205…112310307304…214211409406403…313310空閑盤塊的回收在回收空閑盤塊時，如果超級塊中的空閑盤塊號表未滿，可直接將回收盤塊的編號放入空閑盤塊號表中；若空閑盤塊號表已滿，需先將空閑盤塊號表中的所有盤塊號復制到新回收的盤塊中，再將新回收盤塊的編號放到超級塊空閑盤塊號表中，此塊號就成了表中惟一的盤塊號。超級塊已滿時回收盤塊例回收前（回收100號盤塊）回收后超級塊空閑盤塊號表211208205…112310307304…214211409406403…313310100超級塊空閑盤塊號表211208205…112100310307304…214211409406403…313310空閑文件目錄文件存儲設備上的一個連續空閑區可以看作一個空閑文件，又稱空白文件或自由文件。空閑文件目錄方法為所有空閑文件建立一個目錄，每個空閑文件在該目錄中占一個表目，其中至少包括：空閑區序號、第一個空閑塊塊號、空閑塊數目等信息。空閑文件目錄示例下面給出了一個空閑目錄的例子。序號第一個空閑塊號空閑塊個數物理塊號153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4------空閑文件目錄法的空閑空間管理當請求分配存儲空間時，系統依次掃描空閑文件目錄，直到找到一個能滿足要求的空閑文件為止。若該文件大小大于申請空間量則還要進行劃分。當回收存儲空間時，也需要順序掃描空閑文件目錄，尋找一個空表目，并將釋放空間的第一個物理塊號以及釋放空間的塊數填到這個表目中。若釋放空間與已有空閑文件鄰接，則需進行合并。空閑文件目錄法的特點顯然，只要將動態分區管理方法中的算法稍作修改，即可用于空閑文件目錄方法。特點：僅當文件存儲空間中只有少量空閑文件時該方法有比較好的效果，否則空閑目錄變大導致其效率下降。該方法僅適用于連續文件。11.6效率與性能效率依賴于：磁盤分配和目錄算法文件目錄中的數據類型性能磁盤緩沖提前讀虛擬盤11.7恢復由于文件及目錄可保存在內存和磁盤上，所以必須確保系統失敗不會引起數據丟失及不一致。11.7.1一致性檢查系統崩潰時有可能導致信息的丟失。一致性檢查：比較目錄結構中的數據和磁盤塊中的數據，嘗試著去修正不一致。

11.7.2備份和恢復文件系統備份（轉儲）的方法有兩種：全量轉儲增量轉儲全量轉儲fullbackup全量轉儲：定期將文件存儲器中的所有文件備份轉儲到某存儲介質上，一旦系統出現故障破壞了文件信息，便可以將最近一次轉儲的內容復制到文件系統中去，使系統恢復到上次轉儲時的狀態。全量轉儲的不足：轉儲期間應停止對文件系統進行其他操作，轉儲時間長。增量轉儲增量轉儲：將上次轉儲以來修改過的文件和新增加的文件轉儲到某存儲介質上。增量轉儲能使系統遭到破壞后，恢復到數小時前文件系統的狀態，從而使得所造成的損失減到最小。在實際工作中，兩種方法要配合使用，根據實際情況，確定全量轉儲的周期和增量轉儲的時間間隔。文件系統的恢復過程一旦系統發生故障，文件系統的恢復過程大致如下：從最近一次全量轉儲中裝入全部系統文件從近到遠從增量轉儲盤上恢復文件。同一個文件只恢復最近一次轉儲的副本。習題及補充習題14.1Considerafilecurrentlyconsistingof100blocks.Assumethatthefile-controlblock(andtheindexblock,inthecaseofindexedallocation)isalreadyinmemory.CalculatehowmanydiskI/Ooperationsarerequiredforcontiguous,linked,andindexed(single-level)allocationstrategies,if,foroneblock,thefollowingconditionshold.Inthecontiguous-allocationcase,assumethatthereisnoroomtogrowatthebeginningbutthereisroomtogrowattheend.Alsoassumethattheblockinformationtobeaddedisstoredinmemory.a.Theblockisaddedatthebeginning.b.Theblockisaddedinthemiddle.c.Theblockisaddedattheend.d.Theblockisremovedfromthebeginning.e.Theblockisremovedfromthemiddle.f.Theblockisremovedfromtheend.習題及補充習題假定磁盤塊大小為1KB，若硬盤容量為1.2GB，FAT需占用多少空間？假設盤塊大小為2KB，每個盤塊號占4字節，在兩級索引分配時，允許的最大文件是多少？UNIX文件系統UNIX文件系統的特點：采用樹型目錄結構，且文件系統可以拆卸。采用混合索引式的文件物理結構，既能提高查詢速度又可節省存放文件地址所需的空間采用成組鏈接法管理空閑磁盤空間。既提高查找速度又節省空間。引入了索引節點的概念。文件的物理結構在UNIX系統中，文件的物理結構采用混合索引結構，文件所占用的盤塊號直接或間接地存放在該文件索引節點的13個地址項中。在查找文件時，只需找到該文件的索引節點，便可以用直接或間接的尋址方式獲得指定文件的盤塊號。尋址方式直接尋址方式：在索引節點中建立了10個地址項，每個地址項中直接存放了相應文件所在盤塊的盤塊號。假定一個盤塊的大小為1KB，一個盤塊號占4字節。一次間接尋址方式：先將1～256個盤塊號存放在一個磁盤塊中，再將該磁盤塊的塊號存放在這一地址項中。用一次間接地址項可將尋址范圍由10KB擴大到266KB。尋址方式(續)多次間接尋址方式：為了進一步擴大尋址范圍，又引入了二次間接和三次間接尋址方式。二次間接尋址可將尋址范圍擴大到64MB。三次間接尋址可將尋址范圍擴大到16GB。直接尋址和間接尋址示意圖

直接尋址一次間址二次間址三次間址

……

…

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

…

…

…地址轉換（1）地址轉換過程分兩步實現：將字節偏移量轉換為文件邏輯塊號及塊內偏移量；把邏輯塊號轉換為文件的物理塊號。地址轉換（2）將字節偏移量轉化為文件邏輯塊號：用字節偏移量除以盤塊大小（以字節為單位），其商是文件邏輯塊號，余數是塊內位移量。把文件邏輯塊號轉換為物理盤塊號：根據邏輯盤塊號可知對應的文件地址是直接地址還是間接地址，不同的地址應采用不同的轉換方法。地址轉換（3）直接地址：當邏輯盤塊號＜10時，將文件邏輯塊號轉換為索引節點的地址項下標；從該地址項中即可獲得物理盤塊號。一次間接尋址：當10≤邏輯盤塊號＜266時，從索引節點的一次間接項中得到一次間接的盤塊號；再讀入間接塊的內容；計算一次間接塊中的地址下標（即邏輯塊號－10）；從相應下標的地址項中得到物理塊號。多次間接尋址：當266≤邏輯塊號＜65802時，應采用二次間接尋址；當65802≤邏輯塊號時，應采用三次間接尋址。多次間接尋址的轉換方法和一次間接尋址相類似，但要多次循環。索引節點的管理在UNIX系統中，文件信息存放在磁盤或磁帶上，一個物理存儲器中可包含一個或多個文件系統。超級塊超級塊用于存放文件系統的資源管理信息：文件系統的盤塊數空閑盤塊號表及空閑盤塊號數磁盤索引節點占用的盤塊數空閑索引節點表和空閑索引節點數空閑盤塊號表及空閑索引節點表的鎖字段超級塊修改標志及修改時間

磁盤索引節點的分配過程ialloc當創建一個新文件時，要為之分配一個空閑磁盤索引節點。其分配過程如下：檢查超級塊是否上鎖。若鎖住則睡眠等待。檢查超級塊中的空閑索引節點表是否為空。若為空則應從磁盤上搜索一批空閑索引節點。從空閑索引節點表中分配一個索引節點，并對它進行初始化，填寫有關文件的屬性。分配內存索引節點。將空閑磁盤索引節點計數減1，并設置超級塊修改標志后返回。磁盤索引節點的回收過程ifree當要刪除某文件時，應回收其所占用的盤塊及相應的磁盤索引節點。其回收過程如下：檢查超級塊是否上鎖。若已上鎖便直接返回，即不把本次回收的索引節點號記入空閑索引節點表中。檢查空閑索引節點表是否已滿。若索引節點表已滿，則比較回收索引節點號與銘記索引節點號的大小，將較小者存入銘記索引節點中。若空閑索引節點表未滿，便將回收的索引節點號存入其中。將空閑磁盤索引節點計數加1，設置超級塊修改標志后返回。內存索引節點的分配過程iget該過程的主要功能是分配內存索引節點，其輸入參數是文件系統號和索引節點號。若該i節點（i節點即索引節點）已在索引節點的散列隊列中，則只需對該i節點的引用計數加1。如果該i節點不在散列隊列中，則應從空閑i節點鏈中摘下一個空閑i節點，設置文件系統號和索引節點號，并根據i節點號計算它應在的散列隊列，再將該i節點從原來的散列隊列移至新的散列隊列。調用bread過程將磁盤i節點的內容拷貝到內存i節點中，并對內存i節點進行初始化。內存索引節點的回收過程iput該過程的輸入參數是指向內存i節點的指針。其主要功能是對指定的內存索引節點引用計數進行減1操作。若結果為0，則回收該內存i節點。若它已做過修改，還需將它寫回磁盤后再回收，然后將它鏈入內存空閑i節點表中。若其磁盤i節點的鏈接計數也為0，便刪除該文件，并回收分配給該文件的磁盤i節點和磁盤數據塊。空閑磁盤空間的管理在UNIX中，一個文件系統包含許多物理塊，并按照塊號排列成如下圖所示的結構。0#1#2#...K#...N#引導塊超級塊索引節點表數據塊空閑盤塊的組織UNIX系統采用成組鏈接法對空閑盤塊加以組織。即將若干個空閑盤塊劃為一個組，將每組中的所有盤塊號存放在其前一組的第一個空閑盤塊號指示的盤塊中，而將第一組中的所有空閑盤塊號放入超級塊的空閑盤塊號表中。

空閑盤塊的組織圖10910610310095超級塊空閑盤塊號表211208205…112109310307304…214211409406403…313310空閑盤塊的分配當要分配一個盤塊時，首先檢查超級塊空閑盤塊號表是否已上鎖，若已上鎖則進程睡眠等待；否則將超級塊空閑盤塊號表中下一個可用盤塊號分配出去。如果所分配的盤塊號是超級塊中的最后一個可用盤塊號，則應先將該盤塊中的內容讀入超級塊空閑盤塊號表中；然后才將該盤塊分配出去；最后將空閑盤塊號表解鎖，并喚醒所有等待其解鎖的進程。空閑盤塊的回收在回收空閑盤塊時，如果超級塊中的空閑盤塊號表未滿，可直接將回收盤塊的編號放入空閑盤塊號表中。若空閑盤塊號表已滿，則應先將空閑盤塊號表中的所有盤塊號復制到新回收的盤塊中，再將新回收盤塊的編號放到超級塊空閑盤塊號表中，此塊號就成了表中惟一的盤塊號。用戶文件描述符表系統為每個進程設置了一張用戶文件描述符表，以記錄進程使用文件的情況。當用戶第一次打開指定文件時，系統便在該進程的用戶文件描述符表中分配一個空表項，填入有關信息，再取該表項在用戶文件描述符表中的位移量作為文件描述符返回給用戶。以后，當用戶再訪問該文件時，只需提供該文件的描述符，系統根據描述符便可找到相應文件的內存索引節點。文件表文件表整個系統一張，其中存放文件的讀/寫指針。可以允許用戶采用下述三種方式使用文件：多個用戶通過不同的文件表項讀/寫各自的文件；多個用戶共享一個文件，但彼此獨立地對文件進行讀/寫；多個用戶共享一個文件，且共享一個讀/寫指針。文件的三種讀寫方式文件表內存索引節點………………A用戶B用戶C用戶D用戶E用戶F用戶用戶文件描述符表第一種情況第二種情況第三種情況……………目錄管理文件系統的基本功能是實現按名存取，這是通過文件目錄來實現的。UNIX系統中的每個目錄項由文件名及其相應的索引節點號組成，其中文件名占14個字節，索引節點號占2個字節。通常，每個文件都在文件目錄中