操作系統(tǒng)第6章

1、第六章第六章文件管理文件管理文件文件n文件是指由創(chuàng)建者所定義的、具有文件名的一文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合?？煞譃橛薪Y(jié)構(gòu)文件和無結(jié)構(gòu)組相關(guān)元素的集合?？煞譃橛薪Y(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。文件兩種。 文件文件記錄記錄1記錄記錄2記錄記錄n數(shù)據(jù)項數(shù)據(jù)項1數(shù)據(jù)項數(shù)據(jù)項2數(shù)據(jù)項數(shù)據(jù)項n文件類型文件類型n按用途分類按用途分類n按數(shù)據(jù)形式分類按數(shù)據(jù)形式分類n按存取控制屬性分類按存取控制屬性分類n按組織形式和處理方式分類按組織形式和處理方式分類系統(tǒng)文件系統(tǒng)文件用戶文件用戶文件庫文件庫文件源文件源文件目標(biāo)文件目標(biāo)文件可執(zhí)行文件可執(zhí)行文件只執(zhí)行文件只執(zhí)行文件只讀文件只讀文件讀寫文件讀寫

2、文件普通文件普通文件目錄文件目錄文件特殊文件特殊文件文件系統(tǒng)文件系統(tǒng)n文件系統(tǒng)是指操作系統(tǒng)中各類文件、管理文件的文件系統(tǒng)是指操作系統(tǒng)中各類文件、管理文件的軟件，以及管理文件所涉及到的數(shù)據(jù)結(jié)構(gòu)等信息軟件，以及管理文件所涉及到的數(shù)據(jù)結(jié)構(gòu)等信息的集合。的集合。文件系統(tǒng)接口文件系統(tǒng)接口對象及其屬性對象及其屬性用戶（程序）用戶（程序）對對象操縱對對象操縱和管理的軟和管理的軟件集合件集合邏輯文件系統(tǒng)邏輯文件系統(tǒng)基本基本I/O管理程序管理程序(文件組織模塊文件組織模塊)基本文件系統(tǒng)基本文件系統(tǒng)(物理物理I/O層層)I/O控制層控制層(設(shè)備驅(qū)動程序設(shè)備驅(qū)動程序)文件管理系統(tǒng)管理的對象有：文件管理系統(tǒng)管理的對象

3、有： n文件文件文件管理的直接對象；文件管理的直接對象；n目錄目錄方便用戶對文件檢索和存取。包含文件方便用戶對文件檢索和存取。包含文件名和文件屬性的說明；名和文件屬性的說明；n磁盤存儲空間磁盤存儲空間對文件和目錄占用的外存空間對文件和目錄占用的外存空間進(jìn)行管理，可以提高外存利用率，加快文件的進(jìn)行管理，可以提高外存利用率，加快文件的檢索速度。檢索速度。對象及其屬性對象及其屬性這是文件管理系統(tǒng)的核心部分。主要功能包括：這是文件管理系統(tǒng)的核心部分。主要功能包括：n對文件存儲空間的管理；對文件存儲空間的管理；n對文件目錄的管理；對文件目錄的管理；n將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制；將文件的邏輯地址

4、轉(zhuǎn)換為物理地址的機(jī)制；n對文件讀和寫的管理；對文件讀和寫的管理；n對文件的共享與保護(hù)等功能；對文件的共享與保護(hù)等功能； 對對象操縱和管理的軟件集合對對象操縱和管理的軟件集合nI/O控制層控制層(設(shè)備驅(qū)動程序設(shè)備驅(qū)動程序) 啟動啟動I/O操作和對操作和對設(shè)備發(fā)來的中斷信號處理；設(shè)備發(fā)來的中斷信號處理；n基本文件系統(tǒng)基本文件系統(tǒng)(物理物理I/O層層) 處理內(nèi)存與磁盤處理內(nèi)存與磁盤系統(tǒng)之間數(shù)據(jù)塊的交換；系統(tǒng)之間數(shù)據(jù)塊的交換；n基本基本I/O管理程序管理程序(文件組織模塊文件組織模塊) 完成與完成與I/O有關(guān)的大量事物：選擇文件所在的設(shè)備、地址映有關(guān)的大量事物：選擇文件所在的設(shè)備、地址映射、空閑盤塊的

5、管理、射、空閑盤塊的管理、I/O緩沖的指定；緩沖的指定；n邏輯文件系統(tǒng)邏輯文件系統(tǒng)處理文件和記錄的相關(guān)操作；處理文件和記錄的相關(guān)操作；(1) 命令接口命令接口 (2) 程序接口程序接口文件系統(tǒng)的接口文件系統(tǒng)的接口文件操作文件操作 n創(chuàng)建文件創(chuàng)建文件系統(tǒng)要為新文件分配必要的外存空系統(tǒng)要為新文件分配必要的外存空間，并在文件系統(tǒng)的目錄中為之建一個目錄項；間，并在文件系統(tǒng)的目錄中為之建一個目錄項； n刪除文件刪除文件系統(tǒng)應(yīng)先從目錄中找到要刪除文件系統(tǒng)應(yīng)先從目錄中找到要刪除文件的目錄項，使之成為空項，然后回收該文件所占的目錄項，使之成為空項，然后回收該文件所占用的存儲空間；用的存儲空間； n讀文件讀文件

6、須在系統(tǒng)調(diào)用中給出文件名和文件被須在系統(tǒng)調(diào)用中給出文件名和文件被讀入的內(nèi)存目標(biāo)地址；讀入的內(nèi)存目標(biāo)地址；n寫文件寫文件須在系統(tǒng)調(diào)用中給出文件名和文件須在系統(tǒng)調(diào)用中給出文件名和文件在內(nèi)存中的源地址；在內(nèi)存中的源地址；n截斷文件截斷文件文件內(nèi)容需要全部更新時，將原文件內(nèi)容需要全部更新時，將原文件的長度設(shè)置為文件的長度設(shè)置為0；n設(shè)置文件的讀設(shè)置文件的讀/寫位置寫位置用于設(shè)置文件讀寫指用于設(shè)置文件讀寫指針的位置，以便每次讀寫文件時，不是從其開始針的位置，以便每次讀寫文件時，不是從其開始端開始，而是從所設(shè)置的位置處開始；端開始，而是從所設(shè)置的位置處開始；文件的文件的“打開打開”操作操作n系統(tǒng)將指名文件

7、的屬性從外存拷貝到內(nèi)存打開文件系統(tǒng)將指名文件的屬性從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號返回給用戶。表的一個表目中，并將該表目的編號返回給用戶。n用戶再要求對該文件進(jìn)行操作時，系統(tǒng)直接利用索用戶再要求對該文件進(jìn)行操作時，系統(tǒng)直接利用索引號到打開文件表中去查找，從而避免了對文件的引號到打開文件表中去查找，從而避免了對文件的再次檢索。再次檢索。文件文件“關(guān)閉關(guān)閉”操作操作n如果用戶不再需要對該文件實(shí)施相應(yīng)的操作時，如果用戶不再需要對該文件實(shí)施相應(yīng)的操作時，可利用可利用“關(guān)閉關(guān)閉”(close)系統(tǒng)調(diào)用來關(guān)閉此文件，系統(tǒng)調(diào)用來關(guān)閉此文件，OS把該文件從打開文件表中的表目上刪除掉。把

8、該文件從打開文件表中的表目上刪除掉。OS提供了有關(guān)文件操作的系統(tǒng)調(diào)用：提供了有關(guān)文件操作的系統(tǒng)調(diào)用：n一類是有關(guān)對文件屬性進(jìn)行操作的，即允許用戶一類是有關(guān)對文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的屬性；直接設(shè)置和獲得文件的屬性；n另一類是有關(guān)目錄的，如創(chuàng)建一個目錄，刪除一另一類是有關(guān)目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改變當(dāng)前目錄和工作目錄等；個目錄，改變當(dāng)前目錄和工作目錄等；n用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)用于實(shí)現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。進(jìn)行操作的系統(tǒng)調(diào)用等。 其它文件操作其它文件操作文件的結(jié)構(gòu)文件的結(jié)構(gòu)（1）文件的邏輯結(jié)構(gòu)）文件的邏輯

9、結(jié)構(gòu) 用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于文用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于文件的物理特性，又稱為文件組織；件的物理特性，又稱為文件組織； (2) 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu) 又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式；儲組織形式； 文件邏輯結(jié)構(gòu)的類型文件邏輯結(jié)構(gòu)的類型n有結(jié)構(gòu)文件有結(jié)構(gòu)文件由一個以上的記錄構(gòu)成的文件；由一個以上的記錄構(gòu)成的文件；n無結(jié)構(gòu)文件無結(jié)構(gòu)文件由字符流構(gòu)成的文件；由字符流構(gòu)成的文件；n根據(jù)記錄長度根據(jù)記錄長度(1)定長記錄定長記錄(2)變長記錄變長記錄 n根據(jù)用戶和系統(tǒng)管理上的需要根據(jù)用戶和系統(tǒng)管理上的需

10、要(1)順序文件順序文件 (2)索引文件索引文件 (3)索引順序文件索引順序文件 有結(jié)構(gòu)文件有結(jié)構(gòu)文件n無結(jié)構(gòu)文件又稱流式文件，構(gòu)成文件的基本單位無結(jié)構(gòu)文件又稱流式文件，構(gòu)成文件的基本單位是字符，文件是有邏輯意義的、無結(jié)構(gòu)的一串字是字符，文件是有邏輯意義的、無結(jié)構(gòu)的一串字符的集合。符的集合。n其長度以字節(jié)為單位。對流式文件的訪問，采用其長度以字節(jié)為單位。對流式文件的訪問，采用讀寫指針來指出下一個要訪問的字符。讀寫指針來指出下一個要訪問的字符。n在在UNIX系統(tǒng)中，所有的文件都被看作是流式文系統(tǒng)中，所有的文件都被看作是流式文件，系統(tǒng)不對文件進(jìn)行格式處理；件，系統(tǒng)不對文件進(jìn)行格式處理； 無結(jié)構(gòu)文件

11、無結(jié)構(gòu)文件順序文件邏輯記錄的排序順序文件邏輯記錄的排序 n第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無關(guān)，按存入時間的先后排列；關(guān)，按存入時間的先后排列；n第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)鍵字關(guān)鍵字(詞詞)排列?？梢园搓P(guān)鍵詞的長短從小到大排列?？梢园搓P(guān)鍵詞的長短從小到大排序，也可以從大到小排序；或按其英文字母順排序，也可以從大到小排序；或按其英文字母順序排序；序排序； 對順序文件的讀對順序文件的讀/寫操作寫操作n對于定長記錄文件，如果要查找第對于定長記錄文件，如果要查找第i個記錄，第個記錄，第i個記錄

12、相對于第一個記錄首址的地址為：個記錄相對于第一個記錄首址的地址為： Ai= iLn對于變長度記錄文件，要查找第對于變長度記錄文件，要查找第i個記錄，要順個記錄，要順序地查找每個記錄，獲得相應(yīng)記錄的長度序地查找每個記錄，獲得相應(yīng)記錄的長度Li，然，然后按下式計算出第后按下式計算出第i個記錄的首址。假定在每個個記錄的首址。假定在每個記錄前用一字節(jié)指明該記錄的長度，則：記錄前用一字節(jié)指明該記錄的長度，則：10iiiiiLA定長和變長記錄文件定長和變長記錄文件 R0R1R2R3RiLLLLLL2L3L4LL(i+1)LRptr(a) 定長記錄文件定長記錄文件L0R0L1R1RiWptr(b)變長記錄文

13、件變長記錄文件Li00L0L0+1L1L0+L1+2Li(Lk+1)i-1K=0(Lk+1)iK=0順序文件的優(yōu)缺點(diǎn)順序文件的優(yōu)缺點(diǎn) n最佳應(yīng)用場合是在對諸記錄進(jìn)行批量存取時，最佳應(yīng)用場合是在對諸記錄進(jìn)行批量存取時，即每次要讀或?qū)懸淮笈涗?；即每次要讀或?qū)懸淮笈涗洠籲在交互應(yīng)用場合，用戶要求查找或修改單個記在交互應(yīng)用場合，用戶要求查找或修改單個記錄，便要逐個地查找諸記錄錄，便要逐個地查找諸記錄, ,性能就可能很差；性能就可能很差；n增加或刪除一個記錄，比較困難；增加或刪除一個記錄，比較困難；索引文件索引文件n為變長記錄文件建立一張索引表，對主文件中為變長記錄文件建立一張索引表，對主文件中的每

14、個記錄，在索引表中設(shè)一個相應(yīng)的表項，用的每個記錄，在索引表中設(shè)一個相應(yīng)的表項，用于記錄該記錄的長度于記錄該記錄的長度L以及指向該記錄的指針；以及指向該記錄的指針；n根據(jù)用戶提供的關(guān)鍵字，利用折半查找法去檢根據(jù)用戶提供的關(guān)鍵字，利用折半查找法去檢索索引表，從中找到相應(yīng)的表項；索索引表，從中找到相應(yīng)的表項；n利用該表項中給出的指針值，去訪問所需的記利用該表項中給出的指針值，去訪問所需的記錄錄;索引表索引表索引號索引號0長度長度 m指針指針 ptrm01m1imiR0R1Ri邏輯文件邏輯文件索引順序文件索引順序文件 n是順序文件和索引文件相結(jié)合的產(chǎn)物；是順序文件和索引文件相結(jié)合的產(chǎn)物；n將順序文件中

15、的所有記錄分為若干個組，為順序?qū)㈨樞蛭募械乃杏涗浄譃槿舾蓚€組，為順序文件建立一張索引表；文件建立一張索引表；n在索引表中為每組中的第一個記錄建立一個索引在索引表中為每組中的第一個記錄建立一個索引項，含有該記錄的鍵值和指向該記錄的指針項，含有該記錄的鍵值和指向該記錄的指針; ;n檢索時，先利用用戶提供的關(guān)鍵字檢索時，先利用用戶提供的關(guān)鍵字, ,按某種查找算法按某種查找算法去檢索索引表；去檢索索引表；n找到該記錄所在記錄組中第一個記錄的表項，從中得找到該記錄所在記錄組中第一個記錄的表項，從中得到該記錄組第一個記錄在主文件中的位置；到該記錄組第一個記錄在主文件中的位置；n再利用順序查找法去查找主

16、文件，從中找到所要求的再利用順序查找法去查找主文件，從中找到所要求的記錄；記錄；鍵鍵An QiBao RongChen Lin邏輯地址邏輯地址姓姓 名名An QiAn Kang其它屬性其它屬性Bao Rong邏輯文件邏輯文件直接文件直接文件n可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址理地址; ;n記錄鍵值本身就決定了記錄的物理地址記錄鍵值本身就決定了記錄的物理地址; ;n由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換換; ;哈希哈希(Hash)文件文件 Hash文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)n利用利用Hash

17、函數(shù)，將記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址函數(shù)，將記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址;n由由Hsah函數(shù)所求的是指向一目錄表相應(yīng)表目的指針，函數(shù)所求的是指向一目錄表相應(yīng)表目的指針，該表目的內(nèi)容指向相應(yīng)記錄所在的物理塊該表目的內(nèi)容指向相應(yīng)記錄所在的物理塊;fHash函數(shù)函數(shù)目錄表目錄表鍵值鍵值n連續(xù)分配連續(xù)分配n鏈接分配鏈接分配n索引分配索引分配外存分配方式外存分配方式磁道磁道(柱面柱面)扇區(qū)扇區(qū)磁臂磁臂磁頭磁頭盤面盤面n為每一個文件分配一組相鄰接的盤塊為每一個文件分配一組相鄰接的盤塊; ;n把邏輯文件中的記錄順序地存儲到鄰接的各物把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中理盤塊中; ;n這樣形成的文

18、件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)這樣形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu), ,物理文物理文件稱為順序文件件稱為順序文件; ;連續(xù)分配方式連續(xù)分配方式mail1230567491011813141512171819162122232025262724list29303128countfilestart lengthcount02tr143mail196list284f62目錄目錄 tr f連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)缺點(diǎn) n優(yōu)點(diǎn)：優(yōu)點(diǎn)：(1)順序訪問容易順序訪問容易; (2)順序訪問速度快順序訪問速度快;n缺點(diǎn)：缺點(diǎn)：(1)要求有連續(xù)的存儲空間要求有連續(xù)的存儲空間; (2)必須事先知道文件的長度必須事先

19、知道文件的長度;鏈接分配鏈接分配n 文件的信息存放在若干不連續(xù)的物理塊中；文件的信息存放在若干不連續(xù)的物理塊中；n各塊之間通過指針連接，前一個物理塊指向下各塊之間通過指針連接，前一個物理塊指向下一個物理塊；一個物理塊；n可分為隱式鏈接和顯式鏈接；可分為隱式鏈接和顯式鏈接；16隱式鏈接隱式鏈接 25123056749101181314151217181916212223202526272429303128filestartendjeep925目錄目錄101-1顯式鏈接顯式鏈接 012345物理塊號物理塊號2FCBFAT-1451缺點(diǎn)：缺點(diǎn)：n存取速度慢，不適于隨機(jī)存取存取速度慢，不適于隨機(jī)存取;

20、n可靠性問題，如指針出錯可靠性問題，如指針出錯;n更多的尋道次數(shù)和尋道時間更多的尋道次數(shù)和尋道時間;n鏈接指針占用一定的空間鏈接指針占用一定的空間;FAT16與與FAT32n在在FAT16的情況下，分區(qū)越大簇就相應(yīng)的要增大，存儲的情況下，分區(qū)越大簇就相應(yīng)的要增大，存儲效率就越低，勢必造成存儲空間的浪費(fèi)。效率就越低，勢必造成存儲空間的浪費(fèi)。nFAT32可以大大地節(jié)約磁盤空間。文件在磁盤上是以簇可以大大地節(jié)約磁盤空間。文件在磁盤上是以簇的方式存放的，簇里存放了一個文件就不能再存放另外的方式存放的，簇里存放了一個文件就不能再存放另外的文件。的文件。n假如一個磁盤的分區(qū)大小為假如一個磁盤的分區(qū)大小為5

21、12MB，基，基 于于FAT16的系統(tǒng)的系統(tǒng)的簇的大小為的簇的大小為8KB，而，而FAT32系統(tǒng)的簇的大小僅是系統(tǒng)的簇的大小僅是4KB，那么，現(xiàn)在我們存放一個那么，現(xiàn)在我們存放一個3KB的文件，的文件，F(xiàn)AT16系統(tǒng)就會有系統(tǒng)就會有5KB的空間的空間 被浪費(fèi)，而被浪費(fèi)，而FAT32的浪費(fèi)則會少一些。如果的浪費(fèi)則會少一些。如果分區(qū)達(dá)到分區(qū)達(dá)到1GB，F(xiàn)AT16的簇為的簇為16KB，而，而FAT32還是還是4KB，節(jié)省的也就更多了。節(jié)省的也就更多了。 FAT32FAT32是是FAT系列文件系統(tǒng)的最后一個產(chǎn)品，每個簇系列文件系統(tǒng)的最后一個產(chǎn)品，每個簇固定為固定為4KB ； n最大單文件大?。鹤畲髥挝?/p>

22、件大?。?GB (Fat16分區(qū)是分區(qū)是2 GB )n最大文件數(shù)量：最大文件數(shù)量： 268,435,437n最長檔名限制：最長檔名限制： 8.3或者長文件名或者長文件名255個字符個字符n最大卷大?。鹤畲缶泶笮。?8 TB（8*1024GB）（在）（在windows 2000和和windows XP環(huán)境下格式化程序只能創(chuàng)建最大環(huán)境下格式化程序只能創(chuàng)建最大32GB的的FAT32文件系統(tǒng)）文件系統(tǒng)） http:/ NT以及之后的以及之后的Windows 2000、Windows XP、Windows Server 2003、Windows Server 2008、Windows Vista和和Wi

23、ndows 7的標(biāo)準(zhǔn)文件的標(biāo)準(zhǔn)文件系統(tǒng)。系統(tǒng)。nNTFS采用了更小的簇，大小可由格式化命令或格式采用了更小的簇，大小可由格式化命令或格式化程序按磁盤容量和應(yīng)用需求來確定，可以更有效率化程序按磁盤容量和應(yīng)用需求來確定，可以更有效率地管理磁盤空間。地管理磁盤空間。nNTFS 提供長文件名、數(shù)據(jù)保護(hù)和恢復(fù)，并通過目錄提供長文件名、數(shù)據(jù)保護(hù)和恢復(fù)，并通過目錄和文件許可實(shí)現(xiàn)安全性。和文件許可實(shí)現(xiàn)安全性。NTFS 支持大硬盤和在多個支持大硬盤和在多個硬盤上存儲文件硬盤上存儲文件(稱為卷稱為卷)。n在在NTFS分區(qū)上分區(qū)上,可以為共享資源、文件夾以及文件設(shè)可以為共享資源、文件夾以及文件設(shè)置訪問許可權(quán)限。置訪

24、問許可權(quán)限。http:/ 一個文件的信息存放在若干不連續(xù)物理塊中，一個文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個文件建立一個專用數(shù)據(jù)結(jié)構(gòu)系統(tǒng)為每個文件建立一個專用數(shù)據(jù)結(jié)構(gòu)索引索引表，并將這些塊的塊號存放在一個索引表中；表，并將這些塊的塊號存放在一個索引表中；n索引分配方式支持直接訪問，當(dāng)要讀文件的第索引分配方式支持直接訪問，當(dāng)要讀文件的第i個盤塊時，可以方便地直接從索引塊中找到第個盤塊時，可以方便地直接從索引塊中找到第i個盤塊的盤塊號；個盤塊的盤塊號；123056749101181314151217181916212223202526272429303128countfile塊序號塊序號j

25、eep19目錄目錄91611025-1-1-119單級索引表的優(yōu)缺點(diǎn)單級索引表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：n即能順序存取，又能隨機(jī)存?。患茨茼樞虼嫒?，又能隨機(jī)存??；n滿足了文件動態(tài)增長、插入刪除的要求；滿足了文件動態(tài)增長、插入刪除的要求；n能充分利用外存空間；能充分利用外存空間；缺點(diǎn)：缺點(diǎn)：n索引表本身帶來了系統(tǒng)開銷索引表本身帶來了系統(tǒng)開銷, ,如：內(nèi)外存空間，如：內(nèi)外存空間，存取時間存取時間; ;例題例題 設(shè)一個文件占據(jù)了設(shè)一個文件占據(jù)了100個物理塊，對于連續(xù)結(jié)個物理塊，對于連續(xù)結(jié)構(gòu)、鏈接結(jié)構(gòu)和索引結(jié)構(gòu)的文件，如果要將一塊信構(gòu)、鏈接結(jié)構(gòu)和索引結(jié)構(gòu)的文件，如果要將一塊信息按下述要求操作，假設(shè)文件的文

26、件控制塊已經(jīng)在息按下述要求操作，假設(shè)文件的文件控制塊已經(jīng)在內(nèi)存，問分別要啟動多少次磁盤內(nèi)存，問分別要啟動多少次磁盤I/O操作？（鏈接操作？（鏈接方式使用單鏈表，無頭尾指針）方式使用單鏈表，無頭尾指針）（1）加一塊在文件的首部；）加一塊在文件的首部；（2）加一塊在文件中間（第）加一塊在文件中間（第51塊）；塊）；（3）加一塊在文件結(jié)尾。）加一塊在文件結(jié)尾。（1）在文件中的首部插入一塊，）在文件中的首部插入一塊，n連續(xù)結(jié)構(gòu)需要移動所有盤塊，共啟動磁盤連續(xù)結(jié)構(gòu)需要移動所有盤塊，共啟動磁盤200次，次，然后再啟動首部的盤塊，寫入插入內(nèi)容，所以是然后再啟動首部的盤塊，寫入插入內(nèi)容，所以是201次；次；n

27、鏈接文件需要啟動一個盤塊并把指針指向第一鏈接文件需要啟動一個盤塊并把指針指向第一個盤塊，所以是個盤塊，所以是1次；次；n索引文件需要啟動一個盤塊，然后在索引表中索引文件需要啟動一個盤塊，然后在索引表中添加指向該塊的指針，所以啟動盤塊添加指向該塊的指針，所以啟動盤塊1次；次；（2）在文件中間插入一塊，）在文件中間插入一塊，n連續(xù)結(jié)構(gòu)需要移動后面連續(xù)結(jié)構(gòu)需要移動后面50個盤塊，共啟動磁盤個盤塊，共啟動磁盤100次，然后再啟動中間盤塊，寫入插入內(nèi)容，次，然后再啟動中間盤塊，寫入插入內(nèi)容，所以是所以是101次；次；n鏈接文件需要先啟動一次盤塊寫入新內(nèi)容，然鏈接文件需要先啟動一次盤塊寫入新內(nèi)容，然后啟動

28、前后啟動前50個盤塊，并把第個盤塊，并把第50盤塊指針指向新盤盤塊指針指向新盤塊，啟動新盤塊，指針指向第塊，啟動新盤塊，指針指向第51盤塊，共盤塊，共52次；次；n索引文件需要啟動一個盤塊，然后在索引表中索引文件需要啟動一個盤塊，然后在索引表中添加指向該塊的指針，所以啟動盤塊添加指向該塊的指針，所以啟動盤塊1次；次；（3）在文件尾部插入一塊，）在文件尾部插入一塊，n直接將主存信息寫入磁盤，所以是直接將主存信息寫入磁盤，所以是1次；次；n鏈接文件需要先啟動鏈接文件需要先啟動1次盤塊寫入新內(nèi)容，然后次盤塊寫入新內(nèi)容，然后啟動前啟動前100個盤塊，并修改第個盤塊，并修改第100盤塊指針，共盤塊指針，

29、共101次；次；n索引文件需要啟動一個盤塊，然后在索引表中索引文件需要啟動一個盤塊，然后在索引表中添加指向該塊的指針，所以啟動盤塊添加指向該塊的指針，所以啟動盤塊1次；次；思考？思考？n對于一個磁盤上的文件系統(tǒng)，文件的物理結(jié)構(gòu)可對于一個磁盤上的文件系統(tǒng)，文件的物理結(jié)構(gòu)可以采用連續(xù)、鏈接和索引文件的方式。如果當(dāng)前位以采用連續(xù)、鏈接和索引文件的方式。如果當(dāng)前位于邏輯塊于邏輯塊10，且希望訪問邏輯塊，且希望訪問邏輯塊4，那么，必須分，那么，必須分別從盤上讀幾個物理塊？別從盤上讀幾個物理塊？n連續(xù)方式，需要讀連續(xù)方式，需要讀1個物理塊；個物理塊；n鏈接方式，需要讀鏈接方式，需要讀5個物理塊；個物理塊；

30、n索引方式，需要讀索引方式，需要讀2個物理塊；個物理塊；多級索引分配多級索引分配將一個大文件的所有索引表（二級索引將一個大文件的所有索引表（二級索引) )的地址的地址放在另一個索引表（一級索引放在另一個索引表（一級索引) )中；中；01210510625435635798510510625474035635711259853607401125主索引主索引360第二級索引第二級索引磁盤空間磁盤空間n如每個盤塊的大小為如每個盤塊的大小為1KB，每個盤塊號占，每個盤塊號占4個字節(jié)，個字節(jié)，則一個索引塊中可存放則一個索引塊中可存放256個盤塊號；個盤塊號；n兩級索引表，最多可包含的存放文件的盤塊的盤兩

31、級索引表，最多可包含的存放文件的盤塊的盤塊號總數(shù)塊號總數(shù)N=256*256=64K個盤塊號；個盤塊號；n采用兩級索引時，允許的文件最大長度為采用兩級索引時，允許的文件最大長度為64MB；n倘若盤塊大小為倘若盤塊大小為4KB，一級索引和二級索引所允，一級索引和二級索引所允許的最大文件長度可達(dá)多大？許的最大文件長度可達(dá)多大？modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatad

32、atadatadatadatadatadata混合索引分配方式混合索引分配方式n直接地址直接地址在索引結(jié)點(diǎn)中可設(shè)置在索引結(jié)點(diǎn)中可設(shè)置10個直接地址項，即用個直接地址項，即用iaddr(0)iaddr(9)來存放直接地址。在這里的每項中來存放直接地址。在這里的每項中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號；所存放的是該文件數(shù)據(jù)的盤塊的盤塊號；n一次間接地址一次間接地址地址項地址項iaddr(10)來提供一次間接地址。實(shí)質(zhì)就是一級來提供一次間接地址。實(shí)質(zhì)就是一級索引分配方式；索引分配方式；n多次間接地址多次間接地址地址項地址項iaddr(11)提供二次間接地址。該方式的實(shí)質(zhì)是提供二次間接地址。該方式的實(shí)

33、質(zhì)是兩級索引分配方式；兩級索引分配方式；采用混合索引方式，假如每個盤塊大小為采用混合索引方式，假如每個盤塊大小為4KB，盤塊，盤塊號占用號占用4B；n直接地址可尋址的最大范圍為直接地址可尋址的最大范圍為40K（10*4K）n一次間接地址可尋址的最大范圍為一次間接地址可尋址的最大范圍為4M（1K*4K）n二次間接地址可尋址的最大范圍為二次間接地址可尋址的最大范圍為4G（1K*1K*4K）n三次間接地址可尋址的最大范圍為三次間接地址可尋址的最大范圍為4T（1K*1K*1K*4K）n目錄：所有文件控制塊目錄：所有文件控制塊(FCB)組織在一起，就構(gòu)組織在一起，就構(gòu)成了文件目錄，即文件控制塊的有序集合

34、成了文件目錄，即文件控制塊的有序集合;n目錄項：構(gòu)成文件目錄的項目目錄項：構(gòu)成文件目錄的項目(目錄項就是目錄項就是FCB)n目錄文件：為了實(shí)現(xiàn)對文件目錄的管理，通常目錄文件：為了實(shí)現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件；就叫目錄文件；目錄管理目錄管理filestart lengthcount02tr143mail196list284f62目錄目錄文件控制塊（文件控制塊（FCB）n是是OS為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息；理文件所需的所有有關(guān)信息；

35、n文件控制塊是文件存在的標(biāo)志；文件控制塊是文件存在的標(biāo)志；n文件控制塊的內(nèi)容：文件控制塊的內(nèi)容： 基本信息基本信息存取控制信息存取控制信息使用信息使用信息文文件件名名擴(kuò)擴(kuò)展展名名屬屬性性備備用用時時間間日日期期第第一一塊塊號號盤盤塊塊數(shù)數(shù)索引結(jié)點(diǎn)索引結(jié)點(diǎn)文件名文件名索引結(jié)點(diǎn)編號索引結(jié)點(diǎn)編號文件名文件名1文件名文件名2n把文件名與文件描述信息分開，使文件描述信息單把文件名與文件描述信息分開，使文件描述信息單獨(dú)形成一個稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡稱獨(dú)形成一個稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡稱i結(jié)點(diǎn)。結(jié)點(diǎn)。n在文件目錄中的每個目錄項僅由文件名和指向所對在文件目錄中的每個目錄項僅由文件名和指向所對應(yīng)的應(yīng)的i結(jié)

36、點(diǎn)的指針構(gòu)成；結(jié)點(diǎn)的指針構(gòu)成；UNIX的文件目錄的文件目錄n磁盤索引結(jié)點(diǎn)磁盤索引結(jié)點(diǎn)磁盤上的索引結(jié)點(diǎn)磁盤上的索引結(jié)點(diǎn)l每個文件有唯一的一個磁盤索引結(jié)點(diǎn)；每個文件有唯一的一個磁盤索引結(jié)點(diǎn)；l包括：主標(biāo)識符、類型、存取權(quán)限、物理地址、長包括：主標(biāo)識符、類型、存取權(quán)限、物理地址、長度、連接計數(shù)、存取時間；度、連接計數(shù)、存取時間；n內(nèi)存索引結(jié)點(diǎn)內(nèi)存索引結(jié)點(diǎn)內(nèi)存的中索引結(jié)點(diǎn)內(nèi)存的中索引結(jié)點(diǎn)l當(dāng)文件被打開時，將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存的索當(dāng)文件被打開時，將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存的索引結(jié)點(diǎn)中引結(jié)點(diǎn)中;l增加如增加如 下的內(nèi)容：索引結(jié)點(diǎn)編號、狀態(tài)、訪問計數(shù)、下的內(nèi)容：索引結(jié)點(diǎn)編號、狀態(tài)、訪問計數(shù)、文件所屬文件系

37、統(tǒng)的邏輯設(shè)備號、鏈接指針。文件所屬文件系統(tǒng)的邏輯設(shè)備號、鏈接指針。例題例題n在實(shí)現(xiàn)文件系統(tǒng)時，為加快文件目錄的檢索速度，可利在實(shí)現(xiàn)文件系統(tǒng)時，為加快文件目錄的檢索速度，可利用用“文件控制塊分解法文件控制塊分解法”。假設(shè)目錄存放在磁盤上，每。假設(shè)目錄存放在磁盤上，每個盤塊個盤塊512字節(jié)，文件控制塊占字節(jié)，文件控制塊占64字節(jié)，其中文件名占字節(jié)，其中文件名占8字節(jié)，通常將文件控制塊分解成兩部分，第一部分占字節(jié)，通常將文件控制塊分解成兩部分，第一部分占10字節(jié)（包括文件名和文件內(nèi)部號），第二部分占字節(jié)（包括文件名和文件內(nèi)部號），第二部分占54字節(jié)字節(jié)（包括文件內(nèi)部號和文件其他描述信息）。（包括文件

38、內(nèi)部號和文件其他描述信息）。n假定某一目錄文件共有假定某一目錄文件共有254個文件控制塊，試分別給出個文件控制塊，試分別給出采用分解法前和分解法后，查找該目錄的某一個文件控采用分解法前和分解法后，查找該目錄的某一個文件控制塊的平均訪問磁盤次數(shù)。制塊的平均訪問磁盤次數(shù)。n采用分解法前采用分解法前n一個盤塊存放一個盤塊存放512/64=8個目錄項，個目錄項，254個目錄項需要個目錄項需要32個盤塊；個盤塊；n查找一個文件的平均訪問盤塊數(shù)：查找一個文件的平均訪問盤塊數(shù)：(1+32)/2=16.5次；次；n采用分解法后采用分解法后n一個盤塊存放一個盤塊存放512/10=51個目錄項，個目錄項，254個

39、目錄項需要個目錄項需要5個盤塊；個盤塊；n查找文件的第一部分的平均訪問盤塊數(shù)查找文件的第一部分的平均訪問盤塊數(shù)：(1+5)/2=3次；次；n查找第二部分需要訪問磁盤查找第二部分需要訪問磁盤1次，所以查找一個文件控次，所以查找一個文件控制塊的平均訪問磁盤次數(shù)是制塊的平均訪問磁盤次數(shù)是3+1=4次；次；單級目錄結(jié)構(gòu)單級目錄結(jié)構(gòu) 文件名文件名物理地址物理地址文件說明文件說明狀態(tài)位狀態(tài)位文件名文件名1文件名文件名2在整個文件系統(tǒng)中只建立一張目錄表，每個文件占在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項，目錄項中含有文件名、文件擴(kuò)展名、一個目錄項，目錄項中含有文件名、文件擴(kuò)展名、文件長度、文件

40、類型、文件物理地址以及其他文件文件長度、文件類型、文件物理地址以及其他文件屬性。屬性。n優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡單且能實(shí)現(xiàn)目錄管理的基本功能簡單且能實(shí)現(xiàn)目錄管理的基本功能按名存??；按名存??；n缺點(diǎn)：缺點(diǎn)：(1) 查找速度慢；查找速度慢； (2) 不允許重名；不允許重名； (3) 不便于實(shí)現(xiàn)文件共享；不便于實(shí)現(xiàn)文件共享； 兩級目錄兩級目錄目錄分為兩級：目錄分為兩級：n一級稱為主文件目錄一級稱為主文件目錄MFD，每個用戶目錄文件，每個用戶目錄文件都占有一個目錄項，包含用戶名和指向該用戶子都占有一個目錄項，包含用戶名和指向該用戶子目錄的指針；目錄的指針；n二級稱為用戶文件目錄二級稱為用戶文件目錄UFD(又稱用

41、戶子目錄又稱用戶子目錄)，給出該用戶所有文件的給出該用戶所有文件的FCB；用戶名用戶名WangZhangGao指向子目錄指針指向子目錄指針Wang用戶目錄用戶目錄AlphaTestAlphaTestReportTestZhang用戶目錄用戶目錄ReportTestGao用戶目錄用戶目錄BetaDeviceMisxBetaDeviceMisx優(yōu)點(diǎn)：優(yōu)點(diǎn)：(1)提高了檢索目錄的速度；提高了檢索目錄的速度； (2)在不同的用戶目錄中，可使用相同的文件名；在不同的用戶目錄中，可使用相同的文件名；(3)不同用戶還可使用不同的文件名來訪問系統(tǒng)中不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個共享文件；的同

42、一個共享文件； 多級目錄結(jié)構(gòu)（樹型目錄）多級目錄結(jié)構(gòu)（樹型目錄）n多級目錄結(jié)構(gòu)又稱為樹型目錄結(jié)構(gòu)；多級目錄結(jié)構(gòu)又稱為樹型目錄結(jié)構(gòu)；n主目錄稱為根目錄，數(shù)據(jù)文件稱為樹葉，其主目錄稱為根目錄，數(shù)據(jù)文件稱為樹葉，其他目錄均作為樹的結(jié)點(diǎn)；他目錄均作為樹的結(jié)點(diǎn)；ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89路徑名路徑名n在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條惟一的通路。系統(tǒng)中的每一個文件都有都只有一條惟一的通路。系統(tǒng)中的每一個文件都有惟一的路徑名。惟一的路徑名。n從樹的根從樹的根(

43、即主目錄即主目錄)開始，把全部目錄文件名與數(shù)開始，把全部目錄文件名與數(shù)據(jù)文件名，依次地用據(jù)文件名，依次地用“/”連接起來，構(gòu)成該數(shù)據(jù)文連接起來，構(gòu)成該數(shù)據(jù)文件的路徑名件的路徑名(path name);n從樹根開始的路徑名稱為絕對路徑名從樹根開始的路徑名稱為絕對路徑名(absolute path name)。當(dāng)前目錄當(dāng)前目錄n從當(dāng)前目錄開始，逐級經(jīng)過中間的目錄文件，從當(dāng)前目錄開始，逐級經(jīng)過中間的目錄文件，最后到達(dá)要訪問的數(shù)據(jù)文件。這一路徑上的全部最后到達(dá)要訪問的數(shù)據(jù)文件。這一路徑上的全部目錄文件名與數(shù)據(jù)文件名用目錄文件名與數(shù)據(jù)文件名用“/”連接形成路徑名。連接形成路徑名。n從當(dāng)前目錄開始直到數(shù)據(jù)

44、文件為止所構(gòu)成的路從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名，稱為相對路徑名徑名，稱為相對路徑名(relative path name)；目錄查詢技術(shù)目錄查詢技術(shù)n戶用訪問一個已存在的文件，系統(tǒng)首先利用用戶戶用訪問一個已存在的文件，系統(tǒng)首先利用用戶提供的文件名對目錄進(jìn)行查詢，找出該文件的文提供的文件名對目錄進(jìn)行查詢，找出該文件的文件控制塊或?qū)?yīng)索引結(jié)點(diǎn)；件控制塊或?qū)?yīng)索引結(jié)點(diǎn)；n根據(jù)根據(jù)FCB或索引結(jié)點(diǎn)中所記錄的文件物理地址或索引結(jié)點(diǎn)中所記錄的文件物理地址(盤盤塊號塊號)，換算出文件在磁盤上的物理地址；，換算出文件在磁盤上的物理地址；n再通過磁盤驅(qū)動程序?qū)⑺栉募x入內(nèi)存；再通過磁盤驅(qū)動程序

45、將所需文件讀入內(nèi)存；（1）線性檢索法）線性檢索法n又稱順序檢索法；又稱順序檢索法；n在單級目錄中，利用用戶提供的文件名，用順在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄中找到指名文件的目錄序查找法直接從文件目錄中找到指名文件的目錄項；項；n在樹型目錄中，用戶提供的文件名是由多個文在樹型目錄中，用戶提供的文件名是由多個文件分量名組成的路徑名，對多級目錄進(jìn)行查找；件分量名組成的路徑名，對多級目錄進(jìn)行查找；查找查找/usr/ast/mbox的步驟的步驟例題例題 某文件系統(tǒng)中，根目錄長駐內(nèi)存。某文件系統(tǒng)中，根目錄長駐內(nèi)存。目錄文件采用鏈接結(jié)構(gòu)，普通文件采用目錄文件采用鏈接結(jié)構(gòu)，普通文

46、件采用三級索引結(jié)構(gòu)。三級索引結(jié)構(gòu)。 假設(shè)一個物理塊放假設(shè)一個物理塊放10個目錄項，一個個目錄項，一個目錄下最多放目錄下最多放40個文件。如果下級文件個文件。如果下級文件是目錄文件，則上級目錄項指向該目錄是目錄文件，則上級目錄項指向該目錄文件的首地址；如果下級文件是普通文文件的首地址；如果下級文件是普通文件，則上級目錄項指向該文件的文件控件，則上級目錄項指向該文件的文件控制塊。制塊。 假設(shè)索引表地址放在假設(shè)索引表地址放在FCB中，如果中，如果要讀取要讀取K的某一塊，需要啟動硬盤最少的某一塊，需要啟動硬盤最少幾次，最多幾次？（假設(shè)文件按自左向幾次，最多幾次？（假設(shè)文件按自左向右的順序建立）右的順序

47、建立）ROOTABCDEFGHIJK. .ADGHK讀讀ADGHK的某一塊的某一塊 因為目錄文件采用鏈接形式因為目錄文件采用鏈接形式, 每個磁盤塊存每個磁盤塊存放放10個下級文件的描述個下級文件的描述, 一個目錄下最多存放一個目錄下最多存放40個下級文件，故一個目錄文件最多占個下級文件，故一個目錄文件最多占4個物個物理塊。根目錄文件已在內(nèi)存，故不必啟動硬理塊。根目錄文件已在內(nèi)存，故不必啟動硬盤讀入它。盤讀入它。 最少最少 最多最多n根目錄文件根目錄文件nA目錄文件目錄文件 1次次 4次次nD目錄文件目錄文件 1次次 4次次nG目錄文件目錄文件 1次次 4次次nH目錄文件目錄文件 1次次 4次次

48、nK文件控制塊文件控制塊 1次次 1次次nK文件某一塊文件某一塊 4次次 4次次 共共 9次次 21次次ROOTABCDEFGHIJK. .（2）Hash方法方法n系統(tǒng)利用用戶提供的文件名并將它變換為文件系統(tǒng)利用用戶提供的文件名并將它變換為文件目錄的索引值；目錄的索引值；n再利用該索引值到目錄中去查找，提高檢索速再利用該索引值到目錄中去查找，提高檢索速度；度；文件存儲空間的管理文件存儲空間的管理n空閑分區(qū)表法空閑分區(qū)表法n空閑分區(qū)鏈法空閑分區(qū)鏈法n位示圖法位示圖法n成組鏈接法成組鏈接法空閑塊表空閑塊表n屬于連續(xù)分配方式，為每個文件分配一塊連續(xù)的存屬于連續(xù)分配方式，為每個文件分配一塊連續(xù)的存儲空

49、間；儲空間； n系統(tǒng)為外存上所有空閑區(qū)建立一張空閑表，每個空系統(tǒng)為外存上所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個空閑表項，其中包括表項序號、該空閑區(qū)對應(yīng)于一個空閑表項，其中包括表項序號、該空閑區(qū)的第一個盤塊號、該區(qū)的空閑盤塊數(shù)等信息；閑區(qū)的第一個盤塊號、該區(qū)的空閑盤塊數(shù)等信息；序號序號第一空閑盤塊號第一空閑盤塊號空閑盤塊數(shù)空閑盤塊數(shù)12429331554n空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，采用首次空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等；適應(yīng)算法、循環(huán)首次適應(yīng)算法等；n在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順

50、序地檢索空閑表的各表項，直至找到第一個其大小能滿地檢索空閑表的各表項，直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶足要求的空閑區(qū)，再將該盤區(qū)分配給用戶( (進(jìn)程進(jìn)程) )，同，同時修改空閑表。時修改空閑表。存儲空間的分配存儲空間的分配n系統(tǒng)在對用戶所釋放的存儲空間進(jìn)行回收時，也采系統(tǒng)在對用戶所釋放的存儲空間進(jìn)行回收時，也采取類似于內(nèi)存回收的方法，即要取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并；以合并； 存儲空間的回收存儲空間的回收空閑鏈表法空閑鏈表法 將所有空

51、閑區(qū)拉成一條空閑鏈，可分為：將所有空閑區(qū)拉成一條空閑鏈，可分為：n空閑盤塊鏈空閑盤塊鏈將磁盤上的所有空閑空間，以盤塊為單位拉成一將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈；條鏈；n空閑盤區(qū)鏈空閑盤區(qū)鏈 將磁盤上的所有空閑空盤區(qū)（每個盤區(qū)可包含若將磁盤上的所有空閑空盤區(qū)（每個盤區(qū)可包含若干個盤塊），拉成一條鏈；干個盤塊），拉成一條鏈；1234567891011 12 13 1415161120001110010011020001111110000111311100011111100004.16位圖法位圖法n用一串二進(jìn)制位反映磁盤空間中分配使用情況用一串二進(jìn)制位反映磁盤空間中分配使用情況, 每

52、個物每個物理塊對應(yīng)一位理塊對應(yīng)一位, 分配物理塊為分配物理塊為1，否則為，否則為0；n申請物理塊時，可以在位示圖中查找為申請物理塊時，可以在位示圖中查找為0的位，返回對的位，返回對應(yīng)物理塊號；應(yīng)物理塊號；n歸還時；將對應(yīng)位轉(zhuǎn)置歸還時；將對應(yīng)位轉(zhuǎn)置0盤塊的分配盤塊的分配 n順序掃描位示圖，從中找出一個或一組其值為順序掃描位示圖，從中找出一個或一組其值為“0”的二進(jìn)制位的二進(jìn)制位(“0”表示空閑時表示空閑時)；n將所找到的一個或一組二進(jìn)制位，轉(zhuǎn)換成與之相將所找到的一個或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位，的二進(jìn)制位，位于位示的第位于位

53、示的第i行、第行、第j列，則其相應(yīng)的盤塊號應(yīng)按列，則其相應(yīng)的盤塊號應(yīng)按下式計算：下式計算： b=n(i-1)+j， n代表每行的位數(shù)；代表每行的位數(shù)；n修改位示圖，修改位示圖， 令令mapi,j=1；盤塊的回收盤塊的回收 n將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。列號。 轉(zhuǎn)換公式為：轉(zhuǎn)換公式為： i=(b-1)DIV n+1 j=(b-1)MOD n+1n修改位示圖。令修改位示圖。令map i,j=1； 成組鏈接法成組鏈接法 UNIX系統(tǒng)采用的空閑盤塊管理方法，把空閑塊分成若干系統(tǒng)采用的空閑盤塊管理方法，把空閑塊分成若干組，把指向一組中各空閑塊的指

54、針集中在一起。組，把指向一組中各空閑塊的指針集中在一起。1004003993013001003002992022012991004003992013019907999790179007899780179997901空閑盤空閑盤塊號棧塊號棧S.free019899n首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格；給用戶，然后將棧頂指針下移一格；n若該盤塊號已是棧底，即若該盤塊號已是棧底，即S.free(0)，將棧底盤塊號，將棧底盤塊號所對應(yīng)盤

55、塊的內(nèi)容讀入棧中，作為新的盤塊號棧的所對應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號棧的內(nèi)容；把原棧底對應(yīng)的盤塊分配出去內(nèi)容；把原棧底對應(yīng)的盤塊分配出去(其中的有用其中的有用數(shù)據(jù)已讀入棧中數(shù)據(jù)已讀入棧中)；n再分配一相應(yīng)的緩沖區(qū)再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū)作為該盤塊的緩沖區(qū))。最。最后，把棧中的空閑盤塊數(shù)減后，把棧中的空閑盤塊數(shù)減1并返回。并返回。 空閑盤塊的分配空閑盤塊的分配n將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，并執(zhí)行空閑盤塊數(shù)加并執(zhí)行空閑盤塊數(shù)加1操作。操作。n當(dāng)棧中空閑盤塊號數(shù)目已達(dá)當(dāng)棧中空閑盤塊號數(shù)目已達(dá)100時，表示棧已滿，時，表示

56、棧已滿，便將現(xiàn)有棧中的便將現(xiàn)有棧中的100個盤塊號，記入新回收的盤塊個盤塊號，記入新回收的盤塊中，再將其盤塊號作為新棧底。中，再將其盤塊號作為新棧底。 空閑盤塊的回收空閑盤塊的回收例題例題nUNIX系統(tǒng)采用空閑塊成組鏈接的方法管理磁系統(tǒng)采用空閑塊成組鏈接的方法管理磁盤空閑空間，如圖所示。問此事若一個文件盤空閑空間，如圖所示。問此事若一個文件A需要需要5個盤塊，則系統(tǒng)會將哪些盤塊分配給它？個盤塊，則系統(tǒng)會將哪些盤塊分配給它？若之后有個文件若之后有個文件B被刪除，它占用的盤塊號為被刪除，它占用的盤塊號為333，334，404，405，782，則回收這些盤塊，則回收這些盤塊后，專用塊的內(nèi)容如何？后，

57、專用塊的內(nèi)容如何？空閑塊數(shù)空閑塊數(shù)450495612.空閑塊數(shù)空閑塊數(shù)100150149.5251空閑塊數(shù)空閑塊數(shù)1000449.352.專用塊專用塊50*150*解：解：n從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。所以在專用塊中可獲得然后將棧頂指針下移一格。所以在專用塊中可獲得12、56、49、50塊；塊；n盤塊號盤塊號50已是棧底，即已是棧底，即S.free(0)，須調(diào)用磁盤讀過程，將棧，須調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，再分配一相應(yīng)的盤塊，底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，再分配一

58、相應(yīng)的盤塊，分配分配51號盤塊；號盤塊；n文件文件A得到第得到第12、56、49、50和和51塊。塊?？臻e塊數(shù)空閑塊數(shù)450495612.空閑塊數(shù)空閑塊數(shù)100150149.5251空閑塊數(shù)空閑塊數(shù)1000449.352.專用塊專用塊50*n將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，記錄塊將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，記錄塊號號333，并執(zhí)行空閑盤塊數(shù)加，并執(zhí)行空閑盤塊數(shù)加1操作；操作；n當(dāng)棧中空閑盤塊號數(shù)目已達(dá)當(dāng)棧中空閑盤塊號數(shù)目已達(dá)100時，表示棧已滿，便將時，表示棧已滿，便將現(xiàn)有棧中的現(xiàn)有棧中的100個盤塊號，記入新回收的盤塊中，再將個盤塊號，記入新回收的盤塊中，再將其盤塊號

59、作為新棧底。其盤塊號作為新棧底。n然后專用塊中依次記錄塊號：然后專用塊中依次記錄塊號：334，404，405，782空閑塊數(shù)空閑塊數(shù)4.空閑塊數(shù)空閑塊數(shù)150149.52空閑塊數(shù)空閑塊數(shù)1000449.352.專用塊專用塊33333440440578299100334*n基于索引結(jié)點(diǎn)的共享方式基于索引結(jié)點(diǎn)的共享方式n利用符號鏈實(shí)現(xiàn)文件共享利用符號鏈實(shí)現(xiàn)文件共享文件共享與文件保護(hù)文件共享與文件保護(hù)AABBBBBCCCCC根目錄根目錄?CCCn在樹型結(jié)構(gòu)目錄中，當(dāng)有兩個或多個用戶要共在樹型結(jié)構(gòu)目錄中，當(dāng)有兩個或多個用戶要共享一個子目錄或文件時，必須將共享文件或子目享一個子目錄或文件時，必須將共享文件或子目錄鏈接到兩個或多個用戶的目錄中，才能方便地錄鏈接到兩個或多個用戶的目錄中，才能方便地找到該文件。找到該文件。基于索引結(jié)點(diǎn)的共享方式基于索引結(jié)點(diǎn)的共享方式n引入索引結(jié)點(diǎn)，將文件的物理地址及其它的文件屬引入索引結(jié)點(diǎn)，將文件的物理地址及其它的文件屬性等信息，不再放在目錄項中，而是放在索引結(jié)點(diǎn)性等信息，不再放在目錄項中，而是放在索引結(jié)點(diǎn)中，文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點(diǎn)中，文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點(diǎn)的指針。的