第五章文件系統(tǒng)

1、操作系統(tǒng)原理與實踐操作系統(tǒng)原理與實踐高等教育出版社第五章 文件系統(tǒng)第五章文件系統(tǒng)第五章文件系統(tǒng)l目的與要求目的與要求：掌握文件、文件系統(tǒng)、目錄的：掌握文件、文件系統(tǒng)、目錄的定義，掌握文件系統(tǒng)的實現(xiàn)、文件的分配及定義，掌握文件系統(tǒng)的實現(xiàn)、文件的分配及空閑空間的管理等關鍵技術。了解具體操作空閑空間的管理等關鍵技術。了解具體操作系統(tǒng)的文件系統(tǒng)的實現(xiàn)原理。系統(tǒng)的文件系統(tǒng)的實現(xiàn)原理。l重點與難點重點與難點：文件系統(tǒng)、目錄的定義：文件系統(tǒng)、目錄的定義,文件文件的分配，磁盤空閑空間的管理。的分配，磁盤空閑空間的管理。l作業(yè)作業(yè)： 2 2、3 3、4 4、5 5。主要內容主要內容5.1 5.1 概述概述 5.

2、2 5.2 文件文件 5.3 5.3 文件的訪問文件的訪問 5.4 5.4 文件保護文件保護5.5 5.5 目錄結構目錄結構5.6 5.6 文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)5.7 5.7 空閑空間管理空閑空間管理5.8 5.8 性能和可靠性性能和可靠性5.9 5.9 文件系統(tǒng)實例文件系統(tǒng)實例 文件是操作系統(tǒng)中最重要的概念之一。它文件是操作系統(tǒng)中最重要的概念之一。它是操作系統(tǒng)對底層硬件（即存儲介質）最典型是操作系統(tǒng)對底層硬件（即存儲介質）最典型的抽象之一。有了文件以后，人們總是考慮數(shù)的抽象之一。有了文件以后，人們總是考慮數(shù)據(jù)保存在哪一個文件中，而不是某個存儲介質據(jù)保存在哪一個文件中，而不是某個存儲介

3、質的具體位置。的具體位置。 本章首先介紹文件系統(tǒng)中一些基本概念，本章首先介紹文件系統(tǒng)中一些基本概念，接著再著重介紹文件系統(tǒng)的實現(xiàn)，最后結合兩接著再著重介紹文件系統(tǒng)的實現(xiàn)，最后結合兩個具體的例子（個具體的例子（FAT和和ext2）來講解文件系統(tǒng)）來講解文件系統(tǒng)的具體實現(xiàn)。的具體實現(xiàn)。5.1概述概述5.2 5.2 文件文件 5.2.1 5.2.1 文件的概念文件的概念 5.2.2 5.2.2 文件的屬性文件的屬性 5.2.3 5.2.3 文件的操作文件的操作 5.2.4 5.2.4 文件的類型文件的類型 5.2.5 5.2.5 文件的結構文件的結構5.2.15.2.1文件的概念文件的概念文件文件是

4、一組或者多組相關信息的集合。是一組或者多組相關信息的集合。對于普通用戶來說，文件是最小的數(shù)據(jù)存儲對于普通用戶來說，文件是最小的數(shù)據(jù)存儲單元。文件中保存的內容可以是數(shù)值、文本單元。文件中保存的內容可以是數(shù)值、文本或者二進制的機器代碼。有些文件沒有特定或者二進制的機器代碼。有些文件沒有特定的格式，例如常用的的格式，例如常用的ASCIIASCII文本文件；有些文本文件；有些則包含很復雜的格式，例如可執(zhí)行程序文件。則包含很復雜的格式，例如可執(zhí)行程序文件。5.2 5.2 文件文件5.2.2 5.2.2 文件的屬性文件的屬性名稱名稱類型類型大小大小保護保護擁有者擁有者時間信息時間信息5.2 5.2 文件文

5、件5.2 5.2 文件文件5.2.3 5.2.3 文件的操作文件的操作 文件本質上是一種抽象數(shù)據(jù)類型。除了文件屬文件本質上是一種抽象數(shù)據(jù)類型。除了文件屬性以外，我們還需要定義對文件各種允許的操作。性以外，我們還需要定義對文件各種允許的操作。創(chuàng)建文件創(chuàng)建文件打開文件打開文件關閉文件關閉文件讀取文件讀取文件寫入文件寫入文件刪除文件刪除文件屬性修改屬性修改5.2 5.2 文件文件5.2.4 5.2.4 文件類型文件類型 文件類型文件類型常用擴展名常用擴展名意義意義可執(zhí)行文件exe, bin, com或無擴展名包含可以在系統(tǒng)上執(zhí)行的機器代碼，一般由編譯器生成源程序文件c, cpp, asm一般由程序員

6、編寫的源代碼，不同的編程語言使用的擴展名也不相同目標文件obj, o已經(jīng)完成編譯但尚未被鏈接的機器代碼，一般由編譯器生成庫文件lib, a, dll, so由庫函數(shù)組成的文件，一般由編譯器生成頭文件h, hppC/C+語言程序的頭文件，包含宏，常數(shù)和函數(shù)的定義文本文件txt,包含用戶寫的文字的文件，由編輯器生成圖像文件gif, jpg, bmp, png包含圖像的文件，擴展名代表不同的圖像編碼方式影片文件mpg, avi可連續(xù)播放的影片文件，擴展名代表編碼格式流媒體文件rm, asf, wmf通過網(wǎng)絡播放的影片文件，不需要完整下載整個影片文件壓縮文件zip, rar, gz, Z由多個文件或目

7、錄經(jīng)壓縮而成，擴展名代表不同的壓縮算法音頻文件wav, mp3, mid, wma, aac包含音樂數(shù)據(jù)的文件，擴展名代表不同的聲音壓縮格式網(wǎng)頁文件html, htm, xml包含網(wǎng)頁內容和格式的文件文件分類按文件性質與用途分類按文件性質與用途分類按操作保護分類按操作保護分類按使用情況分類按使用情況分類按用戶觀點分類按用戶觀點分類(UNIX(UNIX或或LinuxLinux操作系統(tǒng)操作系統(tǒng)) )按存取的物理結構分類按存取的物理結構分類按文件中的數(shù)據(jù)形式分類按文件中的數(shù)據(jù)形式分類1) 按性質和用途分類 系統(tǒng)文件系統(tǒng)文件由由系統(tǒng)軟件系統(tǒng)軟件構成的文件，只允許用戶通過系統(tǒng)構成的文件，只允許用戶通過系

8、統(tǒng)調用或系統(tǒng)提供的專用命今來執(zhí)行它們，不允調用或系統(tǒng)提供的專用命今來執(zhí)行它們，不允許對其進行讀寫和修改許對其進行讀寫和修改主要有操作系統(tǒng)核心和各種系統(tǒng)應用程序或實主要有操作系統(tǒng)核心和各種系統(tǒng)應用程序或實用工具程序和數(shù)據(jù)組成用工具程序和數(shù)據(jù)組成例如：例如：,/,/unix 1) 按性質和用途分類庫文件庫文件文件文件允許允許用戶對其進行讀取和執(zhí)行，但用戶對其進行讀取和執(zhí)行，但不允許不允許對其進行修改對其進行修改主要由各種標準子程序庫組成主要由各種標準子程序庫組成例如：例如：C C語言、語言、FORTRANFORTRAN子程序庫存放在子目錄子程序庫存放在子目錄下下 * *.LIB,/lib/,/us

9、r/lib/.LIB,/lib/,/usr/lib/ 1) 按性質和用途分類用戶文件用戶文件是用戶通過是用戶通過操作系統(tǒng)保存操作系統(tǒng)保存的用戶文件，由文件的用戶文件，由文件的所有者或所有者授權的用戶才能使用的所有者或所有者授權的用戶才能使用主要由用戶的源程序源代碼、可執(zhí)行目標程序主要由用戶的源程序源代碼、可執(zhí)行目標程序的文件和用戶數(shù)據(jù)庫數(shù)據(jù)等組成的文件和用戶數(shù)據(jù)庫數(shù)據(jù)等組成例如：例如：* *.c,.c,* *.for,.for,* *.f,.f,* *DBF,DBF,* *.OBJ.OBJ2) 按操作保護分類只讀文件只讀文件只允許文件主及被核準的用戶去讀文件，而不允只允許文件主及被核準的用戶去

10、讀文件，而不允許寫文件。標記為：許寫文件。標記為：-r-r-可讀可寫文件可讀可寫文件允許文件主及被核準的用戶去讀和寫文件。標記允許文件主及被核準的用戶去讀和寫文件。標記為：為： -rw-rw-可執(zhí)行文件可執(zhí)行文件允許文件主及被核準的用戶去調用執(zhí)行該文件而允許文件主及被核準的用戶去調用執(zhí)行該文件而不允許讀和寫文件，標記為：不允許讀和寫文件，標記為： -x-x-2) 按操作保護分類 各個操作系統(tǒng)的各個操作系統(tǒng)的保護方法和級別保護方法和級別有所不同有所不同DOSDOS操作系統(tǒng)三種保護：系統(tǒng)、隱藏、可寫操作系統(tǒng)三種保護：系統(tǒng)、隱藏、可寫UNIXUNIX或或LinuxLinux操作系統(tǒng)有九個級別的保護操

11、作系統(tǒng)有九個級別的保護3) 按使用情況分類臨時文件臨時文件用于系統(tǒng)在工作過程中產生的中間文件，一般有暫用于系統(tǒng)在工作過程中產生的中間文件，一般有暫存的目錄，正常工作情況下，工作完畢會自動刪除，存的目錄，正常工作情況下，工作完畢會自動刪除，一旦有異常情況往往會殘留不少臨時文件一旦有異常情況往往會殘留不少臨時文件永久文件永久文件指一般受系統(tǒng)管理的各種系統(tǒng)和用戶文件，經(jīng)過安指一般受系統(tǒng)管理的各種系統(tǒng)和用戶文件，經(jīng)過安裝或編輯、編譯生成的文件，存放在軟盤、硬盤或裝或編輯、編譯生成的文件，存放在軟盤、硬盤或光盤等外存上光盤等外存上檔案文件檔案文件系統(tǒng)或一些實用工具軟件包在工作過程中記錄在案系統(tǒng)或一些實用

12、工具軟件包在工作過程中記錄在案的文擋資料文件，以便查閱歷史擋案的文擋資料文件，以便查閱歷史擋案4) 按用戶觀點分類普通文件普通文件( (常規(guī)文件常規(guī)文件) ) 是指系統(tǒng)中最一般組織格式的文件，一般是字符是指系統(tǒng)中最一般組織格式的文件，一般是字符流組成的無結構文件流組成的無結構文件目錄文件目錄文件是由文件的目錄信息構成的特殊文件，操作系統(tǒng)是由文件的目錄信息構成的特殊文件，操作系統(tǒng)將目錄也做成文件，便于統(tǒng)一管理將目錄也做成文件，便于統(tǒng)一管理4) 按用戶觀點分類特殊文件（設備文件）特殊文件（設備文件）在在UNIXUNIX或或LinuxLinux操作系統(tǒng)中，所有的輸入輸出外操作系統(tǒng)中，所有的輸入輸出外

13、部設備都被看作特殊文件便于統(tǒng)一管理部設備都被看作特殊文件便于統(tǒng)一管理操作系統(tǒng)會把對特殊文件的操作轉接指向相應操作系統(tǒng)會把對特殊文件的操作轉接指向相應的設備操作，真正的設備驅動程序不包含在這的設備操作，真正的設備驅動程序不包含在這特殊文件中，而是指向與鏈接到操作系統(tǒng)核心特殊文件中，而是指向與鏈接到操作系統(tǒng)核心中存放在內存高端部分中存放在內存高端部分5) 按存取的物理結構分類順序（連續(xù)）文件順序（連續(xù)）文件文件中的紀錄，文件中的紀錄，順序地存儲到連續(xù)的物理盤塊中順序地存儲到連續(xù)的物理盤塊中，順序文件中所記錄的次序，與它們存儲在物理介順序文件中所記錄的次序，與它們存儲在物理介質上存放的次序是一致的質

14、上存放的次序是一致的鏈接文件鏈接文件文件中的記錄可存儲在并不相鄰接的各個物理塊文件中的記錄可存儲在并不相鄰接的各個物理塊中，通過物理塊中的中，通過物理塊中的鏈接指針鏈接指針組成一個鏈表管理，組成一個鏈表管理，形成一個完整的文件形成一個完整的文件, ,又稱指針串連文件或直接存又稱指針串連文件或直接存取文件取文件5) 按存取的物理結構分類索引文件索引文件文件中的記錄可存儲在并不相鄰接的各個物理文件中的記錄可存儲在并不相鄰接的各個物理塊中，記錄和物理塊之間通過索引表項塊中，記錄和物理塊之間通過索引表項按關鍵按關鍵字存取字存取文件，通過物理塊中的文件，通過物理塊中的索引表索引表管理，形管理，形成一個完

15、整的文件。成一個完整的文件。6) 按文件的邏輯存儲結構分類有結構文件有結構文件由若干個記錄所構成的文件，故又稱為記由若干個記錄所構成的文件，故又稱為記錄式文件錄式文件無結構文件無結構文件這是直接由字符序列所構成的文件，故又這是直接由字符序列所構成的文件，故又禰為流式文件禰為流式文件7) 按文件中的數(shù)據(jù)形式分類源文件源文件由源程序和數(shù)據(jù)構成的文件由源程序和數(shù)據(jù)構成的文件一般是由美國信息交換標準碼（一般是由美國信息交換標準碼（ASCIIASCII）、）、EBCDEBCD碼或漢字編碼組成碼或漢字編碼組成目標文件目標文件由源程序經(jīng)過相應的計算機語言編譯程序由源程序經(jīng)過相應的計算機語言編譯程序編譯，但尚

16、未經(jīng)過鏈接程序鏈接的目標代編譯，但尚未經(jīng)過鏈接程序鏈接的目標代碼所形成的文件碼所形成的文件后綴名為后綴名為“.OBJ.OBJ”（DOSDOS系統(tǒng)）或系統(tǒng)）或“.o.o”（UNIXUNIX或或LinuxLinux操作系統(tǒng)）操作系統(tǒng)）5.3 5.3 文件的訪問文件的訪問l 順序訪問順序訪問l 隨機訪問隨機訪問l 索引訪問索引訪問文件的邏輯結構1.順序文件順序文件l定長記錄：定長記錄： 讀指針讀指針rptrrptr指向下一次讀出的記錄地址；指向下一次讀出的記錄地址； 寫指針寫指針wptrwptr指向下一次寫入的記錄地址。指向下一次寫入的記錄地址。 讀完指針做相應修改讀完指針做相應修改:rptr+m=

17、rptr:rptr+m=rptr 寫完指針做相應修改寫完指針做相應修改:wptr+m=wptr:wptr+m=wptrl變長記錄：變長記錄： 每個記錄長度存于記錄前的單元中。每個記錄長度存于記錄前的單元中。 讀完讀完rptr+mi+1=rptrrptr+mi+1=rptr2. 2. 對順序文件的讀對順序文件的讀/ /寫操作寫操作 定長和變長記錄文件 3. 3. 順序文件的優(yōu)缺點順序文件的優(yōu)缺點 l 順序文件的最佳應用是對記錄進行批量存取時，順序文件的最佳應用是對記錄進行批量存取時， 即每次要讀或寫一大批記錄時，對順序文件的存取即每次要讀或寫一大批記錄時，對順序文件的存取效率是所有邏輯文件中最高

18、的；此外，也只有順序效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上，并能有效地工作。文件才能存儲在磁帶上，并能有效地工作。l 在交互應用的場合，如果用戶要求查找或修改單在交互應用的場合，如果用戶要求查找或修改單個記錄，系統(tǒng)要逐個地查找諸記錄。這時，順序文個記錄，系統(tǒng)要逐個地查找諸記錄。這時，順序文件所表現(xiàn)出來的性能就可能很差，尤其是當文件較件所表現(xiàn)出來的性能就可能很差，尤其是當文件較大時，情況更為嚴重。大時，情況更為嚴重。l 增加或刪除一個記錄較困難。增加或刪除一個記錄較困難。索引文件索引文件 對于定長記錄文件，如果要查找第對于定長記錄文件，如果要查找第i i個記錄，個記錄，

19、可直接根據(jù)下式計算來獲得第可直接根據(jù)下式計算來獲得第i i個記錄相對于第一個記錄相對于第一個記錄首址的地址：個記錄首址的地址： A Ai i=i=iL L 對于可變長度記錄的文件，要查找其第對于可變長度記錄的文件，要查找其第i i個記個記錄時，須首先計算出該記錄的首地址。為此，須錄時，須首先計算出該記錄的首地址。為此，須順序地查找每個記錄，從中獲得相應記錄的長度順序地查找每個記錄，從中獲得相應記錄的長度L Li i，然后才能按下式計算出第，然后才能按下式計算出第i i個記錄的首址。假個記錄的首址。假定在每個記錄前用一個字節(jié)指明該記錄的長度，定在每個記錄前用一個字節(jié)指明該記錄的長度，則則 索引文

20、件的組織索引文件的組織 索引文件索引文件 索引順序文件索引順序文件 索引順序文件索引順序文件 直接文件和哈希文件直接文件和哈希文件 1. 直接文件直接文件 對于直接文件，則可根據(jù)給定的記錄鍵對于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉換被稱為種由記錄鍵值到記錄物理地址的轉換被稱為鍵值轉換。組織直接文件的關鍵，鍵值轉換。組織直接文件的關鍵， 在于用什在于用什么方法進行從記錄值到物理地址的轉換。么方法進行從記錄值到物理地址的

21、轉換。 2. 2. 哈希哈希(Hash)(Hash)文件文件 Hash文件的邏輯結構直接文件和哈希文件直接文件和哈希文件 5.45.4文件保護文件保護1.訪問類型訪問類型l讀文件讀文件l寫文件寫文件l執(zhí)行文件執(zhí)行文件l追加文件追加文件l列表文件列表文件l刪除文件刪除文件5.45.4文件保護文件保護2.2.訪問控制（控制訪問類型，控制用戶）訪問控制（控制訪問類型，控制用戶）l基于用戶和組的訪問控制基于用戶和組的訪問控制l訪問控制列表（訪問控制列表（Access Control List，ACL） ACL所采用的方法是給系統(tǒng)中的每一個文件附加一所采用的方法是給系統(tǒng)中的每一個文件附加一個訪問控制列表

22、信息，這個表中包含了哪些用戶對這個個訪問控制列表信息，這個表中包含了哪些用戶對這個文件有哪種類型的訪問。這樣系統(tǒng)打開這個文件之前，文件有哪種類型的訪問。這樣系統(tǒng)打開這個文件之前，都要搜索訪問控制列表來判斷當前用戶是否允許執(zhí)行相都要搜索訪問控制列表來判斷當前用戶是否允許執(zhí)行相應的操作。應的操作。文件名文件名文件擁有者文件擁有者 所屬組所屬組其他用戶其他用戶example.cRWRWRl文件目錄：是文件系統(tǒng)中主要數(shù)據(jù)結構之文件目錄：是文件系統(tǒng)中主要數(shù)據(jù)結構之一一, ,通常通過文件目錄實現(xiàn)文件的組織通常通過文件目錄實現(xiàn)文件的組織。l對目錄管理的要求如下：對目錄管理的要求如下： (1) 實現(xiàn)實現(xiàn)“按名

23、存取按名存取” (2) 提高對目錄的檢索速度提高對目錄的檢索速度 (3) 文件共享文件共享 (4) 允許文件重名允許文件重名5.55.5文件目錄文件目錄文件控制塊文件控制塊(FCB)(FCB)l文件控制塊文件控制塊是操作系統(tǒng)為管理文件而是操作系統(tǒng)為管理文件而設置的數(shù)據(jù)結構，存放了為管理文件設置的數(shù)據(jù)結構，存放了為管理文件所需的所有相關信息。所需的所有相關信息。l文件控制塊文件控制塊是文件存在的標志是文件存在的標志文件控制塊文件控制塊的內容的內容(1)基本信息類基本信息類 文件名文件名 ； 文件物理位置文件物理位置 ； 文件邏輯結構文件邏輯結構 ； 文件的物理結構文件的物理結構 (2) 存取控制

24、信息類存取控制信息類 (3) 使用信息類使用信息類 MS-DOS的文件控制塊 文件名擴展名屬性備用時間日期第一塊號盤塊數(shù) 2. 文件控制塊包括的內容 文件名文件名文件設備文件設備指向下一個指向下一個PCBPCB的指針的指針文件標識符文件標識符 物理位置物理位置 當前共享的狀態(tài)當前共享的狀態(tài)文件結構文件結構 存取控制存取控制共享訪問時等待狀態(tài)共享訪問時等待狀態(tài)文件類型文件類型口令口令進程訪問文件所用的邏輯單元號進程訪問文件所用的邏輯單元號記錄長度記錄長度文件建立時間文件建立時間當前的邏輯位置當前的邏輯位置 當前文件大小當前文件大小上次存取時間上次存取時間訪問元素的當前物理位置訪問元素的當前物理位

25、置緩沖區(qū)大小緩沖區(qū)大小 緩沖區(qū)地址緩沖區(qū)地址 文件創(chuàng)建者文件創(chuàng)建者當前存取方式當前存取方式 文件擁有者文件擁有者 臨時臨時 永久文件永久文件 最大文件尺寸最大文件尺寸 上次修改時間上次修改時間 下一個元素的物理位置下一個元素的物理位置l把所有的把所有的FCBFCB組織在一起，就構成了組織在一起，就構成了文件目文件目錄錄，即文件控制塊的有序集合，即文件控制塊的有序集合l目錄項：構成文件目錄的項目（目錄項：構成文件目錄的項目（目錄項就目錄項就是是FCBFCB）l目錄文件：為了實現(xiàn)對文件目錄的管理，目錄文件：為了實現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，通常將文件目錄以文件的形式保

26、存在外存，這個文件就叫目錄文件這個文件就叫目錄文件文件目錄文件目錄索引結點索引結點1.索引結點的引入索引結點的引入 文件目錄放在外存上，當檢索一個文件時需要啟動磁盤，文件目錄放在外存上，當檢索一個文件時需要啟動磁盤，將不同磁盤塊中的目錄項逐一調入內存。設目錄文件占將不同磁盤塊中的目錄項逐一調入內存。設目錄文件占用用N塊盤塊，則查找目錄項平均調入盤塊（塊盤塊，則查找目錄項平均調入盤塊（N+1）/2。 改進：在查找目錄時，目錄項中只有文件名是必要的。改進：在查找目錄時，目錄項中只有文件名是必要的。所以可以采取文件名和其他文件描述信息分開存儲的辦所以可以采取文件名和其他文件描述信息分開存儲的辦法。法

27、。文件描述信息單獨形成一個稱為索引結點的數(shù)據(jù)結文件描述信息單獨形成一個稱為索引結點的數(shù)據(jù)結構，簡稱構，簡稱i結點。結點。目錄項的內容變成文件名和指向該文件目錄項的內容變成文件名和指向該文件所對應的所對應的i結點的指針所構成。因此目錄文件的存儲盤塊結點的指針所構成。因此目錄文件的存儲盤塊數(shù)大大降低。數(shù)大大降低。文件名擴展名屬性備用時間日期第一塊號盤塊數(shù)文件控制塊文件名I指針擴展名屬性備用時間日期第一塊號盤塊數(shù)索引結點索引結點結點文件名索引結點編號文件名1文件名2UNIX的文件目錄 索引結點結點2. 2. 磁盤索引結點磁盤索引結點 (1)文件主標識符文件主標識符(2) 文件類型文件類型 (3) 文

28、件存取權限文件存取權限 (4) 文件物理地址文件物理地址 (5) 文件長度文件長度 (6) 文件連接計數(shù)文件連接計數(shù) (7) 文件存取時間文件存取時間 (1) 索引結點編號。索引結點編號。 用于標識內存索引結點。用于標識內存索引結點。(2) 狀態(tài)。狀態(tài)。 指示指示i結點是否上鎖或被修改。結點是否上鎖或被修改。(3) 訪問計數(shù)。訪問計數(shù)。 每當有一進程要訪問此每當有一進程要訪問此i結點時，結點時， 將該訪問計數(shù)加將該訪問計數(shù)加1， 訪問完再減訪問完再減1。(4) 文件所屬文件系統(tǒng)的邏輯設備號。文件所屬文件系統(tǒng)的邏輯設備號。(5) 鏈接指針。鏈接指針。 設置有分別指向空閑鏈表和散列隊設置有分別指向

29、空閑鏈表和散列隊列的指針。列的指針。 3. 3. 內存索引結點內存索引結點文件被打開時，將磁盤索引結點拷貝到內存文件被打開時，將磁盤索引結點拷貝到內存的索引結點中，內存索引結點增加了以下內的索引結點中，內存索引結點增加了以下內容容:文件名物理地址文件說明狀態(tài)位文件名1文件名21. 1. 單級目錄結構單級目錄結構 為所有文件建立一個目錄文件。單級目錄的優(yōu)為所有文件建立一個目錄文件。單級目錄的優(yōu)點是簡單且能實現(xiàn)目錄管理的基本功能點是簡單且能實現(xiàn)目錄管理的基本功能按名存取。按名存取。 缺點：缺點：(1) (1) 查找速度慢查找速度慢 ; (2) ; (2) 不允許重名不允許重名 (3) (3) 不便

30、于實現(xiàn)文件共享不便于實現(xiàn)文件共享 l為改變一級目錄文件目錄命名沖突，并提高對目為改變一級目錄文件目錄命名沖突，并提高對目錄文件檢索速度而將目錄分為兩級：一級稱為主錄文件檢索速度而將目錄分為兩級：一級稱為主文件目錄，給出用戶名，用戶子目錄所在的物理文件目錄，給出用戶名，用戶子目錄所在的物理位置；二級稱為用戶文件目錄，給出該用戶所有位置；二級稱為用戶文件目錄，給出該用戶所有文件的文件的FCBFCBl產生于多用戶分時系統(tǒng)，產生于多用戶分時系統(tǒng)，DOS2.0DOS2.0版本以上采用，版本以上采用，文件主目錄（文件主目錄（MFDMFD）的表目按用戶分，每個用戶）的表目按用戶分，每個用戶有一個用戶文件目錄

31、（有一個用戶文件目錄（UFDUFD）l優(yōu)點：解決了文件的重名問題和文件共享問題，優(yōu)點：解決了文件的重名問題和文件共享問題，提高搜索速度，提高搜索速度，查找時間降低查找時間降低l缺點：缺點：缺點是不太適合大量用戶和大量文件的大缺點是不太適合大量用戶和大量文件的大系統(tǒng)，系統(tǒng)，增加了系統(tǒng)開銷，增加了系統(tǒng)開銷，2. 2. 二級目錄結構二級目錄結構 兩級目錄結構兩級目錄結構 l多級目錄結構也稱樹型目錄多級目錄結構也稱樹型目錄l產生于產生于UNIXUNIX操作系統(tǒng)，巳被現(xiàn)代操作系統(tǒng)廣泛操作系統(tǒng)，巳被現(xiàn)代操作系統(tǒng)廣泛采用。目錄與文件在一起，目錄也做成文件采用。目錄與文件在一起，目錄也做成文件l優(yōu)點：優(yōu)點：

32、層次結構清晰，便于管理和保護；有利于文件層次結構清晰，便于管理和保護；有利于文件分類；解決重名問題；提高文件檢索速度；能分類；解決重名問題；提高文件檢索速度；能進行存取權限的控制進行存取權限的控制 l缺點：缺點： 查找一個文件按路徑名逐層檢查，由于每個文查找一個文件按路徑名逐層檢查，由于每個文件都放在外存，多次訪問磁盤，影響速度件都放在外存，多次訪問磁盤，影響速度 3. 3. 多級目錄結構多級目錄結構1) 1) 多級目錄結構多級目錄結構 多級目錄結構 在樹形目錄結構中，從根目錄到任何數(shù)據(jù)文在樹形目錄結構中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通路。在該路徑上從樹的件，都只有一條惟一的通路。

33、在該路徑上從樹的根根( (即主目錄即主目錄) )開始，把全部目錄文件名與數(shù)據(jù)文開始，把全部目錄文件名與數(shù)據(jù)文件名，依次地用件名，依次地用“/ /”連接起來，即構成該數(shù)據(jù)文連接起來，即構成該數(shù)據(jù)文件的路徑名。系統(tǒng)中的每一個文件都有惟一的路件的路徑名。系統(tǒng)中的每一個文件都有惟一的路徑名。例如，在上圖中用戶徑名。例如，在上圖中用戶B B為訪問文件為訪問文件N N，應使，應使用其路徑名用其路徑名/B/F/N/B/F/N來訪問。來訪問。 2) 2) 路徑名路徑名3) 3) 當前目錄當前目錄為了提高文件檢索速度，文件系統(tǒng)向用為了提高文件檢索速度，文件系統(tǒng)向用戶提供了一個當前正在使用的目錄，稱戶提供了一個當

34、前正在使用的目錄，稱為當前目錄（也稱工作目錄或值班目為當前目錄（也稱工作目錄或值班目錄）。查找一個文件可從當前目錄開始，錄）。查找一個文件可從當前目錄開始，使用部分路徑名使用部分路徑名當前目錄可根據(jù)需要任意改變。當前目錄可根據(jù)需要任意改變。當前目錄一般存放在內存當前目錄一般存放在內存5.65.6文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)5.6.1 文件系統(tǒng)的結構文件系統(tǒng)的結構應用軟件應用軟件基本文件系統(tǒng)基本文件系統(tǒng)邏輯文件系統(tǒng)邏輯文件系統(tǒng)文件組織模塊文件組織模塊I/O控制控制磁盤設備磁盤設備5.65.6文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)l應用軟件：應用軟件：當應用軟件需要對某個文件進行操作時，當應用軟件需要對某個

35、文件進行操作時，它通過操作系統(tǒng)的系統(tǒng)調用將文件的路徑信息傳遞它通過操作系統(tǒng)的系統(tǒng)調用將文件的路徑信息傳遞進來；進來；l邏輯文件系統(tǒng)：邏輯文件系統(tǒng)：邏輯文件系統(tǒng)根據(jù)所提供的路徑找邏輯文件系統(tǒng)根據(jù)所提供的路徑找到指定的文件，進行權限的檢查。如果這是一個合到指定的文件，進行權限的檢查。如果這是一個合法的請求，它提取文件的邏輯位置信息；法的請求，它提取文件的邏輯位置信息；5.65.6文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)l文件組織模塊：文件組織模塊：將邏輯位置信息轉換成磁盤上屬于將邏輯位置信息轉換成磁盤上屬于該文件的磁盤塊的位置；該文件的磁盤塊的位置；l基本文件系統(tǒng)：基本文件系統(tǒng)：它負責把磁盤塊的位置信息通過指

36、它負責把磁盤塊的位置信息通過指令發(fā)送給令發(fā)送給I/O系統(tǒng)，請求磁盤操作；系統(tǒng)，請求磁盤操作；lI/O控制：控制：磁盤控制器接收到命令后，發(fā)送一系列磁盤控制器接收到命令后，發(fā)送一系列命令給磁盤設備并等待磁盤操作結束，然后發(fā)出中命令給磁盤設備并等待磁盤操作結束，然后發(fā)出中斷命令等操作；斷命令等操作；5.65.6文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)5.6.3 目錄實現(xiàn)目錄實現(xiàn) 我們可以把目錄看成是一張表，其中的每一我們可以把目錄看成是一張表，其中的每一行記錄了這個目錄下的某個文件或子目錄的名稱、行記錄了這個目錄下的某個文件或子目錄的名稱、邏輯位置等信息。因此，邏輯位置等信息。因此，一個基本的實現(xiàn)問題就是，一

37、個基本的實現(xiàn)問題就是，如何組織這張表才能獲得最好效率和性能呢？如何組織這張表才能獲得最好效率和性能呢？目前，目前，最常用的兩種方式是線性表（最常用的兩種方式是線性表（Linear List）和哈希）和哈希表（表（Hash table）。）。5.65.6文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)l線性表線性表 線性表是最簡單的數(shù)據(jù)結構了。目錄中的文線性表是最簡單的數(shù)據(jù)結構了。目錄中的文件和子目錄信息依次順序存儲在這個特殊的件和子目錄信息依次順序存儲在這個特殊的“文件文件”中就形成了這種結構。中就形成了這種結構。 l哈希表哈希表 為了更快地訪問目錄中的文件，我們可以將目為了更快地訪問目錄中的文件，我們可以將目錄

38、表項組織成哈希結構，采用文件名作為哈希函數(shù)錄表項組織成哈希結構，采用文件名作為哈希函數(shù)的輸入值。的輸入值。 5.65.6文件系統(tǒng)的實現(xiàn)文件系統(tǒng)的實現(xiàn)5.6.4 文件的實現(xiàn)文件的實現(xiàn) 一個文件除了數(shù)據(jù)本身外，還有很多的屬性信一個文件除了數(shù)據(jù)本身外，還有很多的屬性信息。為了方便描述和實現(xiàn)，一般稱文件的所有屬性息。為了方便描述和實現(xiàn)，一般稱文件的所有屬性信息為文件控制塊（信息為文件控制塊（File Control Block， FCB）。）。 文件保護信息文件保護信息文件時間信息文件時間信息文件擁有者，所屬組，文件擁有者，所屬組，ACL文件保存位置文件保存位置文件控制塊文件控制塊5.6.5 5.6.

39、5 文件分配方法文件分配方法1. 連續(xù)分配連續(xù)分配為每個文件分配一組相鄰接的盤塊。一組盤塊的地為每個文件分配一組相鄰接的盤塊。一組盤塊的地址定義了磁盤上的一段線性地址。址定義了磁盤上的一段線性地址。對于這種方式，文件的邏輯組織與物理組織一致。對于這種方式，文件的邏輯組織與物理組織一致。為使系統(tǒng)能找到文件存放的地址，應在目錄項的為使系統(tǒng)能找到文件存放的地址，應在目錄項的“文件物理地址文件物理地址”字段存放該文件的第一個記錄所字段存放該文件的第一個記錄所在的盤塊號和文件長度（盤塊數(shù)）如圖：在的盤塊號和文件長度（盤塊數(shù)）如圖：1. 1. 連續(xù)分配連續(xù)分配l有碎片問題有碎片問題l優(yōu)缺點：優(yōu)缺點：順序訪

40、問容易順序訪問容易順序訪問速度快順序訪問速度快碎片碎片必須知道文件長度必須知道文件長度01234567891011文件文件 起始位置起始位置 大小大小foo 0 2bar 6 32.2.鏈接分配鏈接分配l一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊通過指針連接，前一個物理塊指向下一個物理塊l優(yōu)點：提高了磁盤空間利用率優(yōu)點：提高了磁盤空間利用率 不存在外部碎片問題不存在外部碎片問題 有利于文件插入和刪除有利于文件插入和刪除 有利于文件動態(tài)擴充有利于文件動態(tài)擴充l缺點：存取速度慢，不適于隨機存取缺點：

41、存取速度慢，不適于隨機存取 可靠性問題，如指針出錯可靠性問題，如指針出錯 更多的尋道次數(shù)和尋道時間更多的尋道次數(shù)和尋道時間 鏈接指針占用一定的空間鏈接指針占用一定的空間l分為隱式連接和顯式連接分為隱式連接和顯式連接2.2.鏈接分配鏈接分配文件名文件名 始址始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617181920212223242526272829303111016-125磁盤空間的隱式鏈接分配1） 隱式鏈接隱式鏈接l在文件目錄的每個目錄項中須含有指向鏈接文件第一個盤在文件目錄的每個目錄項中須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。

42、每個盤塊含有指向下一個盤塊塊和最后一個盤塊的指針。每個盤塊含有指向下一個盤塊的指針的指針l問題問題: :只適合順序訪問，因為在盤塊中含下一個盤塊的指只適合順序訪問，因為在盤塊中含下一個盤塊的指針，所以必須啟動磁盤。如果隨機讀取第針，所以必須啟動磁盤。如果隨機讀取第100100塊，則要啟塊，則要啟動磁盤動磁盤100100次。速度很低。改進的方法是次。速度很低。改進的方法是“簇簇”，但改進，但改進有限，且增大碎片有限，且增大碎片2.2.鏈接分配鏈接分配2.2.鏈接分配鏈接分配 顯式鏈接結構 2 2）顯式鏈接）顯式鏈接l計算：計算：1.2M軟盤，塊把用于鏈接文件各物理塊的指針，軟盤，塊把用于鏈接文件

43、各物理塊的指針，顯式地存放在內存的一張鏈接表中，在整個磁盤僅設置一顯式地存放在內存的一張鏈接表中，在整個磁盤僅設置一張。表的序號是物理盤塊號，從張。表的序號是物理盤塊號，從0開始到開始到N-1.每個表項存每個表項存放鏈接指針。文件的首個盤塊號存放在相應文件的放鏈接指針。文件的首個盤塊號存放在相應文件的FCB中。中。l由于在內存中檢索，所以顯著提高檢索速度。由于在內存中檢索，所以顯著提高檢索速度。FATl問題：可能占用較大內存問題：可能占用較大內存l200M硬盤，塊硬盤，塊1K，F(xiàn)AT有多大？有多大？l1.2M軟盤，塊軟盤，塊1K，F(xiàn)AT有多大？有多大？2.2.鏈接分配鏈接分配3.3.索引分配索

44、引分配1 ）單級索引分配單級索引分配l鏈接帶來的問題鏈接帶來的問題不能高效直接存取，對較大文件必須首先在不能高效直接存取，對較大文件必須首先在FAT中查找許多盤塊號中查找許多盤塊號FAT占用較大內存占用較大內存l解決：不將整個解決：不將整個FAT調入內存，將每個文件調入內存，將每個文件對應的盤塊號，存入文件的索引塊對應的盤塊號，存入文件的索引塊 ，該索，該索引塊就是一個含有許多盤塊號的數(shù)組。引塊就是一個含有許多盤塊號的數(shù)組。l問題：花費較多外存，小文件索引塊利用問題：花費較多外存，小文件索引塊利用率極低。率極低。01234567891011121314151617181920212223242

45、5262728293031文件名文件名 索引表地址索引表地址文件目錄文件目錄Jeep 19 916 11025 -1 -1 -1192 2）多級索引分配）多級索引分配l如果文件比較大，一個索引塊不足以存儲所有如果文件比較大，一個索引塊不足以存儲所有盤塊號，則需要多個索引塊，如果為這些索引盤塊號，則需要多個索引塊，如果為這些索引塊建立索引，變形成了兩級索引分配方式。類塊建立索引，變形成了兩級索引分配方式。類似的，更大的文件可以使用三級、四級索引方似的，更大的文件可以使用三級、四級索引方式式3.3.索引分配索引分配3.索引分配索引分配3 3 ）unixunix的混合索引分配方式的混合索引分配方式直

46、接地址、一級索引、兩級索引、直接地址、一級索引、兩級索引、三級索引的結合。三級索引的結合。3.3.索引分配索引分配2010年研究生入學試題年研究生入學試題l設文件索引結點中有7個地址項，其中4個地址項是直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)。若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，這可表示的單個文件最大長度是 A.33KB B.519KB C.1057KB D.16513KB5.7 5.7 空閑空間管理空閑空間管理5.7.1 位示圖位示圖l對于像硬盤這種把存儲空間分成一個個存對于像硬盤這種把存儲空間分成一個個存儲塊的設備而言，我們可

47、以為每一個存儲儲塊的設備而言，我們可以為每一個存儲塊用一個位來記錄它目前是否空閑。把所塊用一個位來記錄它目前是否空閑。把所有的這些標志位組織在一起就形成了所謂有的這些標志位組織在一起就形成了所謂的位示圖。的位示圖。 位示圖法位示圖法l建立一張位示圖，以反映整個存貯空建立一張位示圖，以反映整個存貯空間的分配情況，每一個字的每一位都對應間的分配情況，每一個字的每一位都對應一個物理塊。一個物理塊。0：未分配：未分配(空白塊空白塊)1：已分配：已分配位字0 1 2 3 14 150121 1 0 0 0 00 1 0 0 1 0位示圖法位示圖法為了找到為了找到N個自由塊，就需要搜索位示圖，個自由塊，就

48、需要搜索位示圖，找到找到N個個“ 0”位，再經(jīng)過一個簡單的換算就可位，再經(jīng)過一個簡單的換算就可得得知知相應的塊地址相應的塊地址(物理地址物理地址)，存貯空間的分配，存貯空間的分配和回收工作較為方便，和回收工作較為方便，0,1轉換。轉換。位示圖法位示圖法位示圖法位示圖法l盤塊的分配盤塊的分配（1）順序掃描找到一個或一組值為）順序掃描找到一個或一組值為“0”的二進制位的二進制位（2）轉換成相應盤塊號）轉換成相應盤塊號uB=ni+j（3）修改位示圖）修改位示圖mapI,j=1位示圖法位示圖法l盤塊的回收盤塊的回收（1）將回收盤塊的盤塊號轉換為位示圖）將回收盤塊的盤塊號轉換為位示圖的行號和列號的行號和

49、列號u i=bDIV nuJ=b MOD n（2）修改位示圖令）修改位示圖令mapI,j=05.7 5.7 空閑空間管理空閑空間管理5.7.2 鏈表鏈表l這種方法是將所有的空閑存儲空間通過鏈這種方法是將所有的空閑存儲空間通過鏈表串起來，組成空閑空間鏈表。鏈表的表表串起來，組成空閑空間鏈表。鏈表的表頭指針保存在文件系統(tǒng)中預先設定的某個頭指針保存在文件系統(tǒng)中預先設定的某個位置，并用一個特殊的指針值來作為鏈表位置，并用一個特殊的指針值來作為鏈表的結束標志。的結束標志。 鏈鏈 表表（1）空閑盤塊鏈）空閑盤塊鏈u將磁盤上的所有空閑空間，以盤塊為單位拉將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。當創(chuàng)造

50、文件需要一塊或幾塊時，成一條鏈。當創(chuàng)造文件需要一塊或幾塊時，就從鏈頭依次取下一塊或幾塊。反之，當回就從鏈頭依次取下一塊或幾塊。反之，當回收空間時，把這些空白塊依次鏈到鏈尾上。收空間時，把這些空白塊依次鏈到鏈尾上。這種技術只要在主存中保存一個指針，令它這種技術只要在主存中保存一個指針，令它指向第一個空白塊。指向第一個空白塊。（2）空閑盤區(qū)鏈）空閑盤區(qū)鏈u將磁盤上的所有空閑盤區(qū)拉成一條鏈。每個將磁盤上的所有空閑盤區(qū)拉成一條鏈。每個盤區(qū)上含有本盤區(qū)大小的信息。分配采用首盤區(qū)上含有本盤區(qū)大小的信息。分配采用首次適應算法，回收考慮鄰接空閑區(qū)的合并。次適應算法，回收考慮鄰接空閑區(qū)的合并。5.7 5.7 空

51、閑空間管理空閑空間管理5.7.3 分組計數(shù)分組計數(shù)l分組計數(shù)是對鏈表方法的一種改進。首先，分組計數(shù)是對鏈表方法的一種改進。首先，保存開始的保存開始的n個存儲塊的地址于第一個空閑個存儲塊的地址于第一個空閑塊中，其中前塊中，其中前n-1個的確指向空閑塊，最后個的確指向空閑塊，最后一個指向另一個保存一個指向另一個保存n個空閑塊地址的空閑個空閑塊地址的空閑塊，依次如此。塊，依次如此。 成組鏈接法成組鏈接法1.1.空閑盤塊的組織空閑盤塊的組織(1)空閑盤塊號棧 存放當前可用的一組空閑盤塊的盤塊號（最多100個）。及棧中尚有的空閑盤塊號數(shù)N。N還兼作棧頂指針用。N=100，指向s.free(99)。s.f

52、ree(0)是棧底，棧滿時棧頂為s.free(99)。(2)文件空閑盤塊被分成若干組成組鏈接法成組鏈接法(3)將一組含有盤塊總數(shù)N和該組所有盤塊號，記入前一組的第一個盤塊的s.free(0) s.free(99),這樣各組的第一個盤塊可以鏈成鏈。(4)將第一組的盤塊總數(shù)和所有盤塊號記入空閑盤塊號棧，作為當前克分配的空閑盤塊號。成組鏈接法成組鏈接法成組鏈接法成組鏈接法2 .2 .空閑盤空閑盤塊的分配和回收塊的分配和回收l分配：首先檢查空閑盤塊號棧是否上鎖，如未上鎖從中取出一空閑盤塊號，將對應盤塊分配給用戶，將棧頂下移。若已是棧底，s.free(0)，則把新的盤塊號棧內容讀入，再分配該盤塊。最后把

53、棧中的空閑盤塊數(shù)減1并返回。成組鏈接法成組鏈接法l回收:將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，并執(zhí)行空閑盤塊號數(shù)加1的操作。當棧中空閑盤塊號數(shù)已達100時，將現(xiàn)有棧中的100各盤塊號記入新回收的盤塊中，再將其盤塊號作為新棧底。成組鏈接法成組鏈接法l文件系統(tǒng)采用成組鏈接法描述空閑盤塊，對下圖所示的情況，若分配4個盤塊后又回收了700、750、812、505、522號盤塊，請畫出新的成組鏈接圖。5.85.8性能和可靠性性能和可靠性5.8.1 文件系統(tǒng)的性能l高速緩存l基于軟件的系統(tǒng)緩存模塊 l內存磁盤（RAM disk）5.8.2 文件系統(tǒng)的可靠性l備份 周期性全部備份差異備份5.9 5.9

54、文件系統(tǒng)實例文件系統(tǒng)實例5.9.1 FAT文件系統(tǒng)lFAT是微軟公司最初為它的操作系統(tǒng)DOS開發(fā)的一種文件系統(tǒng)，它有FAT-12，F(xiàn)AT-16和FAT-32三個版本。FAT-12適用于小容量設備，如軟盤；FAT-16對FAT-12做了簡單的擴充，用在Windows的早期版本；而FAT-32是Windows 95 OSR2（OEM Service Release 2）中主要的文件系統(tǒng)，開始支持大容量硬盤。為了保持向后兼容，Windows NT/XP仍然支持FAT文件系統(tǒng)。5.9 5.9 文件系統(tǒng)實例文件系統(tǒng)實例lFAT是File Allocation Table的簡稱，它采用鏈表作為文件分配結構。為了提高性能和可靠性，它把所有的指針收集到一張表中統(tǒng)一保存，稱這張表為文件分配表（FAT）。文件分配表位于分區(qū)的開始，因為它是如此重要的數(shù)據(jù)結構，為了防止文件系統(tǒng)遭到破壞，F(xiàn)AT文件系統(tǒng)保存了兩個文件分配表，它們互為備份。下圖給出了FAT文件系統(tǒng)的總體結構： 引導塊FAT（1）FAT（2）根目錄其他數(shù)據(jù) FAT文件系統(tǒng)結構 5.9 5.9 文件系統(tǒng)實例文件系統(tǒng)實例1引導塊中主要包含用于描述分區(qū)的各種信息，包括邏輯塊的大小、文件分配表的位置等等。2在FAT文件系統(tǒng)的目錄項中，記錄了文件名和屬于該文件的起始邏輯塊編號。 0