第6章 文件管理

第六章文件管理目標：掌握文件系統(tǒng)的基本概念和實現(xiàn)過程順序文件、索引文件和索引順序文件順序文件：什么是順序文件？如何對定長記錄的順序文件進行讀/寫操作？這種文件形式有何優(yōu)缺點，它主要用于何種場合？索引文件：什么是索引文件？為什么要引入索引文件？索引文件采用何種文件組織形式？索引文件的優(yōu)缺點是什么？索引順序文件：什么是索引順序文件？索引順序文件是為了解決什么樣的問題而引入的，如何對索引順序文件進行檢索？當文件非常大時又應如何處理？本章要點（1/9）連續(xù)分配、鏈接分配和索引分配連續(xù)分配：連續(xù)分配是何種為文件分配存儲塊的方式？如何對連續(xù)分配的文件進行順序訪問或隨機訪問？這種分配方式有何優(yōu)缺點？鏈接分配：鏈接分配是何種為文件分配存儲塊的方式？隱式鏈接分配方式是為了解決什么問題而引入的，它有何不足之處？顯式鏈表結(jié)構(gòu)是如何解決上述不足的，它較適合用哪種場合？這兩種分配方式是如何將多個離散的盤塊鏈成一個鏈表的。索引分配：索引分配是何種為文件分配存儲塊的方式？為什么要引入索引分配方式，采用索引分配方式時應如何對文件進行訪問？當文件很大時又應如何處理？混合索引分配方式是為了解決什么問題而引入的？此時，應如何將文件的邏輯地址轉(zhuǎn)換成物理地址？本章要點（2/9）位示圖法和成組鏈接法位示圖法：位示圖法的概念。使用位示圖如何來進行磁盤塊的分配或回收，這種管理方式有何優(yōu)點？成組鏈接法：成組鏈接法的概念。它是如何將盤塊進行分組并將各個盤塊組鏈成一個成組鏈的？它應如何進行盤塊的分配和回收，這種管理方式有什么優(yōu)點？本章要點（3/9）目錄管理文件控制塊（FCB）：什么是FCB，什么是文件目錄？FCB通常應包含哪些內(nèi)容，它與文件之間存在著什么樣的關(guān)系？索引結(jié)點：磁盤索引結(jié)點是為了解決什么問題而引入的，它與FCB、目錄項之間存在著什么樣的關(guān)系？為什么要引入內(nèi)存索引結(jié)點，以及在內(nèi)存索引結(jié)點中還應增加哪些數(shù)據(jù)項，原因是什么？單級目錄和兩級目錄結(jié)構(gòu)：在單級目錄結(jié)構(gòu)中應如何創(chuàng)建或刪除文件，它在哪些地方無法滿足對目錄管理的要求，而兩級文件目錄是如何解決這些問題的？本章要點（4/9）目錄管理多級目錄結(jié)構(gòu)：目錄結(jié)構(gòu)由單級發(fā)展為兩級、并進一步發(fā)展為多級帶來了哪些好處？應如何根據(jù)絕對路徑名或相對路徑名在多級目錄結(jié)構(gòu)中線性地檢索一個文件或子目錄，要創(chuàng)建或刪除一個文件或子目錄時應如何進行處理？本章要點（5/9）文件共享方式文件共享的主要目的是什么？基于索引結(jié)點的共享方式：是何種文件共享方式？如果不引入索引結(jié)點，而直接通過FCB來共享文件會產(chǎn)生什么問題？這種共享方式應如何進行文件的刪除操作，它有何優(yōu)缺點？利用符號鏈實現(xiàn)文件共享：是何種文件共享方式？當用戶訪問LINK類型的文件時，系統(tǒng)應如何進行處理，通過這種方式共享文件有何優(yōu)缺點？本章要點（6/9）磁盤容錯技術(shù)SFT-I：引入SFT-I的目的是什么？雙份目錄和雙份文件分配表措施主要是用來解決什么問題？熱修復重定向和寫后讀校驗措施又是用來解決什么問題，它們分別是如何解決上述問題？SFT-II：引入SFT-II的目的是什么？磁盤鏡像可用來解決什么問題？它對磁盤I/O的速度有什么影響？而磁盤雙工是為了解決什么問題而引入的，它對磁盤I/O的速度又有哪些影響？本章要點（7/9）文件系統(tǒng)的數(shù)據(jù)一致性事務：事務的概念。事務是如何保證數(shù)據(jù)的一致性的？事務操作和原語操作之間存在著什么區(qū)別？在事物操作中引入檢查點主要是為了解決什么問題？為什么多個事務的執(zhí)行具有順序性？如何實現(xiàn)事務的順序性？盤塊號的一致性檢查：盤塊一致性檢查的目的是什么？盤塊號一致性檢查軟件應如何設(shè)置每個盤塊的空閑盤塊號計數(shù)器和數(shù)據(jù)盤塊號計數(shù)器的值，為什么這兩個計數(shù)器的值必須互補？在檢查過程中可能出現(xiàn)哪些異常現(xiàn)象，分別應如何解決？本章要點（8/9）文件系統(tǒng)的數(shù)據(jù)一致性鏈接計數(shù)的一致性檢查：為什么要引入鏈接計數(shù)的一致性檢查？一致性檢查軟件是通過什么和文件索引結(jié)點中的鏈接計數(shù)字段的比較來進行一致性檢查的？在檢查過程中可能會出現(xiàn)哪些異?，F(xiàn)象，分別應如何解決？本章要點（9/9）6.1文件和文件系統(tǒng)6.2文件的邏輯結(jié)構(gòu)6.3外存分配方式6.4目錄管理6.5文件存儲空間的管理

6.6文件共享與文件保護6.7數(shù)據(jù)一致性控制本章內(nèi)容概述所有的計算機應用程序都要：存儲信息，檢索信息三個基本要求：能夠存儲大量的信息長期保存信息可以共享信息解決方法：把信息以一種單元—即文件的形式存儲在磁盤或其他介質(zhì)上文件是通過操作系統(tǒng)來管理的包括：文件的結(jié)構(gòu)，命名，存取，使用，保護和實現(xiàn)方法用戶觀點：

文件系統(tǒng)如何呈現(xiàn)在其面前：一個文件由什么組成，如何命名，如何保護文件，可以進行何種操作等等。操作系統(tǒng)觀點：

文件目錄怎樣實現(xiàn)，怎樣管理存儲空間，文件存儲位置，磁盤實際運作方式(與設(shè)備管理的接口)等等。概述6.1文件和文件系統(tǒng)6.1文件和文件系統(tǒng)

文件管理的目的方便文件訪問和控制：以符號名稱作為文件標識；并發(fā)文件訪問和控制：在多道程系統(tǒng)中支持對文件的并發(fā)訪問和控制；統(tǒng)一的用戶接口：在不同設(shè)備上提供同樣的接口，方便用戶操作和編程；多種文件訪問權(quán)限：在多用戶系統(tǒng)中的不同用戶對同一文件會有不同的訪問權(quán)限；優(yōu)化性能：存儲效率、檢索性能、讀寫性能；差錯恢復：能夠驗證文件的正確性，并具有一定的差錯恢復能力。6.1.1文件、記錄和數(shù)據(jù)項

1、數(shù)據(jù)項基本數(shù)據(jù)項：是用于描述一個對象的某種屬性的字符集數(shù)據(jù)名數(shù)據(jù)類型組合數(shù)據(jù)項：由若干個基本數(shù)據(jù)項組成2、記錄一組相關(guān)數(shù)據(jù)項的集合關(guān)鍵字：能唯一地標識出記錄的基本/組合數(shù)據(jù)項3、文件文件系統(tǒng)：對文件進行操縱和管理的軟件集合。文件：一個具有文件名的一組相關(guān)信息的集合。文件組成：文件體：文件本身的信息有結(jié)構(gòu)文件（由若干相關(guān)記錄組成）無結(jié)構(gòu)文件（字符流）文件屬性：文件存儲和管理信息文件類型文件長度文件的物理位置文件的存取控制文件的建立時間圖6-1文件、記錄和數(shù)據(jù)項之間的層次關(guān)系典型文件擴展名表6.1.2文件類型和文件系統(tǒng)模型

按用途分類系統(tǒng)文件：指與操作系統(tǒng)本身有關(guān)的一些信息所組成的文件。庫文件：指由系統(tǒng)提供給用戶調(diào)用的各種標準過程，函數(shù)和應用程序。用戶文件：由用戶的信息所組成的文件。按存取控制屬性分類只讀文件：僅允許對其進行讀操作的文件。讀寫文件：有控制地允許不同用戶對其進行讀或?qū)懖僮鞯奈募Ｖ粓?zhí)行文件：只允許被核準的用戶調(diào)用執(zhí)行。1、文件系統(tǒng)按文件中的數(shù)據(jù)形式分類源文件：是指從終端或輸入設(shè)備輸入的源程序和數(shù)據(jù)，以及作為處理結(jié)果的輸出數(shù)據(jù)的文件。目標文件（相對地址形式文件）：是指由各種語言編譯程序所輸出的相對地址形成的程序文件。可執(zhí)行文件：是指由鏈接裝配程序鏈接后所生成的可執(zhí)行目標程序文件（用在非動態(tài)連接系統(tǒng)中）。按文件的邏輯結(jié)構(gòu)分類有結(jié)構(gòu)文件：由若干個記錄構(gòu)成的文件（記錄文件）。無結(jié)構(gòu)文件：直接由字符序列構(gòu)成的文件（流式文件）1、文件系統(tǒng)按文件的物理結(jié)構(gòu)分類順序文件鏈接文件索引文件按信息保存期限分類：臨時文件永久文件檔案文件按信息流向分類：輸入文件輸出文件輸入/輸出文件1、文件系統(tǒng)2、文件系統(tǒng)模型文件系統(tǒng)接口對對象操縱和管理的軟件集合邏輯文件系統(tǒng)基本I/O管理程序（文件組織模塊）基本文件系統(tǒng)（物理I/O層）I/O控制層（設(shè)備驅(qū)動程序）對象及其屬性說明對象及其屬性說明文件目錄磁盤（磁帶）存儲空間對對象操縱和管理的軟件集合邏輯文件系統(tǒng)：write(recordof文件，buf)→write(邏輯號，buf)基本I/O管理：write(邏輯號，buf)基本文件系統(tǒng)：向driver發(fā)令，(buf

具體物理盤塊號)I/O控制層：driver文件系統(tǒng)的接口命令接口：作為用戶與文件系統(tǒng)之間交互的接口。程序接口：作為用戶程序與文件系統(tǒng)的接口。2、文件系統(tǒng)模型

文件系統(tǒng)向上層用戶提供的服務文件訪問：文件的創(chuàng)建、打開和關(guān)閉，文件的讀寫；目錄管理：用于文件訪問和控制的信息，不包括文件內(nèi)容文件結(jié)構(gòu)管理：劃分記錄，順序，索引訪問控制：并發(fā)訪問和用戶權(quán)限限額(quota)：限制每個用戶能夠建立的文件數(shù)目、占用外存空間大小等審計(auditing)：記錄對指定文件的使用信息（如訪問時間和用戶等），保存在日志中2、文件系統(tǒng)模型

文件系統(tǒng)要實現(xiàn)的功能模塊文件的分塊存儲：與外存的存儲塊相配合I/O緩沖和調(diào)度：性能優(yōu)化文件定位：在外存上查找文件的各個存儲塊外存存儲空間管理：如分配和釋放。主要針對可改寫的外存如磁盤。外存設(shè)備訪問和控制：包括由設(shè)備驅(qū)動程序支持的各種基本文件系統(tǒng)如硬盤，軟盤，CDROM等2、文件系統(tǒng)模型6.1.3文件操作

文件操作的典型功能，對整體文件而言：打開（open)文件：以準備對該文件進行訪問；關(guān)閉（close)文件：結(jié)束對該文件的使用；建立(create)文件：構(gòu)造一個新文件；撤消（destory)文件：刪去一個文件；復制（copy)文件；對文件改變其文件名（rename);打印或顯示文件內(nèi)容（list)。1、最基本的文件操作文件操作的典型功能，對文件中的數(shù)據(jù)項而言：讀（read)操作：把文件中一個數(shù)據(jù)項輸入給進程；寫（write)操作：進程輸出一個數(shù)據(jù)項到文件中去；修改(update)操作：修改一個已經(jīng)存在的數(shù)據(jù)項；插入(Insert)操作：添加一個新數(shù)據(jù)項；刪除(delete)操作：從文件中移走一個數(shù)據(jù)項。2、文件的“打開”和“關(guān)閉”操作“打開”，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號(或稱為索引)返回給用戶。“關(guān)閉”，是指把該文件從打開文件表中的表目上刪除掉。有關(guān)對文件屬性進行操作的系統(tǒng)調(diào)用：允許用戶直接設(shè)置和獲得文件的屬性。有關(guān)目錄的系統(tǒng)調(diào)用實現(xiàn)文件共享的系統(tǒng)調(diào)用用于對文件系統(tǒng)進行操作的系統(tǒng)調(diào)用3、其它文件操作6.2文件的邏輯結(jié)構(gòu)6.2文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是從用戶的觀點出發(fā)，所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨立于物理特性，又稱文件組織。文件的物理結(jié)構(gòu)又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式，與存儲介質(zhì)的存儲性能有關(guān)。文件邏輯結(jié)構(gòu)的要求訪問性能：便于檢索；便于修改存儲性能：向物理存儲轉(zhuǎn)換方便，節(jié)省空間6.2.1文件邏輯結(jié)構(gòu)的類型

1、有結(jié)構(gòu)文件（記錄式文件）a類：定長記錄變長記錄b類：順序文件：通常是定長記錄，（為何，因變長采用此方式查詢速度慢）索引文件：建立一張索引表，為每個記錄設(shè)置一個表項索引順序文件：順序組織多個組，每組記錄中的第一個記錄設(shè)置一索引項。2、無結(jié)構(gòu)文件（流式文件）以字節(jié)為單位，利用讀/寫指針進行訪問。6.2.2順序文件順序文件類型累積文件(pile)：文件體為無結(jié)構(gòu)記錄序列，通過特定分隔符來劃分記錄，各記錄大小和組成可變。新記錄總是添加到文件末尾。如日志log，或電子郵件的郵箱文件(mailbox)。檢索必須從頭開始。記錄型順序文件：文件體為大小相同的排序記錄序列。它由一個主文件和一個臨時文件組成。記錄大小相同，按某個關(guān)鍵字域(keyfield)排序，存放在主文件(masterfile)中。新記錄暫時保存在日志或事務文件(logfileortransactionfile)中，定期歸并入主文件。1、邏輯記錄的排序按記錄錄入的時間排:串結(jié)構(gòu)。按關(guān)鍵字排序：順序結(jié)構(gòu)。后一種情況更有利于提高查詢速度。如可用折半查找法等。2、對順序文件的讀/寫操作定長記錄順序文件：例：順序讀易于定位，甚至可隨機讀取。變長記錄：不易定位，只能順序讀取。2、對順序文件(SequentialFile)的讀/寫操作圖6-3定長和變長記錄文件3、順序文件的優(yōu)缺點

優(yōu)點：批量存取時效率高，管理簡單、順序存取速度快；缺點：當文件很大時，查找和修改效率低；增加和修改記錄困難、要求連續(xù)存儲空間、必須事先知道文件的長度。6.2.3索引文件

索引文件由變長記錄組成的順序文件不容易直接存取，因此，為其建立一有序的索引表，對索引采用折半查找，速度更快。特點：提高了速度，增加了存儲開銷——放索引文件。增、刪記錄時，對索引表作相應的修改。索引表用于記錄變長文件中每個記錄的長度及指向該記錄的指針（該記錄在邏輯地址空間的首址）。索引表本身是一個定長記錄的順序文件。圖6-4索引文件的組織優(yōu)點：可直接存取，有較快的檢索速度；文件的增刪方便。缺點：除主文件外，還需配置一張索引表，而且每一記錄都要有一索引項，增加了存儲費用。增加新記錄時，也需要修改索引表。6.2.4索引順序文件

索引順序文件將順序文件中若干記錄分為一組；為順序文件建立一張索引表，表中記錄每個組的第一個記錄，該索引項包含記錄的鍵值和指向該記錄的指針；為該組的其它記錄設(shè)置了溢出區(qū)域，在溢出區(qū)域內(nèi)記錄按順序文件方式組織。是順序文件和索引文件的結(jié)合。索引順序文件既適用于交互方式應用，也適用于批處理方式應用。檢索方法：先根據(jù)關(guān)鍵字去檢索索引表，找到該記錄所在組的第一個記錄的位置，然后再利用順序查找法去查找主文件，找到所需記錄。圖6-5索引順序文件6.2.5直接文件和哈希文件

鍵值轉(zhuǎn)換：由記錄鍵值到記錄物理地址的轉(zhuǎn)換A=H(k）1、直接文件

2、哈希(Hash)文件圖6-6Hash文件的邏輯結(jié)構(gòu)6.3外存分配方式6.3.1連續(xù)分配

連續(xù)分配（磁帶，磁盤都可采用）（順序文件）每個文件分配一組相鄰盤塊。特點：簡單順序訪問容易且速度快，因磁頭移動距離小，要求連續(xù)空間，一段時間后需整理磁盤以消除外部碎片。必須事先知道長度，文件不易動態(tài)增長和刪除。文件對應目錄項（屬性）中包含：始址、總塊數(shù)、最后一塊字節(jié)數(shù)。1、連續(xù)分配方式

圖6-7磁盤空間的連續(xù)分配1、連續(xù)分配

圖6-7磁盤空間的連續(xù)分配（緊湊之后）1、連續(xù)分配

優(yōu)點：

順序訪問容易。順序訪問速度快。缺點：

要求有連續(xù)的存儲空間。必須事先知道文件的長度。2、連續(xù)分配的主要優(yōu)缺點

6.3.2鏈接分配鏈接分配一個文件可以放在不連續(xù)的物理塊中，每個物理塊通過指針鏈接起來。優(yōu)點：消除了外部碎片，顯著提高外存利用率；無須事先知道文件長度，根據(jù)文件當前需要分配必須的盤塊；動態(tài)增長時可再分配盤塊；方便對文件進行修改。缺點：不能支持高效地直接存取鏈接分配又可分為以下兩種：隱式鏈接文件目錄的每個目錄項中，都含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。特點：只適合順序訪問，對隨機訪問效率極低；只通過鏈接指針來將一大批離散的盤塊鏈接起來，可靠性較差。顯式鏈接把用于鏈接的指針顯式存放在內(nèi)存的一張表中，查找在內(nèi)存中進行。利用文件分配表FAT，記錄文件的盤塊號。1、隱式鏈接

圖6-8磁盤空間的鏈接式分配2、顯式鏈接圖6-9顯式鏈接結(jié)構(gòu)圖6-10MS-DOS的文件物理結(jié)構(gòu)文件名磁盤目錄表FDT磁盤參數(shù)表文件位置分配表FAT磁盤扇區(qū)定位扇區(qū)物理操作磁盤基數(shù)表DOS磁盤訪問操作流程6.3.3索引分配

鏈接分配問題：不能高效直接存?。籉AT需占較大的內(nèi)存。概念：為每個文件分配一個索引塊特點：文件較大時有利。文件較小時浪費外存空間（還需為小文件建索引塊）當文件較大時，索引塊太多，查找速度減慢解決：當索引太大時，則需建立多級索引1、單級索引分配圖6-11索引分配方式多級索引兩級:設(shè)一個盤塊大小為1KB，每個盤塊號占4byte。則2級索引存放的文件的盤塊號總數(shù)為：256×256=64K，故文件的最大長度為64K×1KB=64MB設(shè)一個盤塊大小為4KB，每個盤塊號占4byte。則2級索引存放的文件的盤塊號總數(shù)為：1KB×1KB=1MB，故文件的最大長度為1M×4KB=4GB2、多級索引分配2、多級索引分配圖6-12兩級索引分配一、二、多級索引合用設(shè)每個塊大小為4K，一索引項占4字節(jié)，則直接地址：用iaddr(0)~iaddr(9)來存放直接地址，小文件（<40K)則立即讀出。一次間址：利用索引結(jié)點中的地址項iaddr(10)來提供一次間接地址，允許文件長達4MB多次尋址：當文件長度大于4MB+40KB時(一次間址與10個直接地址項)，用地址項iaddr(11)提供二次間接地址，文件最大長度可達4GB。地址項iaddr(12)作為三次間接地址，其所允許的文件最大長度可達4TB。3、混合索引分配方式圖6-13混合索引方式6.4目錄管理6.4目錄管理

在現(xiàn)代計算機系統(tǒng)中，主要依賴于文件目錄對文件實現(xiàn)快速、準確地查找。具有將文件名轉(zhuǎn)換為該文件在外存的物理位置的功能。對目錄管理的要求如下：實現(xiàn)“按名存取”。提高對目錄的檢索速度。文件共享。允許文件重名。6.4.1文件控制塊和索引結(jié)點

定義：用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)稱之為文件控制塊（FCB）；作用：文件管理程序借助于文件控制塊中的信息，實現(xiàn)對文件的各種操作；目錄：文件與文件控制塊一一對應，而把文件控制塊的有序集合稱之為目錄：目錄文件：一個文件控制塊就是一個文件目錄項，通常一個文件目錄也被看做是一個文件，稱為目錄文件；基本信息文件名：文件物理位置：（設(shè)備號，盤塊號，文件長度）文件邏輯結(jié)構(gòu)：流式記錄式：定長、變長文件物理結(jié)構(gòu)：順序放離散放：鏈式、索引式1、文件控制塊FCB存取控制信息(安全性)文件主/核準用戶/一般用戶存取權(quán)限。使用信息類文件的建立日期/時間；文件上一次修改時間；當前使用信息。例：DOS1、文件控制塊FCB文件名擴展名屬性備用時間日期第一塊號盤塊數(shù)圖6-14MS-DOS的文件控制塊索引結(jié)點的引入：為何引入：FCB中含:文件名、描述信息，它們較占空間索引結(jié)點：含文件描述信息。例：一個FCB為64byte，一個盤塊為1024byte，設(shè)文件共有3076個，因一個盤塊只能放1024/64=16個FCB，故文件目錄占了3076/16=192個塊，當要訪問某文件，平均調(diào)度塊數(shù)為(192+1)/2=96次。2、索引結(jié)點文件名索引結(jié)點編號文件名1文件名2……圖6-15UNIX的文件目錄UNIX系統(tǒng)中將FCB分為文件名、i（index)節(jié)點指針和相應的i節(jié)點，其中文件名和i節(jié)點指針占16字節(jié)（14+2）

離散存放目錄結(jié)構(gòu)查詢時只調(diào)入文件名部分，找到后才調(diào)入相應節(jié)點。2、索引結(jié)點磁盤索引結(jié)點：文件主標識符文件類型文件存取權(quán)限文件物理地址文件長度文件連接計數(shù)文件存取時間2、索引結(jié)點內(nèi)存索引結(jié)點：文件打開后，將磁盤索引結(jié)點的內(nèi)容部分或全部子集拷貝到內(nèi)存，并增加以下內(nèi)容：索引結(jié)點編號：用于標識內(nèi)存索引結(jié)點狀態(tài)：指示i結(jié)點是否上鎖或被修改訪問計數(shù)：每當有一進程要訪問此i結(jié)點時，將該訪問計數(shù)加1，訪問完再減1

文件所屬文件系統(tǒng)的邏輯設(shè)備號鏈接指針：設(shè)置有分別指向空閑鏈表和散列隊列的指針2、索引結(jié)點6.4.2目錄結(jié)構(gòu)

目錄項包括：文件名、文件擴展名、文件長度、文件類型、文件物理地址、文件屬性、狀態(tài)位。新建文件時—>有無同名—>加入目錄表—>狀態(tài)位置1刪除文件

—>回收塊—>清除占用目錄項特點：簡單速度慢/不允許重名/不便于共享(不能用不同名字訪問同一文件)。1、單級目錄結(jié)構(gòu)文件名物理地址文件說明狀態(tài)位文件名1文件名2…圖6-16單級目錄1、單級目錄結(jié)構(gòu)MFD+UFD新建與刪除文件特點：提高了速度：如n個用戶，每用戶最多m個文件，則最壞速度為n+m而非n*m在不同的用戶目錄中，可以使用相同的文件名不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個共享文件2、雙級目錄圖6-17兩級目錄結(jié)構(gòu)2、兩級目錄MFDUFD目錄文件中的目錄項可為：目錄文件、數(shù)據(jù)文件系統(tǒng)中有一個根目錄（或根目錄文件），在這個目錄中可登記一般文件，也可以登記目錄文件，在每個目錄文件中可以登記一般文件，也可以登記目錄文件。3、多級目錄結(jié)構(gòu)（樹型目錄結(jié)構(gòu)）(1)目錄結(jié)構(gòu)

在樹形目錄結(jié)構(gòu)中，每一個文件都有一個從根到葉的路徑。路徑名：從根目錄出發(fā)到某個文件的通路上所有各級子目錄名和該文件名的順序組合稱為文件的路徑名，在各級子目錄名和文件名之間可用“/”隔開。(2)路徑名相對路徑名：從當前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名稱。絕對路徑名：從樹根開始的路徑名稱MSDOS系統(tǒng)中文件路徑名\A\R\T\B\IU\I\D\B\PNIX系統(tǒng)中文件路徑名/A/R/T/B/IU/I/D/B/P允許重名由于查找文件總是從根目錄開始，因而查找的時間較長。事實上，用戶在一段時間內(nèi)會經(jīng)常訪問一個子目錄下的文件。為了提高效率和方便用戶，文件系統(tǒng)引進了“當前目錄”的概念。系統(tǒng)初始啟動后，當前目錄就是根目錄。當前目錄可根據(jù)需要任意改變，用戶可以用“改變當前目錄”命令指定自己當前的工作目錄。查找一個文件可從當前目錄開始，使用相對路徑名；當前目錄一般存放在內(nèi)存。(3)當前目錄問題：純樹形目錄結(jié)構(gòu)中，只能在用戶級對文件進行臨時共享它允許一個文件或目錄在多個父目錄中占有項目，但并不構(gòu)成環(huán)路。這種結(jié)構(gòu)方式叫做鏈接（Link）(4)非循環(huán)圖目錄結(jié)構(gòu)圖6-18多級目錄結(jié)構(gòu)主目錄(根目錄)數(shù)據(jù)文件(樹葉)其它目錄(樹的結(jié)點)增加目錄刪除目錄不刪除非空目錄可刪除非空目錄4、增加和刪除目錄6.4.3目錄查詢技術(shù)

實現(xiàn)按名存取用戶文件的步驟：

首先，系統(tǒng)利用用戶提供的文件名，找出該文件的文件控制塊或索引結(jié)點；其次，根據(jù)查到的FCB或索引結(jié)點中所記錄的文件物理地址（盤塊號），換算出文件在磁盤上的物理位置；最后，啟動磁盤驅(qū)動程序，將所需文件讀到內(nèi)存中。文件名—>目錄項（FCB）或索引結(jié)點—> 盤塊號—>啟動磁盤—>驅(qū)動程序目前對目錄的查詢技術(shù)有線性檢索法和HASH方法.線性檢索法又稱為順序檢索法在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄中找到指名文件的目錄項。在樹型目錄中，用戶提供的文件名是由多個文件分量名組成的路徑名，此時須對多級目錄進行查找。

1、線性檢索法圖6-19查找/usr/ast/mbox的步驟實現(xiàn)按名存取用戶文件的步驟：/usr/ast/mbox

1、線性檢索法

2、Hash方法

哈希表算法：目錄項信息存在一哈希表中，搜索時根據(jù)文件名計算哈希值，得到一個指向表中文件的指針處理此Hash轉(zhuǎn)換中“沖突”的有效規(guī)則是：

(1)在利用Hash法索引查找目錄時，如果目錄表中相應的目錄項是空的，則表示系統(tǒng)中并無指定文件。

(2)如果目錄項中的文件名與指定文件名相匹配，則表示該目錄項正是所要尋找的文件所對應的目錄項，故而可從中找到該文件所在的物理地址。

(3)如果在目錄表的相應目錄項中的文件名與指定文件名并不匹配，則表示發(fā)生了“沖突”，此時須將其Hash值再加上一個常數(shù)(該常數(shù)應與目錄的長度值互質(zhì))，形成新的索引值，再返回到第一步重新開始查找。6.5文件存儲空間的管理6.5.1空閑表法和空閑鏈表法

1、空閑表法（屬于連續(xù)分配方式）分配：首次/循環(huán)首次/最佳/最壞回收：判斷是否合并。由于連續(xù)分配比較快，因此對對換空間及小文件的管理適用。圖6-20空閑盤塊表序號第一空閑盤塊號空閑盤塊數(shù)12429331554——2、空閑鏈表法空閑盤塊鏈優(yōu)點：用于分配和回收一個盤塊的過程非常簡單缺點：可能該鏈很長，在為一個文件分配盤塊時，可能要重復操作多次?？臻e盤區(qū)鏈一個盤區(qū)含多個盤塊，類似于內(nèi)存分區(qū)分配與回收(合并)每個盤區(qū)含有：用于指示下一個空閑盤區(qū)的指針、指明本盤區(qū)大小的信息。分配通常采用首次適應算法，為了提高對空閑盤區(qū)的檢索速度，可采用顯式鏈接方法。6.5.2位示圖法位示圖是利用二進制的一位來表示磁盤中的一個盤塊的使用情況。1、位示圖圖6-21位示圖2、盤塊的分配：順序掃描，找一個或一組=0的塊；根據(jù)找到的行/列得以盤塊號。b=n(i-1)+j；(n代表每行的位數(shù))修改位圖，令map[i,j]=1。3、盤塊的回收：由磁塊號得(i,j)i=(b-1)div(n+1)j=(b-1)mod(n+1)修改位圖：令map[i,j]=0特點：易于訪問；占空間少，可放入內(nèi)存，查