操作系統(tǒng)chapter6課件

1、第六章文件管理第六章文件管理第六章文件管理 6.1 文件和文件系統(tǒng)6.2 文件邏輯結(jié)構(gòu)6.3 外存分配方式6.4 目錄管理6.5 文件存儲(chǔ)空間的管理6.6 文件共享和保護(hù)6.7 數(shù)據(jù)一致性控制第六章文件管理 6.1 文件和文件系統(tǒng)對(duì)于計(jì)算機(jī)處理和存放的大量信息,因內(nèi)存容量有限且無(wú)法長(zhǎng)期保存,故信息總是以文件的形式存放在輔助存儲(chǔ)器上,當(dāng)需要的時(shí)候再將它們調(diào)入內(nèi)存。操作系統(tǒng)中負(fù)責(zé)管理和存取文件信息的軟件機(jī)構(gòu)被稱為文件管理系統(tǒng)。用戶通過(guò)文件管理系統(tǒng)就可以“按名存取”方便地使用文件,而無(wú)需了解存儲(chǔ)設(shè)備的硬件特征和存取過(guò)程。對(duì)于計(jì)算機(jī)處理和存放的大量信息,因內(nèi)存容量有限且無(wú)法長(zhǎng)期保存 文件管理任務(wù)任務(wù)：

2、把存儲(chǔ)、檢索、共享和保護(hù)文件的手段，提供給用戶，以方便用戶及提高資源利用。功能：分配與管理外存提供合適的存儲(chǔ)方法文件共享，保護(hù)解決沖突 文件管理任務(wù)任務(wù)：把存儲(chǔ)、檢索、共享和保護(hù)文件的手段，提供6.1 文件和文件系統(tǒng) 文件系統(tǒng)是用戶與外存的接口。文件系統(tǒng)=文件管理程序（文件和目錄的集合）+它所管理的全部文件。文件系統(tǒng)的管理功能，是通過(guò)把管理的程序和數(shù)據(jù)組織成一系列文件的方法實(shí)現(xiàn)的。文件是指具有文件名的若干相關(guān)元素的集合。6.1 文件和文件系統(tǒng) 文件系統(tǒng)是用戶與外存的接口。1數(shù)據(jù)項(xiàng)在文件系統(tǒng)中，數(shù)據(jù)項(xiàng)是最低級(jí)的數(shù)據(jù)組織形式，可把它分成以下兩種類型:(1)基本數(shù)據(jù)項(xiàng)。這是用于描述一個(gè)對(duì)象的某種屬性

3、的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，又稱為數(shù)據(jù)元素或字段。 (2) 組合數(shù)據(jù)項(xiàng)。它是由若干個(gè)基本數(shù)據(jù)項(xiàng)組成的，簡(jiǎn)稱組項(xiàng)?；緮?shù)據(jù)項(xiàng)除了數(shù)據(jù)名外，還應(yīng)有數(shù)據(jù)類型。1數(shù)據(jù)項(xiàng)在文件系統(tǒng)中，數(shù)據(jù)項(xiàng)是最低級(jí)的數(shù)據(jù)組織形式，可把它2記錄記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對(duì)象在某方面的屬性。一個(gè)記錄應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需要描述對(duì)象的哪個(gè)方面。而一個(gè)對(duì)象，由于他所處的環(huán)境不同可把他作為不同的對(duì)象。在諸多記錄中，為了能惟一地標(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)。2記錄記錄是一組相關(guān)

4、數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對(duì)象在某方面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ù)單位，它描述了一個(gè)對(duì)象集。3文件文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的3文件例如，可以將一個(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)文件。windows 系統(tǒng)中，

5、可采用長(zhǎng)文件名(255個(gè)字符)。3文件例如，可以將一個(gè)班的學(xué)生記錄作為一個(gè)文件。一個(gè)文件必許多操作系統(tǒng)支持兩部分文件名，兩部分之間用句號(hào)加以分隔。在句號(hào)后面的部分稱作文件擴(kuò)展名，它通常給出了與文件有關(guān)的一些信息。在MS-DOS中文件名由1-8個(gè)字符和1-3個(gè)字符的可選擴(kuò)展名組成。在UNIX中，如果使用擴(kuò)展名，則其長(zhǎng)度完全由用戶決定，甚至一個(gè)文件之中可以含兩個(gè)或多個(gè)部分的擴(kuò)展名。 3文件許多操作系統(tǒng)支持兩部分文件名，兩部分之間用句號(hào)加以分隔。在句一些典型的文件擴(kuò)展名擴(kuò)展名含義file.bak備份文件file.cC源程序file.f77Fortran 77程序file.gifCompuserve

6、圖形轉(zhuǎn)換格式圖像file.hlp幫助文件file.html萬(wàn)維網(wǎng)超文本標(biāo)記語(yǔ)言文檔file.mpg用MPEG標(biāo)準(zhǔn)編碼的電影file.o目標(biāo)文件(編譯器輸出，但未連接) file.psPostscript文件file.tex用于TEX格式化程序的輸入file.txt一般文檔文件file.zip壓縮存檔一些典型的文件擴(kuò)展名擴(kuò)展名含義file.bak備份文件fil3文件每個(gè)文件都有文件名和數(shù)據(jù)。此外，所有操作系統(tǒng)還給文件賦以其他信息，比如，文件創(chuàng)建日期、文件長(zhǎng)度等等。我們把額外的項(xiàng)稱為文件屬性(attribute)。不同系統(tǒng)的屬性差別很大。下面列出了一些可能的屬性，但其他的屬性也存在。然而，每種屬性

7、都在某個(gè)系統(tǒng)中使用。3文件每個(gè)文件都有文件名和數(shù)據(jù)。此外，所有操作系統(tǒng)還給文件3文件(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è)位置的指針。(4) 文件的建立時(shí)間。這是指文件最后一次的修改時(shí)間等。3文件(1) 文件類型?？梢詮牟煌慕嵌葋?lái)規(guī)定文件的類型，域含義保護(hù)誰(shuí)能訪問(wèn)該文件，以何種方式訪問(wèn)口令訪問(wèn)該文件所需口令創(chuàng)建者文件創(chuàng)建者的ID擁有者當(dāng)前擁有者只讀標(biāo)志0表示讀寫，1表示

8、只讀隱藏標(biāo)志0表示正常，1表示不在列表中顯示系統(tǒng)標(biāo)志0表示正常文件，1表示系統(tǒng)文件存檔標(biāo)志0表示已備份過(guò)，1表示需要備份ASCII/二進(jìn)制0表示ASCII文件，1表示二進(jìn)制文件隨機(jī)存取標(biāo)志0表示只能順序存取，1表示隨機(jī)存取域含義保護(hù)誰(shuí)能訪問(wèn)該文件，以何種方式訪問(wèn)口令訪問(wèn)該文件所需口臨時(shí)標(biāo)志0表示正常，1表示在進(jìn)程退出時(shí)刪除文件鎖標(biāo)志0表示未鎖，非零表示已鎖記錄長(zhǎng)度一條記錄的字節(jié)數(shù)關(guān)鍵字位置每條記錄中關(guān)鍵字偏移關(guān)鍵字長(zhǎng)度關(guān)鍵字域的字節(jié)數(shù) 創(chuàng)建時(shí)間文件創(chuàng)建的日期和時(shí)間最后存取時(shí)間文件最后存取的日期和時(shí)間最后修改時(shí)間文件最后修改的日期和時(shí)間當(dāng)前長(zhǎng)度文件字節(jié)數(shù)最大長(zhǎng)度文件最大允許字節(jié)數(shù)臨時(shí)標(biāo)志0表示正

9、常，1表示在進(jìn)程退出時(shí)刪除文件鎖標(biāo)志0表示未文件記錄1記錄2記錄n數(shù)據(jù)項(xiàng)1數(shù)據(jù)項(xiàng)2數(shù)據(jù)項(xiàng)n文件記錄1記錄2記錄n數(shù)據(jù)項(xiàng)1數(shù)據(jù)項(xiàng)2數(shù)據(jù)項(xiàng)n6.1.2文件類型和文件系統(tǒng)模型1文件類型文件的分類是為了更好地管理和使用，要科學(xué)地分門別類，對(duì)不同的文件進(jìn)行不同的管理。這樣，不僅提高了文件的存取速度，對(duì)文件的共享和保護(hù)也有利。由于不同系統(tǒng)對(duì)文件的管理方式不同，因而它們對(duì)文件的分類方法也有很大差異。下面是常用的幾種文件分類方法。6.1.2文件類型和文件系統(tǒng)模型1文件類型1) 按用途分類根據(jù)文件的性質(zhì)和用途的不同，可分為:（1）系統(tǒng)文件：由系統(tǒng)軟件構(gòu)成的文件。（2）用戶文件：用戶委托文件系統(tǒng)保存的文件。由用戶

10、的源代碼、目標(biāo)文件、可執(zhí)行文件或數(shù)據(jù)等構(gòu)成。（3）庫(kù)文件：由系統(tǒng)提供給用戶使用的各種標(biāo)準(zhǔn)過(guò)程、函數(shù)和應(yīng)用程序文件。（可以使用，不能修改）1) 按用途分類根據(jù)文件的性質(zhì)和用途的不同，可分為:2) 按文件中數(shù)據(jù)的形式分類按文件中數(shù)據(jù)的形式分類，可分為三類：（1）源文件：由源程序和數(shù)據(jù)構(gòu)成的文件。（2）目標(biāo)文件：把源程序經(jīng)過(guò)相應(yīng)語(yǔ)言的編譯程序編譯過(guò)，但尚未經(jīng)過(guò)鏈接程序的目標(biāo)代碼所構(gòu)成的文件。（3）可執(zhí)行文件：把編譯后所產(chǎn)生的目標(biāo)代碼再經(jīng)過(guò)鏈接程序鏈接后所形成的文件。2) 按文件中數(shù)據(jù)的形式分類按文件中數(shù)據(jù)的形式分類，可分3) 按存取控制屬性分類根據(jù)存取控制屬性，可將文件分為三類：(1) 只執(zhí)行文件。

11、該類文件只允許被核準(zhǔn)的用戶調(diào)用執(zhí)行，既不允許讀，更不允許寫。(2) 只讀文件。該類文件只允許文件主及被核準(zhǔn)的用戶去讀，但不允許寫。(3) 讀寫文件。這是指允許文件主和被核準(zhǔn)的用戶去讀或?qū)懙奈募?) 按存取控制屬性分類根據(jù)存取控制屬性，可將文件分為三類：4) 按組織形式和處理方式分類根據(jù)文件的組織形式和處理方式，可將文件分為：(1) 普通文件：由ASCII碼或二進(jìn)制碼組成的字符文件。(2) 目錄文件：由文件目錄組成的，用來(lái)管理和實(shí)現(xiàn)文件系統(tǒng)功能的系統(tǒng)文件，通過(guò)目錄文件可以對(duì)其它文件的信息進(jìn)行檢索。(3) 特殊文件：特指系統(tǒng)中的各類I/O設(shè)備。為了便于統(tǒng)一管理，系統(tǒng)將所有的輸入/輸出設(shè)備都視為文

12、件，按文件方式提供給用戶使用。4) 按組織形式和處理方式分類根據(jù)文件的組織形式和處理方式，2文件系統(tǒng)模型可將該模型分為三個(gè)層次，其最底層是對(duì)象及其屬性；中間層是對(duì)對(duì)象進(jìn)行操縱和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。2文件系統(tǒng)模型可將該模型分為三個(gè)層次，其最底層是對(duì)象及其屬1) 對(duì)象及其屬性文件管理系統(tǒng)管理的對(duì)象有： 文件。它作為文件管理的直接對(duì)象。 目錄。為了方便用戶對(duì)文件的存取和檢索，在文件系統(tǒng)中必須配置目錄，每個(gè)目錄項(xiàng)中，必須含有文件名及該文件所在的物理地址(或指針)。 磁盤(磁帶)存儲(chǔ)空間。文件和目錄必定占用存儲(chǔ)空間，對(duì)這部分空間的有效管理，不僅能提高外存的利用率，而且能提高

13、對(duì)文件的存取速度。1) 對(duì)象及其屬性文件管理系統(tǒng)管理的對(duì)象有：2) 對(duì)對(duì)象操縱和管理的軟件集合這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實(shí)現(xiàn)的，其中包括: 對(duì)文件存儲(chǔ)空間的管理、對(duì)文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對(duì)文件讀和寫的管理，以及對(duì)文件的共享與保護(hù)等功能。 2) 對(duì)對(duì)象操縱和管理的軟件集合這是文件管理系統(tǒng)的核心部3) 文件系統(tǒng)的接口為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用戶提供兩種類型的接口:(1) 命令接口。 這是指作為用戶與文件系統(tǒng)交互的接口。 用戶可通過(guò)鍵盤終端鍵入命令，取得文件系統(tǒng)的服務(wù)。(2) 程序接口。這是指作為用戶程序與文件系統(tǒng)的接口

14、。用戶程序可通過(guò)系統(tǒng)調(diào)用來(lái)取得文件系統(tǒng)的服務(wù)。3) 文件系統(tǒng)的接口為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用6.1.3文件操作1最基本的文件操作創(chuàng)建文件。在創(chuàng)建一個(gè)新文件時(shí)，系統(tǒng)首先要為新文件分配必要的外存空間，并在文件系統(tǒng)的目錄中，為之建立一個(gè)目錄項(xiàng)。目錄項(xiàng)中應(yīng)記錄新文件的文件名及其在外存的地址等屬性。創(chuàng)建文件實(shí)質(zhì)是建立文件的FCB6.1.3文件操作1最基本的文件操作（1）創(chuàng)建文件create（文件名，訪問(wèn)權(quán)限，（，最大長(zhǎng)度）（1）檢查參數(shù)的合法性（2）檢查同一目錄下有無(wú)重名文件（3）在目錄中有無(wú)空閑位置（4）填寫目錄項(xiàng)內(nèi)容： 文件名，用戶名等，存取權(quán)限，長(zhǎng)度置零，（，首址）（5）返回（1）創(chuàng)

15、建文件create（文件名，訪問(wèn)權(quán)限，（，最大長(zhǎng)度）(2) 刪除文件當(dāng)已不再需要某文件時(shí)，可將它從文件系統(tǒng)中刪除。在刪除時(shí)，系統(tǒng)應(yīng)先從目錄中找到要?jiǎng)h除文件的目錄項(xiàng)，使之成為空項(xiàng)，然后回收該文件所占用的存儲(chǔ)空間。刪除文件時(shí)要撤銷FCB(2) 刪除文件當(dāng)已不再需要某文件時(shí)，可將它從文件系統(tǒng)中刪除(3) 讀文件在讀一個(gè)文件時(shí)，須在相應(yīng)系統(tǒng)調(diào)用中給出文件名和應(yīng)讀入的內(nèi)存目標(biāo)地址。read（文件名，（文件內(nèi)位置），要讀的長(zhǎng)度，內(nèi)存目的地址）（1）檢查長(zhǎng)度是否為正整數(shù)（2）根據(jù)文件名查找目錄，確定該文件在目錄中的位置。（3）根據(jù)隱含參數(shù)中的進(jìn)程主和目錄中該文件的存儲(chǔ)權(quán)限數(shù)據(jù)，檢查是否有權(quán)讀？(3) 讀文件

16、在讀一個(gè)文件時(shí)，須在相應(yīng)系統(tǒng)調(diào)用中給出文件名和（4）由文件內(nèi)位置與要讀的長(zhǎng)度計(jì)算最末位置，將其與目錄中的文件長(zhǎng)度比較。（5）根據(jù)參數(shù)中的位置、長(zhǎng)度和目錄中的映射信息，確定塊號(hào)、塊數(shù)、塊內(nèi)位移與長(zhǎng)度。（6）根據(jù)下一塊號(hào)讀塊至內(nèi)存緩沖區(qū)（7）根據(jù)塊內(nèi)位移長(zhǎng)度取出要讀的內(nèi)容，送至參數(shù)中的內(nèi)存目的地址（8）根據(jù)塊內(nèi)長(zhǎng)度或起始?jí)K號(hào)+塊數(shù)，確定還讀下一塊嗎？同時(shí)確定下一塊塊號(hào)（9）返回（4）由文件內(nèi)位置與要讀的長(zhǎng)度計(jì)算最末位置，將其與目錄中的文(4) 寫文件在寫一個(gè)文件時(shí)，須在相應(yīng)系統(tǒng)調(diào)用中給出該文件名及該文件在內(nèi)存中的(源)地址。為此，也同樣須先查找目錄，找到指定文件的目錄項(xiàng)，再利用目錄中的寫指針進(jìn)行寫

17、操作。 (4) 寫文件在寫一個(gè)文件時(shí)，須在相應(yīng)系統(tǒng)調(diào)用中給出該文件名(5) 截?cái)辔募绻粋€(gè)文件的內(nèi)容已經(jīng)陳舊而需要全部更新時(shí)，一種方法是將此文件刪除，再重新創(chuàng)建一個(gè)新文件。但如果文件名及其屬性均無(wú)改變時(shí)，則可采取另一種所謂的截?cái)辔募姆椒?，此即將原有文件的長(zhǎng)度設(shè)置為0，或者說(shuō)是放棄原有的文件內(nèi)容。(5) 截?cái)辔募绻粋€(gè)文件的內(nèi)容已經(jīng)陳舊而需要全部更新時(shí)，(6) 設(shè)置文件的讀/寫位置前述的文件讀/寫操作都只提供了對(duì)文件順序存取的手段，即每次都是從文件的始端讀或?qū)?。設(shè)置文件讀/寫位置的操作，用于設(shè)置文件讀/寫指針的位置，以便每次讀/寫文件時(shí)，不是從其始端而是從所設(shè)置的位置開始操作。也正因如此，

18、才能改順序存取為隨機(jī)存取。(6) 設(shè)置文件的讀/寫位置前述的文件讀/寫操作都只提供了對(duì)2文件的“打開”和“關(guān)閉”操作當(dāng)用戶要求對(duì)一個(gè)文件實(shí)施多次讀/寫或其它操作時(shí)，每次都要從檢索目錄開始。使檢索開銷很大。為了避免多次重復(fù)地檢索目錄，在大多數(shù)OS中都引入了“打開”(open)這一文件系統(tǒng)調(diào)用，當(dāng)用戶第一次請(qǐng)求對(duì)某文件進(jìn)行操作時(shí)，先利用open系統(tǒng)調(diào)用將該文件打開。2文件的“打開”和“關(guān)閉”操作當(dāng)用戶要求對(duì)一個(gè)文件實(shí)施多次2文件的“打開”和“關(guān)閉”操作所謂“打開”，是指系統(tǒng)將指名文件的屬性從外存拷貝到內(nèi)存打開文件表的一個(gè)表目中，并將該表目的編號(hào)(或稱為索引)返回給用戶。以后，當(dāng)用戶再要求對(duì)該文件進(jìn)

19、行相應(yīng)的操作時(shí)，便可利用系統(tǒng)所返回的索引號(hào)向系統(tǒng)提出操作請(qǐng)求。如果用戶已不再需要對(duì)該文件實(shí)施相應(yīng)的操作時(shí)，可利用“關(guān)閉”(close)系統(tǒng)調(diào)用來(lái)關(guān)閉此文件，OS將會(huì)把該文件從打開文件表中的表目上刪除掉。2文件的“打開”和“關(guān)閉”操作所謂“打開”，是指系統(tǒng)將指名3其它文件操作OS都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，最常用的一類是有關(guān)對(duì)文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的屬性；另一類是有關(guān)目錄的，如創(chuàng)建一個(gè)目錄，刪除一個(gè)目錄，改變當(dāng)前目錄和工作目錄等；此外，還有用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對(duì)文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。3其它文件操作OS都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，最常6

20、.2文件的邏輯結(jié)構(gòu)文件組織的兩種觀點(diǎn)用戶觀點(diǎn)（邏輯結(jié)構(gòu)）：研究的是用戶思維中的抽象文件，也叫邏輯文件。其目的是為用戶提供一種結(jié)構(gòu)清晰、使用簡(jiǎn)便的邏輯組織。實(shí)現(xiàn)觀點(diǎn)（物理結(jié)構(gòu)）：研究的是存儲(chǔ)在物理設(shè)備介質(zhì)上的實(shí)際文件，即物理文件。其目的是選擇一些性能良好、設(shè)備利用率高的物理結(jié)構(gòu)。系統(tǒng)按此和外部設(shè)備打交道，控制信息的傳輸。6.2文件的邏輯結(jié)構(gòu)文件組織的兩種觀點(diǎn) 6.2.1文件邏輯結(jié)構(gòu)的類型1.有結(jié)構(gòu)的文件 有結(jié)構(gòu)的文件是指由若干個(gè)相關(guān)的記錄構(gòu)成的文件，又稱記錄式文件。 文件是記錄的集合. 每個(gè)記錄由彼此相關(guān)的域構(gòu)成。記錄可按順序編號(hào)為記錄1，記錄2，記錄n。如果文件中所有記錄的長(zhǎng)度都相同，則這種文

21、件為定長(zhǎng)記錄文件。 定長(zhǎng)記錄文件的長(zhǎng)度 = 記錄個(gè)數(shù)*記錄長(zhǎng)度。 變長(zhǎng)記錄文件的長(zhǎng)度為各記錄長(zhǎng)度之和。 6.2.1文件邏輯結(jié)構(gòu)的類型1.有結(jié)構(gòu)的文件 1.有結(jié)構(gòu)的文件根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式來(lái)組織這些記錄，形成下述的幾種文件：(1) 順序文件。這是由一系列記錄按某種順序排列所形成的文件。其中的記錄通常是定長(zhǎng)記錄。 (2) 索引文件。當(dāng)記錄為可變長(zhǎng)度時(shí)，通常為之建立一張索引表，并為每個(gè)記錄設(shè)置一個(gè)表項(xiàng)。(3) 索引順序文件。這是上述兩種文件構(gòu)成方式的結(jié)合。它為文件建立一張索引表，為每一組記錄中的第一個(gè)記錄設(shè)置一個(gè)表項(xiàng)。 1.有結(jié)構(gòu)的文件根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式

22、來(lái)2無(wú)結(jié)構(gòu)文件對(duì)大量的源程序、可執(zhí)行文件、庫(kù)函數(shù)等，所采用的就是無(wú)結(jié)構(gòu)的文件形式，即流式文件。其長(zhǎng)度以字節(jié)為單位。對(duì)流式文件的訪問(wèn)，則是采用讀寫指針來(lái)指出下一個(gè)要訪問(wèn)的字符。可以把流式文件看作是記錄式文件的一個(gè)特例。在UNIX系統(tǒng)中，所有的文件都被看作是流式文件；即使是有結(jié)構(gòu)文件，也被視為流式文件；系統(tǒng)不對(duì)文件進(jìn)行格式處理。 2無(wú)結(jié)構(gòu)文件對(duì)大量的源程序、可執(zhí)行文件、庫(kù)函數(shù)等，所采用的6.2.2順序文件1邏輯記錄的排序文件是記錄的集合。文件中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進(jìn)行排列。一般地，可歸納為以下兩種情況： 第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無(wú)關(guān)。 第二種情況是

23、順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)鍵字(詞)排列。6.2.2順序文件1邏輯記錄的排序2對(duì)順序文件的讀/寫操作順序文件中的記錄可以是定長(zhǎng)的，也可以是變長(zhǎng)的。定長(zhǎng)記錄： 讀指針rptr指向下一次讀出的記錄地址； 寫指針wptr指向下一次寫入的記錄地址。 讀完指針做相應(yīng)修改:Rptr:=Rptr + L 寫完指針做相應(yīng)修改:Wptr:=Wptr + L變長(zhǎng)記錄：對(duì)于變長(zhǎng)記錄的順序文件. 讀完rptr:=rptr+Li2對(duì)順序文件的讀/寫操作順序文件中的記錄可以是定長(zhǎng)的，也可操作系統(tǒng)chapter6課件3. 順序文件的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：方便對(duì)記錄進(jìn)行批量存取時(shí)，此外，也只有順序文件才能存儲(chǔ)在磁帶上，并能有效

24、地工作。缺點(diǎn)：要求查找或修改單個(gè)記錄，系統(tǒng)要逐個(gè)地查找諸記錄。增加或刪除一個(gè)記錄較困難。3. 順序文件的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：方便對(duì)記錄進(jìn)行批量存取時(shí)，此外6.2.3 索引文件 對(duì)于定長(zhǎng)記錄文件，如果要查找第i個(gè)記錄，則第i個(gè)記錄的首地址為： Ai=iL 對(duì)于可變長(zhǎng)度記錄的文件，要查找其第i個(gè)記錄時(shí)，須順序地查找每個(gè)記錄，從中獲得相應(yīng)記錄的長(zhǎng)度Li。6.2.3 索引文件 對(duì)于定長(zhǎng)記錄文件，如果對(duì)于變長(zhǎng)記錄，用直接存取方法來(lái)訪問(wèn)文件中的一個(gè)記錄是十分低效的。為了解決這一問(wèn)題，可為變長(zhǎng)記錄文件建立一張索引表，對(duì)主文件中的每個(gè)記錄，在索引表中設(shè)有一個(gè)相應(yīng)的表項(xiàng)，用于記錄該記錄的長(zhǎng)度L及指向該記錄的指針(指向

25、該記錄在邏輯地址空間的首址)。6.2.3 索引文件 對(duì)于變長(zhǎng)記錄，用直接存取方法來(lái)訪問(wèn)文件中的一個(gè)記錄是十分低效 索引文件的組織 索引文件的組織 6.2.4索引順序文件索引順序文件是順序文件和索引文件相結(jié)合的產(chǎn)物。它將順序文件中的所有記錄分為若干個(gè)組；為順序文件建立一張索引表，在索引表中為每組中的第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指向該記錄的指針。6.2.4索引順序文件索引順序文件是順序文件和索引文件相結(jié) 索引順序文件 索引順序文件 6.2.5 直接文件和哈希文件 1. 直接文件 對(duì)于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的

26、物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換。組織直接文件的關(guān)鍵， 在于用什么方法進(jìn)行從記錄值到物理地址的轉(zhuǎn)換。 6.2.5 直接文件和哈希文件 1. 直接文件 哈希(Hash)文件利用Hash函數(shù)(或稱散列函數(shù))，可將記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址。但為了能實(shí)現(xiàn)文件存儲(chǔ)空間的動(dòng)態(tài)分配，通常由Hash函數(shù)所求得的并非是相應(yīng)記錄的地址，而是指向一目錄表相應(yīng)表目的指針，該表目的內(nèi)容指向相應(yīng)記錄所在的物理塊。2. 哈希(Hash)文件 哈希(Hash)文件利用Hash函數(shù)(或稱散列函數(shù))，可將記 Hash文件的邏輯結(jié)構(gòu)fHash函數(shù)目錄表鍵值 Hash文件的邏輯結(jié)構(gòu)fHash函數(shù)目錄表鍵

27、值6.3外存分配方式磁盤是一種可按指定的塊地址進(jìn)行信息存取的設(shè)備。對(duì)存儲(chǔ)在磁盤上的文件，既可采用順序存取方式，又可采用隨機(jī)存取方式。 采用不同的分配方式，會(huì)形成不同的文件物理結(jié)構(gòu)連續(xù)分配順序式文件結(jié)構(gòu)鏈接分配鏈接式文件結(jié)構(gòu)索引分配索引式文件結(jié)構(gòu)6.3外存分配方式磁盤是一種可按指定的塊地址進(jìn)行信息存取的連續(xù)分配要求為每一個(gè)文件分配一組相鄰接的盤塊。在采用連續(xù)分配方式時(shí)，可把邏輯文件中的記錄順序地存儲(chǔ)到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱為順序文件。 6.4.1 連續(xù)分配連續(xù)分配要求為每一個(gè)文件分配一組相鄰接的盤塊。 6.4.11230567491011813

28、141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr153mail216list293f72目錄trf123056749101181314151217181916 2. 連續(xù)分配的主要優(yōu)缺點(diǎn)優(yōu)點(diǎn): () 順序訪問(wèn)容易；支持順序存取和隨機(jī)存??；() 順序存取速度快；所需的磁盤尋道次數(shù)和尋道時(shí)間最少。 缺點(diǎn): () 要求有連接的存儲(chǔ)空間；外部碎片問(wèn)題() 必須事先知道文件的長(zhǎng)度； 文件不能動(dòng)態(tài)增長(zhǎng)；預(yù)留空間； 不利于文件插入和刪除 2. 連續(xù)分配的主要優(yōu)缺點(diǎn)優(yōu)點(diǎn): 6.3.2鏈接分配一個(gè)文件的信息存放

29、在若干不連續(xù)的物理塊中，各塊之間通過(guò)指針鏈接。 優(yōu)點(diǎn)：提高了磁盤空間利用率,不存在外部碎片問(wèn)題有利于文件插入和刪除有利于文件動(dòng)態(tài)擴(kuò)充 缺點(diǎn)： 存取速度慢，不適于隨機(jī)存取更多的尋道次數(shù)和尋道時(shí)間6.3.2鏈接分配一個(gè)文件的信息存放在若干不連續(xù)的物理塊中1隱式鏈接在采用隱式鏈接分配方式時(shí)，在文件目錄的每個(gè)目錄項(xiàng)中，都須含有指向鏈接文件第一個(gè)盤塊和最后一個(gè)盤塊的指針。而在每個(gè)盤塊中都含有一個(gè)指向下一個(gè)盤塊的指針。1隱式鏈接在采用隱式鏈接分配方式時(shí)，在文件目錄的每個(gè)目錄項(xiàng)文件名 始址 末址jeep 9 25文件目錄01234567891011121314151617181920212223242526

30、272829303111016-125磁盤空間的鏈接式分配文件名 始址 末址jeep 2顯式鏈接把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表在整個(gè)磁盤僅設(shè)置一張，在每個(gè)表項(xiàng)中存放鏈接指針，即下一個(gè)盤塊號(hào)。在該表中，凡是屬于某一文件的第一個(gè)盤塊號(hào)，或者說(shuō)是每一條鏈的鏈?zhǔn)字羔標(biāo)鶎?duì)應(yīng)的盤塊號(hào)，均作為文件地址被填入相應(yīng)文件的FCB的“物理地址”字段中。由于分配給文件的所有盤塊號(hào)都放在該表中，故把該表稱為文件分配表FAT。 2顯式鏈接把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存 顯式鏈接結(jié)構(gòu) 顯式鏈接結(jié)構(gòu) 6.3.3 FAT和NTFS技術(shù)微軟公司的操作系統(tǒng)早期采用的都是FAT文件

31、系統(tǒng)格式包括：FAT12，F(xiàn)AT16，F(xiàn)AT32最近廣泛采用NTFS文件系統(tǒng)格式Linux操作系統(tǒng)主要采用efx2, efx3文件系統(tǒng)格式6.3.3 FAT和NTFS技術(shù)微軟公司的操作系統(tǒng)早期采用1FAT121) 以盤塊為基本分配單位 早期MS-DOS操作系統(tǒng)所使用的是FAT12文件系統(tǒng)，在每個(gè)分區(qū)中都配有兩張文件分配表FAT1和FAT2，在FAT的每個(gè)表項(xiàng)中存放下一個(gè)盤塊號(hào)，它實(shí)際上是用于盤塊之間的鏈接的指針，通過(guò)它可以將一個(gè)文件的所有的盤塊鏈接起來(lái)，而將文件的第一個(gè)盤塊號(hào)放在自己的FCB中。1FAT121) 以盤塊為基本分配單位 MS-DOS的文件物理結(jié)構(gòu)MS-DOS的文件物理結(jié)構(gòu)2) 簇

32、的基本概念為了適應(yīng)磁盤容量不斷增大的需要，在進(jìn)行盤塊分配時(shí)，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的扇區(qū)，在FAT中它是作為一個(gè)虛擬扇區(qū)，簇的大小一般是2n (n為整數(shù))個(gè)盤塊。一個(gè)簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)。例如，當(dāng)一個(gè)簇僅有一個(gè)扇區(qū)時(shí)，磁盤的最大容量為8 MB；當(dāng)一個(gè)簇包含兩個(gè)扇區(qū)時(shí)，磁盤的最大容量可以達(dá)到16 MB。2) 簇的基本概念為了適應(yīng)磁盤容量不斷增大的需要，在進(jìn)行盤塊3) FAT12存在的問(wèn)題盡管FAT12曾是一個(gè)不錯(cuò)的文件系統(tǒng)，但畢竟已老化，已不能滿足操作系統(tǒng)發(fā)展的需要，其表現(xiàn)出來(lái)的主要問(wèn)題是，對(duì)所允許的磁盤容量存在著嚴(yán)重的限制，通常只能是

33、數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來(lái)提高所允許的最大磁盤容量，但隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎片也將隨之成倍地增加。此外，它只能支持8+3格式的文件名。3) FAT12存在的問(wèn)題盡管FAT12曾是一個(gè)不錯(cuò)的文件2FAT16FAT12表最多只允許4096個(gè)表項(xiàng)，亦即最多只能將一個(gè)磁盤分區(qū)分為4096個(gè)簇。這樣，隨著磁盤容量的增加，必定會(huì)引起簇的大小和簇內(nèi)碎片也隨之增加。如果我們將FAT表的寬度增至16位，最大表項(xiàng)數(shù)將增至65536個(gè)，此時(shí)便能將一個(gè)磁盤分區(qū)分為65 536(216)個(gè)簇。我們把具有16位表寬的FAT表稱為FAT16。2FAT16FAT12表最多只允許4096個(gè)表項(xiàng)，亦

34、即最多3FAT32FAT32是FAT系列文件系統(tǒng)的最后一個(gè)產(chǎn)品。每一簇在FAT表中的表項(xiàng)占據(jù)4字節(jié)(232)，F(xiàn)AT表可以表示4 294 967 296項(xiàng)。FAT32的每個(gè)簇都固定為4 KB，即每簇用8個(gè)盤塊代替FAT16的64個(gè)盤塊，每個(gè)盤塊仍為512字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的單個(gè)最大磁盤空間大到4 KB232 = 2 TB。3FAT32FAT32是FAT系列文件系統(tǒng)的最后一個(gè)產(chǎn)品。塊大小/KB FAT12 /MB FAT16/MB FAT32 /TB 0.5 2 1 4 2 8 128 4 16 256 2 8 512 4 16 1024 6 32 2048 8 FAT中簇的大小與

35、最大分區(qū)的對(duì)應(yīng)關(guān)系塊大小/KB FAT12 /MB FAT16/MB FAT34NTFS1) NTFS新特征首先，它使用了64位磁盤地址，理論上可以支持2的64次方字節(jié)的磁盤分區(qū)；其次，在NTFS中可以很好地支持長(zhǎng)文件名；第三，具有系統(tǒng)容錯(cuò)功能，即在系統(tǒng)出現(xiàn)故障或差錯(cuò)時(shí)，仍能保證系統(tǒng)正常運(yùn)行；第四，提供了數(shù)據(jù)的一致性；此外，NTFS還提供了文件加密、文件壓縮等功能。4NTFS1) NTFS新特征4NTFS2) 磁盤組織NTFS也是以簇作為磁盤空間分配和回收的基本單位。一個(gè)文件占用若干個(gè)簇。通過(guò)簇來(lái)間接管理磁盤，可以不需要知道盤塊(扇區(qū))的大小。在NTFS文件系統(tǒng)中，把卷上簇的大小稱為“卷因子”

36、，卷因子是在磁盤格式化時(shí)確定的，簇的大小可由格式化命令或格式化程序按磁盤容量和應(yīng)用需求來(lái)確定。4NTFS2) 磁盤組織4NTFSNTFS是采用邏輯簇號(hào)LCN，將整個(gè)卷中所有的簇按順序進(jìn)行簡(jiǎn)單的編號(hào)，NTFS在進(jìn)行地址映射時(shí)，可以通過(guò)卷因子與LCN的乘積，便可得到文件數(shù)據(jù)所在的物理磁盤地址。NTFS還可以使用虛擬簇號(hào)VCN，以文件為單位，將屬于某個(gè)文件的簇按順序進(jìn)行編號(hào)。只要知道了文件開始的簇地址，便可將VCN映射到LCN。4NTFSNTFS是采用邏輯簇號(hào)LCN，將整個(gè)卷中所有的簇4NTFS3) 文件的組織在NTFS中，以卷為單位，將一個(gè)卷中的所有文件信息、目錄信息以及可用的未分配空間信息，都以

37、文件記錄的方式記錄在一張主控文件表MFT中。卷中的每個(gè)文件作為一條記錄，在MFT 表中占有一行，其中還包括MFT 自己的這一行。每行稱為該行所對(duì)應(yīng)文件的元數(shù)據(jù)(metadata)，也稱為文件控制字。4NTFS3) 文件的組織4NTFS在MFT表中，每個(gè)元數(shù)據(jù)將其所對(duì)應(yīng)文件的所有信息，包括文件的內(nèi)容等，都被組織在所對(duì)應(yīng)文件的一組屬性中。當(dāng)文件較小時(shí)，可以將文件的所有屬性直接記錄在元數(shù)據(jù)中。而當(dāng)文件較大時(shí)，元數(shù)據(jù)僅記錄該文件的一部分屬性，其余屬性可以記錄到卷中的其它可用簇中，并將這些簇按其所記錄文件的屬性進(jìn)行分類，分別鏈接成多個(gè)隊(duì)列。4NTFS在MFT表中，每個(gè)元數(shù)據(jù)將其所對(duì)應(yīng)文件的所有信息6.3

38、.4 索引分配鏈接分配方式雖然解決了連續(xù)分配方式所存在的問(wèn)題，但又出現(xiàn)了下述另外兩個(gè)問(wèn)題：(1) 不能支持高效的直接存取。(2) FAT需占用較大的內(nèi)存空間。由于一個(gè)文件所占用盤塊的盤塊號(hào)是隨機(jī)地分布在FAT中的，因而只有將整個(gè)FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個(gè)文件的所有盤塊號(hào)。6.3.4 索引分配鏈接分配方式雖然解決了連續(xù)分配方式所存在 1單級(jí)索引分配一個(gè)文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個(gè)文件建立一個(gè)專用數(shù)據(jù)結(jié)構(gòu)-索引表，并將這些塊的塊號(hào)存放在一個(gè)索引表中索引表：一個(gè)文件所有記錄的關(guān)鍵字和其它地址的對(duì)照表。一個(gè)索引表就是磁盤塊地址數(shù)組,其中第i個(gè)條目指向文件的第i塊 1單

39、級(jí)索引分配一個(gè)文件的信息存放在若干不連續(xù)物理塊中，系操作系統(tǒng)chapter6課件2多級(jí)索引分配當(dāng)OS為一個(gè)大文件分配磁盤空間時(shí)，如果所分配出去的盤塊的盤塊號(hào)已經(jīng)裝滿一個(gè)索引塊時(shí)，OS便為該文件分配另一個(gè)索引塊。再通過(guò)鏈指針將各索引塊按序鏈接起來(lái)。當(dāng)文件太大，其索引塊太多時(shí)，應(yīng)為這些索引塊再建立級(jí)索引，這樣便形成了兩級(jí)索引分配方式。如果文件非常大時(shí)，還可用三級(jí)、四級(jí)索引分配方式。2多級(jí)索引分配當(dāng)OS為一個(gè)大文件分配磁盤空間時(shí)，如果所0121051062543563579851051062547403563571125985360740.1125主索引360第二級(jí)索引磁盤空間.0121051062

40、54356357985105106254索引結(jié)構(gòu)優(yōu)缺點(diǎn)優(yōu)點(diǎn)： 保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn),又解決了其缺點(diǎn)：即能順序存取,又能隨機(jī)存取，滿足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除的要求，也能充分利用外存空間缺點(diǎn)： 較多的尋道次數(shù)和尋道時(shí)間，索引表本身帶來(lái)了系統(tǒng)開銷，如：內(nèi)外存空間，存取時(shí)間索引結(jié)構(gòu)優(yōu)缺點(diǎn)優(yōu)點(diǎn)：3混合索引分配方式所謂混合索引分配方式，是指將多種索引分配方式相結(jié)合而形成的一種分配方式。例如，系統(tǒng)既采用了直接地址，又采用了一級(jí)索引分配方式，或兩級(jí)索引分配方式，甚至還采用了三級(jí)索引分配方式。如圖所示。在BSD UNIX的索引結(jié)點(diǎn)中，共設(shè)置了13個(gè)地址項(xiàng)，它們都把所有的地址項(xiàng)分成兩類，即直接地址和間接地址。3

41、混合索引分配方式所謂混合索引分配方式，是指將多種索引分modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadata.datadata.datadatadatadatamodeowners (2)time stamps (3)s3混合索引分配方式1) 直接地址為了提高對(duì)文件的檢索速度，在索引結(jié)點(diǎn)中可設(shè)置直接地址項(xiàng)。2) 一次間接地址對(duì)于大、中型文件,可再利用索引結(jié)點(diǎn)中的地址項(xiàng)來(lái)提供一

42、次間接地址。這種方式的實(shí)質(zhì)就是一級(jí)索引分配方式。3) 多次間接地址當(dāng)文件長(zhǎng)度更大時(shí),系統(tǒng)還須采用二次間址分配方式。在二次間址塊中記入所有一次間址塊的盤號(hào)。3混合索引分配方式1) 直接地址6.4目 錄 管 理對(duì)目錄管理的要求如下：(1)實(shí)現(xiàn)“按名存取” (2) 提高對(duì)目錄的檢索速度 (3) 文件共享 (4) 允許文件重名 6.4目 錄 管 理對(duì)目錄管理的要求如下：6.4.1文件控制塊和索引結(jié)點(diǎn)1文件控制塊文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的相關(guān)信息。通常應(yīng)含有三類信息，即基本信息、存取控制信息及使用信息。 文件控制塊是文件存在的標(biāo)志6.4.1文件控制塊和索引結(jié)點(diǎn)

43、1文件控制塊1文件控制塊1) 基本信息類 文件名，指用于標(biāo)識(shí)一個(gè)文件的符號(hào)名。 文件物理位置，它包括存放文件的設(shè)備名、文件在外存上的起始盤塊號(hào)、文件長(zhǎng)度。 文件邏輯結(jié)構(gòu)，指示文件是流式文件還是記錄式文件、記錄數(shù)；文件是定長(zhǎng)記錄還是變長(zhǎng)記錄等。 文件的物理結(jié)構(gòu)，指示文件是順序文件，還是鏈接式文件或索引文件。1文件控制塊1) 基本信息類1文件控制塊2) 存取控制信息類存取控制信息類包括：文件主的存取權(quán)限、核準(zhǔn)用戶的存取權(quán)限以及一般用戶的存取權(quán)限。 3) 使用信息類使用信息類包括: 文件的建立日期和時(shí)間、文件上一次修改的日期和時(shí)間及當(dāng)前使用信息(這項(xiàng)信息包括當(dāng)前已打開該文件的進(jìn)程數(shù)、是否被其它進(jìn)程鎖

44、住、文件在內(nèi)存中是否已被修改但尚未拷貝到盤上)。1文件控制塊2) 存取控制信息類文件控制塊包括的內(nèi)容 文件名文件設(shè)備指向下一個(gè)PCB的指針文件標(biāo)識(shí)符 物理位置 當(dāng)前共享的狀態(tài)文件結(jié)構(gòu) 存取控制共享訪問(wèn)時(shí)等待狀態(tài)文件類型口令進(jìn)程訪問(wèn)文件所用的邏輯單元號(hào)記錄長(zhǎng)度文件建立時(shí)間當(dāng)前的邏輯位置 當(dāng)前文件大小上次存取時(shí)間訪問(wèn)元素的當(dāng)前物理位置緩沖區(qū)大小 緩沖區(qū)地址 文件創(chuàng)建者當(dāng)前存取方式 文件擁有者 臨時(shí)永久文件 最大文件尺寸 上次修改時(shí)間 下一個(gè)元素的物理位置文件控制塊包括的內(nèi)容 文件名文件設(shè)備指向下一個(gè)PCB的指針文MS-DOS的文件控制塊 文件名擴(kuò)展名屬性備用時(shí)間日期第一塊號(hào)盤塊數(shù)MS-DOS的文件

45、控制塊 文件名擴(kuò)展名屬性備用時(shí)間日期第一塊2索引結(jié)點(diǎn)1) 索引結(jié)點(diǎn)的引入文件目錄通常是存放在磁盤上的，當(dāng)文件很多時(shí)，文件目錄可能要占用大量的盤塊。在查找目錄的過(guò)程中，先將存放目錄文件的第一個(gè)盤塊中的目錄調(diào)入內(nèi)存，然后把用戶所給定的文件名與目錄項(xiàng)中的文件名逐一比較。若未找到指定文件，便再將下一個(gè)盤塊中的目錄項(xiàng)調(diào)入內(nèi)存，2索引結(jié)點(diǎn)1) 索引結(jié)點(diǎn)的引入2索引結(jié)點(diǎn)在檢索目錄文件的過(guò)程中，只用到了文件名，僅當(dāng)找到一個(gè)目錄項(xiàng)時(shí)，才需從該目錄項(xiàng)中讀出該文件的物理地址。而其它一些對(duì)該文件進(jìn)行描述的信息，在檢索目錄時(shí)一概不用。為此，在有的系統(tǒng)中，如UNIX系統(tǒng)，便采用了把文件名與文件描述信息分開的辦法。在文件目

46、錄中的每個(gè)目錄項(xiàng)僅由文件名和指向該文件所對(duì)應(yīng)的i結(jié)點(diǎn)的指針?biāo)鶚?gòu)成。2索引結(jié)點(diǎn)在檢索目錄文件的過(guò)程中，只用到了文件名，僅當(dāng)找到圖 UNIX的文件目錄 0 13 14 15 文件名 索引結(jié)點(diǎn)編號(hào) 文件名1 文件名2 圖 UNIX的文件目錄 0 2) 磁盤索引結(jié)點(diǎn)(1) 文件主標(biāo)識(shí)符。(2) 文件類型。(3) 文件存取權(quán)限。(4) 文件物理地址。 (5) 文件長(zhǎng)度。(6) 文件連接計(jì)數(shù)。(7) 文件存取時(shí)間。2) 磁盤索引結(jié)點(diǎn)(1) 文件主標(biāo)識(shí)符。索引結(jié)點(diǎn)編號(hào)。 用于標(biāo)識(shí)內(nèi)存索引結(jié)點(diǎn)。 狀態(tài)。 指示i結(jié)點(diǎn)是否上鎖或被修改。(3) 訪問(wèn)計(jì)數(shù)。 每當(dāng)有一進(jìn)程要訪問(wèn)此i結(jié)點(diǎn)時(shí)， 將該訪問(wèn)計(jì)數(shù)加1， 訪問(wèn)完

47、再減1。 (4) 文件所屬文件系統(tǒng)的邏輯設(shè)備號(hào)。(5) 鏈接指針。 設(shè)置有分別指向空閑鏈表和散列隊(duì)列的指針。3) 內(nèi)存索引結(jié)點(diǎn)索引結(jié)點(diǎn)編號(hào)。 用于標(biāo)識(shí)內(nèi)存索引結(jié)點(diǎn)。3) 內(nèi)存索引結(jié)點(diǎn)6.4.2目錄結(jié)構(gòu)文件目錄：是文件系統(tǒng)中主要數(shù)據(jù)結(jié)構(gòu)之一,文件存儲(chǔ)后用戶通過(guò)用戶文件邏輯結(jié)構(gòu)的索引鏈接找到對(duì)應(yīng)的物理結(jié)構(gòu)按文件符號(hào)名把文件信息的邏輯結(jié)構(gòu)映象設(shè)備介質(zhì)的物理結(jié)構(gòu)，由文件目錄實(shí)現(xiàn)把文件操作命令轉(zhuǎn)換相應(yīng)I/O指令。需要文件目錄6.4.2目錄結(jié)構(gòu)文件目錄：是文件系統(tǒng)中主要數(shù)據(jù)結(jié)構(gòu)之一,6.4.2目錄結(jié)構(gòu) 1. 單級(jí)目錄結(jié)構(gòu)這是最簡(jiǎn)單的目錄結(jié)構(gòu)。在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)，目錄項(xiàng)中

48、含文件名、文件擴(kuò)展名、文件長(zhǎng)度、文件類型、文件物理地址以及其它文件屬性。此外，為表明每個(gè)目錄項(xiàng)是否空閑，又設(shè)置了一個(gè)狀態(tài)位。6.4.2目錄結(jié)構(gòu) 1. 單級(jí)目錄結(jié)構(gòu)文件名 物理地址 文件說(shuō)明 狀態(tài)位 文件名1 文件名2 圖 單級(jí)目錄 文件名 物理地址 文件說(shuō)明 狀態(tài)位 文件名1 文件名21. 單級(jí)目錄結(jié)構(gòu)優(yōu)點(diǎn): 簡(jiǎn)單，易實(shí)現(xiàn)缺點(diǎn): 文件平均檢索時(shí)間長(zhǎng) 限制了用戶對(duì)文件的命名 限制了對(duì)文件的共享1. 單級(jí)目錄結(jié)構(gòu)優(yōu)點(diǎn): 2兩級(jí)目錄為改變一級(jí)目錄文件目錄命名沖突，并提高對(duì)目錄文件檢索速度而將目錄分為兩級(jí)：一級(jí)稱為主文件目錄，給出用戶名，用戶子目錄所在的物理位置；二級(jí)稱為用戶文件目錄，給出該用戶所有文

49、件的FCB產(chǎn)生于多用戶分時(shí)系統(tǒng)，DOS2.0版本以上采用，文件主目錄（MFD）的表目按用戶分，每個(gè)用戶有一個(gè)用戶文件目錄（UFD）2兩級(jí)目錄為改變一級(jí)目錄文件目錄命名沖突，并提高對(duì)目錄文件 兩級(jí)目錄結(jié)構(gòu) 兩級(jí)目錄結(jié)構(gòu) 2兩級(jí)目錄優(yōu)點(diǎn)：(1) 提高了檢索目錄的速度。(2) 在不同的用戶目錄中，可以使用相同的文件名。(3) 便于文件共享。缺點(diǎn)：缺點(diǎn)是不太適合大量用戶和大量文件的大系統(tǒng)，增加了系統(tǒng)開銷，2兩級(jí)目錄優(yōu)點(diǎn)：1) 目錄結(jié)構(gòu)對(duì)于大型文件系統(tǒng)，通常采用三級(jí)或三級(jí)以上的目錄結(jié)構(gòu)，以提高對(duì)目錄的檢索速度和文件系統(tǒng)的性能。多級(jí)目錄結(jié)構(gòu)又稱為樹型目錄結(jié)構(gòu)，主目錄在這里被稱為根目錄，把數(shù)據(jù)文件稱為樹葉，

50、其它的目錄均作為樹的結(jié)點(diǎn)。產(chǎn)生于UNIX操作系統(tǒng)，巳被現(xiàn)代操作系統(tǒng)廣泛采用。 3. 多級(jí)目錄結(jié)構(gòu)1) 目錄結(jié)構(gòu) 3. 多級(jí)目錄結(jié)構(gòu)多級(jí)目錄結(jié)構(gòu) ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89多級(jí)目錄結(jié)構(gòu) ABCFED13ABD2GA4AC567101在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通路。在該路徑上從樹的根(即主目錄)開始，把全部目錄文件名與數(shù)據(jù)文件名，依次地用“/”連接起來(lái)，即構(gòu)成該數(shù)據(jù)文件的路徑名。系統(tǒng)中的每一個(gè)文件都有惟一的路徑名。例如，在上圖中用戶B為訪問(wèn)文件J，應(yīng)使用其路徑名/B/F/J來(lái)訪問(wèn)

51、。 2) 路徑名在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通3) 當(dāng)前目錄為了提高文件檢索速度，文件系統(tǒng)向用戶提供了一個(gè)當(dāng)前正在使用的目錄，稱為當(dāng)前目錄（也稱工作目錄）。查找一個(gè)文件可從當(dāng)前目錄開始，使用部分路徑名當(dāng)前目錄可根據(jù)需要任意改變。當(dāng)前目錄一般存放在內(nèi)存。3) 當(dāng)前目錄為了提高文件檢索速度，文件系統(tǒng)向用戶提供了一個(gè)3. 多級(jí)目錄結(jié)構(gòu)優(yōu)點(diǎn)： 層次結(jié)構(gòu)清晰，便于管理和保護(hù)；有利于文件分類；解決重名問(wèn)題；提高文件檢索速度；能進(jìn)行存取權(quán)限的控制。缺點(diǎn)： 查找一個(gè)文件按路徑名逐層檢查，由于每個(gè)文件都放在外存，多次訪盤影響速度。3. 多級(jí)目錄結(jié)構(gòu)優(yōu)點(diǎn)：4. 增加和刪除目錄在樹型目

52、錄結(jié)構(gòu)中，用戶可為自己建立UFD，并可再創(chuàng)建子目錄。在用戶要?jiǎng)?chuàng)建一個(gè)新文件時(shí)，只需查看在自己的UFD及其子目錄中有無(wú)與新建文件相同的文件名。若無(wú)，便可在UFD或其某個(gè)子目錄中增加一個(gè)新目錄項(xiàng)。對(duì)于一個(gè)已不再需要的目錄，應(yīng)如何刪除其目錄項(xiàng)4. 增加和刪除目錄在樹型目錄結(jié)構(gòu)中，用戶可為自己建立UFD4. 增加和刪除目錄 (1) 不刪除非空目錄。當(dāng)目錄(文件)不空時(shí)， 不能將其刪除，而為了刪除一個(gè)非空目錄，必須先刪除目錄中的所有文件，使之先成為空目錄，后再予以刪除。如果目錄中還包含有子目錄，還必須采取遞歸調(diào)用方式來(lái)將其刪除。(2) 可刪除非空目錄。當(dāng)要?jiǎng)h除一目錄時(shí)，如果在該目錄中還包含有文件，則目錄

53、中的所有文件和子目錄也同時(shí)被刪除。 4. 增加和刪除目錄 (1) 不刪除非空目錄。當(dāng)目錄(文件)6.4.3目錄查詢技術(shù)1線性檢索法線性檢索法又稱為順序檢索法。在單級(jí)目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄中找到指名文件的目錄項(xiàng)。在樹型目錄中，用戶提供的文件名是由多個(gè)文件分量名組成的路徑名，此時(shí)須對(duì)多級(jí)目錄進(jìn)行查找。6.4.3目錄查詢技術(shù)1線性檢索法1*1* *4bin7dev14lib9etc6usr8tmp在結(jié)點(diǎn)6中查找usr字段根目錄132結(jié)點(diǎn)6是/usr的目錄6*1* *19dick30erik51jim26ast45bal132號(hào)盤是/usr的目錄496結(jié)點(diǎn)26是/us

54、r/ast的目錄26*6* *64grants92books60mbox81minik17src496號(hào)盤塊是/usr/ast的目錄查找/usr/ast/mbox的步驟1*1* *4bin7dev14lib9etc6usr8tm6.5.4 目錄查詢技術(shù) 1. 線性檢索法 查找/usr/ast/mbox的步驟 6.5.4 目錄查詢技術(shù) 1. 線性檢索法 查找/2Hash方法如果我們建立了一張Hash索引文件目錄，便可利用Hash方法進(jìn)行查詢，將顯著地提高檢索速度。對(duì)于使用了通配符的文件名，系統(tǒng)此時(shí)便無(wú)法利用Hash方法檢索目錄，因此，這時(shí)系統(tǒng)還是需要利用線性查找法查找目錄。2Hash方法如果我們

55、建立了一張Hash索引文件目錄，便可2Hash方法 一種處理“沖突”的有效規(guī)則是：(1) 在用Hash法索引查找目錄時(shí)，如果目錄表中相應(yīng)的目錄項(xiàng)是空的，則表示系統(tǒng)中并無(wú)此文件。(2) 如果目錄項(xiàng)中的文件名與指定文件名相同， 則表示該目錄項(xiàng)正是所要尋找的文件。(3) 如果在目錄表的相應(yīng)目錄項(xiàng)中的文件名與指定文件名不匹配，則表示發(fā)生了“沖突”，此時(shí)須將其Hash值再加上一個(gè)常數(shù)，形成新的索引值，再重新查找。2Hash方法 一種處理“沖突”的有效規(guī)則是：6.5文件存儲(chǔ)空間的管理為了有效管理存儲(chǔ)空間，首先必須定義相應(yīng)的數(shù)據(jù)結(jié)構(gòu)記錄外存空間的使用情況，然后選擇最合適的存儲(chǔ)空間管理方法以提高外存空間的利用

56、率。常用的輔存空間的管理方法有以下幾種。1空閑塊表法2空閑塊鏈法3位示圖法4. 成組鏈接法6.5文件存儲(chǔ)空間的管理為了有效管理存儲(chǔ)空間，首先必須定義6.5.1空閑表法和空閑鏈表法1空閑表法1) 空閑表空閑表法屬于連續(xù)分配方式，每個(gè)文件分配一塊連續(xù)的存儲(chǔ)空間，即系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對(duì)應(yīng)于一個(gè)空閑表項(xiàng)，其中包括表項(xiàng)序號(hào)、該空閑區(qū)的第一個(gè)盤塊號(hào)、該區(qū)的空閑盤塊數(shù)等信息。再將所有空閑區(qū)按其起始盤塊號(hào)遞增的次序排列。6.5.1空閑表法和空閑鏈表法1空閑表法序 號(hào) 第一空閑盤塊號(hào) 空閑盤塊數(shù) 1 2 4 2 9 3 3 15 5 4 空閑盤塊表 序 號(hào) 第一空閑盤塊號(hào) 空閑

57、盤塊數(shù) 1 2 4 2 92) 存儲(chǔ)空間的分配與回收空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時(shí)，先順序地檢索空閑表的各表項(xiàng)，直至找到第一個(gè)其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶。系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接。2) 存儲(chǔ)空間的分配與回收空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似2空閑鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈所用基本元素的不同，可把鏈表分成兩種形式： 空閑盤塊鏈 空閑盤區(qū)鏈2空閑鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)2空閑鏈表法空

58、閑盤塊鏈。這是將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。當(dāng)用戶請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶。 空閑盤區(qū)鏈。這是將磁盤上的所有空閑盤區(qū) 拉成一條鏈。在每個(gè)盤區(qū)上除含有用于指示下一個(gè)空閑盤區(qū)的指針外，還應(yīng)有能指明本盤區(qū)大小(盤塊數(shù))的信息。2空閑鏈表法空閑盤塊鏈。這是將磁盤上的所有空閑空間，以盤塊6.5.2位示圖法用一串二進(jìn)制位反映磁盤空間中分配使用情況, 每個(gè)物理塊對(duì)應(yīng)一位, 1表示對(duì)應(yīng)的物理塊已分配，0表示其對(duì)應(yīng)的塊未分配申請(qǐng)物理塊時(shí)，可以在位示圖中查找為0的位，返回對(duì)應(yīng)物理塊號(hào)歸還時(shí)；將對(duì)應(yīng)位轉(zhuǎn)置0描述能力強(qiáng)，適合各種物理結(jié)構(gòu)6.5.2位示圖

59、法用一串二進(jìn)制位反映磁盤空間中分配使用情況 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 2 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 3 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 4 M 16 位示圖 1 2 3 4 5 6 7 8 9 10 11 12 132) 盤塊的分配 (1)順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。(2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)

60、制位，位于位示的第i行、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算： b=n(i-1)+j式中，n代表每行的位數(shù)。(3) 修改位示圖， 令mapi,j=1。 2) 盤塊的分配 (1)順序掃描位示圖，從中找出一個(gè)或一組其3) 盤塊的回收 (1) 將回收盤塊的盤塊號(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。 3) 盤塊的回收 (1) 將回收盤塊的盤塊號(hào)6.5.3成組鏈接法空閑塊表法和空閑鏈法都適用小型文件系統(tǒng)，否則會(huì)使空閑塊表和空閑塊鏈太長(zhǎng)。成組鏈接法既克服二者的不足，又可集兩種方法的優(yōu)點(diǎn)于一身，是大