第6章 文件管理

第六章文件管理武漢大學(xué)國(guó)際軟件學(xué)院

二零一一年·春《操作系統(tǒng)原理》16.1文件和文件系統(tǒng)6.2文件的邏輯結(jié)構(gòu)6.3外存分配方式6.4目錄管理6.5文件存儲(chǔ)空間的管理6.6文件共享與文件保護(hù)6.7數(shù)據(jù)一致性控制第六章文件管理26.1.1文件、記錄和數(shù)據(jù)項(xiàng)1.數(shù)據(jù)項(xiàng)

(1)基本數(shù)據(jù)項(xiàng)。這是用于描述一個(gè)對(duì)象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。例如，用于描述一個(gè)學(xué)生的基本數(shù)據(jù)項(xiàng)有：學(xué)號(hào)、姓名、年齡、所在班級(jí)等。6.1文件和文件系統(tǒng)31.數(shù)據(jù)項(xiàng)(2)組合數(shù)據(jù)項(xiàng)。由若干基本數(shù)據(jù)項(xiàng)組成。例如，經(jīng)理由正經(jīng)理和副經(jīng)理兩個(gè)基本項(xiàng)組成。又如，工資可由基本工資、工齡工資和獎(jiǎng)勵(lì)工資等基本項(xiàng)所組成?；緮?shù)據(jù)項(xiàng)除了數(shù)據(jù)名外，還應(yīng)有數(shù)據(jù)類型。由數(shù)據(jù)項(xiàng)的名字和類型兩者共同定義了一個(gè)數(shù)據(jù)項(xiàng)的“型”。而表征一個(gè)實(shí)體在數(shù)據(jù)項(xiàng)上的數(shù)據(jù)則稱為“值”。例如，學(xué)號(hào)/30211、姓名/王有年、性別/男等。6.1.1文件、記錄和數(shù)據(jù)項(xiàng)42.記錄記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對(duì)象在某方面的屬性。一個(gè)記錄應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需要描述對(duì)象的哪個(gè)方面。一個(gè)對(duì)象，由于所處的環(huán)境不同可作為不同的對(duì)象。例如，一個(gè)學(xué)生，當(dāng)作為班上的一名學(xué)生時(shí)，其描述應(yīng)使用學(xué)號(hào)、姓名、年齡及所在系班等。但若作為一個(gè)醫(yī)療對(duì)象時(shí)，其描述數(shù)據(jù)項(xiàng)則應(yīng)使用諸如病歷號(hào)、姓名、性別、出生年月、身高、體重、血壓及病史等項(xiàng)。6.1.1文件、記錄和數(shù)據(jù)項(xiàng)53.文件文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合，可分為兩種：有結(jié)構(gòu)文件：文件由若干個(gè)相關(guān)記錄組成；無(wú)結(jié)構(gòu)文件：可看成是一個(gè)字符流。文件在文件系統(tǒng)中是一個(gè)最大的數(shù)據(jù)單位，它描述了一個(gè)對(duì)象集。文件名的長(zhǎng)度因系統(tǒng)不同而異。如在有的系統(tǒng)中把名字規(guī)定為8個(gè)字符，而在有的系統(tǒng)中又規(guī)定可用14個(gè)字符。6.1.1文件、記錄和數(shù)據(jù)項(xiàng)6

文件屬性可以包括：(1)文件類型。(2)文件長(zhǎng)度。(3)文件的物理位置。(4)文件的建立時(shí)間。6.1.1文件、記錄和數(shù)據(jù)項(xiàng)圖6-1文件、記錄和數(shù)據(jù)項(xiàng)之間的層次關(guān)系71.文件類型1)按用途分類：(1)系統(tǒng)文件。(2)用戶文件。(3)庫(kù)文件。2)按文件中數(shù)據(jù)的形式分類(1)源文件。(2)目標(biāo)文件。(3)可執(zhí)行文件。6.1.2文件類型和文件系統(tǒng)模型81.文件類型3)按存取控制屬性分類(1)只執(zhí)行文件。(2)只讀文件。(3)讀寫文件。6.1.2文件類型和文件系統(tǒng)模型92.文件系統(tǒng)模型6.1.2文件類型和文件系統(tǒng)模型圖6-2文件系統(tǒng)模型文件系統(tǒng)接口對(duì)對(duì)象操縱和管理的軟件集合對(duì)象及其屬性用戶（程序）101)對(duì)象及其屬性文件管理系統(tǒng)管理的對(duì)象有：①文件。它作為文件管理的直接對(duì)象。②目錄。為了方便用戶對(duì)文件的存取和檢索，在文件系統(tǒng)中必須配置目錄。對(duì)目錄的組織和管理是方便用戶和提高對(duì)文件存取速度的關(guān)鍵。③磁盤(磁帶)存儲(chǔ)空間。文件和目錄必定占用存儲(chǔ)空間，對(duì)這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對(duì)文件的存取速度。6.1.2文件類型和文件系統(tǒng)模型112)對(duì)對(duì)象操縱和管理的軟件集合

這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實(shí)現(xiàn)的，其中包括：對(duì)文件存儲(chǔ)空間的管理、對(duì)文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對(duì)文件讀和寫的管理，以及對(duì)文件的共享與保護(hù)等功能。6.1.2文件類型和文件系統(tǒng)模型123)文件系統(tǒng)的接口為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用戶提供兩種類型的接口：(1)命令接口。這是指作為用戶與文件系統(tǒng)交互的接口。用戶可通過(guò)鍵盤終端鍵入命令，取得文件系統(tǒng)服務(wù)。(2)程序接口。這是指作為用戶程序與文件系統(tǒng)的接口。用戶程序可通過(guò)系統(tǒng)調(diào)用來(lái)取得文件系統(tǒng)的服務(wù)。6.1.2文件類型和文件系統(tǒng)模型13(1)創(chuàng)建文件。(2)刪除文件。(3)讀文件。(4)寫文件。(5)截?cái)辔募?6)設(shè)置文件的讀/寫位置。6.1.3文件操作142.文件的“打開”和“關(guān)閉”操作“打開”是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開文件表的一個(gè)表目中，并將該表目的編號(hào)(或稱為索引)返回給用戶。當(dāng)用戶再要求對(duì)該文件進(jìn)行相應(yīng)的操作時(shí)，可利用系統(tǒng)所返回的索引號(hào)向系統(tǒng)提出操作請(qǐng)求。系統(tǒng)可直接利用該索引號(hào)到打開文件表中去查找，避免了對(duì)該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開銷，也顯著地提高了對(duì)文件的操作速度。6.1.3文件操作152.文件的“打開”和“關(guān)閉”操作

如果用戶已不再需要對(duì)該文件實(shí)施相應(yīng)的操作時(shí)，可利用“關(guān)閉”(close)系統(tǒng)調(diào)用來(lái)關(guān)閉此文件，OS將會(huì)把該文件從打開文件表中的表目上刪除掉。6.1.3文件操作163.其它文件操作為了方便用戶使用文件，通常，OS都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，可將這些調(diào)用分成若干類：對(duì)文件屬性進(jìn)行操作；對(duì)目錄進(jìn)行操作；用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對(duì)文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。其中，前兩類操作最為常用，下面將深入地介紹。6.1.3文件操作173.其它文件操作（續(xù)）對(duì)文件屬性進(jìn)行操作，即允許用戶直接設(shè)置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者(文件主)、改變對(duì)文件的訪問(wèn)權(quán)，以及查詢文件的狀態(tài)(包括文件類型、大小和擁有者以及對(duì)文件的訪問(wèn)權(quán)等)；對(duì)目錄進(jìn)行操作，如創(chuàng)建一個(gè)目錄，刪除一個(gè)目錄，改變當(dāng)前目錄和工作目錄等；6.1.3文件操作18對(duì)于任何一個(gè)文件，都存在著以下兩種形式的結(jié)構(gòu)：(1)文件的邏輯結(jié)構(gòu)(FileLogicalStructure)。(2)文件的物理結(jié)構(gòu)，又稱為文件的存儲(chǔ)結(jié)構(gòu)，是指文件在外存上的存儲(chǔ)組織形式。6.2文件的邏輯結(jié)構(gòu)19有結(jié)構(gòu)文件：(1)定長(zhǎng)記錄。(2)變長(zhǎng)記錄?？刹捎貌煌绞浇M織記錄：(1)順序文件。(2)索引文件。(3)索引順序文件。6.2.1文件邏輯結(jié)構(gòu)的類型202.無(wú)結(jié)構(gòu)文件采用有結(jié)構(gòu)的文件形式（數(shù)據(jù)庫(kù)文件等）相對(duì)較少，而大量的源程序、可執(zhí)行文件、庫(kù)函數(shù)等，所采用的是無(wú)結(jié)構(gòu)的文件形式，即流式文件。其長(zhǎng)度以字節(jié)為單位。對(duì)流式文件的訪問(wèn)，則是采用讀寫指針來(lái)指出下一個(gè)要訪問(wèn)的字符。可以把流式文件看作是記錄式文件的一個(gè)特例。在UNIX系統(tǒng)中，所有文件都被看作是流式文件系統(tǒng)不對(duì)文件進(jìn)行格式處理。6.2.1文件邏輯結(jié)構(gòu)的類型211.邏輯記錄的排序第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無(wú)關(guān)。通常的辦法是由時(shí)間來(lái)決定，即按存入時(shí)間的先后排列，最先存入的記錄作為第一個(gè)記錄，其次存入的為第二個(gè)記錄，……依此類推。第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)鍵字(詞)排列?？梢园搓P(guān)鍵詞的長(zhǎng)短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。6.2.2順序文件222.對(duì)順序文件(SequentialFile)的讀/寫操作圖6-3定長(zhǎng)和變長(zhǎng)記錄文件6.2.2順序文件233.順序文件的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：順序文件的最佳應(yīng)用場(chǎng)合，是在對(duì)諸記錄進(jìn)行批量存取時(shí)，即每次要讀或?qū)懸淮笈涗?。此時(shí)，對(duì)順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲(chǔ)在磁帶上，并能有效地工作。6.2.2順序文件243.順序文件的優(yōu)缺點(diǎn)缺點(diǎn)1：

對(duì)于可變長(zhǎng)記錄的順序文件，如果用戶(程序)要求查找或修改單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。這時(shí)，順序文件所表現(xiàn)出來(lái)的性能就可能很差，尤其是當(dāng)文件較大時(shí)，情況更為嚴(yán)重。6.2.2順序文件253.順序文件的優(yōu)缺點(diǎn)缺點(diǎn)2：增加或刪除記錄比較困難。為了解決這一問(wèn)題，可以為順序文件配置一個(gè)運(yùn)行記錄文件(LogFile)或稱為事務(wù)文件(TransactionFile)，把試圖增加、刪除或修改的信息記錄于其中，規(guī)定每隔一定時(shí)間，例如4小時(shí)，將運(yùn)行記錄文件與原來(lái)的主文件加以合并，產(chǎn)生一個(gè)按關(guān)鍵字排序的新文件。6.2.2順序文件26對(duì)于定長(zhǎng)記錄文件，如果要查找第i個(gè)記錄，可直接根據(jù)下式計(jì)算來(lái)獲得第i個(gè)記錄相對(duì)于第一個(gè)記錄首址的地址：

Ai=i×L對(duì)于可變長(zhǎng)度記錄的文件，要查找其第i個(gè)記錄時(shí)，須先計(jì)算出該記錄的首地址。為此須順序地查找每個(gè)記錄，從中獲得相應(yīng)記錄的長(zhǎng)度Li，然后才能按下式計(jì)算出第i個(gè)記錄的首址。假定在每個(gè)記錄前用一個(gè)字節(jié)指明該記錄的長(zhǎng)度，則6.2.3索引文件27圖6-4索引文件的組織6.2.3索引文件28圖6-5索引順序文件6.2.4索引順序文件291.直接文件對(duì)于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換(Keytoaddresstransformation)。組織直接文件的關(guān)鍵，在于用什么方法進(jìn)行從記錄值到物理地址的轉(zhuǎn)換。6.2.5直接文件和哈希文件30圖6-6Hash文件的邏輯結(jié)構(gòu)2.哈希(Hash)文件6.2.5直接文件和哈希文件31圖6-7磁盤空間的連續(xù)分配6.3.1連續(xù)分配6.3外存分配方式322.連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)點(diǎn)如下：(1)順序訪問(wèn)容易。(2)順序訪問(wèn)速度快。連續(xù)分配的主要缺點(diǎn)如下：(1)要求有連續(xù)的存儲(chǔ)空間。(2)必須事先知道文件的長(zhǎng)度。6.3.1連續(xù)分配331.隱式鏈接圖6-8磁盤空間的鏈接式分配6.3.2鏈接分配342.顯式鏈接圖6-9顯式鏈接結(jié)構(gòu)6.3.2鏈接分配35圖6-10MS-DOS的文件物理結(jié)構(gòu)361.單級(jí)索引分配鏈接分配方式雖然解決了連續(xù)分配方式所存在的問(wèn)題，但又出現(xiàn)了另外兩個(gè)問(wèn)題，即：(1)不能支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號(hào)。(2)FAT需占用較大的內(nèi)存空間。6.3.3索引分配37圖6-12索引分配方式382.多級(jí)索引分配圖6-13兩級(jí)索引分配39圖6-14混合索引方式40混合索引(1)直接地址。為了提高對(duì)文件的檢索速度，在索引結(jié)點(diǎn)中可設(shè)置10個(gè)直接地址項(xiàng)，即用iaddr(0)~iaddr(9)來(lái)存放直接地址。換言之，在這里的每項(xiàng)中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號(hào)。假如每個(gè)盤塊的大小為4KB，當(dāng)文件不大于40KB時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部盤塊號(hào)。6.3.3索引分配41混合索引

(2)一次間接地址。對(duì)于大、中型文件，只采用直接地址是不現(xiàn)實(shí)的。為此，可再利用索引結(jié)點(diǎn)中的地址項(xiàng)iaddr(10)來(lái)提供一次間接地址。

這種方式的實(shí)質(zhì)就是一級(jí)索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個(gè)盤塊號(hào)記入其中。在一次間址塊中可存放1K個(gè)盤塊號(hào)，因而允許文件長(zhǎng)達(dá)4MB。6.3.3索引分配42混合索引

(3)多次間接地址。當(dāng)文件長(zhǎng)度大于4MB+40KB時(shí)(一次間址與10個(gè)直接地址項(xiàng))，系統(tǒng)還須采用二次間址分配方式。這時(shí)，用地址項(xiàng)iaddr(11)提供二次間接地址。

該方式的實(shí)質(zhì)是兩級(jí)索引分配方式。系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的盤號(hào)。在采用二次間址方式時(shí)，文件最大長(zhǎng)度可達(dá)4GB。同理，地址項(xiàng)iaddr(12)作為三次間接地址，其所允許的文件最大長(zhǎng)度可達(dá)4TB。6.3.3索引分配43對(duì)目錄管理的要求如下：(1)實(shí)現(xiàn)“按名存取”。(2)提高對(duì)目錄的檢索速度。(3)文件共享。(4)允許文件重名。6.4目錄管理44圖6-15MS-DOS的文件控制塊文件控制塊(1)基本信息類①文件名；②文件物理位置；③文件邏輯結(jié)構(gòu)；④文件的物理結(jié)構(gòu)(2)存取控制信息類(3)使用信息類6.4.1文件控制塊和索引結(jié)點(diǎn)452.索引結(jié)點(diǎn)1)索引結(jié)點(diǎn)的引入圖6-16UNIX的文件目錄文件名索引結(jié)點(diǎn)編號(hào)文件名1文件名2……6.4.1文件控制塊和索引結(jié)點(diǎn)462)磁盤索引結(jié)點(diǎn)(1)文件主標(biāo)識(shí)符(2)文件類型(3)文件存取權(quán)限(4)文件物理地址(5)文件長(zhǎng)度(6)文件連接計(jì)數(shù)(7)文件存取時(shí)間6.4.1文件控制塊和索引結(jié)點(diǎn)473)內(nèi)存索引結(jié)點(diǎn)(1)索引結(jié)點(diǎn)編號(hào)。用于標(biāo)識(shí)內(nèi)存索引結(jié)點(diǎn)。(2)狀態(tài)。指示i結(jié)點(diǎn)是否上鎖或被修改。(3)訪問(wèn)計(jì)數(shù)。每當(dāng)有一進(jìn)程要訪問(wèn)此i結(jié)點(diǎn)時(shí)，將該訪問(wèn)計(jì)數(shù)加1，訪問(wèn)完再減1。(4)文件所屬文件系統(tǒng)的邏輯設(shè)備號(hào)。(5)鏈接指針。設(shè)置有分別指向空閑鏈表和散列隊(duì)列的指針。6.4.1文件控制塊和索引結(jié)點(diǎn)481.單級(jí)目錄結(jié)構(gòu)文件名物理地址文件說(shuō)明狀態(tài)位文件名1文件名2…圖6-17單級(jí)目錄6.4.2目錄結(jié)構(gòu)491.單級(jí)目錄結(jié)構(gòu)單級(jí)目錄的優(yōu)點(diǎn)是簡(jiǎn)單且能實(shí)現(xiàn)目錄管理的基本功能——按名存取，但卻存在下述一些缺點(diǎn)：(1)查找速度慢(2)不允許重名(3)不便于實(shí)現(xiàn)文件共享6.4.2目錄結(jié)構(gòu)50圖6-18兩級(jí)目錄結(jié)構(gòu)2.兩級(jí)目錄6.4.2目錄結(jié)構(gòu)512.兩級(jí)目錄兩級(jí)目錄具有以下優(yōu)點(diǎn)：(1)提高了檢索目錄的速度(2)在不同的用戶目錄中，可以使用相同的文件名。(3)不同用戶可使用不同的文件名來(lái)訪問(wèn)系統(tǒng)中的同一個(gè)共享文件6.4.2目錄結(jié)構(gòu)523.多級(jí)目錄結(jié)構(gòu)(1)目錄結(jié)構(gòu)圖6-19多級(jí)目錄結(jié)構(gòu)6.4.2目錄結(jié)構(gòu)533.多級(jí)目錄結(jié)構(gòu)(2)路徑名在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通路。在該路徑上從樹的根(即主目錄)開始，把全部目錄文件名與數(shù)據(jù)文件名，依次地用“/”連接起來(lái)，即構(gòu)成該數(shù)據(jù)文件的路徑名(pathname)。系統(tǒng)中的每一個(gè)文件都有惟一的路徑名。例如，在圖6-18中用戶B為訪問(wèn)文件J，應(yīng)使用其路徑名/B/F/J來(lái)訪問(wèn)。從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名，稱為相對(duì)路徑名(relativepathname)；從樹根開始的路徑名稱為絕對(duì)路徑名(absolutepathname)。6.4.2目錄結(jié)構(gòu)543.多級(jí)目錄結(jié)構(gòu)(3)當(dāng)前目錄(CurrentDirectory)。當(dāng)文件系統(tǒng)含有許多級(jí)時(shí)，每訪問(wèn)一個(gè)文件，都要使用從樹根開始直到樹葉(數(shù)據(jù)文件)為止的、包括各中間結(jié)點(diǎn)(目錄)名的全路徑名。這相當(dāng)麻煩，同時(shí)由于一個(gè)進(jìn)程運(yùn)行時(shí)所訪問(wèn)的文件，大多僅局限于某個(gè)范圍，因而非常不便?？蔀槊總€(gè)進(jìn)程設(shè)置一個(gè)“當(dāng)前目錄”，又稱為“工作目錄”。進(jìn)程對(duì)各文件的訪問(wèn)都相對(duì)于“當(dāng)前目錄”而進(jìn)行。此時(shí)各文件所使用的路徑名，只需從當(dāng)前目錄開始，逐級(jí)經(jīng)過(guò)中間的目錄文件，最后到達(dá)要訪問(wèn)的數(shù)據(jù)文件。6.4.2目錄結(jié)構(gòu)553.多級(jí)目錄結(jié)構(gòu)(4).增加和刪除目錄(1)不刪除非空目錄。當(dāng)目錄(文件)不空時(shí)，不能將其刪除，必須先刪除目錄中的所有文件，使之成為空目錄，然后再予以刪除。如果目錄中還包含有子目錄，還必須采取遞歸調(diào)用方式來(lái)將其刪除，在MS-DOS中就是采用這種刪除方式。(2)可刪除非空目錄。要?jiǎng)h除一目錄時(shí)，如果在該目錄中還包含有文件，則目錄中的所有文件和子目錄也被刪除。6.4.2目錄結(jié)構(gòu)561.線性檢索法圖6-19查找/usr/ast/mbox的步驟6.4.3目錄查詢技術(shù)572.Hash方法對(duì)于“沖突”，可按下面的有效規(guī)則來(lái)處理：(1)在利用Hash法索引查找目錄時(shí)，如果目錄表中相應(yīng)的目錄項(xiàng)是空的，則表示系統(tǒng)中并無(wú)指定文件。(2)如果目錄項(xiàng)中的文件名與指定文件名相匹配，則表示該目錄項(xiàng)正是所要尋找的文件所對(duì)應(yīng)的目錄項(xiàng)，故而可從中找到該文件所在的物理地址。(3)如果在目錄表的相應(yīng)目錄項(xiàng)中的文件名與指定文件名并不匹配，則表示發(fā)生了“沖突”，此時(shí)須將其Hash值再加上一個(gè)常數(shù)(該常數(shù)應(yīng)與目錄的長(zhǎng)度值互質(zhì))，形成新的索引值，再返回到第一步重新開始查找。6.4.3目錄查詢技術(shù)586.5.1空閑表法和空閑鏈表法1.空閑表法圖6-20空閑盤塊表序號(hào)第一空閑盤塊號(hào)空閑盤塊數(shù)12429331554——6.5文件存儲(chǔ)空間的管理59(2)存儲(chǔ)空間的分配與回收?？臻e盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對(duì)相鄰接者應(yīng)予以合并。6.5.1空閑表法和空閑鏈表法602.空閑鏈表法(1)空閑盤塊鏈(2)空閑盤區(qū)鏈6.5.1空閑表法和空閑鏈表法611.位示圖圖6-21位示圖6.5.2位示圖法622.盤塊的分配(1)順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。(2)將所找到的一個(gè)或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)制位，位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算：b=n(i-1)+j式中，n代表每行的位數(shù)。(3)修改位示圖，令map［i,j］=1。6.5.2位示圖法633.盤塊的回收

(1)將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。轉(zhuǎn)換公式為：

i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示圖。令map［i,j］=1。6.5.2位示圖法641.空閑盤塊的組織圖6-23空閑盤塊的成組鏈接法6.5.3成組鏈接法65

2.空閑盤塊的分配與回收系統(tǒng)為用戶分配文件所需的盤塊：首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。若該盤塊號(hào)已是棧底，即S.free(0)，即當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。由于在該盤塊號(hào)所對(duì)應(yīng)的盤塊中記有下一組可用的盤塊號(hào)，因此須調(diào)用磁盤讀過(guò)程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。然后，再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū))。最后，把棧中的空閑盤塊數(shù)減1并返回。

6.5.3成組鏈接法662.空閑盤塊的分配與回收在系統(tǒng)回收空閑盤塊時(shí)，須調(diào)用盤塊回收過(guò)程進(jìn)行回收。它是將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá)100時(shí)，表示棧已滿，便將現(xiàn)有棧中的100個(gè)盤塊號(hào)，記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底。6.5.3成組鏈接法67圖6-24包含有共享文件的文件系統(tǒng)6.6文件共享與文件保護(hù)68圖6-25基于索引結(jié)點(diǎn)的共享方式69圖6-26進(jìn)程B鏈接前后的情況70在利用符號(hào)鏈方式實(shí)現(xiàn)文件共享時(shí)，只有文件主才擁有指向其索引結(jié)點(diǎn)的指針；而共享該文件的其他用戶，則只有該文件的路徑名，并不擁有指向其索引結(jié)點(diǎn)的指針。因此，不會(huì)發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。當(dāng)文件的擁有者把一個(gè)共享文件刪除后，其他用戶試圖通過(guò)符號(hào)鏈去訪問(wèn)一個(gè)已被刪除的共享文件時(shí)，會(huì)因系統(tǒng)找不到該文件而使訪問(wèn)失敗，于是再將符號(hào)鏈刪除，此時(shí)不會(huì)產(chǎn)生任何影響。6.6.2利用符號(hào)鏈實(shí)現(xiàn)文件共享71(1)通過(guò)存取控制機(jī)制來(lái)防止由人為因素所造成的文件不安全性。(2)通過(guò)磁盤容錯(cuò)技術(shù)，來(lái)防止由磁盤部分的故障所造成的文件不安全性。(3)通過(guò)“后備系統(tǒng)”來(lái)防止由自然因素所造成的不安全性。6.6.3磁盤容錯(cuò)技術(shù)721.第一級(jí)容錯(cuò)技術(shù)SFT-Ⅰ1)雙份目錄和雙份文件分配表

在磁盤上存放的文件目錄和文件分配表FAT，是文件管理所用的重要數(shù)據(jù)結(jié)構(gòu)。如果這些表格被破壞，將導(dǎo)致磁盤上的部分或全部文件成為不可訪問(wèn)的，因而也就等效于文件的丟失。為了防止這類情況發(fā)生，可在不同的磁盤上或在磁盤的不同區(qū)域中，分別建立(雙份)目錄表和FAT。其中，一份被稱為主目錄及主FAT；把另一份稱為備份目錄及備份FAT。6.6.3磁盤容錯(cuò)技術(shù)731.第一級(jí)容錯(cuò)技術(shù)SFT-Ⅰ2)熱修復(fù)重定向和寫后讀校驗(yàn)(1)熱修復(fù)重定向(Hot-Redirection)。(2)寫后讀校驗(yàn)(ReadafterwriteVerification)方式。6.6.3磁盤容錯(cuò)技術(shù)742.第二級(jí)容錯(cuò)技術(shù)SFT-Ⅱ(1)磁盤鏡像(DiskMirroring)。圖6-27磁盤鏡像示意6.6.3磁盤容錯(cuò)技術(shù)75圖6-27磁盤雙工示意(2)磁盤雙工(DiskDuplexing)。6.6.3磁盤容錯(cuò)技術(shù)766.7.1事務(wù)1.事務(wù)的定義事務(wù)是用于訪問(wèn)和修改各種數(shù)據(jù)項(xiàng)的一個(gè)程序單位。

事務(wù)可以看作是一系列相關(guān)讀和寫操作。數(shù)據(jù)可以分散地存放在同一文件的不同記錄中，也可放在多個(gè)文件中。只有對(duì)分布在不同位置的同一數(shù)據(jù)進(jìn)行的讀寫操作全部完成時(shí)，才能以提交操作(CommitOperation)來(lái)終止事務(wù)。只要有任何讀、寫或修改操作失敗，便須執(zhí)行夭折操作(AbortOperation)。讀或?qū)懖僮鞯氖】赡苁怯捎谶壿嬪e(cuò)誤，也可能是系統(tǒng)故障所導(dǎo)致的。6.7數(shù)據(jù)一致性控制772.事務(wù)記錄(TransactionRecord)事務(wù)名：用于標(biāo)識(shí)該事務(wù)的惟一名字；數(shù)據(jù)項(xiàng)名：它是被修改數(shù)據(jù)項(xiàng)的惟一名字；舊值：修改前數(shù)據(jù)項(xiàng)的值；新值：修改后數(shù)據(jù)項(xiàng)將具有的值。6.7.1事務(wù)783.恢復(fù)算法

恢復(fù)