【正文】 50K512K為空閑塊 （ 3）若在申請 80K，兩種算法都不能滿足要求，這說明段式存儲存在碎片，也就是雖然整個空閑空間滿足用戶要求，但是空閑塊不連續(xù)不能分配。 段式存儲管理方案下，空閑塊分配的計算 2 移動技術(shù) 假定計算機系統(tǒng)的內(nèi)存容量為 32K，對內(nèi)存采用動態(tài)可變分區(qū)分配算法?，F(xiàn)已有 3個作業(yè)在內(nèi)存中，當(dāng)作業(yè) J2執(zhí)行時要求擴充3K內(nèi)存。為滿足此要求，應(yīng)移動哪個作業(yè)的信息。 J1 J2 J3 0K 4K 6K 12K 13K 22K 23K 30K 32K 例 1：某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為 4， 3， 2， 1， 4， 3，5， 4， 3， 2， 1， 5，計算缺頁次數(shù) 頁面置換算法 1 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁 1 4 3 2 1 4 3 5 5 5 2 1 1 頁 2 4 3 2 1 4 3 3 3 5 2 2 頁 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x ? ? x x ? 共缺頁中斷 9次 頁面置換算法 2 LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁 1 4 3 2 1 4 3 5 4 3 2 1 5 頁 2 4 3 2 1 4 3 5 4 3 2 1 頁 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x ? ? x x x 共缺頁中斷 10次 頁面置換算法 3 OPT 4 3 2 1 4 3 5 4 3 2 1 5 頁 1 4 3 2 1 1 1 5 5 5 2 1 1 頁 2 4 3 3 3 3 3 3 3 5 5 5 頁 3 4 4 4 4 4 4 4 4 4 4 x x x x ? ? x ? ? x x ? 共缺頁中斷 7次 頁面置換算法 4 例 2：某程序在內(nèi)存中分配 m頁初始為空，頁面走向為 1， 2， 3， 4， 1， 2， 5， 1，2， 3， 4， 5。當(dāng) m=3， m=4時缺頁中斷分別為多少？用 FIFO算法計算缺頁次數(shù)。解釋說明出現(xiàn)的結(jié)果。 m=3時，缺頁中斷 9次， m=4時，缺頁中斷 10次 FIFO頁面淘汰算法會產(chǎn)生異?，F(xiàn)象（ Belady現(xiàn)象），即：當(dāng)分配給進程的物理頁面數(shù)增加時，缺頁次數(shù)反而增加 頁面置換算法 5 例子 3：內(nèi)存分配一頁，初始時第一頁在內(nèi)存；頁面大小為 128個整數(shù)；矩陣 A128X128按行存放 程序編制方法 1： For j:=1 to 128 For i:=1 to 128 A[i,j]:=0。 程序編制方法 2： For i:=1 to 128 For j:=1 to 128 A[i,j]:=0。 頁面置換算法 6 分配給進程的物理頁面數(shù) 頁面本身的大小 程序的編制方法 頁面淘汰算法 影響缺頁次數(shù)的因素 利用索引文件結(jié)構(gòu)管理存儲塊時，計算讀盤量 假定一個文件系統(tǒng)用索引文件結(jié)構(gòu)管理存儲塊。每個文件有一個目錄項，存放文件名、第一個索引塊、以及文件長度。第一索引塊指向 248個文件塊和下一個索引塊。如果一個文件當(dāng)前在第 2020邏輯塊，而下一個操作是訪問第 306個邏輯塊，那么必須從磁盤上讀多少個物理塊？ 答案： 3個物理塊 UNIX系統(tǒng)中采用索引文件結(jié)構(gòu) 管理存儲塊的相關(guān)計算 1 有一個文件系統(tǒng)，根目錄常駐內(nèi)存，如圖所示： 目錄文件采用鏈接結(jié)構(gòu)，規(guī)定一個目錄下最多存放 40個下級文件。下級文件可以是目錄文件，也可以是普通文件。每個磁盤塊可存放 10個下級文件的描述信息，若下級文件為目錄文件，則上級目錄指向該目錄文件的第一塊，否則指向普通文件的文件控制塊。 \A\D\G\I\K （ 1）普通文件采用 UNIX的三級索引結(jié)構(gòu)，即文件控制塊中給出 13個磁盤地址，前 10個磁盤地址指出文件前 10塊的物理地址，第 11個磁盤地址指向一級索引表，一級索引表給出 256個磁盤地址，即指出該文件第 11塊至第 266塊的物理地址；第 12個磁盤地址指向二級索引表，二級索引表中指出 256個一級索引表的地址；第 13個磁盤地址指向三級索引表，三級索引表中指出 256個二級索引表的地址。該文件系統(tǒng)中的普通文件最大可有多少塊？ 假設(shè)主索引表放在 FCB中，若要讀文件 \A\D\G\I\K中的某一塊，最少要啟動磁盤幾次？ 最多要啟動磁盤幾次？若要減少啟動磁盤的次數(shù)，可采用什么方法？ UNIX系統(tǒng)中采用索引文件結(jié)構(gòu) 管理存儲塊的相關(guān)計算 2 UNIX系統(tǒng)中采用索引文件結(jié)構(gòu) 管理存儲塊的相關(guān)計算 3 （ 2）普通文件采用鏈接結(jié)構(gòu)，若要讀 \A\D\G\I\K的第 75塊最少啟動硬盤幾次，最多幾次？ 答案： （ 1）一個文件的所有塊可以通過下面三種途徑找到：直接通過 FCB找到前 10塊，通過一級索引找到 256塊，通過二級索引找到 256*256塊，通過三級索引找到256*256*256塊，所以一個文件最大可以有10+256+256^2+256^3=16,843,018塊 如果要找 \A\D\G\I\K中的某一塊，首先要找到其 FCB，最好的情況是：每次讀取目錄描述信息的時候都在第一塊找到下級目錄或文件，所以要找到該文件至少要讀取 A、 D、 G、 I四個目錄項的第一塊，讀取 K的 FCB，總共 5次啟動硬盤；最壞情況是：每次讀取目錄描述信息的時候都在最后一個塊找到下級的目錄或文件，所以要找到該文件，所以要找到該文件至少要讀取 A的第一塊， D、 G、 I三個目錄項的所有四個塊，在讀取 K的 FCB，總共要 1+4*3+1＝ 14次啟動硬盤。找到 FCB后在讀取某一塊，如果這一塊在前 10塊之列，那么在啟動一 次硬盤就可以找到這一塊，如果這一塊在最后一塊，則可能需要通過三級索引找到這一塊，這總共需要讀取三級索引和最后一塊共 3+1次讀取硬盤。綜上，最好情況下只需要啟動5+1次硬盤，最壞情況需要啟動 14+3+1＝ 18次硬盤 UNIX系統(tǒng)中采用索引文件結(jié)構(gòu) 管理存儲塊的相關(guān)計算 4 若要減少硬盤啟動的次數(shù)，第一可以對于經(jīng)常訪問的文件項或者目錄進行項緩存，第二可以用散列表將常用的文件和目錄進行散列，第三增減常駐內(nèi)存的目錄描述的數(shù)量（可以考慮將所有的一級和二級目錄常駐內(nèi)存），第四減少文件描述項的大小，使得每一塊可以存放更多的文件描述項（更祥細的文件描述信息可以轉(zhuǎn)存他處。） （ 2）為讀取 FCB所啟動的硬盤次數(shù)和（ 1）一樣，那么讀取第 75塊最少需要 5+75＝ 80次硬盤，最多需要啟動 14+75＝ 89次硬盤。 UNIX系統(tǒng)中采用索引文件結(jié)構(gòu) 管理存儲塊的相關(guān)計算 5 1文件控制塊分解法的計算 1 在實現(xiàn)文件系統(tǒng)時，為加快文件目錄的檢索速度，可利用“文件控制塊分解法”。 假設(shè)目錄文件存放在磁盤上，每個盤塊 512 字節(jié)。文件控制塊占 48 字節(jié)，其中文件名占 6字節(jié)，文件號 2字節(jié)。文件控制塊分解后，第一部分占有 8字節(jié)（包括文件名和文件內(nèi)部號），第二部分占 42字節(jié)（包括文件內(nèi)部號和文件其他信息） （ 1）假設(shè)某一目錄文件共有 128個目錄項，試分別給出采用分解法前和分解法后，查找該目錄文件的一個文件控制塊的平均訪盤次數(shù)。 （ 2）一般地，若目錄文件分解前占用 n個盤塊，分解后改用 m個盤塊存放文件名和文件內(nèi)部號部分，請給出訪盤次數(shù)減少的條件。 1文件控制塊分解法的計算 2 解：分解前：占 512/48=10個 FCB 分解后：占 512/8=64個符號目錄項 或 512/42=12個基本目錄項 分解前：占 13塊 分解后：符號文件占 2塊，基本文件占 11塊 查找一個文件的平均訪盤次數(shù) 分解前： (1+13)/2=7次 分解后： (1+2)/2 +1 = 減少了訪問硬盤的次數(shù)，提高了檢索速度 （ 2）分解前：（ 1＋ n） /2 分解后 (1+m)/2+1； 訪盤次數(shù)減少的條件： nm2 1記錄的成組和分解 設(shè)磁帶的記錄密度為每英寸 800個字符，每一個邏輯記錄長為 240個字符，塊與塊之間的間隙為 英寸，現(xiàn)有 500個邏輯記錄需要存儲到磁帶上，試問： （ 1）未采用成組操作時，存儲信息