2013秋季操作系統(tǒng)課件第6章

第六章文件管理6.1文件和文件系統(tǒng)6.2文件的邏輯結(jié)構(gòu)6.3外存分配方式6.4目錄管理6.5文件存儲空間的管理6.6文件共享與文件保護(hù)6.7數(shù)據(jù)一致性控制

6.1

文件和文件系統(tǒng)

6.1.1文件、記錄和數(shù)據(jù)項

1．?dāng)?shù)據(jù)項在文件系統(tǒng)中，數(shù)據(jù)項是最低級的數(shù)據(jù)組織形式，可把它分成以下兩種類型:

(1)基本數(shù)據(jù)項。這是用于描述一個對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(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ù)項的名字和類型兩者共同定義了一個數(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)使用諸如病歷號、姓名、性別、出生年月、身高、體重、血壓及病史等項。

在諸多記錄中，為了能惟一地標(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．文件文件是指由創(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個字符。用戶利用文件名來訪問文件。

此外，文件應(yīng)具有自己的屬性，屬性可以包括：

(1)文件類型。可以從不同的角度來規(guī)定文件的類型，如源文件、目標(biāo)文件及可執(zhí)行文件等。

(2)文件長度。文件長度指文件的當(dāng)前長度，長度的單位可以是字節(jié)、字或塊，也可能是最大允許的長度。

(3)文件的物理位置。該項屬性通常是用于指示文件在哪一個設(shè)備上及在該設(shè)備的哪個位置的指針。

(4)文件的建立時間。這是指文件最后一次的修改時間等。

圖6-1文件、記錄和數(shù)據(jù)項之間的層次關(guān)系

6.1.2文件類型和文件系統(tǒng)模型

1．文件類型為了便于管理和控制文件而將文件分成若干種類型。由于不同系統(tǒng)對文件的管理方式不同，因而它們對文件的分類方法也有很大差異。為了方便系統(tǒng)和用戶了解文件的類型，在許多OS中都把文件類型作為擴(kuò)展名而綴在文件名的后面，在文件名和擴(kuò)展名之間用“.”號隔開。下面是常用的幾種文件分類方法。

1)按用途分類根據(jù)文件的性質(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碼或漢字所組成的。

(2)目標(biāo)文件。這是指把源程序經(jīng)過相應(yīng)語言的編譯程序編譯過，但尚未經(jīng)過鏈接程序鏈接的目標(biāo)代碼所構(gòu)成的文件。它屬于二進(jìn)制文件。通常，目標(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ū)懙奈募?/p>

4)按組織形式和處理方式分類根據(jù)文件的組織形式和系統(tǒng)對其的處理方式，可將文件分為三類：

(1)普通文件：由ASCII碼或二進(jìn)制碼組成的字符文件。一般用戶建立的源程序文件、數(shù)據(jù)文件、目標(biāo)代碼文件及操作系統(tǒng)自身代碼文件、庫文件、實用程序文件等都是普通文件，它們通常存儲在外存儲設(shè)備上。

(2)目錄文件：由文件目錄組成的，用來管理和實現(xiàn)文件系統(tǒng)功能的系統(tǒng)文件，通過目錄文件可以對其它文件的信息進(jìn)行檢索。由于目錄文件也是由字符序列構(gòu)成，因此對其可進(jìn)行與普通文件一樣的種種文件操作。

(3)特殊文件：特指系統(tǒng)中的各類I/O設(shè)備。為了便于統(tǒng)一管理，系統(tǒng)將所有的輸入/輸出設(shè)備都視為文件，按文件方式提供給用戶使用，如目錄的檢索、權(quán)限的驗證等都與普通文件相似，只是對這些文件的操作是和設(shè)備驅(qū)動程序緊密相連的，系統(tǒng)將這些操作轉(zhuǎn)為對具體設(shè)備的操作。根據(jù)設(shè)備數(shù)據(jù)交換單位的不同，又可將特殊文件分為塊設(shè)備文件和字符設(shè)備文件。前者用于磁盤、光盤或磁帶等塊設(shè)備的I/O操作，而后者用于終端、打印機(jī)等字符設(shè)備的I/O操作。

2．文件系統(tǒng)模型圖6-2示出了文件系統(tǒng)的模型?？蓪⒃撃Ｐ头譃槿齻€層次，其最底層是對象及其屬性；中間層是對對象進(jìn)行操縱和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。

圖6-2文件系統(tǒng)模型

1)對象及其屬性文件管理系統(tǒng)管理的對象有：①

文件。它作為文件管理的直接對象。②

目錄。為了方便用戶對文件的存取和檢索，在文件系統(tǒng)中必須配置目錄，每個目錄項中，必須含有文件名及該文件所在的物理地址(或指針)。對目錄的組織和管理是方便用戶和提高對文件存取速度的關(guān)鍵。③

磁盤(磁帶)存儲空間。文件和目錄必定占用存儲空間，對這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對文件的存取速度。

2)對對象操縱和管理的軟件集合這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實現(xiàn)的，其中包括:對文件存儲空間的管理、對文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對文件讀和寫的管理，以及對文件的共享與保護(hù)等功能。

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．最基本的文件操作

(1)創(chuàng)建文件。在創(chuàng)建一個新文件時，系統(tǒng)首先要為新文件分配必要的外存空間，并在文件系統(tǒng)的目錄中，為之建立一個目錄項。目錄項中應(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)存中的(源)地址。為此，也同樣須先查找目錄，找到指定文件的目錄項，再利用目錄中的寫指針進(jìn)行寫操作。

(5)截斷文件。如果一個文件的內(nèi)容已經(jīng)陳舊而需要全部更新時，一種方法是將此文件刪除，再重新創(chuàng)建一個新文件。但如果文件名及其屬性均無改變時，則可采取另一種所謂的截斷文件的方法，此即將原有文件的長度設(shè)置為0，或者說是放棄原有的文件內(nèi)容。

(6)設(shè)置文件的讀/寫位置。前述的文件讀/寫操作都只提供了對文件順序存取的手段，即每次都是從文件的始端讀或?qū)憽ＴO(shè)置文件讀/寫位置的操作，用于設(shè)置文件讀/寫指針的位置，以便每次讀/寫文件時，不是從其始端而是從所設(shè)置的位置開始操作。也正因如此，才能改順序存取為隨機(jī)存取。

2．文件的“打開”和“關(guān)閉”操作當(dāng)前OS所提供的大多數(shù)對文件的操作，其過程大致都是這樣兩步:第一步是通過檢索文件目錄來找到指定文件的屬性及其在外存上的位置；第二步是對文件實施相應(yīng)的操作，如讀文件或?qū)懳募取．?dāng)用戶要求對一個文件實施多次讀/寫或其它操作時，每次都要從檢索目錄開始。為了避免多次重復(fù)地檢索目錄，在大多數(shù)OS中都引入了“打開”(open)這一文件系統(tǒng)調(diào)用，當(dāng)用戶第一次請求對某文件進(jìn)行操作時，先利用open系統(tǒng)調(diào)用將該文件打開。

所謂“打開”，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號(或稱為索引)返回給用戶。以后，當(dāng)用戶再要求對該文件進(jìn)行相應(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)用，可將這些調(diào)用分成若干類:最常用的一類是有關(guān)對文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者(文件主)、改變對文件的訪問權(quán)，以及查詢文件的狀態(tài)(包括文件類型、大小和擁有者以及對文件的訪問權(quán)等)；另一類是有關(guān)目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改變當(dāng)前目錄和工作目錄等；此外，還有用于實現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。

6.2文件的邏輯結(jié)構(gòu)

6.2.1文件邏輯結(jié)構(gòu)的類型

1．有結(jié)構(gòu)文件在記錄式文件中，每個記錄都用于描述實體集中的一個實體，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項。記錄的長度可分為定長和不定長兩類。

(1)定長記錄。這是指文件中所有記錄的長度都是相同的，所有記錄中的各數(shù)據(jù)項都處在記錄中相同的位置，具有相同的順序和長度。文件的長度用記錄數(shù)目表示。對定長記錄的處理方便、開銷小，所以這是目前較常用的一種記錄格式，被廣泛用于數(shù)據(jù)處理中。

(2)變長記錄。這是指文件中各記錄的長度不相同。產(chǎn)生變長記錄的原因，可能是由于一個記錄中所包含的數(shù)據(jù)項數(shù)目并不相同，如書的著作者、論文中的關(guān)鍵詞等；也可能是數(shù)據(jù)項本身的長度不定，例如，病歷記錄中的病因、病史；科技情報記錄中的摘要等。不論是哪一種，在處理前，每個記錄的長度是可知的。根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式來組織這些記錄，形成下述的幾種文件：

(1)順序文件。這是由一系列記錄按某種順序排列所形成的文件。其中的記錄通常是定長記錄，因而能用較快的速度查找文件中的記錄。

(2)索引文件。當(dāng)記錄為可變長度時，通常為之建立一張索引表，并為每個記錄設(shè)置一個表項，以加快對記錄檢索的速度。

(3)索引順序文件。這是上述兩種文件構(gòu)成方式的結(jié)合。它為文件建立一張索引表，為每一組記錄中的第一個記錄設(shè)置一個表項。

2．無結(jié)構(gòu)文件如果說大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫是采用有結(jié)構(gòu)的文件形式的話，則大量的源程序、可執(zhí)行文件、庫函數(shù)等，所采用的就是無結(jié)構(gòu)的文件形式，即流式文件。其長度以字節(jié)為單位。對流式文件的訪問，則是采用讀/寫指針來指出下一個要訪問的字符?？梢园蚜魇轿募醋鍪怯涗浭轿募囊粋€特例。在UNIX系統(tǒng)中，所有的文件都被看做是流式文件，即使是有結(jié)構(gòu)文件，也被視為流式文件，系統(tǒng)不對文件進(jìn)行格式處理。

6.2.2順序文件

1．邏輯記錄的排序文件是記錄的集合。文件中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進(jìn)行排列。一般地，可歸納為以下兩種情況：第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無關(guān)。通常的辦法是由時間來決定，即按存入時間的先后排列，最先存入的記錄作為第一個記錄，其次存入的為第二個記錄……，依此類推。第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)鍵字(詞)排列?？梢园搓P(guān)鍵詞的長短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。

對順序結(jié)構(gòu)文件可有更高的檢索效率，因為在檢索串結(jié)構(gòu)文件時，每次都必須從頭開始，逐個記錄地查找，直至找到指定的記錄，或查完所有的記錄為止。而對順序結(jié)構(gòu)文件，則可利用某種有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法來提高檢索效率。

2．對順序文件(SequentialFile)的讀/寫操作順序文件中的記錄可以是定長的，也可以是變長的。對于定長記錄的順序文件，如果已知當(dāng)前記錄的邏輯地址，便很容易確定下一個記錄的邏輯地址。在讀一個文件時，可設(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定長和變長記錄文件

3．順序文件的優(yōu)缺點順序文件的最佳應(yīng)用場合是在對諸記錄進(jìn)行批量存取時，即每次要讀或?qū)懸淮笈涗洉r。此時，對順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上，并能有效地工作。

在交互應(yīng)用的場合，如果用戶(程序)要求查找或修改單個記錄，為此系統(tǒng)便要去逐個地查找諸記錄。這時，順序文件所表現(xiàn)出來的性能就可能很差，尤其是當(dāng)文件較大時，情況更為嚴(yán)重。例如，有一個含有104個記錄的順序文件，如果對它采用順序查找法去查找一個指定的記錄，則平均需要查找5×103個記錄；如果是可變長記錄的順序文件，則為查找一個記錄所需付出的開銷將更大，這就限制了順序文件的長度。順序文件的另一個缺點是，如果想增加或刪除一個記錄都比較困難。為了解決這一問題，

可以為順序文件配置一個運(yùn)行記錄文件(LogFile)，或稱為事務(wù)文件(TransactionFile)，把試圖增加、刪除或修改的信息記錄于其中，規(guī)定每隔一定時間，例如4小時，將運(yùn)行記錄文件與原來的主文件加以合并，產(chǎn)生一個按關(guān)鍵字排序的新文件。

6.2.3索引文件對于定長記錄文件，如果要查找第i個記錄，可直接根據(jù)下式計算來獲得第i個記錄相對于第一個記錄首址的地址：

Ai=i×

L

然而，對于可變長度記錄的文件，要查找其第i個記錄時，須首先計算出該記錄的首地址。為此，須順序地查找每個記錄，從中獲得相應(yīng)記錄的長度Li，然后才能按下式計算出第i個記錄的首址。假定在每個記錄前用一個字節(jié)指明該記錄的長度，則

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

圖6-4索引文件的組織

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

圖6-5索引順序文件

6.2.5直接文件和哈希文件

1．直接文件采用前述幾種文件結(jié)構(gòu)對記錄進(jìn)行存取時，都須利用給定的記錄鍵值，先對線性表或鏈表進(jìn)行檢索，以找到指定記錄的物理地址。然而對于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換(Keytoaddresstransformation)。組織直接文件的關(guān)鍵，在于用什么方法進(jìn)行從記錄值到物理地址的轉(zhuǎn)換。

2．哈希(Hash)文件這是目前應(yīng)用最為廣泛的一種直接文件。它利用Hash函數(shù)(或稱散列函數(shù))，可將記錄鍵值轉(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-6

Hash文件的邏輯結(jié)構(gòu)

6.3外存分配方式

6.3.1連續(xù)分配

1．連續(xù)分配方式連續(xù)分配(ContinuousAllocation)要求為每一個文件分配一組相鄰接的盤塊。一組盤塊的地址定義了磁盤上的一段線性地址。例如，第一個盤塊的地址為b，則第二個盤塊的地址為b+1，第三個盤塊的地址為b+2……。通常，它們都位于一條磁道上，在進(jìn)行讀/寫時，不必移動磁頭，僅當(dāng)訪問到一條磁道的最后一個盤塊后，才需要移到下一條磁道，于是又去連續(xù)地讀/寫多個盤塊。在采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時的物理文件稱為順序文件。這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。為使系統(tǒng)能找到文件存放的地址，應(yīng)在目錄項的“文件物理地址”字段中，記錄該文件第一個記錄所在的盤塊號和文件長度(以盤塊數(shù)進(jìn)行計量)。圖6-7示出了連續(xù)分配的情況。圖中假定了記錄與盤塊的大小相同。Count文件的第一個盤塊號是0，文件長度為2，因此是在盤塊號為0和1的兩盤塊中存放文件1的數(shù)據(jù)。

圖6-7磁盤空間的連續(xù)分配

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

2．連續(xù)分配的主要優(yōu)缺點連續(xù)分配的主要優(yōu)點如下：

(1)順序訪問容易。訪問一個占有連續(xù)空間的文件非常容易。系統(tǒng)可從目錄中找到該順序文件所在的第一個盤塊號，從此開始順序地、逐個盤塊地往下讀/寫。連續(xù)分配也支持直接存取。例如，要訪問一個從b塊開始存放的文件中的第i個盤塊的內(nèi)容，就可直接訪問b+i號盤塊。

(2)順序訪問速度快。因為由連續(xù)分配所裝入的文件，其所占用的盤塊可能是位于一條或幾條相鄰的磁道上，這時，磁頭的移動距離最少，因此，這種對文件訪問的速度是幾種存儲空間分配方式中最高的一種。連續(xù)分配的主要缺點如下：

(1)要求有連續(xù)的存儲空間。要為每一個文件分配一段連續(xù)的存儲空間，這樣，便會產(chǎn)生出許多外部碎片，嚴(yán)重地降低了外存空間的利用率。如果是定期地利用緊湊方法來消除碎片，則又需花費(fèi)大量的機(jī)器時間。

(2)必須事先知道文件的長度。要將一個文件裝入一個連續(xù)的存儲區(qū)中，必須事先知道文件的大小，然后根據(jù)其大小，在存儲空間中找出一塊其大小足夠的存儲區(qū)，將文件裝入。在有些情況下，知道文件的大小是件非常容易的事，如可拷貝一個已存文件。但有時卻很難，在此情況下，只能靠估算。如果估計的文件大小比實際文件小，就可能因存儲空間不足而中止文件的拷貝，須再要求用戶重新估算，然后再次執(zhí)行。這樣，顯然既費(fèi)時又麻煩。這就促使用戶往往將文件長度估得比實際的大，甚至使所計算的文件長度比實際長度大得多，顯然，這會嚴(yán)重地浪費(fèi)外存空間。對于那些動態(tài)增長的文件，由于開始時文件很小，在運(yùn)行中逐漸增大，比如，這種增長要經(jīng)歷幾天、幾個月。在此情況下，即使事先知道文件的最終大小，在采用預(yù)分配存儲空間的方法時，顯然也將是很低效的，即它使大量的存儲空間長期地空閑著。

6.3.2鏈接分配

1．隱式鏈接在采用隱式鏈接分配方式時，在文件目錄的每個目錄項中，都須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。圖6-8中示出了一個占用5個盤塊的鏈接式文件。在相應(yīng)的目錄項中，指示了其第一個盤塊號是9，最后一個盤塊號是25。而在每個盤塊中都含有一個指向下一個盤塊的指針，如在第一個盤塊9中設(shè)置了第二個盤塊的盤塊號是16；在16號盤塊中又設(shè)置了第三個盤塊的盤塊號1。如果指針占用4個字節(jié)，對于盤塊大小為512字節(jié)的磁盤，則每個盤塊中只有508個字節(jié)可供用戶使用。

圖6-8磁盤空間的鏈接式分配

隱式鏈接分配方式的主要問題在于：它只適合于順序訪問，它對隨機(jī)訪問是極其低效的。如果要訪問文件所在的第i個盤塊，則必須先讀出文件的第一個盤塊……，就這樣順序地查找直至第i塊。當(dāng)i=100時，須啟動100次磁盤去實現(xiàn)讀盤塊的操作，平均每次都要花費(fèi)幾十毫秒?？梢?，隨機(jī)訪問的速度相當(dāng)?shù)汀４送?，只通過鏈接指針來將一大批離散的盤塊鏈接起來，其可靠性較差，因為只要其中的任何一個指針出現(xiàn)問題，都會導(dǎo)致整個鏈的斷開。

2．顯式鏈接這是指把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表在整個磁盤僅設(shè)置一張，如圖6-9所示。表的序號是物理盤塊號，從0開始，直至N-1；N為盤塊總數(shù)。在每個表項中存放鏈接指針，即下一個盤塊號。在該表中，凡是屬于某一文件的第一個盤塊號，或者說是每一條鏈的鏈?zhǔn)字羔標(biāo)鶎?yīng)的盤塊號，均作為文件地址被填入相應(yīng)文件的FCB的“物理地址”字段中。由于查找記錄的過程是在內(nèi)存中進(jìn)行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。由于分配給文件的所有盤塊號都放在該表中，故把該表稱為文件分配表FAT(FileAllocationTable)。

圖6-9顯式鏈接結(jié)構(gòu)

6.3.3FAT和NTFS技術(shù)

1．FAT12

1)以盤塊為基本分配單位早期MS-DOS操作系統(tǒng)所使用的是FAT12文件系統(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.2MB的軟盤，每個盤塊的大小為512B，在每個FAT中共含有2.4K個表項，由于每個FAT表項占12位，故FAT表占用3.6KB的存儲空間。

圖6-10

MS-DOS的文件物理結(jié)構(gòu)

現(xiàn)在我們來計算以盤塊為分配單位時，所允許的最大磁盤容量。由于每個FAT表項為12位，因此，在FAT表中最多允許有4096個表項，如果采用以盤塊作為基本分配單位，每個盤塊(也稱扇區(qū))的大小一般是512字節(jié)，那么，每個磁盤分區(qū)的容量為2MB(4096×512B)。同時，一個物理磁盤支持4個邏輯磁盤分區(qū)，所以相應(yīng)的磁盤最大容量僅為8MB。這對最早時期的硬盤還可應(yīng)付，但很快磁盤的容量就超過了8MB，F(xiàn)AT12是否還可繼續(xù)用呢，回答雖是肯定的，但需要引入一個新的分配單位——簇。

2)簇的基本概念為了適應(yīng)磁盤容量不斷增大的需要，在進(jìn)行盤塊分配時，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的扇區(qū)，在FAT中它是作為一個虛擬扇區(qū)，簇的大小一般是2n(n為整數(shù))個盤塊，在MS-DOS的實際運(yùn)用中，簇的容量可以僅有一個扇區(qū)(512B)、兩個扇區(qū)(1KB)、四個扇區(qū)(2KB)、八個扇區(qū)(4KB)等。一個簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)。例如，當(dāng)一個簇僅有一個扇區(qū)時，磁盤的最大容量為8MB；當(dāng)一個簇包含兩個扇區(qū)時，磁盤的最大容量可以達(dá)到16MB；當(dāng)一個簇包含了八個扇區(qū)時，磁盤的最大容量便可達(dá)到64MB。由上所述可以看出，以簇作為基本的分配單位所帶來的最主要的好處是，能適應(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ā)展的需要，其表現(xiàn)出來的主要問題是，對所允許的磁盤容量存在著嚴(yán)重的限制，通常只能是數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來提高所允許的最大磁盤容量，但隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎片也將隨之成倍地增加。此外，它只能支持8+3格式的文件名。

2．FAT16對FAT12所存在的問題進(jìn)行簡單的分析即可看出，其根本原因在于，F(xiàn)AT12表最多只允許4096個表項，亦即最多只能將一個磁盤分區(qū)分為4096個簇。這樣，隨著磁盤容量的增加，必定會引起簇的大小和簇內(nèi)碎片也隨之增加。由此可以得出解決方法，那就是增加FAT表的表項數(shù)，亦即應(yīng)增加FAT表的寬度，如果我們將FAT表的寬度增至16位，最大表項數(shù)將增至65536個，此時便能將一個磁盤分區(qū)分為65536(216)個簇。我們把具有16位表寬的FAT表稱為FAT16。在FAT16的每個簇中可以有的盤塊數(shù)為4、8、16、32直到64，由此得出FAT16可以管理的最大分區(qū)空間為216×64×512=2048MB。

由上述分析不難看出，F(xiàn)AT16對FAT12的局限性有所改善，但改善很有限。當(dāng)磁盤容量迅速增加時，如果再繼續(xù)使用FAT16，由此所形成的簇內(nèi)碎片所造成的浪費(fèi)也越大。例如，當(dāng)要求磁盤分區(qū)的大小為8GB時，則每個簇的大小達(dá)到128KB，這意味著內(nèi)部零頭最大可達(dá)到128KB。一般而言，對于1～4GB的硬盤來說，大約會浪費(fèi)10％～20％的空間。為了解決這一問題，微軟推出了FAT32。

3．FAT32如同存儲器管理中的分頁管理，所選擇的頁面越大，可能造成的頁內(nèi)零頭也會越大。為減少頁內(nèi)零頭就應(yīng)該選擇適當(dāng)大小的頁面。在這里，為了減小磁盤的簇內(nèi)零頭，也就應(yīng)當(dāng)選擇適當(dāng)大小的簇。問題是FAT16表的長度只有65535項，隨著磁盤容量的增加，簇的大小也必然會隨之增加，為了減少簇內(nèi)零頭，也就應(yīng)當(dāng)增加FAT表的長度。為此，需要再增加FAT表的寬度，這樣也就由FAT16演變?yōu)镕AT32。

FAT32是FAT系列文件系統(tǒng)的最后一個產(chǎn)品。每一簇在FAT表中的表項占據(jù)4字節(jié)(232)，F(xiàn)AT表可以表示4294967296項，即FAT32允許管理比FAT16更多的簇。這樣就允許在FAT32中采用較小的簇，F(xiàn)AT32的每個簇都固定為4KB，即每簇用8個盤塊代替FAT16的64個盤塊，每個盤塊仍為512字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的單個最大磁盤空間大到4KB×232=2TB。三種FAT類型的最大分區(qū)以及所對應(yīng)的塊的大小如圖6-11所示。

圖6-11FAT中簇的大小與最大分區(qū)的對應(yīng)關(guān)系

4．NTFS

1)NTFS新特征

NTFS(NewTechnologyFileSystem)是一個專門為WindowsNT開發(fā)的、全新的文件系統(tǒng)，并適用于Windows2000/XP/2003。NTFS具有許多新的特征：首先，它使用了64位磁盤地址，理論上可以支持2的64次方字節(jié)的磁盤分區(qū)；其次，在NTFS中可以很好地支持長文件名，單個文件名限制在255個字符以內(nèi)，全路徑名為32767個字符；第三，具有系統(tǒng)容錯功能，即在系統(tǒng)出現(xiàn)故障或差錯時，仍能保證系統(tǒng)正常運(yùn)行，這一點我們將在6.6節(jié)中介紹；第四，提供了數(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一樣，也是物理磁盤扇區(qū)的整數(shù)倍，即一個簇包含2n(n為整數(shù))個盤塊，簇的大小可由格式化命令或格式化程序按磁盤容量和應(yīng)用需求來確定，可以為512B、1KB、2KB……，最大可達(dá)64KB。對于小磁盤(≤512MB)，默認(rèn)簇大小為512字節(jié)；對于1GB磁盤，默認(rèn)簇大小為1KB；對于2GB磁盤，則默認(rèn)簇大小為4KB。事實上，為了在傳輸效率和簇內(nèi)碎片之間進(jìn)行折中，NTFS在大多數(shù)情況下都是使用4KB。

對于簇的定位，NTFS是采用邏輯簇號LCN(LogicalClusterNumber)和虛擬簇號VCN(VirtualClusterNumber)進(jìn)行的。LCN是以卷為單位，將整個卷中所有的簇按順序進(jìn)行簡單的編號，NTFS在進(jìn)行地址映射時，可以通過卷因子與LCN的乘積，便可算出卷上的物理字節(jié)偏移量，從而得到文件數(shù)據(jù)所在的物理磁盤地址。為了方便文件中數(shù)據(jù)的引用，NTFS還可以使用VCN，以文件為單位，將屬于某個文件的簇按順序進(jìn)行編號。只要知道了文件開始的簇地址，便可將VCN映射到LCN。

3)文件的組織在NTFS中，以卷為單位，將一個卷中的所有文件信息、目錄信息以及可用的未分配空間信息，都以文件記錄的方式記錄在一張主控文件表MFT(MasterFileTable)中。該表是NTFS卷結(jié)構(gòu)的中心，從邏輯上講，卷中的每個文件作為一條記錄，在MFT表中占有一行，其中還包括MFT自己的這一行。每行大小固定為1KB，每行稱為該行所對應(yīng)文件的元數(shù)據(jù)(metadata)，也稱為文件控制字。

在MFT表中，每個元數(shù)據(jù)將其所對應(yīng)文件的所有信息，包括文件的內(nèi)容等，都被組織在所對應(yīng)文件的一組屬性中。由于文件大小相差懸殊，其屬性所需空間大小也相差很大，因此，在MFT表中，對于元數(shù)據(jù)的1KB空間，可能記錄不下文件的全部信息。所以當(dāng)文件較小時，其屬性值所占空間也較小，可以將文件的所有屬性直接記錄在元數(shù)據(jù)中。而當(dāng)文件較大時，元數(shù)據(jù)僅記錄該文件的一部分屬性，其余屬性，如文件的內(nèi)容等，可以記錄到卷中的其它可用簇中，并將這些簇按其所記錄文件的屬性進(jìn)行分類，分別鏈接成多個隊列，將指向這些隊列的指針保存在元數(shù)據(jù)中。

6.3.4索引分配

1．單級索引分配鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題，但又出現(xiàn)了下述另外兩個問題：

(1)不能支持高效的直接存取。要對一個較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號。

(2)FAT需占用較大的內(nèi)存空間。由于一個文件所占用盤塊的盤塊號是隨機(jī)地分布在FAT中的，因而只有將整個FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個文件的所有盤塊號。當(dāng)磁盤容量較大時，F(xiàn)AT可能要占用數(shù)兆字節(jié)以上的內(nèi)存空間，這是令人難以接受的。事實上，在打開某個文件時，只需把該文件占用的盤塊的編號調(diào)入內(nèi)存即可，完全沒有必要將整個FAT調(diào)入內(nèi)存。為此，應(yīng)將每個文件所對應(yīng)的盤塊號集中地放在一起。索引分配方法就是基于這種想法所形成的一種分配方法。它為每個文件分配一個索引塊(表)，再把分配給該文件的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個含有許多盤塊號的數(shù)組。在建立一個文件時，只需在為之建立的目錄項中填上指向該索引塊的指針。圖6-12示出了磁盤空間的索引分配圖。

圖6-12索引分配方式

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

圖6-13示出了兩級索引分配方式下各索引塊之間的鏈接情況。如果每個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，則在一個索引塊中可存放256個盤塊號。這樣，在兩級索引時，

最多可包含的存放文件的盤塊的盤塊號總數(shù)N=256×256=64K個盤塊號。由此可得出結(jié)論:采用兩級索引時，所允許的文件最大長度為64MB。倘若盤塊的大小為4KB，在采用單級索引時所允許的最大文件長度為4MB；而在采用兩級索引時所允許的最大文件長度可達(dá)4GB。

圖6-13兩級索引分配

3．混合索引分配方式所謂混合索引分配方式，是指將多種索引分配方式相結(jié)合而形成的一種分配方式。例如，系統(tǒng)既采用了直接地址，又采用了一級索引分配方式，或兩級索引分配方式，甚至還采用了三級索引分配方式。這種混合索引分配方式已在UNIX系統(tǒng)中采用。在UNIXSystemⅤ的索引結(jié)點中，共設(shè)置了13個地址項，即iaddr(0)～iaddr(12)，如圖6-14所示。在BSDUNIX的索引結(jié)點中，共設(shè)置了13個地址項，它們都把所有的地址項分成兩類，即直接地址和間接地址。

圖6-14混合索引方式

1)直接地址為了提高對文件的檢索速度，在索引結(jié)點中可設(shè)置10個直接地址項，即用iaddr(0)～iaddr(9)來存放直接地址。換言之，在這里的每項中所存放的是該文件數(shù)據(jù)所在盤塊的盤塊號。假如每個盤塊的大小為

4KB，當(dāng)文件不大于40KB時，便可直接從索引結(jié)點中讀出該文件的全部盤塊號。

2)一次間接地址對于大、中型文件，只采用直接地址是不現(xiàn)實的。為此，可再利用索引結(jié)點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放1K個盤塊號，因而允許文件長達(dá)4MB。

3)多次間接地址當(dāng)文件長度大于4MB+40KB時(一次間址與10個直接地址項)，系統(tǒng)還須采用二次間址分配方式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號。在采用二次間址方式時，文件最大長度可達(dá)4GB。同理，地址項iaddr(12)作為三次間接地址，其所允許的文件最大長度可達(dá)4TB。

6.4目

錄

管

理

通常，在現(xiàn)代計算機(jī)系統(tǒng)中，都要存儲大量的文件。為了能對這些文件實施有效的管理，必須對它們加以妥善組織，這主要是通過文件目錄實現(xiàn)的。文件目錄也是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，供檢索時使用。對目錄管理的要求如下：

(1)實現(xiàn)“按名存取”，即用戶只須向系統(tǒng)提供所需訪問文件的名字，便能快速準(zhǔn)確地找到指定文件在外存上的存儲位置。這是目錄管理中最基本的功能，也是文件系統(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.1文件控制塊和索引結(jié)點

1．文件控制塊為了能對系統(tǒng)中的大量文件施以有效的管理，在文件控制塊中，通常應(yīng)含有三類信息，即基本信息、存取控制信息及使用信息。

1)基本信息類基本信息類包括:①

文件名，指用于標(biāo)識一個文件的符號名。在每個系統(tǒng)中，每一個文件都必須有惟一的名字，用戶利用該名字進(jìn)行存取。②

文件物理位置，指文件在外存上的存儲位置，它包括存放文件的設(shè)備名、文件在外存上的起始盤塊號、指示文件所占用的盤塊數(shù)或字節(jié)數(shù)的文件長度。③

文件邏輯結(jié)構(gòu)，指示文件是流式文件還是記錄式文件、記錄數(shù)；文件是定長記錄還是變長記錄等。④

文件的物理結(jié)構(gòu)，指示文件是順序文件，還是鏈接式文件或索引文件。

2)存取控制信息類存取控制信息類包括：文件主的存取權(quán)限、核準(zhǔn)用戶的存取權(quán)限以及一般用戶的存取權(quán)限。

3)使用信息類使用信息類包括:文件的建立日期和時間、文件上一次修改的日期和時間及當(dāng)前使用信息(這項信息包括當(dāng)前已打開該文件的進(jìn)程數(shù)、是否被其它進(jìn)程鎖住、文件在內(nèi)存中是否已被修改但尚未拷貝到盤上)。應(yīng)該說明，對于不同OS的文件系統(tǒng)，由于功能不同，可能只含有上述信息中的某些部分。圖6-15示出了MS-DOS中的文件控制塊，其中含有文件名、文件所在的第一個盤塊號、文件屬性、文件建立日期和時間及文件長度等。FCB的長度為32個字節(jié)，對于360KB的軟盤，總共可包含112個FCB，共占4KB的存儲空間。

圖6-15

MS-DOS的文件控制塊

2．索引結(jié)點

1)索引結(jié)點的引入文件目錄通常是存放在磁盤上的，當(dāng)文件很多時，文件目錄可能要占用大量的盤塊。在查找目錄的過程中，先將存放目錄文件的第一個盤塊中的目錄調(diào)入內(nèi)存，然后把用戶所給定的文件名與目錄項中的文件名逐一比較。若未找到指定文件，便再將下一個盤塊中的目錄項調(diào)入內(nèi)存。設(shè)目錄文件所占用的盤塊數(shù)為N，按此方法查找，則查找一個目錄項平均需要調(diào)入盤塊(N+1)/2次。假如一個FCB為64B，盤塊大小為1KB，則每個盤塊中只能存放16個FCB；若一個文件目錄中共有640個FCB，需占用40個盤塊，故平均查找一個文件需啟動磁盤20次。

稍加分析可以發(fā)現(xiàn)，在檢索目錄文件的過程中，只用到了文件名，僅當(dāng)找到一個目錄項(即其中的文件名與指定要查找的文件名相匹配)時，才需從該目錄項中讀出該文件的物理地址。而其它一些對該文件進(jìn)行描述的信息，在檢索目錄時一概不用。顯然，這些信息在檢索目錄時不需調(diào)入內(nèi)存。為此，在有的系統(tǒng)中，如UNIX系統(tǒng)，便采用了把文件名與文件描述信息分開的辦法，亦即，使文件描述信息單獨形成一個稱為索引結(jié)點的數(shù)據(jù)結(jié)構(gòu)，簡稱為i結(jié)點。在文件目錄中的每個目錄項僅由文件名和指向該文件所對應(yīng)的i結(jié)點的指針?biāo)鶚?gòu)成。在UNIX系統(tǒng)中一個目錄僅占16個字節(jié)，其中14個字節(jié)是文件名，2個字節(jié)為i結(jié)點指針。在1KB的盤塊中可做64個目錄項，這樣，為找到一個文件，可使平均啟動磁盤次數(shù)減少到原來的1/4，大大節(jié)省了系統(tǒng)開銷。圖6-16示出了UNIX的文件目錄項。

圖6-16

UNIX的文件目錄

0

13?14

15

2)磁盤索引結(jié)點這是存放在磁盤上的索引結(jié)點。每個文件有惟一的一個磁盤索引結(jié)點，它主要包括以下內(nèi)容：

(1)文件主標(biāo)識符，即擁有該文件的個人或小組的標(biāo)識符。

(2)文件類型，包括正規(guī)文件、目錄文件或特別文件。

(3)文件存取權(quán)限，指各類用戶對該文件的存取權(quán)限。

(4)文件物理地址，每一個索引結(jié)點中含有13個地址項，即iaddr(0)～iaddr(12)，它們以直接或間接方式給出數(shù)據(jù)文件所在盤塊的編號。

(5)文件長度，指以字節(jié)為單位的文件長度。

(6)文件連接計數(shù)，表明在本文件系統(tǒng)中所有指向該(文件的)文件名的指針計數(shù)。

(7)文件存取時間，指本文件最近被進(jìn)程存取的時間、最近被修改的時間及索引結(jié)點最近被修改的時間。

3)內(nèi)存索引結(jié)點這是存放在內(nèi)存中的索引結(jié)點。當(dāng)文件被打開時，要將磁盤索引結(jié)點拷貝到內(nèi)存的索引結(jié)點中，便于以后使用。在內(nèi)存索引結(jié)點中又增加了以下內(nèi)容：

(1)索引結(jié)點編號，用于標(biāo)識內(nèi)存索引結(jié)點。

(2)狀態(tài)，指示i結(jié)點是否上鎖或被修改。

(3)訪問計數(shù)，每當(dāng)有一進(jìn)程要訪問此i結(jié)點時，將該訪問計數(shù)加1，訪問完再減1。

(4)文件所屬文件系統(tǒng)的邏輯設(shè)備號。

(5)鏈接指針。設(shè)置有分別指向空閑鏈表和散列隊列的指針。

6.4.2目錄結(jié)構(gòu)

1．單級目錄結(jié)構(gòu)這是最簡單的目錄結(jié)構(gòu)。在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項，目錄項中含文件名、文件擴(kuò)展名、文件長度、文件類型、文件物理地址以及其它文件屬性。此外，為表明每個目錄項是否空閑，又設(shè)置了一個狀態(tài)位。單級目錄如圖6-17所示。

圖6-17單級目錄

每當(dāng)要建立一個新文件時，必須先檢索所有的目錄項，以保證新文件名在目錄中是惟一的。然后再從目錄表中找出一個空白目錄項，填入新文件的文件名及其它說明信息，并置狀態(tài)位為1。刪除文件時，先從目錄中找到該文件的目錄項，回收該文件所占用的存儲空間，然后再清除該目錄項。單級目錄的優(yōu)點是簡單且能實現(xiàn)目錄管理的基本功能——按名存取，但卻存在下述一些缺點：

(1)查找速度慢。對于稍具規(guī)模的文件系統(tǒng)，會擁有數(shù)目可觀的目錄項，致使為找到一個指定的目錄項要花費(fèi)較多的時間。對于一個具有N個目錄項的單級目錄，為檢索出一個目錄項，平均需查找N/2個目錄項。

(2)不允許重名。在一個目錄表中的所有文件，都不能與另一個文件有相同的名字。然而，重名問題在多道程序環(huán)境下卻又是難以避免的；即使在單用戶環(huán)境下，當(dāng)文件數(shù)超過數(shù)百個時，也難于記憶。

(3)不便于實現(xiàn)文件共享。通常，每個用戶都有自己的名字空間或命名習(xí)慣。因此，應(yīng)當(dāng)允許不同用戶使用不同的文件名來訪問同一個文件。然而，單級目錄卻要求所有用戶都用同一個名字來訪問同一文件。簡言之，單級目錄只能滿足對目錄管理的四點要求中的第一點，

因而，它只能適用于單用戶環(huán)境。

2．兩級目錄為了克服單級目錄所存在的缺點，可以為每一個用戶建立一個單獨的用戶文件目錄UFD(UserFileDirectory)。這些文件目錄具有相似的結(jié)構(gòu)，它由用戶所有文件的文件控制塊組成。此外，在系統(tǒng)中再建立一個主文件目錄MFD(MasterFileDirectory)；在主文件目錄中，每個用戶目錄文件都占有一個目錄項，其目錄項中包括用戶名和指向該用戶目錄文件的指針。如圖6-18所示，圖中的主目錄中示出了三個用戶名，即Wang、Zhang和Gao。

圖6-18兩級目錄結(jié)構(gòu)

在兩級目錄結(jié)構(gòu)中，如果用戶希望有自己的用戶文件目錄UFD，可以請求系統(tǒng)為自己建立一個用戶文件目錄；如果自己不再需要UFD，也可以請求系統(tǒng)管理員將它撤消。在有了UFD后，用戶可以根據(jù)自己的需要創(chuàng)建新文件。每當(dāng)此時，OS只需檢查該用戶的UFD，判定在該UFD中是否已有同名的另一個文件。若有，用戶必須為新文件重新命名；若無，便在UFD中建立一個新目錄項，將新文件名及其有關(guān)屬性填入目錄項中，并置其狀態(tài)位為“1”。當(dāng)用戶要刪除一個文件時，OS也只需查找該用戶的UFD，從中找出指定文件的目錄項，

在回收該文件所占用的存儲空間后，將該目錄項刪除。

兩級目錄結(jié)構(gòu)基本上克服了單級目錄的缺點，并具有以下優(yōu)點：

(1)提高了檢索目錄的速度。如果在主目錄中有n個子目錄，每個用戶目錄最多為m個目錄項，則為查找一指定的目錄項，最多只需檢索n+m個目錄項。但如果是采用單級目錄結(jié)構(gòu)，則最多需檢索n×m個目錄項。假定n=m，可以看出，采用兩級目錄可使檢索效率提高n/2倍。

(2)在不同的用戶目錄中，可以使用相同的文件名。只要在用戶自己的UFD中，每一個文件名都是惟一的。例如，用戶Wang可以用Test來命名自己的一個測試文件；而用戶Zhang則可用Test來命名自己的一個并不同于Wang的Test的測試文件。

(3)不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個共享文件。采用兩級目錄結(jié)構(gòu)也存在一些問題。該結(jié)構(gòu)雖然能有效地將多個用戶隔開，在各用戶之間完全無關(guān)時，這種隔離是一個優(yōu)點；但當(dāng)多個用戶之間要相互合作去完成一個大任務(wù)，且一用戶又需去訪問其他用戶的文件時，這種隔離便成為一個缺點，因為這種隔離會使諸用戶之間不便于共享文件。

3．多級目錄結(jié)構(gòu)

1)目錄結(jié)構(gòu)對于大型文件系統(tǒng)，通常采用三級或三級以上的目錄結(jié)構(gòu)，以提高對目錄的檢索速度和文件系統(tǒng)的性能。多級目錄結(jié)構(gòu)又稱為樹型目錄結(jié)構(gòu)，主目錄在這里被稱為根目錄，把數(shù)據(jù)文件稱為樹葉，其它的目錄均作為樹的結(jié)點。圖

6-19示出了多級目錄結(jié)構(gòu)。圖中，用方框代表目錄文件，圓圈代表數(shù)據(jù)文件。在該樹型目錄結(jié)構(gòu)中，主(根)目錄中有三個用戶的總目錄項A、B和C。在B項所指出的B用戶的總目錄B中，又包括三個分目錄F、E和D，其中每個分目錄中又包含多個文件。如B目錄中的F分目錄中，包含J和N兩個文件。為了提高文件系統(tǒng)的靈活性，應(yīng)允許在一個目錄文件中的目錄項既是作為目錄文件的FCB，又是數(shù)據(jù)文件的FCB，這一信息可用目錄項中的一位來指示。例如，在圖6-19中，用戶A的總目錄中，目錄項A是目錄文件的FCB，而目錄項B和D則是數(shù)據(jù)文件的FCB。

圖6-19多級目錄結(jié)構(gòu)

2)路徑名在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通路。在該路徑上從樹的根(即主目錄)開始，把全部目錄文件名與數(shù)據(jù)文件名依次地用“/”連接起來，即構(gòu)成該數(shù)據(jù)文件的路徑名(pathname)。系統(tǒng)中的每一個文件都有惟一的路徑名。例如，在圖6-19中用戶B為訪問文件J，應(yīng)使用其路徑名/B/F/J來訪問。

3)當(dāng)前目錄(CurrentDirectory)當(dāng)一個文件系統(tǒng)含有許多級時，每訪問一個文件，都要使用從樹根開始直到樹葉(數(shù)據(jù)文件)為止的、包括各中間節(jié)點(目錄)名的全路徑名。這是相當(dāng)麻煩的事，同時由于一個進(jìn)程運(yùn)行時所訪問的文件大多僅局限于某個范圍，因而非常不便?；谶@一點，可為每個進(jìn)程設(shè)置一個“當(dāng)前目錄”，又稱為“工作目錄”。進(jìn)程對各文件的訪問都相對于“當(dāng)前目錄”而進(jìn)行。此時各文件所使用的路徑名，只需從當(dāng)前目錄開始，逐級經(jīng)過中間的目錄文件，最后到達(dá)要訪問的數(shù)據(jù)文件。把這一路徑上的全部目錄文件名與數(shù)據(jù)文件名用“/”連接形成路徑名。如用戶B的當(dāng)前目錄是F，則此時文件J的相對路徑名僅是J本身。這樣，把從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名，稱為相對路徑名(relativepathname)；而把從樹根開始的路徑名稱為絕對路徑名(absolutepathname)。

就多級目錄較兩級目錄而言，其查詢速度更快，同時層次結(jié)構(gòu)更加清晰，能夠更加有效地進(jìn)行文件的管理和保護(hù)。在多級目錄中，不同性質(zhì)、不同用戶的文件可以構(gòu)成不同的目錄子樹，不同層次、不同用戶的文件分別呈現(xiàn)在系統(tǒng)目錄樹中的不同層次或不同子樹中，可以容易地賦予不同的存取權(quán)限。但是在多級目錄中查找一個文件，需要按路徑名逐級訪問中間節(jié)點，這就增加了磁盤訪問次數(shù)，無疑將影響查詢速度。目前，大多數(shù)操作系統(tǒng)如UNIX、Linux和Windows系列都采用了多級目錄結(jié)構(gòu)。

4．增加和刪除目錄在樹型目錄結(jié)構(gòu)中，用戶可為自己建立UFD，并可再創(chuàng)建子目錄。在用戶要創(chuàng)建一個新文件時，只需查看在自己的UFD及其子目錄中有無與新建文件相同的文件名。若無，便可在UFD或其某個子目錄中增加一個新目錄項。在樹型目錄中，對于一個已不再需要的目錄，應(yīng)如何刪除其目錄項，須視情況而定。這時，如果所要刪除的目錄是空的，即在該目錄中已不再有任何文件，就可簡單地將該目錄項刪除，使它在其上一級目錄中對應(yīng)的目錄項為空；如果要刪除的目錄不空，即其中尚有幾個文件或子目錄，則可采用下述兩種方法處理：

(1)不刪除非空目錄。當(dāng)目錄(文件)不空時，不能將其刪除，而為了刪除一個非空目錄，必須先刪除目錄中的所有文件，使之先成為空目錄，然后再予以刪除。如果目錄中還包含有子目錄，還必須采取遞歸調(diào)用方式來將其刪除，在MS-DOS中就是采用這種刪除方式。

(2)可刪除非空目錄。當(dāng)要刪除一個目錄時，如果在該目錄中還包含有文件，則目錄中的所有文件和子目錄也同時被刪除。上述兩種方法實現(xiàn)起來都比較容易，第二種方法則更為方便，但比較危險。因為整個目錄結(jié)構(gòu)雖然用一條命令即能刪除，但如果是一條錯誤命令，其后果則可能很嚴(yán)重。

6.4.3目錄查詢技術(shù)

1．線性檢索法線性檢索法又稱為順序檢索法。在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄中找到指名文件的目錄項。在樹型目錄中，用戶提供的文件名是由多個文件分量名組成的路徑名，此時須對多級目錄進(jìn)行查找。假定用戶給定的文件路徑名是/usr/ast/mbox，則查找/usr/ast/mbox文件的過程如圖6-20所示。

圖6-20查找/usr/ast/mbox的步驟

具體查找過程說明如下：首先，系統(tǒng)應(yīng)先讀入第一個文件分量名usr，用它與根目錄文件(或當(dāng)前目錄文件)中各目錄項中的文件名順序地進(jìn)行比較，從中找出匹配者，并得到匹配項的索引結(jié)點號6，再從6號索引結(jié)點中得知usr目錄文件放在132號盤塊中，將該盤塊內(nèi)容讀入內(nèi)存。接著，系統(tǒng)再將路徑名中的第二個文件分量名ast讀入，用它與放在132號盤塊中的第二級目錄文件中各目錄項的文件名順序進(jìn)行比較，又找到匹配項，從中得到ast的目錄文件放在26號索引結(jié)點中，再從26號索引結(jié)點中得知/usr/ast是存放在496號盤塊中，再讀入496號盤塊。

然后，系統(tǒng)又將該文件的第三個分量名mbox讀入，用它與第三級目錄文件/usr/ast中各目錄項中的文件名進(jìn)行比較，最后得到/usr/ast/mbox的索引結(jié)點號為60，即在60號索引結(jié)點中存放了指定文件的物理地址。目錄查詢操作到此結(jié)束。如果在順序查找過程中發(fā)現(xiàn)有一個文件分量名未能找到，則應(yīng)停止查找，并返回“文件未找到”信息。

2．Hash方法在6.2.5節(jié)中曾介紹了Hash文件。如果我們建立了一張Hash索引文件目錄，便可利用Hash方法進(jìn)行查詢，即系統(tǒng)利用用戶提供的文件名并將它變換為文件目錄的索引值，再利用該索引值到目錄中去查找，這將顯著地提高檢索速度。順便指出，在現(xiàn)代操作系統(tǒng)中，通常都提供了模式匹配功能，即在文件名中使用了通配符“*”、“？”等。對于使用了通配符的文件名，系統(tǒng)此時便無法利用Hash方法檢索目錄，因此，這時系統(tǒng)還是需要利用線性查找法查找目錄。

在進(jìn)行文件名的轉(zhuǎn)換時，有可能把n個不同的文件名轉(zhuǎn)換為相同的Hash值，即出現(xiàn)了所謂的“沖突”。一種處理此“沖突”的有效規(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．空閑表法

1)空閑表空閑表法屬于連續(xù)分配方式，它與內(nèi)存的動態(tài)分配方式雷同，它為每個文件分配一塊連續(xù)的存儲空間，即系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個空閑表項，其中包括表項序號、該空閑區(qū)的第一個盤塊號、該區(qū)的空閑盤塊數(shù)等信息。再將所有空閑區(qū)按其起始盤塊號遞增的次序排列，如圖6-21所示。

圖6-21空閑盤塊表

2)存儲空間的分配與回收空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序地檢索空閑表的各表項，直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進(jìn)程)，同時修改空閑表。系統(tǒng)在對用戶所釋放的存儲空間進(jìn)行回收時，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并。應(yīng)該說明，在內(nèi)存分配上，雖然很少采用連續(xù)分配方式，然而在外存的管理中，由于這種分配方式具有較高的分配速度，可減少訪問磁盤的I/O頻率，故它在諸多分配方式中仍占有一席之地。例如，在前面所介紹的對換方式中，對對換空間一般都采用連續(xù)分配方式。對于文件系統(tǒng)，當(dāng)文件較小(1～4個盤塊)時，仍采用連續(xù)分配方式，為文件分配相鄰接的幾個盤塊；當(dāng)文件較大時，便采用離散分配方式。

2．空閑鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈所用基本元素的不同，可把鏈表分成兩種形式：空閑盤塊鏈和空閑盤區(qū)鏈。

(1)空閑盤塊鏈。這是將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。當(dāng)用戶因創(chuàng)建文件而請求分配存儲空間時，系統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶。當(dāng)用戶因刪除文件而釋放存儲空間時，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。這種方法的優(yōu)點是用于分配和回收一個盤塊的過程非常簡單，但在為一個文件分配盤塊時，可能要重復(fù)操作多次。

(2)空閑盤區(qū)鏈。這是將磁盤上的所有空閑盤區(qū)(每個盤區(qū)可包含若干個盤塊)拉成一條鏈。在每個盤區(qū)上除含有用于指示下一個空閑盤區(qū)的指針外，還應(yīng)有能指明本盤區(qū)大小(盤塊數(shù))的信息。分配盤區(qū)的方法與內(nèi)存的動態(tài)分區(qū)分配類似，通常采用首次適應(yīng)算法。在回收盤區(qū)時，同樣也要將回收區(qū)與相鄰接的空閑盤區(qū)相合并。在采用首次適應(yīng)算法時，為了提高對空閑盤區(qū)的檢索速度，可以采用顯式鏈接方法，亦即，在內(nèi)存中為空閑盤區(qū)建立一張鏈表。6.5.2位示圖法

1．位示圖位示圖是利用二進(jìn)制的一位來表示磁盤中一個盤塊的使用情況。當(dāng)其值為“0”時，表示對應(yīng)的盤塊空閑；為“1”時，表示已分配。有的系統(tǒng)把“0”作為盤塊已分配的標(biāo)志，把“1”作為空閑標(biāo)志。(它們在本質(zhì)上是相同的，都是用一位的兩種狀態(tài)來標(biāo)志空閑和已分配兩種情況。)磁盤上的所有盤塊都有一個二進(jìn)制位與之對應(yīng)，這樣，由所有盤塊所對應(yīng)的位構(gòu)成一個集合，稱為位示圖。通常可用m×n個位數(shù)來構(gòu)成位示圖，并使m×n等于磁盤的總塊數(shù)，如圖6-22所示。位示圖也可描述為一個二維數(shù)組map：

Varmap:arrayofbit；圖6-22位示圖

123456789101112131415161110001110010011020001111110000111311100011111100004

16

2．盤塊的分配根據(jù)位示圖進(jìn)行盤塊分配時，可分三步進(jìn)行：

(1)順序掃描位示圖，從中找出一個或一組其值為“0”的二進(jìn)制位(“0”表示空閑時)。

(2)將所找到的一個或一組二進(jìn)制位轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算：b=n(i-1)+j式中，n代表每行的位數(shù)。(3)修改位示圖，令map[i,j]=1。

3．盤塊的回收盤塊的回收分兩步：

(1)將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為：i=(b-1)DIVn+1j=(b-1)MODn+1

(2)修改位示圖。令map[i,j]=0。這種方法的主要優(yōu)點是，從位示圖中很容易找到一個或一組相鄰接的空閑盤塊。例如，我們需要找到6個相鄰接的空閑盤塊，這只需在位示圖中找出6個其值連續(xù)為“0”的位即可。此外，由于位示圖很小，占用空間少，因而可將它保存在內(nèi)存中，進(jìn)而使在每次進(jìn)行盤區(qū)分配時，無需首先把盤區(qū)分配表讀入內(nèi)存，從而節(jié)省了許多磁盤的啟動操作。因此，位示圖常用于微型機(jī)和小型機(jī)中，如CP/M、Apple-DOS等OS中。6.5.3成組鏈接法

1．空閑盤塊的組織

(1)空閑盤塊號棧用來存放當(dāng)前可用的一組空閑盤塊的盤塊號(最多含100個號)，以及棧中尚有的空閑盤塊號數(shù)N。順便指出，N還兼作棧頂指針用。例如，當(dāng)N=100時，它指向S.free(99)。由于棧是臨界資源，每次只允許一個進(jìn)程去訪問，故系統(tǒng)為棧設(shè)置了一把鎖。圖6-23左部示出了空閑盤塊號棧的結(jié)構(gòu)。其中，S.free(0)是棧底，棧滿時的棧頂為S.free(99)。圖6-23空閑盤塊的成組鏈接法

(2)文件區(qū)中的所有空閑盤塊被分成若干個組，比如，將每100個盤塊作為一組。假定盤上共有10000個盤塊，每塊大小為1