【2012】第六章--文件管理-----計(jì)算機(jī)操縱系統(tǒng)--計(jì)算機(jī)科學(xué)與技術(shù)-操作系統(tǒng)-it

1、第六章 文件管理,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 馮霞,引言,所有的計(jì)算機(jī)應(yīng)用程序都要：存儲信息，檢索信息三個(gè)基本要求：能夠存儲大量的信息長期保存信息可以共享信息解決方法：把信息以一種單元，即文件的形式存儲在磁盤或其他外部介質(zhì)上文件是通過操作系統(tǒng)來管理的，包括：文件的結(jié)構(gòu)，命名，存取，使用，保護(hù)和實(shí)現(xiàn)方法,計(jì)算機(jī)為什么需要文件？數(shù)量原因——內(nèi)存無法保存大量信息時(shí)間原因——內(nèi)存無法永久保存信息應(yīng)用原因——內(nèi)存無法方便實(shí)現(xiàn)共享,

2、兩種觀點(diǎn),用戶觀點(diǎn)：文件系統(tǒng)如何呈現(xiàn)在其面前：一個(gè)文件由什么組成，如何命名，如何保護(hù)文件，可以進(jìn)行何種操作等等操作系統(tǒng)觀點(diǎn)：文件目錄怎樣實(shí)現(xiàn)，怎樣管理存儲空間，文件存儲位置，磁盤實(shí)際運(yùn)作方式(與設(shè)備管理的接口)等等文件系統(tǒng)的作用為應(yīng)用程序提供邏輯抽象（虛擬機(jī)）為磁盤空間提供管理機(jī)制（資源管理器）,負(fù)責(zé)管理在外存上的文件為操作系統(tǒng)和用戶提供給對文件的存取、共享和保護(hù)等手段方便用戶保證文件的安全性有效地提高系統(tǒng)資源的利用

3、率,操作系統(tǒng)中的文件管理功能(即文件系統(tǒng)）,文件系統(tǒng)概述,,,,數(shù)據(jù)文件,磁盤空間,映 射,,應(yīng)用層觀點(diǎn)：邏輯抽象,物理層觀點(diǎn)：空間管理,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結(jié)構(gòu) 6.3 外存分配方式 6.4 目錄管理 6.5 文件存儲空間的管理 6.6 文件共享與文件保護(hù) 6.7 數(shù)據(jù)一致性控制,第六章 文件管理,1.文件是存儲在外部介質(zhì)上數(shù)據(jù)的集合。 譚浩強(qiáng),《C程序設(shè)計(jì)》p268.2.文件是大量性質(zhì)相同

4、的記錄組成的集合。 嚴(yán)蔚敏,《數(shù)據(jù)結(jié)構(gòu)》p306.3.文件是按一定的格式組織起來的，存儲在計(jì)算機(jī)系統(tǒng)中特定的外部存儲介質(zhì)上（如磁盤、光盤）的命名的數(shù)據(jù)的集合。 林鈞海,《C程序設(shè)計(jì)課件》,13章文件4.文件是具有文件名的一組相關(guān)元素的集合。 湯小丹，《計(jì)算機(jī)操作系統(tǒng)》p204,什么是文件？,文件是有文件名的若干相關(guān)元素的集合，元素通常是記錄，而記錄是一組有意義的數(shù)據(jù)項(xiàng)的集合。數(shù)據(jù)項(xiàng)描述一個(gè)對象的某種屬性的字符集，是數(shù)

5、據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱為字段。記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對象某方面的屬性。能唯一地標(biāo)識一個(gè)記錄的一個(gè)項(xiàng)或幾個(gè)項(xiàng)稱為關(guān)鍵字(key)。,6.1 文件和文件系統(tǒng),文件：是具有文件名的一組相關(guān)信息的集合。可分為：文件屬性：文件名、文件類型、文件長度、文件的物理位置、文件的存取控制、文件的建立時(shí)間。,常見的文件屬性及其含義,保護(hù)：誰可以存取文件、以什么方式存取文件口令：存取文件需

6、要的口令創(chuàng)建者：文件的創(chuàng)建者ID所有者：當(dāng)前所有者只讀標(biāo)志：0表示讀/寫；1表示只讀隱藏標(biāo)志：0表示正常；1表示不在列表中顯示系統(tǒng)標(biāo)志：0表示普通文件；1表示系統(tǒng)文件存檔標(biāo)志：0表示已經(jīng)備份；1表示需要備份ASCII/二進(jìn)制標(biāo)志：0表示ASCII文件；1表示二進(jìn)制文件隨機(jī)存取標(biāo)志：0表示只允許順序存?。?表示隨機(jī)存取臨時(shí)標(biāo)志：0表示正常；1表示進(jìn)程退出時(shí)刪除文件加鎖標(biāo)志：0表示未加鎖；1表示已加鎖記錄長度：1個(gè)記錄

7、中的字節(jié)數(shù)鍵的位置：每個(gè)記錄中鍵的偏移量鍵的長度：鍵字段的字節(jié)數(shù)創(chuàng)建時(shí)間：文件創(chuàng)建的日期和時(shí)間最后一次存取時(shí)間：文件上一次存取的日期和時(shí)間最后一次修改時(shí)間：文件上一次修改的日期和時(shí)間當(dāng)前大小：文件的字節(jié)數(shù)最大長度：文件可能增長到的字節(jié)數(shù),圖 文件、 記錄和數(shù)據(jù)項(xiàng)之間的層次關(guān)系,6.1.2 文件類型和文件系統(tǒng)模型,1、文件的類型,按文件性質(zhì)和用途分類系統(tǒng)文件：有關(guān)OS及有關(guān)系統(tǒng)所組成文件用戶文件：用戶的程序和數(shù)據(jù)等文

8、件庫文件：標(biāo)準(zhǔn)子程序及常用應(yīng)用程序組成文件，允許用戶使用但不能修改,1、文件的類型,按文件中的數(shù)據(jù)形式分源文件、目標(biāo)文件、可執(zhí)行 按存取控制屬性分只執(zhí)行文件、只讀文件、讀寫文件 按文件的邏輯結(jié)構(gòu)分結(jié)構(gòu)文件和無結(jié)構(gòu)文件 按組織形式和處理方式分普通文件、目錄文件、特殊文件,2、文件系統(tǒng)模型,文件系統(tǒng)是操作系統(tǒng)中統(tǒng)一管理信息資源的軟件模塊，負(fù)責(zé)管理文件的存儲、檢索、更新，提供安全可靠的共享和保護(hù)手段，方便用戶的使用,文件系統(tǒng)的

9、模型,文件系統(tǒng)是OS的重要組成部分。文件系統(tǒng)的模型：分為三個(gè)層次，其最低層是對象及其屬性說明；中間層是對對象進(jìn)行操縱和管理的軟件集合，最高層是文件系統(tǒng)提供給用戶的接口。,2、文件系統(tǒng)模型,一、對象及屬性說明文件目錄（方便對文件的存取和檢索）磁盤（磁帶）存儲空間二、文件系統(tǒng)的接口命令接口程序接口：系統(tǒng)調(diào)用,2、文件系統(tǒng)模型,對文件存儲空間的管理對文件目錄的管理用于將文件的邏輯地址轉(zhuǎn)為物理地址的機(jī)制對文件讀和寫的管理對

10、文件的共享與保護(hù),三、對對象操縱和管理的軟件集合,6.1.3 文件操作,,用戶通過文件系統(tǒng)提供的系統(tǒng)調(diào)用實(shí)施對文件的操作。對文件的操作可分為兩大類：一類是對文件自身的操作，例如，創(chuàng)建一個(gè)新文件、刪除一個(gè)老文件、拷貝一個(gè)文件、為文件改名等；另一類是對記錄的操作，例如，檢索一個(gè)文件中的所有記錄；檢索一個(gè)文件中的單個(gè)記錄等。,6.1.3 文件操作,對記錄的操作檢索所有記錄、檢索單個(gè)記錄、插入、修改、刪除一個(gè)記錄最基本的文件操作創(chuàng)建

11、文件、修改文件、讀、寫文件、截?cái)辔募?、設(shè)置文件讀/寫位置文件的打開和關(guān)閉,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結(jié)構(gòu) 6.3 外存分配方式 6.4 目錄管理 6.5 文件存儲空間的管理 6.6 文件共享與文件保護(hù) 6.7 數(shù)據(jù)一致性控制,第六章 文件管理,6.2 文件的邏輯結(jié)構(gòu),文件的邏輯結(jié)構(gòu)：從用戶角度看文件，研究文件的組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于物理特性，又稱為文件組織。文件的物理結(jié)構(gòu)：又

12、稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式，這與存儲介質(zhì)的存儲性能有關(guān)。無論是文件的邏輯結(jié)構(gòu)還是其物理結(jié)構(gòu)，都會影響對文件的檢索速度。,6.2.1 文件邏輯結(jié)構(gòu)的類型,6.2.1 文件邏輯結(jié)構(gòu)的類型,根據(jù)記錄組織方式不同，有結(jié)構(gòu)文件分為以下三類:順序文件索引文件索引順序文件,6.2.2 順序文件,1、邏輯記錄的排序串結(jié)構(gòu)：記錄之間的順序與關(guān)鍵字無關(guān)，通常由時(shí)間決定。不利于查找。順序結(jié)構(gòu)：文件的所有記錄按關(guān)鍵字排列。

13、可以利用有效的查找算法。對順序結(jié)構(gòu)文件可有更高的檢索效率，因?yàn)榭衫糜行У牟檎宜惴?，如折半查找法、插值查找法、跳步查找法等方法來提高檢索效率。,2. 對順序文件(Sequential File)的讀/寫操作,定長和變長記錄文件,順序文件中的記錄可以是定長或變長的。對于定長記錄的順序文件，如果已知當(dāng)前記錄的邏輯地址，便很容易確定下一個(gè)記錄的邏輯地址。在讀一個(gè)文件時(shí)，可設(shè)置一個(gè)讀指針Rptr，令它指向下一個(gè)記錄的首地址，每當(dāng)讀完一個(gè)

14、記錄時(shí)，便執(zhí)行Rptr := Rptr＋L操作，使之指向再下一個(gè)記錄的首地址。其中的L為記錄長度。類似地，在寫一個(gè)文件時(shí)，也應(yīng)設(shè)置一寫指針wptr，使之指向要寫的記錄的首地址。同樣，在每寫完一個(gè)記錄時(shí)，又執(zhí)行以下操作：Wptr := Wptr＋L對于變長記錄的順序文件，在順序讀或?qū)憰r(shí)的情況相似，應(yīng)分別為它們設(shè)置讀或?qū)懼羔?，在每次讀或?qū)懲暌粋€(gè)記錄后，須將讀或?qū)懼羔樇由螸i，即后移一個(gè)相應(yīng)記錄的長度，或說，Li是剛讀或剛寫完的記錄的

15、長度。,3. 順序文件的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：批量存取，效率高缺點(diǎn)：查找或修改單個(gè)記錄，此時(shí)系統(tǒng)須要去逐個(gè)地查找諸記錄。這時(shí)，順序文件所表現(xiàn)出來的性能就可能很差，這同時(shí)也限制了文件長度。想增加或修改一個(gè)記錄，都比較困難,在順序文件中，查找第i個(gè)記錄 定長記錄 Ai=i×L可變長記錄 定長記錄可方便實(shí)現(xiàn)直接存取，變長記錄較難實(shí)現(xiàn)直接存取,6.2.3 索引文件,6.2.3 索引文件,引入：解決變長文件記錄較難直接

16、存取的問題。思路：為變長記錄文件創(chuàng)建一張索引表，索引表是定長記錄文件，檢索時(shí)，先查找索引表，再根據(jù)指針?biāo)傅牡刂纷x取記錄。主文件的每個(gè)記錄，在索引表中設(shè)一個(gè)相應(yīng)表項(xiàng)，記錄該記錄的長度以及指向該記錄的地址。索引表按記錄鍵排序，是定長記錄的順序文件，可方便實(shí)現(xiàn)直接存取。,索引文件的組織,優(yōu)點(diǎn)：檢索速度快缺點(diǎn)：提高了存儲費(fèi)用,6.2.4 索引順序文件,引入：有效克服變長記錄不便于直接存取的缺點(diǎn)，而且所付出的代價(jià)也不大。是順序文件和索引

17、文件結(jié)合的產(chǎn)物。思路：將順序文件的所有記錄分成若干組，為順序文件建立一張索引表，索引表中為每組的第一個(gè)記錄建立一個(gè)索引項(xiàng)，含記錄的鍵和指向記錄的指針。檢索時(shí)，先檢索索引表，找到記錄所在記錄組的第一個(gè)記錄的表項(xiàng)，再順序查找主文件，得到要求的記錄。當(dāng)文件較大時(shí)，可以考慮多級索引。,索引順序文件,6.2.5 直接文件和哈希文件,1 直接文件 可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址鍵值轉(zhuǎn)換(Key to address t

18、ransformation)：由記錄鍵值到記錄物理地址的轉(zhuǎn)換組織直接文件的關(guān)鍵：用什么方法進(jìn)行從記錄值到物理地址的轉(zhuǎn)換,2. 哈希(Hash)文件（散列法）,Hash文件的邏輯結(jié)構(gòu),目前最流行的一種直接文件。它利用Hash函數(shù)進(jìn)行鍵值轉(zhuǎn)換。但為了實(shí)現(xiàn)存儲空間的動態(tài)分配，通常由Hash函數(shù)求得的不是記錄的物理地址，而是指向一目錄表的表目的指針,1 何謂索引順序文件？2 設(shè)F是一級索引順序文件，它包含N個(gè)記錄。試證明檢索到具有指定關(guān)鍵字

19、的記錄的平均查找記錄數(shù)至少為 。3 設(shè)F是二級索引順序文件它包含N個(gè)記錄。試證明檢索到具有指定關(guān)鍵字的記錄的平均查找記錄數(shù)至少為 。 注：參閱p211-212索引順序文件一節(jié)。,思考題或課堂練習(xí),,N,,,x,x,,文件,,,平均檢索次數(shù),,N/x,索引,X個(gè)記錄為一組,,N,,,x,x,,文件,,N/x,,,,y,y,一級索引,二級索引,,設(shè)平均檢索次數(shù)為S則：,得x=y即要使平均檢索次數(shù)達(dá)到最小，則應(yīng)有

20、x=y,,請考慮：1 若是k級索引順序文件(設(shè)記錄數(shù)為N)，檢索到具有指定關(guān)鍵字的記錄的平均查找記錄數(shù)是多少？2 在什么情況下應(yīng)建立多一級的索引順序文件？,對于k級索引順序文件查找指定關(guān)鍵字的記錄在平均查找記錄數(shù)為：,,k-1級索引順序文件查找指定關(guān)鍵字的記錄的平均查找次數(shù)為：,可以看出當(dāng)N充分大時(shí)k級索引才會優(yōu)于k-1級索引。,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結(jié)構(gòu) 6.3 外存分配方式 6.4 目錄管理 6.5

21、 文件存儲空間的管理 6.6 文件共享與文件保護(hù) 6.7 數(shù)據(jù)一致性控制,第六章 文件管理,6.3 外存分配方式,為文件分配外存空間要考慮的主要問題：有效利用外存提高對文件的訪問速度常用的方法：連續(xù)分配、鏈接分配、索引分配文件的物理結(jié)構(gòu)直接與外存分配有關(guān)連續(xù)分配---順序文件鏈接分配---鏈接文件索引分配---索引文件,6.3.1 連續(xù)分配,每一個(gè)文件占用一個(gè)連續(xù)的磁盤塊的集合,從而成為一種物理上的順序文件即把邏

22、輯文件中的記錄順序地存儲到鄰接的各物理塊。鄰接的物理塊一般在同一條磁道上，所以不必移動磁頭這樣形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱為順序文件在目錄項(xiàng)的“文件物理地址”字段中記錄該文件的第一個(gè)記錄所在盤塊號和文件長度,磁盤空間的連續(xù)分配,,如同內(nèi)存的動態(tài)分區(qū)分配一樣，隨著文件建立時(shí)空間的分配和文件回收時(shí)空間的回收，將使磁盤空間分割成許多小塊，形成外存碎片緊湊！,Contiguous File Allocation (Af

23、ter Compaction),優(yōu)點(diǎn)：順序訪問容易、速度快；可以隨機(jī)存取(Random access)缺點(diǎn)：要求連續(xù)的存儲空間。浪費(fèi)空間：幾次動態(tài)存儲分配后就出現(xiàn)零頭問題；緊湊又要花費(fèi)大量機(jī)器時(shí)間必須事先知道文件長度，不能動態(tài)增長，不利于插入刪除適用：簡單應(yīng)用環(huán)境，已知文件數(shù)量和大小,6.3.2 鏈接分配,將一個(gè)邏輯文件存儲到外存時(shí)將文件裝到多個(gè)離散的盤塊中，通過每個(gè)盤塊上的指針將同屬于一個(gè)文件的盤塊鏈成一個(gè)鏈表。這樣形成

24、的物理文件稱為鏈接文件每個(gè)文件是一個(gè)磁盤塊的鏈接列表：塊可以分散在磁盤各處優(yōu)點(diǎn)：采用離散分配消除了外部碎片，顯著提高了外存利用率；當(dāng)文件動態(tài)增長時(shí)，動態(tài)分配盤塊，不需要預(yù)先知道文件的大??；對文件增刪改方便。有兩種形式：隱式鏈接和顯式鏈接,在文件目錄的每一個(gè)目錄項(xiàng)中含有指向鏈接文件第一個(gè)盤塊和最后盤塊的指針，每個(gè)盤塊內(nèi)含有指向下一盤塊的指針。,1. 隱式鏈接,隱式鏈接的缺點(diǎn)：只適合順序訪問，對隨機(jī)訪問低效可靠性差，只要盤塊指針

25、故障，便使整個(gè)鏈斷開每個(gè)盤塊設(shè)一指針，占用較大的空間,為提高檢索速度和減少指針占用磁盤空間：將幾個(gè)盤塊組成一個(gè)簇盤塊分配以簇為單位鏈接文件中每個(gè)元素以簇為單位成倍減少查找指定塊時(shí)間減少指針占用空間增大了內(nèi)部碎片,2. 顯式鏈接,把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表在整個(gè)磁盤僅設(shè)置一張表的序號是物理塊號，從0開始直到N-1，N為盤塊總數(shù)。在每個(gè)表項(xiàng)中存放鏈接指針，即下一個(gè)盤塊號由于分配給文件

26、的所有盤塊號都放在鏈接表中，故把鏈接表稱為文件分配表FAT (File Allocation Table)在鏈接表中，每條鏈的鏈?zhǔn)字羔槍?yīng)的塊號（屬于某一個(gè)文件的第一個(gè)盤塊號）作為文件地址填入相應(yīng)文件的FCB的“物理地址”字段中,4,0,1,2,3,5,,,,,,,,,,FCB,物理塊號,FAT,顯式鏈接結(jié)構(gòu),,MS-DOS的文件物理結(jié)構(gòu) 。實(shí)例是兩個(gè)文件：文件A占用三個(gè)盤塊，文件B也占用三個(gè)盤塊。,9,0,1,2,3,4,5,6,7

27、,8,,,,,,,,,10,11,,,,,,,FCB A,FCB B,FAT,顯式鏈接的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：除了前述鏈接分配的一般優(yōu)點(diǎn)外，還由于FAT表在內(nèi)存，大大提高了檢索速率，減少訪問磁盤次數(shù)缺點(diǎn)：FAT表中每個(gè)盤塊一項(xiàng)，占用大量內(nèi)存,6.3.3 FAT和NTFS技術(shù),1.FAT121）以盤塊為基本分配單位MS-DOS使用FAT12文件系統(tǒng)，將磁盤劃分為四個(gè)“卷”，即磁盤分區(qū)；每個(gè)分區(qū)獨(dú)立保存各自的目錄文件、FAT表和邏輯驅(qū)動

28、器字母；以盤塊為分配單位。,FAT表容量的計(jì)算 假設(shè)1.2MB的軟盤，每個(gè)盤塊大小為512B，則每個(gè)FAT表含 2.4K(=1.2MB/512B)個(gè)表項(xiàng)；由于每個(gè)FAT表項(xiàng)占12位，故FAT表共占用3.6KB(=2.4K*1.5B)的空間,最大磁盤容量的計(jì)算 由于每個(gè)FAT表項(xiàng)為12位，故FAT表最多允許有4096(=212 ) 個(gè)表項(xiàng)； 每個(gè)盤塊為512B，則每個(gè)分區(qū)的容量為2MB；磁盤分為4個(gè)分區(qū)，則磁盤最大容量

29、為8MB。,2）簇的基本概念 一個(gè)簇的大小為盤塊的2n倍，F(xiàn)AT以簇為單位進(jìn)行登記； 對于同樣大小的FAT表，當(dāng)一個(gè)簇包含一個(gè)扇區(qū)時(shí)，磁盤最大容量為8MB；當(dāng)一個(gè)簇包含兩個(gè)扇區(qū)時(shí)，磁盤最大容量為16MB；當(dāng)一個(gè)簇包含八個(gè)扇區(qū)時(shí)，磁盤最大容量為64MB優(yōu)點(diǎn)：適應(yīng)磁盤容量不斷增大缺點(diǎn)：造成更大簇內(nèi)領(lǐng)頭,3）FAT12存在的問題對磁盤容量存在限制；僅支持8+3格式的文件名。,2.FAT16FAT表項(xiàng)增至16位，則FAT表可登記6

30、5536 (=216) 個(gè)簇；每個(gè)簇包含的扇區(qū)數(shù)為4、8、16、32、64。如果是64，則分區(qū)的最大空間為216 *64*512=2048MB；對分區(qū)容量的改善有限，如果增加簇的大小，則使內(nèi)部碎片增大；不支持長文件名；對FAT12的局限性有所改善，但改善有限。,3.FAT32用更多的FAT表項(xiàng)，換取較小的簇；FAT 32可管理232個(gè)簇，每個(gè)簇固定為4KB，則FAT 32分區(qū)最大容量為16TB(= 4KB* 232)；支

31、持長文件名；由于FAT的擴(kuò)大，導(dǎo)致運(yùn)行速度減慢；FAT32不支持容量小于512MB的分區(qū)；單個(gè)文件的大小不能超過4GB；不能向下兼容。,4.NTFS1）NTFS新特征 使用64位磁盤地址，支持264的磁盤分區(qū)； 支持長文件名，文件名小于 255 個(gè)字符，路徑名小于 32767 個(gè)字符； 具有系統(tǒng)容錯功能； 提供了數(shù)據(jù)一致性功能； 提供了文件加密、壓縮等功能。,2）磁盤的組織 以簇作為磁盤分配和回收的基本單位； 卷

32、上簇的大小稱為“卷因子”，由格式化命令確定其大小，其大小是物理磁盤扇區(qū)的整數(shù)倍； 對于簇的定位，采用邏輯簇號LCN和虛擬簇號VCN：LCN：以卷為單位，將整個(gè)卷中的簇按序編號；地址映射時(shí)，用卷因子乘以LCN即可算出物理字節(jié)偏移量；VCN：以文件為單位，將屬于某個(gè)文件的簇按序編號。,3）文件的組織 以卷為單位，將卷中的所有文件信息、目錄信息以及可用空間信息，以文件記錄的形式記錄在一張主控文件表MFT中； 卷中的每個(gè)文件、目錄等在

33、MFT中占一行，每行固定大小1KB，作為文件的元數(shù)據(jù)； 每個(gè)元數(shù)據(jù)所對應(yīng)的文件信息（包括文件內(nèi)容），組織在一組文件屬性中； 超過1KB的部分，存放在其他簇中，通過指針鏈接； 只被windows NT識別，不能向下兼容。,鏈接分配解決了連續(xù)分配的缺陷。但又出現(xiàn)新問題：不能支持高效的直接存取文件分配表FAT占用較大的內(nèi)存空間,6.3.4 索引分配,當(dāng)打開一文件時(shí)不需要把整個(gè)FAT表調(diào)入內(nèi)存，只要把該文件占用的盤塊的編號調(diào)入內(nèi)存，為

34、此：為每一個(gè)文件建立一個(gè)索引塊(表)，存放分配給該文件的所有盤塊號，通常用一專門的盤塊作為索引表。因此，索引塊(表)就是一個(gè)含有許多盤塊號的數(shù)組建立文件時(shí)，在文件目錄的表項(xiàng)中填上指向該索引塊的指針,1. 單級索引分配,索引分配方式,需要索引塊，可能要花費(fèi)較多的外存（一個(gè)盤塊可放成百甚至上千個(gè)盤塊號）可隨機(jī)存?。ㄖ苯釉L問）可以動態(tài)分配而無外部碎片對于小文件采用索引分配方式，其索引塊的利用率極低,2. 多級索引分配,對于大型文件，

35、一個(gè)索引塊可能容納不下所有的盤塊號，則可再分配一個(gè)索引塊繼續(xù)裝入盤塊號，….,直到裝完所有的盤塊號通過鏈指針將各索引塊鏈接起來若文件太大，索引塊很多，效率很低為索引塊再分配一個(gè)索引塊，裝填索引塊的盤塊號。于是形成二級索引分配方式,兩級索引分配,如果每個(gè)盤塊的大小為1KB，每個(gè)盤塊號占4B，則一個(gè)索引塊可放256個(gè)盤塊號。對于二級索引,最多可存放文件的盤塊總數(shù)為N=256?256=64K個(gè)盤塊號,文件的最大長度為64KB ? 1KB

36、=64MB,3. 混合索引分配方式,多種索引分配的組合。如既采用直接地址，又采用一級索引，兩級索引，甚至于三級索引。UNIX System V的索引結(jié)點(diǎn)中共設(shè)13個(gè)地址項(xiàng)，即iaddr(0)~iaddr(12), 把所有的地址分為兩類即直接地址和間接地址。,直接地址。為提高對文件的檢索速度，在索引結(jié)點(diǎn)中可設(shè)10個(gè)直接地址項(xiàng),即iaddr(0)~iaddr(9)存放直接地址。其中每項(xiàng)存放的是該文件數(shù)據(jù)的盤塊號。若每個(gè)盤塊大小為4KB，當(dāng)

37、文件不大于10*4KB=40KB時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部盤塊號一次間接地址。對于大，中型文件，只采用直接地址是不現(xiàn)實(shí)的。為此可再利用索引結(jié)點(diǎn)中的地址項(xiàng)iaddr(10)提供一次間接地址。實(shí)際上是一級索引分配方式。一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個(gè)盤塊號記入其中，在一次間址塊中可存放1K個(gè)盤塊號，因而允許文件長達(dá)4MB,多次間接地址。當(dāng)文件長度大于4MB+40KB時(shí)(一次間址與10個(gè)直接地址)，系統(tǒng)還須采用二

38、次間接地址分配方式。這時(shí)用地址項(xiàng)iaddr(11)提供二次間接地址。實(shí)際上是兩級索引分配方式。系統(tǒng)此時(shí)在二次間址塊中記入所有一次間址塊的盤塊號。在采用二次間址方式時(shí)，文件最大長度可達(dá)4GB。同理，地址項(xiàng)iaddr(12)作為三次間接地址，允許的文件最大長度可達(dá)4TB。,索引表組織形式鏈接方式：用指針將多個(gè)保存索引表的磁盤塊連在一起多級索引：采用兩級或者三級索引機(jī)制，記錄大文件的磁盤空間地址混合模式：I-Node方法，既適應(yīng)小文件

39、，也滿足大文件需求,優(yōu)點(diǎn)分析充分吸收了連續(xù)分配和鏈接分配的優(yōu)點(diǎn)，支持順序存取和隨機(jī)存取可以方便的實(shí)現(xiàn)文件的空間動態(tài)增長，插入刪除的要求充分利用了外存空間，管理過程有很高的效率缺點(diǎn)分析當(dāng)文件的物理空間分布過于分散時(shí)，文件讀取消耗較長的時(shí)間索引表方式占用了較多的系統(tǒng)資源，包括磁盤和內(nèi)存，同時(shí)對操作系統(tǒng)的設(shè)計(jì)要求也很高,文件物理空間分配方式的總結(jié),課堂練習(xí)題,例1：在某FAT16文件系統(tǒng)中，F(xiàn)AT表的每個(gè)表項(xiàng)用16位表示，每簇64

40、扇區(qū)，扇區(qū)的大小為512字節(jié)。有一個(gè)文件，其起始簇號為0002H，如下圖所示。 FAT表中的表目為FFFFH，表示該簇為文件的最后一簇；表目為0000H，表示該簇為空閑蔟。問：(1)該文件占用了多大的磁盤存儲空間？ (2)若要為該文件再分配一蔟，請修改FAT表。(3)該文件的第32769（十進(jìn)制數(shù)）字節(jié)，在哪一簇中？(4)該分區(qū)最大可為多少字節(jié)？其FAT占用多少存儲空間？(5)如果FAT不在內(nèi)存，讀2M字節(jié)大小的文件的最后一個(gè)

41、字節(jié)，最多要讀多少扇區(qū)，最少要讀多少扇區(qū)?,答：（1）由上圖可知，該文件占用了2、4、7簇，共96K字節(jié)。（2）FAT表的0007H蔟的表項(xiàng)中改為0008H，0008H蔟的表項(xiàng)中改為FFFFH（3）32769=32768 + 1，故第32769字節(jié)在0004H簇中。（4）分區(qū)最大為64K*32K=2G FAT表占128K, 256扇區(qū)（5）2M文件占64蔟，當(dāng)蔟號在FAT中連續(xù)，可在一個(gè)扇區(qū)中中，則此時(shí)是最少的情況，只需要讀2

42、扇區(qū)，即讀FAT一個(gè)扇區(qū)，文件最后一個(gè)字節(jié)1個(gè)扇區(qū)；當(dāng)此文件的蔟號在FAT中分散在64個(gè)簇中時(shí)，即最多讀64+1扇區(qū)（讀文件這個(gè)字節(jié)，要讀一扇區(qū)）,例2： UNIX文件系統(tǒng)的采用索引節(jié)點(diǎn)的結(jié)構(gòu)，其文件的物理結(jié)構(gòu)見教材所示，即文件所占用的盤塊號放在該文件的索引結(jié)點(diǎn)的13個(gè)地址頁中，前10個(gè)為直接尋址，后三個(gè)分別為一次間址，二次間址和三次間尋址。假設(shè)盤塊大小為1KB，每個(gè)間址放256個(gè)盤塊地址。問：(1)這種文件系統(tǒng)可存放的最大文件為多少

43、字節(jié)(2)一個(gè)2MB大小的文件，要占用多少磁盤空間(多少盤塊)？注意：占用的磁盤空間包括文件本身和間址塊兩部分。（需說明怎樣得到以上問題的結(jié)果）,(1) 16G+64M+256K+10K(2) 2057,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結(jié)構(gòu) 6.3 外存分配方式 6.4 目錄管理 6.5 文件存儲空間的管理 6.6 文件共享與文件保護(hù) 6.7 數(shù)據(jù)一致性控制,第六章 文件管理,6.4 目錄管理,目錄是一種數(shù)

44、據(jù)結(jié)構(gòu)，它給出系統(tǒng)中每個(gè)文件與其物理位置之間的映射關(guān)系。對目錄管理的要求如下：實(shí)現(xiàn)“按名存取”提高對目錄的檢索速度文件共享允許文件重名,6.4.1 文件控制塊和索引結(jié)點(diǎn),文件控制塊是用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的，存放了為管理文件所需的所有有關(guān)信息（文件屬性），是文件存在的標(biāo)志。文件管理程序借助于文件控制塊中的信息，實(shí)現(xiàn)對文件的各種操作。文件與文件控制塊一一對應(yīng)，把文件控制塊的有序集合

45、稱為文件目錄。一個(gè)文件控制塊就是一個(gè)文件目錄項(xiàng)。通常，一個(gè)文件目錄也被看做是一個(gè)文件，稱為目錄文件。,FCB內(nèi)容,基本信息類：文件名，文件號，用戶名，文件物理地址，文件長度，文件邏輯結(jié)構(gòu)，文件物理結(jié)構(gòu)存取控制信息類使用信息類：文件的建立日期，保存期限，最后修改日期，最后訪問日期，文件類型，文件屬性，共享計(jì)數(shù),MS-DOS的文件控制塊 （32個(gè)字節(jié)）,2. 索引結(jié)點(diǎn),引入：文件目錄通常存放在磁盤上，當(dāng)文件多時(shí)，目錄項(xiàng)可能占用多個(gè)盤塊

46、，查找速度慢，查找需訪問的盤塊多，效率低。解決：查找是按文件名，因此將文件名和文件描述信息分開，分別放在目錄項(xiàng)和索引結(jié)點(diǎn)中，檢索時(shí)，只將目錄項(xiàng)調(diào)入內(nèi)存，找到后，將該項(xiàng)中的索引結(jié)點(diǎn)調(diào)入即可。,磁盤索引結(jié)點(diǎn)（磁盤上，每個(gè)文件一個(gè)）：主要包括：文件主標(biāo)識，文件類型，文件存取權(quán)限，文件物理地址，文件長度，文件連接計(jì)數(shù)，文件存取時(shí)間。內(nèi)存索引結(jié)點(diǎn)（內(nèi)存，從磁盤索引結(jié)點(diǎn)拷入信息）：主要包括：索引結(jié)點(diǎn)編號，狀態(tài)，訪問計(jì)數(shù)，文件所在設(shè)備的邏輯設(shè)

47、備號，鏈接指針。,UNIX的文件目錄,…,…,6.4.2 目錄結(jié)構(gòu),目錄結(jié)構(gòu)的組織，關(guān)系到文件系統(tǒng)的存取速度，也關(guān)系到文件的共享性和安全性,6.4.2 目錄結(jié)構(gòu),1. 單級目錄結(jié)構(gòu),在整個(gè)系統(tǒng)中，為所有文件建立一個(gè)目錄文件(組成一線性表)，每個(gè)文件占一個(gè)目錄項(xiàng)。目錄項(xiàng)中包含以下幾個(gè)數(shù)據(jù)：文件名及擴(kuò)展名、文件的物理地址、文件長度、文件類型等。為表明每個(gè)目錄項(xiàng)是否空閑，設(shè)置一個(gè)狀態(tài)位。,…,單級目錄,創(chuàng)建新文件:查所有目錄項(xiàng)，看新文件

48、名是否唯一；在目錄中去找出一空目錄項(xiàng)；把新文件名、物理地址和其他屬性填入目錄項(xiàng)中，并置狀態(tài)位為1。刪除文件：在目錄中找到該文件的目錄項(xiàng)，從中找到該文件的物理地址，對它們進(jìn)行回收；再清除其所占用的目錄項(xiàng)(置狀態(tài)位為0)。,優(yōu)點(diǎn): 簡單，實(shí)現(xiàn)了按名存取缺點(diǎn):限制了用戶對文件的命名（不允許重名）文件平均檢索時(shí)間長（查找速度慢）限制了對文件的共享適用于單用戶環(huán)境,2. 兩級目錄,為每一個(gè)用戶建立一個(gè)單獨(dú)的用戶文件目錄UFD(Us

49、er File Directory)。它由用戶所有文件的文件控制塊組成。系統(tǒng)中再建立一個(gè)主文件目錄MFD (Master File Directory)；在主文件目錄中，每個(gè)用戶文件目錄都占有一個(gè)目錄項(xiàng)；目錄項(xiàng)中包括用戶名和指向該用戶目錄文件的指針。,兩級目錄結(jié)構(gòu),在兩級目錄結(jié)構(gòu)中：用戶可以請求系統(tǒng)為之建立一用戶文件目錄；如果用戶已不再需要UFD，也可以請求系統(tǒng)管理員將它撤消；有了UFD后，用戶可以根據(jù)自己的需要創(chuàng)建新文件。

50、新文件的建立：用戶要創(chuàng)建新文件，OS檢查該用戶的UFD，判定在該UFD中是否已有同名的另一個(gè)文件。若有，用戶必須為新文件重新命名；若無，便在UFD中建立一新目錄項(xiàng)，將新文件名及其有關(guān)屬性填入目錄項(xiàng)中，并置其狀態(tài)位為1。刪除文件：OS查找該用戶的UFD，從中找出指定文件的目錄項(xiàng)，在回收該文件所占用的存儲空間后，將該目錄項(xiàng)刪除。,優(yōu)點(diǎn)提高了檢索目錄的速度 在不同的用戶目錄中， 可以使用相同的文件名不同用戶還可使用不同的文件名來訪問

51、系統(tǒng)中的同一個(gè)共享文件 缺點(diǎn)：增加了系統(tǒng)開銷,3. 多級目錄結(jié)構(gòu),在兩級目錄結(jié)構(gòu)的基礎(chǔ)上，允許用戶再創(chuàng)建自己的子目錄及子目錄的子目錄…優(yōu)點(diǎn)：層次結(jié)構(gòu)清晰，便于管理和保護(hù)；有利于文件分類；解決重名問題；提高文件檢索速度；能進(jìn)行存取權(quán)限的控制；便于實(shí)現(xiàn)文件共享；被廣泛使用，且已成為目前廣為流行的一種目錄結(jié)構(gòu)。說明：查找一個(gè)文件按路徑名逐層檢查，可以按絕對路徑和相對路徑查找。,多級目錄結(jié)構(gòu),主目錄在樹型目錄結(jié)構(gòu)中，作為樹的根結(jié)點(diǎn)，

52、稱為根目錄。數(shù)據(jù)文件作為樹葉，其它所有目錄均作為樹的結(jié)點(diǎn)。路徑名在樹型目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件之間，只有一條唯一的通路，在該路徑上從樹的根(即主目錄)開始，把全部目錄文件名與數(shù)據(jù)文件名，依次用“/”連接起來，即構(gòu)成該數(shù)據(jù)文件的路徑名(path name)。系統(tǒng)中的每個(gè)數(shù)據(jù)文件都有唯一的路徑名。用戶訪問文件時(shí)，為保證訪問的唯一性，用戶在開始時(shí)必須使用文件的路徑名。,當(dāng)前目錄當(dāng)一個(gè)文件系統(tǒng)包含很多級時(shí)，如果每訪問一個(gè)文

53、件都要使用從樹根開始，直到樹葉的數(shù)據(jù)文件為止的、包括所有中間各級目錄名在內(nèi)的全路徑名，是相當(dāng)麻煩的事。又一個(gè)進(jìn)程在運(yùn)行時(shí)所要訪問的文件，大多只局限于某個(gè)范圍之內(nèi)?；谶@一點(diǎn)，可為每個(gè)進(jìn)程設(shè)置一個(gè)“當(dāng)前目錄”，又稱為“工作目錄”。進(jìn)程對各文件的訪問都是相對于“當(dāng)前目錄”進(jìn)行的。此時(shí)對各文件所使用的路徑名，只需從當(dāng)前目錄開始，再逐級通過中間的目錄文件，最后到達(dá)所要訪問的數(shù)據(jù)文件。將這一路徑上的全部目錄文件名與數(shù)據(jù)文件名用“／”連接而形

54、成的路徑名稱為相對路徑名(relative path name)。相應(yīng)地，前面從樹根開始的路徑名，稱為絕對路徑名(absolute path name) 。,在樹型結(jié)構(gòu)目錄中，用戶可為自己建立UFD，并可以再創(chuàng)建子目錄。在用戶要創(chuàng)建一新文件時(shí)，只需查看在自己的UFD及其子目錄中，有否與新建文件相同的文件名。若無，便可在UFD或其子目錄中增加一新目錄項(xiàng)。在樹型目錄中，對于一個(gè)已不需要的目錄，應(yīng)如何刪除其目錄項(xiàng)，則需視情況而定。這

55、時(shí)，如果所要刪除的目錄是空的，即該目錄中已不再有任何文件，就可簡單地將該目錄文件刪除，使它在其上一級目錄中對應(yīng)的目錄項(xiàng)為空。,增加和刪除目錄,在樹型目錄中，如果要刪除的目錄不空，即其中尚有幾個(gè)文件或子目錄，則可采取下述兩種方法處理： 不刪除非空目錄：當(dāng)目錄(文件)中不空時(shí)，不能將其刪除，而為了刪除一個(gè)非空目錄必須先刪除目錄中的所有文件，使之成為空目錄后再予以刪除。如果目錄中還包含有子目錄，還必須采取遞歸調(diào)用方式來將其刪除，在MS-DO

56、S中就是采用這種刪除方式?？蓜h除非空目錄：當(dāng)要求刪除一目錄時(shí)，如果該目錄中包含有文件，則目錄中的所有文件和子目錄也同時(shí)被刪除。,目錄的其他實(shí)現(xiàn)方法,哈希表算法：目錄項(xiàng)信息存在一哈希表中搜索時(shí)根據(jù)文件名計(jì)算哈希值得到一個(gè)指向表中文件的指針其他算法：如B+樹NTFS文件系統(tǒng)就采用了B+樹,6.4.3 目錄查詢技術(shù),當(dāng)用戶要訪問一個(gè)已存文件：1、利用文件名查找文件目錄，找出FCB或者i節(jié)點(diǎn)2、找到FCB或者i節(jié)點(diǎn)記錄的文件物

57、理地址，換算出物理位置3、啟動磁盤操作，將所需文件讀入目錄檢索方式線性檢索法HASH方法,順序檢索方法（線性檢索法）,在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄表中找到指名文件的目錄項(xiàng)。在樹型目錄中，用戶提供的文件名是由多個(gè)文件分量名組成的路徑名，此時(shí)須對多級目錄進(jìn)行查找。,查找 /usr/ast/mbox 的步驟,順序檢索方法（線性檢索法）,2. Hash方法,建立了Hash索引文件目錄，則可利用Hash

58、方法進(jìn)行查詢。即系統(tǒng)利用用戶提供的文件名并將它轉(zhuǎn)換為文件目錄的索引值，再利用該索引值到目錄中查詢。,2. Hash方法,一種處理此“沖突”的有效規(guī)則是：在利用Hash法索引查找目錄時(shí)，如果目錄表中相應(yīng)的目錄項(xiàng)是空的，則表示系統(tǒng)中并無指定文件。如果目錄項(xiàng)中的文件名與指定文件名相匹配， 則表示該目錄項(xiàng)正是所要尋找的文件所對應(yīng)的目錄項(xiàng)，故而可從中找到該文件所在的物理地址。如果在目錄表的相應(yīng)目錄項(xiàng)中的文件名與指定文件名并不匹配，則

59、表示發(fā)生了“沖突”，此時(shí)須將其Hash值再加上一個(gè)常數(shù)(該常數(shù)應(yīng)與目錄的長度值互質(zhì))，形成新的索引值， 再返回到第一步重新開始查找。,目錄項(xiàng)的實(shí)例說明,目錄項(xiàng)的實(shí)例說明,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結(jié)構(gòu) 6.3 外存分配方式 6.4 目錄管理 6.5 文件存儲空間的管理 6.6 文件共享與文件保護(hù) 6.7 數(shù)據(jù)一致性控制,第六章 文件管理,6.5 文件存儲空間的管理,為新創(chuàng)建的文件分配外存空間是文件管理的重要任

60、務(wù)外存分配與內(nèi)存分配類似，同樣可采用連續(xù)分配和離散分配方式外存分配的基本單位是磁盤塊而非字節(jié)實(shí)現(xiàn)存儲空間分配應(yīng)做： 1 記錄存儲空間的使用情況（數(shù)據(jù)結(jié)構(gòu)） 2 對存儲空間進(jìn)行分配和回收（手段）,6.5.1 空閑表法和空閑鏈表法,1. 空閑表法,空閑表屬于連續(xù)分配方式，為每個(gè)文件分配一塊連續(xù)的存儲空間。類似于內(nèi)存的動態(tài)分區(qū)分配。系統(tǒng)為所有的外存空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對應(yīng)一個(gè)空閑表項(xiàng)，其中包括表項(xiàng)序號，該空

61、閑區(qū)的第一個(gè)盤塊號，該區(qū)的空閑盤塊數(shù)等信息。將所有空閑區(qū)按其起始盤塊號遞增的次序排列。,圖 空閑盤塊表,存儲空間的分配與回收,與內(nèi)存分配類似，可采用首次適應(yīng)算法，循環(huán)首次適應(yīng)算法等分配時(shí)，先順序檢查空閑表直至找到第一個(gè)大小能滿足要求的空閑區(qū)，將該區(qū)分配給進(jìn)程，同時(shí)修改空閑表回收時(shí)要考慮回收區(qū)是否與空閑表的插入點(diǎn)的前后區(qū)相鄰接，若是鄰接應(yīng)予以合并對于文件系統(tǒng)，當(dāng)文件較小時(shí)(1~4個(gè)盤塊)多采用連續(xù)分配，當(dāng)文件較大時(shí)采用離散分配方

62、式。,2. 空閑鏈表法,有兩種形式（鏈元素不同）：空閑盤塊鏈：將磁盤上所有的空閑空間以盤塊為單位建立鏈表。分配和回收非常簡單，但為文件分配空間時(shí)可能要重復(fù)操作多次?？臻e盤區(qū)鏈：將磁盤上所有的空閑盤區(qū)(每個(gè)盤區(qū)包含若干盤塊)建立鏈表。分配時(shí)多采用首次適應(yīng)算法。為了提高速度可采用顯式鏈接方法，即在內(nèi)存中為空閑盤區(qū)建立一張鏈接表。回收時(shí)也要考慮與相鄰盤區(qū)合并的問題。,6.5.2 位示圖法,用二進(jìn)制位表示磁盤中某一塊的使用情況?！?”表示空

63、閑，“1”表示已分配，或者相反。磁盤上所有盤塊都有一個(gè)二進(jìn)制位與之對應(yīng)。所有盤塊對應(yīng)的位構(gòu)成一集合，稱為位示圖。通常用m×n個(gè)位構(gòu)成位示圖。m×n等于盤塊總數(shù)。,位示圖,圖 位示圖,盤塊的分配,順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。將所找到的一個(gè)或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位，位于位示的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式

64、計(jì)算： b=n(i-1)+j 式中，n代表每行的位數(shù)。修改位示圖，令map［i,j］=1。,盤塊的回收,將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。 轉(zhuǎn)換公式為：i=(b-1)DIV n+1j=(b-1)MOD n+1修改位示圖。令map［i,j］=0。,已知塊號，則磁盤地址：       柱面號＝[塊號/

65、（磁頭數(shù)×扇區(qū)數(shù)）]     磁頭號＝[（塊號mod （磁頭數(shù)×扇區(qū)數(shù)））/扇區(qū)數(shù)]     扇區(qū)號＝（塊號mod （磁頭數(shù)×扇區(qū)數(shù)））mod 扇區(qū)數(shù)已知磁盤地址：塊號＝柱面號×（磁頭數(shù)×扇區(qū)數(shù)）＋磁頭號×扇區(qū)數(shù)＋扇區(qū)號,位示圖的優(yōu)點(diǎn)：,容易找空閑相鄰的空閑盤塊(位示圖的相鄰位均為0)；位

66、示圖占用空間少，可保存在內(nèi)存。,6.5.3 成組鏈接法,,實(shí)現(xiàn)思想空閑表法和空閑鏈表法不適用于大型文件系統(tǒng)，因?yàn)榭臻e表和空閑鏈表太長。UNIX的是將上述兩種方法結(jié)合而成的成組鏈接法,空閑盤塊號棧用于存放一組空閑盤塊的盤塊號(最多含100個(gè)號)以及棧中尚有的空閑盤塊號數(shù)N。順便指出，N兼作棧頂指針。如當(dāng)N=100時(shí)，它指向S.free(99)。由于棧是臨界資源，每次只允許一個(gè)進(jìn)程訪問。文件區(qū)中的所有空閑盤塊，分成若干個(gè)組。比如將每1

67、00個(gè)盤塊作為一組。假定盤上共有10000個(gè)盤塊，其中201~7999號盤塊用于存放文件，即作為文件區(qū)，這樣最末一組盤塊號應(yīng)為7901~7999號；次末組為7801~7900， …,第二組的盤塊號為301~400；第一組為201~300。,空閑盤塊的組織,將每一組的盤塊總數(shù)N和該組所有盤塊號記入其前一組的第一個(gè)盤塊的S.free(0)~S.free(99)中，這樣，由各組的第一個(gè)盤塊可鏈成一條鏈將第一組的盤塊總數(shù)和所有的盤塊號，記入空

68、閑盤塊號棧中，作為當(dāng)前可供分配的空閑盤塊號最末一組只有99個(gè)盤塊，其盤塊號分別記入其前一組的S,free(1)~S.free(99)中，而在S.free(0)中則存放0，作為空閑盤塊鏈的結(jié)束標(biāo)志,,空閑盤塊號棧,S.free,0,1,98,99,300,400,7900,,,,,,,,,,299,399,7899,7999,201,301,7801,7901,,,,,,,,,,,,,,,,,,,,,,,,,圖 空閑盤塊的成組鏈接法

69、,,,,,空閑盤塊的分配,當(dāng)系統(tǒng)進(jìn)程要為用戶分配文件所需的盤塊時(shí)，調(diào)用盤塊分配過程完成該過程從棧頂取出一空閑塊號將與它對應(yīng)的盤塊分配給用戶，然后棧頂指針下移一格若該盤塊號已是棧底，即S.free(0),這是當(dāng)前棧中最后一個(gè)可供分配的盤塊號。由于在該盤塊號所對應(yīng)的盤塊中記有下一組可用的盤塊號，因此，需調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號棧的內(nèi)容，并把原棧底對應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。