第六章文件管理2

1、第六章 文件管理文件管理的功能文件管理的功能 文件的按名存取實現(xiàn)文件的共享、保護和保密 文件目錄的建立與維護 邏輯文件到物理文件的轉(zhuǎn)換 文件存儲空間的分配和管理 提供一組可供用戶使用的文件操作 文件：文件：具有文件名文件名的一組相關(guān)信息相關(guān)信息的集合。6.1 6.1 文件和文件系統(tǒng)文件和文件系統(tǒng)1）文件的相關(guān)概念）文件的相關(guān)概念 文件類型文件類型 按性質(zhì)與用途劃分：系統(tǒng)文件，用戶文件，庫文件 按數(shù)據(jù)形式劃分：源文件，目標文件，可執(zhí)行文件 按數(shù)據(jù)存取方式劃分：只讀文件，讀寫文件，只 可執(zhí)行文件 文件的組成文件的組成文件名、基本內(nèi)容、文件屬性（說明信息） 文件的結(jié)構(gòu)文件的結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：物理

2、結(jié)構(gòu)物理結(jié)構(gòu)：呈現(xiàn)在用戶面前的文件自身的組織形式與結(jié)構(gòu)，根據(jù)其基本內(nèi)容的組織方式可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件文件在物理存儲器上的組織形式與存儲結(jié)構(gòu)。其分配方式可分為連續(xù)分配、鏈接分配和索引分配2 2）文件系統(tǒng)）文件系統(tǒng) 用于對文件進行組織、存儲與管理的子系統(tǒng)。用于對文件進行組織、存儲與管理的子系統(tǒng)。l 用戶角度用戶角度：存儲信息和使用信息的接口（按名存取：命令，程序接口）l 系統(tǒng)角度系統(tǒng)角度：負責文件存儲空間管理文件系統(tǒng)接口文件系統(tǒng)接口管理程序集合管理程序集合管理對象：文件、文件管理對象：文件、文件目錄、文件存儲空間目錄、文件存儲空間文件系統(tǒng)結(jié)構(gòu)模型文件系統(tǒng)結(jié)構(gòu)模型 文件系統(tǒng)類型lFATlVF

3、ATlNTFSlEXT2lHPFS 注：現(xiàn)代OS一般支持多種文件系統(tǒng)3）文件操作）文件操作用戶通過文件系統(tǒng)的接口對文件所能實現(xiàn)的操作用戶通過文件系統(tǒng)的接口對文件所能實現(xiàn)的操作。l基本操作基本操作創(chuàng)建文件、 刪除文件、 讀文件、 寫文件、設置文件讀寫指針l其他操作其他操作目錄操作、修改文件屬性、設置文件訪問權(quán)限、更改文件名l 打開文件與關(guān)閉文件打開文件與關(guān)閉文件打開：文件屬性從外存拷貝到內(nèi)存打開文件表的一個打開：文件屬性從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號返回給用戶表目中，并將該表目的編號返回給用戶關(guān)閉：文件從打開文件表中的表目上刪除掉關(guān)閉：文件從打開文件表中的表目上刪除掉6

4、.2 6.2 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)p 記錄式文件結(jié)構(gòu)（又稱有結(jié)構(gòu)文件）記錄式文件結(jié)構(gòu)（又稱有結(jié)構(gòu)文件） 用戶把文件內(nèi)的信息按邏輯上獨立的含義劃 分信息單位，每個單位稱為一個記錄p 流式文件結(jié)構(gòu)（又稱無結(jié)構(gòu)文件）流式文件結(jié)構(gòu)（又稱無結(jié)構(gòu)文件） 對文件內(nèi)信息不再劃分單位，它是依次的一串字符流構(gòu)成的文件文件由字符（字節(jié)）序列構(gòu)成 文件 記錄 n 記錄 2 記錄 1 數(shù)據(jù)項n 數(shù)據(jù)項2 數(shù)據(jù)項1 圖圖1： 文件，記錄和數(shù)據(jù)項之間的層次關(guān)系文件，記錄和數(shù)據(jù)項之間的層次關(guān)系1）組成）組成文件文件由若干記錄記錄組成，每個記錄又由若干數(shù)據(jù)項數(shù)據(jù)項組成 記錄：記錄：數(shù)據(jù)的基本單位(存取訪問的基本對象)

5、數(shù)據(jù)項：數(shù)據(jù)項：數(shù)據(jù)的最小單位（指基本數(shù)據(jù)項）n 記錄式文件結(jié)構(gòu)記錄式文件結(jié)構(gòu)lllR0R1Ri數(shù)據(jù)項數(shù)據(jù)項1數(shù)據(jù)項數(shù)據(jù)項2數(shù)據(jù)項數(shù)據(jù)項n定長記錄文件定長記錄文件R0R1R2Ril0l1l2li變長記錄文件變長記錄文件2）類型：）類型： 定長記錄文件定長記錄文件 變長記錄文件變長記錄文件3）邏輯文件）邏輯文件根據(jù)記錄的不同組織方式形成不同的邏輯文件l順序文件順序文件l索引文件索引文件l索引順序文件索引順序文件 順序文件順序文件 順序文件一般是定長記錄，記錄中的數(shù)據(jù)項順序文件一般是定長記錄，記錄中的數(shù)據(jù)項的類型長度與次序固定，一般還有一個可以唯一的類型長度與次序固定，一般還有一個可以唯一標識記錄

6、的數(shù)據(jù)項，稱為鍵（標識記錄的數(shù)據(jù)項，稱為鍵（key），記錄按鍵），記錄按鍵值的約定次序組織。值的約定次序組織。 順序文件常用于批處理應用，對于更新某個順序文件常用于批處理應用，對于更新某個記錄的請求的處理性能不佳記錄的請求的處理性能不佳 索引文件索引文件建立一張索引表，記錄變長記錄的長度及邏輯首址索引號索引號長度長度l邏輯首址邏輯首址01il0l1li索引表索引表邏輯文件邏輯文件R0R1Ri注：索引表本身是一個按記錄鍵值排序的定長記錄的順序文件注：索引表本身是一個按記錄鍵值排序的定長記錄的順序文件 索引順序文件索引順序文件 順序文件與索引文件的結(jié)合（可減少索引表的長度）關(guān)鍵字邏輯地址姓名其它屬

7、性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件順序文件4）存取方法順序存取順序存取按照文件的邏輯地址順序存取，在記錄式文件中，這反映為按記錄的排列順序來存取隨機存取隨機存取允許用戶根據(jù)記錄的編號來存取文件的任一記錄6.3 6.3 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu) 1）文件的存儲方式）文件的存儲方式 連續(xù)分配存儲方式 離散分配存儲方式鏈接分配方式索引分配方式2）連續(xù)分配）連續(xù)分配順序文件順序文件 邏輯文件中連續(xù)的信息存儲到磁盤連續(xù)的物理盤塊中所形成的文件（位于同一磁道或相鄰磁道）。在文件控制塊FCB（或在目錄）中存放文件第一個記錄所存放的盤塊

8、號ADRR和文件總的盤塊數(shù)NContiguous Allocation of Disk Space優(yōu)點優(yōu)點：有利于文件的順序存取，且可獲得較高的存取速度缺點缺點：要求有足夠大的連續(xù)盤塊空間，不利于文件的動態(tài)增長，且易產(chǎn)生“磁盤碎片”3 3）鏈接分配）鏈接分配鏈接文件鏈接文件 為文件分配離散的盤塊離散的盤塊，其間（邏輯塊間）的邏輯關(guān)系通過鏈接指針鏈接形成，鏈接方式有兩種： 隱式鏈接：隱式鏈接：鏈接指針設置在每個物理盤塊最后一個單元。管理鏈接文件只需在文件控制塊FCB中存儲文件頭塊信息的盤塊號，有時也存儲文件尾塊信息的盤塊號。Linked Allocation of disk space優(yōu)點：優(yōu)點

9、：缺點：缺點： 顯式鏈接：顯式鏈接：用于鏈接文件各物理塊的指針顯式地存放在內(nèi)存的一張鏈表中，分配給文件的所有盤塊號都放在該表中，故該表也稱為文件分配表（FAT） 優(yōu)點：優(yōu)點：能提高檢索速度大大減少訪問磁盤的次數(shù) 缺點：缺點：文件分配表FAT需占用大量空間消除外碎片，存儲空間利用率提高；有利于文件動態(tài)增長文件的直接存取需多次讀盤獲取鏈接地址（指針），不利于直接存??；可靠性差4）索引分配方式）索引分配方式 采用離散分配方式存儲文件，為采用離散分配方式存儲文件，為每個文件每個文件建立一張建立一張索索引表引表，記錄邏輯塊與物理塊的對應關(guān)系，通過查找索引表，記錄邏輯塊與物理塊的對應關(guān)系，通過查找索引表獲

10、得物理盤塊地址。獲得物理盤塊地址。在在FCBFCB中放置了索引表指針，它指向中放置了索引表指針，它指向索引表始址，索引表存放在盤塊中。索引表始址，索引表存放在盤塊中。012349161102501234邏輯塊邏輯塊物理塊號物理塊號文件文件索引塊（盤塊）索引塊（盤塊）索引表被存放在專門的盤塊中，該盤塊稱為索引塊Example of Indexed Allocation優(yōu)點：方便直接存?。ú檎宜饕砗笾苯幼x優(yōu)點：方便直接存?。ú檎宜饕砗笾苯幼x/寫盤塊）寫盤塊）缺點：索引表占用外存空間，需先讀索引塊，文件很缺點：索引表占用外存空間，需先讀索引塊，文件很大時，占用多個塊，且查找索引表花費時間大時，占

11、用多個塊，且查找索引表花費時間索引表查找速度問題的解決索引表查找速度問題的解決I.采用兩級索引，針對一般不太長文件采用兩級索引，針對一般不太長文件II. 采用多級索引，針對較長文件采用多級索引，針對較長文件III. 采用混合索引，長、短文件均適用采用混合索引，長、短文件均適用 二級索引二級索引: :將一個大文件的所有索引表（二級索將一個大文件的所有索引表（二級索引引) )的地址放在另一個索引表（一級索引的地址放在另一個索引表（一級索引) )中中. . 混合索引（混合索引（UNIX O.SUNIX O.S采用）采用）由于由于8080以上文件是小文件，為了解決能高速存取小文件以上文件是小文件，為了

12、解決能高速存取小文件和管理大文件的矛盾，和管理大文件的矛盾，UNIXUNIX將直接尋址、一級索引、二級將直接尋址、一級索引、二級索引和三級索引結(jié)合起來，形成了混合尋址方式。索引和三級索引結(jié)合起來，形成了混合尋址方式。019101112主索引表主索引表iaddr（0） iaddr（9）iaddr（10）iaddr（11）iaddr（12）索引結(jié)點索引結(jié)點直接地址直接地址一次間址一次間址二次間址二次間址三次間址三次間址索引分配方式對應的物理文件稱為索引文件索引分配方式對應的物理文件稱為索引文件UNIX UNIX /Linux直接間接混合尋址方式直接間接混合尋址方式 二次間接塊二次間接塊一次間接塊一

13、次間接塊 三次間接塊三次間接塊 . . . . 。 . . . . . . . .di_addr0 di_addr1 di_addr2 . . . di_addr9 di_addr10 一次間接一次間接di_addr11 二次間接二次間接di_addr12 三次間接三次間接1034#數(shù)據(jù)數(shù)據(jù)塊塊0#1#2#9#10#5）三種分配方式比較）三種分配方式比較連續(xù)鏈接索引空間要求較高（連續(xù)）不高不高存取方式順序存取高速亦可直接存取只適合順序存取順序、直接存取均可缺點不利于文件動態(tài)增長，易產(chǎn)生磁盤碎片隱式鏈接不利于直接存取顯式鏈接需占用內(nèi)存空間（鏈表）索引表占用外存盤塊空間，查索引表需花費一定時間文件

14、結(jié)構(gòu)歸納文件結(jié)構(gòu)歸納邏輯結(jié)構(gòu)物理結(jié)構(gòu)概念與定義 文件自身的組織形式與結(jié)構(gòu)用戶所能看到的數(shù)據(jù)的組織形式文件在物理存儲器上的組織形式與結(jié)構(gòu)用戶看不見的、根據(jù)不同分配方式形成的不同的物理文件形式記錄式文件流式文件順序文件鏈接文件索引文件思考題： 一個文件系統(tǒng)中有一個一個文件系統(tǒng)中有一個20MB20MB大文件和一個大文件和一個20KB20KB小文小文件件, ,當分別采用連續(xù)、鏈接、二級索引和當分別采用連續(xù)、鏈接、二級索引和UNIX S V UNIX S V 分配方案時分配方案時( (每塊大小為每塊大小為4096B,4096B,每塊地址用每塊地址用4B4B表示表示) )，問問: :1.1.各文件系統(tǒng)管理

15、的最大的文件是多少各文件系統(tǒng)管理的最大的文件是多少? ? 2.2.每種方案對大、小二文件各需要多少專用塊來記錄每種方案對大、小二文件各需要多少專用塊來記錄文件的物理地址文件的物理地址( (說明各塊的用途說明各塊的用途) ?) ?解答：解答：1 1：各種分配方案的文件系統(tǒng)可管理的最大文件：各種分配方案的文件系統(tǒng)可管理的最大文件v連續(xù)分配連續(xù)分配：不受限制，可大到整個磁盤文件區(qū)。v鏈接分配鏈接分配：同上。v二級索引二級索引：由于盤塊大小為4KB，每個地址用4B表示，一個盤塊可存1K個索引表目，二級索引可管理的最大文件容量為4KB1K1K4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件

16、。vUNIXUNIX混合分配：混合分配：可管理的最大文件為40KB4MB+4GB4TB。解答：解答：2 2：每種分配方案對每種分配方案對20MB20MB大文件和大文件和20KB20KB小文件各需要多少小文件各需要多少專用塊來記錄文件的物理地址專用塊來記錄文件的物理地址? ?v連續(xù)分配連續(xù)分配：對大小二個文件都只需在文件控制塊FCB中設二項，一是首塊物理塊塊號，另一是文件總塊數(shù)，不需專用塊來記錄文件的物理地址。v鏈接分配鏈接分配：對大小二個文件都只需在文件控制塊FCB中設二項，一是首塊物理塊塊號，另一是文件尾塊數(shù)；同時在每塊存文件的物理塊中設置存貯下一塊塊號的指針。解答：解答：v 二級索引二級索

17、引：對大小文件都固定要用二級索引，對20KB小文件，用一塊作第一級索引，用另一塊作二級索引，共用二塊專用物理塊作索引塊，對于20MB大文件，用一塊作第一級索引，用5塊作第二級索引，共用六塊專用物理塊作索引塊。v UNIXUNIX的混合分配的混合分配：對20KB小文件只需在文件控制塊FCB的i_addr13中使用前5個表目存放文件的物理塊號，不需專用索引塊。對20MB大文件，F(xiàn)CB的i_addr13中使用前10個表目存放大文件前10塊物理塊塊號，用一級索引塊一塊保存大文件接著的1K塊塊號，還要用二級索引存大文件以后的塊號，二級索引使用第一級索引1塊，第二級索引4塊?？偣惨残枰?塊專用物理塊來存放

18、文件物理地址。6.4 文件目錄管理文件目錄管理 1）概）概 述述 目錄管理的基本要求目錄管理的基本要求能實現(xiàn)“按名存取按名存取”的目標具有較高的查詢（檢索）速度可實現(xiàn)文件共享允許不同用戶采用相同的文件名文件目錄 存放文件說明信息及存取控制信息的一種數(shù)據(jù)結(jié)構(gòu)，用于標識系統(tǒng)中的文件及其物理地址供檢索時使用。一個文件目錄項又稱為一個文件控制塊文件控制塊（FCB）。）。FCB中包含的信息有以下三類： 基本信息：基本信息：文件名，用戶名，文件類型、文件長度，文件結(jié)構(gòu)(邏輯結(jié)構(gòu)，物理結(jié)構(gòu))等 控制信息：控制信息：文件主及其他用戶的存取權(quán)限等 使用信息：使用信息：文件建立日期、最后一次修改日期，當前使用的信

19、息如打開文件的進程數(shù)等2 2）索引結(jié)點）索引結(jié)點為減少目錄數(shù)據(jù)量，減少讀盤次數(shù)，提高目錄查詢速度 即將文件名與文件說明信息分開存放文件名文件名Z1Ws索引結(jié)點編號索引結(jié)點編號文件長度文件長度文件結(jié)構(gòu)文件結(jié)構(gòu)物理地址物理地址文件長度文件長度文件結(jié)構(gòu)文件結(jié)構(gòu)物理地址物理地址Z1文件索引結(jié)點文件索引結(jié)點Ws文件索引結(jié)點文件索引結(jié)點Z1文件文件Ws文件文件文件目錄文件目錄磁盤索引結(jié)點：磁盤索引結(jié)點： 文件建立時生成，每個文件有惟一的一個磁盤索引結(jié)點，主要包括文件主標識符、文件類型、文件存取權(quán)限、文件物理地址等相關(guān)文件說明信息。內(nèi)存索引結(jié)點內(nèi)存索引結(jié)點： 文件操作，打開文件時建立。將磁盤索引結(jié)點拷貝到內(nèi)

20、存索引結(jié)點并增加如下內(nèi)容：索引結(jié)點編號、狀態(tài)、訪問計數(shù)、文件所屬文件系統(tǒng)的邏輯設備號、鏈接指針。 例：設某文件系統(tǒng)中有128個文件，每個文件的FCB占48B，其中文件名6B。索引節(jié)點編號2B.假設磁盤盤塊大小為512B。求引入索引節(jié)點之前和之后查找一個文件所需的平均讀盤次數(shù)。解：引入前一盤塊可存放的FCB數(shù)：512/48=10（個）引入后一盤塊可存放的目錄項數(shù)512/8=64（個） 可存放的索引節(jié)點數(shù)：512/42=12（個）128個文件在索引節(jié)點引入前目錄項占128/10=13個盤塊；索引節(jié)點引入后目錄項占2塊，索引節(jié)點占11塊。故查找一個文件的平均訪盤次數(shù) 引入前：(1+13)/2=7次

21、引入后：(1+2)/2 +1 =2.5次3）目錄結(jié)構(gòu)簡介）目錄結(jié)構(gòu)簡介單級目錄結(jié)構(gòu)單級目錄結(jié)構(gòu)文件名文件長度物理地址狀態(tài)f11Zs10Ls1整個文件系統(tǒng)一張表格，每個文件占有一個目錄項整個文件系統(tǒng)一張表格，每個文件占有一個目錄項 文件的建立和刪除文件的建立和刪除建立新文件：建立新文件： 刪除文件：刪除文件： 優(yōu)點：優(yōu)點： 缺點：缺點：查目錄，無同名文件則找一個空目錄（狀態(tài)為0）分配給新文件使用（填入相關(guān)說明信息）查目錄，找到同名者，根據(jù)物理地址回收外存空間，將對應表目狀態(tài)置為0（表目回收）文件名與物理文件一一對應，可實現(xiàn)“按名存取”，目錄結(jié)構(gòu)簡單，管理簡單不允許重名，不便于共享，故一般適用于單

22、用戶 兩級目錄結(jié)構(gòu)兩級目錄結(jié)構(gòu)用戶名用戶名 目錄指針目錄指針ZhangWangLi文件名文件名物理地址物理地址Z1Z2文件名文件名物理地址物理地址WaWb文件名文件名物理地址物理地址LimWaZ1Z2WaWbLimWa主目錄主目錄MFD（整個文件系統(tǒng)一張）（整個文件系統(tǒng)一張）用戶文件目錄用戶文件目錄UFD（每個用戶一張表）（每個用戶一張表） 文件的建立和刪除文件的建立和刪除用戶登錄建立新文件：需分配MFD表目和UFD空間用戶退出：需釋放UFD空間和對應MFD表目 建立、刪除文件必須先查主目錄，再查用戶文件目錄， 然后實施操作 優(yōu)點優(yōu)點提高了目錄的查詢（檢索）速度允許不同用戶取相同文件名，利于文

23、件的保護可用不同文件名共享使用同一文件 缺點缺點用戶不能建立自己的子目錄多級目錄結(jié)構(gòu)（三級或三級以上目錄）多級目錄結(jié)構(gòu)（三級或三級以上目錄）ABCABDFEDGAACJNKJMKAHF123456789101112131415161718192021多級目錄組織多級目錄組織在多級目錄中，第一級目錄稱為根目錄，目錄中的非葉結(jié)點在多級目錄中，第一級目錄稱為根目錄，目錄中的非葉結(jié)點均為子目錄，樹葉結(jié)點均為文件，多級目錄也稱樹形目錄。均為子目錄，樹葉結(jié)點均為文件，多級目錄也稱樹形目錄。根根目錄目錄文文件件Unix 的樹型多級目錄的樹型多級目錄 路徑名路徑名從根目錄開始到該文件的通路上所有各級目錄名拼起

24、來得從根目錄開始到該文件的通路上所有各級目錄名拼起來得到（文件名）到（文件名），各子目錄之間可用分隔符隔開。 例：ls文件的路徑名為：/bin/ls（絕對路徑名）（絕對路徑名） 當前目錄（工作目錄）當前目錄（工作目錄）訪問文件從當前目錄開始，相對于當前目錄而設置路徑訪問文件從當前目錄開始，相對于當前目錄而設置路徑。 例：當前目錄為/usr/bin子目錄 則dc文件的路徑名為：./dc（相對路徑名）（相對路徑名）優(yōu)點：優(yōu)點： 允許文件重名，利于文件共享和保護，具有較高的查詢速度，特別是在當前目錄下查找文件將更為快捷。缺點：缺點： 多級查找可能要多次讀盤（讀子目錄文件），降低查找速度6.5 6.5

25、 文件存儲空間的分配與管理文件存儲空間的分配與管理1）分配要求與算法）分配要求與算法 基本要求：基本要求： -有利于外存空間的充分利用-具有較高的訪問速度 常用算法常用算法 -空閑表法（連續(xù)分配方式）-空閑鏈表法-位示圖法-成組鏈接法2）空閑表法）空閑表法 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：序號第一個空閑盤塊號空閑盤塊數(shù)1242933155空閑表空閑表 盤塊的分配與回收盤塊的分配與回收 分配：查空閑表，找到一個足夠大的空閑盤區(qū)，一分為二分配之 回收：先進行回收盤區(qū)的鄰接合并，再記入（修改）空閑表 特點：可為文件分配連續(xù)盤塊空間，但會產(chǎn)生磁盤碎片建立一張空閑表，記錄所有空閑盤區(qū)情況建立一張空閑表，記錄所有空閑

26、盤區(qū)情況（2, 3, 4, 5）（9, 10, 11）（15, 16, 17, 18, 19）3）空閑鏈表法）空閑鏈表法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 空閑盤區(qū)鏈表空閑盤區(qū)鏈表：以空閑盤區(qū)為單位鏈成一條鏈表 空閑盤塊鏈表空閑盤塊鏈表：以空閑盤塊為單位鏈成一條鏈表將磁盤上所有空閑盤區(qū)鏈接在一個隊列中將磁盤上所有空閑盤區(qū)鏈接在一個隊列中 空閑鏈空閑鏈表表 空閑鏈頭塊塊號空閑鏈頭塊塊號3 3 空閑鏈尾塊塊號空閑鏈尾塊塊號2020 8 8 16 16 10 10 20 20 物理塊號物理塊號 3 8 3 8 16 10 2016 10 20 分配與回收（針對空閑盤塊鏈）分配與回收（針對空閑盤塊鏈） 分配：分配：查

27、空閑鏈表，只要鏈表不空，便可根據(jù)文件需要的盤塊數(shù)逐一摘下空閑盤塊分配之 回收：回收：將所有回收盤塊一一插入（插在鏈尾）空閑盤塊鏈 特點：特點：為文件分配不連續(xù)的盤塊空間，空間利用率高，采用隱式鏈表會增加（分配時）讀盤次數(shù)注：空閑盤區(qū)鏈是空閑表的另一種結(jié)構(gòu)形式，可采用類似可變分區(qū)分配算法為文件分配連續(xù)存儲空間4）成組鏈接法（）成組鏈接法（UNIX O.S采用）采用）算法思想：成組鏈接法是空閑表和空閑鏈表的結(jié)合。將磁算法思想：成組鏈接法是空閑表和空閑鏈表的結(jié)合。將磁盤空閑塊盤空閑塊分成若干組分成若干組，如將每，如將每100100個盤塊作為一組，用個盤塊作為一組，用索引索引表表表示；該組空閑塊總數(shù)和

28、各空閑塊塊號存入下一組的第表示；該組空閑塊總數(shù)和各空閑塊塊號存入下一組的第一個空閑塊中（從后往前分組），一個空閑塊中（從后往前分組），各組各組通過鏈接指針連在通過鏈接指針連在一起形成一起形成鏈表，鏈表，最后不滿最后不滿100100塊的那組空閑塊總數(shù)和各空閑塊的那組空閑塊總數(shù)和各空閑塊塊號記入磁盤區(qū)專用管理塊（超級塊）的塊塊號記入磁盤區(qū)專用管理塊（超級塊）的空閑盤塊號棧空閑盤塊號棧的的s_nfrees_nfree和和s_free100s_free100中。其數(shù)據(jù)結(jié)構(gòu)如下所示：中。其數(shù)據(jù)結(jié)構(gòu)如下所示： 超級超級 塊塊（已在內(nèi)存）（已在內(nèi)存）棧頂棧頂分配與回收（借助空閑盤塊號棧分配與回收（借助空閑盤

29、塊號棧） 分配分配a)出棧，將棧頂盤塊號分配出去；b)當分配到棧底盤塊時，先將棧底盤塊出棧，將該盤塊數(shù)據(jù)讀到內(nèi)存空閑盤塊號棧中，再將原棧底盤塊分配出去； 回收回收 a)進棧，依次將回收盤塊號壓入棧中；b)當棧滿時，若再回收一個盤塊，先將棧內(nèi)數(shù)據(jù)寫到該新回收盤塊中，將棧清空，再將該回收盤塊進棧 特點：特點： 利用空閑盤塊存放（暫時）鏈接數(shù)據(jù)，只需為空閑盤塊號棧分配輔助存儲空間（內(nèi)存及外存）即可，且為分配、回收操作進行的讀、寫盤次數(shù)相對較少成組鏈接法盤塊分配回收示例：成組鏈接法盤塊分配回收示例：v空閑盤塊的分配：空閑盤塊的分配： 開始的空閑盤塊資源如下圖開始的空閑盤塊資源如下圖(a)(a)所示。所

30、示。 1 1）如果某一個文件要求申請一個空閑塊）如果某一個文件要求申請一個空閑塊 將s_nfree-1=38，s_free38即12號塊分配給申請者。如果還要申請，則繼續(xù)。經(jīng)過若干次申請后s_nfree=2，如圖(b)所示。 2 2）如果此時又有一個文件要申請）如果此時又有一個文件要申請4 4塊塊 首先可以得到棧底元素s_free0的盤塊號50先將50塊中的內(nèi)容讀出：把50#塊中的總塊數(shù)100賦給超級塊的s_nfree，并把對應的100個物理塊號復制到數(shù)組s_free100中，如圖(c)所示； 然后再把50塊分配給申請者，最后再將51、52塊分配給申請者。如下圖(d)所示。v空閑盤塊的釋放：空

31、閑盤塊的釋放： 1 1）假定有一個文件占用了三）假定有一個文件占用了三個物理塊，塊號分別是個物理塊，塊號分別是180180，181181，182182。未釋放。未釋放前的空閑盤塊的狀態(tài)如下圖前的空閑盤塊的狀態(tài)如下圖(a)(a)所示。所示。 釋放時首先填寫182到s_nfree65中，然后s_nfree+1=66，同理釋放181，180塊，釋放后的空閑盤塊如圖(b)所示。 2)2)假設某時刻磁盤的空閑盤塊狀況如下圖假設某時刻磁盤的空閑盤塊狀況如下圖(a)(a)所示。如果有所示。如果有一個文件釋放所要占用的一個文件釋放所要占用的4 4塊，塊號分別為塊，塊號分別為190190，185185，1841

32、84，170170。 其釋放過程為：首先有2塊的塊號170，184寫入超級塊中，其狀態(tài)如下圖(b)所示。此時s_free=100,表示內(nèi)存中登記的空閑塊已經(jīng)滿。還要釋放185、190，則系統(tǒng)把當前卷資源表中的空閑塊數(shù)100連同100個登記項，寫到185#中，然后將s_nfree清0，再將185、190#填入到超級塊中，如圖(c)所示。5）位示圖法）位示圖法利用計算機存儲單元的一位指示對應盤塊的空閑及分配情況利用計算機存儲單元的一位指示對應盤塊的空閑及分配情況取值取值0和和1分別表示空閑和占用分別表示空閑和占用 分配和回收過程分配和回收過程 特點：特點：位示圖的大小由磁盤空間的大小（物理塊總數(shù)）

33、決定，位示圖的描述能力強，適合各種物理結(jié)構(gòu)。既可分配連續(xù)盤塊空間，又可離散分配，輔助空間占用較少6.6 文件的共享與保護文件的共享與保護1）基于索引結(jié)點的共享方法）基于索引結(jié)點的共享方法文件名文件名 索引結(jié)點指針索引結(jié)點指針TestWang用戶文件目錄用戶文件目錄文件名文件名 索引結(jié)點指針索引結(jié)點指針TestZhang用戶文件目錄用戶文件目錄Test文件文件不同用戶（進程）的文件目錄某文不同用戶（進程）的文件目錄某文件表目指向同一文件索引結(jié)點件表目指向同一文件索引結(jié)點特點：文件主刪除文件，索引結(jié)點同時消失，共享用戶共享指針懸空；此種鏈接不能跨越文件系統(tǒng)2）利用符號鏈實現(xiàn)文件共享）利用符號鏈實現(xiàn)文件共享文件名文件名指針指針TestW用戶文件目錄用戶文件目錄文件名文件名指針指針TestZ用戶文件目錄用戶文件目錄Test索引結(jié)點索引結(jié)點Test文件文件（Link）索引結(jié)點）索引結(jié)點（Link）文件（符號鏈接）文件（符號鏈接）其只包含其只包含Test文件的路徑名文件的路徑名文件主訪問文件：文件主訪問文件：直接通過文件索引結(jié)點直接通過文件