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

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

2、種文件形式：前者說明文 件是件是由字節(jié)組成由字節(jié)組成，這是一種無結(jié)構(gòu)的文件，或，這是一種無結(jié)構(gòu)的文件，或 稱稱流式文件流式文件。 無結(jié)構(gòu)文件由于采用字符流方式，與源程序、無結(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 文件及其分類文件及其分類 后者說明文件是后者說明文件是由記錄組成由記錄組成。而記錄則是由一。而記錄則是由一 組相關(guān)信息項組成。組

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

4、：系統(tǒng)文件：由操作系統(tǒng)及其他系統(tǒng)程序和數(shù)據(jù)組成的由操作系統(tǒng)及其他系統(tǒng)程序和數(shù)據(jù)組成的 文件。這種文件不對用戶開放，僅供系統(tǒng)使用，用戶文件。這種文件不對用戶開放，僅供系統(tǒng)使用，用戶 只能通過操作系統(tǒng)只能通過操作系統(tǒng)提供的系統(tǒng)調(diào)用提供的系統(tǒng)調(diào)用來使用它們。來使用它們。 庫文件：庫文件：是指系統(tǒng)為用戶提供的各種標(biāo)準(zhǔn)函數(shù)，標(biāo)準(zhǔn)是指系統(tǒng)為用戶提供的各種標(biāo)準(zhǔn)函數(shù)，標(biāo)準(zhǔn) 過程和實用程序等。用戶只能使用這些文件，而無權(quán)過程和實用程序等。用戶只能使用這些文件，而無權(quán) 對其進(jìn)行修改。對其進(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)用戶對其進(jìn)允許文件主和授權(quán)用戶對其進(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目錄文件：目錄文件： 管理和實現(xiàn)文件系統(tǒng)的文件目管理和實現(xiàn)文件系統(tǒng)的文件目 錄項組成的系統(tǒng)文件，對目錄文件可以進(jìn)行錄項組成的系統(tǒng)文件，對目錄文件可以進(jìn)行 與普通文件一樣的各種文件操作。與普通文件一樣的各種文件操作。 n特別文件：特別文件： 有的系統(tǒng)把設(shè)備作為文件統(tǒng)一有的系統(tǒng)把設(shè)備作為文件統(tǒng)一 管理和使用，并為區(qū)別起見，管理和使用，并為區(qū)別起見，把設(shè)備稱為特把設(shè)備稱為特 別文件別文件。例如：。例如：unix/linux 8 6.1.3 文件系統(tǒng)及其功能 文件系統(tǒng)是操作系統(tǒng)中負(fù)責(zé)存取和

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

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

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

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

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

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

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

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

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

16、操作? 30 鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)文件的特點 這種文件結(jié)構(gòu)不要求連續(xù)存放。 對于記錄式文件一塊中可包含一個邏輯 記錄或多個邏輯記錄 也可以若干物理塊包含一個邏輯記錄。 31 鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)文件的特點 優(yōu)點： 1.存儲空間利用率高； 2.文件創(chuàng)建時用戶不必指出文件的大??； 3.文件動態(tài)擴充和修改容易。 缺點：只能按隊列中的指針順序搜索，隨機存 取效率太低，如果訪問文件的最后的內(nèi)容，實 際上是要訪問整個文件。 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 在采用隱式鏈接分配時，在文件目錄的每個目錄項中， 都須含有指向鏈接文件的第一個盤塊和最后一個盤塊 的指針。 而在每個盤塊中都含有一個指向下一個盤塊的指針。 33 2. 顯式鏈接顯式鏈接 圖 6-9 顯式鏈接結(jié)構(gòu) 0 1 2 3 4 5 物理塊號 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， 采用顯式鏈接分配方式時，其FAT需占用多少 存儲空間？如果文件A占用硬盤的第11，12， 16，14四個盤塊，試畫出文件A中各盤塊的鏈 接情況及FAT的情況。 36 例題： 假設(shè)盤塊大小為1KB，盤塊號需占4個字節(jié)。請 分別解釋在連續(xù)分配方式，隱式鏈接分配方式 和顯式鏈接分配方式中如何將文件的字節(jié)偏移 量3500轉(zhuǎn)換為物理塊號和塊內(nèi)位移量。 37 3、索引結(jié)構(gòu)、索引結(jié)構(gòu) 鏈接結(jié)構(gòu)解決了連續(xù)分配的外部碎片和大小鏈接結(jié)構(gòu)解決了連續(xù)分配的外部碎片和大小 聲明的問題，但是，聲明的問題，但是，鏈接結(jié)構(gòu)不能有效地支鏈接結(jié)構(gòu)不能有效地支 持直接訪問持直接訪問，這是因為塊指針與塊一起分布這是因為

19、塊指針與塊一起分布 在整個磁盤，且必須按順序讀出。在整個磁盤，且必須按順序讀出。 索引結(jié)構(gòu)解決了這個問題。索引結(jié)構(gòu)解決了這個問題。索引分配要求系索引分配要求系 統(tǒng)為每個文件建立統(tǒng)為每個文件建立一張索引表一張索引表。 索引結(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ù)存放的存儲介質(zhì)上的 物理塊號與文件的邏輯塊號一一對應(yīng)， 并建立這樣對應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu) 文件索引表 39 3、索引結(jié)構(gòu)、索引結(jié)構(gòu) 訪問文件時，根據(jù)文件的邏輯塊號查文 件索引表，找到對應(yīng)的物理塊號，然后， 進(jìn)行訪問。 文件由索引

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

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

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

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

24、標(biāo) 志。 使用計數(shù)：表示當(dāng)前有多少個進(jìn)程正在使用或打開了 該文件。 時間和日期：這個信息反映了文件創(chuàng)建、最后修改、 最后使用等情況，可用于對文件實施保護(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.文件目錄文件目錄 為了對眾多的文件進(jìn)行分門別類的管理，提高為了對眾多的文件進(jìn)行分門別類的管理，提高 文件檢索的效率，現(xiàn)代操作系統(tǒng)往往文件檢索的效率，現(xiàn)代操作系統(tǒng)往往將文件的將文件的 文件控制塊集中在一起進(jìn)行管理文件控制塊集中在一起進(jìn)行管理。 這種這種FCB的有序集合就稱為文件目錄的有序集合就稱為文件目錄，文件控，文件控 制塊就是其中的目錄項（構(gòu)成文件目錄的項制塊就是其中的目錄項（構(gòu)成文件目錄的項 目）。目）。 另外，為了實現(xiàn)對文件目錄的管理，另外，為了實現(xiàn)對文件目錄的管理，通常將文通常將文 件目錄以文件的形式保存在外

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

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

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

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

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

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

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

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

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

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

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

37、物理塊都對 應(yīng)一個比特位。應(yīng)一個比特位。 n如果該位為如果該位為“0”，則表示所對應(yīng)的塊是空閑，則表示所對應(yīng)的塊是空閑 塊；塊； n反之，如果該位為反之，如果該位為“1”，則表示所對應(yīng)的塊，則表示所對應(yīng)的塊 已被分配出去。已被分配出去。 73 圖 6-21 位示圖 3.位示圖位示圖 74 盤塊的分配：盤塊的分配： (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代

38、表每行的位數(shù)。 (3) 修改位示圖， 令mapi,j=1。 3.位示圖位示圖 75 盤塊的回收：盤塊的回收： (1) 將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列 號。 轉(zhuǎn)換公式為： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修改位示圖。 令map i,j=1。 3.位示圖位示圖 76 例題：例題： 在頁式存儲管理中，可以用位示圖表示內(nèi)存空閑塊狀 況。假設(shè)字長為32位，每一位(編號為0-31)與一個內(nèi) 存塊對應(yīng)，取值可為0或1。當(dāng)取值為1時表示對應(yīng)塊已 被占用，當(dāng)取值為0時表示對應(yīng)塊為空閑。 (1) 如果內(nèi)存可分配區(qū)被劃分為1024塊，則位示圖共 需要多少個字來表示？

39、A) 15 B) 16 C) 31 D) 32 答案：D (2) 已知某一位的字號是5，位號為14，假設(shè)字號也從 0開始編號。則對應(yīng)的內(nèi)存塊號是多少？（假設(shè)內(nèi)存塊 從0開始編號） A) 70 B) 105 C) 173 D) 224 答案：C 77 例題： 有一計算機系統(tǒng)利用下圖所示的位示圖來管理空 閑塊（行、列號均從0開始），如果塊號從1開 始，每個盤塊大小為1kb。 1.現(xiàn)要為文件分配兩個盤塊，具體說明分配過程。 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 空閑盤塊號 棧 S.free 0 1 98 99

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