1、目的與要求目的與要求：了解文件結(jié)構(gòu)，訪問方式，存儲(chǔ)結(jié)了解文件結(jié)構(gòu)，訪問方式，存儲(chǔ)結(jié)構(gòu)。掌握文件管理用的文件控制塊和文件目錄構(gòu)。掌握文件管理用的文件控制塊和文件目錄結(jié)構(gòu)。了解文件存儲(chǔ)器分區(qū)和空間管理。文件結(jié)構(gòu)。了解文件存儲(chǔ)器分區(qū)和空間管理。文件存放與訪問方式，文件目錄結(jié)構(gòu)。文件使用和存放與訪問方式，文件目錄結(jié)構(gòu)。文件使用和控制、文件保護(hù)控制、文件保護(hù)重點(diǎn)與難點(diǎn)重點(diǎn)與難點(diǎn)：掌握文件系統(tǒng)調(diào)用處理及使掌握文件系統(tǒng)調(diào)用處理及使 用。了解文件備份與保護(hù)、系統(tǒng)的組成和各部用。了解文件備份與保護(hù)、系統(tǒng)的組成和各部分功能。分功能。第七章第七章 文件系統(tǒng)文件系統(tǒng)1.1.大量的程序和數(shù)據(jù)需要管理。為了大量的程序和數(shù)

2、據(jù)需要管理。為了方便使用管理系統(tǒng)的公共程序和數(shù)據(jù)方便使用管理系統(tǒng)的公共程序和數(shù)據(jù)以及用戶自己的程序和數(shù)據(jù)而引入文以及用戶自己的程序和數(shù)據(jù)而引入文件。件。為什么引入文件和文件系統(tǒng)為什么引入文件和文件系統(tǒng)2.2.內(nèi)存空間有限。不是所有的程序和數(shù)內(nèi)存空間有限。不是所有的程序和數(shù)據(jù)都能常駐內(nèi)存。據(jù)都能常駐內(nèi)存。3.3.為了對(duì)程序和數(shù)據(jù)實(shí)現(xiàn)按名存取。為為了對(duì)程序和數(shù)據(jù)實(shí)現(xiàn)按名存取。為了對(duì)外存儲(chǔ)器空間管理和對(duì)其上文件的了對(duì)外存儲(chǔ)器空間管理和對(duì)其上文件的按名訪問而引入文件系統(tǒng)按名訪問而引入文件系統(tǒng) 。為什么引入文件和文件系統(tǒng)為什么引入文件和文件系統(tǒng)文件系統(tǒng)的基礎(chǔ)是什么文件系統(tǒng)的基礎(chǔ)是什么? ?大容量磁盤大容

3、量磁盤7 7.1. .1. 概述概述一、什么是文件？一、什么是文件？文件（文件（filefile）是被命名的相關(guān)信息的集是被命名的相關(guān)信息的集合體。合體。它由創(chuàng)建者定義，通常存放在外存上，它由創(chuàng)建者定義，通常存放在外存上，可以作為一個(gè)獨(dú)立單位來實(shí)施相應(yīng)的操可以作為一個(gè)獨(dú)立單位來實(shí)施相應(yīng)的操作（如打開、關(guān)閉、讀寫等）。作（如打開、關(guān)閉、讀寫等）。二、文件的主要屬性包括哪些？二、文件的主要屬性包括哪些？ 文件名，文件類型，文件長(zhǎng)度，文件名，文件類型，文件長(zhǎng)度，創(chuàng)建者，創(chuàng)建時(shí)間，修改時(shí)間，創(chuàng)建者，創(chuàng)建時(shí)間，修改時(shí)間，文件定位信息文件定位信息 ，文件所包含的，文件所包含的信息。信息。三、文件的基本特征

4、有哪些？三、文件的基本特征有哪些？文件體內(nèi)容豐富，可以是源程序、文件體內(nèi)容豐富，可以是源程序、可執(zhí)行代碼、數(shù)據(jù)、表格、語言或可執(zhí)行代碼、數(shù)據(jù)、表格、語言或圖像等。圖像等。無論何種內(nèi)容的文件都用一個(gè)名無論何種內(nèi)容的文件都用一個(gè)名字唯一標(biāo)識(shí)，并都遵循按名存取原字唯一標(biāo)識(shí)，并都遵循按名存取原則。則。文件具有可重用性和可保存性。文件具有可重用性和可保存性。四、文件的分類四、文件的分類（1 1）按文件的用途分為）按文件的用途分為3 3類：類：系統(tǒng)文系統(tǒng)文件、庫文件和用戶文件件、庫文件和用戶文件系統(tǒng)文件。由操作系統(tǒng)及其他系統(tǒng)程系統(tǒng)文件。由操作系統(tǒng)及其他系統(tǒng)程序的信息所組成的文件。序的信息所組成的文件。如操

5、作系統(tǒng)核心目標(biāo)代碼文件，驅(qū)如操作系統(tǒng)核心目標(biāo)代碼文件，驅(qū)動(dòng)程序文件，注冊(cè)庫配置文件。動(dòng)程序文件，注冊(cè)庫配置文件。庫文件。指系統(tǒng)提供的實(shí)用子程序庫，庫文件。指系統(tǒng)提供的實(shí)用子程序庫，用戶只能使用不能修改的程序文件。如用戶只能使用不能修改的程序文件。如C C語言、語言、PASCALPASCAL語言提供的子程序庫，語言提供的子程序庫，windowswindows中的中的 . .dlldll，.exe.exe。用戶文件。如用戶源程序和數(shù)據(jù)文件，用戶文件。如用戶源程序和數(shù)據(jù)文件，各種應(yīng)用程序用的數(shù)據(jù)文件。各種應(yīng)用程序用的數(shù)據(jù)文件。（2 2）按文件中的數(shù)據(jù)形式分類）按文件中的數(shù)據(jù)形式分類源文件源文件目標(biāo)文

6、件目標(biāo)文件可執(zhí)行文件可執(zhí)行文件（3 3）按存取權(quán)限分類）按存取權(quán)限分類只讀文件只讀文件讀寫文件讀寫文件可執(zhí)行文件可執(zhí)行文件（4 4）按保存時(shí)間分類）按保存時(shí)間分類臨時(shí)文件臨時(shí)文件永久文件永久文件（5 5）按文件的內(nèi)部構(gòu)造和處理方式分類）按文件的內(nèi)部構(gòu)造和處理方式分類普通文件普通文件-由表示程序、數(shù)據(jù)或文由表示程序、數(shù)據(jù)或文本的字符串構(gòu)成，內(nèi)部沒有固定的結(jié)構(gòu)。本的字符串構(gòu)成，內(nèi)部沒有固定的結(jié)構(gòu)。目錄文件目錄文件-由下屬文件的目錄項(xiàng)構(gòu)由下屬文件的目錄項(xiàng)構(gòu)成的文件。成的文件。特殊文件特殊文件-特指各種外部設(shè)備。特指各種外部設(shè)備。五、文件存取方法五、文件存取方法 （1 1）順序存取法）順序存取法 按照

7、文件的邏輯地址順序來存取。按照文件的邏輯地址順序來存取。程序依次訪問文件的數(shù)據(jù)，操作系程序依次訪問文件的數(shù)據(jù)，操作系統(tǒng)自動(dòng)記錄文件訪問的當(dāng)前位置。統(tǒng)自動(dòng)記錄文件訪問的當(dāng)前位置。生活中的例子：生活中的例子：v文件歸檔時(shí)按文件編號(hào)順序存放，文件歸檔時(shí)按文件編號(hào)順序存放，查閱時(shí)按文件編號(hào)順序查找。查閱時(shí)按文件編號(hào)順序查找。（2 2）隨機(jī)存取法）隨機(jī)存取法 程序讀程序讀/ /寫時(shí)直接給出要訪問數(shù)據(jù)的寫時(shí)直接給出要訪問數(shù)據(jù)的邏輯位置（即記錄編號(hào)，如第幾個(gè)字邏輯位置（即記錄編號(hào)，如第幾個(gè)字節(jié)或第幾個(gè)記錄）及長(zhǎng)度，由節(jié)或第幾個(gè)記錄）及長(zhǎng)度，由OSOS將邏將邏輯位置轉(zhuǎn)換成物理位置并訪問輯位置轉(zhuǎn)換成物理位置并訪

8、問生活中的例子：生活中的例子：v文件存放時(shí)按自己的生活習(xí)慣把文文件存放時(shí)按自己的生活習(xí)慣把文件存放于自己易于記憶的地方，取件存放于自己易于記憶的地方，取閱時(shí)自己記?。ù竽X轉(zhuǎn)換）存放的閱時(shí)自己記?。ù竽X轉(zhuǎn)換）存放的地方。地方。（3 3）其他方法（如按鍵存取法，索引）其他方法（如按鍵存取法，索引存取法等）存取法等）按鍵存取法按鍵存取法文件的存取根據(jù)給定的鍵或記錄名進(jìn)文件的存取根據(jù)給定的鍵或記錄名進(jìn)行。行。生活中的例子：生活中的例子：文件存放時(shí)按文件名（如標(biāo)題）文件存放時(shí)按文件名（如標(biāo)題）分類存放，取閱時(shí)按文件類型查找。分類存放，取閱時(shí)按文件類型查找。六、文件的存儲(chǔ)介質(zhì)六、文件的存儲(chǔ)介質(zhì) 順序存儲(chǔ)設(shè)

9、備順序存儲(chǔ)設(shè)備v如：磁帶如：磁帶 直接存儲(chǔ)設(shè)備（隨機(jī)存取設(shè)備）直接存儲(chǔ)設(shè)備（隨機(jī)存取設(shè)備）v如：磁盤、光盤、閃存等如：磁盤、光盤、閃存等7 7.2 .2 文件系統(tǒng)的功能與結(jié)構(gòu)文件系統(tǒng)的功能與結(jié)構(gòu) 一、文件系統(tǒng)的概念一、文件系統(tǒng)的概念現(xiàn)代操作系統(tǒng)中都配置較為完備的現(xiàn)代操作系統(tǒng)中都配置較為完備的文件管理系統(tǒng)，簡(jiǎn)稱文件系統(tǒng)。文件管理系統(tǒng)，簡(jiǎn)稱文件系統(tǒng)?；颍何募到y(tǒng)，就是操作系統(tǒng)中負(fù)或：文件系統(tǒng)，就是操作系統(tǒng)中負(fù)責(zé)操縱和管理文件的一整套設(shè)施，責(zé)操縱和管理文件的一整套設(shè)施，客觀存在實(shí)現(xiàn)文件的共享和保護(hù)，客觀存在實(shí)現(xiàn)文件的共享和保護(hù)，方便用戶方便用戶“按名存取按名存取”文件。文件。二、文件系統(tǒng)的功能二、文

10、件系統(tǒng)的功能文件管理文件管理目錄管理目錄管理文件存儲(chǔ)空間管理文件存儲(chǔ)空間管理文件的共享與保護(hù)文件的共享與保護(hù)提供方便的接口提供方便的接口7.3 7.3 文件目錄結(jié)構(gòu)和目錄查詢文件目錄結(jié)構(gòu)和目錄查詢 為管理大量的文件，實(shí)現(xiàn)對(duì)文件為管理大量的文件，實(shí)現(xiàn)對(duì)文件信息的信息的“按名存取按名存取”，一般用文件目，一般用文件目錄的方法來管理文件，每個(gè)文件在文錄的方法來管理文件，每個(gè)文件在文件目錄中有一個(gè)目錄項(xiàng)。文件目錄記件目錄中有一個(gè)目錄項(xiàng)。文件目錄記錄所有文件的名字及它代表的文件存錄所有文件的名字及它代表的文件存放的物理地址。放的物理地址。（一）文件的內(nèi)涵（一）文件的內(nèi)涵一個(gè)文件由文件說明和文件體組成一個(gè)

11、文件由文件說明和文件體組成（二）文件控制塊（二）文件控制塊說明部分的全部信息集中起來，以一說明部分的全部信息集中起來，以一個(gè)數(shù)據(jù)結(jié)構(gòu)的形式表示，稱此結(jié)構(gòu)為個(gè)數(shù)據(jù)結(jié)構(gòu)的形式表示，稱此結(jié)構(gòu)為文件控制塊文件控制塊（FCBFCB）。）。因此，文件包含因此，文件包含文件控制塊和文件體。文件控制塊和文件體。（三）（三）FCBFCB的主要內(nèi)容：的主要內(nèi)容：(1)(1)文件名文件名(2)(2)文件類型文件類型(3)(3)文件位置文件位置(4)(4)文件大小文件大小(5)(5)保護(hù)信息保護(hù)信息(6)(6)使用計(jì)數(shù)使用計(jì)數(shù)(7)(7)時(shí)間時(shí)間（四）文件目錄的組成（四）文件目錄的組成所有文件的文件控制塊的有序集合，

12、所有文件的文件控制塊的有序集合，就構(gòu)成了就構(gòu)成了文件目錄文件目錄。完全由文件控制塊構(gòu)成的文件稱為完全由文件控制塊構(gòu)成的文件稱為目錄文件目錄文件。例：例：MS-DOSMS-DOS的文件控制塊的文件控制塊在在MS-DOSMS-DOS系統(tǒng)中，一個(gè)文件控制塊系統(tǒng)中，一個(gè)文件控制塊有有1616個(gè)字節(jié)長(zhǎng)，其中包含文件名，個(gè)字節(jié)長(zhǎng)，其中包含文件名，擴(kuò)展名、屬性、時(shí)間、日期、首塊擴(kuò)展名、屬性、時(shí)間、日期、首塊號(hào)和文件大小。如下圖示：號(hào)和文件大小。如下圖示：文件名文件名擴(kuò)展名擴(kuò)展名保留保留大小大小屬性屬性時(shí)間時(shí)間日期日期首塊號(hào)首塊號(hào)文件目錄文件目錄例：例：MS-DOSMS-DOS的文件目錄的文件目錄例：例：MS

13、-DOSMS-DOS的目錄文件的目錄文件將上例文件目錄以一個(gè)名字存儲(chǔ)起來得將上例文件目錄以一個(gè)名字存儲(chǔ)起來得到的文件稱目錄文件。到的文件稱目錄文件。每個(gè)磁盤設(shè)備都有一個(gè)且只有一個(gè)根目每個(gè)磁盤設(shè)備都有一個(gè)且只有一個(gè)根目錄文件錄文件, ,但可以有很多子目錄文件但可以有很多子目錄文件WINDOWSWINDOWS系統(tǒng)以文件夾圖標(biāo)標(biāo)示。系統(tǒng)以文件夾圖標(biāo)標(biāo)示。 7.3.2 7.3.2 文件的目錄結(jié)構(gòu)文件的目錄結(jié)構(gòu)1.1.一級(jí)目錄結(jié)構(gòu)一級(jí)目錄結(jié)構(gòu) 為外存上的全部文件設(shè)立一張線性排為外存上的全部文件設(shè)立一張線性排列的目錄表，包含所有文件的列的目錄表，包含所有文件的FCBFCB。每建每建立一個(gè)新文件即在目錄中增

14、加一個(gè)立一個(gè)新文件即在目錄中增加一個(gè)FCBFCB，每當(dāng)刪除一個(gè)文件即刪除對(duì)應(yīng)的每當(dāng)刪除一個(gè)文件即刪除對(duì)應(yīng)的FCBFCB，當(dāng)當(dāng)要訪問一個(gè)文件時(shí)，先按文件名在目錄要訪問一個(gè)文件時(shí)，先按文件名在目錄中找到對(duì)應(yīng)的文件中找到對(duì)應(yīng)的文件FCBFCB。然后由它的然后由它的FCBFCB映射其存放的物理地址。（見下圖示）映射其存放的物理地址。（見下圖示） FCB1 FCB2 FCB3 FCBn 文件1 文件2 文件3 文件n 一級(jí)目錄結(jié)構(gòu)示意圖一級(jí)目錄結(jié)構(gòu)示意圖FCBnn2.2.二級(jí)目錄結(jié)構(gòu)二級(jí)目錄結(jié)構(gòu) 設(shè)一個(gè)設(shè)一個(gè)主目錄主目錄MFDMFD，然后為系統(tǒng)的每個(gè)然后為系統(tǒng)的每個(gè)用戶設(shè)用戶設(shè)用戶目錄用戶目錄UFDUF

15、D。用戶目錄是用戶用戶目錄是用戶所有文件所有文件FCBFCB的集合，主目錄中存放每的集合，主目錄中存放每個(gè)用戶目錄的用戶目錄名和個(gè)用戶目錄的用戶目錄名和UFDUFD的索引的索引表等（當(dāng)我們把表等（當(dāng)我們把UFDUFD看做是一個(gè)文件，看做是一個(gè)文件，這個(gè)文件的內(nèi)容是用戶所有文件這個(gè)文件的內(nèi)容是用戶所有文件FCBFCB的的集合，集合，MFDMFD中則包含每個(gè)中則包含每個(gè)UFDUFD文件的文件的FCBFCB，見下圖示）。見下圖示）。 CAT BO A TEST X TEST DATA A A A DATA User1 User2 User4 User3 主文件目錄 用戶文件目錄 文件 二級(jí)目錄結(jié)構(gòu)示

16、意圖二級(jí)目錄結(jié)構(gòu)示意圖二級(jí)目錄結(jié)構(gòu)實(shí)現(xiàn)二級(jí)目錄結(jié)構(gòu)實(shí)現(xiàn)(1)(1)可以把主目錄和二級(jí)用戶目錄放可以把主目錄和二級(jí)用戶目錄放于外存頭部，也可以把二級(jí)目錄當(dāng)于外存頭部，也可以把二級(jí)目錄當(dāng)一般文件存放。一般文件存放。(2)(2) 將用戶名與文件名連到一起組將用戶名與文件名連到一起組成路經(jīng)名成路經(jīng)名, ,訪問時(shí)給出路徑名。訪問時(shí)給出路徑名。例如：例如：/ /OS/test.cOS/test.c。3.3.多級(jí)目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）多級(jí)目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）任何一級(jí)目錄中的任何一級(jí)目錄中的FCBFCB既可以描既可以描述次一級(jí)的子目錄，又可以描述述次一級(jí)的子目錄，又可以描述一個(gè)文件。一個(gè)文件。( (見下

17、圖見下圖) ) root programs mail e p hex count recorder list find prt last fist copy all list obj spell prog mail start dict spell bin find count hex recorder addr 樹型目錄結(jié)構(gòu)示意圖樹型目錄結(jié)構(gòu)示意圖樹型目錄結(jié)構(gòu)的特點(diǎn)：樹型目錄結(jié)構(gòu)的特點(diǎn)：v利于文件分類，從文件路徑名可看出利于文件分類，從文件路徑名可看出文件類別；文件類別；v查找文件查找文件FCBFCB耗費(fèi)時(shí)間，要得到文件耗費(fèi)時(shí)間，要得到文件FCBFCB，必須從根查起；必須從根查起；v惟一確定

18、文件的路徑名太長(zhǎng)，故引入惟一確定文件的路徑名太長(zhǎng)，故引入當(dāng)前目錄當(dāng)前目錄 概念，提供相對(duì)于當(dāng)前目錄概念，提供相對(duì)于當(dāng)前目錄的的相對(duì)路徑名相對(duì)路徑名可加速文件可加速文件FCBFCB的查找，的查找，進(jìn)程控制塊存有當(dāng)前目錄信息。進(jìn)程控制塊存有當(dāng)前目錄信息。4.4.無環(huán)圖目錄結(jié)構(gòu)無環(huán)圖目錄結(jié)構(gòu)當(dāng)一個(gè)文件副本可以同時(shí)分到兩個(gè)不當(dāng)一個(gè)文件副本可以同時(shí)分到兩個(gè)不同目錄（類別）時(shí)，即同一個(gè)文件有同目錄（類別）時(shí)，即同一個(gè)文件有兩條路徑名或多條路徑名時(shí)出現(xiàn)無環(huán)兩條路徑名或多條路徑名時(shí)出現(xiàn)無環(huán)圖目錄結(jié)構(gòu)。圖目錄結(jié)構(gòu)。( (見下圖見下圖) ) root dict spell list root rade W7 li

19、st count p 無環(huán)圖目錄結(jié)構(gòu)示意圖無環(huán)圖目錄結(jié)構(gòu)示意圖圖中目錄圖中目錄dictdict與與 spellspell共享文件共享文件count,count,共享子目錄共享子目錄p.p.圖中目錄圖中目錄dictdict與其子與其子目錄目錄p p共享文件共享文件root.root.無環(huán)圖目錄結(jié)構(gòu)的特點(diǎn)：無環(huán)圖目錄結(jié)構(gòu)的特點(diǎn)：vUnixUnix的文件系統(tǒng)采用這種結(jié)構(gòu)的文件系統(tǒng)采用這種結(jié)構(gòu)v優(yōu)點(diǎn)優(yōu)點(diǎn): :方便文件共享，分類；方便文件共享，分類；v缺點(diǎn)缺點(diǎn): :兩個(gè)或多個(gè)兩個(gè)或多個(gè)FCBFCB的一致性難以保的一致性難以保證（如刪除文件時(shí)，當(dāng)文件修改而引證（如刪除文件時(shí)，當(dāng)文件修改而引起起FCBFCB

20、內(nèi)容變化時(shí)）。內(nèi)容變化時(shí)）。 5. 5.無環(huán)圖目錄結(jié)構(gòu)無環(huán)圖目錄結(jié)構(gòu)一種變通的實(shí)現(xiàn)方一種變通的實(shí)現(xiàn)方法法 符號(hào)鏈接符號(hào)鏈接建立多個(gè)符號(hào)鏈文件，該文件內(nèi)容為建立多個(gè)符號(hào)鏈文件，該文件內(nèi)容為要訪問文件的路徑名。要訪問文件的路徑名。當(dāng)訪問符號(hào)鏈文件時(shí)，讀出文件中的當(dāng)訪問符號(hào)鏈文件時(shí)，讀出文件中的路徑名，再重新從根查找路徑名代表路徑名，再重新從根查找路徑名代表的文件的文件FCB。無環(huán)圖目錄結(jié)構(gòu)dictcountcountrootspellroot/dict/countcountlistroot/dict/countcountroot/dict/countcountroot/dict/countcoun

21、t目錄目錄dictdict與與spellspell目錄共享目錄目錄共享目錄count,count,只在只在spellspell目錄中指明目錄中指明countcount的路徑的路徑7.4 7.4 文件和目錄的操作文件和目錄的操作 （略）（略）7.5 7.5 文件系統(tǒng)的實(shí)現(xiàn)文件系統(tǒng)的實(shí)現(xiàn) 7.5.1.7.5.1.文件系統(tǒng)的格式文件系統(tǒng)的格式（略）（略） 7.5.2 7.5.2 文件存儲(chǔ)分配文件存儲(chǔ)分配目前常用的文件分配方法有：連續(xù)分配、目前常用的文件分配方法有：連續(xù)分配、鏈接分配和索引分配三種。鏈接分配和索引分配三種。 1.1.連續(xù)分配連續(xù)分配-把一組連續(xù)的盤塊分把一組連續(xù)的盤塊分配給一個(gè)文件。配

22、給一個(gè)文件。采用連續(xù)分配方法可把邏輯文件中的采用連續(xù)分配方法可把邏輯文件中的信息順序地存放到一組相鄰的物理盤信息順序地存放到一組相鄰的物理盤塊中，這樣形成的物理文件稱為連續(xù)塊中，這樣形成的物理文件稱為連續(xù)文件（或順序文件）。文件（或順序文件）。連續(xù)分配舉例連續(xù)分配舉例 存存儲(chǔ)儲(chǔ)器器0123456789101112 1314151617 1819202122 2324文件分配表文件分配表 連續(xù)文件的優(yōu)缺點(diǎn)連續(xù)文件的優(yōu)缺點(diǎn)v優(yōu)點(diǎn)：順序訪問容易、速度快。優(yōu)點(diǎn)：順序訪問容易、速度快。v缺點(diǎn)：缺點(diǎn)：要求有連續(xù)的存儲(chǔ)空間。要求有連續(xù)的存儲(chǔ)空間。必須事先知道文件的長(zhǎng)度。必須事先知道文件的長(zhǎng)度。2.2.鏈接分

23、配鏈接分配-把邏輯上連續(xù)的把邏輯上連續(xù)的文件文件不連續(xù)地存放于不同的盤塊上，并使不連續(xù)地存放于不同的盤塊上，并使用指針按文件數(shù)據(jù)順序?qū)⑵滏溄悠饋?。用指針按文件?shù)據(jù)順序?qū)⑵滏溄悠饋怼０存溄臃峙浞椒ㄐ纬傻奈募Q鏈接文按鏈接分配方法形成的文件稱鏈接文件或串連文件。件或串連文件。文件鏈?zhǔn)浇Y(jié)構(gòu)例文件鏈?zhǔn)浇Y(jié)構(gòu)例11282316R0R0R1R1R2R2R3R3R4R4邏輯文件邏輯文件ABCABC文件分配表文件分配表鏈接文件的優(yōu)點(diǎn)鏈接文件的優(yōu)點(diǎn)可以充分利用磁盤中零散的空閑塊，可以充分利用磁盤中零散的空閑塊，提高外存空間的利用率。提高外存空間的利用率。消除外部碎片。消除外部碎片。但訪問或查找只能順著指針鏈進(jìn)行但

24、訪問或查找只能順著指針鏈進(jìn)行, ,速度較慢速度較慢, ,當(dāng)需要的磁盤塊較多時(shí)當(dāng)需要的磁盤塊較多時(shí), ,鏈條很長(zhǎng)鏈條很長(zhǎng). .3.3.索引分配索引分配-為每個(gè)文件分配一個(gè)為每個(gè)文件分配一個(gè)索引表，把分配給該文件的所有盤塊索引表，把分配給該文件的所有盤塊號(hào)都記錄在該索引表中，索引表本身號(hào)都記錄在該索引表中，索引表本身也存放在一個(gè)盤塊中。也存放在一個(gè)盤塊中。按這種分配方式存儲(chǔ)的文件就是索引按這種分配方式存儲(chǔ)的文件就是索引文件。文件。 文件索引結(jié)構(gòu)存存儲(chǔ)儲(chǔ)器器FCB索引表索引表12043112823161128231619索引文件優(yōu)點(diǎn)索引文件優(yōu)點(diǎn) 主要是提高了文件的查找速度，主要是提高了文件的查找速度

25、，也不會(huì)產(chǎn)生外部碎片，當(dāng)文件較也不會(huì)產(chǎn)生外部碎片，當(dāng)文件較大時(shí)，索引分配方式優(yōu)于鏈接分大時(shí)，索引分配方式優(yōu)于鏈接分配方式。配方式。 4 4、多重索引分配：如果索引表過大，、多重索引分配：如果索引表過大，可以組織成如下的多級(jí)索引表，這樣單可以組織成如下的多級(jí)索引表，這樣單個(gè)索引表可以定長(zhǎng)，利于實(shí)現(xiàn)，下面是個(gè)索引表可以定長(zhǎng)，利于實(shí)現(xiàn)，下面是多級(jí)索引表示意圖多級(jí)索引表示意圖二級(jí)索引表二級(jí)索引表一級(jí)索引表一級(jí)索引表數(shù)據(jù)塊數(shù)據(jù)塊多重索引多重索引分配例：分配例：UNIXUNIX的文的文件系統(tǒng)采件系統(tǒng)采用多重索用多重索引分配方引分配方式。式。UnixUnix系統(tǒng)多重索引分配例系統(tǒng)多重索引分配例：設(shè)盤塊大小為

26、：設(shè)盤塊大小為1KB1KB，盤塊號(hào)用盤塊號(hào)用4 4個(gè)字節(jié)表示。個(gè)字節(jié)表示。對(duì)于一般文件來說，其大小多數(shù)在對(duì)于一般文件來說，其大小多數(shù)在10KB10KB以內(nèi)，可以利用直接項(xiàng)立即得到存放數(shù)據(jù)的以內(nèi)，可以利用直接項(xiàng)立即得到存放數(shù)據(jù)的盤塊號(hào)，因而存取速度較快。直接項(xiàng)能夠存盤塊號(hào)，因而存取速度較快。直接項(xiàng)能夠存放的最大文件長(zhǎng)度為放的最大文件長(zhǎng)度為10KB10KB。對(duì)于大于對(duì)于大于10KB10KB的中小型文件，可對(duì)的中小型文件，可對(duì)1010塊塊以上的部分采用一次間接（它至多可以放以上的部分采用一次間接（它至多可以放1KB1KB4=1024B4=1024B4=2564=256個(gè)盤塊），一次間接允個(gè)盤塊），一

27、次間接允許文件長(zhǎng)達(dá)許文件長(zhǎng)達(dá)2562561KB=256KBKB=256KB。對(duì)于大于對(duì)于大于266KB266KB（10KB+256KB10KB+256KB）的中大）的中大型文件，超過型文件，超過266KB266KB的部分，則接著采用二次的部分，則接著采用二次間接（它至多可以放間接（它至多可以放256256256256個(gè)盤塊號(hào)），個(gè)盤塊號(hào)），二次間接允許文件長(zhǎng)達(dá)二次間接允許文件長(zhǎng)達(dá)2562562562561KB=64MB1KB=64MB。對(duì)于大于對(duì)于大于10KB+256KB+64MB10KB+256KB+64MB的巨型文件，的巨型文件，則接著采用三次間接（它最多可以放則接著采用三次間接（它最多可

28、以放256256256256256256個(gè)盤塊號(hào)），三次間接允許的個(gè)盤塊號(hào)），三次間接允許的文件長(zhǎng)達(dá)文件長(zhǎng)達(dá)2562562562562562561KB=16GB1KB=16GB。小結(jié)：小結(jié)：UNIXUNIX采用這種多重索引分配方式，采用這種多重索引分配方式，一個(gè)文件的最大容量是：一個(gè)文件的最大容量是：10KB+256KB+64MB+16GB10KB+256KB+64MB+16GB11億字節(jié)億字節(jié)。例：在例：在UnixUnix系統(tǒng)中，假定磁盤塊大小是系統(tǒng)中，假定磁盤塊大小是1KB1KB，每，每個(gè)盤塊號(hào)占個(gè)盤塊號(hào)占4B4B，文件索引節(jié)點(diǎn)中的磁盤地址明，文件索引節(jié)點(diǎn)中的磁盤地址明細(xì)表如下圖所示，請(qǐng)將

29、下列文件的字節(jié)偏移量細(xì)表如下圖所示，請(qǐng)將下列文件的字節(jié)偏移量轉(zhuǎn)換為物理地址（寫出計(jì)算過程）。轉(zhuǎn)換為物理地址（寫出計(jì)算過程）。（1 1）80008000（2 2）1300013000（3 3）350000350000409622845428931111150101367174289156824直直接接地地址址一次間接一次間接二次間接二次間接三次間接三次間接1091011954952428#9156#3314523300333308331#01747576012345678910111201220052554095255v 解：（解：（1）8000/1024=7（表示整除），（表示整除），8000

30、%1024=832（表示取模）（表示取模） 使用直接地址，其物理地址是：使用直接地址，其物理地址是：101#塊內(nèi)的塊內(nèi)的832號(hào)地址。號(hào)地址。v（2）13 000/1024=12，13 000%1024=712 邏輯塊數(shù)邏輯塊數(shù)12超出直接地址范圍（超出直接地址范圍（10），但是?。切∮谟?66 (=10+256),利用一次間接。從利用一次間接。從428#塊中塊中得到相應(yīng)的物理塊號(hào)為得到相應(yīng)的物理塊號(hào)為954。所以，其物理地。所以，其物理地址是：址是：954#塊內(nèi)的塊內(nèi)的712號(hào)地址。號(hào)地址。v （3）解：）解：v350 000/1024=341，350 000%1 024=816 邏輯

31、塊數(shù)邏輯塊數(shù)341超出一次間接地址范圍超出一次間接地址范圍(266)，但，但是小于是小于65 802(=10+256+65536），利用二次），利用二次間接。間接。341-（10+256）=75，75/256=0，75%256=75。v從從9156#塊中找到第塊中找到第0項(xiàng)對(duì)應(yīng)的物理塊項(xiàng)對(duì)應(yīng)的物理塊331，再，再從從331塊中找到下標(biāo)為塊中找到下標(biāo)為75的項(xiàng)，進(jìn)而得到物理的項(xiàng)，進(jìn)而得到物理塊號(hào)塊號(hào)333。所以，其物理地址是：。所以，其物理地址是：333#塊內(nèi)的塊內(nèi)的816號(hào)地址。號(hào)地址。7.5.3 空閑存儲(chǔ)空間的管理目前常用的磁盤空閑空間管理技術(shù)主要目前常用的磁盤空閑空間管理技術(shù)主要有：有：1

32、.1.空閑空間表法空閑空間表法2.2.空閑塊鏈接法空閑塊鏈接法3.3.位示圖法位示圖法4.4.成組鏈接法。成組鏈接法。1.1.空閑空間表法空閑空間表法(1)(1)空閑空間表。為了記載磁盤上哪些盤塊空閑空間表。為了記載磁盤上哪些盤塊是空閑的，文件系統(tǒng)需要?jiǎng)?chuàng)建空閑空間表。是空閑的，文件系統(tǒng)需要?jiǎng)?chuàng)建空閑空間表。如圖：如圖：(2)(2)空閑塊分配?？臻e塊分配。在新建文件時(shí)，要為它分配盤空間。在新建文件時(shí)，要為它分配盤空間。為此系統(tǒng)檢索空閑空間表，按一定算為此系統(tǒng)檢索空閑空間表，按一定算法找到合適文件大小的表項(xiàng)分配出去，法找到合適文件大小的表項(xiàng)分配出去，并在文件分配表中登記。如果對(duì)應(yīng)空并在文件分配表中登

33、記。如果對(duì)應(yīng)空閑區(qū)的大小恰好是所申請(qǐng)的，就把該閑區(qū)的大小恰好是所申請(qǐng)的，就把該從表中刪除；如果該區(qū)大于所需數(shù)量，從表中刪除；如果該區(qū)大于所需數(shù)量，則把分配后剩余的部分記在表項(xiàng)中。則把分配后剩余的部分記在表項(xiàng)中?？臻e塊分配例如：空閑塊分配例如：空閑空間表前述圖。新建文件空閑空間表前述圖。新建文件ABCABC，大小為，大小為3KB3KB時(shí)，系統(tǒng)在空閑空間表中找到第時(shí)，系統(tǒng)在空閑空間表中找到第1 1項(xiàng)的空間能項(xiàng)的空間能滿足，故將序號(hào)滿足，故將序號(hào)1 1的空閑空間分配出去的空閑空間分配出去3 3塊，余塊，余下的下的1 1塊繼續(xù)留在空閑空間表并修改數(shù)據(jù)，并塊繼續(xù)留在空閑空間表并修改數(shù)據(jù)，并將分配出去的盤

34、塊登記在文件分配表中。設(shè)分將分配出去的盤塊登記在文件分配表中。設(shè)分配前文件分配表如下表：配前文件分配表如下表：分配前的文件分配表分配前的文件分配表修改空閑空間表：修改空閑空間表：修改文件分配表修改文件分配表 (3)(3)空閑塊回收空閑塊回收在刪除文件時(shí)，系統(tǒng)回收該文件占用的盤塊，在刪除文件時(shí)，系統(tǒng)回收該文件占用的盤塊，且把相應(yīng)的空閑塊信息填回空閑空間表中。如且把相應(yīng)的空閑塊信息填回空閑空間表中。如果釋放的盤區(qū)和原有的空閑區(qū)相鄰接，則合并果釋放的盤區(qū)和原有的空閑區(qū)相鄰接，則合并成一個(gè)大的空閑區(qū)，記在一個(gè)表項(xiàng)中。成一個(gè)大的空閑區(qū)，記在一個(gè)表項(xiàng)中。如圖：若刪除文件如圖：若刪除文件C C，則要在此文件

35、分配表中刪，則要在此文件分配表中刪除文件除文件C C的目錄項(xiàng)。的目錄項(xiàng)。并修改空閑空間表。并修改空閑空間表。由于文件由于文件C C的盤塊與表的盤塊與表中的序號(hào)中的序號(hào)2 2相鄰接，故相鄰接，故合并成一個(gè)大空閑區(qū)。合并成一個(gè)大空閑區(qū)。修改空閑空間表：修改空閑空間表：修改文件分配表修改文件分配表 2.2.空閑塊鏈接法空閑塊鏈接法 這種方法與串這種方法與串連文件結(jié)構(gòu)相似，連文件結(jié)構(gòu)相似，只是鏈接的是空只是鏈接的是空閑塊而已。閑塊而已。 分配與回收。分配與回收。（略）（略）3.3.位示圖法位示圖法 它利用一串二進(jìn)位值反映磁盤空間的分配它利用一串二進(jìn)位值反映磁盤空間的分配情況，也稱位向量法。每個(gè)盤塊都對(duì)

36、應(yīng)一個(gè)情況，也稱位向量法。每個(gè)盤塊都對(duì)應(yīng)一個(gè)二進(jìn)制位。如果盤塊是空閑的，對(duì)應(yīng)位是二進(jìn)制位。如果盤塊是空閑的，對(duì)應(yīng)位是1 1；如果已經(jīng)分出去，則對(duì)應(yīng)位是如果已經(jīng)分出去，則對(duì)應(yīng)位是0 0。例如：設(shè)下列盤塊是空閑的：例如：設(shè)下列盤塊是空閑的：2,3,4,5,8,9,10,11,12,13,17,18,25,26,22,3,4,5,8,9,10,11,12,13,17,18,25,26,27 7, ,則位示圖向量是：則位示圖向量是：00111100111111000110000001110011110011111100011000000111如何構(gòu)造位示圖？如何構(gòu)造位示圖？ 根據(jù)一個(gè)磁盤的總盤塊數(shù)決定

37、位示圖由多少根據(jù)一個(gè)磁盤的總盤塊數(shù)決定位示圖由多少字組成。字組成。例：假定有一個(gè)盤組共有例：假定有一個(gè)盤組共有100100個(gè)柱面（編號(hào)為個(gè)柱面（編號(hào)為0-0-9999），每個(gè)柱面有），每個(gè)柱面有8 8個(gè)磁道（編號(hào)為個(gè)磁道（編號(hào)為0-70-7），每個(gè)），每個(gè)盤面分為盤面分為4 4個(gè)扇區(qū)（編號(hào)為個(gè)扇區(qū)（編號(hào)為0-30-3）。那么，整個(gè)磁）。那么，整個(gè)磁盤空間共有盤空間共有4 48 8100=3200100=3200個(gè)磁盤塊可用來存儲(chǔ)個(gè)磁盤塊可用來存儲(chǔ)信息。如果用字長(zhǎng)信息。如果用字長(zhǎng)3232位的字來構(gòu)造位示圖，共需位的字來構(gòu)造位示圖，共需100100個(gè)字。如下圖示：個(gè)字。如下圖示：位示圖如下位示圖如

38、下: : 如果磁盤塊的塊號(hào)按柱面順序來編號(hào)如果磁盤塊的塊號(hào)按柱面順序來編號(hào), ,則第則第0 0柱面柱面第第0 0盤面上的塊號(hào)是盤面上的塊號(hào)是0,1,2,3,0,1,2,3,第第0 0柱面第柱面第1 1盤面上的盤面上的塊號(hào)是塊號(hào)是4,5,6,7,4,5,6,7,依次計(jì)算依次計(jì)算, ,第第0 0柱面上共有柱面上共有3232塊塊, ,編編號(hào)為號(hào)為031,031,第第1 1柱面的塊號(hào)就為柱面的塊號(hào)就為32633263于是于是, ,位位示圖中第示圖中第i i個(gè)字的第個(gè)字的第j j位對(duì)應(yīng)的塊號(hào)為位對(duì)應(yīng)的塊號(hào)為: :塊號(hào)塊號(hào)=i=i32+j 塊空間分配過程。塊空間分配過程。（1 1）當(dāng)有文件要存放到磁盤上時(shí)

39、）當(dāng)有文件要存放到磁盤上時(shí), ,查找位示圖中查找位示圖中為為“0”0”的位的位, ,表示對(duì)應(yīng)的磁盤塊空閑可供使用。表示對(duì)應(yīng)的磁盤塊空閑可供使用。根據(jù)查到的位號(hào)和字號(hào)就可計(jì)算出塊號(hào)，同時(shí)在根據(jù)查到的位號(hào)和字號(hào)就可計(jì)算出塊號(hào)，同時(shí)在該位上填上占用標(biāo)志該位上填上占用標(biāo)志“1”1”。（2 2）磁盤定位。根據(jù)塊號(hào)計(jì)算出本塊所在的柱）磁盤定位。根據(jù)塊號(hào)計(jì)算出本塊所在的柱面號(hào)，盤面號(hào)（磁頭號(hào)）和扇區(qū)號(hào)。面號(hào)，盤面號(hào)（磁頭號(hào)）和扇區(qū)號(hào)。柱面號(hào)柱面號(hào)=塊號(hào)塊號(hào)/32/32磁頭號(hào)磁頭號(hào)=（塊號(hào)（塊號(hào) MOD 32MOD 32）/4/4扇區(qū)號(hào)扇區(qū)號(hào)= =（塊號(hào)（塊號(hào) MOD 32MOD 32）MOD 4MOD 4塊

40、空間回收（刪除）過程。塊空間回收（刪除）過程。（1 1）當(dāng)刪除文件歸還存儲(chǔ)空間時(shí)，可以根據(jù)歸）當(dāng)刪除文件歸還存儲(chǔ)空間時(shí)，可以根據(jù)歸還的位置推算出塊號(hào)和在位示圖中的位置：還的位置推算出塊號(hào)和在位示圖中的位置：塊號(hào)塊號(hào)= =柱面號(hào)柱面號(hào)32+32+磁頭號(hào)磁頭號(hào)4+扇區(qū)號(hào)扇區(qū)號(hào)字號(hào)字號(hào)=塊號(hào)塊號(hào)/32/32位號(hào)位號(hào)= =塊號(hào)塊號(hào) MOD 32MOD 32（2 2）把位示圖中對(duì)應(yīng)的位號(hào)、字號(hào)所在位的占）把位示圖中對(duì)應(yīng)的位號(hào)、字號(hào)所在位的占用標(biāo)志改為用標(biāo)志改為“0”0”。例例1有一計(jì)算機(jī)系統(tǒng)采用如下表所示的位示圖（字號(hào)、有一計(jì)算機(jī)系統(tǒng)采用如下表所示的位示圖（字號(hào)、位號(hào)都從位號(hào)都從0開始編號(hào)）來管理空閑盤

41、塊。如果盤塊從開始編號(hào)）來管理空閑盤塊。如果盤塊從0開開始編號(hào)，每個(gè)盤塊的大小為始編號(hào)，每個(gè)盤塊的大小為1KB。（1）現(xiàn)要為文件分配兩個(gè)盤塊，試具體說明分配過程。）現(xiàn)要為文件分配兩個(gè)盤塊，試具體說明分配過程。（2）若要釋放磁盤的第）若要釋放磁盤的第300塊，應(yīng)如何處理？塊，應(yīng)如何處理？【解解】 （1）為某文件分配兩個(gè)盤塊的過程如下：）為某文件分配兩個(gè)盤塊的過程如下：順序檢索位示圖，從中找到第一個(gè)值為順序檢索位示圖，從中找到第一個(gè)值為0的二進(jìn)制的二進(jìn)制位，得到其字號(hào)位，得到其字號(hào)i1=1，位號(hào)，位號(hào)j1=5;第二個(gè)值為第二個(gè)值為0的二的二進(jìn)制位，得到其字號(hào)進(jìn)制位，得到其字號(hào)i2=1,位號(hào)位號(hào)j2

42、=10。計(jì)算出找到的兩個(gè)空閑塊的盤塊號(hào)分別為：計(jì)算出找到的兩個(gè)空閑塊的盤塊號(hào)分別為： b1i116j1=116521 b2i216j211610=26修改位示圖，令修改位示圖，令Map1,5=Map1,10=1，并，并將對(duì)應(yīng)塊將對(duì)應(yīng)塊21, 26分配出去。分配出去。（2）釋放磁盤的第）釋放磁盤的第300塊時(shí)，應(yīng)進(jìn)行如下處理：塊時(shí)，應(yīng)進(jìn)行如下處理： 計(jì)算出磁盤第計(jì)算出磁盤第300塊所對(duì)應(yīng)二進(jìn)制位的字號(hào)塊所對(duì)應(yīng)二進(jìn)制位的字號(hào)i和位和位號(hào)號(hào)j：i=300/1618，j=300 Mod 1612 修改位示圖，令修改位示圖，令Map18,12=0,表示對(duì)應(yīng)塊為空表示對(duì)應(yīng)塊為空閑塊。閑塊。4.4.空閑塊成

43、組鏈接法。空閑塊成組鏈接法。（1 1）空閑塊成組鏈接）空閑塊成組鏈接 此法是把所有空閑盤塊按固定數(shù)量分組，例如每此法是把所有空閑盤塊按固定數(shù)量分組，例如每50個(gè)空閑塊為一組，組中的第個(gè)空閑塊為一組，組中的第1塊為塊為“組長(zhǎng)組長(zhǎng)”塊。塊。第第1組的組的50個(gè)空閑塊塊號(hào)放在第個(gè)空閑塊塊號(hào)放在第2組的組長(zhǎng)塊中，而組的組長(zhǎng)塊中，而第第2組的其余組的其余49塊是完全空閑的。第塊是完全空閑的。第2組的組的50個(gè)塊號(hào)個(gè)塊號(hào)又放在第三組的組長(zhǎng)塊中。依此類推，組與組之間又放在第三組的組長(zhǎng)塊中。依此類推，組與組之間形成鏈接關(guān)系。最后一組的塊號(hào)（可能不足形成鏈接關(guān)系。最后一組的塊號(hào)（可能不足50塊）塊）通常放在內(nèi)存的一個(gè)專用棧（即文件系統(tǒng)超級(jí)塊中通常放在內(nèi)存的一個(gè)專用棧（即文件系統(tǒng)超級(jí)塊中的空閑塊號(hào)棧）結(jié)構(gòu)中。這樣，平常對(duì)盤塊的分配的空閑塊號(hào)棧）結(jié)構(gòu)中。這樣，平常對(duì)盤塊的分配和釋放在棧中（或構(gòu)成新的一組）進(jìn)行，如下圖。和釋放在棧中（或構(gòu)成新的一組）進(jìn)行，如下圖。UNIX系統(tǒng)中就采用這種方法。系統(tǒng)中就采用這種方法。（2）空閑塊分配）空閑塊分配 當(dāng)需要為新建文件分配空閑盤塊時(shí)，總當(dāng)需要為新建文件分配空閑盤塊時(shí)，總是先把超級(jí)塊中表