第六章鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)操作系統(tǒng)——文件管理

1、第六章第六章 文件管理文件管理 2 6.1.1 文件及其分類文件及其分類 1.文件的定義文件的定義 文件是計(jì)算機(jī)系統(tǒng)中信息存放的一種組織形式，文件是計(jì)算機(jī)系統(tǒng)中信息存放的一種組織形式， 目前尚無(wú)嚴(yán)格的定義，下面給出兩種有代表性目前尚無(wú)嚴(yán)格的定義，下面給出兩種有代表性 的解釋：的解釋： n（1）文件是具有標(biāo)識(shí)符的相關(guān)字符流的集合。）文件是具有標(biāo)識(shí)符的相關(guān)字符流的集合。 n（2）文件是具有標(biāo)識(shí)符的相關(guān)記錄（一個(gè)有）文件是具有標(biāo)識(shí)符的相關(guān)記錄（一個(gè)有 意義的信息單位）的集合。意義的信息單位）的集合。 3 6.1.1 文件及其分類文件及其分類 這兩種解釋定義了兩種文件形式：前者說(shuō)明文這兩種解釋定義了兩

2、種文件形式：前者說(shuō)明文 件是件是由字節(jié)組成由字節(jié)組成，這是一種無(wú)結(jié)構(gòu)的文件，或，這是一種無(wú)結(jié)構(gòu)的文件，或 稱稱流式文件流式文件。 無(wú)結(jié)構(gòu)文件由于采用字符流方式，與源程序、無(wú)結(jié)構(gòu)文件由于采用字符流方式，與源程序、 目標(biāo)代碼等在形式上是一致的，因此，該方式目標(biāo)代碼等在形式上是一致的，因此，該方式 適用于源程序、目標(biāo)代碼等文件。適用于源程序、目標(biāo)代碼等文件。 目前目前UNIX操作系統(tǒng)，操作系統(tǒng)，MS-DOS系統(tǒng)均采用這系統(tǒng)均采用這 種文件形式。種文件形式。 4 6.1.1 文件及其分類文件及其分類 后者說(shuō)明文件是后者說(shuō)明文件是由記錄組成由記錄組成。而記錄則是由一。而記錄則是由一 組相關(guān)信息項(xiàng)組成。組

3、相關(guān)信息項(xiàng)組成。 例如每個(gè)學(xué)生的登記表可視為一個(gè)記錄，它包例如每個(gè)學(xué)生的登記表可視為一個(gè)記錄，它包 括學(xué)生姓名，出生年月，性別，籍貫等信息項(xiàng)。括學(xué)生姓名，出生年月，性別，籍貫等信息項(xiàng)。 所有學(xué)生登記表組成一個(gè)學(xué)生文件。所有學(xué)生登記表組成一個(gè)學(xué)生文件。 記錄式文件主要用于信息管理。記錄式文件主要用于信息管理。 在現(xiàn)代計(jì)算機(jī)操作系統(tǒng)中，為方便用戶，在現(xiàn)代計(jì)算機(jī)操作系統(tǒng)中，為方便用戶，把設(shè)把設(shè) 備也作為文件來(lái)統(tǒng)一管理備也作為文件來(lái)統(tǒng)一管理，從某種意義上說(shuō)已，從某種意義上說(shuō)已 拓寬了文件的含義。拓寬了文件的含義。 5 6.1.2 文件的分類文件的分類 （1）以文件的）以文件的用途分類用途分類 系統(tǒng)文件

4、：系統(tǒng)文件：由操作系統(tǒng)及其他系統(tǒng)程序和數(shù)據(jù)組成的由操作系統(tǒng)及其他系統(tǒng)程序和數(shù)據(jù)組成的 文件。這種文件不對(duì)用戶開(kāi)放，僅供系統(tǒng)使用，用戶文件。這種文件不對(duì)用戶開(kāi)放，僅供系統(tǒng)使用，用戶 只能通過(guò)操作系統(tǒng)只能通過(guò)操作系統(tǒng)提供的系統(tǒng)調(diào)用提供的系統(tǒng)調(diào)用來(lái)使用它們。來(lái)使用它們。 庫(kù)文件：庫(kù)文件：是指系統(tǒng)為用戶提供的各種標(biāo)準(zhǔn)函數(shù)，標(biāo)準(zhǔn)是指系統(tǒng)為用戶提供的各種標(biāo)準(zhǔn)函數(shù)，標(biāo)準(zhǔn) 過(guò)程和實(shí)用程序等。用戶只能使用這些文件，而無(wú)權(quán)過(guò)程和實(shí)用程序等。用戶只能使用這些文件，而無(wú)權(quán) 對(duì)其進(jìn)行修改。對(duì)其進(jìn)行修改。 用戶文件：用戶文件：由用戶的信息組成的文件，如源程序文件，由用戶的信息組成的文件，如源程序文件， 數(shù)據(jù)文件等。這種文

5、件的使用和修改權(quán)均屬于用戶。數(shù)據(jù)文件等。這種文件的使用和修改權(quán)均屬于用戶。 6 6.1.2文件的分類文件的分類 （2）按文件的操作保護(hù)分類）按文件的操作保護(hù)分類 n只讀文件：只讀文件： 只允許進(jìn)行讀操作，不能進(jìn)行只允許進(jìn)行讀操作，不能進(jìn)行 寫操作的文件。寫操作的文件。 n讀寫文件：讀寫文件： 允許文件主和授權(quán)用戶對(duì)其進(jìn)允許文件主和授權(quán)用戶對(duì)其進(jìn) 行讀或?qū)懖僮鞯奈募?。行讀或?qū)懖僮鞯奈募?n只執(zhí)行文件：只執(zhí)行文件：該類文件只允許授權(quán)的用戶調(diào)該類文件只允許授權(quán)的用戶調(diào) 用執(zhí)行，而不允許其修改或讀出文件的內(nèi)容。用執(zhí)行，而不允許其修改或讀出文件的內(nèi)容。 7 6.1.2文件的分類文件的分類 （3）按文件

6、的性質(zhì)分類）按文件的性質(zhì)分類 n普通文件：普通文件： 指一般的用戶文件和系統(tǒng)文件。指一般的用戶文件和系統(tǒng)文件。 n目錄文件：目錄文件： 管理和實(shí)現(xiàn)文件系統(tǒng)的文件目管理和實(shí)現(xiàn)文件系統(tǒng)的文件目 錄項(xiàng)組成的系統(tǒng)文件，對(duì)目錄文件可以進(jìn)行錄項(xiàng)組成的系統(tǒng)文件，對(duì)目錄文件可以進(jìn)行 與普通文件一樣的各種文件操作。與普通文件一樣的各種文件操作。 n特別文件：特別文件： 有的系統(tǒng)把設(shè)備作為文件統(tǒng)一有的系統(tǒng)把設(shè)備作為文件統(tǒng)一 管理和使用，并為區(qū)別起見(jiàn)，管理和使用，并為區(qū)別起見(jiàn)，把設(shè)備稱為特把設(shè)備稱為特 別文件別文件。例如：。例如：unix/linux 8 6.1.3 文件系統(tǒng)及其功能 文件系統(tǒng)是操作系統(tǒng)中負(fù)責(zé)存取和

7、管理信息的 模塊，它用統(tǒng)一的方式管理用戶和對(duì)系統(tǒng)信息 的存儲(chǔ)、檢索、更新、共享和保護(hù)，并為用戶 提供一整套方便有效的文件使用和操作方法。 它由管理文件所需的數(shù)據(jù)結(jié)構(gòu)（如文件控制塊 及存儲(chǔ)分配表等）和相應(yīng)的管理軟件以及訪問(wèn) 文件的一組操作組成。 9 文件系統(tǒng)的功能 1.使用戶可執(zhí)行創(chuàng)建、修改及刪除讀寫文件 的命令。 2.使用戶在系統(tǒng)控制下共享其他用戶的文件， 以便用戶可共享其它人的工作成果。 3.使用戶能以合適的方式構(gòu)造其他文件 4.使用戶能使用在文件間進(jìn)行數(shù)據(jù)傳輸?shù)拿?10 文件系統(tǒng)的功能 5.為了實(shí)現(xiàn)按名存取，需要有一個(gè)用戶可見(jiàn) 的文件邏輯結(jié)構(gòu)，用戶按照文件邏輯結(jié)構(gòu)所 給定的方式進(jìn)行信息的

8、存取和加工。這種邏 輯結(jié)構(gòu)是獨(dú)立于物理存儲(chǔ)設(shè)備的。 6.為了防止意外事故，文件系統(tǒng)具有轉(zhuǎn)儲(chǔ)和 恢復(fù)文件的能力 7.能提供可靠的保護(hù)和保密措施 11 Widows的主流文件系統(tǒng) FAT(File Allocation Table)是“文件分配表”的 意 思。對(duì)我們來(lái)說(shuō)，它的意義在于對(duì)硬盤分區(qū) 的管理。 FAT16、FAT32、NTFS是目前最常見(jiàn)的三種文 件系統(tǒng)。 12 其它文件系統(tǒng) FAT12:是IBM第一臺(tái)個(gè)人電腦中的MS-DOS 1.0使用的 文件系統(tǒng)，主要用于軟盤。這種系統(tǒng)限制分區(qū)的容量 最大為16MB但這根本算不上問(wèn)題，因?yàn)檐洷P容量 從來(lái)沒(méi)有達(dá)到16MB。 ISO9660：CD-ROM

9、的文件系統(tǒng)，不過(guò)現(xiàn)在已經(jīng)延伸出 很多新的文件系統(tǒng)，對(duì)它的一些缺點(diǎn)進(jìn)行了彌補(bǔ)，如 Juliet等。 UDF：可讀寫光盤的文件系統(tǒng)。 Mac HFS：蘋果電腦的文件系統(tǒng)，對(duì)大容量磁盤有比 較好的支持。不過(guò)，現(xiàn)在大多數(shù)蘋果電腦還在使用 FAT32文件系統(tǒng)。 13 6.2 文件的結(jié)構(gòu)與組織 通常，用戶在使用文件時(shí)，只關(guān)心文件的邏輯 結(jié)構(gòu)。從用戶觀點(diǎn)觀察到的文件組織形式主要 有兩類： 一類是有結(jié)構(gòu)的文件 另一類是無(wú)結(jié)構(gòu)的流式文件 14 (1) 邏輯記錄邏輯記錄(結(jié)構(gòu)結(jié)構(gòu)) 邏輯記錄是文件中按信息在邏輯上的獨(dú)立含義來(lái)劃 分的信息單位。 邏輯記錄是對(duì)文件進(jìn)行存取操作的基本單位。 (2) 物理記錄物理記錄(結(jié)

10、構(gòu)結(jié)構(gòu)) 在存儲(chǔ)介質(zhì)上，由連續(xù)信息所組成的一個(gè)區(qū)域稱為 塊，也叫物理記錄。 (3) 邏輯記錄與物理記錄的區(qū)別與關(guān)系邏輯記錄與物理記錄的區(qū)別與關(guān)系 一個(gè)是邏輯的概念，一個(gè)是物理的概念 邏輯記錄最終在存放到物理記錄上上 文件的兩種結(jié)構(gòu)：文件的兩種結(jié)構(gòu)： 15 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu) 1. 記錄式文件記錄式文件 記錄式文件是一種有結(jié)構(gòu)的文件。 2. 流式文件流式文件 流式文件是相關(guān)的有序字符的集合。是無(wú)結(jié)構(gòu)的。 流式文件是按信息的個(gè)數(shù)或以特殊字符為界進(jìn)行存取 的。 16 1.記錄式文件 每個(gè)記錄由彼此相關(guān)的域構(gòu)成。記錄可按順序 編號(hào)為記錄1，記錄2，記錄n。如果文件 中所有記錄的長(zhǎng)度都相同，則

11、這種文件為定長(zhǎng) 記錄文件。 例如:學(xué)生登記表文件 xsdjb.dbf 姓名 學(xué)號(hào) 籍貫 通信地址 郵政編碼 李銘 925678 武昌 武昌關(guān)山街125號(hào) 430074 司馬樂(lè) 925679 北京 北京海軍路88號(hào) 100034 17 1.記錄式文件記錄式文件 記錄式文件按照記錄長(zhǎng)度是否相同，又可分為記錄式文件按照記錄長(zhǎng)度是否相同，又可分為 定長(zhǎng)記錄文件和不定長(zhǎng)記錄定長(zhǎng)記錄文件和不定長(zhǎng)記錄文件兩種。文件兩種。 （1）定長(zhǎng)記錄：定長(zhǎng)記錄：文件中所有記錄的長(zhǎng)度相等文件中所有記錄的長(zhǎng)度相等 。 （2）變長(zhǎng)記錄：變長(zhǎng)記錄：文件中記錄的長(zhǎng)度不相等。文件中記錄的長(zhǎng)度不相等。 定長(zhǎng)記錄文件的長(zhǎng)度 = 記錄個(gè)數(shù)

12、記錄長(zhǎng)度。 變長(zhǎng)記錄文件的長(zhǎng)度為各記錄長(zhǎng)度之和。 18 記錄式文件記錄式文件 19 2.無(wú)結(jié)構(gòu)的文件無(wú)結(jié)構(gòu)的文件 無(wú)結(jié)構(gòu)文件無(wú)結(jié)構(gòu)文件是指文件內(nèi)部不再劃分記錄，是由是指文件內(nèi)部不再劃分記錄，是由 一組相關(guān)信息組成的有序字符流，即流式文件。一組相關(guān)信息組成的有序字符流，即流式文件。 其其長(zhǎng)度直接按字節(jié)來(lái)計(jì)算長(zhǎng)度直接按字節(jié)來(lái)計(jì)算。 事實(shí)上事實(shí)上操作系統(tǒng)不知道或不關(guān)心文件中存放的操作系統(tǒng)不知道或不關(guān)心文件中存放的 內(nèi)容是什么內(nèi)容是什么，它所見(jiàn)到的都是一個(gè)一個(gè)的字節(jié)。，它所見(jiàn)到的都是一個(gè)一個(gè)的字節(jié)。 文件中任何信息的含義都由用戶級(jí)程序解釋文件中任何信息的含義都由用戶級(jí)程序解釋。 20 2.無(wú)結(jié)構(gòu)的文件

13、無(wú)結(jié)構(gòu)的文件 21 兩種文件的比較 流式文件就象給一張白紙給用戶，用戶可將他 的信息任意地寫到紙上，沒(méi)有任何格式上的限 制。 記錄式文件就象給一張表格給用戶，用戶要按 表規(guī)定的格式填信息。 顯然，結(jié)構(gòu)式文件對(duì)用戶的限制很大，使用起 來(lái)就不方便，所以記錄式文件被淘汰是理所當(dāng) 然的。 22 6.3 外存分配方式 一個(gè)文件存儲(chǔ)介質(zhì)，格式化后就分成許多大小 相等的單位存儲(chǔ)塊（物理盤塊），在現(xiàn)代 計(jì)算機(jī)系統(tǒng)中. 一般來(lái)說(shuō)，每個(gè)物理塊是一個(gè)磁盤的扇區(qū)， 512字節(jié)。并給每個(gè)存儲(chǔ)塊有個(gè)編號(hào)，稱為物 理塊號(hào)。 常用的外存分配方式有連續(xù)分配，鏈接分配和 索引分配三種。 23 文件存儲(chǔ)空間的分配文件存儲(chǔ)空間的分配

14、文件的物理結(jié)構(gòu) 24 一.連續(xù)分配 25 1.連續(xù)分配連續(xù)分配 文件A 3 100 r0 r1 r2 磁盤塊號(hào) 100101102 文件目錄文件目錄 文件A 目錄項(xiàng) 26 2.連續(xù)文件結(jié)構(gòu)的特點(diǎn)連續(xù)文件結(jié)構(gòu)的特點(diǎn) 優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單，實(shí)現(xiàn)容易，不需要額 外的開(kāi)銷。 缺點(diǎn)： n用戶創(chuàng)建文件時(shí)要給出文件的大??； n不利于文件的動(dòng)態(tài)增加和修改； 27 連續(xù)結(jié)構(gòu)文件的特點(diǎn)連續(xù)結(jié)構(gòu)文件的特點(diǎn) 連續(xù)分配的優(yōu)點(diǎn)是在順序存取時(shí)速度較快，一 次可以存取多個(gè)盤塊，改進(jìn)了I/O性能。 所以，它常用于存放系統(tǒng)文件，因?yàn)檫@類文件 往往被從頭到尾一次存取。另外，也很容易直 接存取文件中的任意一塊 例如，要訪問(wèn)從b塊開(kāi)始的第i

15、塊，可以直接從 b+i塊開(kāi)始讀取，因此，連續(xù)結(jié)構(gòu)方式支持順 序訪問(wèn)和直接訪問(wèn)。 28 二二.鏈接分配鏈接分配 鏈接分配的文件也稱之為鏈接分配的文件也稱之為是串聯(lián)文件是串聯(lián)文件 串聯(lián)文件結(jié)構(gòu)是按順序由串聯(lián)的塊組成的，即 文件的信息存于若干塊物理塊中，每個(gè)物理塊 的最末一個(gè)字作為鏈接字，它指出后繼塊的物 理地址。 文件的最后一塊的鏈接字為結(jié)束標(biāo)記“”， 它表示文件至本塊結(jié)束。 類似數(shù)據(jù)結(jié)構(gòu)的鏈表 29 鏈接結(jié)構(gòu)鏈接結(jié)構(gòu) 文件A 100 r1 57 r2 r0 150 磁盤塊號(hào) 100 磁盤塊號(hào) 150 磁盤塊號(hào) 57 文件目錄 文件A 目錄項(xiàng) 問(wèn)題：在串聯(lián)文件結(jié)構(gòu)下，當(dāng)要存取R i 記錄時(shí)，應(yīng)如何

16、操作? 30 鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)文件的特點(diǎn) 這種文件結(jié)構(gòu)不要求連續(xù)存放。 對(duì)于記錄式文件一塊中可包含一個(gè)邏輯 記錄或多個(gè)邏輯記錄 也可以若干物理塊包含一個(gè)邏輯記錄。 31 鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)文件的特點(diǎn) 優(yōu)點(diǎn)： 1.存儲(chǔ)空間利用率高； 2.文件創(chuàng)建時(shí)用戶不必指出文件的大小； 3.文件動(dòng)態(tài)擴(kuò)充和修改容易。 缺點(diǎn)：只能按隊(duì)列中的指針順序搜索，隨機(jī)存 取效率太低，如果訪問(wèn)文件的最后的內(nèi)容，實(shí) 際上是要訪問(wèn)整個(gè)文件。 32 鏈接分配的兩種形式：鏈接分配的兩種形式： 1. 隱式鏈接隱式鏈接 25 123 0 567 4 9 10 11 8 131415 12 171819 16 2122 23 20 25 2

17、6 27 24 293031 28 filestartend jeep925 目 錄 10 1 -1 16 在采用隱式鏈接分配時(shí)，在文件目錄的每個(gè)目錄項(xiàng)中， 都須含有指向鏈接文件的第一個(gè)盤塊和最后一個(gè)盤塊 的指針。 而在每個(gè)盤塊中都含有一個(gè)指向下一個(gè)盤塊的指針。 33 2. 顯式鏈接顯式鏈接 圖 6-9 顯式鏈接結(jié)構(gòu) 0 1 2 3 4 5 物理塊號(hào) 2 FCBFAT 0 4 5 1 34 6 EOF 11 10 5 EOF 0 1 2 3 4 5 6 7 8 9 FATFCB A 4 FCB B 9 圖 6-10 MS-DOS的文件物理結(jié)構(gòu) 35 例題: 假定盤塊的大小是1KB,硬盤的大小為

18、500MB， 采用顯式鏈接分配方式時(shí)，其FAT需占用多少 存儲(chǔ)空間？如果文件A占用硬盤的第11，12， 16，14四個(gè)盤塊，試畫出文件A中各盤塊的鏈 接情況及FAT的情況。 36 例題： 假設(shè)盤塊大小為1KB，盤塊號(hào)需占4個(gè)字節(jié)。請(qǐng) 分別解釋在連續(xù)分配方式，隱式鏈接分配方式 和顯式鏈接分配方式中如何將文件的字節(jié)偏移 量3500轉(zhuǎn)換為物理塊號(hào)和塊內(nèi)位移量。 37 3、索引結(jié)構(gòu)、索引結(jié)構(gòu) 鏈接結(jié)構(gòu)解決了連續(xù)分配的外部碎片和大小鏈接結(jié)構(gòu)解決了連續(xù)分配的外部碎片和大小 聲明的問(wèn)題，但是，聲明的問(wèn)題，但是，鏈接結(jié)構(gòu)不能有效地支鏈接結(jié)構(gòu)不能有效地支 持直接訪問(wèn)持直接訪問(wèn)，這是因?yàn)閴K指針與塊一起分布這是因?yàn)?/p>

19、塊指針與塊一起分布 在整個(gè)磁盤，且必須按順序讀出。在整個(gè)磁盤，且必須按順序讀出。 索引結(jié)構(gòu)解決了這個(gè)問(wèn)題。索引結(jié)構(gòu)解決了這個(gè)問(wèn)題。索引分配要求系索引分配要求系 統(tǒng)為每個(gè)文件建立統(tǒng)為每個(gè)文件建立一張索引表一張索引表。 索引結(jié)構(gòu)創(chuàng)建的文件索引結(jié)構(gòu)創(chuàng)建的文件也稱之為也稱之為索引文件索引文件 38 3、索引結(jié)構(gòu)、索引結(jié)構(gòu) 索引結(jié)構(gòu)文件索引結(jié)構(gòu)文件是另一種形式的非連續(xù) 文件，文件數(shù)據(jù)存放的存儲(chǔ)介質(zhì)上的 物理塊號(hào)與文件的邏輯塊號(hào)一一對(duì)應(yīng)， 并建立這樣對(duì)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu) 文件索引表 39 3、索引結(jié)構(gòu)、索引結(jié)構(gòu) 訪問(wèn)文件時(shí)，根據(jù)文件的邏輯塊號(hào)查文 件索引表，找到對(duì)應(yīng)的物理塊號(hào)，然后， 進(jìn)行訪問(wèn)。 文件由索引

20、表和數(shù)據(jù)文件構(gòu)成。這種文件稱為 索引文件。 非常類似于書(shū)本，它由書(shū)目錄和正文組成 40 多重索引多重索引 41 索引文件結(jié)構(gòu) 索引文件在存儲(chǔ)區(qū)中占兩個(gè)區(qū)：索引區(qū) 和數(shù)據(jù)區(qū)。索引區(qū)存放索引表，數(shù)據(jù)區(qū) 存放數(shù)據(jù)文件本身。 訪問(wèn)索引文件需要兩步操作 查文件索引，由邏輯塊號(hào)查得物理 塊號(hào) 由此磁盤物理塊號(hào)而獲得所要求的 信息。 42 索引文件結(jié)構(gòu) 索引文件的特點(diǎn)索引文件的特點(diǎn) 易于文件的增刪 直接讀寫任意記錄 索引表的組織索引表的組織多級(jí)索引多級(jí)索引 43 索引文件實(shí)例分析索引文件實(shí)例分析UNIX文件索引方式文件索引方式 0 1 9 10 11 12 直接尋址塊 直接尋址塊 一級(jí)間接塊 直接尋址塊一級(jí)

21、間接塊二級(jí)間接塊 直接 尋址 一級(jí)間接 二級(jí)間接 三級(jí)間接 44 華中科技大學(xué)2000年 某文件系統(tǒng)采用索引文件結(jié)構(gòu)，假定文件索引 表的每個(gè)表項(xiàng)占3個(gè)字節(jié)，存放一個(gè)磁盤塊的 塊號(hào)（磁盤塊的大小為512B）。試問(wèn) 1）該文件系統(tǒng)能管理的最大磁盤空間是多少 字節(jié) 2）若采用2級(jí)或3級(jí)索引該文件系統(tǒng)能管理的 最大磁盤空間又是多少字節(jié)？ 45 分析 由于索引表占用一個(gè)大小為512B的磁盤，所以 該文件系統(tǒng)的索引表可以管理512/3=170個(gè)表 項(xiàng)，而每一個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)物理塊，因此該文 件系統(tǒng)可以管理的最大磁盤空間為 170*512B=87040B=85K 若采用二級(jí)索引，則是： 170*170*512

22、B=7225KB 若采用三級(jí)索引，則是： 170*170*170*512B=2456500KB=2398.93M 46 例題： 存放在某個(gè)磁盤上的文件系統(tǒng)采用混合索引分配方式， 其FCB中共有13個(gè)地址項(xiàng)，第09個(gè)地址項(xiàng)為直接地 址，第10個(gè)地址項(xiàng)為一次間接地址，第11個(gè)地址項(xiàng)為 二次間接地址，第12個(gè)地址項(xiàng)為三次間接地址。如果 每個(gè)盤塊的大小為512字節(jié)，若盤塊號(hào)需要用3個(gè)字節(jié) 來(lái)描述，而每個(gè)盤塊最多存放170個(gè)盤塊地址。則： （1）該文件系統(tǒng)允許文件的最大長(zhǎng)度是多少？ （2）將文件的字節(jié)偏移量5000，15000和150000轉(zhuǎn)換 為物理塊號(hào)和塊內(nèi)偏移量。 47 6.3 文件目錄 通常，在

23、計(jì)算機(jī)系統(tǒng)中，大量的文件被 存儲(chǔ)在磁盤上。為了對(duì)存儲(chǔ)在磁盤上的 眾多文件進(jìn)行有效的控制和管理，必須 對(duì)它們加以妥善組織。 這種組織是通過(guò)文件目錄來(lái)實(shí)現(xiàn)的，文 件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用來(lái)標(biāo)識(shí)文件 系統(tǒng)中的文件及其物理地址，供檢索時(shí) 使用。 48 文件目錄的組成 文件名：符號(hào)文件名名，如music、game、file等。 文件類型：指明文件屬性是普通文件，還是目錄文件 或特別文件，是系統(tǒng)文件還是用戶文件等。 文件的物理位置：文件在物理設(shè)備上的位置，如文件 存放在哪臺(tái)設(shè)備的哪些盤塊上。 文件的大?。寒?dāng)前文件大?。ㄒ宰止?jié)、字或塊為單位） 和允許的最大長(zhǎng)度。 保護(hù)信息：對(duì)文件讀、寫及執(zhí)行等操作的控制權(quán)限

24、標(biāo) 志。 使用計(jì)數(shù)：表示當(dāng)前有多少個(gè)進(jìn)程正在使用或打開(kāi)了 該文件。 時(shí)間和日期：這個(gè)信息反映了文件創(chuàng)建、最后修改、 最后使用等情況，可用于對(duì)文件實(shí)施保護(hù)和監(jiān)控等 49 6.3.1 文件控制塊和文件目錄文件控制塊和文件目錄 而文件目錄信息也叫文件控制塊（而文件目錄信息也叫文件控制塊（file control block ,FCB），它是操作系統(tǒng)），它是操作系統(tǒng) 為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了 為管理文件所需的所有有關(guān)信息（文件為管理文件所需的所有有關(guān)信息（文件 屬性）。屬性）。 文件控制塊是文件存在的標(biāo)志文件控制塊是文件存在的標(biāo)志，它通常，它通常 由文件屬性

25、信息組成。由文件屬性信息組成。 50 FCB的外部表現(xiàn)：文件的屬性 51 2.文件目錄文件目錄 為了對(duì)眾多的文件進(jìn)行分門別類的管理，提高為了對(duì)眾多的文件進(jìn)行分門別類的管理，提高 文件檢索的效率，現(xiàn)代操作系統(tǒng)往往文件檢索的效率，現(xiàn)代操作系統(tǒng)往往將文件的將文件的 文件控制塊集中在一起進(jìn)行管理文件控制塊集中在一起進(jìn)行管理。 這種這種FCB的有序集合就稱為文件目錄的有序集合就稱為文件目錄，文件控，文件控 制塊就是其中的目錄項(xiàng)（構(gòu)成文件目錄的項(xiàng)制塊就是其中的目錄項(xiàng)（構(gòu)成文件目錄的項(xiàng) 目）。目）。 另外，為了實(shí)現(xiàn)對(duì)文件目錄的管理，另外，為了實(shí)現(xiàn)對(duì)文件目錄的管理，通常將文通常將文 件目錄以文件的形式保存在外

26、存，這個(gè)文件就件目錄以文件的形式保存在外存，這個(gè)文件就 叫目錄文件。叫目錄文件。 52 3.索引結(jié)點(diǎn)的引入索引結(jié)點(diǎn)的引入 為了減少系統(tǒng)開(kāi)銷，采用了把文件名與文件描述信為了減少系統(tǒng)開(kāi)銷，采用了把文件名與文件描述信 息分開(kāi)的辦法，息分開(kāi)的辦法，即使文件描述信息單獨(dú)形成一個(gè)稱即使文件描述信息單獨(dú)形成一個(gè)稱 為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱為，簡(jiǎn)稱為i結(jié)點(diǎn)。結(jié)點(diǎn)。 文件名索引結(jié)點(diǎn)編號(hào) 文件名1 文件名2 圖 6-15 UNIX的文件目錄 53 例題： 在某個(gè)文件系統(tǒng)中，每個(gè)盤塊為512字節(jié)，文 件控制塊占64個(gè)字節(jié)，其中文件名占8個(gè)字節(jié)。 如果索引結(jié)點(diǎn)編號(hào)占2個(gè)字節(jié)，對(duì)一個(gè)存放在 磁盤上

27、的256個(gè)目錄項(xiàng)的目錄，試比較引入索 引結(jié)點(diǎn)前后，為找到其中一個(gè)文件的FCB，平 均其中磁盤的次數(shù)。 54 6.3文件目錄文件目錄 為了方便用戶的使用，提高文件系統(tǒng)的 效率，也必須對(duì)系統(tǒng)內(nèi)的所有文件目錄 進(jìn)行組織。 在現(xiàn)代操作系統(tǒng)中，目錄的基本組織方 式有： n一級(jí)目錄 n二級(jí)目錄 n樹(shù)形目錄 55 6.3.2 一級(jí)目錄一級(jí)目錄 一級(jí)目錄是最簡(jiǎn)單的目錄結(jié)構(gòu)。在這種組織方式下，一級(jí)目錄是最簡(jiǎn)單的目錄結(jié)構(gòu)。在這種組織方式下， 全部文件都登記在同一目錄中。全部文件都登記在同一目錄中。 其特點(diǎn)是簡(jiǎn)單、易于理解和實(shí)現(xiàn)，但那也存在以下的其特點(diǎn)是簡(jiǎn)單、易于理解和實(shí)現(xiàn)，但那也存在以下的 缺陷：缺陷：查找速度慢

28、、不允許重名和不便于文件的共享查找速度慢、不允許重名和不便于文件的共享 56 6. 3. 2 二級(jí)目錄二級(jí)目錄 n為改變一級(jí)目錄文件目錄命名沖突，并提高為改變一級(jí)目錄文件目錄命名沖突，并提高 對(duì)目錄文件檢索速度而將目錄分為兩級(jí)：對(duì)目錄文件檢索速度而將目錄分為兩級(jí)： n一級(jí)稱為主文件目錄，給出用戶名一級(jí)稱為主文件目錄，給出用戶名，用戶子，用戶子 目錄所在的物理位置；目錄所在的物理位置； n二級(jí)稱為用戶文件目錄二級(jí)稱為用戶文件目錄，給出該用戶所有文，給出該用戶所有文 件的件的FCB。 n文件主目錄（文件主目錄（MFD）的表目按用戶分）的表目按用戶分，每每 個(gè)用戶有一個(gè)用戶文件目錄（個(gè)用戶有一個(gè)用戶

29、文件目錄（UFD） 57 6.2.3 兩級(jí)目錄兩級(jí)目錄 58 6.2.3 兩級(jí)目錄兩級(jí)目錄 n在二級(jí)目錄結(jié)構(gòu)中，用戶引用特定的文件時(shí)，在二級(jí)目錄結(jié)構(gòu)中，用戶引用特定的文件時(shí)， 系統(tǒng)只需搜索他自己的系統(tǒng)只需搜索他自己的UFD，因此，不同用，因此，不同用 戶可擁有具有相同名稱的文件，戶可擁有具有相同名稱的文件，只要每個(gè)只要每個(gè) UFD內(nèi)的所有文件名稱惟一即可。內(nèi)的所有文件名稱惟一即可。 n當(dāng)用戶創(chuàng)建文件時(shí)，操作系統(tǒng)當(dāng)用戶創(chuàng)建文件時(shí)，操作系統(tǒng)也只搜索該用也只搜索該用 戶的戶的UFD以確定具有相同名字的文件是否存以確定具有相同名字的文件是否存 在在。 n當(dāng)刪除文件時(shí)，操作系統(tǒng)只在局部當(dāng)刪除文件時(shí)，操作

30、系統(tǒng)只在局部UFD中對(duì)中對(duì) 其進(jìn)行搜索，因此，它并不會(huì)刪除另一個(gè)用其進(jìn)行搜索，因此，它并不會(huì)刪除另一個(gè)用 戶的具有相同名稱的文件。戶的具有相同名稱的文件。 59 6.2.3 兩級(jí)目錄的特點(diǎn)兩級(jí)目錄的特點(diǎn) 二級(jí)目錄的優(yōu)點(diǎn)：解決了名稱沖突 和文件共享問(wèn)題，提高了搜索速度， 查找時(shí)間也降低了。 但是，它仍有一定的缺陷：缺少靈 活性、不能反映現(xiàn)實(shí)世界中的多層 關(guān)系。 因此就產(chǎn)生了多級(jí)目錄結(jié)構(gòu) 60 6.3.3 樹(shù)型目錄（多級(jí)目錄結(jié)構(gòu)）樹(shù)型目錄（多級(jí)目錄結(jié)構(gòu)） 又稱為多級(jí)目錄結(jié)構(gòu)，它是二級(jí)目錄結(jié)又稱為多級(jí)目錄結(jié)構(gòu)，它是二級(jí)目錄結(jié) 構(gòu)的擴(kuò)充。構(gòu)的擴(kuò)充。 這種多層次的目錄結(jié)構(gòu)如同一棵倒置的這種多層次的目錄結(jié)

31、構(gòu)如同一棵倒置的 樹(shù)，主目錄就是樹(shù)根，稱為樹(shù)，主目錄就是樹(shù)根，稱為根目錄根目錄 每一個(gè)樹(shù)枝結(jié)點(diǎn)就是一個(gè)子目錄每一個(gè)樹(shù)枝結(jié)點(diǎn)就是一個(gè)子目錄，每一，每一 片樹(shù)葉描述的一個(gè)文件。片樹(shù)葉描述的一個(gè)文件。 61 6.3.3 樹(shù)型目錄樹(shù)型目錄 62 6.3.3 樹(shù)型目錄樹(shù)型目錄 在樹(shù)形目錄結(jié)構(gòu)中，在樹(shù)形目錄結(jié)構(gòu)中，一個(gè)文件的全一個(gè)文件的全 名名將包括從根目錄開(kāi)始到文件為止將包括從根目錄開(kāi)始到文件為止 的通路上遇到的所有子目錄路徑。的通路上遇到的所有子目錄路徑。 各子目錄名之間用各子目錄名之間用正斜線正斜線“/”或反或反 斜線斜線“”隔開(kāi)，其中，子目錄名組隔開(kāi)，其中，子目錄名組 成的部分又稱為路徑名。成的部

32、分又稱為路徑名。 63 6.3.3 樹(shù)型目錄樹(shù)型目錄 系統(tǒng)內(nèi)的每個(gè)文件都有惟一的路徑名。系統(tǒng)內(nèi)的每個(gè)文件都有惟一的路徑名。 路徑名路徑名是從根經(jīng)過(guò)所有子目錄再到指定文件的路徑。是從根經(jīng)過(guò)所有子目錄再到指定文件的路徑。 路徑名有兩種形式：路徑名有兩種形式：絕對(duì)路徑名和相對(duì)路徑名絕對(duì)路徑名和相對(duì)路徑名。 n絕對(duì)路徑名絕對(duì)路徑名從根目錄開(kāi)始并給出路徑上的目錄名直從根目錄開(kāi)始并給出路徑上的目錄名直 到指定的文件到指定的文件 n相對(duì)路徑名相對(duì)路徑名從當(dāng)前目錄開(kāi)始定義一個(gè)路徑。從當(dāng)前目錄開(kāi)始定義一個(gè)路徑。 n UNIX/Linux也使用相對(duì)路徑名和絕對(duì)路徑名來(lái)標(biāo)識(shí)也使用相對(duì)路徑名和絕對(duì)路徑名來(lái)標(biāo)識(shí) 文件或

33、目錄，只不過(guò)文件和目錄之間采用文件或目錄，只不過(guò)文件和目錄之間采用“/”來(lái)分隔，來(lái)分隔， 而不是而不是DOS的的“” 。 64 6.2.4 樹(shù)型目錄樹(shù)型目錄 樹(shù)形目錄 當(dāng)前目錄/root/spell/mail 請(qǐng)問(wèn)first的相對(duì)路徑和絕 對(duì)路徑分別是什么？ 65 6.3.3 樹(shù)型目錄樹(shù)型目錄 在上圖所示的樹(shù)形目錄中，如果當(dāng)前目錄是 /root/spell/mail， 那么相對(duì)路徑名prt/first 和絕對(duì)路徑名root/spell/mail/prt/first指向相同 的文件。 66 6.4文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理 存儲(chǔ)空間管理是文件系統(tǒng)的重要任務(wù)之一。只 有有效地進(jìn)行存儲(chǔ)空間

34、管理，才能保證多個(gè)用 戶共享文件存儲(chǔ)設(shè)備和得以實(shí)現(xiàn)文件的按名存 取。 由于文件存儲(chǔ)設(shè)備是分成若干個(gè)大小相等的物 理塊，并以塊為單位來(lái)交換信息的，因此，文 件存儲(chǔ)空間的管理實(shí)質(zhì)上是一個(gè)空閑塊的組織 和管理問(wèn)題，它包括空閑塊的組織，空閑塊的 分配與空閑塊的回收等幾個(gè)問(wèn)題。 67 6.4文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理 有4種不同的空閑塊管理方法。它們是： (1) 空閑文件表； (2) 空閑塊鏈； (3) 位示圖； (4) 成組鏈接法。 下面介紹這幾種空閑空間的分配方法。 68 1、空閑文件表： 簡(jiǎn)單的空閑塊管理方法就是簡(jiǎn)單的空閑塊管理方法就是把文件存儲(chǔ)把文件存儲(chǔ) 設(shè)備中的設(shè)備中的空閑塊的塊號(hào)空

35、閑塊的塊號(hào)統(tǒng)一放在一個(gè)稱統(tǒng)一放在一個(gè)稱 為空閑文件目錄的物理塊中為空閑文件目錄的物理塊中。 其中空閑文件目錄的每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)其中空閑文件目錄的每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè) 由多個(gè)空閑塊構(gòu)成的空閑區(qū)，它包括由多個(gè)空閑塊構(gòu)成的空閑區(qū)，它包括空空 閑塊個(gè)數(shù)，空閑塊號(hào)和第一個(gè)空閑塊號(hào)閑塊個(gè)數(shù)，空閑塊號(hào)和第一個(gè)空閑塊號(hào) 等。等。 69 1、空閑文件表 70 2、空閑塊鏈、空閑塊鏈 空閑塊鏈?zhǔn)且环N較常用的空閑塊管理方法。空閑塊鏈?zhǔn)且环N較常用的空閑塊管理方法。 空閑塊鏈把文件存儲(chǔ)設(shè)備上的所有空閑塊鏈把文件存儲(chǔ)設(shè)備上的所有空閑塊鏈接空閑塊鏈接 在一起在一起 當(dāng)申請(qǐng)者需要空閑塊時(shí)，分配程序從當(dāng)申請(qǐng)者需要空閑塊時(shí)，分配程序

36、從鏈頭開(kāi)始鏈頭開(kāi)始 摘取所需要的空閑塊，然后調(diào)整鏈?zhǔn)字羔樥∷枰目臻e塊，然后調(diào)整鏈?zhǔn)字羔槨?反之，當(dāng)回收空閑塊時(shí)，把釋放的空閑塊逐個(gè)反之，當(dāng)回收空閑塊時(shí)，把釋放的空閑塊逐個(gè) 插入鏈尾上。插入鏈尾上。 71 2.空閑塊鏈空閑塊鏈 空閑塊鏈?zhǔn)疽鈭D r1 57 r2 r0 150 rn 72 3.位示圖位示圖 系統(tǒng)首先從系統(tǒng)首先從內(nèi)存中分配若干個(gè)字節(jié)內(nèi)存中分配若干個(gè)字節(jié)，為每個(gè)文，為每個(gè)文 件存儲(chǔ)設(shè)備建立件存儲(chǔ)設(shè)備建立一張位示圖一張位示圖。 這張位示圖反映每個(gè)文件存儲(chǔ)設(shè)備的使用情況。這張位示圖反映每個(gè)文件存儲(chǔ)設(shè)備的使用情況。 在位示圖中，每個(gè)文件存儲(chǔ)設(shè)備的物理塊都對(duì)在位示圖中，每個(gè)文件存儲(chǔ)設(shè)備的

37、物理塊都對(duì) 應(yīng)一個(gè)比特位。應(yīng)一個(gè)比特位。 n如果該位為如果該位為“0”，則表示所對(duì)應(yīng)的塊是空閑，則表示所對(duì)應(yīng)的塊是空閑 塊；塊； n反之，如果該位為反之，如果該位為“1”，則表示所對(duì)應(yīng)的塊，則表示所對(duì)應(yīng)的塊 已被分配出去。已被分配出去。 73 圖 6-21 位示圖 3.位示圖位示圖 74 盤塊的分配：盤塊的分配： (1) 順序掃描位示圖，從中找出一個(gè)或一組其值為“0” 的二進(jìn)制位(“0”表示空閑時(shí))。 (2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng) 的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)制位，位于位示 的第i行、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算： b=n(i-1)+j 式中， n代

38、表每行的位數(shù)。 (3) 修改位示圖， 令mapi,j=1。 3.位示圖位示圖 75 盤塊的回收：盤塊的回收： (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.位示圖位示圖 76 例題：例題： 在頁(yè)式存儲(chǔ)管理中，可以用位示圖表示內(nèi)存空閑塊狀 況。假設(shè)字長(zhǎng)為32位，每一位(編號(hào)為0-31)與一個(gè)內(nèi) 存塊對(duì)應(yīng)，取值可為0或1。當(dāng)取值為1時(shí)表示對(duì)應(yīng)塊已 被占用，當(dāng)取值為0時(shí)表示對(duì)應(yīng)塊為空閑。 (1) 如果內(nèi)存可分配區(qū)被劃分為1024塊，則位示圖共 需要多少個(gè)字來(lái)表示？

39、A) 15 B) 16 C) 31 D) 32 答案：D (2) 已知某一位的字號(hào)是5，位號(hào)為14，假設(shè)字號(hào)也從 0開(kāi)始編號(hào)。則對(duì)應(yīng)的內(nèi)存塊號(hào)是多少？（假設(shè)內(nèi)存塊 從0開(kāi)始編號(hào)） A) 70 B) 105 C) 173 D) 224 答案：C 77 例題： 有一計(jì)算機(jī)系統(tǒng)利用下圖所示的位示圖來(lái)管理空 閑塊（行、列號(hào)均從0開(kāi)始），如果塊號(hào)從1開(kāi) 始，每個(gè)盤塊大小為1kb。 1.現(xiàn)要為文件分配兩個(gè)盤塊，具體說(shuō)明分配過(guò)程。 2.若要釋放磁盤的第300塊，應(yīng)如何處理？ 78 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 1 1

40、1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79 4. 成組鏈接法成組鏈接法 1. 空閑盤塊的組織空閑盤塊的組織 100 400 399 301 300 100 300 299 202 201 299 100 400 399 201301 99 0 7999 7901 7900 7899 7801 7999 7901 空閑盤塊號(hào) 棧 S.free 0 1 98 99

41、 圖 6-22 空閑盤塊的成組鏈接法 80 2. 空閑盤塊的分配與回收空閑盤塊的分配與回收 在分配時(shí)，首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖， 便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶， 然后將棧頂指針下移一格。 若該盤塊號(hào)已是棧底， 即該塊是當(dāng)前組中可分配的盤塊。 由于在該盤塊號(hào)所對(duì)應(yīng)的盤塊中記有下一組可用的盤塊號(hào)列 表，因此，須將其讀入棧中，作為新的一組空閑塊，并把原 棧底對(duì)應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。 81 在系統(tǒng)回收空閑盤塊時(shí)，將回收盤塊的盤塊號(hào)記入空 閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。當(dāng)棧中空 閑盤塊號(hào)數(shù)目已達(dá)100時(shí)， 表示棧已滿，便將現(xiàn)有棧中的 100個(gè)盤塊號(hào)， 記入新回收的盤塊中，再將其盤塊號(hào)作為新 棧底。 82 例題： 某個(gè)系統(tǒng)采用成組鏈接法來(lái)管理磁盤的空閑空 間，目前磁盤的狀態(tài)如圖。 1