1、第七章第七章 文件管理文件管理 在現(xiàn)代計算機系統(tǒng)中在現(xiàn)代計算機系統(tǒng)中, ,要用到大量的程序和數(shù)據(jù)要用到大量的程序和數(shù)據(jù), ,由于內(nèi)存容量有限由于內(nèi)存容量有限, ,又不能長期保存又不能長期保存, ,故平時總是把它故平時總是把它們以文件的形式存放在外存中們以文件的形式存放在外存中, ,需要時可隨時將它們調(diào)需要時可隨時將它們調(diào)入內(nèi)存入內(nèi)存. . 但是這些外存文件由用戶管理不僅非常困難也不但是這些外存文件由用戶管理不僅非常困難也不現(xiàn)實現(xiàn)實. .必須由操作系統(tǒng)管理必須由操作系統(tǒng)管理. .所以在操作系統(tǒng)中增加了所以在操作系統(tǒng)中增加了文件系統(tǒng)文件系統(tǒng). . 信息是計算機系統(tǒng)中的重要資源信息是計算機系統(tǒng)中的重

2、要資源, ,文件系統(tǒng)文件系統(tǒng)是操作系統(tǒng)中的一個重要組成部分是操作系統(tǒng)中的一個重要組成部分. . 是負責信息是負責信息的組織、存儲和訪問。的組織、存儲和訪問。 文件系統(tǒng)的功能就是提供高效、快速和方便文件系統(tǒng)的功能就是提供高效、快速和方便的信息存儲和訪問功能。本章的主要內(nèi)容就是信的信息存儲和訪問功能。本章的主要內(nèi)容就是信息的組織。息的組織。 本章主要內(nèi)容本章主要內(nèi)容: 文件和文件系統(tǒng)文件和文件系統(tǒng) 文件邏輯機構文件邏輯機構 目錄管理目錄管理 文件共享文件共享 文件保護文件保護 7.1.1 文件、記錄和數(shù)據(jù)項文件、記錄和數(shù)據(jù)項 文件管理系統(tǒng)是指文件和對文件進行操文件管理系統(tǒng)是指文件和對文件進行操縱和

3、管理的軟件集合縱和管理的軟件集合. (1)數(shù)據(jù)項數(shù)據(jù)項: 基本數(shù)據(jù)項基本數(shù)據(jù)項:用于描述一個對象的某種屬用于描述一個對象的某種屬性的字符集合性的字符集合. 組合數(shù)據(jù)項組合數(shù)據(jù)項:若干個基本數(shù)據(jù)項組成若干個基本數(shù)據(jù)項組成.(2)記錄記錄: 記錄是一組相關數(shù)據(jù)項的集合。用于描述一個對象某記錄是一組相關數(shù)據(jù)項的集合。用于描述一個對象某方面的屬性方面的屬性.(3)文件文件: 文件是由創(chuàng)建者所定義，具有文件名的一組相關信息文件是由創(chuàng)建者所定義，具有文件名的一組相關信息的集合的集合.可分為有結構文件和無結構文件。可分為有結構文件和無結構文件。 用戶觀點：用戶觀點： 文件系統(tǒng)如何呈現(xiàn)在其面前：一個文件有什么

4、組成，文件系統(tǒng)如何呈現(xiàn)在其面前：一個文件有什么組成，如何命名，如何保護文件，可以進行何種操作等等。如何命名，如何保護文件，可以進行何種操作等等。 操作系統(tǒng)觀點：操作系統(tǒng)觀點： 文件目錄怎樣實現(xiàn)，怎樣管理存儲空間，文件存儲文件目錄怎樣實現(xiàn)，怎樣管理存儲空間，文件存儲位置，磁盤實際運作方式位置，磁盤實際運作方式(與設備管理的接口與設備管理的接口)等等。等等。數(shù)據(jù)項數(shù)據(jù)項n 數(shù)據(jù)項數(shù)據(jù)項2 數(shù)據(jù)項數(shù)據(jù)項1 記錄記錄n 記錄記錄2記錄記錄1文件文件 文件、記錄和數(shù)據(jù)項間的層次關系文件、記錄和數(shù)據(jù)項間的層次關系: 文件的除了有文件名之外，還具有文件屬性文件的除了有文件名之外，還具有文件屬性: 文件類型：

5、從不同角度來規(guī)定文件的類型文件類型：從不同角度來規(guī)定文件的類型; 文件長度：單位可以是字節(jié)、字或塊文件長度：單位可以是字節(jié)、字或塊,也可以是最大允許也可以是最大允許長度；長度； 文件的物理位置：用于指示文件在哪一個設備上及在該文件的物理位置：用于指示文件在哪一個設備上及在該設備的哪個位置設備的哪個位置; 文件的存取控制：文件的讀、寫、執(zhí)行權限文件的存取控制：文件的讀、寫、執(zhí)行權限; 文件的建立時間：創(chuàng)建文件的時間文件的建立時間：創(chuàng)建文件的時間; 文件的修改時間：修改文件的時間。文件的修改時間：修改文件的時間。1 1 文件名和擴展名文件名和擴展名 （1 1）文件名。）文件名。在不同的系統(tǒng)之間，對

6、文件名的規(guī)定是不同的，在在不同的系統(tǒng)之間，對文件名的規(guī)定是不同的，在一些老的系統(tǒng)中，名字的長度還會受到限制。一些老的系統(tǒng)中，名字的長度還會受到限制。 （2 2）擴展名。）擴展名。擴展名是添加在文件名后面的若干個附加字符，又擴展名是添加在文件名后面的若干個附加字符，又稱為后綴名，用于指示文件的類型。稱為后綴名，用于指示文件的類型。2 2 文件類型文件類型（1 1）按用途分類）按用途分類 系統(tǒng)文件：由系統(tǒng)軟件構成的文件系統(tǒng)文件：由系統(tǒng)軟件構成的文件. .有的系統(tǒng)文件只有的系統(tǒng)文件只允許用戶讀允許用戶讀, ,不能修改。有的系統(tǒng)文件不對用戶開放不能修改。有的系統(tǒng)文件不對用戶開放. . 用戶文件：由用戶

7、的源代碼、可執(zhí)行文件或數(shù)據(jù)等用戶文件：由用戶的源代碼、可執(zhí)行文件或數(shù)據(jù)等所構成的文件所構成的文件. .允許用戶調(diào)用允許用戶調(diào)用, ,但不能修改但不能修改. . 庫文件：由標準子程序及常用應用程序組成文件，庫文件：由標準子程序及常用應用程序組成文件，允許用戶使用但不能修改。允許用戶使用但不能修改。（2）按文件中的數(shù)據(jù)形式分類）按文件中的數(shù)據(jù)形式分類源文件：由源程序和數(shù)據(jù)構成的文件。源文件：由源程序和數(shù)據(jù)構成的文件。目標文件：把源程序經(jīng)過相應語言的編譯程序編譯，但目標文件：把源程序經(jīng)過相應語言的編譯程序編譯，但尚未經(jīng)過鏈接程序鏈接的目標代碼所形成的文件。尚未經(jīng)過鏈接程序鏈接的目標代碼所形成的文件。

8、可執(zhí)行文件：經(jīng)編譯后所產(chǎn)生的目標代碼，再由鏈接程可執(zhí)行文件：經(jīng)編譯后所產(chǎn)生的目標代碼，再由鏈接程序鏈接后形成的文件。序鏈接后形成的文件。（3）按存取控制屬性分類）按存取控制屬性分類只執(zhí)行文件：只允許被核準的用戶調(diào)用執(zhí)行，既不允許讀，只執(zhí)行文件：只允許被核準的用戶調(diào)用執(zhí)行，既不允許讀，更不允許寫。更不允許寫。只讀文件：只允許文件主及被核準的用戶去讀，但不允許只讀文件：只允許文件主及被核準的用戶去讀，但不允許寫。寫。讀寫文件：允許文件主和被核準的用戶去讀文件和寫文件。讀寫文件：允許文件主和被核準的用戶去讀文件和寫文件。(4)按文件的邏輯結構分類按文件的邏輯結構分類有結構文件有結構文件:由若干個記錄

9、所構成由若干個記錄所構成,故又稱為記錄式文件故又稱為記錄式文件.根據(jù)記錄的長度分為定長記錄文件和可變長記錄文根據(jù)記錄的長度分為定長記錄文件和可變長記錄文件件.無結構文件（流式文件）無結構文件（流式文件）:這是直接由字符序列構成的文這是直接由字符序列構成的文件件,故又稱為流式文件故又稱為流式文件.可以把流式文件看成是記錄式可以把流式文件看成是記錄式文件的特例文件的特例,即其每個記錄中只含有一個字符即其每個記錄中只含有一個字符.(5)(5)按文件的物理結構分類按文件的物理結構分類: :順序文件順序文件: :指把邏輯文件中的記錄順序地存儲到連續(xù)地物指把邏輯文件中的記錄順序地存儲到連續(xù)地物理盤塊中理盤

10、塊中, ,這樣順序文件中所有記錄的次序這樣順序文件中所有記錄的次序, ,與它們在介質(zhì)與它們在介質(zhì)上存放的次序是一致的上存放的次序是一致的. .鏈接文件鏈接文件: :指文件中的各個記錄可以存放在不相鄰的各個指文件中的各個記錄可以存放在不相鄰的各個物理盤塊中物理盤塊中, ,通過物理塊中的鏈接指針將它們連接成一個鏈通過物理塊中的鏈接指針將它們連接成一個鏈表表. .索引文件索引文件: :指文件中的各個記錄可存儲在不相鄰的各個物指文件中的各個記錄可存儲在不相鄰的各個物理塊中理塊中, ,如同分區(qū)存儲管理一樣如同分區(qū)存儲管理一樣, ,需為每個文件建立一張所需為每個文件建立一張所引表引表, ,來實現(xiàn)記錄和物理

11、塊之間的映射來實現(xiàn)記錄和物理塊之間的映射. .在索引表中為每個在索引表中為每個記錄設置一個表項記錄設置一個表項, ,其中存放該記錄的記錄號極其所在的物其中存放該記錄的記錄號極其所在的物理塊號理塊號. .文文 件件 系系 統(tǒng)統(tǒng) 接接 口口邏邏 輯輯 文文 件件 系系 統(tǒng)統(tǒng)基本基本I/O管理程序（文件組織模塊）管理程序（文件組織模塊）基本文件系統(tǒng)（物理基本文件系統(tǒng)（物理I/O層）層）I/O控制層（設備驅(qū)動程序）控制層（設備驅(qū)動程序）對對 象象 及及 其其 屬屬 性性 說說 明明對對象操縱對對象操縱和管理的軟和管理的軟件集合件集合 文件系統(tǒng)是操作系統(tǒng)的重要組成部分文件系統(tǒng)是操作系統(tǒng)的重要組成部分,所

12、謂文所謂文件系統(tǒng)是指含有大量的文件極其屬性的說明件系統(tǒng)是指含有大量的文件極其屬性的說明,對文對文件進行操作和管理的軟件件進行操作和管理的軟件,以及向用戶提供的使用以及向用戶提供的使用文件的接口等的集合文件的接口等的集合. 文件系統(tǒng)的模型文件系統(tǒng)的模型:7.1.37.1.3文件系統(tǒng)的層次結構文件系統(tǒng)的層次結構(1)對象極其屬性說明對象極其屬性說明:文件：文件是文件系統(tǒng)管理的直接對象文件：文件是文件系統(tǒng)管理的直接對象.目錄目錄:為了方便用戶對文件的檢索和存取為了方便用戶對文件的檢索和存取,在文件系統(tǒng)中必須在文件系統(tǒng)中必須配置目錄配置目錄.在目錄中除包含文件名外在目錄中除包含文件名外,號包含文件屬性

13、說號包含文件屬性說明明.對目錄的組織和管理對目錄的組織和管理,是方便用戶和提高文件存取速是方便用戶和提高文件存取速度的關鍵度的關鍵.磁盤磁盤(磁帶磁帶)存儲空間存儲空間:文件和目錄必定占據(jù)存儲空間文件和目錄必定占據(jù)存儲空間,對這部對這部分存儲空間的有效管理分存儲空間的有效管理,不僅能提高外存的利用率不僅能提高外存的利用率,而且而且能加速對文件的存取能加速對文件的存取.(2)對對象操縱和管理軟件集合對對象操縱和管理軟件集合: 軟件集合是文件系統(tǒng)的核心軟件集合是文件系統(tǒng)的核心,文件系統(tǒng)的大部分功能都是在文件系統(tǒng)的大部分功能都是在這一層上實現(xiàn)的這一層上實現(xiàn)的.其功能有其功能有:對文件存儲空間的管理對

14、文件存儲空間的管理;對文件目錄的管理對文件目錄的管理;地址映射地址映射;文件的讀寫管理文件的讀寫管理;文件的共享與保護文件的共享與保護. 在這些功能的實現(xiàn)中在這些功能的實現(xiàn)中,通常又進一步劃分成幾個層次通常又進一步劃分成幾個層次:I/O控制層控制層:最低層最低層,主要由磁盤驅(qū)動程序和磁帶驅(qū)動程序組成主要由磁盤驅(qū)動程序和磁帶驅(qū)動程序組成.故又稱為設備驅(qū)動層故又稱為設備驅(qū)動層. 基本文件系統(tǒng)基本文件系統(tǒng): :又稱為物理又稱為物理I/OI/O層層. .該層主要用該層主要用于處理內(nèi)存與磁盤或磁帶機系統(tǒng)之間數(shù)據(jù)塊的交于處理內(nèi)存與磁盤或磁帶機系統(tǒng)之間數(shù)據(jù)塊的交換換. .基本文件系統(tǒng)無需了解所傳送的數(shù)據(jù)塊的

15、內(nèi)基本文件系統(tǒng)無需了解所傳送的數(shù)據(jù)塊的內(nèi)容或文件的結構容或文件的結構. . 基本基本I/OI/O管理程序管理程序: :又稱為文件組織模塊又稱為文件組織模塊. .該層該層完成與磁盤完成與磁盤I/OI/O有關的大量事務有關的大量事務, ,有有: :要選擇文件所在的設備要選擇文件所在的設備; ;進行文件邏輯塊號到物理塊號的轉(zhuǎn)換進行文件邏輯塊號到物理塊號的轉(zhuǎn)換; ;空隙盤塊的管理空隙盤塊的管理; ;I/OI/O緩沖區(qū)的指定緩沖區(qū)的指定; ; 邏輯文件系統(tǒng)邏輯文件系統(tǒng). .(3)(3)文件系統(tǒng)的接口文件系統(tǒng)的接口: : 文件系統(tǒng)向用戶提供兩種接口文件系統(tǒng)向用戶提供兩種接口: : 命令接口命令接口; ;

16、程序接口程序接口. . 7.1.4 7.1.4 文件操作文件操作(1)(1)最基本的文件操作最基本的文件操作: : 創(chuàng)建文件創(chuàng)建文件; ; 刪除文件刪除文件; ; 讀文件讀文件; ; 寫文件寫文件; ;設置文件的讀設置文件的讀/ /寫位置寫位置. .(2)(2)文件的文件的“打開打開”和和“關閉關閉”: :“打開打開”：指系統(tǒng)將指名文件的屬性（包括該文件在：指系統(tǒng)將指名文件的屬性（包括該文件在外存上的物理位置）從外存拷貝到內(nèi)存中的一個打開外存上的物理位置）從外存拷貝到內(nèi)存中的一個打開文件表的表目中。并將該表目的編號（或稱為索引）文件表的表目中。并將該表目的編號（或稱為索引）返回給用戶。返回給用

17、戶。“關閉關閉”：將打開的文件從打開文件表的表目中刪除：將打開的文件從打開文件表的表目中刪除掉。掉。（3 3）其它文件操作：）其它文件操作：對文件屬性的操作；對文件屬性的操作；對文件有關的目錄的操作：創(chuàng)建目錄，刪除目錄等。對文件有關的目錄的操作：創(chuàng)建目錄，刪除目錄等。 文件的邏輯結構：從用戶觀點出發(fā)所觀察到的文件的組織文件的邏輯結構：從用戶觀點出發(fā)所觀察到的文件的組織形式，是用戶可以直接處理的數(shù)據(jù)及其結構，獨立于文件形式，是用戶可以直接處理的數(shù)據(jù)及其結構，獨立于文件的物理特性。又稱為文件組織。的物理特性。又稱為文件組織。 文件的物理結構：又稱為文件的存儲結構。指文件在外存文件的物理結構：又稱為

18、文件的存儲結構。指文件在外存上的存儲組織形式。不僅與存儲介質(zhì)的存儲性能有關，而上的存儲組織形式。不僅與存儲介質(zhì)的存儲性能有關，而且與所采用的外存分配方式有關。且與所采用的外存分配方式有關。 文件邏輯結構的設計要求：文件邏輯結構的設計要求： 訪問性能：便于檢索；便于修改訪問性能：便于檢索；便于修改; 存儲性能：向物理存儲轉(zhuǎn)換方便，節(jié)省空間存儲性能：向物理存儲轉(zhuǎn)換方便，節(jié)省空間; 文件的不同組織層次：域、記錄、文件文件的不同組織層次：域、記錄、文件.1 1 按文件是否有結構分類按文件是否有結構分類(1)(1)有結構文件有結構文件 在記錄式文件中，所有的記錄通常都是描述在記錄式文件中，所有的記錄通常

19、都是描述一個實體集的，有著相同或不同數(shù)目的數(shù)據(jù)項，一個實體集的，有著相同或不同數(shù)目的數(shù)據(jù)項，記錄的長度可分為定長和不定長兩類。記錄的長度可分為定長和不定長兩類。 另外根據(jù)用戶和系統(tǒng)管理的需要可采用多種另外根據(jù)用戶和系統(tǒng)管理的需要可采用多種方式來組織這些記錄方式來組織這些記錄, ,形成形成: : 順序文件順序文件: :一系列記錄按照某種順序排列所形成一系列記錄按照某種順序排列所形成的文件的文件, ,記錄通常是定長的記錄通常是定長的. . 索引文件索引文件: :記錄可變長記錄可變長; ; 索引順序文件索引順序文件: :既有索引表又為每一組記錄中的既有索引表又為每一組記錄中的第一個記錄設置一表項第一

20、個記錄設置一表項. .(2)(2)無結構文件無結構文件 文件體為字節(jié)流，不劃分記錄，順序訪問，文件體為字節(jié)流，不劃分記錄，順序訪問，每次讀寫訪問可以指定任意數(shù)據(jù)長度。當前操作每次讀寫訪問可以指定任意數(shù)據(jù)長度。當前操作系統(tǒng)中常用的文件組織。系統(tǒng)中常用的文件組織。 如如:大量的源程序大量的源程序; 庫函數(shù)庫函數(shù). 在在UNIX系統(tǒng)中所有的文件都被看成流式文系統(tǒng)中所有的文件都被看成流式文件件.系統(tǒng)不對文件進行格式處理系統(tǒng)不對文件進行格式處理. 2 按文件的組織方式分類按文件的組織方式分類 （1）順序文件：指由一系列記錄按某種順序）順序文件：指由一系列記錄按某種順序排列所形成的文件。排列所形成的文件。

21、 （2）索引文件：指為可變長記錄文件建立一）索引文件：指為可變長記錄文件建立一張索引表，為每個記錄設置一個表項，以加速對張索引表，為每個記錄設置一個表項，以加速對記錄的檢索速度。記錄的檢索速度。 （3）索引順序文件：這是順序文件和索引文）索引順序文件：這是順序文件和索引文件相結合的產(chǎn)物，在為每個文件建立一張索引表件相結合的產(chǎn)物，在為每個文件建立一張索引表時，并不是為每個記錄建立一個索引表項，而是時，并不是為每個記錄建立一個索引表項，而是為一組記錄中的第一個記錄建立索引表項。為一組記錄中的第一個記錄建立索引表項。 文件體為大小相同的排序記錄序列。文件體為大小相同的排序記錄序列。 它由一個主文件和

22、一個臨時文件組成。它由一個主文件和一個臨時文件組成。 記錄大小相同，按某個關鍵字域記錄大小相同，按某個關鍵字域(key (key field)field)排序，存放在主文件排序，存放在主文件(master file)(master file)中。中。新記錄暫時保存在日志或事務文件新記錄暫時保存在日志或事務文件(log file (log file or transaction file)or transaction file)中，定期歸并入主文中，定期歸并入主文件。件。(1)(1)順序文件的排序方式順序文件的排序方式串結構：按存入時間的先后排列。串結構：按存入時間的先后排列。順序結構：文件中的

23、所有記錄按關鍵字排列。順序結構：文件中的所有記錄按關鍵字排列。 對順序結構文件有更高的檢索效率對順序結構文件有更高的檢索效率. . 因為在檢索串結構文件時因為在檢索串結構文件時, ,每次都必須從頭每次都必須從頭開始開始. .逐個記錄查找逐個記錄查找, ,直到找到指定記錄或查完直到找到指定記錄或查完所有的記錄為止所有的記錄為止. .而對順序結構文件而對順序結構文件, ,可利用某可利用某種有效的查找算法種有效的查找算法, ,如折半查找法、插值查找法、如折半查找法、插值查找法、跳步查找法等方法來提高檢索效率跳步查找法等方法來提高檢索效率. .(2)(2)順序文件的優(yōu)缺點順序文件的優(yōu)缺點優(yōu)點優(yōu)點: :

24、 簡單簡單; ; 支持順序存取和隨機存取支持順序存取和隨機存取; ; 順序存取速度快順序存取速度快; ; 所需的磁盤尋道次數(shù)和尋道時間最少所需的磁盤尋道次數(shù)和尋道時間最少. .缺點缺點: : 文件不能動態(tài)增長文件不能動態(tài)增長, ,預留空間預留空間, ,浪費浪費; ;重新分配和移動重新分配和移動; ;不利于文件插入和刪除不利于文件插入和刪除; ;外部碎片問題外部碎片問題, ,存儲壓縮技術存儲壓縮技術. . 為了訪問順序文件中的一條記錄，首先為了訪問順序文件中的一條記錄，首先應找到該記錄的地址。應找到該記錄的地址。 查找記錄地址的方法有：查找記錄地址的方法有：隱式尋址方式隱式尋址方式顯式尋址方式顯

25、式尋址方式R0R1I0I1IiR2R3RiR0R1RiRptrRptrllllll 0l 1l i0l2l3l4li l(i+1) l0l 0+1l 0+l 1+2(l k+1)(l k+1)K=0K=0ii - 1 定長記錄文件；定長記錄文件； 變長記錄文件變長記錄文件 (1)(1)隱式尋址方式隱式尋址方式 順序文件中的記錄可以是定長的，也可以是順序文件中的記錄可以是定長的，也可以是變長的變長的. . 對于定長記錄的順序文件，如果已知當前記對于定長記錄的順序文件，如果已知當前記錄的邏輯地址，便很容易確定下一個記錄的邏輯錄的邏輯地址，便很容易確定下一個記錄的邏輯地址。地址。 在讀一個文件時，可

26、設置一個讀指針在讀一個文件時，可設置一個讀指針Rptr，令它指向下一個記錄的首地址，每當讀完一個記令它指向下一個記錄的首地址，每當讀完一個記錄時，便執(zhí)行錄時，便執(zhí)行: Rptr ：= Rptr + l操作，使之指向下一個記錄的首地址。操作，使之指向下一個記錄的首地址。 在寫一個文件時，也應設置一寫指針在寫一個文件時，也應設置一寫指針Wptr，使之指向要寫的記錄的首地址。同樣，在每寫完使之指向要寫的記錄的首地址。同樣，在每寫完一個記錄時，又執(zhí)行以下操作：一個記錄時，又執(zhí)行以下操作： Wptr ：= Wptr + 1 記錄大小不必相同，不必排序，存放在主文件記錄大小不必相同，不必排序，存放在主文件

27、(primary file)(primary file)中。索引文件與索引順序文件的區(qū)中。索引文件與索引順序文件的區(qū)別在于主文件不排序。另外建立索引，每個索引項別在于主文件不排序。另外建立索引，每個索引項指向一個記錄，索引項按照記錄中的某個關鍵字域指向一個記錄，索引項按照記錄中的某個關鍵字域排序。對同一主文件，可以針對不同的關鍵字域相排序。對同一主文件，可以針對不同的關鍵字域相應建立多個索引。索引文件的記錄項通常較小，查應建立多個索引。索引文件的記錄項通常較小，查找速度快，便于隨機訪問找速度快，便于隨機訪問(random access)(random access)。(1)(1)索引文件的優(yōu)缺

28、點索引文件的優(yōu)缺點 優(yōu)點：優(yōu)點： 保持了鏈接結構的優(yōu)點保持了鏈接結構的優(yōu)點, ,又解決了其缺點：又解決了其缺點： 既能順序存取既能順序存取, ,又能隨機存取又能隨機存取; ; 滿足了文件動態(tài)增長、插入刪除的要求滿足了文件動態(tài)增長、插入刪除的要求; ; 能充分利用外存空間。能充分利用外存空間。 缺點缺點: : 較多的尋道次數(shù)和尋道時間較多的尋道次數(shù)和尋道時間 索引表本身帶來了系統(tǒng)開銷索引表本身帶來了系統(tǒng)開銷; ; 內(nèi)外存空間內(nèi)外存空間, ,存取時間。存取時間。(2)索引表組織索引表組織鏈接模式鏈接模式: 一個盤塊一個索引表，多個索引表鏈接起來一個盤塊一個索引表，多個索引表鏈接起來.多級索引多級索

29、引: 將一個大文件的所有索引表（二級索引將一個大文件的所有索引表（二級索引)的地址的地址放在另一個索引表（一級索引放在另一個索引表（一級索引)中中.綜合模式綜合模式: : UNIX UNIX文件系統(tǒng)采用的是多級索引結構文件系統(tǒng)采用的是多級索引結構( (綜合模式綜合模式) )。每個文件的索引表為每個文件的索引表為1313個索引項，每項個索引項，每項2 2個字節(jié)。最前個字節(jié)。最前面面1010項直接登記存放文件信息的物理塊號（直接尋項直接登記存放文件信息的物理塊號（直接尋址）。址）。 如果文件大于如果文件大于1010塊，則利用第塊，則利用第1111項指向一個物理項指向一個物理塊，該塊中最多可放塊，該

30、塊中最多可放256256個存放文件物理塊的塊號（一個存放文件物理塊的塊號（一次間接尋址）。對于更大的文件還可利用第次間接尋址）。對于更大的文件還可利用第1212和第和第1313項作為二次和三次間接尋址。項作為二次和三次間接尋址。 UNIXUNIX中采用了三級索引結構后，文件最大可達中采用了三級索引結構后，文件最大可達1616兆個物理塊。兆個物理塊。索引號01m1m0指針ptr長度mimiR0R1Ri.索引表索引表邏輯文件邏輯文件索引文件的組織索引文件的組織:1 1 索引順序文件的特征索引順序文件的特征 是順序文件和索引文件相結合的產(chǎn)物是順序文件和索引文件相結合的產(chǎn)物. .在在順序文件（主文件順

31、序文件（主文件main filemain file）的基礎上，另）的基礎上，另外建立索引外建立索引(index)(index)和溢出文件和溢出文件(overflow (overflow file)file)。這樣做的目的是加快順序文件的檢索。這樣做的目的是加快順序文件的檢索速度。速度。 在索引文件中，可將關鍵字域中的取值劃在索引文件中，可將關鍵字域中的取值劃分若干個區(qū)間（如分若干個區(qū)間（如AZAZ可以劃分為可以劃分為A A到到Z Z共共2626個個區(qū)間），每個區(qū)間對應一個索引項，后者指向區(qū)間），每個區(qū)間對應一個索引項，后者指向該區(qū)間的開頭記錄。新記錄暫時保存在溢出文該區(qū)間的開頭記錄。新記錄暫時

32、保存在溢出文件中，定期歸并入主文件。件中，定期歸并入主文件。關鍵字邏輯地址姓名其它屬性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件順序文件2 一級索引順序文件一級索引順序文件:3 3 多級索引順序文件多級索引順序文件 通過劃分層次，在記錄數(shù)量較大時，比通過劃分層次，在記錄數(shù)量較大時，比順序文件大大縮短檢索時間。順序文件是順序文件大大縮短檢索時間。順序文件是N/2(N/2(這時可使用折半查找這時可使用折半查找) )，而索引順序文件，而索引順序文件（一級索引）是（一級索引）是i/2 + N/(2i/2 + N/(2* *i)i)，其中，其中

33、i i為索為索引長度。索引還可以是多級的。如：有引長度。索引還可以是多級的。如：有1000,0001000,000條記錄的順序文件的平均檢索長度條記錄的順序文件的平均檢索長度為為500,000500,000，而在添加一個有，而在添加一個有10001000條索引項條索引項的索引文件后，平均檢索長度為的索引文件后，平均檢索長度為10001000。1 1 直接文件直接文件 采用前面幾種文件結構對記錄進行存取時，采用前面幾種文件結構對記錄進行存取時，都必須用給定的記錄鍵值，先對線性表或鏈表都必須用給定的記錄鍵值，先對線性表或鏈表進行檢索，以找到指定記錄的物理地址。進行檢索，以找到指定記錄的物理地址。

34、然而對于直接文件，則可根據(jù)給定的關鍵然而對于直接文件，則可根據(jù)給定的關鍵字直接獲得指定記錄的物理地址。字直接獲得指定記錄的物理地址。1 1 哈希文件哈希文件 這是目前應用最為廣泛的一種直接文件。這是目前應用最為廣泛的一種直接文件。它利用它利用HashHash函數(shù)（散列函數(shù)）可將關鍵字轉(zhuǎn)換函數(shù)（散列函數(shù)）可將關鍵字轉(zhuǎn)換為相應記錄的地址。為相應記錄的地址。6.3 6.3 外存分配方法外存分配方法6.3.1 6.3.1 連續(xù)分配連續(xù)分配6.3.2 6.3.2 鏈接分配鏈接分配 6.3.3 6.3.3 索引分配索引分配 文件目錄是一種數(shù)據(jù)結構，用于標識系統(tǒng)中的文件目錄是一種數(shù)據(jù)結構，用于標識系統(tǒng)中的文

35、件及其物理地址，供檢索時使用。文件及其物理地址，供檢索時使用。 目錄是由文件說明索引組成的用于文件檢索的目錄是由文件說明索引組成的用于文件檢索的特殊文件。文件目錄的內(nèi)容主要是文件訪問的控制特殊文件。文件目錄的內(nèi)容主要是文件訪問的控制信息（不包括文件內(nèi)容）。目錄管理是指目錄訪問信息（不包括文件內(nèi)容）。目錄管理是指目錄訪問和目錄屬性控制。和目錄屬性控制。 文件目錄具有將文件名轉(zhuǎn)換為該文件在外存文件目錄具有將文件名轉(zhuǎn)換為該文件在外存的物理位置的功能，這也正是文件目錄所提供的的物理位置的功能，這也正是文件目錄所提供的最基本的功能。對文件目錄的管理有以下要求：最基本的功能。對文件目錄的管理有以下要求：

36、實現(xiàn)實現(xiàn)“按名存取按名存取“； 提高對目錄的檢索速；提高對目錄的檢索速； 文件共享；文件共享； 允許文件重名。允許文件重名。 1 文件控制塊（文件控制塊（FCB） 文件控制塊是操作系統(tǒng)為管理文件而設置的文件控制塊是操作系統(tǒng)為管理文件而設置的數(shù)據(jù)結構，存放了為管理文件所需的所有有關信數(shù)據(jù)結構，存放了為管理文件所需的所有有關信息。息。 文件控制塊是文件存在的標志。文件控制塊是文件存在的標志。 文件控制塊的內(nèi)容：文件控制塊的內(nèi)容： 基本信息：文件名，文件物理位置，文件邏輯結構，文基本信息：文件名，文件物理位置，文件邏輯結構，文件物理結構。件物理結構。 存取控制信息：文件主的存取權限、核準用戶的存取權

37、存取控制信息：文件主的存取權限、核準用戶的存取權限及一般用戶的存取權限。限及一般用戶的存取權限。 使用信息：文件的建立日期和時間，文件最后修改日期使用信息：文件的建立日期和時間，文件最后修改日期和時間和當前使用信息（如已經(jīng)打開文件的進程數(shù)據(jù)，和時間和當前使用信息（如已經(jīng)打開文件的進程數(shù)據(jù)，是否會被其它進程鎖住等）。是否會被其它進程鎖住等）。文件名文件名擴展名擴展名屬屬 性性備備 用用時時 間間日日 期期第一塊號第一塊號盤塊數(shù)盤塊數(shù)MS-DOS的文件控制塊的文件控制塊 2 2 索引結點索引結點 索引結點的引入索引結點的引入: : 在有些系統(tǒng)中如在有些系統(tǒng)中如UNIXUNIX系統(tǒng)，把文件描述信息單

38、獨形系統(tǒng)，把文件描述信息單獨形成一個稱為索引結點的數(shù)據(jù)結構，簡稱為成一個稱為索引結點的數(shù)據(jù)結構，簡稱為i i結點；而在結點；而在文件目錄的每個目錄項，則僅由文件名及指向該文件文件目錄的每個目錄項，則僅由文件名及指向該文件所對應的所對應的i i結點的指針所構成。結點的指針所構成。文件名文件名1文件名2索引結點編號UNIX的文件目錄磁盤索引結點主要內(nèi)容包括：磁盤索引結點主要內(nèi)容包括： 文件主標識、文件類型、文件存取權限、文件物文件主標識、文件類型、文件存取權限、文件物理地址、文件長度、文件連接計數(shù)和文件存取時間。理地址、文件長度、文件連接計數(shù)和文件存取時間。內(nèi)存索引結點主要內(nèi)容包括：內(nèi)存索引結點主

39、要內(nèi)容包括： 索引結點編號、狀態(tài)、訪問計數(shù)、文件所在設備索引結點編號、狀態(tài)、訪問計數(shù)、文件所在設備的邏輯設備號和鏈接指針。的邏輯設備號和鏈接指針。 1. 1.單級目錄結構（一級目錄結構）：單級目錄結構（一級目錄結構）： 整個目錄組織是一個線性結構，系統(tǒng)中的所有文整個目錄組織是一個線性結構，系統(tǒng)中的所有文件都建立在一張目錄表中。它主要用于單用戶操作系件都建立在一張目錄表中。它主要用于單用戶操作系統(tǒng)。統(tǒng)。優(yōu)點優(yōu)點: : 簡單，易實現(xiàn)簡單，易實現(xiàn). .缺點缺點: : 限制了用戶對文件的命名，不允許文件重名限制了用戶對文件的命名，不允許文件重名; ; 文件平均檢索時間長文件平均檢索時間長; ; 限制了

40、對文件的共享限制了對文件的共享. .文件名狀態(tài)位物理地址文件其它屬性AlphaReportText單級目錄單級目錄: : 2. 2.兩級目錄結構：兩級目錄結構： 在根目錄下，每個用戶對應一個目錄（第二級目在根目錄下，每個用戶對應一個目錄（第二級目錄）；在用戶目錄下是該用戶的文件，而不再有下級錄）；在用戶目錄下是該用戶的文件，而不再有下級目錄。適用于多用戶系統(tǒng)，各用戶可有自己的專用目目錄。適用于多用戶系統(tǒng)，各用戶可有自己的專用目錄。錄。 為改變一級目錄文件目錄命名沖突，并提高對目為改變一級目錄文件目錄命名沖突，并提高對目錄文件檢索速度而改進。錄文件檢索速度而改進。目錄分為兩級：目錄分為兩級： 一

41、級稱為主文件目錄，給出用戶名，用戶子目錄一級稱為主文件目錄，給出用戶名，用戶子目錄所在的物理位置；所在的物理位置； 二級稱為用戶文件目錄（又稱用戶子目錄），給二級稱為用戶文件目錄（又稱用戶子目錄），給出該用戶所有文件的出該用戶所有文件的FCBFCB。 優(yōu)點：優(yōu)點： 提高了檢索目錄的速度；提高了檢索目錄的速度； 在不同的用戶目錄中，可以使用相同文件名，只要在不同的用戶目錄中，可以使用相同文件名，只要在用戶自己的在用戶自己的UFDUFD中其文件名都是唯一的；中其文件名都是唯一的； 不同用戶還可使用不同的文件名，來訪問系統(tǒng)中的不同用戶還可使用不同的文件名，來訪問系統(tǒng)中的同一個共享文件。同一個共享文件

42、。 缺點：增加了系統(tǒng)開銷缺點：增加了系統(tǒng)開銷. .用戶名WangZhangGaoAophaTestReportTestBetaDeviceMisx指向子目錄指針Wang用戶目錄Zhang用戶目錄Gao用戶目錄AlphaTestTestReportBeta DeviceMisx兩極目錄結構兩極目錄結構 3 3 多級目錄結構多級目錄結構 或稱為樹狀目錄或稱為樹狀目錄(tree-like)(tree-like)。在文件數(shù)目較多時，。在文件數(shù)目較多時，便于系統(tǒng)和用戶將文件分散管理。適用于較大的文件便于系統(tǒng)和用戶將文件分散管理。適用于較大的文件系統(tǒng)管理。目錄級別太多時，會增加路徑檢索時間。系統(tǒng)管理。目錄

43、級別太多時，會增加路徑檢索時間。通常把包括三級在內(nèi)的三級以上的文件目錄結構稱為通常把包括三級在內(nèi)的三級以上的文件目錄結構稱為樹型結構的目錄樹型結構的目錄. .目錄名：可以修改。目錄名：可以修改。目錄樹：中間結點是目錄，葉子結點是目錄或文件。目錄樹：中間結點是目錄，葉子結點是目錄或文件。目錄的上下級關系：目錄的上下級關系： 當前目錄當前目錄(current directory, working directory)(current directory, working directory)； 父目錄父目錄(parent directory)(parent directory)； 子目錄子目錄(s

44、ubdirectory)(subdirectory)； 根目錄根目錄(root directory)(root directory)等等. . 路徑路徑(path)(path)： 每個目錄或文件，可以由根目錄開始依次經(jīng)由的每個目錄或文件，可以由根目錄開始依次經(jīng)由的各級目錄名，加上最終的目錄名或文件名來表示各級目錄名，加上最終的目錄名或文件名來表示. . 優(yōu)點：優(yōu)點： 層次結構清晰，便于管理和保護層次結構清晰，便于管理和保護, ,解決重名問題解決重名問題, ,查找速度加快查找速度加快. . 缺點：缺點： 查找一個文件按路徑名逐層檢查，由于每個文件查找一個文件按路徑名逐層檢查，由于每個文件都放在外

45、存，多次訪盤影響速度。都放在外存，多次訪盤影響速度。ABC根目錄EPABDFEDBGAEHIJKABCDELMNA 改進的多級目錄：改進的多級目錄： 為了提高目錄檢索速度，可把目錄中的文件說明（文件為了提高目錄檢索速度，可把目錄中的文件說明（文件描述符）信息分成兩個部分：描述符）信息分成兩個部分： 符號文件目錄：符號文件目錄： 由文件名和文件內(nèi)部標識組成的樹狀結構，按文件名由文件名和文件內(nèi)部標識組成的樹狀結構，按文件名排序排序. . 基本文件目錄（索引節(jié)點目錄）：基本文件目錄（索引節(jié)點目錄）： 由其余文件說明信息組成的線性結構，按文件內(nèi)部標由其余文件說明信息組成的線性結構，按文件內(nèi)部標識排序識

46、排序. .1內(nèi)部名ID其它信息地址234567891011基本文件目錄(ID1)ID4ID5ID7ID9ID10ID11文件名ID3Tu-Lide8Tu-Qi根目錄(ID2)文件名ID7Products5RoomsTu-Lide的目錄(ID3)4Software6Tools文件名IDTools的目錄(ID6)11SA-SD10Univer文件名ID10Univer5ClassroomTu-Lide的目錄(ID3)9Tools基本文件目錄基本文件目錄:Tu-Lide的目錄(ID3)ProductsRoomsSoftwareTools根目錄(ID2)Tu-LideTu-QiTu-Lide的目錄(I

47、D8)UniverClassroomToolsTools的目錄(ID6)SA-SDUniverID4ID5ID7ID9ID10ID11符號文件目錄的層次結構符號文件目錄的層次結構:對目錄進行查詢的方式：對目錄進行查詢的方式： 線性檢索法和線性檢索法和Hash方法方法線性檢索法：線性檢索法： 又稱為順序檢索法，在單級目錄中，利用用又稱為順序檢索法，在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄戶提供的文件名，用順序查找法直接從文件目錄表中找到指名文件的目錄項。在樹型目錄中，用表中找到指名文件的目錄項。在樹型目錄中，用戶提供的文件名是由多個文件分量名組成的路徑戶提供的文件名是由多個

48、文件分量名組成的路徑名，此時須對多級目錄進行查找。名，此時須對多級目錄進行查找。114791468bal bindev496libetcusrtmp6119305126452666492176081132astjimerikdicksrcminixmboxbooksgrants 根目錄結點6是/usr的目錄132#塊是/usr的目錄結點26是/usr/ast目錄496#塊是/usr/ast目錄在結點6中查找usr字段查找查找/usr/ast/mbox/usr/ast/mbox的步驟的步驟: :HashHash方法：方法： 如果建立了一張如果建立了一張 HashHash索引目錄，利用索引目錄，利

49、用HashHash方法進行查方法進行查詢。詢。 系統(tǒng)利用用戶提供的文件名并將它變換為文件目錄的系統(tǒng)利用用戶提供的文件名并將它變換為文件目錄的索引值，再利用該索引值到目錄中去查找，將顯著的提高索引值，再利用該索引值到目錄中去查找，將顯著的提高檢索速度。檢索速度。 在進行文件名轉(zhuǎn)換時，可能把不同的文件名轉(zhuǎn)換為相在進行文件名轉(zhuǎn)換時，可能把不同的文件名轉(zhuǎn)換為相同的同的HashHash值，解決此問題的方法是：值，解決此問題的方法是： 在利用在利用HashHash法索引查找目錄時，如果目錄表中相應的目錄法索引查找目錄時，如果目錄表中相應的目錄項是空的，表示系統(tǒng)中并無指定文件；項是空的，表示系統(tǒng)中并無指定文

50、件； 如果目錄表項中的文件名與指定文件名相匹配，表示該目如果目錄表項中的文件名與指定文件名相匹配，表示該目錄項正式所要尋找的文件所對應的目錄項，可以從中找到錄項正式所要尋找的文件所對應的目錄項，可以從中找到該文件的物理地址；該文件的物理地址； 如果在目錄表項中的文件名與指定文件名不匹配，表示發(fā)如果在目錄表項中的文件名與指定文件名不匹配，表示發(fā)生了沖突，此時需將生了沖突，此時需將HashHash值再加上一個常數(shù)（該常數(shù)應與值再加上一個常數(shù)（該常數(shù)應與目錄的長度值互質(zhì)），形成新的索引值，再返回到第一步目錄的長度值互質(zhì)），形成新的索引值，再返回到第一步重新開始查找。重新開始查找。 定義定義: : 一

51、個文件被多個用戶或程序使用。一個文件被多個用戶或程序使用。 目的：目的： 節(jié)省時間和存儲空間，減少了用戶節(jié)省時間和存儲空間，減少了用戶 工作量；進程間通過文件交換信息。工作量；進程間通過文件交換信息。 繞彎路法繞彎路法: :早期的早期的MULTICSMULTICS等操作系統(tǒng)中所采用的一種等操作系統(tǒng)中所采用的一種共享文件方法共享文件方法. .該方法中該方法中, ,允許用戶獲得一個允許用戶獲得一個“當前目當前目錄錄”. .用戶所訪問的所有文件都是相對于當前目錄用戶所訪問的所有文件都是相對于當前目錄; ; 當所訪問的文件不在其當前目錄下時當所訪問的文件不在其當前目錄下時, ,可以通過可以通過“向上走

52、向上走”的方式去訪問其上級目錄的方式去訪問其上級目錄. .為此用為此用“* *”表表示一個目錄的父目錄示一個目錄的父目錄. .假定當前目錄為假定當前目錄為F,F,若用戶要訪問若用戶要訪問E E的文件的文件J,J,可利用路徑名可利用路徑名* *.E.J,.E.J,還可以利用還可以利用* *. .* *.C.A.C.A來來訪問文件訪問文件, ,缺點：路徑繞彎缺點：路徑繞彎; ; 文件文件n,n,文件文件1 1：不同的文件名可以：不同的文件名可以 訪問該文件。訪問該文件。 連訪法連訪法: :在目錄項之間進行鏈接在目錄項之間進行鏈接. .一個目錄中的目錄項一個目錄中的目錄項直接指向另一目錄中的目錄項直

53、接指向另一目錄中的目錄項. .在連訪法實現(xiàn)文件共享在連訪法實現(xiàn)文件共享時時, ,應在文件說明中增加一連訪屬性應在文件說明中增加一連訪屬性, ,以指示文件說明以指示文件說明中的物理地址是一指向文件或共享文件的目錄項的指中的物理地址是一指向文件或共享文件的目錄項的指針針, ,應包括共享該文件的應包括共享該文件的“用戶計數(shù)用戶計數(shù)”, ,用于表示共有用于表示共有多少用戶需要使用此文件多少用戶需要使用此文件, ,僅當已無用戶再需要此文件僅當已無用戶再需要此文件時才可將此共享文件撤消時才可將此共享文件撤消. . 缺點：（缺點：（1 1）增加了連訪屬性）增加了連訪屬性 （2 2）增加）增加“用戶計數(shù)用戶計

54、數(shù)” （3 3）文件）文件n,n,文件文件1 1：不同的文件名可以：不同的文件名可以 訪問該訪問該文件。文件。 利用基本文件目錄實現(xiàn)文件共享利用基本文件目錄實現(xiàn)文件共享: : 在文件系統(tǒng)中設置一個基本目錄，每在文件系統(tǒng)中設置一個基本目錄，每個文件在該目錄中均占有一個目錄項，用個文件在該目錄中均占有一個目錄項，用于給出系統(tǒng)賦予的、對應于該文件名的唯于給出系統(tǒng)賦予的、對應于該文件名的唯一標識符（整數(shù)），以及該文件的有關說一標識符（整數(shù)），以及該文件的有關說明信息。明信息。0123456789Wang3Zhang1MistAlphaReportOaf7689空閑文件目錄ID物理位置主文件目錄MFD符

55、號名 IDSqrtBeta56符號名 ID符號名 ID主目錄MFDZhang的SFDSqrt Wang的Beta Zhang的AlphaMistReportOafWang的SFD基本文件目錄利用基本文件目錄實現(xiàn)文件共享利用基本文件目錄實現(xiàn)文件共享: 將諸如文件的物理地址及其它的文件屬性等信息將諸如文件的物理地址及其它的文件屬性等信息放在索引結點中。在文件目錄中只設置文件名及指向放在索引結點中。在文件目錄中只設置文件名及指向相應索引結點的指針相應索引結點的指針.Test rTest rcount = 2文件物理地址Test索引結點Wang用戶文件目錄Lee用戶文件目錄基于索引結點的共享方式基于索引結點的共享方式: B為了共享為了共享C的一個文件的一個文件F，可以由系統(tǒng)創(chuàng)建一個，可以由系統(tǒng)創(chuàng)建一個LINK類型的新文件，將新文件類型的新文件，將新文件F寫入寫入B的用戶目錄中，的用戶目錄中，以實現(xiàn)以實現(xiàn)B的目錄與文件的目錄與文件F的鏈接。在新文件中只包含被鏈的鏈接。在新文件中只包含被鏈接文件接文件F的路徑名，稱這樣的鏈接方法為符號鏈接的路徑名，稱這樣的鏈接方法為符號鏈接（Symbolic Linking）。）。 優(yōu)點：能夠鏈接世界上任何地方的機器中的文件優(yōu)點：能夠鏈接世界上任何地方的機器中的文件 缺點：需要配置索引結點缺點：需要配置索引結點