第六章

文件系統程序和數據以文件的形式保留在外存中。本章主要討論文件的組織結構，共享與保護以及文件系統空間管理。6．1

文件和文件系統文件系統的功能實現按名存取文件的物理結構文件信息的檢索文件的共享和保護文件組織形式數據項：最低級的數據組織形式?；緮祿棧阂粋€對象的某種屬性的字符集，是數據組織中可以命名的最小邏輯單位。組合數據項：一個對象的若干個基本數據項的組合。記錄：一組相關數據項的集合。文件：文件是一個具有符號名字的一組相關元素的有序集合。有結構文件（定長和變長文件）和無結構文件（流式文件）文件的常用屬性文件類型文件長度文件的物理位置文件的存取控制文件的建立時間文件的類型按文件的性質和用途分為：系統文件，庫文件，用戶文件按文件中數據的形式分為：源文件、目標文件、可執行文件按組織形式分為：普通文件，目錄文件，特殊文件按文件的存取控制屬性分為：只讀，讀寫文件、只執行文件。按文件的物理結構分類：順序文件、鏈接文件、索引文件。文件系統OS中負責管理和存取文件信息的軟件機構。負責文件的建立，撤消，存入，讀寫，修改和復制，還負責完成對文件的按名存取和進行存取控制。使用文件系統的優點使用的方便性數據的安全性接口的統一性文件系統模型用戶（程序）文件存儲空間的管理；文件目錄的管理；邏輯地址到物理地址的轉換；文件讀、寫管理；文件的共享與保護文件系統的模型對象及其屬性說明：文件、目錄和磁盤存儲空間。對對象操縱和管理的軟件集合：文件存儲空間、目錄的管理、從文件邏輯地址到系統物理地址的轉換、對文件的讀、寫及共享，保護等。文件系統的接口：命令接口和程序接口。文件操作

對文件最基本操作：創建、刪除、讀、寫截斷、設置文件的讀寫位置。對文件“打開”和“關閉”OS對文件的一般操作步驟：1、檢索文件目錄，找到指定文件的屬性及在外存上的位置；

2、對文件施加相應的讀、寫操作。

打開(Open)：指系統將指定文件的屬性從外存拷貝到內存打開文件表的一個表目中，并將表目的編號返回給用戶。

關閉（Close）：將把相應的文件從打開文件表中的表目上刪除掉。6．2

文件的邏輯結構

文件的邏輯結構（文件的組織）：從用戶角度看到的文件組織形式，也就是它的記錄結構，用戶可以直接處理。它獨立于文件物理特性。

文件的物理結構（文件的存儲結構）：文件在外存上的存儲組織形式，一般由操作系統決定和使用。它與存儲介質有關，同時與外存的分配方式有關。邏輯結構的類型（記錄式文件和流式文件）有結構文件：定長記錄和變長記錄記錄的組織形式順序文件、索引文件、索引順序文件流式文件它是有序字符的集合，文件長度等于該文件所包含的字符數。順序文件順序文件是記錄式文件串結構（連續結構）：按記錄生成的先后順序連續排列的邏輯結構。順序結構：把文件中的鍵（關鍵字）按規定的順序排列起來。使用各種查找算法可實現高效檢索。存取方法順?wptr=wptr+L；R序0

存取法R記1

錄的讀寫…?定長：Rirptr=rptr+L；rptr變長記錄不定長：rptr=rptr+Li；wptr=wptr+Li；rptr節保留該記L0

用一字錄長度R0L1R1…LiRi

索引文件：為文件中所有記錄建立一張索引表，每個記錄對應一索引表項，用于記錄該記錄的

長度及指向該記錄的指針（指向該記錄在邏輯

地址空間的首址）

索引順序結構：將順序文件中所有記錄分為若干個組；為順序文件建立一張索引表，在索引表中為每組的第一個記錄建立一個索引項，其中含有該記錄的鍵值和指向該記錄的指針。

直接文件：根據給定的記錄鍵值，直接獲得指定記錄的物理地址。哈希（hash)文件：目前最為廣泛的一種直接文件，它利用Hash函數將記錄鍵值轉換為相應記錄的地址。6．3

外存分配方法外存分配方式：連續分配、鏈接分配、索引分配。連續分配（順序文件）分配與回收分配：把一個邏輯上連續的文件信息依次存放在物理塊中?；厥眨核槠韱栴}。特點優點：順序訪問容易，能很快進行存取。缺點：要求有連續的存儲空間；不便于記錄的增，刪操作；必須事先知道文件長度，不能動態增長，存在碎片問題。鏈接分配（串聯文件）：文件被離散放到磁盤的盤塊中。隱式鏈接在文件的目錄中記錄該文件的第一和最后一個盤塊的指針，每個塊中的指針指向文件的下一物理塊號。優點：文件可動態增長，不需指明文件長度，便于增刪記錄，節約空間。缺點：只適合順序存取，不宜于直接存取，查找效率低。由于設置鏈接字而破壞了物理信息的完整。改進：將幾個盤塊組成簇（cluster），以簇為位分配。顯示鏈接將鏈接文件各物理塊的指針顯示地放在內存的一張鏈接表中。該表整個磁盤中設一張，表的序號為盤塊號，在文件的FCB的物理地址中填寫其鏈首指針所對應的盤塊號。FAT（File

Allocation

Table）：文件分配表，整個磁盤設置一張，放在內存中。缺點：不能直接存??；FAT占較大內存空間。FAT和NTFS技術FAT12、FAT16，FAT32以及NTFS的文件分配基本上都是采用類似顯示鏈接方法。1、FAT12：（每個表項占12bit）每個分區中都配有兩張文件分配表FAT1和FAT2，在FAT的每個表項中存放下一個盤塊號，而將文件的第一個盤塊號放在自己的FCB中。整個系統有一張文件分配表FAT。在FAT的每個表項中存放下一個盤塊號。簇：由一組連續的扇區構成，在FAT中作為一個虛擬扇區，大小一般是2n個盤塊。FAT和NTFS技術2、FAT16：每個表項16位在FAT16中，每個簇中可以有的盤塊數可為4、8、16、32、64FAT16和FAT32都不支持長文件名。3、FAT32：每個表項占32bit.在FAT32中，每個簇固定為4KB。FAT32比FAT16支持更小簇的更大的磁盤容量。同時支持長文件名。FAT和NTFS技術4、NTFSNTFS使用64位磁盤地址；可以很好支持長文件名，單個文件名限制在255個字符內，全路徑名最長為32767字符；具有系統容錯功能，提供數據一致性。NTFS以簇作為磁盤分配的基本單位，具有了與磁盤物理扇區大小無關的獨立性。卷上簇的大小稱為卷因子，為盤塊的2n倍，最大64KB索引文件要求為每一文件建立一張索引表。每個表目指出文件邏輯記錄所在的物理塊號。特點：方便地進行隨機存??；增加了索引表的空間開銷，增加一次訪問操作。單級索引（串聯文件方式組織）多級索引（多重索引方式組織）綜合組織方式（混合索引）把索引表的頭幾項設計為直接尋址方式，存放物理塊號，后幾項設計成多重索引。綜合組織方式適用于順序存取和隨機存取。直接地址：

iaddr(0)

—

iaddr(9) 用于小于10盤塊的文件一次間接地址：iaddr(10)大、中型文件二次間接地址：iaddr(11)三次間接地址：iaddr(12)大、超大型文件6．3

文件目錄管理

一個文件的說明信息稱為該文件的目錄。用戶向系統提供符號名，系統根據文件的符號名找到它的物理地址。

功能：實現文件的按名存取，實現符號名與具體物理地址之間的轉換，文件的共享和保護。文件控制塊和索引結點文件的組成：文件說明（FCB）和文件體。FCB即為文件的目錄。文件與FCB一一對應，FCB的有序集合通常稱為文件目錄。一個文件目錄也被看為一文件，稱為一個目錄文件。文件控制塊（File

Control

Block）基本信息：文件名、物理位置、邏輯結構、物理結構。存取控制信息：存取權限使用信息：建立和修改的時間，當前使用文件的進程情況等。索引結點文件目錄的缺陷：FCB中有許多信息與文件的查找無關。索引結點的引入目錄：文件名和指向i結點的指針i結點：文件描述信息。文件名索引結點編號文件名1PTR1文件名2PTR2……磁盤索引結點：每個文件有唯一的磁盤索引結點。文件主標識：擁有文件的個人或小組的標識符。文件類型：正規文件、目錄文件、特別文件。文件存取權限：各類用戶對文件的存取權限。

文件物理地址：直接或間接的給出數據文件的盤塊號。文件長度：文件的字節數。

文件連接計數：所有共享該文件的進程（用戶）數。

文件存取時間：本文件最近被進程存取的時間、最近被修改的時間及索引結點最近被修改的時間內存索引結點（存放在內存中的索引結點）文件被打開后，系統要將磁盤索引結點拷貝到內存的索引結點中。索引結點編號：標識內存索引結點狀態：該結點i是否上鎖或被修改訪問計數：使用該結點的進程數文件所在設備的邏輯設備號鏈接指針：空閑鏈表、散列隊列指針單級目錄（系統中只有一張目錄表）目錄內容：文件名、物理地址、其它屬性。文件訪問過程：直接查表創建和刪除文件：直接修改目錄表項存在的問題重名問題：別名問題：文件數量過多時，查找效率低。兩級目錄結構：系統由主目錄（MFD）和用戶目錄（UFD）構成。文件的建立和文件的刪除：文件的查找：主目錄項+用戶目錄項樹型目錄多級樹型目錄結構（結點與目錄）文件路徑名（路徑的唯一性）當前目錄（工作目錄）增加和刪除目錄（刪除目錄，同時要刪除該目錄下所有文件和目錄的目錄項，同時使上一級目錄中對應的目錄項為空）目錄的查詢技術過程根據文件名（全名）找到其FCB或索引結點；查找FCB或索引結點中的文件物理地址（盤塊號），換算為物理位置；啟動磁盤驅動程序，將文件讀入內存。檢索方法順序查找法：二分查找法：Hash法：6．4

文件存儲空間管理

系統應能自動地為用戶分配存儲空間，管理系統和用戶的存儲空間，實現按名存取。

文件存儲空間的管理包括空閑塊的組織分配和回收。空閑表空閑表把一個連續未分配區域稱為“空閑文件”，系統為所有“空閑文件”單獨建立一個目錄。表目內容：序號，第一個空白塊號，空白塊個數?？臻g分配和回收序號第一空閑盤塊號空閑盤塊數124293--空閑鏈表法空閑盤塊鏈（以盤塊為鏈的基本單位）分配和釋放順序：從頭分配，從尾回收。缺點：盤塊鏈可能很長?？臻e盤區鏈（以空閑盤塊區為鏈的基本單位）分配：首次適應算法回收：分配和回收的過程較復雜，且存在拼接問題位示圖為文件存儲器存儲空間建立一張位示圖，用以反映整個空間的分配情況。簡單，速度快，占一定的空間。盤塊號與位示圖行列的分配與回收的轉換公式：成組鏈接法實現方法對所有的空白塊從尾倒著向前分組，每

組的塊數及相應塊號記錄在前一組的第一塊中。(第一組99塊，隨后每組100塊)，最后一組（不足100塊）的數據登記在空閑盤塊棧（卷資源表）中。第二組的0號單元的值仍為100，1號單元值為0

（文卷卷尾標志），表示無空閑塊可分配。假定系統中有349塊空閑盤塊：其組織方式如下：分配和釋放系統工作后，把磁盤文件卷的卷資源復制到內存指定區域。資源表中登記空閑塊號的區域是一種棧結構。其中，記載總塊數作為該空白塊棧的指針ptr。分配時，ptr-1，然后取出對應項作為這次申請得到的物理塊。如此下去，直到棧底。當ptr=0時，續入下一組的塊號及總數，并把該塊分配出去。當ptr=0，且相應此表目中的值為0時，表示遇到卷尾標志。當回收時，先登記塊號，然后ptr+1，當填滿一組后，再回收一塊時，把前一組的內容記入該塊內，置ptr=0，并把這一塊的塊號記入相應表目中。特點空白塊號的登記不占用額外空間。

絕大部分分配和釋放工作都在主存進行。把總塊數作為空白塊棧的指針使用，是理想的存儲結構。效率高。6．5

文件共享早期共享方法繞道法（當訪問內容不在本目錄下，則每一次都要指明訪問路徑）連訪法（鏈接法）

一個目錄中的表目直接指向另一個目錄表目，在要訪問的表目之間直接建立一條鏈接。

在FCB中必須增加“連訪屬性”和“用戶計數”項?；谒饕Y點的共享方法樹型目錄中文件共享的問題：將共享文件鏈接到兩個用戶的目錄中。用索引結點實現文件共享指向相同的索引結點鏈接計數器count文件共享的過程基于索引的共享共享的鏈接過程利用符號鏈實現文件共享實現B共享C的文件F，由系統創建LINK類型的新文件（也命名為F），它包含被C的F文件的路徑名（符號鏈），并寫入B的用戶目錄中。

只有文件主才擁有指向索引結點的指針，其它共享用戶通過路徑名訪問（可以解決指針懸空的問題）。問題

訪問速度慢；鏈接文件也要建立索引結點；同一文件有不同的文件名，導致多個副本存在。6．6

文件存取控制文件保護文件保護機構的功能存取驗證模塊的基本任務審定用戶的存取權限；比較用戶存取權限和本次存取要求；比較本次存取要求和被訪問文件的存取保護信息。保護域進程僅在保護域內執行操作，同時保護域指明了進程所能操作的對象。進程與域的關系：靜態聯系：可用資源集在進程的整個生命周期內是固定的，在該方式下，應允許修改域的內容。動態聯系：可用資源集在其整個生命周期內是變化的。在該方式下，允許進程

在不同時期，從一個域切換到另一個域。訪問（存取控制）矩陣實現方法用一個二維矩陣來實現存取控制，一維是所有的域（用戶或進程），另一維列出全部文件。每個元素表示某一用戶對某一文件的存取控制權限。訪問（存取）控制表把有存取要求的用戶按某種關系或工程項目的類別分為若干組，同時規定每組的存取權限，得到文件的存取控制表。訪問權限表以用戶或用戶組為單位建立存取控制表，稱為用戶權限表。將一個用戶（組）所要存取的文件名集中起來存入一張表中，每個表目指明用戶對相應文件的存取權限。分級安全管理（一般分為4級）系統級防止用戶非法進入系統：注冊（系統管理員完成）、登錄（用戶完成）等。用戶級用戶分類的兩種類型文件主、伙伴和一般用戶。超級用戶、系統操作員、用戶和顧客。文件訪問權限：建立(C)、刪除(D)、打開(O)、讀(R)、寫(W)、查詢(S)、修改(M)和父權(P)。目錄級只有系統核心具有寫目錄的權利。保護系統目錄，與用戶權限無關。文件級通過對文件屬性（8種常用屬性）的設置，來控