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

1、n文件系統(tǒng)的概念n文件的邏輯結(jié)構(gòu)和存取方法n文件的物理結(jié)構(gòu)與存儲設(shè)備n文件存儲空間的管理n文件目錄管理n文件存取控制n文件的使用n文件系統(tǒng)的層次模型第8章 文件系統(tǒng)第8章 文件系統(tǒng)n所有的計算機應(yīng)用程序都要存儲信息檢索信息n三個基本要求能夠存儲大量的信息長期保存信息可以共享信息n解決方法把信息以一種單元，即文件的形式存儲在外部介質(zhì)上文件是通過操作系統(tǒng)來管理的，包括：文件的結(jié)構(gòu)、命名、存取、使用、保護和實現(xiàn)方法文件系統(tǒng)是計算機組織、存取和保存信息的重要手段第8章 文件系統(tǒng)n研究文件系統(tǒng)的兩種觀點用戶觀點n文件系統(tǒng)如何呈現(xiàn)在用戶面前：一個文件由什么組成，如何命名，如何保護，可以進行何種操作等等操作

2、系統(tǒng)觀點n文件目錄怎樣實現(xiàn)，怎樣管理存儲空間，文件存儲位置，磁盤實際運作方式(與設(shè)備管理的接口)等等n本章討論文件的組織結(jié)構(gòu)、存取結(jié)構(gòu)、保護以及文件系統(tǒng)空間管理問題第8章 文件系統(tǒng)8.1 文件系統(tǒng)的概念 1.文件系統(tǒng)的引入操作系統(tǒng)管理計算機的軟件和硬件資源圖8.1 操作系統(tǒng)的軟硬件管理1.文件系統(tǒng)的引入n使用計算機完成某件任務(wù)，用戶會遇到問題：使用現(xiàn)有的軟件資源來協(xié)助完成自己的任務(wù)將編制的程序和要訪問的數(shù)據(jù)存放何處即，如何對軟件資源進行透明地快速存??？n文件系統(tǒng)實現(xiàn)對程序和數(shù)據(jù)的透明存取透明存?。菏侵覆槐亓私馕募娣诺奈锢斫Y(jié)構(gòu)和查找方法等與存取介質(zhì)有關(guān)的部分，只需給定文件名，文件系統(tǒng)便可實現(xiàn)對

3、其的有關(guān)操作1.文件系統(tǒng)的引入n文件系統(tǒng)必須完成以下工作統(tǒng)一管理文件的存儲空間，實施存儲空間的分配與回收實現(xiàn)文件的按名存取，需要一個用戶可見的文件邏輯結(jié)構(gòu)實現(xiàn)信息的存放與加工，需要文件的物理結(jié)構(gòu)實現(xiàn)文件信息的查找實現(xiàn)文件信息的共享，并提供文件的保護和保密措施8.1 文件系統(tǒng)的概念2.文件與文件系統(tǒng)的概念（1）文件定義：文件是一組賦名的相關(guān)聯(lián)字符流的集合，或者是相關(guān)聯(lián)記錄的集合。 字符流文件n是一種無結(jié)構(gòu)文件或流式文件n適用于源程序、目標(biāo)代碼等文件記錄式文件n記錄：由N 個字節(jié)組成的具有特定意義的信息單位n適用于信息管理，例如數(shù)據(jù)庫系統(tǒng)等2.文件與文件系統(tǒng)的概念文件中的元素是可編址的最小信息項n

4、信息項：構(gòu)成文件內(nèi)容的基本單位n長度：單個字節(jié)或多個字節(jié)記錄式文件：由若干個記錄組成n記錄是一個有意義的信息集合，是對文件進行存取操作的基本單位n記錄的長度可以相等/不等各信息項之間具有順序關(guān)系信息項 信息項 . 信息項 . 信息項編號：編號：0 1 i n-1讀寫指針讀寫指針n文件是一個抽象機制，它提供了一種把信息保存在存儲介質(zhì)上，而且便于以后存取的方法，用戶不必關(guān)心實現(xiàn)細節(jié)。n用戶文件名由用戶給定（2）文件系統(tǒng)文件系統(tǒng)：操作系統(tǒng)中管理文件有關(guān)的軟件和數(shù)據(jù)稱為文件系統(tǒng)。它負責(zé)管理文件的存儲、檢索、更新，提供安全可靠的共享和保護手段，并且方便用戶使用。文件系統(tǒng)的組成n與文件管理有關(guān)的軟件n被管

5、理的文件n實施文件管理所需要的數(shù)據(jù)結(jié)構(gòu)2. 文件與文件系統(tǒng)（2）文件系統(tǒng)從系統(tǒng)角度n負責(zé)為用戶建立文件n存入、讀出、修改、轉(zhuǎn)儲文件、控制文件的存取n撤消文件為用戶帶來的好處n使用的方便性n數(shù)據(jù)的安全性n接口的統(tǒng)一性2. 文件與文件系統(tǒng)8.1 文件系統(tǒng)的概念3.文件的分類按文件性質(zhì)和用途分類（1）系統(tǒng)文件n系統(tǒng)軟件的文件，用戶通過系統(tǒng)調(diào)用或系統(tǒng)提供的專用命今來執(zhí)行，不允許對其進行讀寫和修改n主要有操作系統(tǒng)核心和各種系統(tǒng)應(yīng)用程序或?qū)嵱霉ぞ叱绦蚝蛿?shù)據(jù)組成n例如，,3.文件的分類（2）庫文件n允許用戶進行讀取和執(zhí)行，不允許對其進行修改，主要由各種標(biāo)準(zhǔn)子程序庫組成例如，C語言、FORTRAN子程序庫存放

6、在子目錄下 *.LIB,/lib/,/usr/lib/（3）用戶文件n用戶委托文件系統(tǒng)保存的文件n該類文件只由文件的所有者或授權(quán)者使用n主要由用戶的源程序等組成例如，*.c，*.for，*.f，*DBF，*.OBJ3.文件的分類n按文件的組織形式分類（1）普通文件(常規(guī)文件) n是指組織格式為系統(tǒng)中所規(guī)定的最一般格式的文件，例如由字符流組成的無結(jié)構(gòu)文件（2）目錄文件n是由文件的目錄信息構(gòu)成的特殊文件，便于操作系統(tǒng)統(tǒng)一管理（3）特殊文件（設(shè)備驅(qū)動程序）n輸入輸出外部設(shè)備被看作特殊文件，便于統(tǒng)一管理n操作系統(tǒng)把對特殊文件的操作轉(zhuǎn)入到對相應(yīng)設(shè)備的操作3.文件的分類n按文件的保護方式分類只讀文件讀寫文

7、件不保護文件n按文件信息的流向分類輸入文件輸出文件輸入輸出文件8.2 文件的邏輯結(jié)構(gòu)與存取方法n用兩種不同的觀點來研究文件結(jié)構(gòu)用戶觀點n研究用戶“思維”中的抽象文件，或稱邏輯文件n研究的側(cè)重點在于：為用戶提供一種邏輯結(jié)構(gòu)清晰、使用簡便的邏輯文件形式。用戶將按照這種形式去存儲、檢索和加工有關(guān)文件中的信息。實現(xiàn)觀點（系統(tǒng)觀點）n研究駐留在設(shè)備“介質(zhì)”中的實際文件，或稱物理文件n研究的側(cè)重點是選擇一些工作性能良好、設(shè)備利用率高的物理文件形式。系統(tǒng)將按照這種形式同外部設(shè)備打交道并控制信息的傳輸。8.2 文件的邏輯結(jié)構(gòu)與存取方法n文件的組織有兩種文件的邏輯結(jié)構(gòu)n文件的邏輯結(jié)構(gòu)是指用戶思維中的文件結(jié)構(gòu)。即

8、從用戶的角度來看文件的組織結(jié)構(gòu)。文件的物理結(jié)構(gòu)n文件的物理結(jié)構(gòu)是指文件在存儲介質(zhì)上的結(jié)構(gòu)（或組織）n目前，文件的存儲介質(zhì)主要是磁盤和光盤，包括硬盤、U盤、光盤、磁帶，早期還有磁鼓。由于目前的磁帶是模擬磁盤的結(jié)構(gòu)，所以文件的物理結(jié)構(gòu)主要是指磁盤上文件的結(jié)構(gòu)8.2.1 邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是用戶可見結(jié)構(gòu)分類n字符流式的無結(jié)構(gòu)文件n記錄式的有結(jié)構(gòu)文件8.2 文件的邏輯結(jié)構(gòu)與存取方法n選取文件的邏輯結(jié)構(gòu)應(yīng)遵循的原則當(dāng)進行修改操作時，應(yīng)盡量減少對已存儲好信息的變動當(dāng)進行操作時，查找所需記錄或基本信息單位的時間應(yīng)盡可能短應(yīng)使文件信息占據(jù)最小的存儲空間便于用戶操作8.2.1 邏輯結(jié)構(gòu)n字符流式的無結(jié)構(gòu)文件

9、構(gòu)成文件的基本單位是字符流式文件是有邏輯意義的、無結(jié)構(gòu)的一串字符的集合優(yōu)點：提供很大的靈活性適用：對基本信息單位操作不多的文件例如，源程序文件、目標(biāo)代碼文件，在UNIX、DOS、WINDOWS系統(tǒng)中的普通文件都是流式文件。8.2.1 邏輯結(jié)構(gòu)n記錄式的有結(jié)構(gòu)文件記錄：是一個具有特定意義的信息單位，它由該記錄在文件中的邏輯地址與記錄名所對應(yīng)的一組關(guān)鍵字、屬性及其屬性值組成。可按順序編號為記錄1，記錄2，記錄n例如，職工登記表文件 xsdjb.dbf姓名 性別 出生年月 工資 通信地址 郵政編碼李銘 男 1962年2月 3560元 武昌關(guān)山街125號 430074司馬樂 男 1981年3月 180

10、0元 北京海軍路88號 1000348.2.1 邏輯結(jié)構(gòu)圖8.2 記錄組成例n記錄式的有結(jié)構(gòu)文件文件是由若干個記錄組成，記錄可按各種不同的方式排列，構(gòu)成不同的邏輯結(jié)構(gòu)，以便用戶按鍵或記錄進行修改、查找和管理等記錄式文件是有結(jié)構(gòu)的，如果文件中所有記錄的長度都相同，則這種文件為定長記錄文件文件長度定長記錄文件的長度 = 記錄個數(shù)記錄長度變長記錄文件的長度為各記錄長度之和8.2.1 邏輯結(jié)構(gòu)8.2.1 邏輯結(jié)構(gòu)n兩種文件的比較流式文件就像給用戶一張白紙，用戶可將信息任意地寫到紙上，沒有任何格式上的限制。記錄式文件就像給用戶一張表格，用戶要按表規(guī)定的格式填信息。顯然，結(jié)構(gòu)式文件對用戶的限制很大，使用起

11、來就不方便8.2.1 邏輯結(jié)構(gòu)n常用的記錄式結(jié)構(gòu)文件有以下4種1. 連續(xù)結(jié)構(gòu)連續(xù)結(jié)構(gòu)是一種將記錄按生成的先后順序連續(xù)排列的邏輯結(jié)構(gòu)特點：n適用性強，可用于所有文件，且記錄的排列與記錄的內(nèi)容無關(guān)n搜索性能較差常用的記錄式結(jié)構(gòu)文件2. 多重結(jié)構(gòu)將記錄按關(guān)鍵字和記錄名排列成行列式結(jié)構(gòu)，則一個包含n個記錄名、m個關(guān)鍵字的文件構(gòu)成一個mn維行列式。如圖8.3圖8.3 文件的記錄名和關(guān)鍵字構(gòu)成的行列式常用的記錄式結(jié)構(gòu)文件2. 多重結(jié)構(gòu)將行列式中那些為零的項去掉，并以關(guān)鍵字Ki為隊首，以包含關(guān)鍵字 Ki的記錄為隊列元素來構(gòu)成一個記錄隊列。對于m個關(guān)鍵字，有m個隊列，從而構(gòu)成該文件的多重結(jié)構(gòu)。如圖8.4圖8.

12、4 文件的多重結(jié)構(gòu)常用的記錄式結(jié)構(gòu)文件3.轉(zhuǎn)置結(jié)構(gòu)將含有相同關(guān)鍵字的記錄指針全部指向該關(guān)鍵字。即，把所有與同一關(guān)鍵字對應(yīng)的記錄指針連續(xù)地置于目錄中該關(guān)鍵字的位置下。如圖8.5最適合給定關(guān)鍵字后的記錄搜索圖8.5 文件的轉(zhuǎn)置結(jié)構(gòu)常用的記錄式結(jié)構(gòu)文件4. 順序結(jié)構(gòu)將文件中的關(guān)鍵字按規(guī)定的順序排列起來就形成順序文件結(jié)構(gòu)適用：系統(tǒng)要求按某種優(yōu)先順序來搜索、追加、刪除記錄的情況8.2.2 存取方法n用戶通過對文件的存取來完成對文件的修改、追加、搜索等n文件的存取是要找到文件內(nèi)容所在的邏輯地址n常用的存取方法有以下3類：順序存取法隨機存取法（直接存取法）按關(guān)鍵字存取法順序存取法n順序存取是按照文件的邏輯地

13、址順序依次存取R0R1R2R3RiLLLLLL2L3L4LL(i1)LRptr(a) 定長記錄文件L0R0L1R1RiWptr(b) 變 長記錄文件Li00L0L01L1L0L12Li(Lk1)i1k0(Lk1)ik0順序存取法n定長記錄 讀指針rptr指向下一次讀出的記錄地址 寫指針wptr指向下一次寫入的記錄地址 讀完指針做相應(yīng)修改： rptr+L=rptr 寫完指針做相應(yīng)修改： wptr+L=wptrn變長記錄每次將讀寫指針加上Li，Li是剛讀或?qū)懲甑挠涗浀拈L度讀完指針做相應(yīng)修改： rptr+Li=rptr寫完指針做相應(yīng)修改： wptr+Li=wptr隨機存取法n隨機存取法允許用戶按任意

14、順序存取文件中的任何一個物理記錄，可以根據(jù)記錄的編號來直接存取文件中的任意一個記錄，或者是根據(jù)存取命令把讀寫指針移到欲讀寫處來讀寫。nUNIX、MS-DOS等操作系統(tǒng)都采用順序存取和隨機存取等兩種方法。隨機存取法n定長記錄的順序文件，第i個記錄的首地址為：Rptraddr i L 其中，addr是該文件的首地址，L為記錄長度。n變長記錄的文件，通常采用索引文件的方式組織，由于索引表本身是定長的，也可以采用同樣的方法，先用直接存取法在索引表中找，再找到具體對應(yīng)的地址。 按關(guān)鍵字存取法n按關(guān)鍵字存取法實質(zhì)上是隨機存取法隨機存取法，它不是根據(jù)記錄編號或地址來存取，而是根據(jù)給定的關(guān)鍵字或記錄名進行的。

15、n按關(guān)鍵字存取法首先搜索到要進行存取的記錄的邏輯位置，再經(jīng)過某種方法計算處理，轉(zhuǎn)換成相應(yīng)的物理地址后進行存取。n它被廣泛用于現(xiàn)代操作系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)中的數(shù)據(jù)查找。 按關(guān)鍵字存取的搜索方法n對文件進行搜索的目的：查找出特定記錄所對應(yīng)的邏輯地址，以便將其轉(zhuǎn)換為相應(yīng)的物理地址，實現(xiàn)對文件的操作n對文件的搜索包括：關(guān)鍵字的搜索：在用戶給定所要搜索的關(guān)鍵字和記錄之后，確定該關(guān)鍵字在文件中的位置；記錄的搜索：在搜索到所要查找的關(guān)鍵字之后，在含有該關(guān)鍵字的所有記錄中查找出所需要的記錄。n不同邏輯結(jié)構(gòu)的文件，其搜索方法和效率是不同的對指定記錄Ri的搜索過程如圖8.6所示 圖8.6 記錄 Ri的搜索過程按關(guān)

16、鍵字存取的搜索方法n對關(guān)鍵字或記錄的搜索屬于表格搜索，搜索算法大致分為3種類型：線性搜索法(linear search)散列法(hash coding)二分搜索法(binary search algorithm)按關(guān)鍵字存取的搜索方法n線性搜索法是一種最簡單、直觀的搜索方法方法：從第一個關(guān)鍵字或記錄開始，依次和所要搜索的關(guān)鍵字或記錄比較，直到找到所需要的記錄為止搜索時間：與所搜索的表格大小的1/2成正比搜索效率低按關(guān)鍵字存取的搜索方法n散列法被廣泛用于現(xiàn)代操作系統(tǒng)的數(shù)據(jù)查找核心思想：定義一個散列函數(shù)h(k)，對于給定的關(guān)鍵字k，散列函數(shù)h(k)將其變換為 k所對應(yīng)的邏輯地址。按關(guān)鍵字存取的搜索

17、方法n散列沖突：散列沖突：兩個不同的輸入值變換到同一地址的問題即 對于k1!=k2，有h(k1)=h(k2)=An解決散列沖突的方法：多次散列搜索法 隨機數(shù)法平方散列函數(shù)法 按關(guān)鍵字存取的搜索方法n二分搜索法首先需要將搜索對象按一定順序排列搜索效率較高搜索過程如圖8.7圖8.7 二分搜索法的搜索過程 8.3 文件的物理結(jié)構(gòu)與存儲設(shè)備n對文件的存取，首先搜索到操作對象記錄或某段字符流信息的邏輯地址，然后將邏輯地址轉(zhuǎn)換成相應(yīng)的物理地址，再對物理地址的有關(guān)信息進行操作n文件的存取方法和邏輯結(jié)構(gòu)，實際上與物理存儲介質(zhì)有關(guān)8.3.1 文件的物理結(jié)構(gòu)n物理塊與邏輯塊在文件系統(tǒng)中，文件的存儲設(shè)備通常劃分為若

18、干大小相等的物理塊，每塊長度為512字節(jié)或1024字節(jié)。同時，也將文件信息劃分成相同大小的邏輯塊，所有塊統(tǒng)一編號。以塊為單位進行信息的存儲、傳輸、分配8.3.1 文件的物理結(jié)構(gòu)n物理結(jié)構(gòu)：指一個文件在外存上的存放方法，是從系統(tǒng)的角度來看文件。n采用不同的外存分配方式時，將形成不同的文件物理結(jié)構(gòu)。例如，采用連續(xù)分配方式時的文件物理結(jié)構(gòu)，將形成順序式的文件結(jié)構(gòu)采用鏈接分配方式時的文件物理結(jié)構(gòu)，將形成鏈接式文件結(jié)構(gòu)采用索引分配方式時的文件物理結(jié)構(gòu)，將形成索引式文件結(jié)構(gòu)n連續(xù)文件：將一個在邏輯上連續(xù)的文件信息依次存放在若干連續(xù)的物理塊中1. 連續(xù)文件圖8.8 連續(xù)文件結(jié)構(gòu)n優(yōu)點簡單、支持順序存取和隨機

19、存取順序存取速度快所需的磁盤尋道次數(shù)和尋道時間最少n 缺點文件不能動態(tài)增長，需要預(yù)留足夠空間不利于文件插入和刪除外部碎片問題、存儲壓縮技術(shù)1. 連續(xù)文件n串聯(lián)文件：一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊2. 串聯(lián)文件圖8.9 串聯(lián)文件的物理結(jié)構(gòu)2. 串聯(lián)文件存儲器FCB首記錄01234n優(yōu)點提高了磁盤空間利用率，不存在外部碎片問題有利于文件插入和刪除有利于文件動態(tài)擴充n缺點存取速度慢，不適于隨機存取可靠性問題，如指針出錯更多的尋道次數(shù)和尋道時間鏈接指針占用一定的空間2. 串聯(lián)文件n索引文件：文件信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個文件建

20、立一張索引表，表中每一欄目指出文件信息所在的邏輯塊號和與之對應(yīng)的物理塊號（類似頁表） n索引表的物理地址：由文件說明信息項給出3. 索引文件圖8.10 索引文件示意圖 012345678910111213141516171819202122232425262728293031文件名 索引表地址文件說明信息Jeep 19 916 11025 -1 -1 -119單級索引分配單級索引文件n索引表組織按串聯(lián)方式存放：一個盤塊一個索引表，多個索引表鏈接起來多重索引：將一個大文件的所有索引表（二級索引)的地址放在另一個索引表（一級索引)中。這樣單個索引表可以定長，利于實現(xiàn)3. 索引文件多重索引結(jié)構(gòu)圖8.

21、11 多重索引結(jié)構(gòu)n混合索引分配：指將多種索引分配方式相結(jié)合而形成的一種分配方式例如，系統(tǒng)既采用了直接地址，又采用了一級索引分配方式，或兩級索引分配方式，甚至還采用了三級索引分配方式。 混合索引分配混合索引分配混合索引分配混合索引分配例，假如每個盤塊的大小為4KB，則n直接地址：iaddr(0)iaddr(9) 這10個直接地址項支持的文件最大為：4KB10=40KBn一次間接地址：iaddr(10)地址項可存放1K個盤塊號，因而允許文件長達： 1K 4KB40KB4MB n二次間接地址：iaddr(11) 地址項可存放：1K 1K=1M個盤塊號，允許的文件長度為：1M 4kB 4MB 4Bn

22、三次間接地址：同理地址項iaddr(12) 允許的文件最大長度可達4TBnUNIX文件系統(tǒng)采用的是多重索引結(jié)構(gòu)每個文件的索引表為13個索引項，每項2個字節(jié)直接尋址：最前面10項直接存放文件信息的物理塊號一次間接尋址：如果文件大于10塊，則利用第11項指向一個物理塊，該塊中最多可放256個文件物理塊的塊號二次和三次間接尋址：對于更大的文件還可利用第12和第13項作為二次和三次間接尋址nUNIX中采用了三級索引結(jié)構(gòu)后，文件最大可達8兆個物理塊。 采用這樣的結(jié)構(gòu)即使文件非常大，其索引表也只有40字節(jié)對小/中型文件，可采用直接索引或一次間接索引3. 索引文件混合索引分配例，假如每個盤塊的大小為512B

23、，則n直接地址：iaddr(0)iaddr(9) 這10個直接地址項支持的文件最大為： 512B 10=5120B=5KBn一次間接地址：iaddr(10)地址項可存放256個盤塊號，因而允許文件長達： 256 512B5KB=133KB n二次間接地址：iaddr(11) 地址項可存放：256 256=64KB個盤塊號，允許的文件長度為：64KB 512B 133KB =32901KB32MBn三次間接地址：同理地址項iaddr(12) 允許的文件最大長度可達：256 256 256 512B 256 256 512B 256 512B 5KB =8GB 32MB 128KB+5KBn優(yōu)點：

24、保持了鏈接結(jié)構(gòu)的優(yōu)點，又解決了其缺點既能順序存取,又能隨機存取滿足了文件動態(tài)增長、插入刪除的要求也能充分利用外存空間n缺點索引表本身帶來了系統(tǒng)開銷，如內(nèi)外存空間，存取時間較多的尋道次數(shù)和尋道時間3. 索引文件8.3.2 文件存儲設(shè)備n常用的存儲設(shè)備有磁盤、光盤、磁帶等1. 順序存取設(shè)備磁帶是最典型的順序存取設(shè)備順序存取設(shè)備n前面的物理塊被存取訪問之后，才能存取后續(xù)的物理塊的內(nèi)容n存取速度較慢：主要用于后備存儲，或存儲不經(jīng)常用的信息，或用于傳遞數(shù)據(jù)的介質(zhì)圖8.12 磁帶的結(jié)構(gòu)8.3.2 文件存儲設(shè)備2. 直接（隨機）存取設(shè)備磁盤是最典型的直接存取設(shè)備允許文件系統(tǒng)存取磁盤上任一物理塊，其存取時間不

25、依賴于該物理塊所處的位置 圖8.13 磁盤的結(jié)構(gòu)n信息記錄在磁道上，多個盤片，正反兩面都用來記錄信息，每面一個磁頭n柱面：所有盤面中處于同一磁道號上的所有磁道組成一個柱面n物理地址形式：磁頭號（盤面號）磁道號（柱面號）扇區(qū)號n磁盤系統(tǒng)：由磁盤本身和驅(qū)動控制設(shè)備組成，實際存取讀寫的動作過程是由磁盤驅(qū)動控制設(shè)備按照主機要求完成的2. 直接存取設(shè)備磁盤n 一次訪盤請求：讀/寫磁盤地址（設(shè)備號，柱面號，磁頭號，扇區(qū)號）內(nèi)存地址（源/目）n完成過程由三個動作組成：p尋道（時間）：磁頭移動定位到指定磁道p旋轉(zhuǎn)延遲（時間）：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過p數(shù)據(jù)傳輸（時間）：數(shù)據(jù)在磁盤與內(nèi)存之間的實際傳輸2.

26、直接存取設(shè)備磁盤n很多系統(tǒng)允許有些磁盤是可裝卸的 n節(jié)省驅(qū)動設(shè)備成本，增加靈活性和便攜性n硬盤分為兩種：固定頭磁盤：每個磁道設(shè)置一個磁頭，變換磁道時不需要磁頭的機械移動，速度快但成本高移動頭磁盤：一個盤面只有一個磁頭，變換磁道時需要移動磁頭，速度慢但成本低2. 直接存取設(shè)備磁盤n光盤容量大，速度快，價格便宜，但一般不可寫n可讀寫光盤驅(qū)動器價格貴，寫過程很麻煩n光盤的空間結(jié)構(gòu)與磁盤類似光盤n容量大，斷電后仍可保存信息，速度較慢，成本較低n由兩部分組成：驅(qū)動部分+存儲介質(zhì)n種類很多n外存空間組織與地址與存取方式非常復(fù)雜nI/O過程方式非常復(fù)雜外存的特點n用戶對外存的使用：讀寫外存數(shù)據(jù)n用戶對外存的

27、要求：方便、效率、安全在讀寫外存時不涉及硬件細節(jié)，使用邏輯地址和邏輯操作存取速度盡可能快，容量大且空間利用率高外存上存放的信息安全可靠，防止來自硬件的故障和他人的侵權(quán)可以方便地共享，動態(tài)擴縮，攜帶拆卸，了解存儲情況和使用情況以盡可能小的代價完成上述要求用戶對外存的要求文件結(jié)構(gòu)、文件存取設(shè)備與存儲法的關(guān)系存儲介質(zhì)存儲介質(zhì)物理結(jié)構(gòu)物理結(jié)構(gòu)存取方式存取方式磁帶磁帶連續(xù)結(jié)構(gòu)連續(xù)結(jié)構(gòu)順序存取順序存取磁盤磁盤連續(xù)連續(xù)鏈接鏈接索引索引順序順序順序順序順序順序隨機隨機 隨機隨機8.4 文件存儲空間管理n文件存儲設(shè)備是分成若干個大小相等的物理塊，并以塊為單位交換信息。n文件存儲空間的管理實質(zhì)上就是空閑塊的組織和

28、管理。需要解決以下問題：如何登記空閑區(qū)的分布情況？如何按需給一個文件分配存儲空間？當(dāng)某一文件或某一部分不再需要保留時，如何收回它所占的存儲空間？8.4 文件存儲空間的管理1. 空閑文件目錄系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑文件目錄，每個空閑區(qū)對應(yīng)于空閑文件目錄中的一個表項，其中包括表項序號、該空閑區(qū)的第一個空閑塊號、該區(qū)的空閑塊個數(shù)等 文件的創(chuàng)建：請求分配存儲空間文件的刪除：釋放存儲空間 類似內(nèi)存分區(qū)管理方法 1. 空閑文件目錄序號第一空白塊號空白塊個數(shù)空閑物理塊號124（2，3，4，5）293（9，10，11）3155（15，16，17，18，19)4n僅當(dāng)有少量的空閑區(qū)時才有較好的效果n

29、如果存取空間中有著大量的小的空閑區(qū)，則空閑表變得很大，效率大為降低n這種分配技術(shù)適用于建立連續(xù)文件 2. 空閑塊鏈n空閑塊鏈：把文件存儲設(shè)備上的所有空閑塊鏈接在一起分配：當(dāng)申請者需要空閑塊時，分配程序從鏈頭開始摘取所需的空閑塊，然后調(diào)整鏈?zhǔn)字羔樆厥眨寒?dāng)回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上n常用的鏈接方法按空閑區(qū)大小順序鏈接的方法按釋放先后順序鏈接的方法成組鏈接法（UNIX文件系統(tǒng)）nUNIX文件存儲空間的管理存儲介質(zhì)：磁盤或磁帶文件卷一個文件卷包括：n0#塊：引導(dǎo)塊，用于引導(dǎo)操作系統(tǒng)n1#塊：資源管理塊（超級塊），用于存放文件卷的資源管理信息，為便于管理在內(nèi)存中有其副本n從2#塊起存放磁

30、盤索引節(jié)點塊，其塊數(shù)由文件系統(tǒng)決定，在索引節(jié)點塊后是一般數(shù)據(jù)塊成組鏈接法UNIX系統(tǒng)n空閑塊的分組所有空閑塊按50塊劃分為一組，組的劃分從后往前劃分每組的第一塊用來存放前一組中各塊的塊號和總塊數(shù)第1組的塊數(shù)為49塊；通常，最后一組不足50塊，其塊號與總塊數(shù)只能放在管理文件存儲設(shè)備用的文件資源表中成組鏈接法圖8.14 成組鏈法的組織100400399301300100300299-202201299-100400399-2013019907999790179007899-78017999-7901空閑盤塊號棧S.free019899空閑塊的成組鏈接法 空閑塊的組織n空閑塊的分配首先，系統(tǒng)在初啟時

31、把文件資源表復(fù)制到內(nèi)存，從而使文件資源表中放有最后一組空閑塊塊號與總塊數(shù)的堆棧進入內(nèi)存，并使得空閑塊的分配與釋放在內(nèi)存進行。堆棧設(shè)置有棧指針Ptr，其初值等于該組空閑塊的總塊數(shù)。當(dāng)申請者提出空閑塊要求n時，按照先進先出原則，分配程序從棧頂取出Ptr所指的空閑塊號，將對應(yīng)的物理塊分配，然后棧指針下移一格，即Ptr Ptr 1。這過程一直持續(xù)，直到所要求的n塊都已分配或堆棧中只剩下最后一個空閑塊的塊號。成組鏈接法n空閑塊的分配當(dāng)堆棧中只剩下最后一個空閑塊號時，該盤塊號所對應(yīng)的盤塊中記有下一組可用的盤塊號與總塊數(shù)。因此，系統(tǒng)將啟動設(shè)備管理程序， 將該塊的內(nèi)容讀入內(nèi)存之后將該塊分配給申請者。然后，系統(tǒng)

32、重新設(shè)置Ptr指針，并繼續(xù)為申請者進程分配空閑塊。成組鏈接法成組鏈接法n空閑塊的釋放在回收時，回收程序先做Ptr Ptr 1操作，然后把回收的物理塊號放入當(dāng)前指針Ptr所指的位置。如果Ptr等于50，則表示該組已經(jīng)回收結(jié)束。此時，如果還有新的物理塊需要回收，則回收該塊并啟動I/O設(shè)備管理程序，把回收的50個塊號與塊數(shù)寫入新回收的塊中。然后，將指針Ptr重新置為1，另起一個新組。成組鏈接法舉例1、某系統(tǒng)磁盤空間使用“空閑塊成組鏈接法”進行管理（每組50塊）（1）通過圖1所示的當(dāng)前狀態(tài)，為某文件分配4個空閑塊。請寫出該文件分配到的磁盤塊號，并圖示出分配后有關(guān)物理塊的內(nèi)容及相互關(guān)系。（2）要刪除某文

33、件，可回收5個物理塊89、90、123、137、138。結(jié)合圖2，給出回收后的有關(guān)表格和磁盤塊結(jié)構(gòu)圖。圖1 分配前超級塊與物理塊示意圖圖2 回收前超級塊示意圖答：（1）該文件分配了94、95、115、116四個物理塊。3. 位示圖系統(tǒng)建立一張位示圖，以反映整個存儲空間的分配情況用二進制位反映磁盤空間的分配, 每個物理塊對應(yīng)一位， 1表示對應(yīng)的物理塊已分配，0表示其對應(yīng)的塊未分配分配：申請物理塊時，可以在位示圖中查找為0的位，返回對應(yīng)物理塊號回收：歸還時，將物理塊所對應(yīng)的位置為0 3. 位示圖位示圖 8.5 文件目錄管理n建立文件系統(tǒng)的作用在于：對文件信息實現(xiàn)“按名存取”，力求查找簡便，減少查找

34、時間n一般，采用文件目錄的方法來管理文件，每個文件有一個目錄項n文件的目錄：也稱為文件說明信息，包括文件名以及對該文件實施控制管理的控制管理信息n利用文件目錄，實現(xiàn)對文件的創(chuàng)建、檢索、維護等n對文件目錄的管理就是對文件說明信息的管理8.5 文件目錄管理8.5.1 文件的組成一個文件包括兩部分：文件體和文件說明文件說明：也稱為文件控制塊FCB，是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息，是文件存在的標(biāo)志。其內(nèi)容包括：n有關(guān)文件結(jié)構(gòu)的信息n有關(guān)存取控制信息n有關(guān)管理方面的信息8.5.1 文件的組成p文件控制塊（FCB）的主要內(nèi)容：n文件號、用戶名n文件地址、文件長度、

35、文件類型、文件屬性n文件的建立日期、保存期限、最后修改日期、最后訪問日期n文件物理位置信息：如索引表n口令：用于對文件訪問進行驗證n操作限制：如讀、寫、執(zhí)行權(quán)限說明n文件邏輯結(jié)構(gòu)，文件物理結(jié)構(gòu)n共享說明（UNIX中是與操作限制一起說明）8.5.1 文件的組成文件目錄：把所有的FCB組織在一起，就構(gòu)成了文件目錄，即文件控制塊的有序集合目錄項：構(gòu)成文件目錄的項目(目錄項就是FCB)目錄文件：為了實現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件文件系統(tǒng)利用目錄文件完成按名存取和對文件信息的共享與保護8.5.1 文件的組成n對目錄管理的要求： (1) (1) 實現(xiàn)實現(xiàn)“

36、按名存取按名存取” ” (2) (2) 提高對目錄的檢索速度提高對目錄的檢索速度 (3) (3) 文件共享文件共享 (4) (4) 允許文件重名允許文件重名8.5.2 文件目錄n單級目錄文件系統(tǒng)為存儲設(shè)備的所有文件建立一張目錄表，每個文件在其中占有一項用來存放文件說明信息。該目錄表存放在存儲設(shè)備的固定區(qū)域，在系統(tǒng)啟動或需要時，系統(tǒng)將其調(diào)入內(nèi)存或部分調(diào)入內(nèi)存。文件系統(tǒng)通過對該表提供的信息實現(xiàn)文件的增、刪等操作。每建立一個新文件即在目錄中增加一個FCB，每當(dāng)刪除一個文件即刪除對應(yīng)的FCB，當(dāng)要訪問一個文件時，先按文件名在目錄中找到對應(yīng)的文件FCB。 FCB1 FCB2 FCB3 FCBn 文 件1

37、 文 件2 文 件3 文 件n 單級目錄結(jié)構(gòu)示意圖圖8.15 單級目錄的讀寫處理過程單級目錄n優(yōu)點簡單，能實現(xiàn)目錄管理的基本功能按名存取n 缺點查找速度慢不允許重名 不便于實現(xiàn)文件共享8.5.2 文件目錄n二級目錄目錄分為兩級：n一級目錄：稱為主文件目錄MFD，給出用戶目錄的名字、目錄大小及其所在的物理位置等n二級目錄：稱為用戶文件目錄UFD（又稱用戶子目錄），給出該用戶所有文件的FCB圖8.16 二級目錄結(jié)構(gòu) 二級目錄n二級目錄結(jié)構(gòu)實現(xiàn)可以把主目錄和二級用戶目錄放于外存頭部，也可以把二級目錄當(dāng)一般文件存放。路徑名：將用戶名與文件名連到一起組成路經(jīng)名。例如，/luoyu/test.c。n優(yōu)點解

38、決了文件的重名問題和文件共享問題用戶名文件名查找時間降低n缺點增加了系統(tǒng)開銷多級目錄n多級樹型目錄結(jié)構(gòu)任何一級目錄中的FCB既可以描述次一級的子目錄，又可以描述一個文件。特點：n利于文件分類，從文件路徑名可看出文件類別；n查找文件FCB耗費時間，要得到文件FCB，必須從根查起；n惟一確定文件的路徑名太長，故引入當(dāng)前目錄概念，提供相對于當(dāng)前目錄的相對路徑名可加速文件FCB的查找，進程控制塊存有當(dāng)前目錄信息。圖8.17 文件系統(tǒng)的樹形結(jié)構(gòu) 多級目錄n絕對路徑和相對路徑絕對路徑：從根目錄開始到達文件的路徑相對路徑：從當(dāng)前目錄開始到達文件的路徑n為了提高文件檢索速度，文件系統(tǒng)向用戶提供了一個當(dāng)前正在使

39、用的目錄，稱為當(dāng)前目錄。n查找一個文件可從當(dāng)前目錄開始，使用部分路徑名；當(dāng)前目錄可根據(jù)需要任意改變。n當(dāng)前目錄一般存放在內(nèi)存多級目錄n優(yōu)點層次結(jié)構(gòu)清晰，便于管理和保護解決重名問題查找速度加快n缺點查找一個文件按路徑名逐層檢查，由于每個文件都放在外存，多次訪盤影響速度8.5.3 便于共享的文件目錄n文件共享一個文件被多個用戶或程序使用，形式有n被多個用戶使用，由存取權(quán)限控制n被多個程序使用，但各用自己的讀寫指針n被多個程序使用，但共享讀寫指針目的n節(jié)省時間和存儲空間，減少了用戶工作量；n進程間通過文件交換信息8.5.3 便于共享的文件目錄n實現(xiàn)文件共享的3種方法：繞道法鏈接法基本文件目錄表BFD

40、 繞道法n繞道法：要求每個用戶處在當(dāng)前目錄下工作，用戶對所有文件的訪問都是相對于當(dāng)前目錄進行的。圖8.18 繞道法繞道法要繞彎路訪問多級目錄，因此搜索效率低。鏈接法n鏈接法：在相應(yīng)目錄表之間進行鏈接。即將一個目錄中的鏈接指針直接指向被共享文件所在的目錄。n需要用戶指定被共享的文件和被鏈接的目錄基本文件目錄表BFDn基本文件目錄表 該方法將所有文件目錄的內(nèi)容分成兩部分：基本文件目錄表(BFD)：包括文件的結(jié)構(gòu)信息、物理塊號、存取控制和管理信息等，并由系統(tǒng)賦予惟一的內(nèi)部標(biāo)識符來標(biāo)識。符號文件目錄表(SFD)：由用戶給出的符號名和系統(tǒng)的內(nèi)部標(biāo)識符組成。圖8.19 采用基本文件目錄表實現(xiàn)共享8.5.4

41、 目錄管理n目錄文件存放在文件存儲設(shè)備中，因此存取一個文件時，必須訪問多級目錄。n實現(xiàn)方法將當(dāng)前正在使用的那些文件的目錄表復(fù)制到內(nèi)存中打開文件(fopen)：將文件存儲設(shè)備中的目錄文件復(fù)制到內(nèi)存的操作，稱為打開文件刪除文件(fclose)：將刪除文件的內(nèi)存副本的操作稱為關(guān)閉文件對于按BDF和SFD方式排列的多級目錄文件，系統(tǒng)打開文件的方式如下： 將主目錄MFD中的相應(yīng)表目，即與待打開文件相聯(lián)系的有關(guān)表目復(fù)制到內(nèi)存。 根據(jù)所復(fù)制得到的標(biāo)識符，再復(fù)制此標(biāo)識符所指明的基本文件目錄表BDF的有關(guān)表目。 根據(jù) 所得到的子目錄說明信息搜索SFD，以找到與待打開文件相對應(yīng)的目錄表項。若找到的表目是子目錄名，

42、則繼續(xù)上述復(fù)制，直到找到待打開的文件名。 根據(jù)所搜索到的文件名所對應(yīng)的標(biāo)識符id，將相應(yīng)的BDF的表目項復(fù)制到內(nèi)存。 這樣，待打開文件的說明信息就已復(fù)制到內(nèi)存中。系統(tǒng)便可根據(jù)其信息實現(xiàn)對文件的有關(guān)操作。8.6 文件存取控制n文件的存取控制：與文件的共享、保護、保密不同，但又緊密相關(guān)的問題文件共享：不同的用戶共同使用一個文件文件保護：防止文件的擁有者或其他用戶破壞文件內(nèi)容文件保密：未經(jīng)文件擁有者許可，任何用戶不得訪問該文件 這三個問題實際上是一個用戶對文件的使用權(quán)限問題，即讀、寫、執(zhí)行的許可權(quán)問題。8.6 文件存取控制n文件系統(tǒng)的存取控制部分應(yīng)實現(xiàn)：對于擁有讀、寫或執(zhí)行權(quán)限的用戶，應(yīng)讓其對文件進行相應(yīng)的操作對于沒有讀、寫或執(zhí)行權(quán)限的用戶，應(yīng)禁止他們對文件進行相應(yīng)的操作應(yīng)防止一個用戶冒充其他用戶對文件進行存取應(yīng)防止擁有存取權(quán)限的用戶誤用文件以上功能由存取控制驗證模塊程序?qū)崿F(xiàn)8.