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

1、第八章:文件管理趙恒 主講21文件物理結(jié)構(gòu)的概念文件物理結(jié)構(gòu)的概念 文件的物理結(jié)構(gòu)，又稱為文件的存儲結(jié)構(gòu)，它是文件的物理結(jié)構(gòu)，又稱為文件的存儲結(jié)構(gòu)，它是指文件在外存上存儲時的組織結(jié)構(gòu)。指文件在外存上存儲時的組織結(jié)構(gòu)。文件的物理結(jié)構(gòu)與存儲介質(zhì)的物理特性及用戶對文件的物理結(jié)構(gòu)與存儲介質(zhì)的物理特性及用戶對文件的訪問方式有關(guān)。文件的訪問方式有關(guān)。文件的物理結(jié)構(gòu)通常劃分為大小相等的物理塊，文件的物理結(jié)構(gòu)通常劃分為大小相等的物理塊，也稱為物理記錄。它是文件分配及傳輸信息的基也稱為物理記錄。它是文件分配及傳輸信息的基本單位。物理記錄的大小與物理設(shè)備有關(guān)，與邏本單位。物理記錄的大小與物理設(shè)備有關(guān)，與邏輯記錄的

2、大小無關(guān)。輯記錄的大小無關(guān)。 8.1 外存分配方式外存分配方式32文件物理結(jié)構(gòu)的形式文件物理結(jié)構(gòu)的形式 三種文件物理結(jié)構(gòu)組織文件：三種文件物理結(jié)構(gòu)組織文件：n順序結(jié)構(gòu)：順序結(jié)構(gòu)將一個在邏輯上連續(xù)的文件信順序結(jié)構(gòu)：順序結(jié)構(gòu)將一個在邏輯上連續(xù)的文件信息依次存放在外存連續(xù)的物理塊中息依次存放在外存連續(xù)的物理塊中 。n鏈接結(jié)構(gòu)：鏈接結(jié)構(gòu)將文件存放在外存的若干個物鏈接結(jié)構(gòu)：鏈接結(jié)構(gòu)將文件存放在外存的若干個物理塊中，這些物理塊不必連續(xù)，并且在每一個物理理塊中，這些物理塊不必連續(xù)，并且在每一個物理塊中設(shè)一個指針，指向下一個物理塊的位置，從而塊中設(shè)一個指針，指向下一個物理塊的位置，從而使得存放同一個文件的物理

3、塊鏈接起來。使得存放同一個文件的物理塊鏈接起來。 n索引結(jié)構(gòu)：將文件存放在外存的若干個物理塊中，索引結(jié)構(gòu)：將文件存放在外存的若干個物理塊中，并為每個文件建立一個索引表，索引表中的每個表并為每個文件建立一個索引表，索引表中的每個表目存放文件信息的邏輯塊號和與之對應(yīng)的物理塊號。目存放文件信息的邏輯塊號和與之對應(yīng)的物理塊號。 4一個文件存儲介質(zhì)，格式化后就分成許多大小一個文件存儲介質(zhì)，格式化后就分成許多大小相等的單位存儲塊（物理盤塊），在現(xiàn)代計相等的單位存儲塊（物理盤塊），在現(xiàn)代計算機(jī)系統(tǒng)中，一般來說，每個物理塊是算機(jī)系統(tǒng)中，一般來說，每個物理塊是一個磁盤一個磁盤的扇區(qū)，的扇區(qū)，512字節(jié)字節(jié)。并給

4、每個存儲塊有個編號，。并給每個存儲塊有個編號，稱為稱為物理塊號物理塊號。常用的外存分配方式有常用的外存分配方式有連續(xù)分配，鏈接分配和連續(xù)分配，鏈接分配和索引分配索引分配三種。三種。5一一.連續(xù)分配連續(xù)分配定義：為每個文件分配相鄰的物理塊，并將文件信息定義：為每個文件分配相鄰的物理塊，并將文件信息按邏輯順序依次存放在這些物理塊中。按邏輯順序依次存放在這些物理塊中。分配給文件的首個物理塊的地址被登記在它的目錄項分配給文件的首個物理塊的地址被登記在它的目錄項內(nèi)。這樣所形成的文件物理結(jié)構(gòu)被稱為順序結(jié)構(gòu)，相內(nèi)。這樣所形成的文件物理結(jié)構(gòu)被稱為順序結(jié)構(gòu)，相應(yīng)的物理文件則稱為順序文件應(yīng)的物理文件則稱為順序文件

5、(Sequential File)。文件文件A 3 100 r0 r1 r2 磁盤塊號磁盤塊號100101102文件目錄文件目錄文件文件A目錄項目錄項6磁盤空間的磁盤空間的連續(xù)分配連續(xù)分配012345678910111213141516171819202122232425262728293031文件名文件名 始址始址 塊數(shù)塊數(shù)count 0 2tr 14 3mail 19 6list 28 4f 6 2 文件目錄文件目錄countftrmaillist72.連續(xù)文件結(jié)構(gòu)的特點連續(xù)文件結(jié)構(gòu)的特點 優(yōu)點：優(yōu)點：順序訪問容易順序訪問容易存取速度快存取速度快缺點：缺點：要求連續(xù)的存儲空間。易產(chǎn)生外部碎

6、片，空間利要求連續(xù)的存儲空間。易產(chǎn)生外部碎片，空間利用率降低用率降低須事先知道文件長度。不利于文件動態(tài)增長。須事先知道文件長度。不利于文件動態(tài)增長。8二二.鏈接分配鏈接分配鏈接分配的文件也稱之為是串聯(lián)文件。串聯(lián)文件結(jié)構(gòu)是按順序由串聯(lián)的塊組成的，即串聯(lián)文件結(jié)構(gòu)是按順序由串聯(lián)的塊組成的，即文件的信息存于若干文件的信息存于若干不連續(xù)的物理塊中不連續(xù)的物理塊中，每個，每個物理塊的最末一個字作為物理塊的最末一個字作為鏈接字鏈接字，它指出后繼，它指出后繼塊的物理地址。塊的物理地址。文件的最后一塊的鏈接字為結(jié)束標(biāo)記文件的最后一塊的鏈接字為結(jié)束標(biāo)記“”，它，它表示文件至本塊結(jié)束。表示文件至本塊結(jié)束。類似數(shù)據(jù)結(jié)

7、構(gòu)的類似數(shù)據(jù)結(jié)構(gòu)的鏈表。鏈表。9鏈接結(jié)構(gòu)文件文件A 100 r1 57 r2 r0 150磁盤塊號磁盤塊號 100磁盤塊號磁盤塊號 150磁盤塊號磁盤塊號 57文件目錄文件目錄文件文件A目錄項目錄項問題：在串聯(lián)文件結(jié)構(gòu)下，當(dāng)要存取R i 記錄時，應(yīng)如何操作?10鏈接結(jié)構(gòu)文件的特點文件的特點優(yōu)點：優(yōu)點：1.存儲空間利用率高；存儲空間利用率高；2.文件創(chuàng)建時用戶不必文件創(chuàng)建時用戶不必指出文件的大小指出文件的大??；3.文件動態(tài)擴(kuò)充和修改容易。文件動態(tài)擴(kuò)充和修改容易。缺點：只能按隊列中的指針順序搜索缺點：只能按隊列中的指針順序搜索，隨機(jī)存，隨機(jī)存取效率太低，取效率太低，如果訪問文件的最后的內(nèi)容，實如果

8、訪問文件的最后的內(nèi)容，實際上是要訪問整個文件際上是要訪問整個文件。11鏈接分配的兩種形式：鏈接分配的兩種形式：1. 隱式鏈接隱式鏈接 25123056749101181314151217181916212223202526272429303128filestartendjeep925目 錄101-116在采用隱式鏈接分配時，在在采用隱式鏈接分配時，在文件目錄的每個目錄項中，文件目錄的每個目錄項中，都須含有指向鏈接文件的第一個盤塊和最后一個盤塊都須含有指向鏈接文件的第一個盤塊和最后一個盤塊的指針的指針。而在每個盤塊中都含有一個指向下一個盤塊的指針。而在每個盤塊中都含有一個指向下一個盤塊的指針。1

9、2隱式鏈接隱式鏈接優(yōu)缺點：優(yōu)缺點：優(yōu)點優(yōu)點：消除了外部碎片，提高利用率消除了外部碎片，提高利用率允許作業(yè)動態(tài)增長。允許作業(yè)動態(tài)增長。缺點缺點：可靠性差：一個指針出現(xiàn)問題，導(dǎo)致整個鏈斷開可靠性差：一個指針出現(xiàn)問題，導(dǎo)致整個鏈斷開只適合于順序訪問，不適合隨機(jī)訪問。只適合于順序訪問，不適合隨機(jī)訪問。132. 顯式鏈接顯式鏈接這是指把用于鏈接文件各物理塊的指針，這是指把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)顯式地存放在內(nèi)存的一張鏈接表中存的一張鏈接表中。該表在整個磁盤僅設(shè)置一張，由于查。該表在整個磁盤僅設(shè)置一張，由于查找記錄的過程是在內(nèi)存中進(jìn)行的，因而不僅顯著地提高了找記錄的過程是在內(nèi)存中進(jìn)行的，

10、因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。檢索速度，而且大大減少了訪問磁盤的次數(shù)。 圖 6-9 顯式鏈接結(jié)構(gòu) 012345物理塊號2FCBFAT0451146EOF11105EOF0123456789FATFCB A4FCB B9MS-DOS的文件物理結(jié)構(gòu)15顯示鏈接顯示鏈接特點：特點：優(yōu)點優(yōu)點：顯著提高檢索速度：顯著提高檢索速度缺點缺點：n不支持大文件隨機(jī)存取不支持大文件隨機(jī)存取FAT需要占用較大的內(nèi)存空間需要占用較大的內(nèi)存空間163、索引結(jié)構(gòu)、索引結(jié)構(gòu)鏈接結(jié)構(gòu)解決了連續(xù)分配的外部碎片和大小聲明鏈接結(jié)構(gòu)解決了連續(xù)分配的外部碎片和大小聲明的問題，但是，的問題，但是，鏈接結(jié)構(gòu)不

11、能有效地支持直接訪鏈接結(jié)構(gòu)不能有效地支持直接訪問問，這是因為塊指針與塊一起分布在整個磁盤，這是因為塊指針與塊一起分布在整個磁盤，且必須按順序讀出。且必須按順序讀出。索引結(jié)構(gòu)解決了這個問題。索引結(jié)構(gòu)解決了這個問題。索引分配要求系統(tǒng)為索引分配要求系統(tǒng)為每個文件建立每個文件建立一張索引表一張索引表。索引結(jié)構(gòu)創(chuàng)建的文件索引結(jié)構(gòu)創(chuàng)建的文件也稱之為也稱之為索引文件。索引文件。173、索引結(jié)構(gòu)、索引結(jié)構(gòu)索引結(jié)構(gòu)文件是另一種形式的是另一種形式的非連續(xù)文件非連續(xù)文件，文件數(shù)據(jù)存放的存儲介質(zhì)上的物理塊號與文件數(shù)據(jù)存放的存儲介質(zhì)上的物理塊號與文件的邏輯塊號一一對應(yīng)，并建立這樣對文件的邏輯塊號一一對應(yīng)，并建立這樣對應(yīng)

12、關(guān)系的數(shù)據(jù)結(jié)構(gòu)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)文件索引表。文件索引表。183、索引結(jié)構(gòu)、索引結(jié)構(gòu)訪問文件時，訪問文件時，根據(jù)文件的邏輯塊號查文根據(jù)文件的邏輯塊號查文件索引表件索引表，找到對應(yīng)的物理塊號，然后，找到對應(yīng)的物理塊號，然后，進(jìn)行訪問。進(jìn)行訪問。文件由文件由索引表和數(shù)據(jù)文件索引表和數(shù)據(jù)文件構(gòu)成。這種文件稱為構(gòu)成。這種文件稱為索引文件。索引文件。非常類似于書本，它由非常類似于書本，它由書目錄和正文書目錄和正文組成。組成。1920索引文件結(jié)構(gòu)索引文件結(jié)構(gòu)索引文件在存儲區(qū)中占兩個區(qū)：索引區(qū)索引文件在存儲區(qū)中占兩個區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放索引表，數(shù)據(jù)區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放數(shù)據(jù)文件本身。

13、存放數(shù)據(jù)文件本身。訪問索引文件需要訪問索引文件需要兩步操作兩步操作 查文件索引，由邏輯塊號查得物理查文件索引，由邏輯塊號查得物理塊號塊號 由此磁盤物理塊號而獲得所要求的由此磁盤物理塊號而獲得所要求的信息。信息。 Operating SystemOperating Systemq單級索引分配單級索引分配v鏈接分配存在的問題鏈接分配存在的問題不能支持高效的直接存取不能支持高效的直接存取，要對一個，要對一個較大的文較大的文件件進(jìn)行進(jìn)行直接存取直接存取，須首先在，須首先在FAT中順序地查找中順序地查找許多盤塊號。許多盤塊號。FAT需需占用較大占用較大的的內(nèi)存內(nèi)存空間空間v索引分配索引分配為為每個文件分

14、配一個索引塊每個文件分配一個索引塊，把分配給該文件，把分配給該文件的所有盤塊號都記錄在該索引塊中的所有盤塊號都記錄在該索引塊中在建立一個文件時，便為之建立的目錄項中填在建立一個文件時，便為之建立的目錄項中填上指向該索引塊的指針上指向該索引塊的指針v支持直接訪問支持直接訪問對于大文件而言，該方式優(yōu)于鏈?zhǔn)椒峙浞绞綄τ诖笪募?，該方式?yōu)于鏈?zhǔn)椒峙浞绞絆perating SystemOperating System012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目錄文件目錄Jeep 19 916 110

15、25 -1 -1 -119Operating SystemOperating Systemq若每個盤塊大小為若每個盤塊大小為1KB，每個盤塊號占，每個盤塊號占4B，則索引塊中可存放則索引塊中可存放256個盤塊號，即采用這種個盤塊號，即采用這種索引方式時每個文件索引方式時每個文件大小不能大小不能超過超過256KBq索引表組織索引表組織v鏈接模式鏈接模式: :一個盤塊一個索引表一個盤塊一個索引表, ,多個索引多個索引表鏈接起來表鏈接起來v多級索引多級索引: :將一個大文件的所有索引表（二將一個大文件的所有索引表（二級索引級索引) )的地址放在另一個索引表（一級索的地址放在另一個索引表（一級索引引)

16、 )中中Operating SystemOperating Systemq多級索引分配多級索引分配012-105106254356357985105106254740356357-1125985360740-1125-主索引主索引360第二級索引第二級索引磁盤空間磁盤空間Operating SystemOperating Systemq若每個盤塊大小為若每個盤塊大小為1KB，每個盤塊號占，每個盤塊號占4B，則一，則一級索引塊中可存放級索引塊中可存放256個盤塊號，即對應(yīng)個盤塊號，即對應(yīng)256個個二級索引塊二級索引塊q每個二級索引塊可對應(yīng)每個二級索引塊可對應(yīng)256個物理磁盤塊，采用個物理磁盤塊，

17、采用這種索引方式時每個文件大小不能超過這種索引方式時每個文件大小不能超過256*256*1KB=64MBq若每個盤塊大小為若每個盤塊大小為4K，則最大文件大小為，則最大文件大小為1K*1K*4K=4GBOperating SystemOperating Systemmodeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadata-datadata-datadatadatadata直接地

18、址物理盤塊索引塊Operating SystemOperating Systemq直接地址直接地址v為了提高對文件的檢索速度，為了提高對文件的檢索速度， 在索引結(jié)點中可在索引結(jié)點中可設(shè)置設(shè)置10個直接地址項，個直接地址項， 即用即用iaddr(0)iaddr(9)來存放直接地址來存放直接地址q一次間接地址一次間接地址v對于大、對于大、 中型文件，可再利用索引結(jié)點中的地中型文件，可再利用索引結(jié)點中的地址項址項iaddr(10)來提供一次間接地址。這種方式來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式的實質(zhì)就是一級索引分配方式q多次間接地址多次間接地址v當(dāng)文件長度大于當(dāng)文件長度大于4 MB

19、+40 KB時時(一次間址與一次間址與10個直接地址項個直接地址項)， 系統(tǒng)還須采用二次間址分配系統(tǒng)還須采用二次間址分配方式。這時，用地址項方式。這時，用地址項iaddr(11)提供二次間接提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式地址。該方式的實質(zhì)是兩級索引分配方式Operating SystemOperating Systemq索引結(jié)構(gòu)優(yōu)缺點索引結(jié)構(gòu)優(yōu)缺點v優(yōu)點：優(yōu)點： 保持了鏈接結(jié)構(gòu)的優(yōu)點保持了鏈接結(jié)構(gòu)的優(yōu)點, ,又解決了其缺又解決了其缺點：即能順序存取點：即能順序存取, ,又能隨機(jī)存取，滿足了又能隨機(jī)存取，滿足了文件動態(tài)增長、插入刪除的要求，也能充文件動態(tài)增長、插入刪除的要求，也

20、能充分利用外存空間分利用外存空間v缺點：缺點： 較多的尋道次數(shù)和尋道時間，索引表較多的尋道次數(shù)和尋道時間，索引表本身帶來了系統(tǒng)開銷，如：內(nèi)外存空間，本身帶來了系統(tǒng)開銷，如：內(nèi)外存空間，存取時間存取時間Operating SystemOperating Systemq索引分配的主要問題索引分配的主要問題v需要較多外存空間來建立索引塊需要較多外存空間來建立索引塊v對于小文件，空間浪費嚴(yán)重對于小文件，空間浪費嚴(yán)重Operating SystemOperating Systemq連續(xù)文件的連續(xù)文件的優(yōu)點優(yōu)點是不需要額外的空間開銷，只是不需要額外的空間開銷，只要在文件目錄中指出文件的大小和首塊的塊號要在

21、文件目錄中指出文件的大小和首塊的塊號即可，對順序的訪問效率很高。適應(yīng)于順序存即可，對順序的訪問效率很高。適應(yīng)于順序存取。取。缺點缺點是動態(tài)地增長和縮小系統(tǒng)開銷很大；是動態(tài)地增長和縮小系統(tǒng)開銷很大；文件創(chuàng)建時要求用戶提供文件的大??；存儲空文件創(chuàng)建時要求用戶提供文件的大??；存儲空間浪費較大。間浪費較大。q鏈?zhǔn)轿募朔诉B續(xù)文件的不足之處，但文件鏈?zhǔn)轿募朔诉B續(xù)文件的不足之處，但文件的隨機(jī)訪問系統(tǒng)開銷較大。適應(yīng)于順序訪問。的隨機(jī)訪問系統(tǒng)開銷較大。適應(yīng)于順序訪問。DOS系統(tǒng)中改造了鏈?zhǔn)轿募慕Y(jié)構(gòu)，使其克服系統(tǒng)中改造了鏈?zhǔn)轿募慕Y(jié)構(gòu)，使其克服了鏈?zhǔn)轿募牟蛔?，但增加了系統(tǒng)的危險性。了鏈?zhǔn)轿募牟蛔?，?/p>

22、增加了系統(tǒng)的危險性。Operating SystemOperating Systemq索引文件既適應(yīng)于順序存訪問，也適應(yīng)于隨機(jī)訪索引文件既適應(yīng)于順序存訪問，也適應(yīng)于隨機(jī)訪問，是一種比較好的文件物理結(jié)構(gòu)，但要有用于問，是一種比較好的文件物理結(jié)構(gòu)，但要有用于索引表的空間開銷和文件索引的時間開銷。索引表的空間開銷和文件索引的時間開銷。UNIX系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。q在當(dāng)前流行的一些在當(dāng)前流行的一些UNIX操作系統(tǒng)的版本中，同操作系統(tǒng)的版本中，同時支持連續(xù)文件結(jié)構(gòu)和索引文件結(jié)構(gòu)。時支持連續(xù)文件結(jié)構(gòu)和索引文件結(jié)構(gòu)。DOS、WINDOWS系統(tǒng)支撐類似于文件映照結(jié)構(gòu)系統(tǒng)

23、支撐類似于文件映照結(jié)構(gòu)32華中科技大學(xué)華中科技大學(xué)2000年年某文件系統(tǒng)采用索引文件結(jié)構(gòu)，假定文件索引某文件系統(tǒng)采用索引文件結(jié)構(gòu)，假定文件索引表的表的每個表項占每個表項占3個字節(jié)個字節(jié)，用一個磁盤塊存放，用一個磁盤塊存放塊號（磁盤塊的大小為塊號（磁盤塊的大小為512B）。試問）。試問1）該文件系統(tǒng)能管理的最大磁盤空間是多少）該文件系統(tǒng)能管理的最大磁盤空間是多少字節(jié)字節(jié)2）若采用）若采用2級或級或3級索引該文件系統(tǒng)能管理的級索引該文件系統(tǒng)能管理的最大磁盤空間又是多少字節(jié)？最大磁盤空間又是多少字節(jié)？33分析分析由于索引表占用一個大小為由于索引表占用一個大小為512B的磁盤，所以該的磁盤，所以該文件

24、系統(tǒng)的索引表可以管理文件系統(tǒng)的索引表可以管理512/3=170個表項，而個表項，而每一個表項對應(yīng)一個物理塊，因此該文件系統(tǒng)可每一個表項對應(yīng)一個物理塊，因此該文件系統(tǒng)可以管理的最大磁盤空間為以管理的最大磁盤空間為170*512B=87040B=85K若采用二級索引，則是：若采用二級索引，則是：170*170*512B=7225KB若采用三級索引，則是：若采用三級索引，則是：170*170*170*512B=2456500KB=2398.93M34多選題：多選題：西安電子科技大學(xué)西安電子科技大學(xué)20021.文件的物理結(jié)構(gòu)一般有（）文件的物理結(jié)構(gòu)一般有（）A 連續(xù)文件連續(xù)文件B 流式文件流式文件C

25、記錄式文件記錄式文件D串聯(lián)文件串聯(lián)文件E 索引文件索引文件答案：答案：A D E35多選題：多選題：西安電子科技大學(xué)西安電子科技大學(xué)20022.連續(xù)結(jié)構(gòu)的文件適合采用（）存取方法連續(xù)結(jié)構(gòu)的文件適合采用（）存取方法A 順序存取順序存取B 直接存取直接存取C 按鍵存取按鍵存取D分區(qū)存取分區(qū)存取E 以上均不對以上均不對答案：答案：A B36思考題思考題考慮一個存于磁盤上的文件系統(tǒng)，其中的文件由考慮一個存于磁盤上的文件系統(tǒng)，其中的文件由大小為大小為512B的塊組成。假定每一個文件有一個文的塊組成。假定每一個文件有一個文件目錄項，該目錄項包含此文件的名字、文件長件目錄項，該目錄項包含此文件的名字、文件長

26、度以及第一塊度以及第一塊(或第一索引塊或第一索引塊)和最后一塊的位置，和最后一塊的位置，而且該目錄項位于內(nèi)存。對于索引結(jié)構(gòu)文件，該而且該目錄項位于內(nèi)存。對于索引結(jié)構(gòu)文件，該目錄項指明第一索引塊，該索引塊又依次指向目錄項指明第一索引塊，該索引塊又依次指向511個文件塊且有一個指向下一個索引塊的指針。針個文件塊且有一個指向下一個索引塊的指針。針對連續(xù)、鏈接、索引結(jié)構(gòu)的每一種，如果當(dāng)前位對連續(xù)、鏈接、索引結(jié)構(gòu)的每一種，如果當(dāng)前位于邏輯塊于邏輯塊10(即最后一次訪問的塊是邏輯塊即最后一次訪問的塊是邏輯塊10)，且，且希望訪問邏輯塊希望訪問邏輯塊4，那么必須分別從盤上讀，那么必須分別從盤上讀_，_，_個

27、物理塊。個物理塊。37課外思考題課外思考題文件系統(tǒng)采用多重索引結(jié)構(gòu)搜索文件內(nèi)容。設(shè)文件系統(tǒng)采用多重索引結(jié)構(gòu)搜索文件內(nèi)容。設(shè)塊長為塊長為512字節(jié)字節(jié),每個塊號長每個塊號長3字節(jié)字節(jié),如果不考慮如果不考慮邏輯塊號在物理塊中所占的位置邏輯塊號在物理塊中所占的位置,分別求二級索分別求二級索引和三級索引時可尋址的文件最大長度。引和三級索引時可尋址的文件最大長度。（西電（西電2002）388.2文件存儲空間的管理文件存儲空間的管理有有4種不同的空閑塊管理方法。它們是：種不同的空閑塊管理方法。它們是：(1) 空閑文件表；空閑文件表；(2) 空閑塊鏈；空閑塊鏈；(3) 位示圖；位示圖；(4) 成組鏈接法。成

28、組鏈接法。下面介紹這幾種空閑空間的分配方法。下面介紹這幾種空閑空間的分配方法。391、空閑文件表、空閑文件表簡單的空閑塊管理方法就是簡單的空閑塊管理方法就是把文件存儲設(shè)把文件存儲設(shè)備中的備中的空閑塊的塊號空閑塊的塊號統(tǒng)一放在一個稱為空統(tǒng)一放在一個稱為空閑文件目錄的物理塊中閑文件目錄的物理塊中。其中空閑文件目錄的每個表項對應(yīng)一個由其中空閑文件目錄的每個表項對應(yīng)一個由多個空閑塊構(gòu)成的空閑區(qū)，它包括多個空閑塊構(gòu)成的空閑區(qū)，它包括空閑塊空閑塊個數(shù)，空閑塊號和第一個空閑塊號個數(shù)，空閑塊號和第一個空閑塊號等。等。 401、空閑文件表、空閑文件表41存儲空間的分配和回收存儲空間的分配和回收在系統(tǒng)為某個文件分

29、配空閑塊時，首先掃描空閑分區(qū)表的在系統(tǒng)為某個文件分配空閑塊時，首先掃描空閑分區(qū)表的各表項，如找到合適的空閑區(qū)項，則分配給申請者，并把各表項，如找到合適的空閑區(qū)項，則分配給申請者，并把該項從空白文件目錄中去調(diào)。如果一個空閑區(qū)項不能滿足該項從空白文件目錄中去調(diào)。如果一個空閑區(qū)項不能滿足申請者要求，則把目錄中另一項分配給申請者。如果一個申請者要求，則把目錄中另一項分配給申請者。如果一個空閑區(qū)項所含塊數(shù)超過申請者要求，則為申請者分配了所空閑區(qū)項所含塊數(shù)超過申請者要求，則為申請者分配了所要的物理塊之后，再修改該表項。要的物理塊之后，再修改該表項。 當(dāng)一個文件被刪除，釋放存儲物理塊時，系統(tǒng)則把被釋放當(dāng)一個

30、文件被刪除，釋放存儲物理塊時，系統(tǒng)則把被釋放的塊號、長度以及第一塊塊號置入空閑分區(qū)表的新表項中。的塊號、長度以及第一塊塊號置入空閑分區(qū)表的新表項中。顯然，我們在內(nèi)存管理時討論過有關(guān)空閑連續(xù)區(qū)分配和釋顯然，我們在內(nèi)存管理時討論過有關(guān)空閑連續(xù)區(qū)分配和釋放算法。只要稍加修改就可用于空閑分區(qū)表的分配和回收。放算法。只要稍加修改就可用于空閑分區(qū)表的分配和回收。 空閑分區(qū)表方法適用于連續(xù)文件結(jié)構(gòu)的文件存儲區(qū)的分空閑分區(qū)表方法適用于連續(xù)文件結(jié)構(gòu)的文件存儲區(qū)的分配與回收。配與回收。422、空閑塊鏈、空閑塊鏈空閑塊鏈?zhǔn)且环N較常用的空閑塊管理方法?？臻e塊鏈?zhǔn)且环N較常用的空閑塊管理方法。空閑塊鏈把文件存儲設(shè)備上的所

31、有空閑塊鏈把文件存儲設(shè)備上的所有空閑塊鏈接空閑塊鏈接在一起，當(dāng)申請者需要空閑塊時，分配程序從在一起，當(dāng)申請者需要空閑塊時，分配程序從鏈頭開始摘取所需要的空閑塊，然后調(diào)整鏈?zhǔn)祖滎^開始摘取所需要的空閑塊，然后調(diào)整鏈?zhǔn)字羔樦羔?。反之，?dāng)回收空閑塊時，把釋放的空閑。反之，當(dāng)回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上。塊逐個插入鏈尾上。43 2.空閑塊鏈空閑塊鏈空閑塊鏈?zhǔn)疽鈭D r1 57 r2 r0 150 rn 443.位示圖位示圖系統(tǒng)首先從系統(tǒng)首先從內(nèi)存中分配若干個字節(jié)內(nèi)存中分配若干個字節(jié)，為每個文件，為每個文件存儲設(shè)備建立存儲設(shè)備建立一張位示圖一張位示圖。這張位示圖反映每個文件存儲設(shè)備的使用情況。

32、這張位示圖反映每個文件存儲設(shè)備的使用情況。在位示圖中，每個文件存儲設(shè)備的物理塊都對應(yīng)在位示圖中，每個文件存儲設(shè)備的物理塊都對應(yīng)一個比特位。一個比特位。n如果該位為如果該位為“0”，則表示所對應(yīng)的塊是空閑塊；，則表示所對應(yīng)的塊是空閑塊；n反之，如果該位為反之，如果該位為“1”，則表示所對應(yīng)的塊已被，則表示所對應(yīng)的塊已被分配出去。分配出去。45位示圖 3.位示圖位示圖46盤塊的分配：盤塊的分配： (1) 順序掃描位示圖，從中找出一個或一組其值為順序掃描位示圖，從中找出一個或一組其值為“0”的二進(jìn)制位的二進(jìn)制位(“0”表示空閑時表示空閑時)。 (2) 將所找到的一個或一組二進(jìn)制位，將所找到的一個或一

33、組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為的盤塊號。假定找到的其值為“0”的二進(jìn)制位，位于位示的二進(jìn)制位，位于位示圖的第圖的第i行、第行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算：列，則其相應(yīng)的盤塊號應(yīng)按下式計算： b=n(i-1)+j （皆從（皆從1開始編號）開始編號）式中，式中， n代表每行的位數(shù)。代表每行的位數(shù)。 (3) 修改位示圖，修改位示圖， 令令mapi,j=1。 3.位示圖位示圖47盤塊的回收：盤塊的回收： (1) 將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。列號。 轉(zhuǎn)換公式為：轉(zhuǎn)換公式為： i=(b-1)DIV n

34、+1 j=(b-1)MOD n+1(2) 修改位示圖。修改位示圖。 令令map i,j=0。 3.位示圖位示圖48例題：設(shè)某系統(tǒng)磁盤共有500塊，塊號從0499，若用位示圖法管理這500塊的盤空間，當(dāng)字長為32位時：(1)位示圖需要多少個字？(2)第i字第j位對應(yīng)的塊號是多少？（西安理工2001)參考答案：參考答案： (1)位示圖需要位示圖需要: 500/32=16個字。個字。(2)第第i字第字第j位對應(yīng)的塊號是位對應(yīng)的塊號是:32(i)+j。位示圖方法可用于位示圖方法可用于( )。A.盤空間的管理盤空間的管理 B.盤的驅(qū)動調(diào)度盤的驅(qū)動調(diào)度C.文件目錄的查找文件目錄的查找 D.頁式虛擬存貯管理

35、中的頁面調(diào)度頁式虛擬存貯管理中的頁面調(diào)度494、成組鏈接法、成組鏈接法在在UNIX系統(tǒng)中，將空閑塊分成若干組，每系統(tǒng)中，將空閑塊分成若干組，每100個空閑塊為個空閑塊為一組，每組的第一空閑塊登記了下一組空閑塊的物理盤塊一組，每組的第一空閑塊登記了下一組空閑塊的物理盤塊號和空閑塊總數(shù)。如果一個組的第一個空閑塊號等于號和空閑塊總數(shù)。如果一個組的第一個空閑塊號等于0，則有特殊的含義，意味著該組是最后一組，即無下一個空則有特殊的含義，意味著該組是最后一組，即無下一個空閑塊。閑塊。 分配空閑塊的時候，從前往后分配，先從第一組開始分配，分配空閑塊的時候，從前往后分配，先從第一組開始分配，第一組空閑的第一組空閑的100塊分完了，才進(jìn)入第二組。塊分完了，才進(jìn)入第二組。 釋放空閑塊的時候正好相反，從后往前分配，先將釋放的釋放空閑塊的時候正好相反，從后往前分配，先將釋放的空閑塊放到第一組，第一組滿了，在第一組前再開辟一組，空閑塊放到第一組，第一組滿了，在第一組前再開辟一組，之前的第一組變成第二組。之前的第一組變成第二組。 501. 空閑盤塊的組織空閑盤塊的組織100400399301300100300299202201299100400399201301990799979017900789978017