1、磁盤設(shè)備驅(qū)動程序磁盤設(shè)備驅(qū)動程序磁帶設(shè)備驅(qū)動程序磁帶設(shè)備驅(qū)動程序基本文件系統(tǒng)（物理基本文件系統(tǒng)（物理I/O層）層）基本基本I/O管理程序管理程序邏輯邏輯I/O堆堆順序順序索引順序索引順序索引索引哈希哈希用戶程序用戶程序結(jié)構(gòu)結(jié)構(gòu)u設(shè)備驅(qū)動程序：設(shè)備驅(qū)動程序：負責啟動該設(shè)備上的負責啟動該設(shè)備上的I/O操作，處理操作，處理I/O請求的完成請求的完成u基本文件系統(tǒng)（物理基本文件系統(tǒng)（物理I/O層）：層）：處理與磁盤或磁帶交換處理與磁盤或磁帶交換的的數(shù)據(jù)塊。數(shù)據(jù)塊。u注重的是這些塊在外存設(shè)備中的位置，而并不知道該文件所涉及的注重的是這些塊在外存設(shè)備中的位置，而并不知道該文件所涉及的數(shù)據(jù)或結(jié)構(gòu)的內(nèi)容。數(shù)據(jù)

2、或結(jié)構(gòu)的內(nèi)容。u基本基本I/O管理程序：管理程序：負責所有文件負責所有文件I/O的開始或結(jié)束。選的開始或結(jié)束。選擇執(zhí)行文件的擇執(zhí)行文件的I/O設(shè)備，外存的分配，設(shè)備，外存的分配，I/O緩沖區(qū)的指定緩沖區(qū)的指定u邏輯邏輯I/O：使用戶和應用程序能夠訪問到使用戶和應用程序能夠訪問到記錄記錄。u物理物理I/O層處理的是數(shù)據(jù)塊，邏輯層處理的是數(shù)據(jù)塊，邏輯I/O處理的是文件記錄。它提供一處理的是文件記錄。它提供一種通用的記錄種通用的記錄I/O的能力。的能力。u訪問方法層訪問方法層 ：與用戶最近的一層。在應用程序和文件與用戶最近的一層。在應用程序和文件系統(tǒng)及保存數(shù)據(jù)的設(shè)備之間提供了一種標準接口。系統(tǒng)及保存

3、數(shù)據(jù)的設(shè)備之間提供了一種標準接口。u不同的訪問方法反映出不同的文件結(jié)構(gòu)和訪問數(shù)據(jù)的不同方法。不同的訪問方法反映出不同的文件結(jié)構(gòu)和訪問數(shù)據(jù)的不同方法。結(jié)構(gòu)結(jié)構(gòu)u為了實現(xiàn)用戶對文件的按名存取，系統(tǒng)要對目錄進行查詢?yōu)榱藢崿F(xiàn)用戶對文件的按名存取，系統(tǒng)要對目錄進行查詢，找出該文件的文件控制塊或者索引節(jié)點，進而找到該文，找出該文件的文件控制塊或者索引節(jié)點，進而找到該文件的物理地址。件的物理地址。u線性列表：線性列表：順序檢索法。目錄文件由目錄項構(gòu)成一個線順序檢索法。目錄文件由目錄項構(gòu)成一個線性表，每個目錄項包括文件名和執(zhí)行數(shù)據(jù)塊的指針。性表，每個目錄項包括文件名和執(zhí)行數(shù)據(jù)塊的指針。u創(chuàng)建新文件：創(chuàng)建新文件

4、：檢索該目錄，檢查是否同名，沒有同檢索該目錄，檢查是否同名，沒有同名，則將新文件的目錄項添加到目錄末尾名，則將新文件的目錄項添加到目錄末尾u刪除文件時：刪除文件時：檢索目錄找到該目錄項，然后釋放分檢索目錄找到該目錄項，然后釋放分配給它的全部空間，并且清空該項配給它的全部空間，并且清空該項u評價：評價：簡單易行、速度慢。簡單易行、速度慢。改善：改善：使用緩存來存放使用緩存來存放最近用過的目錄信息。將目錄排序，使用二分檢索最近用過的目錄信息。將目錄排序，使用二分檢索法，縮短平均查找時間，但會使文件的創(chuàng)建和刪除法，縮短平均查找時間，但會使文件的創(chuàng)建和刪除變得復雜變得復雜u哈希表：哈希表：利用線性表存

5、放目錄項，利用哈息表進行檢索利用線性表存放目錄項，利用哈息表進行檢索。哈希表根據(jù)文件名得到一個值，并返回一個指向線性。哈希表根據(jù)文件名得到一個值，并返回一個指向線性列表中的元素的指針。列表中的元素的指針。u沖突問題：沖突問題：兩個文件名相同的哈希值。兩個文件名相同的哈希值。u目錄目錄u目錄文件目錄文件文件名文件類型外存地址作業(yè)目錄文件軟件目錄文件娛樂目錄文件F1數(shù)據(jù)文件根目錄文件的內(nèi)容：根目錄文件的內(nèi)容：文件名文件類型外存地址C目錄文件OS目錄文件F1.C數(shù)據(jù)文件F2.C數(shù)據(jù)文件OS1數(shù)據(jù)文件作業(yè)目錄文件的內(nèi)容：作業(yè)目錄文件的內(nèi)容：u連續(xù)分配連續(xù)分配u鏈式分配鏈式分配u索引分配索引分配u連續(xù)分

6、配：連續(xù)分配：創(chuàng)建文件時，分配一組連續(xù)的塊；創(chuàng)建文件時，分配一組連續(xù)的塊；FAT中每個文件只要一中每個文件只要一項，說明起始塊和文件的長度。項，說明起始塊和文件的長度。對順序文件有利對順序文件有利。u優(yōu)點優(yōu)點: :u 簡單。適用于一次性寫入的操作簡單。適用于一次性寫入的操作 u 支持順序存取和隨機存取，順序存取速度快支持順序存取和隨機存取，順序存取速度快 u 所需的磁盤尋道次數(shù)和尋道時間最少（因為由于空間的所需的磁盤尋道次數(shù)和尋道時間最少（因為由于空間的連續(xù)性，當訪問下一個磁盤塊時，一般無需移動磁頭，當連續(xù)性，當訪問下一個磁盤塊時，一般無需移動磁頭，當需要磁頭移動，只需要移動一個磁道。需要磁頭

7、移動，只需要移動一個磁道。u缺點缺點: :u文件不能動態(tài)增長（可能文件末尾處的空塊已經(jīng)分配給別文件不能動態(tài)增長（可能文件末尾處的空塊已經(jīng)分配給別的文件）的文件）u不利于文件插入和刪除不利于文件插入和刪除u外部碎片問題（反復增刪文件后），外部碎片問題（反復增刪文件后），使得很難找到空間大使得很難找到空間大小足夠的連續(xù)塊。進行緊縮小足夠的連續(xù)塊。進行緊縮u在創(chuàng)建文件時聲明文件的大小。在創(chuàng)建文件時聲明文件的大小。u鏈式分配：鏈式分配：一個文件的信息存放在若干不連續(xù)的物理一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下塊中，各塊之間通過指針連接，前一個物理塊指向下一個

8、物理塊。一個物理塊。FATFAT中每個文件同樣只需要一項，包括中每個文件同樣只需要一項，包括文件名、起始塊號和最后塊號。任何一個自由塊都可文件名、起始塊號和最后塊號。任何一個自由塊都可以加入到鏈中。以加入到鏈中。 u優(yōu)點：優(yōu)點：u提高了磁盤空間利用率提高了磁盤空間利用率, ,不存在外部碎片問題不存在外部碎片問題u有利于文件插入和刪除有利于文件插入和刪除u有利于文件動態(tài)擴充有利于文件動態(tài)擴充u 缺點：缺點：u存取速度慢，一般僅適于對信息的順序存取，存取速度慢，一般僅適于對信息的順序存取，不適于隨機不適于隨機存取存取: :查找某一個塊必須從頭開始沿指針進行。查找某一個塊必須從頭開始沿指針進行。u可

9、靠性問題，如指針出錯；更多的尋道次數(shù)和尋道時間可靠性問題，如指針出錯；更多的尋道次數(shù)和尋道時間u鏈接指針占用一定的空間，將多個塊組成簇（鏈接指針占用一定的空間，將多個塊組成簇（clustercluster），），按簇進行分配而不是按塊進行分配（增加了磁盤碎片）。按簇進行分配而不是按塊進行分配（增加了磁盤碎片）。使用FAT文件分配表法鏈接分配的變種，如MS-DOS和OS/2。見教材P312u一個已經(jīng)打開的連續(xù)文件，要讀取其第一個已經(jīng)打開的連續(xù)文件，要讀取其第1010號數(shù)號數(shù)據(jù)塊，則需要據(jù)塊，則需要_次次I/OI/O操作；對于鏈式文件操作；對于鏈式文件需要需要_次次I/OI/O操作？操作？u 設(shè)某

10、個文件為鏈式文件，由設(shè)某個文件為鏈式文件，由5 5個邏輯記錄組成個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊大小相等，均，每個邏輯記錄的大小與磁盤塊大小相等，均為為512512字節(jié)，并依次存放在字節(jié)，并依次存放在5050、121121、7575、8080、6363號磁盤塊上。若要存取文件的第號磁盤塊上。若要存取文件的第15691569邏輯字邏輯字節(jié)處的信息，問要訪問哪一個磁盤塊？節(jié)處的信息，問要訪問哪一個磁盤塊？u索引分配：索引分配：每個文件在每個文件在FAT中有一個一級索引，索引包含分中有一個一級索引，索引包含分配給文件的每個分區(qū)的入口。文件的索引保存在一個單獨的配給文件的每個分區(qū)的入口。文件

11、的索引保存在一個單獨的塊中。塊中。FAT中該文件的入口指向這一塊。中該文件的入口指向這一塊。u 優(yōu)點：優(yōu)點：u保持了鏈接結(jié)構(gòu)的優(yōu)點保持了鏈接結(jié)構(gòu)的優(yōu)點, ,又解決了其缺點：按塊分配又解決了其缺點：按塊分配可以可以消除外部碎片消除外部碎片，按大小可變的分區(qū)分配可以，按大小可變的分區(qū)分配可以提提高局部性高局部性。索引分配支持順序訪問文件和直接訪問。索引分配支持順序訪問文件和直接訪問文件，是普遍采用的一種方式。文件，是普遍采用的一種方式。u滿足了文件動態(tài)增長、插入刪除的要求（只要有空滿足了文件動態(tài)增長、插入刪除的要求（只要有空閑塊）閑塊）u也能充分利用外存空間也能充分利用外存空間u 缺點：缺點：u較

12、多的尋道次數(shù)和尋道時間較多的尋道次數(shù)和尋道時間. .u索引表本身帶來了系統(tǒng)開銷，索引表本身帶來了系統(tǒng)開銷， 如：內(nèi)外存空間，存如：內(nèi)外存空間，存取時間取時間文件的直接訪問：文件的直接訪問：使用連續(xù)分配方式使用連續(xù)分配方式文件的順序訪問：文件的順序訪問：采用鏈接分配采用鏈接分配對于這些系統(tǒng)，所使用的訪問類型必須在文對于這些系統(tǒng)，所使用的訪問類型必須在文件創(chuàng)建時加以說明。件創(chuàng)建時加以說明。連續(xù)分配和索引分配相結(jié)合：連續(xù)分配和索引分配相結(jié)合：對于小文件對于小文件（3塊或者塊或者4塊），采用連續(xù)分配，當文件塊），采用連續(xù)分配，當文件大時，自動切換到索引分配。大時，自動切換到索引分配。索引表指針索引表指

13、針文件說明信息文件說明信息邏輯塊邏輯塊號號物理物理塊號塊號02011522232520152225索引表索引表索引文件的物理結(jié)構(gòu)索引文件的物理結(jié)構(gòu) 索引表組織索引表組織多級索引多級索引: :將一個大文件的所有索引表（二級索引將一個大文件的所有索引表（二級索引) )的地的地址放在另一個索引表（一級索引址放在另一個索引表（一級索引) )中。中。u2種方式種方式u命令級接口：命令級接口：dirdir、copycopy等等u系統(tǒng)調(diào)用：系統(tǒng)調(diào)用：文件系統(tǒng)的程序級接口，用戶可以文件系統(tǒng)的程序級接口，用戶可以在程序中使用這些系統(tǒng)調(diào)用對文件進行各種操在程序中使用這些系統(tǒng)調(diào)用對文件進行各種操作。作。u如建立文件

14、、打開文件、關(guān)閉文件、刪除文件、如建立文件、打開文件、關(guān)閉文件、刪除文件、讀文件、寫文件。讀文件、寫文件。u建立文件建立文件：creatcreat（文件名、文件屬性）文件名、文件屬性）u檢查參數(shù)合法性：按給定的路徑查文件目錄，找出用戶檢查參數(shù)合法性：按給定的路徑查文件目錄，找出用戶指定的目錄位置，檢查目錄上是否存在同名文件，若存指定的目錄位置，檢查目錄上是否存在同名文件，若存在則發(fā)出錯誤信息。在則發(fā)出錯誤信息。u在指定的目錄中找一個空表項作為該文件的目錄項，寫在指定的目錄中找一個空表項作為該文件的目錄項，寫入指定的文件名。入指定的文件名。u由文件長度確定文件存儲所需的物理塊數(shù)。由文件長度確定文

15、件存儲所需的物理塊數(shù)。u按規(guī)定的物理結(jié)構(gòu)為文件分配存儲空間。對連續(xù)文件，按規(guī)定的物理結(jié)構(gòu)為文件分配存儲空間。對連續(xù)文件，則分配塊連續(xù)的空間，對索引文件，現(xiàn)分配索引表用的則分配塊連續(xù)的空間，對索引文件，現(xiàn)分配索引表用的物理塊。物理塊。u在該文件目錄項中寫入文件的屬性、文件的物理塊首址在該文件目錄項中寫入文件的屬性、文件的物理塊首址等。等。u打開文件打開文件(open):u按指定的文件名檢索文件目錄，將待訪問文件按指定的文件名檢索文件目錄，將待訪問文件的目錄信息讀入內(nèi)存活動文件表中，建立起用的目錄信息讀入內(nèi)存活動文件表中，建立起用戶和文件的聯(lián)系。戶和文件的聯(lián)系。u一旦文件被打開就可以多次使用。直到

16、文件被一旦文件被打開就可以多次使用。直到文件被關(guān)閉。關(guān)閉。多重索引結(jié)構(gòu)多重索引結(jié)構(gòu)u大文件：大文件：設(shè)一個盤塊大小為設(shè)一個盤塊大小為1KB，長度為，長度為100KB的的文件就需要文件就需要100個盤塊，索引表至少包含個盤塊，索引表至少包含100項；項；若文件大小為若文件大小為1000KB，則相應索引表項要有則相應索引表項要有1000項。設(shè)盤塊號用項。設(shè)盤塊號用4個字節(jié)表示，則該索引表至少占個字節(jié)表示，則該索引表至少占用用4000B（約約4K）。）。u當文件很大時，當文件很大時，存在的問題存在的問題：u需要很多的磁盤塊需要很多的磁盤塊u索引表很大索引表很大u不能將整個索引表放在內(nèi)存不能將整個索引

17、表放在內(nèi)存u解決途徑：解決途徑：采取多重索引結(jié)構(gòu)采取多重索引結(jié)構(gòu)索引表指針索引表指針文件說明信息文件說明信息記錄號記錄號物理物理塊號塊號020115222325物理塊號物理塊號索引表索引表20252215物理塊號物理塊號物理塊號物理塊號物理塊號物理塊號文件信息文件信息文件信息文件信息多重索引結(jié)構(gòu)多重索引結(jié)構(gòu) outer-indexindex tablefile多重索引結(jié)構(gòu)圖示多重索引結(jié)構(gòu)圖示多重索引結(jié)構(gòu)舉例多重索引結(jié)構(gòu)舉例u為此，我們可以將文件名和其他信息分開，后者單獨形成一個獨為此，我們可以將文件名和其他信息分開，后者單獨形成一個獨立的數(shù)據(jù)結(jié)構(gòu)，稱為索引節(jié)點（立的數(shù)據(jù)結(jié)構(gòu)，稱為索引節(jié)點（in

18、dex node或者或者i_node)對應的對應的目錄項就不再是完整的一個目錄項就不再是完整的一個FCB,而是由文件名和指向索引節(jié)點的而是由文件名和指向索引節(jié)點的指針組成指針組成u在引入索引節(jié)點之后，一個文件在創(chuàng)建后將立即有與之對應的一在引入索引節(jié)點之后，一個文件在創(chuàng)建后將立即有與之對應的一個磁盤索引節(jié)點若該文件被調(diào)進內(nèi)存，將立即有對應的一個內(nèi)個磁盤索引節(jié)點若該文件被調(diào)進內(nèi)存，將立即有對應的一個內(nèi)存索引結(jié)點存索引結(jié)點u為了加速對文件目錄的查找，在為了加速對文件目錄的查找，在Unix系統(tǒng)中，將文件系統(tǒng)中，將文件名和其它文件說明信息分開，名和其它文件說明信息分開，由文件說明信息形成一由文件說明信息

19、形成一個稱為索引節(jié)點的數(shù)據(jù)結(jié)構(gòu)個稱為索引節(jié)點的數(shù)據(jù)結(jié)構(gòu)，而，而相應的文件目錄項只相應的文件目錄項只由文件名由文件名和和對應的索引節(jié)點號組成。對應的索引節(jié)點號組成。文件名i節(jié)點號多重索引結(jié)構(gòu)舉例多重索引結(jié)構(gòu)舉例u文件分配以文件分配以塊塊為基礎(chǔ)。按照需要為基礎(chǔ)。按照需要動態(tài)動態(tài)進行，不是預定義的。進行，不是預定義的。u文件在磁盤中的塊不一定是連續(xù)的。文件在磁盤中的塊不一定是連續(xù)的。uUnix系統(tǒng)為了訪問文件，系統(tǒng)為了訪問文件，采用索引的方法采用索引的方法，索引的一部分保索引的一部分保存在該文件的索引節(jié)點中。存在該文件的索引節(jié)點中。u索引節(jié)點（索引節(jié)點（I節(jié)點）節(jié)點）文件名文件名索引節(jié)點編號索引節(jié)點

20、編號gamesmailNewsworku所有類型的所有類型的Unix文件都是由文件都是由OS通過索引節(jié)點來管理通過索引節(jié)點來管理的的u索引節(jié)點索引節(jié)點是一個控制結(jié)構(gòu)，包含是一個控制結(jié)構(gòu)，包含OS所要的關(guān)于某個所要的關(guān)于某個文件的重要信息文件的重要信息:u文件模式文件模式u鏈接計數(shù)鏈接計數(shù)u所有者所有者IDu組組IDu文件大小文件大小u文件地址文件地址（39字節(jié)）字節(jié)）u最后一次被訪問最后一次被訪問u最后一次被修改最后一次被修改u索引節(jié)點被修改索引節(jié)點被修改多重索引結(jié)構(gòu)舉例多重索引結(jié)構(gòu)舉例多重索引結(jié)構(gòu)舉例多重索引結(jié)構(gòu)舉例uUnix中通過為每個文件創(chuàng)建一個中通過為每個文件創(chuàng)建一個i節(jié)點節(jié)點的方法，

21、巧妙：的方法，巧妙：ui節(jié)點中包含節(jié)點中包含39個字節(jié)的地址信息個字節(jié)的地址信息，這個地址信息被組織成，這個地址信息被組織成13個個3字節(jié)的地址或指針。字節(jié)的地址或指針。u前前10個表目是直接索引，指向文件最初的個表目是直接索引，指向文件最初的10個數(shù)據(jù)塊。個數(shù)據(jù)塊。當文件大小小于當文件大小小于10塊時，可以直接定位到這塊時，可以直接定位到這10個塊；個塊；u第第11個表目是一級索引表，指向磁盤中包含下一部分索個表目是一級索引表，指向磁盤中包含下一部分索引的塊。引的塊。u第第12個表目是二級索引表，個表目是二級索引表，u第第13個表目是三級索引表；個表目是三級索引表；u對比：對比：在許多文件系

22、統(tǒng)中，在許多文件系統(tǒng)中，如如MSDOS中，使用文件分配表中，使用文件分配表FAT來管理文件的物理盤塊來管理文件的物理盤塊：u使用使用FAT的主要問題：整個磁盤的所有文件登記在同一個的主要問題：整個磁盤的所有文件登記在同一個FAT表中。因此，即使僅打開一個文件，也要使用整個表中。因此，即使僅打開一個文件，也要使用整個FAT來查找該文件所所分配的盤塊，浪費時間。來查找該文件所所分配的盤塊，浪費時間。u在在Unix系統(tǒng)中使用系統(tǒng)中使用1KB的物理塊，每個索引的物理塊，每個索引表的表目需要用表的表目需要用32位來存放物理塊地址，因位來存放物理塊地址，因此每個物理塊剛好是此每個物理塊剛好是256個表目，

23、可以映射個表目，可以映射256個物理塊。因此：個物理塊。因此：u小文件小文件（1010塊）：只使用直接索引表。塊）：只使用直接索引表。u中等文件中等文件（266266塊塊）：使用直接索引表與一）：使用直接索引表與一級索引表級索引表u大型文件大型文件（10102562562562562562566580265802塊塊）：使用直接索引表與一級和二級索引表。）：使用直接索引表與一級和二級索引表。u巨型文件：巨型文件：使用全部索引表，可尋址使用全部索引表，可尋址16777216塊。塊。u文件系統(tǒng)采用多級索引結(jié)構(gòu)來搜索文件文件內(nèi)容文件系統(tǒng)采用多級索引結(jié)構(gòu)來搜索文件文件內(nèi)容。設(shè)塊長為。設(shè)塊長為512字節(jié)

24、，每個塊號長字節(jié)，每個塊號長3字節(jié)。如果字節(jié)。如果不考慮邏輯塊號在物理塊中所占的位置，分別求不考慮邏輯塊號在物理塊中所占的位置，分別求二級索引和三級索引時可尋址的文件最大長度。二級索引和三級索引時可尋址的文件最大長度。u（512/3=170)u一級索引：一級索引：170塊塊u二級索引：二級索引塊），（塊），289005121450K字節(jié)字節(jié)u三級索引：三級索引：1701701704913000（塊），（塊）， 4913000 5122456500K字節(jié)字節(jié)u創(chuàng)建新文件時，系統(tǒng)要為用戶的文件分配相應創(chuàng)建新文件時，系統(tǒng)要為用戶的文件分配相應的外存空間；刪除一個老文件時，系

25、統(tǒng)要回收的外存空間；刪除一個老文件時，系統(tǒng)要回收該文件所占用的外存空間，供新文件使用。因該文件所占用的外存空間，供新文件使用。因此，系統(tǒng)需要對外存空閑塊進行妥善管理。此，系統(tǒng)需要對外存空閑塊進行妥善管理。u在分配時，首先知道磁盤中的哪些塊是可用的在分配時，首先知道磁盤中的哪些塊是可用的。除了。除了FAT外，還需要一個外，還需要一個DAT（disk allocation Table）。實現(xiàn)技術(shù)：。實現(xiàn)技術(shù)：u位圖位圖u空間塊鏈接法空間塊鏈接法u空閑目錄法空閑目錄法u成組塊鏈接法成組塊鏈接法u位圖（位向量）：位圖（位向量）：使用一個向量，向量中的每位（使用一個向量，向量中的每位（bit）對應于磁盤

26、中的每一個塊（對應于磁盤中的每一個塊（block）u0：表示一個表示一個空閑塊空閑塊u1：表示一個表示一個已使用的塊。已使用的塊。例：例：2,3,4,5,8,9,10,11,12,13,17,18,25,26,27, =0011110011111100011000000111u優(yōu)點：優(yōu)點：u可以比較可以比較容易地找到第一個或一組連續(xù)的自由容易地找到第一個或一組連續(xù)的自由塊，適用于任何一塊，適用于任何一種文件分配方法。（而且很多計算機都提供位操作指令）種文件分配方法。（而且很多計算機都提供位操作指令）u位表小，但長度可變位表小，但長度可變u例：對于一個例：對于一個16GB的磁盤，塊大小為的磁盤，

27、塊大小為512 字節(jié)，則位表占字節(jié)，則位表占4MB空間?？臻g。u缺點：缺點：u對于大文件，位圖占用內(nèi)存空間較多，可以按合并對于大文件，位圖占用內(nèi)存空間較多，可以按合并4個扇區(qū)位一個個扇區(qū)位一個cluster（簇）的方法。簇）的方法。u位表的管理：位表的管理：u位圖可以位于內(nèi)存或磁盤中，但在磁盤中需要搜索位圖可以位于內(nèi)存或磁盤中，但在磁盤中需要搜索時間，時間，故位表一般位于內(nèi)存中。故位表一般位于內(nèi)存中。u即使位于主存中，窮舉式搜索會影響文件系統(tǒng)的性即使位于主存中，窮舉式搜索會影響文件系統(tǒng)的性能，尤其是當磁盤快滿時只剩下很少自由塊時問題能，尤其是當磁盤快滿時只剩下很少自由塊時問題會很嚴重。會很嚴重

28、。u因此，大多數(shù)使用位表的文件系統(tǒng)都有因此，大多數(shù)使用位表的文件系統(tǒng)都有一個輔助數(shù)一個輔助數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)，用于匯總位圖的子區(qū)域的內(nèi)容用于匯總位圖的子區(qū)域的內(nèi)容。u例如：例如：位圖可以在邏輯上劃分成許多子區(qū)域，位圖可以在邏輯上劃分成許多子區(qū)域，對對于每個子區(qū)域，匯總表中包括它的自由塊的數(shù)目于每個子區(qū)域，匯總表中包括它的自由塊的數(shù)目和連續(xù)自由塊的最大數(shù)目。和連續(xù)自由塊的最大數(shù)目。u當文件系統(tǒng)需要大量的連續(xù)塊時，它可以通過掃當文件系統(tǒng)需要大量的連續(xù)塊時，它可以通過掃描匯總表來發(fā)現(xiàn)適合的子區(qū)域，然后再搜索這個描匯總表來發(fā)現(xiàn)適合的子區(qū)域，然后再搜索這個子區(qū)域。子區(qū)域。u將文件存儲設(shè)備上的每個空閑空間看作

29、一個空閑文將文件存儲設(shè)備上的每個空閑空間看作一個空閑文件，系統(tǒng)為所有空閑文件單獨建立一個目錄。件，系統(tǒng)為所有空閑文件單獨建立一個目錄。每個每個空閑文件在這個目錄中占用一個表目。表目的內(nèi)容空閑文件在這個目錄中占用一個表目。表目的內(nèi)容包括第一個空閑塊的地址（物理塊號）、空閑塊的包括第一個空閑塊的地址（物理塊號）、空閑塊的數(shù)目。如：數(shù)目。如：u分配過程：分配過程：新建文件時，掃描索引，找到符合條件新建文件時，掃描索引，找到符合條件的項，并從表中刪除；的項，并從表中刪除；u回收過程：回收過程：刪除文件時，系統(tǒng)回收該文件所占用的刪除文件時，系統(tǒng)回收該文件所占用的盤塊，將相應的空閑塊的信息填回空閑空間表中

30、，盤塊，將相應的空閑塊的信息填回空閑空間表中，如果釋放的區(qū)域和和原有空閑區(qū)鄰接，則將它們合如果釋放的區(qū)域和和原有空閑區(qū)鄰接，則將它們合并成一個大的空閑區(qū)，記在一個表項中。并成一個大的空閑區(qū)，記在一個表項中。u適合于連續(xù)文件的存放適合于連續(xù)文件的存放u但是，如果有大量的小空閑區(qū)，則空閑區(qū)表很大，但是，如果有大量的小空閑區(qū)，則空閑區(qū)表很大，檢索效率很低。檢索效率很低。序號序號第一個空第一個空閑塊號閑塊號空閑塊空閑塊個數(shù)個數(shù)物理塊號物理塊號153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-u鏈表：鏈表：通過使用指向每個空閑區(qū)的指針和它們的通

31、過使用指向每個空閑區(qū)的指針和它們的長度值的一個鏈將空閑區(qū)鏈接起來。長度值的一個鏈將空閑區(qū)鏈接起來。u如果需要一個塊：如果需要一個塊：從鏈的頭部取出一塊，并調(diào)整長從鏈的頭部取出一塊，并調(diào)整長度；如果是基于可變分區(qū)長度分配的，可采用首次度；如果是基于可變分區(qū)長度分配的，可采用首次適配算法，同樣需要調(diào)整指針和長度。適配算法，同樣需要調(diào)整指針和長度。u優(yōu)點：優(yōu)點：空間開銷?。簝H需要一個指向鏈開始處的指空間開銷?。簝H需要一個指向鏈開始處的指針及第一個分區(qū)的長度針及第一個分區(qū)的長度u問題：問題：u每次分配一個塊時，在將數(shù)據(jù)寫到這個塊中每次分配一個塊時，在將數(shù)據(jù)寫到這個塊中之前，需要先讀這個塊，以發(fā)現(xiàn)指向新

32、的第之前，需要先讀這個塊，以發(fā)現(xiàn)指向新的第一個空閑塊的指針。一個空閑塊的指針。u效率低，開銷大。效率低，開銷大。u成組塊鏈接法：成組塊鏈接法：將外存中的所有空閑塊按將外存中的所有空閑塊按50塊（或塊（或n塊）劃分為一組，用塊）劃分為一組，用索引表索引表表示；每組的第一塊表示；每組的第一塊用來存放前一組中各塊的塊號和總塊數(shù)；因此，各用來存放前一組中各塊的塊號和總塊數(shù)；因此，各組間通過鏈表指針串在一起，構(gòu)成組間通過鏈表指針串在一起，構(gòu)成鏈表鏈表。（把鏈表。（把鏈表和索引相結(jié)合。）和索引相結(jié)合。）u 第一組的塊數(shù)為第一組的塊數(shù)為49塊，最后一組可能不足塊，最后一組可能不足50塊，塊，且最后組的物理塊

33、號與總塊數(shù)只能放在內(nèi)存的一個且最后組的物理塊號與總塊數(shù)只能放在內(nèi)存的一個專用棧中（如：專用棧中（如：Unix中超級塊中）；中超級塊中）；u 對塊的分配和釋放在棧中進行。對塊的分配和釋放在棧中進行。棧計數(shù)棧計數(shù)count是棧是棧中的空閑塊數(shù)目，棧中的元素是空閑塊編號。中的空閑塊數(shù)目，棧中的元素是空閑塊編號。成組塊鏈接法成組塊鏈接法每組的第一塊用來存放前一組中各塊的塊號和總塊數(shù)u系統(tǒng)啟動時的初始化系統(tǒng)啟動時的初始化u系統(tǒng)中設(shè)立有專用的磁盤空系統(tǒng)中設(shè)立有專用的磁盤空間分配間分配/回收用的回收用的內(nèi)存堆棧區(qū)內(nèi)存堆棧區(qū)，使得空閑塊的分配和釋放，使得空閑塊的分配和釋放可在內(nèi)存進行；同時用于空可在內(nèi)存進行；

34、同時用于空閑塊分配和回收的堆棧有閑塊分配和回收的堆棧有堆堆棧指針棧指針Ptr， Ptr的初值等于的初值等于該組空閑塊的總塊數(shù)。分配該組空閑塊的總塊數(shù)。分配時，時， Ptr Ptr1；回收時回收時， Ptr Ptr1；空閑塊的空閑塊的分配和釋放必須互斥進行分配和釋放必須互斥進行u啟動時將卷資源表中的最后啟動時將卷資源表中的最后一組的信息讀入內(nèi)存堆棧一組的信息讀入內(nèi)存堆棧S中。其中中。其中0單元存放總塊數(shù)，單元存放總塊數(shù)，棧頂指針值等于總塊數(shù)棧頂指針值等于總塊數(shù)3XYZ堆棧堆棧S0 1 2 3 4 5 u空閑塊分配過程空閑塊分配過程：當需要一塊空閑塊時，首先查看棧中：當需要一塊空閑塊時，首先查看棧

35、中是否是否count = 1：u若不是若不是，則彈出棧頂元素，則彈出棧頂元素N（表示可用磁盤塊號）分配出表示可用磁盤塊號）分配出去，去，-count；u若是，若是，彈出棧頂元素彈出棧頂元素N，把空閑塊把空閑塊N中的塊號讀入到棧中；中的塊號讀入到棧中；返回空閑塊編號返回空閑塊編號N（因為所分配的磁盤塊號是棧中最后一因為所分配的磁盤塊號是棧中最后一個可用盤塊號，由于在該盤塊中存放了下一組的所有盤塊個可用盤塊號，由于在該盤塊中存放了下一組的所有盤塊號，于是要先將該塊的內(nèi)容讀入棧中，然后才能將該塊分號，于是要先將該塊的內(nèi)容讀入棧中，然后才能將該塊分配出去）配出去）u釋放過程：釋放過程：被釋放空閑塊為編

36、號被釋放空閑塊為編號N。查看是否棧已滿（查看是否棧已滿（如如count = 50）；）；u若不是，若不是，則則N入棧，入棧，+count；u若是，若是，則將棧（包括棧計數(shù)）寫入到空閑塊則將棧（包括棧計數(shù)）寫入到空閑塊N，然后把然后把N放放入棧頂并置入棧頂并置count為為1。（說明棧已滿，須先將棧中所有盤。（說明棧已滿，須先將棧中所有盤塊號復制到新回收的盤塊中，再將新回收盤塊的編號放到塊號復制到新回收的盤塊中，再將新回收盤塊的編號放到棧中，成為棧中第一個盤塊）棧中，成為棧中第一個盤塊）41350187Super Blockcount50040400351.049count50450401.04

37、9count460.045count#350#400Last One.成組塊鏈接 下組指針 本組塊數(shù)本組塊號First1已知一文件系統(tǒng)采用鏈式文件方式存儲文件，存儲設(shè)備已知一文件系統(tǒng)采用鏈式文件方式存儲文件，存儲設(shè)備用成組塊鏈接法管理，每組用成組塊鏈接法管理，每組8塊。目前系統(tǒng)的狀態(tài)如下圖塊。目前系統(tǒng)的狀態(tài)如下圖：1)一進程欲申請一進程欲申請10個磁盤塊，請給出其得到的磁盤塊號序個磁盤塊，請給出其得到的磁盤塊號序列，并畫出分配后的系統(tǒng)狀態(tài)；并指出完成本次申請，列，并畫出分配后的系統(tǒng)狀態(tài)；并指出完成本次申請，I/O操作的次數(shù)。操作的次數(shù)。2）在）在1）基礎(chǔ)上，回收一個以）基礎(chǔ)上，回收一個以50作為起始塊號的具有作為起始塊號的具有6個塊個塊的文件，畫出回收后的系統(tǒng)狀態(tài)圖。并指出完成本次回的文件，畫出回收后的系統(tǒng)狀態(tài)圖。并指出完成本次回收，收，I/O操作的次數(shù)。操作的次數(shù)。 系統(tǒng)磁盤塊管理系統(tǒng)磁盤塊管理堆棧堆棧其中其中0#單元存放單元存放總塊數(shù)總塊數(shù)堆棧指針值等于堆棧指針值等于總塊數(shù)總塊數(shù)第第80#磁磁盤塊盤塊第第 8 8#磁磁盤塊盤塊051802793784775766757748738888786858483828189695949392919089假定磁盤塊的大小為假定磁盤塊的大小為1KB，每個盤塊號占每個盤塊號占4