計算機操作系統(tǒng)第三版第6章

1、第六章 文件管理 第六章第六章 文文 件件 管管 理理 6.1 6.1 文件和文件系統(tǒng)文件和文件系統(tǒng) 6.2 6.2 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu) 6.3 6.3 外存分配方式外存分配方式 6.4 6.4 目錄管理目錄管理 6.5 6.5 文件存儲空間的管理文件存儲空間的管理 6.6 6.6 文件共享與文件保護文件共享與文件保護 6.7 6.7 數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 第六章 文件管理 6.1 文件和文件系統(tǒng)文件和文件系統(tǒng) 6.1.1 文件、記錄和數(shù)據(jù)項文件、記錄和數(shù)據(jù)項 1. 數(shù)據(jù)項數(shù)據(jù)項 (1) 基本數(shù)據(jù)項。這是用于描述一個對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單

2、位， 即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。例如，用于描述一個學(xué)生的基本數(shù)據(jù)項有： 學(xué)號、 姓名、 年齡、 所在班級等。 第六章 文件管理 (2) 組合數(shù)據(jù)項。它是由若干個基本數(shù)據(jù)項組成的，簡稱組項。例如，經(jīng)理便是個組項，它由正經(jīng)理和副經(jīng)理兩個基本項組成。又如，工資也是個組項，它可由基本工資、工齡工資和獎勵工資等基本項所組成。 基本數(shù)據(jù)項除了數(shù)據(jù)名外，還應(yīng)有數(shù)據(jù)類型。因為基本項僅是描述某個對象的屬性，根據(jù)屬性的不同，需要用不同的數(shù)據(jù)類型來描述。例如，在描述學(xué)生的學(xué)號時，應(yīng)使用整數(shù)； 描述學(xué)生的姓名則應(yīng)使用字符串(含漢字)；描述性別時，可用邏輯變量或漢字。可見，由數(shù)據(jù)項的名

3、字和類型兩者共同定義了一個數(shù)據(jù)項的“型”。 而表征一個實體在數(shù)據(jù)項上的數(shù)據(jù)則稱為“值”。例如，學(xué)號/30211、姓名/王有年、性別/男等。 第六章 文件管理 2. 記錄記錄 記錄是一組相關(guān)數(shù)據(jù)項的集合，用于描述一個對象在某方面的屬性。一個記錄應(yīng)包含哪些數(shù)據(jù)項，取決于需要描述對象的哪個方面。而一個對象，由于他所處的環(huán)境不同可把他作為不同的對象。 例如，一個學(xué)生，當(dāng)把他作為班上的一名學(xué)生時， 對他的描述應(yīng)使用學(xué)號、姓名、年齡及所在系班，也可能還包括他所學(xué)過的課程的名稱、 成績等數(shù)據(jù)項。 但若把學(xué)生作為一個醫(yī)療對象時，對他描述的數(shù)據(jù)項則應(yīng)使用諸如病歷號、 姓名、 性別、 出生年月、 身高、 體重、

4、血壓及病史等項。 第六章 文件管理 3. 文件文件 文件是指由創(chuàng)建者所定義的、 具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。 在有結(jié)構(gòu)的文件中，文件由若干個相關(guān)記錄組成；而無結(jié)構(gòu)文件則被看成是一個字符流。文件在文件系統(tǒng)中是一個最大的數(shù)據(jù)單位，它描述了一個對象集。例如，可以將一個班的學(xué)生記錄作為一個文件。一個文件必須要有一個文件名， 它通常是由一串ASCII碼或(和)漢字構(gòu)成，名字的長度因系統(tǒng)不同而異。如在有的系統(tǒng)中把名字規(guī)定為8個字符，而在有的系統(tǒng)中又規(guī)定可用14個字符。 第六章 文件管理 屬性可以包括：(1) 文件類型。(2) 文件長度。 (3) 文件的物理位置。 (4

5、) 文件的建立時間。 文件記錄1記錄2記錄n數(shù)據(jù)項1數(shù)據(jù)項2數(shù)據(jù)項n圖 6-1 文件、 記錄和數(shù)據(jù)項之間的層次關(guān)系 第六章 文件管理 6.1.2 文件類型和文件系統(tǒng)模型文件類型和文件系統(tǒng)模型 1. 文件類型文件類型 1) 按用途分類(1) 系統(tǒng)文件。 (2) 用戶文件。 (3) 庫文件。 第六章 文件管理 2) 按文件中數(shù)據(jù)的形式分類 (1) 源文件。 (2) 目標(biāo)文件。 (3) 可執(zhí)行文件。 第六章 文件管理 3) 按存取控制屬性分類 (1) 只執(zhí)行文件。 (2) 只讀文件。 (3) 讀寫文件。 第六章 文件管理 2. 文件系統(tǒng)模型文件系統(tǒng)模型 圖 6-2 文件系統(tǒng)模型 第六章 文件管理 1

6、) 對象及其屬性 文件管理系統(tǒng)管理的對象有： 文件。 它作為文件管理的直接對象。 目錄。為了方便用戶對文件的存取和檢索，在文件系統(tǒng)中必須配置目錄。對目錄的組織和管理是方便用戶和提高對文件存取速度的關(guān)鍵。 磁盤(磁帶)存儲空間。 文件和目錄必定占用存儲空間，對這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對文件的存取速度。 第六章 文件管理 2) 對對象操縱和管理的軟件集合 這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實現(xiàn)的，其中包括：對文件存儲空間的管理、對文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機制、對文件讀和寫的管理，以及對文件的共享與保護等功能。 第六章

7、 文件管理 3) 文件系統(tǒng)的接口 為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用戶提供兩種類型的接口： (1) 命令接口。這是指作為用戶與文件系統(tǒng)交互的接口。 用戶可通過鍵盤終端鍵入命令，取得文件系統(tǒng)的服務(wù)。 (2) 程序接口。這是指作為用戶程序與文件系統(tǒng)的接口。 用戶程序可通過系統(tǒng)調(diào)用來取得文件系統(tǒng)的服務(wù)。 第六章 文件管理 6.1.3 文件操作文件操作 (1) 創(chuàng)建文件。 (2) 刪除文件。 (3) 讀文件。 (4) 寫文件。 (5) 截斷文件。 (6) 設(shè)置文件的讀/寫位置。 第六章 文件管理 2. 文件的文件的“打開打開”和和“關(guān)閉關(guān)閉”操作操作 所謂“打開”，是指系統(tǒng)將指名文件的屬性(包括

8、該文件在外存上的物理位置)從外存拷貝到內(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)用

9、，可將這些調(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)文件的邏輯結(jié)構(gòu) 對于任何一個文件，都存在著以下兩種形式的結(jié)構(gòu)： （1）文件的邏輯結(jié)構(gòu)(File Logical Structure)。 (2) 文件的物理結(jié)構(gòu)， 又

10、稱為文件的存儲結(jié)構(gòu)， 是指文件在外存上的存儲組織形式。 第六章 文件管理 6.2.1 文件邏輯結(jié)構(gòu)的類型文件邏輯結(jié)構(gòu)的類型 1. 有結(jié)構(gòu)文件有結(jié)構(gòu)文件(1) 定長記錄。 (2) 變長記錄。 (2) 順序文件。 (2) 索引文件。 (3) 索引順序文件。 第六章 文件管理 2. 無結(jié)構(gòu)文件無結(jié)構(gòu)文件 如果說大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫，是采用有結(jié)構(gòu)的文件形式的話，則大量的源程序、 可執(zhí)行文件、 庫函數(shù)等， 所采用的就是無結(jié)構(gòu)的文件形式，即流式文件。 其長度以字節(jié)為單位。對流式文件的訪問，則是采用讀寫指針來指出下一個要訪問的字符?？梢园蚜魇轿募醋魇怯涗浭轿募囊粋€特例。在UNIX系統(tǒng)中，所有的文件都被

11、看作是流式文件；即使是有結(jié)構(gòu)文件，也被視為流式文件；系統(tǒng)不對文件進行格式處理。 第六章 文件管理 6.2.2 順序文件順序文件1. 邏輯記錄的排序邏輯記錄的排序 第一種是串結(jié)構(gòu)， 各記錄之間的順序與關(guān)鍵字無關(guān)。 通常的辦法是由時間來決定，即按存入時間的先后排列， 最先存入的記錄作為第一個記錄，其次存入的為第二個記錄， 依此類推。 第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)鍵字(詞)排列?？梢园搓P(guān)鍵詞的長短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。 第六章 文件管理 2. 對順序文件對順序文件(Sequential File)的讀的讀/寫操作寫操作 R0R1R2R3RiLLLL

12、LL2L3L4LL(i1)LRptr(a) 定長記錄文件L0R0L1R1RiWptr(b) 變 長記錄文件Li00L0L01L1L0L12Li(Lk1)i1k0(Lk1)ik0圖 6-3 定長和變長記錄文件 第六章 文件管理 3. 順序文件的優(yōu)缺點順序文件的優(yōu)缺點 順序文件的最佳應(yīng)用場合，是在對諸記錄進行批量存取時， 即每次要讀或?qū)懸淮笈涗?。此時，對順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上， 并能有效地工作。 在交互應(yīng)用的場合，如果用戶(程序)要求查找或修改單個記錄，為此系統(tǒng)便要去逐個地查找諸記錄。 這時， 順序文件所表現(xiàn)出來的性能就可能很差， 尤其是當(dāng)

13、文件較大時， 情況更為嚴(yán)重。 例如，有一個含有104個記錄的順序文件，如果對它采用順序查找法去查找一個指定的記錄，則平均需要查找5103個記錄； 如果是可變長記錄的順序文件，則為查找一個記錄所需付出的開銷將更大，這就限制了順序文件的長度。 第六章 文件管理 順序文件的另一個缺點是， 如果想增加或刪除一個記錄， 都比較困難。 為了解決這一問題， 可以為順序文件配置一個運行記錄文件(Log File)或稱為事務(wù)文件(Transaction File)， 把試圖增加、 刪除或修改的信息記錄于其中， 規(guī)定每隔一定時間， 例如4小時，將運行記錄文件與原來的主文件加以合并， 產(chǎn)生一個按關(guān)鍵字排序的新文件。

14、 第六章 文件管理 6.2.3 索引文件索引文件 對于定長記錄文件，如果要查找第i個記錄， 可直接根據(jù)下式計算來獲得第i個記錄相對于第一個記錄首址的地址： Ai=iL 然而，對于可變長度記錄的文件，要查找其第i個記錄時，須首先計算出該記錄的首地址。為此，須順序地查找每個記錄，從中獲得相應(yīng)記錄的長度Li，然后才能按下式計算出第i個記錄的首址。假定在每個記錄前用一個字節(jié)指明該記錄的長度，則 10iiiiiLA第六章 文件管理 索引號0長度 m指針 ptrm01m1imi索引表R0R1Ri邏輯文件圖 6-4 索引文件的組織 第六章 文件管理 6.2.4 索引順序文件索引順序文件 鍵An QiBao

15、RongChen Lin邏輯地址姓 名An QiAn Kang其它屬性Bao Rong邏輯文件圖 6-5 索引順序文件 第六章 文件管理 6.2.5 直接文件和哈希文件直接文件和哈希文件 1. 直接文件直接文件 對于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換(Key to address transformation)。組織直接文件的關(guān)鍵， 在于用什么方法進行從記錄值到物理地址的轉(zhuǎn)換。 第六章 文件管理 2. 哈希哈希(Hash)文件文件 圖 6-6 Hash文件的邏輯結(jié)構(gòu)fHash

16、函數(shù)目錄表鍵值第六章 文件管理 6.3 外存分配方式外存分配方式 6.3.1 連續(xù)分配連續(xù)分配 1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目錄trf圖 6-7 磁盤空間的連續(xù)分配 第六章 文件管理 2. 連續(xù)分配的主要優(yōu)缺點連續(xù)分配的主要優(yōu)缺點 連續(xù)分配的主要優(yōu)點如下：(1) 順序訪問容易。 (2) 順序訪問速度快。 連續(xù)分配的主要缺點如下：(1) 要求有連續(xù)的存儲空間。 (2) 必須事先知道文件的長度。 第六章 文

17、件管理 6.3.2 鏈接分配鏈接分配1. 隱式鏈接隱式鏈接 圖 6-8 磁盤空間的鏈接式分配 25123056749101181314151217181916212223202526272429303128filestartendjeep925目錄101-116第六章 文件管理 2. 顯式鏈接顯式鏈接 圖 6-9 顯式鏈接結(jié)構(gòu) 012345物理塊號2FCBFAT0451第六章 文件管理 6EOF11105EOF0123456789FATFCB A4FCB B9圖 6-10 MS-DOS的文件物理結(jié)構(gòu)第六章 文件管理 6.3.3 索引分配索引分配 1. 單級索引分配單級索引分配 鏈接分配方式雖然

18、解決了連續(xù)分配方式所存在的問題， 但又出現(xiàn)了另外兩個問題， 即： (1) 不能支持高效的直接存取。要對一個較大的文件進行直接存取，須首先在FAT中順序地查找許多盤塊號。 (2) FAT需占用較大的內(nèi)存空間。 第六章 文件管理 圖 6-11 索引分配方式 123056749101181314151217181916212223202526272429303128countfile塊序號jeep19目錄9161102511119第六章 文件管理 2. 多級索引分配多級索引分配01210510625435635798510510625474035635711259853607401125主索引360

19、第二級索引磁盤空間圖 6-12 兩級索引分配第六章 文件管理 圖 6-13 混合索引方式 modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata第六章 文件管理 (1) 直接地址。 為了提高對文件的檢索速度， 在索引結(jié)點中可設(shè)置10個直接地址項， 即用iaddr(0)iaddr(9)來存放直接地址。 換言之，在這里的每項中所存放

20、的是該文件數(shù)據(jù)的盤塊的盤塊號。假如每個盤塊的大小為 4 KB，當(dāng)文件不大于40 KB時，便可直接從索引結(jié)點中讀出該文件的全部盤塊號。第六章 文件管理 (2) 一次間接地址。 對于大、 中型文件， 只采用直接地址是不現(xiàn)實的。 為此，可再利用索引結(jié)點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放1K個盤塊號， 因而允許文件長達(dá)4 MB。 第六章 文件管理 (3) 多次間接地址。 當(dāng)文件長度大于4 MB+40 KB時(一次間址與10個直接地址項)， 系統(tǒng)還須采用二次間址分配方

21、式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號。在采用二次間址方式時，文件最大長度可達(dá)4 GB。 同理，地址項iaddr(12)作為三次間接地址， 其所允許的文件最大長度可達(dá)4 TB。 第六章 文件管理 6.4 目目 錄錄 管管 理理 對目錄管理的要求如下：(1) 實現(xiàn)“按名存取”。 (2) 提高對目錄的檢索速度。 (3) 文件共享。 (4) 允許文件重名。 第六章 文件管理 6.4.1 文件控制塊和索引結(jié)點文件控制塊和索引結(jié)點 1. 文件控制塊文件控制塊 (1) 基本信息類 文件名 ； 文件物理位置 ；

22、文件邏輯結(jié)構(gòu) ； 文件的物理結(jié)構(gòu) (2) 存取控制信息類 (3) 使用信息類 圖 6-14 MS-DOS的文件控制塊 文件名擴展名屬性備用時間日期第一塊號盤塊數(shù)第六章 文件管理 2. 索引結(jié)點索引結(jié)點1) 索引結(jié)點的引入 圖 6-15 UNIX的文件目錄 文件名索引結(jié)點編號文件名1文件名2第六章 文件管理 2) 磁盤索引結(jié)點 (1) 文件主標(biāo)識符 (2) 文件類型 (3) 文件存取權(quán)限 (4) 文件物理地址 (5) 文件長度 (6) 文件連接計數(shù) (7) 文件存取時間 第六章 文件管理 3) 內(nèi)存索引結(jié)點 (1) 索引結(jié)點編號。 用于標(biāo)識內(nèi)存索引結(jié)點。(2) 狀態(tài)。 指示i結(jié)點是否上鎖或被修改

23、。(3) 訪問計數(shù)。 每當(dāng)有一進程要訪問此i結(jié)點時， 將該訪問計數(shù)加1， 訪問完再減1。(4) 文件所屬文件系統(tǒng)的邏輯設(shè)備號。(5) 鏈接指針。 設(shè)置有分別指向空閑鏈表和散列隊列的指針。 第六章 文件管理 6.4.2 目錄結(jié)構(gòu)目錄結(jié)構(gòu) 1. 單級目錄結(jié)構(gòu)單級目錄結(jié)構(gòu) 文件名物理地址文件說明狀態(tài)位文件名1文件名2圖 6-16 單級目錄 第六章 文件管理 單級目錄的優(yōu)點是簡單且能實現(xiàn)目錄管理的基本功能按名存取，但卻存在下述一些缺點： (1) 查找速度慢 (2) 不允許重名 (3) 不便于實現(xiàn)文件共享 第六章 文件管理 2. 兩級目錄兩級目錄 圖 6-17 兩級目錄結(jié)構(gòu) 用戶名WangZhangGa

24、o指向子目錄指針Wang用戶目錄AlphaTestAlphaTestReportTestZhang用戶目錄ReportTestGao用戶目錄BetaDeviceMisxBetaDeviceMisx第六章 文件管理 具有以下優(yōu)點：(1) 提高了檢索目錄的速度 (2) 在不同的用戶目錄中， 可以使用相同的文件名。 (3) 不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個共享文件 第六章 文件管理 3. 多級目錄結(jié)構(gòu)多級目錄結(jié)構(gòu) (1) 目錄結(jié)構(gòu) 圖 6-18 多級目錄結(jié)構(gòu) ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89第六章 文件

25、管理 (2) 路徑名。 在樹形目錄結(jié)構(gòu)中， 從根目錄到任何數(shù)據(jù)文件， 都只有一條惟一的通路。 在該路徑上從樹的根(即主目錄)開始， 把全部目錄文件名與數(shù)據(jù)文件名，依次地用“/”連接起來， 即構(gòu)成該數(shù)據(jù)文件的路徑名(path name)。 系統(tǒng)中的每一個文件都有惟一的路徑名。 例如，在圖 6-18 中用戶B為訪問文件J， 應(yīng)使用其路徑名/B/F/J來訪問。 第六章 文件管理 (3) 當(dāng)前目錄(Current Directory)。 當(dāng)一個文件系統(tǒng)含有許多級時，每訪問一個文件，都要使用從樹根開始直到樹葉(數(shù)據(jù)文件)為止的、包括各中間結(jié)點(目錄)名的全路徑名。 這是相當(dāng)麻煩的事，同時由于一個進程運行

26、時所訪問的文件，大多僅局限于某個范圍，因而非常不便。 基于這一點，可為每個進程設(shè)置一個“當(dāng)前目錄”，又稱為“工作目錄”。進程對各文件的訪問都相對于“當(dāng)前目錄”而進行。此時各文件所使用的路徑名， 只需從當(dāng)前目錄開始， 逐級經(jīng)過中間的目錄文件，最后到達(dá)要訪問的數(shù)據(jù)文件。把這一路徑上的全部目錄文件名與數(shù)據(jù)文件名用“/”連接形成路徑名，如用戶B的當(dāng)前目錄是F，則此時文件J的相對路徑名僅是J本身。 這樣， 把從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名，稱為相對路徑名(relative path name)；而把從樹根開始的路徑名稱為絕對路徑名(absolute path name)。 第六章 文件管理

27、 4. 增加和刪除目錄增加和刪除目錄 (1) 不刪除非空目錄。當(dāng)目錄(文件)不空時， 不能將其刪除，而為了刪除一個非空目錄，必須先刪除目錄中的所有文件，使之先成為空目錄， 后再予以刪除。如果目錄中還包含有子目錄，還必須采取遞歸調(diào)用方式來將其刪除， 在MS-DOS中就是采用這種刪除方式。 (2) 可刪除非空目錄。當(dāng)要刪除一目錄時，如果在該目錄中還包含有文件，則目錄中的所有文件和子目錄也同時被刪除。 第六章 文件管理 6.4.3 目錄查詢技術(shù)目錄查詢技術(shù) 1. 線性檢索法線性檢索法 圖 6-19 查找/usr/ast/mbox的步驟 第六章 文件管理 2. Hash方法方法 一種處理此“沖突”的有

28、效規(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. 空閑表法空閑表法 圖 6-2

29、0 空閑盤塊表 序號第一空閑盤塊號空閑盤塊數(shù)12429331554第六章 文件管理 (2) 存儲空間的分配與回收。 空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序地檢索空閑表的各表項， 直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進程)，同時修改空閑表。系統(tǒng)在對用戶所釋放的存儲空間進行回收時，也采取類似于內(nèi)存回收的方法， 即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并。 第六章 文件管理 2. 空閑鏈表法空閑鏈表法 (1) 空閑盤塊鏈。 (2) 空閑盤區(qū)鏈 第六章

30、文件管理 6.5.2 位示圖法位示圖法 1. 位示圖位示圖 圖 6-21 位示圖 第六章 文件管理 2. 盤塊的分配盤塊的分配 (1) 順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑時)。 (2) 將所找到的一個或一組二進制位， 轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進制位，位于位示的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算： b=n(i-1)+j式中， n代表每行的位數(shù)。 (3) 修改位示圖， 令mapi,j=1。 第六章 文件管理 3. 盤塊的回收盤塊的回收 (1) 將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。 轉(zhuǎn)換公式為： i=(b-1)DIV

31、 n+1 j=(b-1)MOD n+1 (2) 修改位示圖。 令map i,j=1。 第六章 文件管理 6.5.3 成組鏈接法成組鏈接法 1. 空閑盤塊的組織空閑盤塊的組織 1004003993013001003002992022012991004003992013019907999790179007899780179997901空閑盤塊號棧S.free019899圖 6-22 空閑盤塊的成組鏈接法 第六章 文件管理 2. 空閑盤塊的分配與回收空閑盤塊的分配與回收 當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時，須調(diào)用盤塊分配過程來完成。該過程首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊

32、號，將與之對應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。若該盤塊號已是棧底， 即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ù)目已達(dá)100時，

33、表示棧已滿，便將現(xiàn)有棧中的100個盤塊號， 記入新回收的盤塊中，再將其盤塊號作為新棧底。 第六章 文件管理 6.6 文件共享與文件保護文件共享與文件保護AABBBBBCCCCC根目錄?CCC圖 6-23 包含有共享文件的文件系統(tǒng) 第六章 文件管理 圖 6-24 基于索引結(jié)點的共享方式 Wang用戶文件目錄Test rLee用戶文件目錄Test rcount2文件物理地址索引結(jié)點Test第六章 文件管理 圖 6-25 進程B鏈接前后的情況 C的目錄ownerccount1鏈接前C的目錄ownerccount2建立鏈接后B的目錄B的目錄ownerccount1擁有者刪除文件后第六章 文件管理 6.

34、6.2 利用符號鏈實現(xiàn)文件共享利用符號鏈實現(xiàn)文件共享 在利用符號鏈方式實現(xiàn)文件共享時， 只是文件主才擁有指向其索引結(jié)點的指針；而共享該文件的其他用戶，則只有該文件的路徑名，并不擁有指向其索引結(jié)點的指針。這樣， 也就不會發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。 當(dāng)文件的擁有者把一個共享文件刪除后， 其他用戶試圖通過符號鏈去訪問一個已被刪除的共享文件時，會因系統(tǒng)找不到該文件而使訪問失敗，于是再將符號鏈刪除，此時不會產(chǎn)生任何影響。 第六章 文件管理 6.6.3 磁盤容錯技術(shù)磁盤容錯技術(shù) (1) 通過存取控制機制來防止由人為因素所造成的文件不安全性。 (2) 通過磁盤容錯技術(shù)， 來防止由磁盤

35、部分的故障所造成的文件不安全性。 (3) 通過“后備系統(tǒng)”來防止由自然因素所造成的不安全性。 第六章 文件管理 1. 第一級容錯技術(shù)第一級容錯技術(shù)SFT- 1) 雙份目錄和雙份文件分配表 在磁盤上存放的文件目錄和文件分配表FAT， 是文件管理所用的重要數(shù)據(jù)結(jié)構(gòu)。如果這些表格被破壞， 將導(dǎo)致磁盤上的部分或全部文件成為不可訪問的，因而也就等效于文件的丟失。為了防止這類情況發(fā)生，可在不同的磁盤上或在磁盤的不同區(qū)域中，分別建立(雙份)目錄表和FAT。 其中，一份被稱為主目錄及主FAT； 把另一份稱為備份目錄及備份FAT。 第六章 文件管理 2) 熱修復(fù)重定向和寫后讀校驗 (1) 熱修復(fù)重定向(Hot-

36、Redirection)。 (2) 寫后讀校驗(Read after write Verification)方式。 第六章 文件管理 2. 第二級容錯技術(shù)第二級容錯技術(shù)SFT- (1) 磁盤鏡像(Disk Mirroring)。 磁盤控制器主機通道磁盤驅(qū)動器圖 6-26 磁盤鏡像示意 第六章 文件管理 (2) 磁盤雙工磁盤雙工(Disk Duplexing)。 圖 6-27 磁盤雙工示意 主機磁盤控制器磁盤控制器通道通道磁盤驅(qū)動器第六章 文件管理 6.7 數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 6.7.1 事務(wù)事務(wù) 1. 事務(wù)的定義事務(wù)的定義 事務(wù)是用于訪問和修改各種數(shù)據(jù)項的一個程序單位。 事務(wù)也可以被

37、看作是一系列相關(guān)讀和寫操作。被訪問的數(shù)據(jù)可以分散地存放在同一文件的不同記錄中，也可放在多個文件中。只有對分布在不同位置的同一數(shù)據(jù)所進行的讀和寫(含修改)操作全部完成時，才能再以托付操作(Commit Operation)來終止事務(wù)。 只要有一個讀、寫或修改操作失敗，便須執(zhí)行夭折操作(Abort Operation)。讀或?qū)懖僮鞯氖】赡苁怯捎谶壿嬪e誤， 也可能是系統(tǒng)故障所導(dǎo)致的。 第六章 文件管理 2. 事務(wù)記錄事務(wù)記錄(Transaction Record) 事務(wù)名： 用于標(biāo)識該事務(wù)的惟一名字；數(shù)據(jù)項名： 它是被修改數(shù)據(jù)項的惟一名字；舊值： 修改前數(shù)據(jù)項的值；新值： 修改后數(shù)據(jù)項將具有的值。 第六章 文件管理 3. 恢復(fù)算法恢復(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)?；?， 即每隔一定時間便做一次