計(jì)算機(jī)操作系統(tǒng)_06文件和文件系統(tǒng)

1、第六章文 件 管 理 第六章文 件 管 理 6.1文件和文件系統(tǒng)文件和文件系統(tǒng)6.2文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)6.3外存分配方式外存分配方式6.4目錄管理目錄管理6.5文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理6.6文件共享與文件保護(hù)文件共享與文件保護(hù)6.7數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 第六章文 件 管 理 6.1文件和文件系統(tǒng)文件和文件系統(tǒng) 6.1.16.1.1文件、記錄和數(shù)據(jù)項(xiàng)文件、記錄和數(shù)據(jù)項(xiàng)1 1數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)在文件系統(tǒng)中，數(shù)據(jù)項(xiàng)是最低級(jí)的數(shù)據(jù)組織形式，可把它分成以下兩種類型:(1) 基本數(shù)據(jù)項(xiàng)。這是用于描述一個(gè)對(duì)象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱

2、為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。例如，用于描述一個(gè)學(xué)生的基本數(shù)據(jù)項(xiàng)有學(xué)號(hào)、姓名、年齡、所在班級(jí)等。 第六章文 件 管 理 (2) 組合數(shù)據(jù)項(xiàng)。它是由若干個(gè)基本數(shù)據(jù)項(xiàng)組成的，簡(jiǎn)稱組項(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è)對(duì)象的屬性，根據(jù)屬性的不同，需要用不同的數(shù)據(jù)類型來(lái)描述。例如，在描述學(xué)生的學(xué)號(hào)時(shí)，應(yīng)使用整數(shù)；描述學(xué)生的姓名則應(yīng)使用字符串(含漢字)；描述性別時(shí)，可用邏輯變量或漢字?？梢?jiàn)，由數(shù)據(jù)項(xiàng)的名字和類型兩者共同定義了一個(gè)數(shù)據(jù)項(xiàng)

3、的“型”。而表征一個(gè)實(shí)體在數(shù)據(jù)項(xiàng)上的數(shù)據(jù)則稱為“值”。例如，學(xué)號(hào)/30211、姓名/王有年、性別/男等。 第六章文 件 管 理 2 2記錄記錄記錄是一組相關(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í)，對(duì)他的描述應(yīng)使用學(xué)號(hào)、姓名、年齡及所在系班，也可能還包括他所學(xué)過(guò)的課程的名稱、成績(jī)等數(shù)據(jù)項(xiàng)。但若把學(xué)生作為一個(gè)醫(yī)療對(duì)象時(shí)，對(duì)他描述的數(shù)據(jù)項(xiàng)則應(yīng)使用諸如病歷號(hào)、姓名、性別、出生年月、身高、體重、血壓及病史等項(xiàng)。 第六章文 件 管 理 在諸多記錄中

4、，為了能惟一地標(biāo)識(shí)一個(gè)記錄，必須在一個(gè)記錄的各個(gè)數(shù)據(jù)項(xiàng)中，確定出一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)，把它們的集合稱為關(guān)鍵字(key)?；蛘哒f(shuō)，關(guān)鍵字是惟一能標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)。通常，只需用一個(gè)數(shù)據(jù)項(xiàng)作為關(guān)鍵字。例如，前面的病歷號(hào)或?qū)W號(hào)便可用來(lái)從諸多記錄中標(biāo)識(shí)出惟一的一個(gè)記錄。然而有時(shí)找不到這樣的數(shù)據(jù)項(xiàng)，只好把幾個(gè)數(shù)據(jù)項(xiàng)定為能在諸多記錄中惟一地標(biāo)識(shí)出某個(gè)記錄的關(guān)鍵字。 第六章文 件 管 理 3 3文件文件文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無(wú)結(jié)構(gòu)文件兩種。在有結(jié)構(gòu)的文件中，文件由若干個(gè)相關(guān)記錄組成；而無(wú)結(jié)構(gòu)文件則被看成是一個(gè)字符流。文件在文件系統(tǒng)中是一個(gè)最大的數(shù)據(jù)單位，它

5、描述了一個(gè)對(duì)象集。例如，可以將一個(gè)班的學(xué)生記錄作為一個(gè)文件。一個(gè)文件必須要有一個(gè)文件名，它通常是由一串ASCII碼或(和)漢字構(gòu)成的，名字的長(zhǎng)度因系統(tǒng)不同而異。如在有的系統(tǒng)中把名字規(guī)定為8個(gè)字符，而在有的系統(tǒng)中又規(guī)定可用14個(gè)字符。用戶利用文件名來(lái)訪問(wèn)文件。 第六章文 件 管 理 此外，文件應(yīng)具有自己的屬性，屬性可以包括：(1) 文件類型?？梢詮牟煌慕嵌葋?lái)規(guī)定文件的類型，如源文件、目標(biāo)文件及可執(zhí)行文件等。(2) 文件長(zhǎng)度。文件長(zhǎng)度指文件的當(dāng)前長(zhǎng)度，長(zhǎng)度的單位可以是字節(jié)、字或塊，也可能是最大允許的長(zhǎng)度。(3) 文件的物理位置。該項(xiàng)屬性通常是用于指示文件在哪一個(gè)設(shè)備上及在該設(shè)備的哪個(gè)位置的指針。

6、(4) 文件的建立時(shí)間。這是指文件最后一次的修改時(shí)間等。 第六章文 件 管 理 圖6-1文件、記錄和數(shù)據(jù)項(xiàng)之間的層次關(guān)系 文件記錄1記錄2記錄n數(shù)據(jù)項(xiàng)1數(shù)據(jù)項(xiàng)2數(shù)據(jù)項(xiàng)n第六章文 件 管 理 6.1.26.1.2文件類型和文件系統(tǒng)模型文件類型和文件系統(tǒng)模型1 1文件類型文件類型為了便于管理和控制文件而將文件分成若干種類型。由于不同系統(tǒng)對(duì)文件的管理方式不同，因而它們對(duì)文件的分類方法也有很大差異。為了方便系統(tǒng)和用戶了解文件的類型，在許多OS中都把文件類型作為擴(kuò)展名而綴在文件名的后面，在文件名和擴(kuò)展名之間用“.”號(hào)隔開(kāi)。下面是常用的幾種文件分類方法。 第六章文 件 管 理 1) 按用途分類根據(jù)文件的性

7、質(zhì)和用途的不同，可將文件分為三類:(1) 系統(tǒng)文件。這是指由系統(tǒng)軟件構(gòu)成的文件。大多數(shù)的系統(tǒng)文件只允許用戶調(diào)用，但不允許用戶去讀，更不允許修改；有的系統(tǒng)文件不直接對(duì)用戶開(kāi)放。(2) 用戶文件。指由用戶的源代碼、目標(biāo)文件、可執(zhí)行文件或數(shù)據(jù)等所構(gòu)成的文件。用戶將這些文件委托給系統(tǒng)保管。(3) 庫(kù)文件。這是由標(biāo)準(zhǔn)子例程及常用的例程等所構(gòu)成的文件。這類文件允許用戶調(diào)用，但不允許修改。 第六章文 件 管 理 2) 按文件中數(shù)據(jù)的形式分類按這種方式分類，也可把文件分為三類：(1) 源文件。這是指由源程序和數(shù)據(jù)構(gòu)成的文件。通常由終端或輸入設(shè)備輸入的源程序和數(shù)據(jù)所形成的文件都屬于源文件。它通常是由ASCII碼

8、或漢字所組成的。(2) 目標(biāo)文件。這是指把源程序經(jīng)過(guò)相應(yīng)語(yǔ)言的編譯程序編譯過(guò)，但尚未經(jīng)過(guò)鏈接程序鏈接的目標(biāo)代碼所構(gòu)成的文件。它屬于二進(jìn)制文件。通常，目標(biāo)文件所使用的后綴名是“.obj”。(3) 可執(zhí)行文件。這是指把編譯后所產(chǎn)生的目標(biāo)代碼再經(jīng)過(guò)鏈接程序鏈接后所形成的文件。 第六章文 件 管 理 3) 按存取控制屬性分類根據(jù)系統(tǒng)管理員或用戶所規(guī)定的存取控制屬性，可將文件分為三類：(1) 只執(zhí)行文件。該類文件只允許被核準(zhǔn)的用戶調(diào)用執(zhí)行，既不允許讀，更不允許寫。(2) 只讀文件。該類文件只允許文件主及被核準(zhǔn)的用戶去讀，但不允許寫。(3) 讀寫文件。這是指允許文件主和被核準(zhǔn)的用戶去讀或?qū)懙奈募?第六章

9、文 件 管 理 4) 按組織形式和處理方式分類根據(jù)文件的組織形式和系統(tǒng)對(duì)其的處理方式，可將文件分為三類：(1) 普通文件：由ASCII碼或二進(jìn)制碼組成的字符文件。一般用戶建立的源程序文件、數(shù)據(jù)文件、目標(biāo)代碼文件及操作系統(tǒng)自身代碼文件、庫(kù)文件、實(shí)用程序文件等都是普通文件，它們通常存儲(chǔ)在外存儲(chǔ)設(shè)備上。(2) 目錄文件：由文件目錄組成的，用來(lái)管理和實(shí)現(xiàn)文件系統(tǒng)功能的系統(tǒng)文件，通過(guò)目錄文件可以對(duì)其它文件的信息進(jìn)行檢索。由于目錄文件也是由字符序列構(gòu)成，因此對(duì)其可進(jìn)行與普通文件一樣的種種文件操作。 第六章文 件 管 理 (3) 特殊文件：特指系統(tǒng)中的各類I/O設(shè)備。為了便于統(tǒng)一管理，系統(tǒng)將所有的輸入/輸出

10、設(shè)備都視為文件，按文件方式提供給用戶使用，如目錄的檢索、權(quán)限的驗(yàn)證等都與普通文件相似，只是對(duì)這些文件的操作是和設(shè)備驅(qū)動(dòng)程序緊密相連的，系統(tǒng)將這些操作轉(zhuǎn)為對(duì)具體設(shè)備的操作。根據(jù)設(shè)備數(shù)據(jù)交換單位的不同，又可將特殊文件分為塊設(shè)備文件和字符設(shè)備文件。前者用于磁盤、光盤或磁帶等塊設(shè)備的I/O 操作，而后者用于終端、打印機(jī)等字符設(shè)備的I/O 操作。 第六章文 件 管 理 2 2文件系統(tǒng)模型文件系統(tǒng)模型圖6-2示出了文件系統(tǒng)的模型。可將該模型分為三個(gè)層次，其最底層是對(duì)象及其屬性；中間層是對(duì)對(duì)象進(jìn)行操縱和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。 第六章文 件 管 理 圖6-2文件系統(tǒng)模型 第六章文

11、件 管 理 1) 對(duì)象及其屬性文件管理系統(tǒng)管理的對(duì)象有： 文件。它作為文件管理的直接對(duì)象。 目錄。為了方便用戶對(duì)文件的存取和檢索，在文件系統(tǒng)中必須配置目錄，每個(gè)目錄項(xiàng)中，必須含有文件名及該文件所在的物理地址(或指針)。對(duì)目錄的組織和管理是方便用戶和提高對(duì)文件存取速度的關(guān)鍵。 磁盤(磁帶)存儲(chǔ)空間。文件和目錄必定占用存儲(chǔ)空間，對(duì)這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對(duì)文件的存取速度。 第六章文 件 管 理 2) 對(duì)對(duì)象操縱和管理的軟件集合這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實(shí)現(xiàn)的，其中包括: 對(duì)文件存儲(chǔ)空間的管理、對(duì)文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為

12、物理地址的機(jī)制、對(duì)文件讀和寫的管理，以及對(duì)文件的共享與保護(hù)等功能。 第六章文 件 管 理 3) 文件系統(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.36.1.3文件操作文件操作1 1最基本的文件操作最基本的文件操作(1) 創(chuàng)建文件。在創(chuàng)建一個(gè)新文件時(shí)，系統(tǒng)首先要為新文件分配必要的外存空間，并在文件系統(tǒng)的目錄中，為之建立一個(gè)目錄項(xiàng)。目錄項(xiàng)中

13、應(yīng)記錄新文件的文件名及其在外存的地址等屬性。(2) 刪除文件。當(dāng)已不再需要某文件時(shí)，可將它從文件系統(tǒng)中刪除。在刪除時(shí)，系統(tǒng)應(yīng)先從目錄中找到要?jiǎng)h除文件的目錄項(xiàng)，使之成為空項(xiàng)，然后回收該文件所占用的存儲(chǔ)空間。 第六章文 件 管 理 (3) 讀文件。在讀一個(gè)文件時(shí)，須在相應(yīng)系統(tǒng)調(diào)用中給出文件名和應(yīng)讀入的內(nèi)存目標(biāo)地址。此時(shí)，系統(tǒng)同樣要查找目錄，找到指定的目錄項(xiàng)，從中得到被讀文件在外存中的位置。在目錄項(xiàng)中，還有一個(gè)指針用于對(duì)文件的讀/寫。(4) 寫文件。在寫一個(gè)文件時(shí)，須在相應(yīng)系統(tǒng)調(diào)用中給出該文件名及該文件在內(nèi)存中的(源)地址。為此，也同樣須先查找目錄，找到指定文件的目錄項(xiàng)，再利用目錄中的寫指針進(jìn)行寫操

14、作。 第六章文 件 管 理 (5) 截?cái)辔募?。如果一個(gè)文件的內(nèi)容已經(jīng)陳舊而需要全部更新時(shí)，一種方法是將此文件刪除，再重新創(chuàng)建一個(gè)新文件。但如果文件名及其屬性均無(wú)改變時(shí)，則可采取另一種所謂的截?cái)辔募姆椒?，此即將原有文件的長(zhǎng)度設(shè)置為0，或者說(shuō)是放棄原有的文件內(nèi)容。(6) 設(shè)置文件的讀/寫位置。前述的文件讀/寫操作都只提供了對(duì)文件順序存取的手段，即每次都是從文件的始端讀或?qū)?。設(shè)置文件讀/寫位置的操作，用于設(shè)置文件讀/寫指針的位置，以便每次讀/寫文件時(shí)，不是從其始端而是從所設(shè)置的位置開(kāi)始操作。也正因如此，才能改順序存取為隨機(jī)存取。 第六章文 件 管 理 2 2文件的文件的“打開(kāi)打開(kāi)”和和“關(guān)閉關(guān)閉”

15、操作操作當(dāng)前OS所提供的大多數(shù)對(duì)文件的操作，其過(guò)程大致都是這樣兩步: 第一步是通過(guò)檢索文件目錄來(lái)找到指定文件的屬性及其在外存上的位置；第二步是對(duì)文件實(shí)施相應(yīng)的操作，如讀文件或?qū)懳募?。?dāng)用戶要求對(duì)一個(gè)文件實(shí)施多次讀/寫或其它操作時(shí)，每次都要從檢索目錄開(kāi)始。為了避免多次重復(fù)地檢索目錄，在大多數(shù)OS中都引入了“打開(kāi)”(open)這一文件系統(tǒng)調(diào)用，當(dāng)用戶第一次請(qǐng)求對(duì)某文件進(jìn)行操作時(shí)，先利用open系統(tǒng)調(diào)用將該文件打開(kāi)。 第六章文 件 管 理 所謂“打開(kāi)”，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開(kāi)文件表的一個(gè)表目中，并將該表目的編號(hào)(或稱為索引)返回給用戶。以后，當(dāng)

16、用戶再要求對(duì)該文件進(jìn)行相應(yīng)的操作時(shí)，便可利用系統(tǒng)所返回的索引號(hào)向系統(tǒng)提出操作請(qǐng)求。系統(tǒng)這時(shí)便可直接利用該索引號(hào)到打開(kāi)文件表中去查找，從而避免了對(duì)該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開(kāi)銷，也顯著地提高了對(duì)文件的操作速度。如果用戶已不再需要對(duì)該文件實(shí)施相應(yīng)的操作時(shí)，可利用“關(guān)閉”(close)系統(tǒng)調(diào)用來(lái)關(guān)閉此文件，OS將會(huì)把該文件從打開(kāi)文件表中的表目上刪除掉。 第六章文 件 管 理 3 3其它文件操作其它文件操作為了方便用戶使用文件，通常，OS都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，可將這些調(diào)用分成若干類: 最常用的一類是有關(guān)對(duì)文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的屬性，如改變已存文

17、件的文件名、改變文件的擁有者(文件主)、改變對(duì)文件的訪問(wèn)權(quán)，以及查詢文件的狀態(tài)(包括文件類型、大小和擁有者以及對(duì)文件的訪問(wèn)權(quán)等)；另一類是有關(guān)目錄的，如創(chuàng)建一個(gè)目錄，刪除一個(gè)目錄，改變當(dāng)前目錄和工作目錄等；此外，還有用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對(duì)文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。 第六章文 件 管 理 6.2文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu) 6.2.16.2.1文件邏輯結(jié)構(gòu)的類型文件邏輯結(jié)構(gòu)的類型1 1有結(jié)構(gòu)文件有結(jié)構(gòu)文件在記錄式文件中，每個(gè)記錄都用于描述實(shí)體集中的一個(gè)實(shí)體，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項(xiàng)。記錄的長(zhǎng)度可分為定長(zhǎng)和不定長(zhǎng)兩類。(1) 定長(zhǎng)記錄。這是指文件中所有記錄的長(zhǎng)度都是相同的，

18、所有記錄中的各數(shù)據(jù)項(xiàng)都處在記錄中相同的位置，具有相同的順序和長(zhǎng)度。文件的長(zhǎng)度用記錄數(shù)目表示。對(duì)定長(zhǎng)記錄的處理方便、開(kāi)銷小，所以這是目前較常用的一種記錄格式，被廣泛用于數(shù)據(jù)處理中。 第六章文 件 管 理 (2) 變長(zhǎng)記錄。這是指文件中各記錄的長(zhǎng)度不相同。產(chǎn)生變長(zhǎng)記錄的原因，可能是由于一個(gè)記錄中所包含的數(shù)據(jù)項(xiàng)數(shù)目并不相同，如書(shū)的著作者、論文中的關(guān)鍵詞等；也可能是數(shù)據(jù)項(xiàng)本身的長(zhǎng)度不定，例如，病歷記錄中的病因、病史；科技情報(bào)記錄中的摘要等。不論是哪一種，在處理前，每個(gè)記錄的長(zhǎng)度是可知的。根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式來(lái)組織這些記錄，形成下述的幾種文件：(1) 順序文件。這是由一系列記錄按某

19、種順序排列所形成的文件。其中的記錄通常是定長(zhǎng)記錄，因而能用較快的速度查找文件中的記錄。 第六章文 件 管 理 (2) 索引文件。當(dāng)記錄為可變長(zhǎng)度時(shí)，通常為之建立一張索引表，并為每個(gè)記錄設(shè)置一個(gè)表項(xiàng)，以加快對(duì)記錄檢索的速度。(3) 索引順序文件。這是上述兩種文件構(gòu)成方式的結(jié)合。它為文件建立一張索引表，為每一組記錄中的第一個(gè)記錄設(shè)置一個(gè)表項(xiàng)。 第六章文 件 管 理 2 2無(wú)結(jié)構(gòu)文件無(wú)結(jié)構(gòu)文件如果說(shuō)大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)是采用有結(jié)構(gòu)的文件形式的話，則大量的源程序、可執(zhí)行文件、庫(kù)函數(shù)等，所采用的就是無(wú)結(jié)構(gòu)的文件形式，即流式文件。其長(zhǎng)度以字節(jié)為單位。對(duì)流式文件的訪問(wèn)，則是采用讀/寫指針來(lái)指出下一個(gè)要訪問(wèn)

20、的字符?？梢园蚜魇轿募醋鍪怯涗浭轿募囊粋€(gè)特例。在UNIX系統(tǒng)中，所有的文件都被看做是流式文件，即使是有結(jié)構(gòu)文件，也被視為流式文件，系統(tǒng)不對(duì)文件進(jìn)行格式處理。 第六章文 件 管 理 6.2.26.2.2順序文件順序文件1 1邏輯記錄的排序邏輯記錄的排序文件是記錄的集合。文件中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進(jìn)行排列。一般地，可歸納為以下兩種情況：第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無(wú)關(guān)。通常的辦法是由時(shí)間來(lái)決定，即按存入時(shí)間的先后排列，最先存入的記錄作為第一個(gè)記錄，其次存入的為第二個(gè)記錄， 依此類推。第六章文 件 管 理 第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)

21、鍵字(詞)排列?？梢园搓P(guān)鍵詞的長(zhǎng)短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。 對(duì)順序結(jié)構(gòu)文件可有更高的檢索效率，因?yàn)樵跈z索串結(jié)構(gòu)文件時(shí)，每次都必須從頭開(kāi)始，逐個(gè)記錄地查找，直至找到指定的記錄，或查完所有的記錄為止。而對(duì)順序結(jié)構(gòu)文件，則可利用某種有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法來(lái)提高檢索效率。 第六章文 件 管 理 2 2對(duì)順序文件對(duì)順序文件(Sequential File)(Sequential File)的讀的讀/ /寫操作寫操作順序文件中的記錄可以是定長(zhǎng)的，也可以是變長(zhǎng)的。對(duì)于定長(zhǎng)記錄的順序文件，如果已知當(dāng)前記錄的邏輯地址，便很容易確定下一個(gè)記錄的

22、邏輯地址。在讀一個(gè)文件時(shí)，可設(shè)置一個(gè)讀指針Rptr，令它指向下一個(gè)記錄的首地址，每當(dāng)讀完一個(gè)記錄時(shí)，便執(zhí)行Rptr:=Rptr + L 第六章文 件 管 理 操作，使之指向下一個(gè)記錄的首地址，其中的L為記錄長(zhǎng)度。類似地，在寫一個(gè)文件時(shí)，也應(yīng)設(shè)置一個(gè)寫指針Wptr，使之指向要寫的記錄的首地址。同樣，在每寫完一個(gè)記錄時(shí)，又須執(zhí)行以下操作:Wptr:=Wptr + L對(duì)于變長(zhǎng)記錄的順序文件，在順序讀或?qū)憰r(shí)的情況相似，但應(yīng)分別為它們?cè)O(shè)置讀或?qū)懼羔?，在每次讀或?qū)懲暌粋€(gè)記錄后，須將讀或?qū)懼羔樇由螸i。Li是剛讀或剛寫完的記錄的長(zhǎng)度。圖6-3所示為定長(zhǎng)和變長(zhǎng)記錄文件。 第六章文 件 管 理 圖6-3定長(zhǎng)和變

23、長(zhǎng)記錄文件 R0R1R2R3RiLLLLLL2L3L4LiL(i1)LRptr(a) 定長(zhǎng)記錄文件L0R0L1R1RiWptr(b) 變長(zhǎng)記錄文件Li00L0L01L1L0L12Li(Lk1)i1k0(Lk1)ik0第六章文 件 管 理 3 3順序文件的優(yōu)缺點(diǎn)順序文件的優(yōu)缺點(diǎn)順序文件的最佳應(yīng)用場(chǎng)合是在對(duì)諸記錄進(jìn)行批量存取時(shí)，即每次要讀或?qū)懸淮笈涗洉r(shí)。此時(shí)，對(duì)順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲(chǔ)在磁帶上，并能有效地工作。 第六章文 件 管 理 在交互應(yīng)用的場(chǎng)合，如果用戶(程序)要求查找或修改單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。這時(shí)，順序文件所表現(xiàn)出來(lái)的性

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

25、。 第六章文 件 管 理 6.2.36.2.3索引文件索引文件對(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)度，則 10iiiiiLA第六章文 件 管 理 可見(jiàn)，對(duì)于定長(zhǎng)記錄，除了可以方便地實(shí)現(xiàn)順序存取外，還可較方便地實(shí)現(xiàn)直接存取。然而，對(duì)于變長(zhǎng)記錄就較難實(shí)現(xiàn)直接存取了，因?yàn)橛弥苯哟嫒》椒▉?lái)訪問(wèn)變長(zhǎng)記錄文件中

26、的一個(gè)記錄是十分低效的，其檢索時(shí)間也很難令人接受。為了解決這一問(wèn)題，可為變長(zhǎng)記錄文件建立一張索引表，對(duì)主文件中的每個(gè)記錄，在索引表中設(shè)有一個(gè)相應(yīng)的表項(xiàng)，用于記錄該記錄的長(zhǎng)度L及指向該記錄的指針(指向該記錄在邏輯地址空間的首址)。由于索引表是按記錄鍵排序的，因此，索引表本身是一個(gè)定長(zhǎng)記錄的順序文件，從而也就可以方便地實(shí)現(xiàn)直接存取。圖6-4示出了索引文件(Index File)的組織形式。 第六章文 件 管 理 圖6-4索引文件的組織 索引號(hào)0長(zhǎng)度 m指針 ptrm01m1imi索引表R0R1Ri邏輯文件第六章文 件 管 理 6.2.46.2.4索引順序文件索引順序文件索引順序文件(Index S

27、equential File)可能是最常見(jiàn)的一種邏輯文件形式。它有效地克服了變長(zhǎng)記錄文件不便于直接存取的缺點(diǎn)，而且所付出的代價(jià)也不算太大。前已述及，它是順序文件和索引文件相結(jié)合的產(chǎn)物。它將順序文件中的所有記錄分為若干個(gè)組(例如，50個(gè)記錄為一個(gè)組)；為順序文件建立一張索引表，在索引表中為每組中的第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指向該記錄的指針。索引順序文件如圖6-5所示。 第六章文 件 管 理 圖6-5索引順序文件 鍵An QiBao RongChen Lin邏輯地址姓 名An QiAn Kang其它屬性Bao Rong邏輯文件第六章文 件 管 理 6.2.56.2.5直接文件

28、和哈希文件直接文件和哈希文件1 1直接文件直接文件采用前述幾種文件結(jié)構(gòu)對(duì)記錄進(jìn)行存取時(shí)，都須利用給定的記錄鍵值，先對(duì)線性表或鏈表進(jìn)行檢索，以找到指定記錄的物理地址。然而對(duì)于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換(Key to address transformation)。組織直接文件的關(guān)鍵，在于用什么方法進(jìn)行從記錄值到物理地址的轉(zhuǎn)換。 第六章文 件 管 理 2 2哈希哈希(Hash)(Hash)文件文件這是目前應(yīng)用最為廣泛的一種直接文件。它利用Hash函數(shù)(或稱散列函數(shù))，可將

29、記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址。但為了能實(shí)現(xiàn)文件存儲(chǔ)空間的動(dòng)態(tài)分配，通常由Hash函數(shù)所求得的并非是相應(yīng)記錄的地址，而是指向一目錄表相應(yīng)表目的指針，該表目的內(nèi)容指向相應(yīng)記錄所在的物理塊，如圖6-6所示。例如，若令K為記錄鍵值，用A作為通過(guò)Hash函數(shù)H的轉(zhuǎn)換所形成的該記錄在目錄表中對(duì)應(yīng)表目的位置，則有關(guān)系A(chǔ)=H(K)。通常，把Hash函數(shù)作為標(biāo)準(zhǔn)函數(shù)存于系統(tǒng)中，供存取文件時(shí)調(diào)用。 第六章文 件 管 理 圖6-6Hash文件的邏輯結(jié)構(gòu) fHash函數(shù)目錄表鍵值第六章文 件 管 理 6.3外存分配方式外存分配方式 6.3.16.3.1連續(xù)分配連續(xù)分配1 1連續(xù)分配方式連續(xù)分配方式連續(xù)分配(Conti

30、nuous Allocation)要求為每一個(gè)文件分配一組相鄰接的盤塊。一組盤塊的地址定義了磁盤上的一段線性地址。例如，第一個(gè)盤塊的地址為b，則第二個(gè)盤塊的地址為b+1，第三個(gè)盤塊的地址為b+2。通常，它們都位于一條磁道上，在進(jìn)行讀/寫時(shí)，不必移動(dòng)磁頭，僅當(dāng)訪問(wèn)到一條磁道的最后一個(gè)盤塊后，才需要移到下一條磁道，于是又去連續(xù)地讀/寫多個(gè)盤塊。第六章文 件 管 理 在采用連續(xù)分配方式時(shí)，可把邏輯文件中的記錄順序地存儲(chǔ)到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱為順序文件。這種分配方式保證了邏輯文件中的記錄順序與存儲(chǔ)器中文件占用盤塊的順序的一致性。為使系統(tǒng)能找到文件存

31、放的地址，應(yīng)在目錄項(xiàng)的“文件物理地址”字段中，記錄該文件第一個(gè)記錄所在的盤塊號(hào)和文件長(zhǎng)度(以盤塊數(shù)進(jìn)行計(jì)量)。圖6-7 示出了連續(xù)分配的情況。圖中假定了記錄與盤塊的大小相同。Count文件的第一個(gè)盤塊號(hào)是0，文件長(zhǎng)度為2，因此是在盤塊號(hào)為0和1的兩盤塊中存放文件1的數(shù)據(jù)。 第六章文 件 管 理 圖6-7磁盤空間的連續(xù)分配 1230567491011813141512171819162122232025262724list29303128mailcountfilestart lengthcount 02tr153mail216list293f72目錄trf第六章文 件 管 理 如同內(nèi)存的動(dòng)態(tài)分區(qū)

32、分配一樣，隨著文件建立時(shí)空間的分配和文件刪除時(shí)空間的回收，將使磁盤空間被分割成許多小塊，這些較小的連續(xù)區(qū)已難于用來(lái)存儲(chǔ)文件，此即外存的碎片。同樣，我們也可以利用緊湊的方法，將盤上所有的文件緊靠在一起，把所有的碎片拼接成一大片連續(xù)的存儲(chǔ)空間。例如，可以運(yùn)行一個(gè)再裝配例程(repack routine)，由它將磁盤A上的大量文件拷貝到一張軟盤B或幾張軟盤(C，D，)上，并釋放原來(lái)的A盤，使之成為一個(gè)空閑盤。然后再將軟盤B(C，D，)上的文件拷回A盤上。這種方法能將含有多個(gè)文件的盤上的所有空閑盤塊都集中在一起，從而消除了外部碎片。但為了將外存上的空閑空間進(jìn)行一次緊湊，所花費(fèi)的時(shí)間遠(yuǎn)比將內(nèi)存緊湊一次所

33、花費(fèi)的時(shí)間多得多。 第六章文 件 管 理 2連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)點(diǎn)如下：(1) 順序訪問(wèn)容易。訪問(wèn)一個(gè)占有連續(xù)空間的文件非常容易。系統(tǒng)可從目錄中找到該順序文件所在的第一個(gè)盤塊號(hào)，從此開(kāi)始順序地、逐個(gè)盤塊地往下讀/寫。連續(xù)分配也支持直接存取。例如，要訪問(wèn)一個(gè)從b塊開(kāi)始存放的文件中的第i個(gè)盤塊的內(nèi)容，就可直接訪問(wèn)b+i號(hào)盤塊。(2) 順序訪問(wèn)速度快。因?yàn)橛蛇B續(xù)分配所裝入的文件，其所占用的盤塊可能是位于一條或幾條相鄰的磁道上，這時(shí)，磁頭的移動(dòng)距離最少，因此，這種對(duì)文件訪問(wèn)的速度是幾種存儲(chǔ)空間分配方式中最高的一種。 第六章文 件 管 理 連續(xù)分配的主要缺點(diǎn)如下：(1

34、) 要求有連續(xù)的存儲(chǔ)空間。要為每一個(gè)文件分配一段連續(xù)的存儲(chǔ)空間，這樣，便會(huì)產(chǎn)生出許多外部碎片，嚴(yán)重地降低了外存空間的利用率。如果是定期地利用緊湊方法來(lái)消除碎片，則又需花費(fèi)大量的機(jī)器時(shí)間。 第六章文 件 管 理 (2) 必須事先知道文件的長(zhǎng)度。要將一個(gè)文件裝入一個(gè)連續(xù)的存儲(chǔ)區(qū)中，必須事先知道文件的大小，然后根據(jù)其大小，在存儲(chǔ)空間中找出一塊其大小足夠的存儲(chǔ)區(qū)，將文件裝入。在有些情況下，知道文件的大小是件非常容易的事，如可拷貝一個(gè)已存文件。但有時(shí)卻很難，在此情況下，只能靠估算。如果估計(jì)的文件大小比實(shí)際文件小，就可能因存儲(chǔ)空間不足而中止文件的拷貝，須再要求用戶重新估算，然后再次執(zhí)行。這樣，顯然既費(fèi)時(shí)又

35、麻煩。這就促使用戶往往將文件長(zhǎng)度估得比實(shí)際的大，甚至使所計(jì)算的文件長(zhǎng)度比實(shí)際長(zhǎng)度大得多，顯然，這會(huì)嚴(yán)重地浪費(fèi)外存空間。對(duì)于那些動(dòng)態(tài)增長(zhǎng)的文件，由于開(kāi)始時(shí)文件很小，在運(yùn)行中逐漸增大，比如，這種增長(zhǎng)要經(jīng)歷幾天、幾個(gè)月。在此情況下，即使事先知道文件的最終大小，在采用預(yù)分配存儲(chǔ)空間的方法時(shí)，顯然也將是很低效的，即它使大量的存儲(chǔ)空間長(zhǎng)期地空閑著。 第六章文 件 管 理 6.3.26.3.2鏈接分配鏈接分配1 1隱式鏈接隱式鏈接在采用隱式鏈接分配方式時(shí)，在文件目錄的每個(gè)目錄項(xiàng)中，都須含有指向鏈接文件第一個(gè)盤塊和最后一個(gè)盤塊的指針。圖6-8 中示出了一個(gè)占用5個(gè)盤塊的鏈接式文件。在相應(yīng)的目錄項(xiàng)中，指示了其第

36、一個(gè)盤塊號(hào)是9，最后一個(gè)盤塊號(hào)是25。而在每個(gè)盤塊中都含有一個(gè)指向下一個(gè)盤塊的指針，如在第一個(gè)盤塊9中設(shè)置了第二個(gè)盤塊的盤塊號(hào)是16；在16號(hào)盤塊中又設(shè)置了第三個(gè)盤塊的盤塊號(hào)1。如果指針占用4個(gè)字節(jié)，對(duì)于盤塊大小為512字節(jié)的磁盤，則每個(gè)盤塊中只有508個(gè)字節(jié)可供用戶使用。 第六章文 件 管 理 圖6-8磁盤空間的鏈接式分配 25123056749101181314151217181916212223202526272429303128filestartendjeep925目錄101-116第六章文 件 管 理 隱式鏈接分配方式的主要問(wèn)題在于：它只適合于順序訪問(wèn)，它對(duì)隨機(jī)訪問(wèn)是極其低效的。如果

37、要訪問(wèn)文件所在的第i個(gè)盤塊，則必須先讀出文件的第一個(gè)盤塊，就這樣順序地查找直至第i塊。當(dāng)i=100時(shí)，須啟動(dòng)100次磁盤去實(shí)現(xiàn)讀盤塊的操作，平均每次都要花費(fèi)幾十毫秒?？梢?jiàn)，隨機(jī)訪問(wèn)的速度相當(dāng)?shù)?。此外，只通過(guò)鏈接指針來(lái)將一大批離散的盤塊鏈接起來(lái)，其可靠性較差，因?yàn)橹灰渲械娜魏我粋€(gè)指針出現(xiàn)問(wèn)題，都會(huì)導(dǎo)致整個(gè)鏈的斷開(kāi)。 第六章文 件 管 理 2 2顯式鏈接顯式鏈接這是指把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表在整個(gè)磁盤僅設(shè)置一張，如圖6-9所示。表的序號(hào)是物理盤塊號(hào)，從0開(kāi)始，直至N-1；N為盤塊總數(shù)。在每個(gè)表項(xiàng)中存放鏈接指針，即下一個(gè)盤塊號(hào)。在該表中，凡是屬于某一文件的

38、第一個(gè)盤塊號(hào)，或者說(shuō)是每一條鏈的鏈?zhǔn)字羔標(biāo)鶎?duì)應(yīng)的盤塊號(hào)，均作為文件地址被填入相應(yīng)文件的FCB的“物理地址”字段中。由于查找記錄的過(guò)程是在內(nèi)存中進(jìn)行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問(wèn)磁盤的次數(shù)。由于分配給文件的所有盤塊號(hào)都放在該表中，故把該表稱為文件分配表FAT(File Allocation Table)。 第六章文 件 管 理 圖6-9顯式鏈接結(jié)構(gòu) 012345物理塊號(hào)2FCBFAT0451第六章文 件 管 理 6.3.3 FAT6.3.3 FAT和和NTFSNTFS技術(shù)技術(shù)1 1FAT12FAT121) 以盤塊為基本分配單位 早期MS-DOS操作系統(tǒng)所使用的是FAT12文

39、件系統(tǒng)，在每個(gè)分區(qū)中都配有兩張文件分配表FAT1和FAT2，在FAT的每個(gè)表項(xiàng)中存放下一個(gè)盤塊號(hào)，它實(shí)際上是用于盤塊之間的鏈接的指針，通過(guò)它可以將一個(gè)文件的所有的盤塊鏈接起來(lái)，而將文件的第一個(gè)盤塊號(hào)放在自己的FCB中。第六章文 件 管 理 圖6-10示出了MS-DOS的文件物理結(jié)構(gòu)，這里示出了兩個(gè)文件，文件A占用三個(gè)盤塊，其盤塊號(hào)依次為4、6、11；文件B則依次占用9、10及5號(hào)三個(gè)盤塊。每個(gè)文件的第一個(gè)盤塊號(hào)放在自己的FCB中。整個(gè)系統(tǒng)有一張文件分配表FAT。在FAT的每個(gè)表項(xiàng)中存放下一個(gè)盤塊號(hào)。對(duì)于1.2 MB的軟盤，每個(gè)盤塊的大小為512 B，在每個(gè)FAT中共含有2.4 K個(gè)表項(xiàng)，由于每

40、個(gè)FAT表項(xiàng)占12位，故FAT表占用3.6 KB的存儲(chǔ)空間。 第六章文 件 管 理 圖6-10MS-DOS的文件物理結(jié)構(gòu) 6EOF11105EOF0123456789FATFCB A4FCB B9第六章文 件 管 理 現(xiàn)在我們來(lái)計(jì)算以盤塊為分配單位時(shí)，所允許的最大磁盤容量。由于每個(gè)FAT表項(xiàng)為12位，因此，在FAT表中最多允許有4096個(gè)表項(xiàng)，如果采用以盤塊作為基本分配單位，每個(gè)盤塊(也稱扇區(qū))的大小一般是512字節(jié)，那么，每個(gè)磁盤分區(qū)的容量為2 MB(4096512 B)。同時(shí)，一個(gè)物理磁盤支持4個(gè)邏輯磁盤分區(qū)，所以相應(yīng)的磁盤最大容量?jī)H為8 MB。這對(duì)最早時(shí)期的硬盤還可應(yīng)付，但很快磁盤的容量

41、就超過(guò)了8 MB，F(xiàn)AT12是否還可繼續(xù)用呢，回答雖是肯定的，但需要引入一個(gè)新的分配單位簇。 第六章文 件 管 理 2) 簇的基本概念為了適應(yīng)磁盤容量不斷增大的需要，在進(jìn)行盤塊分配時(shí)，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的扇區(qū)，在FAT中它是作為一個(gè)虛擬扇區(qū)，簇的大小一般是2n (n為整數(shù))個(gè)盤塊，在MS-DOS的實(shí)際運(yùn)用中，簇的容量可以僅有一個(gè)扇區(qū)(512 B)、兩個(gè)扇區(qū)(1 KB)、四個(gè)扇區(qū)(2 KB)、八個(gè)扇區(qū)(4 KB)等。一個(gè)簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)。例如，當(dāng)一個(gè)簇僅有一個(gè)扇區(qū)時(shí)，磁盤的最大容量為8 MB；當(dāng)一個(gè)簇包含兩個(gè)扇區(qū)時(shí)，磁盤的最大容

42、量可以達(dá)到16 MB；當(dāng)一個(gè)簇包含了八個(gè)扇區(qū)時(shí)，磁盤的最大容量便可達(dá)到64 MB。第六章文 件 管 理 由上所述可以看出，以簇作為基本的分配單位所帶來(lái)的最主要的好處是，能適應(yīng)磁盤容量不斷增大的情況。值得注意的是，使用簇作為基本的分配單位雖可減少FAT表中的項(xiàng)數(shù)(在相同的磁盤容量下，F(xiàn)AT表的項(xiàng)數(shù)是與簇的大小成反比的)。這一方面會(huì)使FAT表占用更少的存儲(chǔ)空間，并減少訪問(wèn)FAT表的存取開(kāi)銷，提高文件系統(tǒng)的效率；但這也會(huì)造成更大的簇內(nèi)零頭(它與存儲(chǔ)器管理中的頁(yè)內(nèi)零頭相似)。 第六章文 件 管 理 3) FAT12存在的問(wèn)題盡管FAT12曾是一個(gè)不錯(cuò)的文件系統(tǒng)，但畢竟已老化，已不能滿足操作系統(tǒng)發(fā)展的需

43、要，其表現(xiàn)出來(lái)的主要問(wèn)題是，對(duì)所允許的磁盤容量存在著嚴(yán)重的限制，通常只能是數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來(lái)提高所允許的最大磁盤容量，但隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎片也將隨之成倍地增加。此外，它只能支持8+3格式的文件名。 第六章文 件 管 理 2 2FAT16FAT16對(duì)FAT12所存在的問(wèn)題進(jìn)行簡(jiǎn)單的分析即可看出，其根本原因在于，F(xiàn)AT12表最多只允許4096個(gè)表項(xiàng)，亦即最多只能將一個(gè)磁盤分區(qū)分為4096個(gè)簇。這樣，隨著磁盤容量的增加，必定會(huì)引起簇的大小和簇內(nèi)碎片也隨之增加。由此可以得出解決方法，那就是增加FAT表的表項(xiàng)數(shù)，亦即應(yīng)增加FAT表的寬度，如果我們將FAT表的寬度

44、增至16位，最大表項(xiàng)數(shù)將增至65536個(gè)，此時(shí)便能將一個(gè)磁盤分區(qū)分為65 536(216)個(gè)簇。我們把具有16位表寬的FAT表稱為FAT16。在FAT16的每個(gè)簇中可以有的盤塊數(shù)為4、8、16、32直到64，由此得出FAT16可以管理的最大分區(qū)空間為216 64 512 = 2048 MB。 第六章文 件 管 理 由上述分析不難看出，F(xiàn)AT16對(duì)FAT12的局限性有所改善，但改善很有限。當(dāng)磁盤容量迅速增加時(shí)，如果再繼續(xù)使用FAT16，由此所形成的簇內(nèi)碎片所造成的浪費(fèi)也越大。例如，當(dāng)要求磁盤分區(qū)的大小為8 GB時(shí)，則每個(gè)簇的大小達(dá)到128 KB，這意味著內(nèi)部零頭最大可達(dá)到128 KB。一般而言，

45、對(duì)于14 GB的硬盤來(lái)說(shuō)，大約會(huì)浪費(fèi)1020的空間。為了解決這一問(wèn)題，微軟推出了FAT32。 第六章文 件 管 理 3 3FAT32FAT32如同存儲(chǔ)器管理中的分頁(yè)管理，所選擇的頁(yè)面越大，可能造成的頁(yè)內(nèi)零頭也會(huì)越大。為減少頁(yè)內(nèi)零頭就應(yīng)該選擇適當(dāng)大小的頁(yè)面。在這里，為了減小磁盤的簇內(nèi)零頭，也就應(yīng)當(dāng)選擇適當(dāng)大小的簇。問(wèn)題是FAT16表的長(zhǎng)度只有65 535項(xiàng)，隨著磁盤容量的增加，簇的大小也必然會(huì)隨之增加，為了減少簇內(nèi)零頭，也就應(yīng)當(dāng)增加FAT表的長(zhǎng)度。為此，需要再增加FAT表的寬度，這樣也就由FAT16演變?yōu)镕AT32。 第六章文 件 管 理 FAT32是FAT系列文件系統(tǒng)的最后一個(gè)產(chǎn)品。每一簇在F

46、AT表中的表項(xiàng)占據(jù)4字節(jié)(232)，F(xiàn)AT表可以表示4 294 967 296項(xiàng)，即FAT32允許管理比FAT16更多的簇。這樣就允許在FAT32中采用較小的簇，F(xiàn)AT32的每個(gè)簇都固定為4 KB，即每簇用8個(gè)盤塊代替FAT16的64個(gè)盤塊，每個(gè)盤塊仍為512字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的單個(gè)最大磁盤空間大到4 KB232 = 2 TB。三種FAT類型的最大分區(qū)以及所對(duì)應(yīng)的塊的大小如圖6-11所示。 第六章文 件 管 理 圖6-11 FAT中簇的大小與最大分區(qū)的對(duì)應(yīng)關(guān)系 塊大小/KB FAT12/MB FAT16/MB FAT32/TB 0.5 2 1 4 2 8 128 4 16 256

47、 1 8 512 2 16 1024 2 32 2048 2 第六章文 件 管 理 4 4NTFSNTFS1) NTFS新特征NTFS(New Technology File System)是一個(gè)專門為Windows NT開(kāi)發(fā)的、全新的文件系統(tǒng)，并適用于Windows 2000/XP/2003。NTFS具有許多新的特征：首先，它使用了64位磁盤地址，理論上可以支持2的64次方字節(jié)的磁盤分區(qū)；其次，在NTFS中可以很好地支持長(zhǎng)文件名，單個(gè)文件名限制在255個(gè)字符以內(nèi)，全路徑名為32 767個(gè)字符；第三，具有系統(tǒng)容錯(cuò)功能，即在系統(tǒng)出現(xiàn)故障或差錯(cuò)時(shí)，仍能保證系統(tǒng)正常運(yùn)行，這一點(diǎn)我們將在6.6節(jié)中介紹

48、；第四，提供了數(shù)據(jù)的一致性，這是一個(gè)非常有用的功能，我們將在本章的最后一節(jié)介紹；此外，NTFS還提供了文件加密、文件壓縮等功能。 第六章文 件 管 理 2) 磁盤組織同F(xiàn)AT文件系統(tǒng)一樣，NTFS也是以簇作為磁盤空間分配和回收的基本單位。一個(gè)文件占用若干個(gè)簇，一個(gè)簇只屬于一個(gè)文件。通過(guò)簇來(lái)間接管理磁盤，可以不需要知道盤塊(扇區(qū))的大小，使NTFS具有了與磁盤物理扇區(qū)大小無(wú)關(guān)的獨(dú)立性，很容易支持扇區(qū)大小不是512字節(jié)的非標(biāo)準(zhǔn)磁盤，從而可以根據(jù)不同的磁盤選擇匹配的簇大小。 第六章文 件 管 理 在NTFS文件系統(tǒng)中，把卷上簇的大小稱為“卷因子”，卷因子是在磁盤格式化時(shí)確定的，其大小同F(xiàn)AT一樣，也

49、是物理磁盤扇區(qū)的整數(shù)倍，即一個(gè)簇包含2n(n為整數(shù))個(gè)盤塊，簇的大小可由格式化命令或格式化程序按磁盤容量和應(yīng)用需求來(lái)確定，可以為512 B、1 KB、2 KB，最大可達(dá)64 KB。對(duì)于小磁盤(512 MB)，默認(rèn)簇大小為512字節(jié)；對(duì)于1 GB磁盤，默認(rèn)簇大小為1 KB；對(duì)于2 GB磁盤，則默認(rèn)簇大小為4 KB。事實(shí)上，為了在傳輸效率和簇內(nèi)碎片之間進(jìn)行折中，NTFS在大多數(shù)情況下都是使用4 KB。 第六章文 件 管 理 對(duì)于簇的定位，NTFS是采用邏輯簇號(hào)LCN(Logical Cluster Number)和虛擬簇號(hào)VCN(Virtual Cluster Number)進(jìn)行的。LCN是以卷為

50、單位，將整個(gè)卷中所有的簇按順序進(jìn)行簡(jiǎn)單的編號(hào)，NTFS在進(jìn)行地址映射時(shí)，可以通過(guò)卷因子與LCN的乘積，便可算出卷上的物理字節(jié)偏移量，從而得到文件數(shù)據(jù)所在的物理磁盤地址。為了方便文件中數(shù)據(jù)的引用，NTFS還可以使用VCN，以文件為單位，將屬于某個(gè)文件的簇按順序進(jìn)行編號(hào)。只要知道了文件開(kāi)始的簇地址，便可將VCN映射到LCN。 第六章文 件 管 理 3) 文件的組織在NTFS中，以卷為單位，將一個(gè)卷中的所有文件信息、目錄信息以及可用的未分配空間信息，都以文件記錄的方式記錄在一張主控文件表MFT(Master File Table)中。該表是NTFS 卷結(jié)構(gòu)的中心，從邏輯上講，卷中的每個(gè)文件作為一條記

51、錄，在MFT 表中占有一行，其中還包括MFT 自己的這一行。每行大小固定為1 KB，每行稱為該行所對(duì)應(yīng)文件的元數(shù)據(jù)(metadata)，也稱為文件控制字。 第六章文 件 管 理 在MFT表中，每個(gè)元數(shù)據(jù)將其所對(duì)應(yīng)文件的所有信息，包括文件的內(nèi)容等，都被組織在所對(duì)應(yīng)文件的一組屬性中。由于文件大小相差懸殊，其屬性所需空間大小也相差很大，因此，在MFT表中，對(duì)于元數(shù)據(jù)的1 KB空間，可能記錄不下文件的全部信息。所以當(dāng)文件較小時(shí)，其屬性值所占空間也較小，可以將文件的所有屬性直接記錄在元數(shù)據(jù)中。而當(dāng)文件較大時(shí)，元數(shù)據(jù)僅記錄該文件的一部分屬性，其余屬性，如文件的內(nèi)容等，可以記錄到卷中的其它可用簇中，并將這些

52、簇按其所記錄文件的屬性進(jìn)行分類，分別鏈接成多個(gè)隊(duì)列，將指向這些隊(duì)列的指針保存在元數(shù)據(jù)中。 第六章文 件 管 理 6.3.46.3.4索引分配索引分配1 1單級(jí)索引分配單級(jí)索引分配鏈接分配方式雖然解決了連續(xù)分配方式所存在的問(wèn)題，但又出現(xiàn)了下述另外兩個(gè)問(wèn)題：(1) 不能支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號(hào)。 第六章文 件 管 理 (2) FAT需占用較大的內(nèi)存空間。由于一個(gè)文件所占用盤塊的盤塊號(hào)是隨機(jī)地分布在FAT中的，因而只有將整個(gè)FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個(gè)文件的所有盤塊號(hào)。當(dāng)磁盤容量較大時(shí)，F(xiàn)AT可能要占用數(shù)兆字節(jié)以上的內(nèi)存空

53、間，這是令人難以接受的。事實(shí)上，在打開(kāi)某個(gè)文件時(shí)，只需把該文件占用的盤塊的編號(hào)調(diào)入內(nèi)存即可，完全沒(méi)有必要將整個(gè)FAT調(diào)入內(nèi)存。為此，應(yīng)將每個(gè)文件所對(duì)應(yīng)的盤塊號(hào)集中地放在一起。索引分配方法就是基于這種想法所形成的一種分配方法。它為每個(gè)文件分配一個(gè)索引塊(表)，再把分配給該文件的所有盤塊號(hào)都記錄在該索引塊中，因而該索引塊就是一個(gè)含有許多盤塊號(hào)的數(shù)組。在建立一個(gè)文件時(shí)，只需在為之建立的目錄項(xiàng)中填上指向該索引塊的指針。圖6-12 示出了磁盤空間的索引分配圖。 第六章文 件 管 理 圖6-12索引分配方式 1230567491011813141512171819162122232025262724293

54、03128countfile塊序號(hào)jeep19目錄9161102511119第六章文 件 管 理 2 2多級(jí)索引分配多級(jí)索引分配當(dāng)OS為一個(gè)大文件分配磁盤空間時(shí)，如果所分配出去的盤塊的盤塊號(hào)已經(jīng)裝滿一個(gè)索引塊時(shí)，OS便為該文件分配另一個(gè)索引塊，用于將以后繼續(xù)為之分配的盤塊號(hào)記錄于其中。依此類推，再通過(guò)鏈指針將各索引塊按序鏈接起來(lái)。顯然，當(dāng)文件太大，其索引塊太多時(shí)，這種方法是低效的。此時(shí)，應(yīng)為這些索引塊再建立一級(jí)索引，稱為第一級(jí)索引，即系統(tǒng)再分配一個(gè)索引塊，作為第一級(jí)索引的索引塊，將第一塊、第二塊等索引塊的盤塊號(hào)填入到此索引表中，這樣便形成了兩級(jí)索引分配方式。如果文件非常大時(shí)，還可用三級(jí)、四級(jí)索

55、引分配方式。 第六章文 件 管 理 圖6-13示出了兩級(jí)索引分配方式下各索引塊之間的鏈接情況。如果每個(gè)盤塊的大小為1 KB，每個(gè)盤塊號(hào)占4個(gè)字節(jié)，則在一個(gè)索引塊中可存放256個(gè)盤塊號(hào)。這樣，在兩級(jí)索引時(shí)， 最多可包含的存放文件的盤塊的盤塊號(hào)總數(shù)N = 256 256 = 64 K個(gè)盤塊號(hào)。由此可得出結(jié)論: 采用兩級(jí)索引時(shí)，所允許的文件最大長(zhǎng)度為64 MB。倘若盤塊的大小為4 KB，在采用單級(jí)索引時(shí)所允許的最大文件長(zhǎng)度為4 MB；而在采用兩級(jí)索引時(shí)所允許的最大文件長(zhǎng)度可達(dá)4 GB。 第六章文 件 管 理 圖6-13兩級(jí)索引分配 0121051062543563579851051062547403

56、5635711259853607401125主索引360第二級(jí)索引磁盤空間第六章文 件 管 理 3 3混合索引分配方式混合索引分配方式所謂混合索引分配方式，是指將多種索引分配方式相結(jié)合而形成的一種分配方式。例如，系統(tǒng)既采用了直接地址，又采用了一級(jí)索引分配方式，或兩級(jí)索引分配方式，甚至還采用了三級(jí)索引分配方式。這種混合索引分配方式已在UNIX系統(tǒng)中采用。在UNIX System 的索引結(jié)點(diǎn)中，共設(shè)置了13個(gè)地址項(xiàng)，即iaddr(0)iaddr(12)，如圖6-14所示。在BSD UNIX的索引結(jié)點(diǎn)中，共設(shè)置了13個(gè)地址項(xiàng)，它們都把所有的地址項(xiàng)分成兩類，即直接地址和間接地址。 第六章文 件 管 理

57、 圖6-14混合索引方式 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)，即用iaddr(0)iaddr(9)來(lái)存放直接地址。換言之，在這里的每項(xiàng)中所存放的是該文件數(shù)據(jù)所在盤塊的盤塊號(hào)。假如每個(gè)盤塊的大小為 4 KB，當(dāng)文件不

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

59、分配方式。系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的盤號(hào)。在采用二次間址方式時(shí)，文件最大長(zhǎng)度可達(dá)4 GB。同理，地址項(xiàng)iaddr(12)作為三次間接地址，其所允許的文件最大長(zhǎng)度可達(dá)4 TB。 第六章文 件 管 理 6.4目目 錄錄 管管 理理 通常，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，都要存儲(chǔ)大量的文件。為了能對(duì)這些文件實(shí)施有效的管理，必須對(duì)它們加以妥善組織，這主要是通過(guò)文件目錄實(shí)現(xiàn)的。文件目錄也是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識(shí)系統(tǒng)中的文件及其物理地址，供檢索時(shí)使用。對(duì)目錄管理的要求如下：(1) 實(shí)現(xiàn)“按名存取”，即用戶只須向系統(tǒng)提供所需訪問(wèn)文件的名字，便能快速準(zhǔn)確地找到指定文件在外存上的存儲(chǔ)位置。這是目錄管理中最

60、基本的功能，也是文件系統(tǒng)向用戶提供的最基本的服務(wù)。 第六章文 件 管 理 (2) 提高對(duì)目錄的檢索速度。通過(guò)合理地組織目錄結(jié)構(gòu)的方法，可加快對(duì)目錄的檢索速度，從而提高對(duì)文件的存取速度。這是在設(shè)計(jì)一個(gè)大、中型文件系統(tǒng)時(shí)所追求的主要目標(biāo)。(3) 文件共享。在多用戶系統(tǒng)中，應(yīng)允許多個(gè)用戶共享一個(gè)文件。這樣就須在外存中只保留一份該文件的副本，供不同用戶使用，以節(jié)省大量的存儲(chǔ)空間，并方便用戶和提高文件利用率。(4) 允許文件重名。系統(tǒng)應(yīng)允許不同用戶對(duì)不同文件采用相同的名字，以便于用戶按照自己的習(xí)慣給文件命名和使用文件。 第六章文 件 管 理 6.4.16.4.1文件控制塊和索引結(jié)點(diǎn)文件控制塊和索引結(jié)點(diǎn)1