【正文】 163 2022/8/17 第六章 存儲(chǔ)管理 ? 2*3=6us ? *3+*6= 164 2022/8/17 第六章 存儲(chǔ)管理 在分頁(yè)存儲(chǔ)管理系統(tǒng)中，有一作業(yè)大小為 4頁(yè)，頁(yè)長(zhǎng)為 2K， 頁(yè)表如下： 試借助地址變換圖（即要求畫出地址變換圖）求出邏輯地址 4635所對(duì)應(yīng)的物理地址。 (1) 如果對(duì)主存的一次存取要 3us， 問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)要多長(zhǎng)時(shí)間。 128*128 128 153 2022/8/17 第六章 存儲(chǔ)管理 在虛存中，頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。 這兩個(gè)程序執(zhí)行時(shí)分別會(huì)產(chǎn)生多少次缺頁(yè)中斷？ 152 2022/8/17 第六章 存儲(chǔ)管理 解 程序編制方法 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。 (3) 如何解釋所出現(xiàn)的現(xiàn)象。進(jìn)程執(zhí)行時(shí)使用頁(yè)號(hào)的順序?yàn)? 4 3 2 1 4 3 5 4 3 2 1 5 (1) 該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)幾次缺頁(yè)。 139 2022/8/17 第六章 存儲(chǔ)管理 某程序在內(nèi)存中分配三個(gè)塊，訪問(wèn)頁(yè)的走向?yàn)?4， 3， 2， 1， 4， 3， 5， 4， 3， 2， 1，5，按 FIFO、 LRU、 OPT算法分別計(jì)算缺頁(yè)次數(shù) 假設(shè)開始時(shí)所有頁(yè)均不在內(nèi)存 例 1 140 2022/8/17 第六章 存儲(chǔ)管理 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 4 3 5 5 5 2 1 1 頁(yè) 2 4 3 2 1 4 3 3 3 5 2 2 頁(yè) 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x ? ? x x ? 共缺頁(yè)中斷 9次 FIFO 141 2022/8/17 第六章 存儲(chǔ)管理 LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 2 4 3 2 1 4 3 5 4 3 2 1 頁(yè) 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x ? ? x x x 共缺頁(yè)中斷 10次 LRU 142 2022/8/17 第六章 存儲(chǔ)管理 OPT 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 1 1 5 5 5 2 1 1 頁(yè) 2 4 3 3 3 3 3 3 3 5 5 5 頁(yè) 3 4 4 4 4 4 4 4 4 4 4 x x x x ? ? x ? ? x x ? 共缺頁(yè)中斷 7次 OPT 143 2022/8/17 第六章 存儲(chǔ)管理 練習(xí) 某程序在內(nèi)存中分配 四 個(gè)塊，訪問(wèn)頁(yè)的走向?yàn)?， 3， 2， 1， 4， 3， 5， 4， 3， 2， 1， 5，按LRU、 OPT算法分別計(jì)算缺頁(yè)次數(shù) 假設(shè)開始時(shí)所有頁(yè)均不在內(nèi)存 144 2022/8/17 第六章 存儲(chǔ)管理 LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 2 4 3 2 1 4 3 5 4 3 2 1 頁(yè) 3 4 3 2 1 4 3 5 4 3 2 頁(yè) 4 4 3 2 1 1 1 5 4 3 x x x x ? ? x ? ? x x x 共缺頁(yè)中斷 8次 145 2022/8/17 第六章 存儲(chǔ)管理 OPT 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 1 1 5 5 5 5 1 1 頁(yè) 2 4 3 2 2 2 2 2 2 2 5 5 頁(yè) 3 4 3 3 3 3 3 3 3 3 3 頁(yè) 4 4 4 4 4 4 4 4 4 4 x x x x ? ? x ? ? ? x ? 共缺頁(yè)中斷 6次 146 2022/8/17 第六章 存儲(chǔ)管理 有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出的頁(yè)面淘汰算法。太大，所有頁(yè)的引用位可能都為 1，找不到合適的淘汰頁(yè)。 缺點(diǎn)： T難定。 137 2022/8/17 第六章 存儲(chǔ)管理 LRU近似算法： 在頁(yè)表中增加一訪問(wèn)位，每當(dāng)訪問(wèn)一頁(yè)時(shí)，將該頁(yè)的訪問(wèn)位由硬件置 1，軟件周期（ T） 性地將所有訪問(wèn)位置 0。 136 2022/8/17 第六章 存儲(chǔ)管理 LRU軟件解法： 設(shè)置一個(gè)頁(yè)號(hào)棧 ， 當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí) ， 就立即將它的頁(yè)號(hào)壓入頁(yè)號(hào)棧 ， 并檢查頁(yè)號(hào)棧中是否有與剛壓入棧頂?shù)南嗤捻?yè)號(hào) ， 若有 ， 則從頁(yè)號(hào)棧中抽出 ，以保證頁(yè)號(hào)棧中無(wú)相同的頁(yè)號(hào) 。顯然， R的位數(shù)越多越精確。也就是說(shuō) R值越大，對(duì)應(yīng)的頁(yè)未被使用的時(shí)間越長(zhǎng)。如指令可能訪問(wèn)多個(gè)內(nèi)存地址，這些地址在不同的頁(yè)中。 ? 覆蓋只能覆蓋那些與覆蓋段無(wú)關(guān)的程序段 123 2022/8/17 第六章 存儲(chǔ)管理 虛擬存儲(chǔ) 以 CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù) ? 概述 ? 虛擬頁(yè)式存儲(chǔ)管理 ? 虛擬段式存儲(chǔ)管理 124 2022/8/17 第六章 存儲(chǔ)管理 概述 程序局部性原理 ? 時(shí)間局部性 一條指令被執(zhí)行了，則在不久的將來(lái)它可能再被執(zhí)行 ? 空間局部性 若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該存儲(chǔ)單元相鄰的單元可能被使用 125 2022/8/17 第六章 存儲(chǔ)管理 、虛擬頁(yè)式存儲(chǔ)管理 基本思想 在進(jìn)程開始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入幾個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面； 當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面 126 2022/8/17 第六章 存儲(chǔ)管理 X X X X 7 X 5 X X X 3 4 0 6 1 2 60K64K 56K60K 52K56K 48K52K 44K48K 40K44K 36K40K 32K36K 28K32K 24K28K 20K24K 16K20K 12K16K 8K12K 4K8K 0K4K 28K32K 24K28K 20K24K 16K20K 12K16K 8K12K 4K8K 0K4K 虛地址空間 物理地址空間 } 虛頁(yè) 頁(yè)框 127 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)表表項(xiàng) 頁(yè)號(hào) 、 內(nèi)存塊號(hào)、 駐留位、 外存地址 、訪問(wèn)位、修改位 ? 駐留位（中斷位）：表示該頁(yè)是在內(nèi)存還是在外存 ? 訪問(wèn)位：根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定） ? 修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò) 頁(yè)號(hào) 中斷位 內(nèi)存塊號(hào) 外存地址 訪問(wèn)位 修改位 128 2022/8/17 第六章 存儲(chǔ)管理 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 000 0 000 0 000 0 000 0 111 1 000 0 101 1 000 0 000 0 000 0 011 1 100 1 000 1 110 1 001 1 010 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 110 在 /不在內(nèi)存 頁(yè)表 虛地址 8196 物理地址 24580 129 2022/8/17 第六章 存儲(chǔ)管理 缺頁(yè)中斷（ Page Fault） 處理 ? 在地址映射過(guò)程中，在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存，則產(chǎn)生 缺頁(yè)中斷 。 119 2022/8/17 第六章 存儲(chǔ)管理 交換時(shí)機(jī)的確定 何時(shí)需發(fā)生交換？ 例子： ?只要不用就換出（或很少再用） ?只在內(nèi)存空間不夠或有不夠的危險(xiǎn)時(shí)換出 120 2022/8/17 第六章 存儲(chǔ)管理 交換時(shí)需要做哪些工作？ 需要一個(gè)盤交換區(qū)： 必須足夠大以存放用戶程序的內(nèi)存映像的拷貝； 必須對(duì)這些內(nèi)存映像直接存取。 ? 段的共享比頁(yè)的共享更容易。 105 2022/8/17 第六章 存儲(chǔ)管理 ? 段長(zhǎng)由用戶決定，且各段的大小一般不相等，唯一的限制是最大長(zhǎng)度。 ? 段式技術(shù)中程序地址空間是二維的 ， 分頁(yè)技術(shù)中程序地址空間是一維的 。 為了加快訪問(wèn)內(nèi)存的速度也可采用快速存儲(chǔ)器組成快表 。 ? 把段首地址與段內(nèi)位移相加 ， 形成內(nèi)存地址送入 MR中 ， 并以此地址訪問(wèn)內(nèi)存 。 ? 取出段號(hào) S和段內(nèi)位移 W。 每一進(jìn)程有個(gè)段表 ， 程序的每一個(gè)段在段表中占用一個(gè)表目 。 段表首址指針和段表長(zhǎng)度存放在進(jìn)程自己的 PCB中 。 90 2022/8/17 第六章 存儲(chǔ)管理 二級(jí)頁(yè)表結(jié)構(gòu)及地址映射 頁(yè)目錄地址 目錄位移 頁(yè)表位移 頁(yè)位移 虛擬地址 頁(yè)表地址 . . . 頁(yè)目錄（每進(jìn)程一個(gè)） 塊號(hào) . . . 頁(yè)表 代碼或數(shù)據(jù) . . . 內(nèi)存塊 + + 91 2022/8/17 第六章 存儲(chǔ)管理 圖 : 三級(jí)頁(yè)表結(jié)構(gòu)及其地址映射過(guò)程 92 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)式存儲(chǔ)管理方案小結(jié) ? 優(yōu)點(diǎn)：解決了碎片問(wèn)題 便于管理 ? 缺點(diǎn)：不易實(shí)現(xiàn)共享 不便于動(dòng)態(tài)連接 93 2022/8/17 第六章 存儲(chǔ)管理 分段存儲(chǔ)管理 ? 分段存儲(chǔ)管理基本思想 ? 段地址映射 ? 段式存儲(chǔ)管理方案小結(jié) 94 2022/8/17 第六章 存儲(chǔ)管理 分段存儲(chǔ)管理基本思想 ? 用戶程序劃分 按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè)段