計(jì)算機(jī)操作系統(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 文件共享與文件保護(hù)文件共享與文件保護(hù) 6.7 6.7 數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 第六章 文件管理 6.1 文件和文件系統(tǒng)文件和文件系統(tǒng) 6.1.1 文件、記錄和數(shù)據(jù)項(xiàng)文件、記錄和數(shù)據(jù)項(xiàng) 1. 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) (1) 基本數(shù)據(jù)項(xiàng)。這是用于描述一個(gè)對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單

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

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

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

5、) 文件的建立時(shí)間。 文件記錄1記錄2記錄n數(shù)據(jù)項(xiàng)1數(shù)據(jù)項(xiàng)2數(shù)據(jù)項(xiàng)n圖 6-1 文件、 記錄和數(shù)據(jù)項(xiàng)之間的層次關(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)的功能大多是在這一層實(shí)現(xiàn)的，其中包括：對文件存儲空間的管理、對文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對文件讀和寫的管理，以及對文件的共享與保護(hù)等功能。 第六章

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) 截?cái)辔募?(6) 設(shè)置文件的讀/寫位置。 第六章 文件管理 2. 文件的文件的“打開打開”和和“關(guān)閉關(guān)閉”操作操作 所謂“打開”，是指系統(tǒng)將指名文件的屬性(包括

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

9、，可將這些調(diào)用分成若干類：最常用的一類是有關(guān)對文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者(文件主)、改變對文件的訪問權(quán)，以及查詢文件的狀態(tài)(包括文件類型、大小和擁有者以及對文件的訪問權(quán)等)；另一類是有關(guān)目錄的，如創(chuàng)建一個(gè)目錄，刪除一個(gè)目錄，改變當(dāng)前目錄和工作目錄等；此外，還有用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。 第六章 文件管理 6.2 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu) 對于任何一個(gè)文件，都存在著以下兩種形式的結(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é)為單位。對流式文件的訪問，則是采用讀寫指針來指出下一個(gè)要訪問的字符?？梢园蚜魇轿募醋魇怯涗浭轿募囊粋€(gè)特例。在UNIX系統(tǒng)中，所有的文件都被

11、看作是流式文件；即使是有結(jié)構(gòu)文件，也被視為流式文件；系統(tǒng)不對文件進(jìn)行格式處理。 第六章 文件管理 6.2.2 順序文件順序文件1. 邏輯記錄的排序邏輯記錄的排序 第一種是串結(jié)構(gòu)， 各記錄之間的順序與關(guān)鍵字無關(guān)。 通常的辦法是由時(shí)間來決定，即按存入時(shí)間的先后排列， 最先存入的記錄作為第一個(gè)記錄，其次存入的為第二個(gè)記錄， 依此類推。 第二種情況是順序結(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)缺點(diǎn)順序文件的優(yōu)缺點(diǎn) 順序文件的最佳應(yīng)用場合，是在對諸記錄進(jìn)行批量存取時(shí)， 即每次要讀或?qū)懸淮笈涗?。此時(shí)，對順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上， 并能有效地工作。 在交互應(yīng)用的場合，如果用戶(程序)要求查找或修改單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。 這時(shí)， 順序文件所表現(xiàn)出來的性能就可能很差， 尤其是當(dāng)

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

14、 第六章 文件管理 6.2.3 索引文件索引文件 對于定長記錄文件，如果要查找第i個(gè)記錄， 可直接根據(jù)下式計(jì)算來獲得第i個(gè)記錄相對于第一個(gè)記錄首址的地址： Ai=iL 然而，對于可變長度記錄的文件，要查找其第i個(gè)記錄時(shí)，須首先計(jì)算出該記錄的首地址。為此，須順序地查找每個(gè)記錄，從中獲得相應(yīng)記錄的長度Li，然后才能按下式計(jì)算出第i個(gè)記錄的首址。假定在每個(gè)記錄前用一個(gè)字節(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)鍵， 在于用什么方法進(jì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)缺點(diǎn)連續(xù)分配的主要優(yōu)缺點(diǎn) 連續(xù)分配的主要優(yōu)點(diǎn)如下：(1) 順序訪問容易。 (2) 順序訪問速度快。 連續(xù)分配的主要缺點(diǎn)如下：(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)了另外兩個(gè)問題， 即： (1) 不能支持高效的直接存取。要對一個(gè)較大的文件進(jìn)行直接存取，須首先在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é)點(diǎn)中可設(shè)置10個(gè)直接地址項(xiàng)， 即用iaddr(0)iaddr(9)來存放直接地址。 換言之，在這里的每項(xiàng)中所存放

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

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

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

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

24、o指向子目錄指針Wang用戶目錄AlphaTestAlphaTestReportTestZhang用戶目錄ReportTestGao用戶目錄BetaDeviceMisxBetaDeviceMisx第六章 文件管理 具有以下優(yōu)點(diǎn)：(1) 提高了檢索目錄的速度 (2) 在不同的用戶目錄中， 可以使用相同的文件名。 (3) 不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個(gè)共享文件 第六章 文件管理 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)中的每一個(gè)文件都有惟一的路徑名。 例如，在圖 6-18 中用戶B為訪問文件J， 應(yīng)使用其路徑名/B/F/J來訪問。 第六章 文件管理 (3) 當(dāng)前目錄(Current Directory)。 當(dāng)一個(gè)文件系統(tǒng)含有許多級時(shí)，每訪問一個(gè)文件，都要使用從樹根開始直到樹葉(數(shù)據(jù)文件)為止的、包括各中間結(jié)點(diǎn)(目錄)名的全路徑名。 這是相當(dāng)麻煩的事，同時(shí)由于一個(gè)進(jìn)程運(yùn)行

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

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

28、效規(guī)則是： (1) 在利用Hash法索引查找目錄時(shí)，如果目錄表中相應(yīng)的目錄項(xiàng)是空的，則表示系統(tǒng)中并無指定文件。 (2) 如果目錄項(xiàng)中的文件名與指定文件名相匹配， 則表示該目錄項(xiàng)正是所要尋找的文件所對應(yīng)的目錄項(xiàng)，故而可從中找到該文件所在的物理地址。 (3) 如果在目錄表的相應(yīng)目錄項(xiàng)中的文件名與指定文件名并不匹配，則表示發(fā)生了“沖突”，此時(shí)須將其Hash值再加上一個(gè)常數(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)建的文件分配空閑盤塊時(shí)，先順序地檢索空閑表的各表項(xiàng)， 直至找到第一個(gè)其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進(jìn)程)，同時(shí)修改空閑表。系統(tǒng)在對用戶所釋放的存儲空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法， 即要考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并。 第六章 文件管理 2. 空閑鏈表法空閑鏈表法 (1) 空閑盤塊鏈。 (2) 空閑盤區(qū)鏈 第六章

30、文件管理 6.5.2 位示圖法位示圖法 1. 位示圖位示圖 圖 6-21 位示圖 第六章 文件管理 2. 盤塊的分配盤塊的分配 (1) 順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。 (2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位，位于位示的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計(jì)算： 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)要為用戶分配文件所需的盤塊時(shí)，須調(diào)用盤塊分配過程來完成。該過程首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊

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

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

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

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

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

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