1、第六章 文 件 管 理,在現(xiàn)代計算機系統(tǒng)中，要用到大量的程序和數(shù)據(jù)，它們以文件的形式存放在外存中，需要時可隨時調(diào)入內(nèi)存。操作系統(tǒng)中的文件管理模塊，負責(zé)管理在外存上的文件，并負責(zé)對文件的存取、共享和保護。文件管理功能既方便了用戶，保證了文件的安全性，還可有效地提高系統(tǒng)資源的利用率。,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結(jié)構(gòu) 6.3 外存分配方式 6.4 目錄管理 6.5 文件存儲空間的管理 6.6 文件共享與文件保護 6.7 數(shù)據(jù)一致性控制,6.1 文件和文件系統(tǒng),6.1.1 文件、記錄和數(shù)據(jù)項,1. 數(shù)據(jù)項,(1) 基本數(shù)據(jù)項。這是用于描述一個對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名

2、的最小邏輯數(shù)據(jù)單位， 即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。 (2) 組合數(shù)據(jù)項。它是由若干個基本數(shù)據(jù)項組成的，簡稱組項。 基本數(shù)據(jù)項除了數(shù)據(jù)名外，還應(yīng)有數(shù)據(jù)類型。因為基本項僅是描述某個對象的屬性，根據(jù)屬性的不同，需要用不同的數(shù)據(jù)類型來描述。 由數(shù)據(jù)項的名字和類型兩者共同定義了一個數(shù)據(jù)項的“型”。 而表征一個實體在數(shù)據(jù)項上的數(shù)據(jù)則稱為“值”。,2. 記錄 記錄是一組相關(guān)數(shù)據(jù)項的集合，用于描述一個對象在某方面的屬性。一個記錄應(yīng)包含哪些數(shù)據(jù)項，取決于需要描述對象的哪個方面。而一個對象，由于他所處的環(huán)境不同可把他作為不同的對象。 關(guān)鍵字是能唯一標(biāo)識一個記錄的數(shù)據(jù)項。,3. 文件

3、,文件是指由創(chuàng)建者所定義的、 具有文件名的一組相關(guān)信息的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。 在有結(jié)構(gòu)的文件中，文件由若干個相關(guān)記錄組成；而無結(jié)構(gòu)文件則被看成是一個字符流。文件在文件系統(tǒng)中是一個最大的數(shù)據(jù)單位，它描述了一個對象集。,文件應(yīng)具有自己的屬性，屬性可以包括： (1) 文件類型 (2) 文件長度 (3) 文件的物理位置 (4) 文件的建立時間,6.1.2 文件類型和文件系統(tǒng)模型,1. 文件類型,為了便于管理和控制文件而將文件分為若干種類型,2. 文件系統(tǒng)模型,文件系統(tǒng)是OS的重要組成部分。下圖為文件系統(tǒng)的模型圖：,分為三個層次，最低層是對象及其屬性說明；中間層是對對象操縱和管理的軟

4、件集合；最高層是文件系統(tǒng)提供給用戶的接口。,1對象及其屬性說明（最低層） 文件 目錄 磁盤（磁帶）存儲空間,2對對象操縱和管理的軟件集合（中間層） 是文件系統(tǒng)的核心部分。其功能有五點：,3文件系統(tǒng)的接口（最高層） 提供兩種類型接口： 命令接口 這是指作為用戶與文件系統(tǒng)交互的接口。用戶可通過鍵盤終端鍵入命令，取得文件系統(tǒng)的服務(wù)。 程序接口 這是指作為用戶程序與文件系統(tǒng)的接口。用戶程序可通過系統(tǒng)調(diào)用來取得 文件系統(tǒng)的服務(wù)。,6.1.3 文件操作,對文件的操作,對文件的操作可分為兩大類： 對記錄的操作 這可能是用戶用得最多的一類操作。有以下5種：,2. 文件的“打開”和“關(guān)閉”操作,所謂“打開”，是

5、指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號(或稱為索引)返回給用戶。以后， 當(dāng)用戶再要求對該文件進行相應(yīng)的操作時，便可利用系統(tǒng)所返回的索引號向系統(tǒng)提出操作請求。系統(tǒng)這時便可直接利用該索引號到打開文件表中去查找，從而避免了對該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開銷，也顯著地提高了對文件的操作速度。如果用戶已不再需要對該文件實施相應(yīng)的操作時，可利用“關(guān)閉”(close)系統(tǒng)調(diào)用來關(guān)閉此文件，OS將會把該文件從打開文件表中的表目上刪除掉。,3. 其它文件操作 為了方便用戶使用文件，通常，OS都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，

6、可將這些調(diào)用分成若干類：最常用的一類是有關(guān)對文件屬性進行操作的，即允許用戶直接設(shè)置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者(文件主)、改變對文件的訪問權(quán)，以及查詢文件的狀態(tài)(包括文件類型、大小和擁有者以及對文件的訪問權(quán)等)；另一類是有關(guān)目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改變當(dāng)前目錄和工作目錄等；此外，還有用于實現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)進行操作的系統(tǒng)調(diào)用等。,6.2 文件的邏輯結(jié)構(gòu),通常，文件是由一系列的記錄組成的。文件系統(tǒng)設(shè)計的關(guān)鍵，是將這些記錄構(gòu)成一個文件的方法，以及將一個文件存儲到外存上的方法。對于任一個文件，都存在兩種形式的結(jié)構(gòu)： 文件的邏輯結(jié)構(gòu) 文件的

7、物理結(jié)構(gòu),對文件的邏輯結(jié)構(gòu)的要求如下：,是從用戶觀點出發(fā)，所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨立于物理特性，又稱為文件組織,又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式，這與存儲介質(zhì)的存儲性能有關(guān)。,6.2.1 文件邏輯結(jié)構(gòu)的類型,有結(jié)構(gòu)文件,文件邏輯結(jié)構(gòu)可分為兩大類：有結(jié)構(gòu)文件（記錄式文件）和無結(jié)構(gòu)文件（流式文件）。,即記錄式文件。大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫采用此類文件。在此類文件中，記錄的長度可分定長和不定長兩類。 根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式來組織這些記錄。形成下述的文件：,2. 無結(jié)構(gòu)文件 即流式文件。大量的源程序、可執(zhí)行文件、庫函數(shù)等采用的

8、是此類文件。,6.2.2 順序文件,1. 邏輯記錄的排序,文件是記錄的集合。文件中的記錄可以是任意順序的，一般可歸納為以下兩種情況： 串結(jié)構(gòu)-記錄之間的順序與關(guān)鍵字無關(guān)。通常的辦法是由時間來決定，即按存入時間的先后排列。 順序結(jié)構(gòu)-文件中的所有記錄按關(guān)鍵字排序。 對順序結(jié)構(gòu)文件可有更高的檢索效率。,2. 對順序文件(Sequential File)的讀/寫操作,順序文件中的記錄可以是定長的，也可以是變長的，如下圖：,3. 順序文件的優(yōu)缺點,6.2.3 索引文件,對于定長記錄文件，如果要查找第i個記錄， 可直接根據(jù)下式計算來獲得第i個記錄相對于第一個記錄首址的地址： Ai=iL 然而，對于可變長

9、度記錄的文件，要查找其第i個記錄時，須首先計算出該記錄的首地址。為此，須順序地查找每個記錄，從中獲得相應(yīng)記錄的長度Li，然后才能按下式計算出第i個記錄的首址。假定在每個記錄前用一個字節(jié)指明該記錄的長度，則,則由以上可見，對于變長記錄較難實現(xiàn)直接存取。為了解決這一問題，可為變長記錄文件建立一張索引表。索引表本身是一個定長記錄的順序文件。索引文件組織圖如下：,在對索引文件進行檢索時，首先是根據(jù)用戶（程序）提供的關(guān)鍵字，并利用折半查找法去檢索索引表，從中找到相應(yīng)的表項；再利用該表項中給出的指向記錄的指針值，去訪問所需的記錄。,6.2.4 索引順序文件,索引順序文件（Index Sequential

10、File）有效地克服了變長記錄文件不便于直接存取的缺點，且付出代價不算大。索引順序文件如下圖：,在對索引順序文件進行檢索時，首先也是利用用戶（程序）所提供的關(guān)鍵字以及某種查找方法，去檢索索引表，找到該記錄所在記錄組中第一個記錄的表項，從中得到該記錄組第一個記錄在主文件中的位置；然后，再利用順序查找法去查找主文件，從中找到記錄。,6.2.5 直接文件和哈希文件,1. 直接文件,對于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換(Key to address transformation)。

11、組織直接文件的關(guān)鍵，在于用什么方法進行從記錄值到物理地址的轉(zhuǎn)換。,2. 哈希(Hash)文件,Hash文件的邏輯結(jié)構(gòu),6.3 外存分配方式,由于磁盤具有可直接訪問的特性，故利用磁盤來存放文件時，具有很大的靈活性。在為文件分配外存空間時所要考慮的主要問題有：,目前常用的外存分配方法有： 連續(xù)分配 鏈接分配 索引分配,6.3 外存分配方式,6.3.1 連續(xù)分配,連續(xù)分配（Continuous Allocation）要求為每一個文件分配一組相鄰接的盤塊。一組盤塊的 地址定義了磁盤上的一段線性地址。在采用連續(xù)分配方式時，可把邏輯文件中的記錄，順序 地存取到鄰接的各物理盤塊中，這樣形成的物理文件稱順序文

12、件。,這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。為使系統(tǒng)能找到文件存放的地址，應(yīng)在目錄項的“文件物理地址”字段中，記錄該文件的第一個記錄所在的盤塊號和文件長度。,連續(xù)分配的主要優(yōu)缺點,連續(xù)分配的主要優(yōu)點如下： 順序訪問容易。 (2) 順序訪問速度快。,連續(xù)分配的主要缺點如下： 要求有連續(xù)的存儲空間。 (2) 必須事先知道文件的長度。,6.3.2 鏈接分配,在采用鏈接分配（Linked Allocation）方式時，可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，由次所形成的物理文件稱為鏈接文件。 鏈接方式又可分為隱式鏈接和顯式鏈接

13、。,1.隱式鏈接 在采用隱式鏈接分配方式時，在文件目錄的每個目錄項中，都須含有指向鏈接文件第 一個盤塊和最后一個盤塊的指針，如右圖所示。,2. 顯式鏈接,指把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表是整個磁盤僅設(shè)置一張。由于分配給文件的所有盤塊號都放在該表中，故把該表稱為文件分配表 （File Allocation）。,主要問題 不能支持高效地直接存取 FAT表需占用較大的內(nèi)存空間,MS-DOS的文件物理結(jié)構(gòu),6.3.3 索引分配,1. 單級索引分配 鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題， 但又出現(xiàn)了另外兩個問題， 即： (1) 不能支持高效的直接存取。要對一

14、個較大的文件進行直接存取，須首先在FAT中順序地查找許多盤塊號。 (2) FAT需占用較大的內(nèi)存空間。 索引分配方法為每個文件分配一個索引塊（表），把分配給該文件的所有盤塊號，都記錄在該索引表中，因而該索引塊就是一個含有許多盤塊號的數(shù)組。,索引分配方式,主要問題是：可能要花費較多的外存空間,2. 多級索引分配,兩級索引分配,當(dāng)OS為一個大文件分配磁盤空間時，可能出現(xiàn)索引塊太多的情況，這時是低效的。應(yīng) 為這些索引塊在建立一級索引，稱第一級索引，這樣便形成了兩級索引分配方式。文件非 常大時，還可用三級、四級索引分配方式。,是指將多種分配方式相結(jié)合而形成的一種分配方式。它們把所有的地址項分成兩類，

15、即直接地址和間接地址。如下圖,3. 混合索引分配方式,混合索引方式,(1) 直接地址 為了提高對文件的檢索速度，在索引結(jié)點中可設(shè)置10個直接地址項，即用iaddr(0)iaddr(9)來存放直接地址。換言之，在這里的每項中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號。假如每個盤塊的大小為 4 KB，當(dāng)文件不大于40 KB時，便可直接從索引結(jié)點中讀出該文件的全部盤塊號。 (2) 一次間接地址 對于大、中型文件，只采用直接地址是不現(xiàn)實的。為此，可再利用索引結(jié)點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中

16、。在一次間址塊中可存放1K個盤塊號， 因而允許文件長達4 MB。 (3) 多次間接地址 當(dāng)文件長度大于4MB+40KB時(一次間址與10個直接地址項)，系統(tǒng)還須采用二次間址分配方式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號。在采用二次間址方式時，文件最大長度可達4GB。同理，地址項iaddr(12)作為三次間接地址，其所允許的文件最大長度可達4TB。,6.4 目 錄 管 理,為了能有效地管理大量文件，必須對它們加以妥善的組織。這主要依賴于文件目錄來實現(xiàn)。或者說，文件目錄具有將文件名轉(zhuǎn)換為該文件在外存的物理

17、位置的功能，這也正是文件目錄提供的最基本的功能。對文件目錄的管理有以下要求：,6.4.1 文件控制塊和索引結(jié)點,為能對一個文件進行正確的存取，必須為文件設(shè)置文件控制塊。文件與文件控制塊一一對應(yīng)，而把文件控制塊的有序集合稱為文件目錄。換言之，一個文件控制塊就是一個文件目錄項。通常一個文件目錄也被看作一個文件，稱目錄文件。,1.文件控制塊,文件控制塊包含以下三種信息：,各信息包括以下各項：,2. 索引結(jié)點,1) 索引結(jié)點的引入,UNIX的文件目錄,在檢索目錄文件的過程中，只用到了文件名，一概用不著該文件的描述信息。僅當(dāng)找到一個其文件名與指定文件名相匹配的目錄項時，才需從該目錄項中讀出該文件的物理地

18、址。 因此，有些系統(tǒng)如UNIX，采用了把文件名與文件描述信息分開的辦法。即把文件 描述信息單獨形成一個稱為索引結(jié)點的數(shù)據(jù)結(jié)構(gòu)，簡稱i結(jié)點；而在文件目錄中的每個 目錄項，則僅由文件名及指向該文件所對應(yīng)的i結(jié)點的指針?biāo)鶚?gòu)成。,2) 磁盤索引結(jié)點,(1) 文件主標(biāo)識符 (2) 文件類型 (3) 文件存取權(quán)限 (4) 文件物理地址 (5) 文件長度 (6) 文件連接計數(shù) (7) 文件存取時間,它是指存放在磁盤上的索引結(jié)點。每個文件有唯一的一個磁盤索引結(jié)點。主要包括以下內(nèi)容：,(1) 索引結(jié)點編號。 用于標(biāo)識內(nèi)存索引結(jié)點。 (2) 狀態(tài)。 指示i結(jié)點是否上鎖或被修改。 (3) 訪問計數(shù)。 每當(dāng)有一進程要

19、訪問此i結(jié)點時， 將該訪問計數(shù)加1， 訪問完再減1。 (4) 文件所屬文件系統(tǒng)的邏輯設(shè)備號。 (5) 鏈接指針。 設(shè)置有分別指向空閑鏈表和散列隊列的指針。,3)內(nèi)存索引結(jié)點,是指存放在內(nèi)存的索引結(jié)點。當(dāng)文件被打開時，要將磁盤索引結(jié)點拷貝到內(nèi)存索 引結(jié)點中，以便于以后使用。在內(nèi)存索引結(jié)點中又增加了以下內(nèi)容：,6.4.2 目錄結(jié)構(gòu),1. 單級目錄結(jié)構(gòu),單級目錄（Single Level Director）結(jié)構(gòu)是最簡單的目錄結(jié)構(gòu)。如下圖：,創(chuàng)建、刪除文件,單級目錄結(jié)構(gòu)的優(yōu)、缺點,2. 兩級目錄,為了克服單級目錄結(jié)構(gòu)的缺點，可為每用戶建立一個單獨的用戶文件目錄UFD，它由用戶所有文件的文件控制塊組成。

20、再在系統(tǒng)中建立一個主文件目錄MFD。在主文件目錄中，每個用戶文件目錄都占有一個目錄項；其目錄項中包括用戶名和指向該用戶目錄文件的指針。,兩級目錄結(jié)構(gòu)基本上克服了單級目錄的缺點，并具有以下優(yōu)點：,兩級目錄結(jié)構(gòu)的優(yōu)點,3. 多級目錄結(jié)構(gòu),(1) 目錄結(jié)構(gòu),樹型目錄具有檢索效率高、允許重名、便于實現(xiàn)文件共享等一系列優(yōu)點。,(2) 路徑名 在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通路。在該路徑上從樹的根(即主目錄)開始，把全部目錄文件名與數(shù)據(jù)文件名，依次地用“/”連接起來，即構(gòu)成該數(shù)據(jù)文件的路徑名(path name)。 (3) 當(dāng)前目錄 可為每個進程設(shè)置一個“當(dāng)前目錄”，又稱為“工

21、作目錄”。進程對各文件的訪問都是相對于“當(dāng)前目錄”進行的。此時對各文件所使用的路徑名，只需從當(dāng)前目錄開始，再 逐級通過中間的目錄文件，最后到達要訪問的數(shù)據(jù)文件。將這一路徑上的全部目錄文件名 與數(shù)據(jù)文件名用“/”連接而形成的路徑名稱為相對路徑名。從樹根開始的路徑名，稱為 絕對路徑名。,4. 增加和刪除目錄,在樹型結(jié)構(gòu)目錄中，用戶可為自己建立UPD，并可以再創(chuàng)建子目錄。對于一個已不需 要的目錄，可按如下方法刪除：,6.4.3 目錄查詢技術(shù),1. 線性檢索法,對目錄進行查詢的方式有兩種：線性檢索法和Hash方法,假定用戶給定的文件路徑名為/usr/ast/mbox，查找/usr/ast/mobx的過

22、程如下：,2. Hash方法,一種處理此“沖突”的有效規(guī)則是： (1) 在利用Hash法索引查找目錄時，如果目錄表中相應(yīng)的目錄項是空的，則表示系統(tǒng)中并無指定文件。 (2) 如果目錄項中的文件名與指定文件名相匹配， 則表示該目錄項正是所要尋找的文件所對應(yīng)的目錄項，故而可從中找到該文件所在的物理地址。 (3) 如果在目錄表的相應(yīng)目錄項中的文件名與指定文件名并不匹配，則表示發(fā)生了“沖突”，此時須將其Hash值再加上一個常數(shù)(該常數(shù)應(yīng)與目錄的長度值互質(zhì))，形成新的索引值， 再返回到第一步重新開始查找。,6.5 文件存儲空間的管理,6.5.1 空閑表法和空閑鏈表法,1. 空閑表法,為了實現(xiàn)存儲空間的分配

23、，首先必須記住空閑存儲空間的情況。為此，首先，系統(tǒng)應(yīng)為分配存儲空間而設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；其次，系統(tǒng)應(yīng)提供對存儲空間進行分配和回收的功能。下面介紹幾種常用的文件存儲空間管理方法。,空閑表法屬于連續(xù)分配方式。它與內(nèi)存管理中的動態(tài)分區(qū)分配方式相似。,空閑盤塊表,它為每個文件分配一個連續(xù)的存儲空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于 一個空閑表項。,空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序地檢索空閑表的各表項， 直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進程)，同時修改空

24、閑表。系統(tǒng)在對用戶所釋放的存儲空間進行回收時，也采取類似于內(nèi)存回收的方法， 即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并。,2. 空閑鏈表法,(1) 空閑盤塊鏈 它是將磁盤上的所有空閑存儲空間，以盤塊為基本元素拉成一條鏈。優(yōu)點是用于分配 和回收一個盤塊的過程非常簡單；缺點是空閑盤塊鏈可能很長。 (2) 空閑盤區(qū)鏈 這是將磁盤上的所有空閑盤區(qū)（每個盤區(qū)可包含若干個盤塊）拉成一條鏈。在每個盤 區(qū)上除了含有用于指示下一個空閑盤區(qū)的指針外，還應(yīng)標(biāo)有指明本盤區(qū)大?。ūP塊數(shù)）的 信息。這種方法分配和回收過程較復(fù)雜，但空閑盤區(qū)鏈較短。,是將所有的空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成

25、鏈的基本元素的不同，可有兩種鏈表方 式：空閑盤塊鏈、空閑盤區(qū)鏈。,6.5.2 位示圖法,1. 位示圖,位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況。當(dāng)其值為“0”時，表 示對應(yīng)的盤塊空閑；為“1”時表示已分配。由所有盤塊對應(yīng)的位構(gòu)成一個集合，稱為位示 圖。位示圖也可描述為一個二維數(shù)組map：Var map:array1.m,1.n of bit;,2. 盤塊的分配,根據(jù)位示圖進行盤塊分配時，可分三步進行：,3. 盤塊的回收,盤塊的回收分兩步：,6.5.3 成組鏈接法,1. 空閑盤塊的組織,空閑表法和空閑鏈法，都不適合用在大型文件系統(tǒng)中。在UNIX中采用的成組鏈接法兼?zhèn)淞藘煞N方法的優(yōu)點

26、而克服了兩種方法均有的、表太長的缺點,文件區(qū)中的所有空閑盤塊，被分成若干個組。 將每一組含有的盤塊總數(shù)N和該組所有的盤塊號，記入其前一組的第一個盤塊的S.free(0)S.free(99)中。 將第一組的盤塊總數(shù)和所有的盤塊號，記入空閑盤塊號棧中。 最末一組只有99個盤塊，盤塊號記入其前一組第一盤塊的S.free(1)S.free(99)中。而在S.free(0)中存放“0”，作為空閑盤塊鏈的結(jié)束標(biāo)志。,2. 空閑盤塊的分配與回收 當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時，須調(diào)用盤塊分配過程來完成。該過程首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，然

27、后將棧頂指針下移一格。若該盤塊號已是棧底，即S.free(0)，這是當(dāng)前棧中最后一個可分配的盤塊號。由于在該盤塊號所對應(yīng)的盤塊中記有下一組可用的盤塊號，因此，須調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號棧的內(nèi)容，并把原棧底對應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。然后，再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū))。最后，把棧中的空閑盤塊數(shù)減1并返回。,在系統(tǒng)回收空閑盤塊時，須調(diào)用盤塊回收過程進行回收。它是將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。當(dāng)棧中空閑盤塊號數(shù)目已達100時， 表示棧已滿，便將現(xiàn)有棧中的100個盤塊號， 記入新回收的盤

28、塊中，再將其盤塊號作為新棧底。,6.6 文件共享與文件保護,在現(xiàn)代計算機系統(tǒng)中，有些文件可供許多用戶所共享，或者，有若干人在共同地為一個項目而工作，有關(guān)該項目的所有文件能供這一組人員所共享。為此，現(xiàn)代計算機系統(tǒng)必須提供文件共享功能，即指系統(tǒng)應(yīng)允許多個用戶（進程）共享同一份文件。,早期實現(xiàn)文件共享的方法 ：繞彎路法、連訪法 繞彎路法：在該方法中，允許每個用戶獲得一“當(dāng)前目錄”，用戶所訪問的所有文件都是相對于當(dāng)前目錄的；當(dāng)所訪問的文件不在其當(dāng)前目錄下時，可以通過“向上走”的方式去訪問其上級目錄。 連訪法：為了提高對共享文件的訪問速度，可在相應(yīng)的目錄項之間進行鏈接，即，使一個目錄中的目錄項直接指向另

29、一目錄中的目錄項。,1. 基于索引結(jié)點的共享方式,在樹型結(jié)構(gòu)目錄中，當(dāng)有兩個（或多個）用戶要共享一個子目錄或文件時，必須講共享文件或子目錄鏈接到兩個（或多個）用戶的目錄中，以便能方便地找到該文件，此時該文件系統(tǒng)的目錄結(jié)構(gòu)已是個有向無環(huán)圖DAG（Directed Acyclic Graph）。如下圖所示。,為了建立B目錄與共享文件之間的鏈接，并順利實現(xiàn)共享，可以引用索引結(jié)點，即諸如文件的物理地址及其它的文件屬性等信息，不在放在目錄項中，而放在索引結(jié)點中。在文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點的指針。如下圖所示,圖 6-25 進程B鏈接前后的情況,6.6.2 利用符號鏈實現(xiàn)文件共享,B為了共享

30、C的一個文件F，可以由系統(tǒng)創(chuàng)建一個LINK類型的新文件，將新文件F寫入B的用戶目錄中，以實現(xiàn)B的目錄與文件F的鏈接。在新文件中只包含被鏈接文件F的路徑名，稱這樣的鏈接方法為符號鏈接（Symbolic Linking）。 在利用符號鏈接方式實現(xiàn)文件共享時，只有文件主才擁有指向其索引結(jié)點的指針；而共享該文件的其他用戶，只有該文件的路徑名，而不是指向索引結(jié)點的指針。,符號鏈接方式的問題 每次訪問貢獻文件時，都可能要多次讀盤； 要為每個共享用戶建立一條符號鏈，消費一定的磁盤空間。 符號鏈接方式的優(yōu)點 能夠用于鏈接（通過計算機網(wǎng)絡(luò)）世界上任何地方的機器中的文件，此時只需提供該文件所在機器的網(wǎng)絡(luò)地址，以及

31、在該機器中的文件路徑。,6.6.3 磁盤容錯技術(shù),采取措施： (1) 通過存取控制機制來防止由人為因素所造成的文件不安全性。 (2) 通過磁盤容錯技術(shù)，來防止由磁盤部分的故障所造成的文件不安全性。 (3) 通過“后備系統(tǒng)”來防止由自然因素所造成的不安全性。,影響文件安全性的主要因素： (1) 人為因素，有意或無意破壞 (2) 系統(tǒng)因素，由于系統(tǒng)某部分出現(xiàn)異常 (3) 自然因素,1. 第一級容錯技術(shù)SFT-,1) 雙份目錄和雙份文件分配表 在磁盤上存放的文件目錄和文件分配表FAT， 是文件管理所用的重要數(shù)據(jù)結(jié)構(gòu)。如果這些表格被破壞， 將導(dǎo)致磁盤上的部分或全部文件成為不可訪問的，因而也就等效于文件

32、的丟失。為了防止這類情況發(fā)生，可在不同的磁盤上或在磁盤的不同區(qū)域中，分別建立(雙份)目錄表和FAT。 其中，一份被稱為主目錄及主FAT； 把另一份稱為備份目錄及備份FAT。,2) 熱修復(fù)重定向和寫后讀校驗,熱修復(fù)重定向(Hot-Redirection)。 (2) 寫后讀校驗(Read after write Verification)方式。,2. 第二級容錯技術(shù)SFT-,(1) 磁盤鏡像(Disk Mirroring)。,(2) 磁盤雙工(Disk Duplexing)。,6.7 數(shù)據(jù)一致性控制,6.7.1 事務(wù),1. 事務(wù)的定義 事務(wù)是用于訪問和修改各種數(shù)據(jù)項的一個程序單位。 事務(wù)也可以被看

33、作是一系列相關(guān)讀和寫操作。被訪問的數(shù)據(jù)可以分散地存放在同一文件的不同記錄中，也可放在多個文件中。只有對分布在不同位置的同一數(shù)據(jù)所進行的讀和寫(含修改)操作全部完成時，才能再以托付操作(Commit Operation)來終止事務(wù)。 只要有一個讀、寫或修改操作失敗，便須執(zhí)行夭折操作(Abort Operation)。讀或?qū)懖僮鞯氖】赡苁怯捎谶壿嬪e誤， 也可能是系統(tǒng)故障所導(dǎo)致的。,2. 事務(wù)記錄(Transaction Record),事務(wù)名： 用于標(biāo)識該事務(wù)的惟一名字； 數(shù)據(jù)項名： 它是被修改數(shù)據(jù)項的惟一名字； 舊值： 修改前數(shù)據(jù)項的值； 新值： 修改后數(shù)據(jù)項將具有的值。,3. 恢復(fù)算法,恢復(fù)算法可利用以下兩個過程： (1) undoTi。該過程把所有被事務(wù)Ti修改過的數(shù)據(jù)，恢復(fù)為修改前的值。 (2) redoTi。該過程能把所有被事務(wù)Ti修改過的數(shù)據(jù)，設(shè)置為新值。 如果系統(tǒng)發(fā)生故障， 系統(tǒng)應(yīng)對以前所發(fā)生的事務(wù)進行清理。,6.7.2 檢查點,1. 檢查點(Check Points)的作用,引入檢查點的主要目的，是使對事務(wù)記錄表中事務(wù)記錄的清理工作經(jīng)?；?， 即每隔一定時間便做一次下述工