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