【正文】 頁(yè)面淘汰算法。 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)的物理地址。太大，所有頁(yè)的引用位可能都為 1，找不到合適的淘汰頁(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)存映像直接存取。 段表首址指針和段表長(zhǎng)度存放在進(jìn)程自己的 PCB中 。（ 主要用來(lái)判斷訪問(wèn)是否越權(quán) ） 83 2022/8/17 第六章 存儲(chǔ)管理 快表和聯(lián)想存儲(chǔ)器 ? 在前述的頁(yè)地址變換過(guò)程中有一個(gè)嚴(yán)重的問(wèn)題 ， 那就是每一次對(duì)內(nèi)存的訪問(wèn)都要訪問(wèn)頁(yè)表 ， 頁(yè)表是放在內(nèi)存中的 ， 也就是說(shuō)每一次訪問(wèn)內(nèi)存的指令至少要訪問(wèn)兩次內(nèi)存 ， 運(yùn)行速度要下降一半 。 ? IBM AS/400 VAX NS32032 ： 512字節(jié) ? Intel 80386 Motorola 68030 4096字節(jié) 頁(yè)的大小是 2K ， k： 912。 ? 定期壓縮存儲(chǔ)空間，將所有空閑區(qū)集中到內(nèi)存的一端，但這種方法的系統(tǒng)開銷太大。 54 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：進(jìn)程申請(qǐng)一個(gè)大小為 SIZE的存儲(chǔ)區(qū)時(shí)，總是檢查空閑區(qū)表的第一個(gè)空閑區(qū)的大小是否大于或等于 SIZE。 46 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE的內(nèi)存時(shí) ， 系統(tǒng)從空閑區(qū)表的第一個(gè)表目開始查詢 ， 直到首次找到等于或大于 SIZE的空閑區(qū) 。 36 2022/8/17 第六章 存儲(chǔ)管理 空閑區(qū)表和空閑區(qū)隊(duì)列舉例 37 2022/8/17 第六章 存儲(chǔ)管理 動(dòng)態(tài)分區(qū)的分配和回收 分區(qū)的分配 在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中 ， 系統(tǒng)初啟后 。 ? 要由操作系統(tǒng)結(jié)合相關(guān)硬件來(lái)完成上述工件，這樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為 虛擬存儲(chǔ)器 。 18 2022/8/17 第六章 存儲(chǔ)管理 置換策略 ? 當(dāng)需要將某個(gè)用戶程序調(diào)入內(nèi)存而內(nèi)存空間又不夠時(shí) ， 就要確定哪個(gè)或哪些程序可以從內(nèi)存中移走 。 ? 缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間；一旦程序裝入后不能移動(dòng)。 。 ? 便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼 。 這種面向編程的存儲(chǔ)器稱為 虛擬存儲(chǔ)器 。 是一種較為實(shí)用的存儲(chǔ)管理方法 。 其首址仍為前空閑區(qū)首址 ， 大小為釋放區(qū)大小與空閑區(qū)大小之和 。 52 2022/8/17 第六章 存儲(chǔ)管理 分析 優(yōu)點(diǎn)： ? 在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū) ，必定會(huì)被選中 ， 而首次適應(yīng)法則不一定 。 59 2022/8/17 第六章 存儲(chǔ)管理 練習(xí) ? 有作業(yè)序列：作業(yè) A要求 21K； 作業(yè) B要求 30K， 作業(yè)C要求 25K。 ? 占用處理機(jī)的現(xiàn)行進(jìn)程的頁(yè)表必須駐留在內(nèi)存 ， 其首地址和長(zhǎng)度由地址映射機(jī)構(gòu)的 頁(yè)表起址和長(zhǎng)度寄存器 指示 。 80 2022/8/17 第六章 存儲(chǔ)管理 若給出的地址字為 10進(jìn)制 ， 則用公式： 程序地址字 /頁(yè)長(zhǎng) 商為頁(yè)號(hào) ， 余數(shù)為頁(yè)內(nèi)地址 。 89 2022/8/17 第六章 存儲(chǔ)管理 兩級(jí)頁(yè)表和多級(jí)頁(yè)表 ? 當(dāng)頁(yè)表項(xiàng)很多時(shí) ， 僅采用一級(jí)頁(yè)表需要大片邊續(xù)空間 ， 可將頁(yè)表也分頁(yè) ， 并對(duì)頁(yè)表所占的空間進(jìn)行索引形成外層頁(yè)表 。 ? 段是面向用戶的 ， 頁(yè)對(duì)用戶而言是透明的 。 當(dāng)系統(tǒng)要淘汰一節(jié)時(shí) ， 總是從頁(yè)號(hào)棧底取出一個(gè)頁(yè)號(hào)淘汰 ， 即淘汰的頁(yè)是最久未使用的 。 程序編制方法 2： for i:=1 to 128 for j:=1 to 128 A[i,j]:=0。 例 2 147 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次 m=3 148 2022/8/17 第六章 存儲(chǔ)管理 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 1 1 5 4 3 2 1 5 頁(yè) 2 4 3 2 2 2 1 5 4 3 2 1 頁(yè) 3 4 3 3 3 2 1 5 4 3 2 頁(yè) 4 4 4 4 3 2 1 5 4 3 x x x x ? ? x x x x x x 共缺頁(yè)中斷 10次 m=4 149 2022/8/17 第六章 存儲(chǔ)管理 m=3時(shí)，缺頁(yè)中斷 9次 m=4時(shí)，缺頁(yè)中斷 10次 FIFO頁(yè)面淘汰算法會(huì)產(chǎn)生異常現(xiàn)象（ Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁(yè)面數(shù)增加時(shí)，缺頁(yè)次數(shù)反而增加 150 2022/8/17 第六章 存儲(chǔ)管理 (1) 分配給進(jìn)程的物理塊數(shù) (2) 頁(yè)本身的大小 (3) 程序的編制方法 (4) 頁(yè)淘汰算法 影響缺頁(yè)次數(shù)的因素 151 2022/8/17 第六章 存儲(chǔ)管理 練習(xí) 程序編制方法 1： for j:=1 to 128 for i:=1 to 128 A[i,j]:=0。所以淘汰的是最久未使用的頁(yè)。 102 2022/8/17 第六章 存儲(chǔ)管理 快表 ? 同頁(yè)地址變換一樣 ， 在段地址變換過(guò)程中 ，也有兩次訪問(wèn)內(nèi)存的問(wèn)題 。 ? 硬件根據(jù)需要將頁(yè)表中當(dāng)前需要的少量表目讀入快表 ， 其它表目仍留在內(nèi)存的頁(yè)表中 ， 當(dāng)需要時(shí)讀入新的表目 ， 并淘汰適當(dāng)?shù)谋砟?。 ? 將 VR中的 W的值 452復(fù)制到 MR的低 10位中 ， 從而形成內(nèi)存地址 。一般，一頁(yè)的大小為 2的整數(shù)次冪，因此，地址的高位部分為 頁(yè)號(hào) ，低位部分為 頁(yè)內(nèi)地址 頁(yè)號(hào) 頁(yè)內(nèi)地址 0 11 12 31 頁(yè)號(hào) P 頁(yè)內(nèi)位移量 W 編號(hào) 0~1048575 相對(duì)地址 0~4095 66 2022/8/17 第六章 存儲(chǔ)管理 ? 內(nèi)存空間 按頁(yè)的大小劃分為大小相等的區(qū)域，稱為 塊或內(nèi)存塊（物理頁(yè)面，頁(yè)框） 67 2022/8/17 第六章 存儲(chǔ)管理 ? 內(nèi)存分配 以頁(yè)為單位進(jìn)行分配，并按作業(yè)的頁(yè)數(shù)多少來(lái)分配。 ? 對(duì)于某一作業(yè)序列來(lái)說(shuō) ， 某種算法能將該作業(yè)序列中所有作業(yè)安置完畢 ， 那么我們說(shuō) 該算法對(duì)這一作業(yè)序列是合適的 。 50 2022/8/17 第六章 存儲(chǔ)管理 ? 分配：當(dāng)進(jìn)程申請(qǐng)一個(gè)存儲(chǔ)區(qū)時(shí)，系統(tǒng)從表頭開始查找，當(dāng)找到第一個(gè)滿足要求的空閑區(qū)時(shí)，停止查找，并且這個(gè)空閑區(qū)是最佳的空閑區(qū)。 將一個(gè)空閑區(qū)分成二部分有兩種辦法： 一是從空閑區(qū)的上部開始劃出 SIZE大小的空閑區(qū)給用戶； 二是從空閑區(qū)的底部開始向上劃出 SIZE大小的空閑區(qū)給用戶 。 在這種情況下分區(qū)的大小選擇與作業(yè)大小相當(dāng) ， 這樣內(nèi)存的使用效率較高 。 由于內(nèi)存有限 ，系統(tǒng)中不可能容納所有進(jìn)程 ， 有些進(jìn)程的映像可以存放在外存 ， 當(dāng)要運(yùn)行這些進(jìn)程時(shí) ， 必須把它們調(diào)入內(nèi)存 。 ? 地址轉(zhuǎn)換機(jī)構(gòu)把 VR和 BR中的內(nèi)容相加，并將結(jié)果送入 MR中，作為實(shí)際訪問(wèn)的地址。 ? 內(nèi)存地址的集合稱為 內(nèi)存空間（或物理地址空間） 。 ? 在地址重定位機(jī)構(gòu)中 ， 有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器 VR， 一個(gè)內(nèi)存地址寄存器 MR。 ? 進(jìn)程運(yùn)行的過(guò)程中 ， 它所占用的內(nèi)存也可能發(fā)生變化 。 ? 早期的 IBM的 OS/360MFT（ 具有固定任務(wù)數(shù)的多道程序系統(tǒng) ） 采用了這種固定分區(qū)的方法 。 38 2022/8/17 第六章 存儲(chǔ)管理 分配時(shí)的三種情況 ? 其一是系統(tǒng)中無(wú)滿足要求的空閑區(qū) ， 則分配失敗 。 首次適應(yīng)法的優(yōu)點(diǎn)： ? 釋放某一存儲(chǔ)區(qū)時(shí) ， 若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去 ， 這種情況并不改變?cè)搮^(qū)在表中的位置 ， 只要修改其大小或首址 。 56 2022/8/17 第六章 存儲(chǔ)管理 分析 最壞適應(yīng)法看起來(lái)公似乎有些荒唐 ， 但在更加嚴(yán)密地考察后 ， 還是有它的優(yōu)點(diǎn)： ? 當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后 ， 剩下的空閑區(qū)還可能相當(dāng)大 ， 還能裝下較大的程序 。 這種技術(shù)對(duì)操作系統(tǒng)的發(fā)展產(chǎn)生了深遠(yuǎn)影響 。 77 2022/8/17 第六章 存儲(chǔ)管理 說(shuō)明 ? 在執(zhí)行指令 MOV r1， [2500]時(shí) ， 地址轉(zhuǎn)換步驟如下： ? 取出程序地址字 2500送虛地址寄存器 VR， 然后由硬件分離出頁(yè)號(hào) P和頁(yè)內(nèi)地址 W， 實(shí)際上分離出頁(yè)號(hào)和頁(yè)內(nèi)地址是一件很簡(jiǎn)單的事 ， 因?yàn)轫?yè)長(zhǎng)為 1K， 所以頁(yè)內(nèi)地址占 10位 （ 09位 ） ， 頁(yè)號(hào)占 6位 （ 1015位 ） ，所以硬件只要簡(jiǎn)單地取出 VR寄存器中的高 6位即為頁(yè)號(hào) ， 低 10 位即為頁(yè)內(nèi)地址 。 ? 快表又叫 相聯(lián) (聯(lián)想 )存儲(chǔ)器 （ associative memory） 或 TLB（ Translation lookaside buffers） 85 2022/8/17 第六章 存儲(chǔ)管理 討論 深入一點(diǎn)的討論： 一個(gè)程序可能會(huì)很大 ， 如 1M， 若頁(yè)長(zhǎng)為 1K， 則該程序有 1000個(gè)頁(yè) ， 則該程序的頁(yè)表就需要 1000個(gè)表項(xiàng) ， 當(dāng)程序更大時(shí) ， 頁(yè)表會(huì)更大 ， 那么我們應(yīng)該有一個(gè)多大的快速存儲(chǔ)器才能滿足要求呢 ？ 這會(huì)遇到兩個(gè)問(wèn)題： ? 可能快速存儲(chǔ)器多大都是不夠的 ， 因?yàn)槌绦蚩赡軙?huì)更大 。 ? 取出段號(hào) S和段內(nèi)位移 W。如指令可能訪問(wèn)多個(gè)內(nèi)存地址，這些地址在不同的頁(yè)中。進(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è)。 (1) 如果對(duì)主存的一次存取要 3us， 問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)要多長(zhǎng)時(shí)間。 缺點(diǎn)： T難定。 ? 段的共享比頁(yè)的共享更容易。 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)及其地址