第七講文件系統(tǒng)

1、目的與要求目的與要求：了解文件結(jié)構(gòu)，訪問方式，存儲結(jié)了解文件結(jié)構(gòu)，訪問方式，存儲結(jié)構(gòu)。掌握文件管理用的文件控制塊和文件目錄構(gòu)。掌握文件管理用的文件控制塊和文件目錄結(jié)構(gòu)。了解文件存儲器分區(qū)和空間管理。文件結(jié)構(gòu)。了解文件存儲器分區(qū)和空間管理。文件存放與訪問方式，文件目錄結(jié)構(gòu)。文件使用和存放與訪問方式，文件目錄結(jié)構(gòu)。文件使用和控制、文件保護(hù)控制、文件保護(hù)重點與難點重點與難點：掌握文件系統(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.為了對程序和數(shù)據(jù)實現(xiàn)按名存取。為為了對程序和數(shù)據(jù)實現(xiàn)按名存取。為了對外存儲器空間管理和對其上文件的了對外存儲器空間管理和對其上文件的按名訪問而引入文件系統(tǒng)按名訪問而引入文件系統(tǒng) 。為什么引入文件和文件系統(tǒng)為什么引入文件和文件系統(tǒng)文件系統(tǒng)的基礎(chǔ)是什么文件系統(tǒng)的基礎(chǔ)是什么? ?大容量磁盤大容

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

4、哪些？三、文件的基本特征有哪些？文件體內(nèi)容豐富，可以是源程序、文件體內(nèi)容豐富，可以是源程序、可執(zhí)行代碼、數(shù)據(jù)、表格、語言或可執(zhí)行代碼、數(shù)據(jù)、表格、語言或圖像等。圖像等。無論何種內(nèi)容的文件都用一個名無論何種內(nèi)容的文件都用一個名字唯一標(biāo)識，并都遵循按名存取原字唯一標(biāo)識，并都遵循按名存取原則。則。文件具有可重用性和可保存性。文件具有可重用性和可保存性。四、文件的分類四、文件的分類（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ū)動程序文件，注冊庫配置文件。動程序文件，注冊庫配置文件。庫文件。指系統(tǒng)提供的實用子程序庫，庫文件。指系統(tǒng)提供的實用子程序庫，用戶只能使用不能修改的程序文件。如用戶只能使用不能修改的程序文件。如C C語言、語言、PASCALPASCAL語言提供的子程序庫，語言提供的子程序庫，windowswindows中的中的 .dll .dll，.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）按保存時間分類）按保存時間分類臨時文件臨時文件永久文件永久文件（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)。目錄文件目錄文件-由下屬文件的目錄項構(gòu)由下屬文件的目錄項構(gòu)成的文件。成的文件。特殊文件特殊文件-特指各種外部設(shè)備。特指各種外部設(shè)備。五、文件存取方法五、文件存取方法 （1 1）順序存取法）順序存取法 按照文

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

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

9、順序存儲設(shè)備v如：磁帶如：磁帶 直接存儲設(shè)備（隨機存取設(shè)備）直接存儲設(shè)備（隨機存取設(shè)備）v如：磁盤、光盤、閃存等如：磁盤、光盤、閃存等7.2 7.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)，簡稱文件系統(tǒng)。文件管理系統(tǒng)，簡稱文件系統(tǒng)?；颍何募到y(tǒng)，就是操作系統(tǒng)中負(fù)或：文件系統(tǒng)，就是操作系統(tǒng)中負(fù)責(zé)操縱和管理文件的一整套設(shè)施，責(zé)操縱和管理文件的一整套設(shè)施，客觀存在實現(xiàn)文件的共享和保護(hù)，客觀存在實現(xiàn)文件的共享和保護(hù)，方便用戶方便用戶“按名存取按名存取”文件。文件。二、文件系統(tǒng)的功能二、文件系

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

11、由文件說明和文件體組成（二）文件控制塊（二）文件控制塊說明部分的全部信息集中起來，以一說明部分的全部信息集中起來，以一個數(shù)據(jù)結(jié)構(gòu)的形式表示，稱此結(jié)構(gòu)為個數(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)使用計數(shù)使用計數(shù)(7)(7)時間時間（四）文件目錄的組成（四）文件目錄的組成所有文件的文件控制塊的有序集合，所有

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

13、OSMS-DOS的目錄文件的目錄文件將上例文件目錄以一個名字存儲起來得將上例文件目錄以一個名字存儲起來得到的文件稱目錄文件。到的文件稱目錄文件。每個磁盤設(shè)備都有一個且只有一個根目每個磁盤設(shè)備都有一個且只有一個根目錄文件錄文件, ,但可以有很多子目錄文件但可以有很多子目錄文件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.一級目錄結(jié)構(gòu)一級目錄結(jié)構(gòu) 為外存上的全部文件設(shè)立一張線性排為外存上的全部文件設(shè)立一張線性排列的目錄表，包含所有文件的列的目錄表，包含所有文件的FCBFCB。每建。每建立一個新文件即在目錄中增加

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

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

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

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)的特點：樹型目錄結(jié)構(gòu)的特點：v利于文件分類，從文件路徑名可看出利于文件分類，從文件路徑名可看出文件類別；文件類別；v查找文件查找文件FCBFCB耗費時間，要得到文件耗費時間，要得到文件FCBFCB，必須從根查起；，必須從根查起；v惟

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

19、 list 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)的特點：無環(huán)圖目錄結(jié)構(gòu)的特點：vUnixUnix的文件系統(tǒng)采用這種結(jié)構(gòu)的文件系統(tǒng)采用這種結(jié)構(gòu)v優(yōu)點優(yōu)點: :方便文件共享，分類；方便文件共享，分類；v缺點缺點: :兩個或多個兩個或多個FCBFCB的一致性難以保的一致性難以保證（如刪除文件時，當(dāng)文件修改而引證（如刪除文件時，當(dāng)文件修改而引起起FCB

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

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

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

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

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

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

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

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

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

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

30、000%1024=832（表示取模）（表示取模） 使用直接地址，其物理地址是：使用直接地址，其物理地址是：101#塊內(nèi)的塊內(nèi)的832號地址。號地址。v（2）13 000/1024=12，13 000%1024=712 邏輯塊數(shù)邏輯塊數(shù)12超出直接地址范圍（超出直接地址范圍（10），但是?。?，但是小于于266 (=10+256),利用一次間接。從利用一次間接。從428#塊中塊中得到相應(yīng)的物理塊號為得到相應(yīng)的物理塊號為954。所以，其物理地。所以，其物理地址是：址是：954#塊內(nèi)的塊內(nèi)的712號地址。號地址。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項對應(yīng)的物理塊項對應(yīng)的物理塊331，再，再從從331塊中找到下標(biāo)為塊中找到下標(biāo)為75的項，進(jìn)而得到物理的項，進(jìn)而得到物理塊號塊號333。所以，其物理地址是：。所以，其物理地址是：333#塊內(nèi)的塊內(nèi)的816號地址。號地址。7.5.3 空閑存儲空間的管理目前常用的磁盤空閑空間管理技術(shù)主要目前常用的磁盤空閑空間管理技術(shù)主要有：

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

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

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

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

36、塊都對應(yīng)一個情況，也稱位向量法。每個盤塊都對應(yīng)一個二進(jìn)制位。如果盤塊是空閑的，對應(yīng)位是二進(jìn)制位。如果盤塊是空閑的，對應(yīng)位是1 1；如果已經(jīng)分出去，則對應(yīng)位是如果已經(jīng)分出去，則對應(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ù)一個磁盤的總盤塊

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

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

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

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

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

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

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