計算機操作系統(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文件存儲空間的管理文件存儲空間的管理6.6文件共享與文件保護文件共享與文件保護6.7數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 第六章文 件 管 理 6.1文件和文件系統(tǒng)文件和文件系統(tǒng) 6.1.16.1.1文件、記錄和數(shù)據(jù)項文件、記錄和數(shù)據(jù)項1 1數(shù)據(jù)項數(shù)據(jù)項在文件系統(tǒng)中，數(shù)據(jù)項是最低級的數(shù)據(jù)組織形式，可把它分成以下兩種類型:(1) 基本數(shù)據(jù)項。這是用于描述一個對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱

2、為數(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ù)項的名字和類型兩者共同定義了一個數(shù)據(jù)項

3、的“型”。而表征一個實體在數(shù)據(jù)項上的數(shù)據(jù)則稱為“值”。例如，學(xué)號/30211、姓名/王有年、性別/男等。 第六章文 件 管 理 2 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、，為了能惟一地標(biāo)識一個記錄，必須在一個記錄的各個數(shù)據(jù)項中，確定出一個或幾個數(shù)據(jù)項，把它們的集合稱為關(guān)鍵字(key)?；蛘哒f，關(guān)鍵字是惟一能標(biāo)識一個記錄的數(shù)據(jù)項。通常，只需用一個數(shù)據(jù)項作為關(guān)鍵字。例如，前面的病歷號或?qū)W號便可用來從諸多記錄中標(biāo)識出惟一的一個記錄。然而有時找不到這樣的數(shù)據(jù)項，只好把幾個數(shù)據(jù)項定為能在諸多記錄中惟一地標(biāo)識出某個記錄的關(guān)鍵字。 第六章文 件 管 理 3 3文件文件文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。在有結(jié)構(gòu)的文件中，文件由若干個相關(guān)記錄組成；而無結(jié)構(gòu)文件則被看成是一個字符流。文件在文件系統(tǒng)中是一個最大的數(shù)據(jù)單位，它

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

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

7、質(zhì)和用途的不同，可將文件分為三類:(1) 系統(tǒng)文件。這是指由系統(tǒng)軟件構(gòu)成的文件。大多數(shù)的系統(tǒng)文件只允許用戶調(diào)用，但不允許用戶去讀，更不允許修改；有的系統(tǒng)文件不直接對用戶開放。(2) 用戶文件。指由用戶的源代碼、目標(biāo)文件、可執(zhí)行文件或數(shù)據(jù)等所構(gòu)成的文件。用戶將這些文件委托給系統(tǒng)保管。(3) 庫文件。這是由標(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)過相應(yīng)語言的編譯程序編譯過，但尚未經(jīng)過鏈接程序鏈接的目標(biāo)代碼所構(gòu)成的文件。它屬于二進制文件。通常，目標(biāo)文件所使用的后綴名是“.obj”。(3) 可執(zhí)行文件。這是指把編譯后所產(chǎn)生的目標(biāo)代碼再經(jīng)過鏈接程序鏈接后所形成的文件。 第六章文 件 管 理 3) 按存取控制屬性分類根據(jù)系統(tǒng)管理員或用戶所規(guī)定的存取控制屬性，可將文件分為三類：(1) 只執(zhí)行文件。該類文件只允許被核準(zhǔn)的用戶調(diào)用執(zhí)行，既不允許讀，更不允許寫。(2) 只讀文件。該類文件只允許文件主及被核準(zhǔn)的用戶去讀，但不允許寫。(3) 讀寫文件。這是指允許文件主和被核準(zhǔn)的用戶去讀或?qū)懙奈募?第六章

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

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

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

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

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

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

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

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

17、件的文件名、改變文件的擁有者(文件主)、改變對文件的訪問權(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) 6.2.16.2.1文件邏輯結(jié)構(gòu)的類型文件邏輯結(jié)構(gòu)的類型1 1有結(jié)構(gòu)文件有結(jié)構(gòu)文件在記錄式文件中，每個記錄都用于描述實體集中的一個實體，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項。記錄的長度可分為定長和不定長兩類。(1) 定長記錄。這是指文件中所有記錄的長度都是相同的，

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

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

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

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

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

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

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

25、。 第六章文 件 管 理 6.2.36.2.3索引文件索引文件對于定長記錄文件，如果要查找第i個記錄，可直接根據(jù)下式計算來獲得第i個記錄相對于第一個記錄首址的地址： Ai = i L 然而，對于可變長度記錄的文件，要查找其第i個記錄時，須首先計算出該記錄的首地址。為此，須順序地查找每個記錄，從中獲得相應(yīng)記錄的長度Li，然后才能按下式計算出第i個記錄的首址。假定在每個記錄前用一個字節(jié)指明該記錄的長度，則 10iiiiiLA第六章文 件 管 理 可見，對于定長記錄，除了可以方便地實現(xiàn)順序存取外，還可較方便地實現(xiàn)直接存取。然而，對于變長記錄就較難實現(xiàn)直接存取了，因為用直接存取方法來訪問變長記錄文件中

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

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

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

29、記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址。但為了能實現(xiàn)文件存儲空間的動態(tài)分配，通常由Hash函數(shù)所求得的并非是相應(yīng)記錄的地址，而是指向一目錄表相應(yīng)表目的指針，該表目的內(nèi)容指向相應(yīng)記錄所在的物理塊，如圖6-6所示。例如，若令K為記錄鍵值，用A作為通過Hash函數(shù)H的轉(zhuǎn)換所形成的該記錄在目錄表中對應(yīng)表目的位置，則有關(guān)系A(chǔ)=H(K)。通常，把Hash函數(shù)作為標(biāo)準(zhǔn)函數(shù)存于系統(tǒng)中，供存取文件時調(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)要求為每一個文件分配一組相鄰接的盤塊。一組盤塊的地址定義了磁盤上的一段線性地址。例如，第一個盤塊的地址為b，則第二個盤塊的地址為b+1，第三個盤塊的地址為b+2。通常，它們都位于一條磁道上，在進行讀/寫時，不必移動磁頭，僅當(dāng)訪問到一條磁道的最后一個盤塊后，才需要移到下一條磁道，于是又去連續(xù)地讀/寫多個盤塊。第六章文 件 管 理 在采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時的物理文件稱為順序文件。這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。為使系統(tǒng)能找到文件存

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46、AT表中的表項占據(jù)4字節(jié)(232)，F(xiàn)AT表可以表示4 294 967 296項，即FAT32允許管理比FAT16更多的簇。這樣就允許在FAT32中采用較小的簇，F(xiàn)AT32的每個簇都固定為4 KB，即每簇用8個盤塊代替FAT16的64個盤塊，每個盤塊仍為512字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的單個最大磁盤空間大到4 KB232 = 2 TB。三種FAT類型的最大分區(qū)以及所對應(yīng)的塊的大小如圖6-11所示。 第六章文 件 管 理 圖6-11 FAT中簇的大小與最大分區(qū)的對應(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)是一個專門為Windows NT開發(fā)的、全新的文件系統(tǒng)，并適用于Windows 2000/XP/2003。NTFS具有許多新的特征：首先，它使用了64位磁盤地址，理論上可以支持2的64次方字節(jié)的磁盤分區(qū)；其次，在NTFS中可以很好地支持長文件名，單個文件名限制在255個字符以內(nèi)，全路徑名為32 767個字符；第三，具有系統(tǒng)容錯功能，即在系統(tǒng)出現(xiàn)故障或差錯時，仍能保證系統(tǒng)正常運行，這一點我們將在6.6節(jié)中介紹

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

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

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

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

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

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

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

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

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

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

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

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

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