[計(jì)算機(jī)軟件及應(yīng)用]os操作系統(tǒng)ppt課件

1、第六章 文 件 管 理 6.1 6.1 文件和文件系統(tǒng)文件和文件系統(tǒng) 6.2 6.2 文件的邏輯構(gòu)造文件的邏輯構(gòu)造 6.3 6.3 外存分配方式外存分配方式 6.4 6.4 目錄管理目錄管理 6.5 6.5 文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理 6.6 6.6 文件共享與文件維護(hù)文件共享與文件維護(hù) 6.7 6.7 數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 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)。這是用于描畫(huà)一個(gè)對(duì)象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位， 即原子數(shù)據(jù)，又稱(chēng)為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。例如，用于描畫(huà)一個(gè)學(xué)生

2、的根本數(shù)據(jù)項(xiàng)有： 學(xué)號(hào)、 姓名、 年齡、 所在班級(jí)等。 6.1 文件和文件系統(tǒng) (2) 組合數(shù)據(jù)項(xiàng)。它是由假設(shè)干個(gè)根本數(shù)據(jù)項(xiàng)組成的，簡(jiǎn)稱(chē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ù)類(lèi)型。由于根本項(xiàng)僅是描畫(huà)某個(gè)對(duì)象的屬性，根據(jù)屬性的不同，需求用不同的數(shù)據(jù)類(lèi)型來(lái)描畫(huà)。例如，在描畫(huà)學(xué)生的學(xué)號(hào)時(shí)，應(yīng)運(yùn)用整數(shù)； 描畫(huà)學(xué)生的姓名那么應(yīng)運(yùn)用字符串(含漢字)；描畫(huà)性別時(shí)，可用邏輯變量或漢字?？梢?jiàn)，由數(shù)據(jù)項(xiàng)的名字和類(lèi)型兩者共同定義了一個(gè)數(shù)據(jù)項(xiàng)的“型。 而表征一個(gè)實(shí)體在數(shù)據(jù)項(xiàng)上的數(shù)據(jù)那么稱(chēng)

3、為“值。例如，學(xué)號(hào)/30211、姓名/王有年、性別/男等。 2. 記錄記錄 記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描畫(huà)一個(gè)對(duì)象在某記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描畫(huà)一個(gè)對(duì)象在某方面的屬性。一個(gè)記錄應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需求描畫(huà)方面的屬性。一個(gè)記錄應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需求描畫(huà)對(duì)象的哪個(gè)方面。而一個(gè)對(duì)象，由于他所處的環(huán)境不同可把對(duì)象的哪個(gè)方面。而一個(gè)對(duì)象，由于他所處的環(huán)境不同可把他作為不同的對(duì)象。他作為不同的對(duì)象。 例如，一個(gè)學(xué)生，當(dāng)把他作為班上的例如，一個(gè)學(xué)生，當(dāng)把他作為班上的一名學(xué)生時(shí)，一名學(xué)生時(shí)， 對(duì)他的描畫(huà)應(yīng)運(yùn)用學(xué)號(hào)、姓名、年齡及所在對(duì)他的描畫(huà)應(yīng)運(yùn)用學(xué)號(hào)、姓名、年齡及所在系班，也能夠還包

4、括他所學(xué)過(guò)的課程的稱(chēng)號(hào)、系班，也能夠還包括他所學(xué)過(guò)的課程的稱(chēng)號(hào)、 成果等數(shù)據(jù)成果等數(shù)據(jù)項(xiàng)。項(xiàng)。 但假設(shè)把學(xué)生作為一個(gè)醫(yī)療對(duì)象時(shí)，對(duì)他描畫(huà)的數(shù)據(jù)但假設(shè)把學(xué)生作為一個(gè)醫(yī)療對(duì)象時(shí)，對(duì)他描畫(huà)的數(shù)據(jù)項(xiàng)那么應(yīng)運(yùn)用諸如病歷號(hào)、項(xiàng)那么應(yīng)運(yùn)用諸如病歷號(hào)、 姓名、姓名、 性別、性別、 出生年月、出生年月、 身高、身高、 體重、體重、 血壓及病史等項(xiàng)。血壓及病史等項(xiàng)。 3. 文件文件 文件是指由創(chuàng)建者所定義的、 具有文件名的一組相關(guān)元素的集合，可分為有構(gòu)造文件和無(wú)構(gòu)造文件兩種。 在有構(gòu)造的文件中，文件由假設(shè)干個(gè)相關(guān)記錄組成；而無(wú)構(gòu)造文件那么被看成是一個(gè)字符流。文件在文件系統(tǒng)中是一個(gè)最大的數(shù)據(jù)單位，它描畫(huà)了一個(gè)對(duì)象集

5、。例如，可以將一個(gè)班的學(xué)生記錄作為一個(gè)文件。一個(gè)文件必需求有一個(gè)文件名， 它通常是由一串ASCII碼或(和)漢字構(gòu)成，名字的長(zhǎng)度因系統(tǒng)不同而異。如在有的系統(tǒng)中把名字規(guī)定為8個(gè)字符，而在有的系統(tǒng)中又規(guī)定可用14個(gè)字符。 屬性可以包括：文件類(lèi)型。(2) 文件長(zhǎng)度。 (3) 文件的物理位置。 (4) 文件的建立時(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 文件類(lèi)型和文件系統(tǒng)模型文件類(lèi)型和文件系統(tǒng)模型 1. 文件類(lèi)型文件類(lèi)型 按用途分類(lèi)系統(tǒng)文件。 (2) 用戶(hù)文件。 (3) 庫(kù)文件。 2) 按文件中數(shù)據(jù)的方式分類(lèi) 源文件。 (2) 目

6、的文件。 (3) 可執(zhí)行文件。 3) 按存取控制屬性分類(lèi) 只執(zhí)行文件。 (2) 只讀文件。 (3) 讀寫(xiě)文件。 2. 文件系統(tǒng)模型文件系統(tǒng)模型 圖 6-2 文件系統(tǒng)模型 1) 對(duì)象及其屬性 文件管理系統(tǒng)管理的對(duì)象有： 文件。 它作為文件管理的直接對(duì)象。 目錄。為了方便用戶(hù)對(duì)文件的存取和檢索，在文件系統(tǒng)中必需配置目錄。對(duì)目錄的組織和管理是方便用戶(hù)和提高對(duì)文件存取速度的關(guān)鍵。 磁盤(pán)(磁帶)存儲(chǔ)空間。 文件和目錄必定占用存儲(chǔ)空間，對(duì)這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對(duì)文件的存取速度。 2) 對(duì)對(duì)象支配和管理的軟件集合 這是文件管理系統(tǒng)的中心部分。文件系統(tǒng)的功能大多是在這一層實(shí)現(xiàn)

7、的，其中包括：對(duì)文件存儲(chǔ)空間的管理、對(duì)文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對(duì)文件讀和寫(xiě)的管理，以及對(duì)文件的共享與維護(hù)等功能。 3) 文件系統(tǒng)的接口 為方便用戶(hù)運(yùn)用文件系統(tǒng)，文件系統(tǒng)通常向用戶(hù)提供兩種類(lèi)型的接口： (1) 命令接口。這是指作為用戶(hù)與文件系統(tǒng)交互的接口。 用戶(hù)可經(jīng)過(guò)鍵盤(pán)終端鍵入命令，獲得文件系統(tǒng)的效力。 (2) 程序接口。這是指作為用戶(hù)程序與文件系統(tǒng)的接口。 用戶(hù)程序可經(jīng)過(guò)系統(tǒng)調(diào)用來(lái)獲得文件系統(tǒng)的效力。 6.1.3 文件操作文件操作 創(chuàng)建文件。 (2) 刪除文件。 (3) 讀文件。 (4) 寫(xiě)文件。 (5) 截?cái)辔募?(6) 設(shè)置文件的讀/寫(xiě)位置。 2. 文

8、件的文件的“翻開(kāi)和翻開(kāi)和“封鎖操作封鎖操作 所謂“翻開(kāi)，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存翻開(kāi)文件表的一個(gè)表目中，并將該表目的編號(hào)(或稱(chēng)為索引)前往給用戶(hù)。以后， 當(dāng)用戶(hù)再要求對(duì)該文件進(jìn)展相應(yīng)的操作時(shí)，便可利用系統(tǒng)所前往的索引號(hào)向系統(tǒng)提出操作懇求。系統(tǒng)這時(shí)便可直接利用該索引號(hào)到翻開(kāi)文件表中去查找，從而防止了對(duì)該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開(kāi)銷(xiāo)，也顯著地提高了對(duì)文件的操作速度。假設(shè)用戶(hù)已不再需求對(duì)該文件實(shí)施相應(yīng)的操作時(shí)，可利用“封鎖(close)系統(tǒng)調(diào)用來(lái)封鎖此文件，OS將會(huì)把該文件從翻開(kāi)文件表中的表目上刪除掉。 3. 其它文件操作其它文件操作

9、為了方便用戶(hù)運(yùn)用文件，通常，為了方便用戶(hù)運(yùn)用文件，通常，OS都提供了數(shù)條有關(guān)都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，可將這些調(diào)用分成假設(shè)干類(lèi)：最常用文件操作的系統(tǒng)調(diào)用，可將這些調(diào)用分成假設(shè)干類(lèi)：最常用的一類(lèi)是有關(guān)對(duì)文件屬性進(jìn)展操作的，即允許用戶(hù)直接設(shè)置的一類(lèi)是有關(guān)對(duì)文件屬性進(jìn)展操作的，即允許用戶(hù)直接設(shè)置和獲得文件的屬性，如改動(dòng)已存文件的文件名、改動(dòng)文件的和獲得文件的屬性，如改動(dòng)已存文件的文件名、改動(dòng)文件的擁有者擁有者(文件主文件主)、改動(dòng)對(duì)文件的訪問(wèn)權(quán)，以及查詢(xún)文件的形、改動(dòng)對(duì)文件的訪問(wèn)權(quán)，以及查詢(xún)文件的形狀狀(包括文件類(lèi)型、大小和擁有者以及對(duì)文件的訪問(wèn)權(quán)等包括文件類(lèi)型、大小和擁有者以及對(duì)文件的訪

10、問(wèn)權(quán)等)；另一類(lèi)是有關(guān)目錄的，如創(chuàng)建一個(gè)目錄，刪除一個(gè)目錄，改另一類(lèi)是有關(guān)目錄的，如創(chuàng)建一個(gè)目錄，刪除一個(gè)目錄，改動(dòng)當(dāng)前目錄和任務(wù)目錄等；此外，還有用于實(shí)現(xiàn)文件共享的動(dòng)當(dāng)前目錄和任務(wù)目錄等；此外，還有用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對(duì)文件系統(tǒng)進(jìn)展操作的系統(tǒng)調(diào)用等。系統(tǒng)調(diào)用和用于對(duì)文件系統(tǒng)進(jìn)展操作的系統(tǒng)調(diào)用等。 對(duì)于任何一個(gè)文件，都存在著以下兩種方式的構(gòu)造： 1文件的邏輯構(gòu)造(File Logical Structure)。 (2) 文件的物理構(gòu)造， 又稱(chēng)為文件的存儲(chǔ)構(gòu)造， 是指文件在外存上的存儲(chǔ)組織方式。 6.2 文件的邏輯構(gòu)造6.2.1 文件邏輯構(gòu)造的類(lèi)型文件邏輯構(gòu)造的類(lèi)型 有構(gòu)造文件有構(gòu)造

11、文件定長(zhǎng)記錄。定長(zhǎng)記錄。 (2) 變長(zhǎng)記錄。變長(zhǎng)記錄。 順序文件。順序文件。 (2) 索引文件。索引文件。 (3) 索引順序文件。索引順序文件。 2. 無(wú)構(gòu)造文件無(wú)構(gòu)造文件 假設(shè)說(shuō)大量的數(shù)據(jù)構(gòu)造和數(shù)據(jù)庫(kù)，是采用有構(gòu)造的文假設(shè)說(shuō)大量的數(shù)據(jù)構(gòu)造和數(shù)據(jù)庫(kù)，是采用有構(gòu)造的文件方式的話，那么大量的源程序、件方式的話，那么大量的源程序、 可執(zhí)行文件、可執(zhí)行文件、 庫(kù)函數(shù)庫(kù)函數(shù)等，等， 所采用的就是無(wú)構(gòu)造的文件方式，即流式文件。所采用的就是無(wú)構(gòu)造的文件方式，即流式文件。 其其長(zhǎng)度以字節(jié)為單位。對(duì)流式文件的訪問(wèn)，那么是采用讀寫(xiě)長(zhǎng)度以字節(jié)為單位。對(duì)流式文件的訪問(wèn)，那么是采用讀寫(xiě)指針來(lái)指出下一個(gè)要訪問(wèn)的字符。可以

12、把流式文件看作是指針來(lái)指出下一個(gè)要訪問(wèn)的字符。可以把流式文件看作是記錄式文件的一個(gè)特例。在記錄式文件的一個(gè)特例。在UNIX系統(tǒng)中，一切的文件都系統(tǒng)中，一切的文件都被看作是流式文件；即使是有構(gòu)造文件，也被視為流式文被看作是流式文件；即使是有構(gòu)造文件，也被視為流式文件；系統(tǒng)不對(duì)文件進(jìn)展格式處置。件；系統(tǒng)不對(duì)文件進(jìn)展格式處置。 6.2.2 順序文件順序文件1. 邏輯記錄的排序邏輯記錄的排序 第一種是串構(gòu)造， 各記錄之間的順序與關(guān)鍵字無(wú)關(guān)。 通常的方法是由時(shí)間來(lái)決議，即按存入時(shí)間的先后陳列， 最先存入的記錄作為第一個(gè)記錄，其次存入的為第二個(gè)記錄， 依此類(lèi)推。 第二種情況是順序構(gòu)造，指文件中的一切記錄按

13、關(guān)鍵字(詞)陳列?？梢园搓P(guān)鍵詞的長(zhǎng)短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。 2. 對(duì)順序文件對(duì)順序文件(Sequential File)的讀的讀/寫(xiě)操作寫(xiě)操作 R0R1R2R3RiLLLLLL2L3L4LL(i1)LRptr(a) 定長(zhǎng)記錄文件L0R0L1R1RiWptr(b) 變 長(zhǎng)記錄文件Li00L0L01L1L0L12Li(Lk1)i1k0(Lk1)ik0圖 6-3 定長(zhǎng)和變長(zhǎng)記錄文件 3. 順序文件的優(yōu)缺陷順序文件的優(yōu)缺陷 順序文件的最正確運(yùn)用場(chǎng)所，是在對(duì)諸記錄進(jìn)展批量存取時(shí)， 即每次要讀或?qū)懸淮笈涗洝４藭r(shí)，對(duì)順序文件的存取效率是一切邏輯文件中最高的；此外，也只需

14、順序文件才干存儲(chǔ)在磁帶上， 并能有效地任務(wù)。 在交互運(yùn)用的場(chǎng)所，假設(shè)用戶(hù)(程序)要求查找或修正單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。 這時(shí)， 順序文件所表現(xiàn)出來(lái)的性能就能夠很差， 尤其是當(dāng)文件較大時(shí)， 情況更為嚴(yán)重。 例如，有一個(gè)含有104個(gè)記錄的順序文件，假設(shè)對(duì)它采用順序查找法去查找一個(gè)指定的記錄，那么平均需求查找5103個(gè)記錄； 假設(shè)是可變長(zhǎng)記錄的順序文件，那么為查找一個(gè)記錄所需付出的開(kāi)銷(xiāo)將更大，這就限制了順序文件的長(zhǎng)度。 順序文件的另一個(gè)缺陷是， 假設(shè)想添加或刪除一個(gè)記錄， 都比較困難。 為理處理這一問(wèn)題， 可以為順序文件配置一個(gè)運(yùn)轉(zhuǎn)記錄文件(Log File)或稱(chēng)為事務(wù)文件(Tra

15、nsaction File)， 把試圖添加、 刪除或修正的信息記錄于其中， 規(guī)定每隔一定時(shí)間， 例如4小時(shí)，將運(yùn)轉(zhuǎn)記錄文件與原來(lái)的主文件加以合并， 產(chǎn)生一個(gè)按關(guān)鍵字排序的新文件。 6.2.3 索引文件索引文件 對(duì)于定長(zhǎng)記錄文件，假設(shè)要查找第i個(gè)記錄， 可直接根據(jù)下式計(jì)算來(lái)獲得第i個(gè)記錄相對(duì)于第一個(gè)記錄首址的地址： Ai=iL 然而，對(duì)于可變長(zhǎng)度記錄的文件，要查找其第i個(gè)記錄時(shí)，須首先計(jì)算出該記錄的首地址。為此，須順序地查找每個(gè)記錄，從中獲得相應(yīng)記錄的長(zhǎng)度Li，然后才干按下式計(jì)算出第i個(gè)記錄的首址。假定在每個(gè)記錄前用一個(gè)字節(jié)指明該記錄的長(zhǎng)度，那么 10iiiiiLA索引號(hào)0長(zhǎng)度 m指針 ptrm

16、01m1imi索引表R0R1Ri邏輯文件圖 6-4 索引文件的組織 6.2.4 索引順序文件索引順序文件 鍵An QiBao RongChen Lin邏輯地址姓 名An QiAn Kang其它屬性Bao Rong邏輯文件圖 6-5 索引順序文件 6.2.5 直接文件和哈希文件直接文件和哈希文件 1. 直接文件直接文件 對(duì)于直接文件，那么可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決議了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱(chēng)為鍵值轉(zhuǎn)換(Key to address transformation)。組織直接文件的關(guān)鍵， 在于用什么方法進(jìn)展從記錄值到物理地

17、址的轉(zhuǎn)換。 2. 哈希哈希(Hash)文件文件 圖 6-6 Hash文件的邏輯構(gòu)造fHash函數(shù)目錄表鍵值1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目錄trf6.3.1 延續(xù)分配延續(xù)分配 圖 6-7 磁盤(pán)空間的延續(xù)分配 6.3 外存分配方式 2. 延續(xù)分配的主要優(yōu)缺陷延續(xù)分配的主要優(yōu)缺陷 延續(xù)分配的主要優(yōu)點(diǎn)如下：順序訪問(wèn)容易。 (2) 順序訪問(wèn)速度快。 延續(xù)分配的主要缺陷如下：要求有延續(xù)的存儲(chǔ)空間。 (2) 必需事先

18、知道文件的長(zhǎng)度。 6.3.2 鏈接分配鏈接分配1. 隱式鏈接隱式鏈接 圖 6-8 磁盤(pán)空間的鏈接式分配 25123056749101181314151217181916212223202526272429303128filestartendjeep925目錄101-1162. 顯式鏈接顯式鏈接 圖 6-9 顯式鏈接構(gòu)造 012345物理塊號(hào)2FCBFAT04516EOF11105EOF0123456789FATFCB A4FCB B9圖 6-10 MS-DOS的文件物理構(gòu)造6.3.3 索引分配索引分配 1. 單級(jí)索引分配單級(jí)索引分配 鏈接分配方式雖然處理了延續(xù)分配方式所存在的問(wèn)題，鏈接分配方式

19、雖然處理了延續(xù)分配方式所存在的問(wèn)題， 但又出現(xiàn)了另外兩個(gè)問(wèn)題，但又出現(xiàn)了另外兩個(gè)問(wèn)題， 即：即： (1) 不能支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)不能支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)展直接存取，須首先在展直接存取，須首先在FAT中順序地查找許多盤(pán)塊號(hào)。中順序地查找許多盤(pán)塊號(hào)。 (2) FAT需占用較大的內(nèi)存空間。需占用較大的內(nèi)存空間。 圖 6-11 索引分配方式 123056749101181314151217181916212223202526272429303128countfile塊序號(hào)jeep19目錄91611025111192. 多級(jí)索引分配多級(jí)索引分配012105106

20、25435635798510510625474035635711259853607401125主索引360第二級(jí)索引磁盤(pán)空間圖 6-12 兩級(jí)索引分配圖 6-13 混合索引方式 modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata (1) 直接地址。 為了提高對(duì)文件的檢索速度， 在索引結(jié)點(diǎn)中可設(shè)置10個(gè)直接地址項(xiàng)， 即用iad

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

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

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

24、計(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.2 目錄構(gòu)造目錄構(gòu)造 1. 單級(jí)目錄構(gòu)造單級(jí)目錄構(gòu)造 文件名物理地址文件說(shuō)明狀態(tài)位文件名1文件名2圖 6-16 單級(jí)目錄 單級(jí)目錄的優(yōu)點(diǎn)是簡(jiǎn)單且能實(shí)現(xiàn)目錄管理的根本功能按名存取，但卻存在下述一些缺陷： (1) 查找速度慢 (2) 不允許重名 (3) 不便于實(shí)現(xiàn)文件共享 2. 兩級(jí)目錄兩級(jí)目錄 圖 6-17 兩級(jí)目錄構(gòu)造 用戶(hù)名WangZhangGao指向子目錄指針Wang用戶(hù)目錄AlphaTestAlphaTest

25、ReportTestZhang用戶(hù)目錄ReportTestGao用戶(hù)目錄BetaDeviceMisxBetaDeviceMisx具有以下優(yōu)點(diǎn)：提高了檢索目錄的速度 (2) 在不同的用戶(hù)目錄中， 可以運(yùn)用一樣的文件名。 (3) 不同用戶(hù)還可運(yùn)用不同的文件名來(lái)訪問(wèn)系統(tǒng)中的同一個(gè)共享文件 ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a893. 多級(jí)目錄構(gòu)造多級(jí)目錄構(gòu)造 (1) 目錄構(gòu)造 圖 6-18 多級(jí)目錄構(gòu)造 (2) 途徑名。 在樹(shù)形目錄構(gòu)造中， 從根目錄到任何數(shù)據(jù)文件， 都只需一條獨(dú)一的通路。 在該途徑上從樹(shù)的根(即主目錄)開(kāi)場(chǎng)，

26、 把全部目錄文件名與數(shù)據(jù)文件名，依次地用“/銜接起來(lái)， 即構(gòu)成該數(shù)據(jù)文件的途徑名(path name)。 系統(tǒng)中的每一個(gè)文件都有獨(dú)一的途徑名。 例如，在圖 6-18 中用戶(hù)B為訪問(wèn)文件J， 應(yīng)運(yùn)用其途徑名/B/F/J來(lái)訪問(wèn)。 (3) 當(dāng)前目錄(Current Directory)。 當(dāng)一個(gè)文件系統(tǒng)含有許多級(jí)時(shí)，每訪問(wèn)一個(gè)文件，都要運(yùn)用從樹(shù)根開(kāi)場(chǎng)直到樹(shù)葉(數(shù)據(jù)文件)為止的、包括各中間結(jié)點(diǎn)(目錄)名的全途徑名。 這是相當(dāng)費(fèi)事的事，同時(shí)由于一個(gè)進(jìn)程運(yùn)轉(zhuǎn)時(shí)所訪問(wèn)的文件，大多僅局限于某個(gè)范圍，因此非常不便。 基于這一點(diǎn)，可為每個(gè)進(jìn)程設(shè)置一個(gè)“當(dāng)前目錄，又稱(chēng)為“任務(wù)目錄。進(jìn)程對(duì)各文件的訪問(wèn)都相對(duì)于“當(dāng)前目

27、錄而進(jìn)展。此時(shí)各文件所運(yùn)用的途徑名， 只需從當(dāng)前目錄開(kāi)場(chǎng)， 逐級(jí)經(jīng)過(guò)中間的目錄文件，最后到達(dá)要訪問(wèn)的數(shù)據(jù)文件。把這一途徑上的全部目錄文件名與數(shù)據(jù)文件名用“/銜接構(gòu)成途徑名，如用戶(hù)B的當(dāng)前目錄是F，那么此時(shí)文件J的相對(duì)途徑名僅是J本身。 這樣， 把從當(dāng)前目錄開(kāi)場(chǎng)直到數(shù)據(jù)文件為止所構(gòu)成的途徑名，稱(chēng)為相對(duì)途徑名(relative path name)；而把從樹(shù)根開(kāi)場(chǎng)的途徑稱(chēng)號(hào)為絕對(duì)途徑名(absolute path name)。 4. 添加和刪除目錄添加和刪除目錄 (1) 不刪除非空目錄。當(dāng)目錄(文件)不空時(shí)， 不能將其刪除，而為了刪除一個(gè)非空目錄，必需先刪除目錄中的一切文件，使之先成為空目錄， 后

28、再予以刪除。假設(shè)目錄中還包含有子目錄，還必需采取遞歸調(diào)用方式來(lái)將其刪除， 在MS-DOS中就是采用這種刪除方式。 (2) 可刪除非空目錄。當(dāng)要?jiǎng)h除一目錄時(shí)，假設(shè)在該目錄中還包含有文件，那么目錄中的一切文件和子目錄也同時(shí)被刪除。 6.4.3 目錄查詢(xún)技術(shù)目錄查詢(xún)技術(shù) 1. 線性檢索法線性檢索法 圖 6-19 查找/usr/ast/mbox的步驟 2. Hash方法方法 一種處置此“沖突的有效規(guī)那么是： (1) 在利用Hash法索引查找目錄時(shí)，假設(shè)目錄表中相應(yīng)的目錄項(xiàng)是空的，那么表示系統(tǒng)中并無(wú)指定文件。 (2) 假設(shè)目錄項(xiàng)中的文件名與指定文件名相匹配， 那么表示該目錄項(xiàng)正是所要尋覓的文件所對(duì)應(yīng)的目

29、錄項(xiàng)，故而可從中找到該文件所在的物理地址。 (3) 假設(shè)在目錄表的相應(yīng)目錄項(xiàng)中的文件名與指定文件名并不匹配，那么表示發(fā)生了“沖突，此時(shí)須將其Hash值再加上一個(gè)常數(shù)(該常數(shù)應(yīng)與目錄的長(zhǎng)度值互質(zhì))，構(gòu)成新的索引值， 再前往到第一步重新開(kāi)場(chǎng)查找。 6.5.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法 1. 空閑表法空閑表法 圖 6-20 空閑盤(pán)塊表 序號(hào)第一空閑盤(pán)塊號(hào)空閑盤(pán)塊數(shù)124293315546.5 文件存儲(chǔ)空間的管理 (2) 存儲(chǔ)空間的分配與回收。 空閑盤(pán)區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類(lèi)似，同樣是采用初次順應(yīng)算法、循環(huán)初次順應(yīng)算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤(pán)塊時(shí)，先順序地檢索空閑表

30、的各表項(xiàng)， 直至找到第一個(gè)其大小能滿足要求的空閑區(qū)，再將該盤(pán)區(qū)分配給用戶(hù)(進(jìn)程)，同時(shí)修正空閑表。系統(tǒng)在對(duì)用戶(hù)所釋放的存儲(chǔ)空間進(jìn)展回收時(shí)，也采取類(lèi)似于內(nèi)存回收的方法， 即要思索回收區(qū)能否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對(duì)相鄰接者應(yīng)予以合并。 2. 空閑鏈表法空閑鏈表法 空閑盤(pán)塊鏈。 (2) 空閑盤(pán)區(qū)鏈 6.5.2 位示圖法位示圖法 1. 位示圖位示圖 圖 6-21 位示圖 2. 盤(pán)塊的分配盤(pán)塊的分配 (1) 順序掃描位示圖，從中找出一個(gè)或一組其值為“0的二進(jìn)制位(“0表示空閑時(shí))。 (2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)的盤(pán)塊號(hào)。假定找到的其值為“0的二進(jìn)制位，位于位示的第

31、i行、第j列，那么其相應(yīng)的盤(pán)塊號(hào)應(yīng)按下式計(jì)算： b=n(i-1)+j式中， n代表每行的位數(shù)。 (3) 修正位示圖， 令mapi,j=1。 3. 盤(pán)塊的回收盤(pán)塊的回收 (1) 將回收盤(pán)塊的盤(pán)塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。 轉(zhuǎn)換公式為： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修正位示圖。 令map i,j=1。 6.5.3 成組鏈接法成組鏈接法 1. 空閑盤(pán)塊的組織空閑盤(pán)塊的組織 1004003993013001003002992022012991004003992013019907999790179007899780179997901空閑盤(pán)塊號(hào)棧S.free01

32、9899圖 6-22 空閑盤(pán)塊的成組鏈接法 2. 空閑盤(pán)塊的分配與回收空閑盤(pán)塊的分配與回收 當(dāng)系統(tǒng)要為用戶(hù)分配文件所需的盤(pán)塊時(shí)，須調(diào)用盤(pán)塊分當(dāng)系統(tǒng)要為用戶(hù)分配文件所需的盤(pán)塊時(shí)，須調(diào)用盤(pán)塊分配過(guò)程來(lái)完成。該過(guò)程首先檢查空閑盤(pán)塊號(hào)棧能否上鎖，如配過(guò)程來(lái)完成。該過(guò)程首先檢查空閑盤(pán)塊號(hào)棧能否上鎖，如未上鎖，便從棧頂取出一空閑盤(pán)塊號(hào)，將與之對(duì)應(yīng)的盤(pán)塊分未上鎖，便從棧頂取出一空閑盤(pán)塊號(hào)，將與之對(duì)應(yīng)的盤(pán)塊分配給用戶(hù)，然后將棧頂指針下移一格。假設(shè)該盤(pán)塊號(hào)已是棧配給用戶(hù)，然后將棧頂指針下移一格。假設(shè)該盤(pán)塊號(hào)已是棧底，底， 即即S.free(0)，這是當(dāng)前棧中最后一個(gè)可分配的盤(pán)塊號(hào)。，這是當(dāng)前棧中最后一個(gè)可分配的

33、盤(pán)塊號(hào)。由于在該盤(pán)塊號(hào)所對(duì)應(yīng)的盤(pán)塊中記有下一組可用的盤(pán)塊號(hào)，由于在該盤(pán)塊號(hào)所對(duì)應(yīng)的盤(pán)塊中記有下一組可用的盤(pán)塊號(hào)，因此，因此， 須調(diào)用磁盤(pán)讀過(guò)程，將棧底盤(pán)塊號(hào)所對(duì)應(yīng)盤(pán)塊的內(nèi)須調(diào)用磁盤(pán)讀過(guò)程，將棧底盤(pán)塊號(hào)所對(duì)應(yīng)盤(pán)塊的內(nèi)容讀入棧中，作為新的盤(pán)塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的容讀入棧中，作為新的盤(pán)塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的盤(pán)塊分配出去盤(pán)塊分配出去(其中的有用數(shù)據(jù)已讀入棧中其中的有用數(shù)據(jù)已讀入棧中)。 然后，再分配然后，再分配一相應(yīng)的緩沖區(qū)一相應(yīng)的緩沖區(qū)(作為該盤(pán)塊的緩沖區(qū)作為該盤(pán)塊的緩沖區(qū))。最后，把棧中的空。最后，把棧中的空閑盤(pán)塊數(shù)減閑盤(pán)塊數(shù)減1并前往。并前往。 在系統(tǒng)回收空閑盤(pán)塊時(shí)，須調(diào)用盤(pán)塊回

34、收過(guò)程進(jìn)展回收。它是將回收盤(pán)塊的盤(pán)塊號(hào)記入空閑盤(pán)塊號(hào)棧的頂部，并執(zhí)行空閑盤(pán)塊數(shù)加1操作。當(dāng)棧中空閑盤(pán)塊號(hào)數(shù)目已達(dá)100時(shí)， 表示棧已滿，便將現(xiàn)有棧中的100個(gè)盤(pán)塊號(hào)， 記入新回收的盤(pán)塊中，再將其盤(pán)塊號(hào)作為新棧底。 文件卷 磁盤(pán)分區(qū)(partition)：通常把一個(gè)物理磁盤(pán)的存儲(chǔ)空間劃分為幾個(gè)相互獨(dú)立的部分，稱(chēng)為分區(qū)。一個(gè)分區(qū)的參數(shù)包括：磁盤(pán)參數(shù)如每道扇區(qū)數(shù)和磁頭數(shù)，分區(qū)的起始和終了柱面等。 文件卷(volume)：或稱(chēng)為邏輯驅(qū)動(dòng)器(logical drive)。在同一個(gè)文件卷中運(yùn)用同一份管理數(shù)據(jù)進(jìn)展文件分配和外存空閑空間管理，而在不同的文件卷中運(yùn)用相互獨(dú)立的管理數(shù)據(jù)。 一個(gè)文件不能分散存放在多

35、個(gè)文件卷中，其最大長(zhǎng)度不超越所在文件卷的容量。 通常一個(gè)文件卷只能存放在一個(gè)物理外設(shè)上并不絕對(duì)，如一個(gè)磁盤(pán)分區(qū)或一盤(pán)磁帶。 格式化(format)：在一個(gè)文件卷上建立文件系統(tǒng)，即： 建立并初始化用于進(jìn)展文件分配和外存空閑空間管理的管理數(shù)據(jù)。 通常，進(jìn)展格式化操作使得一個(gè)文件卷上原有的文件都被刪除。 擴(kuò)展文件卷集(extended volume set)：一個(gè)文件卷由一個(gè)或幾個(gè)磁盤(pán)上的多個(gè)磁盤(pán)分區(qū)依次銜接組成。可以包容長(zhǎng)度大于磁盤(pán)分區(qū)容量的文件。 實(shí)例：Windows NT中的擴(kuò)展文件卷集。 磁盤(pán)交叉存儲(chǔ)(disk interleaving)：將一個(gè)文件卷的存儲(chǔ)塊依次分散在多個(gè)磁盤(pán)上。如4個(gè)磁盤(pán)

36、，那么磁盤(pán)0上是文件卷塊0, 4, 8, ，磁盤(pán)1上是文件卷塊1, 5, 9, 。 優(yōu)點(diǎn)：提高I/O效率。假設(shè)需求訪問(wèn)一個(gè)文件的多個(gè)存儲(chǔ)塊，而它們分散在多個(gè)磁盤(pán)上，那么可以并發(fā)地向多個(gè)磁盤(pán)發(fā)出懇求，并可在此根底上提供文件系統(tǒng)的容錯(cuò)功能。關(guān)鍵：磁盤(pán)訪問(wèn)時(shí)間大部分由旋轉(zhuǎn)等待時(shí)間組成。 需求相應(yīng)硬件設(shè)備：如多個(gè)硬盤(pán)銜接在同一個(gè)或不同的SCSI接口上，或者兩個(gè)硬盤(pán)銜接在一個(gè)或不同的IDE接口上兩個(gè)硬盤(pán)銜接在同一個(gè)IDE接口上，不能提高I/O效率 實(shí)例：Windows NT中的條帶卷(stripe set)，每個(gè)文件卷塊的大小是64KB。 類(lèi)似例子：在虛擬存儲(chǔ)器中建立多個(gè)交換區(qū)，分散在多個(gè)磁盤(pán)上Disk

37、 0Disk 1Disk 2Disk 3Cycling WaitData TransfertRequestComplete多個(gè)磁盤(pán)上的交換區(qū)訪問(wèn)AABBBBBCCCCC根目錄?CCC圖 6-23 包含有共享文件的文件系統(tǒng) 6.6 文件共享與文件維護(hù)圖 6-24 基于索引結(jié)點(diǎn)的共享方式 Wang用戶(hù)文件目錄Test rLee用戶(hù)文件目錄Test rcount2文件物理地址索引結(jié)點(diǎn)Test圖 6-25 進(jìn)程B鏈接前后的情況 C的目錄ownerccount1鏈接前C的目錄ownerccount2建立鏈接后B的目錄B的目錄ownerccount1擁有者刪除文件后6.6.2 利用符號(hào)鏈實(shí)現(xiàn)文件共享利用符

38、號(hào)鏈實(shí)現(xiàn)文件共享 在利用符號(hào)鏈方式實(shí)現(xiàn)文件共享時(shí)， 只是文件主才擁有指向其索引結(jié)點(diǎn)的指針；而共享該文件的其他用戶(hù)，那么只需該文件的途徑名，并不擁有指向其索引結(jié)點(diǎn)的指針。這樣， 也就不會(huì)發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。 當(dāng)文件的擁有者把一個(gè)共享文件刪除后， 其他用戶(hù)試圖經(jīng)過(guò)符號(hào)鏈去訪問(wèn)一個(gè)已被刪除的共享文件時(shí)，會(huì)因系統(tǒng)找不到該文件而使訪問(wèn)失敗，于是再將符號(hào)鏈刪除，此時(shí)不會(huì)產(chǎn)生任何影響。 UNIX 文件別名的實(shí)現(xiàn) 基于索引結(jié)點(diǎn) 基于符號(hào)鏈接提供文件共享的方法有兩種：各用戶(hù)經(jīng)過(guò)獨(dú)一的共享文件的途徑名訪問(wèn)共享文件該方法的訪問(wèn)速度慢，適用于不經(jīng)常訪問(wèn)的文件共享，或利用多個(gè)目錄中的不同文

39、件名來(lái)描畫(huà)同一共享文件即文件別名，該方法的訪問(wèn)速度快，但會(huì)影響文件系統(tǒng)的樹(shù)狀構(gòu)造，適用于經(jīng)常訪問(wèn)的文件共享，同時(shí)存在一定的限制。文件別名的實(shí)現(xiàn)方法有以下兩種：1. 基于索引結(jié)點(diǎn)(index node)的文件別名 UNIX舉例：ln source target ; rm source那么該文件還存在，文件名為target； 限制：不能跨越不同文件卷；通常不適用于目錄在UNIX中只對(duì)超級(jí)用戶(hù)允許，否那么由樹(shù)狀變?yōu)榫W(wǎng)狀。也稱(chēng)為硬鏈接hard link；基于改良的多級(jí)目錄構(gòu)造，將目錄內(nèi)容分為兩部分：文件名和索引結(jié)點(diǎn)。前者包括文件名和索引結(jié)點(diǎn)編號(hào)，后者包括文件的其他內(nèi)容包括屬主和訪問(wèn)權(quán)限。經(jīng)過(guò)多個(gè)文件名

40、鏈接(link)到同一個(gè)索引結(jié)點(diǎn)，可建立同一個(gè)文件的多個(gè)彼此平等的別名。別名的數(shù)目記錄在索引結(jié)點(diǎn)的鏈接計(jì)數(shù)中，假設(shè)其減至0，那么文件被刪除。2. 基于符號(hào)鏈接(symbolic link, shortcut)的文件別名 UNIX舉例：ln -s a b ; rm a那么文件a不存在，b能被控制但無(wú)法訪問(wèn)。假設(shè)a是目錄，ln -s /user/a /tmp/b那么cd /tmp/b ; cd .是進(jìn)入目錄/user而不是/tmp； 缺陷：空間和時(shí)間開(kāi)銷(xiāo)更大。假設(shè)設(shè)置不當(dāng)，上下級(jí)目錄關(guān)系能夠會(huì)構(gòu)成環(huán)狀。它是一種特殊類(lèi)型的文件，其內(nèi)容是到另一個(gè)目錄或文件途徑的鏈接。建立符號(hào)鏈接文件，并不影響原文件，

41、實(shí)踐上它們各是一個(gè)文件。可以建立恣意的別名關(guān)系，甚至原文件是在其他計(jì)算機(jī)上。6.6.3 磁盤(pán)容錯(cuò)技術(shù)磁盤(pán)容錯(cuò)技術(shù) (1) 經(jīng)過(guò)存取控制機(jī)制來(lái)防止由人為要素所呵斥的文件不平安性。 (2) 經(jīng)過(guò)磁盤(pán)容錯(cuò)技術(shù)， 來(lái)防止由磁盤(pán)部分的缺點(diǎn)所呵斥的文件不平安性。 (3) 經(jīng)過(guò)“后備系統(tǒng)來(lái)防止由自然要素所呵斥的不平安性。 1. 第一級(jí)容錯(cuò)技術(shù)第一級(jí)容錯(cuò)技術(shù)SFT- 1) 雙份目錄和雙份文件分配表 在磁盤(pán)上存放的文件目錄和文件分配表FAT， 是文件管理所用的重要數(shù)據(jù)構(gòu)造。假設(shè)這些表格被破壞， 將導(dǎo)致磁盤(pán)上的部分或全部文件成為不可訪問(wèn)的，因此也就等效于文件的喪失。為了防止這類(lèi)情況發(fā)生，可在不同的磁盤(pán)上或在磁盤(pán)的

42、不同區(qū)域中，分別建立(雙份)目錄表和FAT。 其中，一份被稱(chēng)為主目錄及主FAT； 把另一份稱(chēng)為備份目錄及備份FAT。 2) 熱修復(fù)重定向和寫(xiě)后讀校驗(yàn) 熱修復(fù)重定向(Hot-Redirection)。 (2) 寫(xiě)后讀校驗(yàn)(Read after write Verification)方式。 2. 第二級(jí)容錯(cuò)技術(shù)第二級(jí)容錯(cuò)技術(shù)SFT- (1) 磁盤(pán)鏡像(Disk Mirroring)。 磁盤(pán)控制器主機(jī)通道磁盤(pán)驅(qū)動(dòng)器圖 6-26 磁盤(pán)鏡像表示 (2) 磁盤(pán)雙工磁盤(pán)雙工(Disk Duplexing)。 圖 6-27 磁盤(pán)雙工表示 主機(jī)磁盤(pán)控制器磁盤(pán)控制器通道通道磁盤(pán)驅(qū)動(dòng)器6.7.1 事務(wù)事務(wù) 1. 事

43、務(wù)的定義事務(wù)的定義 事務(wù)是用于訪問(wèn)和修正各種數(shù)據(jù)項(xiàng)的一個(gè)程序單位。事務(wù)是用于訪問(wèn)和修正各種數(shù)據(jù)項(xiàng)的一個(gè)程序單位。 事事務(wù)也可以被看作是一系列相關(guān)讀和寫(xiě)操作。被訪問(wèn)的數(shù)據(jù)可以務(wù)也可以被看作是一系列相關(guān)讀和寫(xiě)操作。被訪問(wèn)的數(shù)據(jù)可以分散地存放在同一文件的不同記錄中，也可放在多個(gè)文件中。分散地存放在同一文件的不同記錄中，也可放在多個(gè)文件中。只需對(duì)分布在不同位置的同一數(shù)據(jù)所進(jìn)展的讀和寫(xiě)只需對(duì)分布在不同位置的同一數(shù)據(jù)所進(jìn)展的讀和寫(xiě)(含修正含修正)操操作全部完成時(shí)，才干再以拜托操作作全部完成時(shí)，才干再以拜托操作(Commit Operation)來(lái)終止來(lái)終止事務(wù)。事務(wù)。 只需有一個(gè)讀、寫(xiě)或修正操作失敗，便須

44、執(zhí)行夭折操只需有一個(gè)讀、寫(xiě)或修正操作失敗，便須執(zhí)行夭折操作作(Abort Operation)。讀或?qū)懖僮鞯氖∧軌蚴怯捎谶壿嬪e(cuò)誤，。讀或?qū)懖僮鞯氖∧軌蚴怯捎谶壿嬪e(cuò)誤， 也能夠是系統(tǒng)缺點(diǎn)所導(dǎo)致的。也能夠是系統(tǒng)缺點(diǎn)所導(dǎo)致的。 6.7 數(shù)據(jù)一致性控制 2. 事務(wù)記錄事務(wù)記錄(Transaction Record) 事務(wù)名： 用于標(biāo)識(shí)該事務(wù)的獨(dú)一名字；數(shù)據(jù)項(xiàng)名： 它是被修正數(shù)據(jù)項(xiàng)的獨(dú)一名字；舊值： 修正前數(shù)據(jù)項(xiàng)的值；新值： 修正后數(shù)據(jù)項(xiàng)將具有的值。 3. 恢復(fù)算法恢復(fù)算法 恢復(fù)算法可利用以下兩個(gè)過(guò)程： (1) undoTi。該過(guò)程把一切被事務(wù)Ti修正正的數(shù)據(jù)，恢復(fù)為修正前的值。 (2) redoT

45、i。該過(guò)程能把一切被事務(wù)Ti修正正的數(shù)據(jù)，設(shè)置為新值。 假設(shè)系統(tǒng)發(fā)生缺點(diǎn)， 系統(tǒng)應(yīng)對(duì)以前所發(fā)生的事務(wù)進(jìn)展清理。 6.7.2 檢查點(diǎn)檢查點(diǎn) 1. 檢查點(diǎn)檢查點(diǎn)(Check Points)的作用的作用 引入檢查點(diǎn)的主要目的，是使對(duì)事務(wù)記錄表中事務(wù)記錄的清理任務(wù)經(jīng)常化， 即每隔一定時(shí)間便做一次下述任務(wù)： 首先是將駐留在易失性存儲(chǔ)器(內(nèi)存)中的當(dāng)前事務(wù)記錄表中的一切記錄，輸出到穩(wěn)定存儲(chǔ)器中；其次是將駐留在易失性存儲(chǔ)器中的一切已修正數(shù)據(jù)，輸出到穩(wěn)定存儲(chǔ)器中；然后是將事務(wù)記錄表中的檢查點(diǎn)記錄，輸出到穩(wěn)定存儲(chǔ)器中； 最后是每當(dāng)出現(xiàn)一個(gè)檢查點(diǎn)記錄時(shí)，系統(tǒng)便執(zhí)行上小節(jié)所引見(jiàn)的恢復(fù)操作，利用redo和undo過(guò)程

46、實(shí)現(xiàn)恢復(fù)功能。 2. 新的恢復(fù)算法新的恢復(fù)算法 恢復(fù)例程首先查找事務(wù)記錄表，確定在最近檢查點(diǎn)以前開(kāi)場(chǎng)執(zhí)行的最后的事務(wù)Ti。在找到這樣的事務(wù)后， 再前往去搜索事務(wù)記錄表，便可找到第一個(gè)檢查點(diǎn)記錄，恢復(fù)例程便從該檢查點(diǎn)開(kāi)場(chǎng)，前往搜索各個(gè)事務(wù)的記錄，并利用redo和undo過(guò)程對(duì)它們進(jìn)展處置。 假設(shè)把一切在事務(wù)Ti以后開(kāi)場(chǎng)執(zhí)行的事務(wù)表示為事務(wù)集T， 那么新的恢復(fù)操作要求是：對(duì)一切在T中的事務(wù)TK, 假設(shè)在事務(wù)記錄表中出現(xiàn)了TK拜托記錄，那么執(zhí)行redoTK操作； 反之，假設(shè)在事務(wù)記錄表中并未出現(xiàn)TK拜托記錄，那么執(zhí)行undoTK操作。6.7.3 并發(fā)控制并發(fā)控制 利用互斥鎖實(shí)現(xiàn)利用互斥鎖實(shí)現(xiàn)“順序性

47、順序性2. 利用互斥鎖和共享鎖實(shí)現(xiàn)順序性利用互斥鎖和共享鎖實(shí)現(xiàn)順序性 6.7.4 反復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問(wèn)題反復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問(wèn)題 1. 反復(fù)文件的一致性反復(fù)文件的一致性 圖 6-28 UNIX類(lèi)型的目錄 2. 盤(pán)塊號(hào)一致性的檢查盤(pán)塊號(hào)一致性的檢查 圖 6-29 檢查盤(pán)塊號(hào)一致性情況 圖 6-29 檢查盤(pán)塊號(hào)一致性情況 3. 鏈接數(shù)一致性檢查鏈接數(shù)一致性檢查 為每個(gè)盤(pán)塊建立一個(gè)表項(xiàng)，其中含有該索引結(jié)點(diǎn)號(hào)的計(jì)數(shù)值。 在進(jìn)展檢查時(shí)，從根目錄開(kāi)場(chǎng)查找，每當(dāng)在目錄中遇到該索引結(jié)點(diǎn)號(hào)時(shí)， 便在該計(jì)數(shù)器表中相應(yīng)文件的表項(xiàng)上加1。當(dāng)把一切目錄都檢查完后，便可將該計(jì)數(shù)器表中每個(gè)表項(xiàng)中的索引結(jié)點(diǎn)號(hào)計(jì)數(shù)值與該文件

48、索引結(jié)點(diǎn)中的鏈接計(jì)數(shù)count值加以比較， 假設(shè)兩者一致，表示是正確的；否那么，便是發(fā)生了鏈接數(shù)據(jù)不一致的錯(cuò)誤。 假設(shè)索引結(jié)點(diǎn)中的鏈接計(jì)數(shù)count值大于計(jì)數(shù)器表中相應(yīng)索引結(jié)點(diǎn)號(hào)的計(jì)數(shù)值，那么即使在一切共享此文件的用戶(hù)都不再運(yùn)用此文件時(shí)，其count值仍不為0，因此該文件不會(huì)被刪除。這種錯(cuò)誤的后果是使一些已無(wú)用戶(hù)需求的文件仍駐留在磁盤(pán)上，浪費(fèi)了存儲(chǔ)空間。處理的方法是用計(jì)數(shù)器表中的正確的計(jì)數(shù)值去為count重新賦值。 反之，假設(shè)出現(xiàn)count值小于計(jì)數(shù)器表中索引結(jié)點(diǎn)號(hào)計(jì)數(shù)值的情況時(shí)，就有潛在的危險(xiǎn)。假設(shè)有兩個(gè)用戶(hù)共享一個(gè)文件，但是count值仍為1， 這樣， 只需其中有一個(gè)用戶(hù)不再需求此文件時(shí)，

49、 count值就會(huì)減為0，從而使系統(tǒng)將此文件刪除， 并釋放其索引結(jié)點(diǎn)及文件所占用的盤(pán)塊，導(dǎo)致另一共享此文件的用戶(hù)所對(duì)應(yīng)的目錄項(xiàng)，指向了一個(gè)空索引結(jié)點(diǎn)，最終是使該用戶(hù)再無(wú)法訪問(wèn)此文件。假設(shè)該索引結(jié)點(diǎn)很快又被分配給其它文件，那么又會(huì)帶來(lái)潛在的危險(xiǎn)。 處理的方法是將count值置為正確值。 文件系統(tǒng)舉例1 MS DOS的文件系統(tǒng)2 Windows NT的文件系統(tǒng)3 UNIX的文件系統(tǒng)1 MS DOS的文件系統(tǒng)多級(jí)目錄，不支持文件別名，無(wú)用戶(hù)訪問(wèn)權(quán)限控制1. 磁盤(pán)文件卷構(gòu)造FAT 1FAT 2RootDirectoryData(File & Directory)BootRecordVolume Str

50、ucture in MS DOSSector #0N12N 文件卷(volume)信息：記錄在引導(dǎo)記錄的扇區(qū)中。包括：簇大小，根目錄項(xiàng)數(shù)目，F(xiàn)AT表大小，磁盤(pán)參數(shù)每道扇區(qū)數(shù)，磁頭數(shù)，文件卷中的扇區(qū)總數(shù)，簇編號(hào)長(zhǎng)度等 邏輯扇區(qū)號(hào)：三元組柱面號(hào)，磁頭號(hào)，扇區(qū)號(hào)一個(gè)文件卷中從0開(kāi)場(chǎng)對(duì)每個(gè)扇區(qū)編號(hào)，優(yōu)點(diǎn)：屏蔽了物理磁盤(pán)參數(shù)的不同 允許同時(shí)訪問(wèn)的文件卷數(shù)目上限可以由config.sys文件中的LASTDRIVE= 語(yǔ)句指定 簇(cluster)：由假設(shè)干個(gè)扇區(qū)組成。在一個(gè)文件卷中從0開(kāi)場(chǎng)對(duì)每個(gè)簇編號(hào)。 每個(gè)FAT表項(xiàng)所占位數(shù)是簇編號(hào)的位數(shù)，其值是以FAT12為例： 0：表示該簇空閑 FF7h：物理壞扇區(qū) FF8hFFFh：表示該簇是文件的最后一個(gè)簇 其他值：表示該簇被文件占用，而且表項(xiàng)中的值是文件下一個(gè)簇的編號(hào)。FAT表：兩個(gè)鏡像，互為備份。文件卷中的每個(gè)簇均對(duì)應(yīng)一個(gè)FAT表項(xiàng)，文件分配采用鏈?zhǔn)椒峙浞椒ā?目錄：是目錄項(xiàng)的順序文件(即大小一樣的排序記錄序列)，不對(duì)目錄項(xiàng)排序。 假設(shè)目錄中包含的文件數(shù)目較多，那么搜索效率低。 每個(gè)目錄項(xiàng)大小為32字