【正文】 這種現(xiàn)象稱為顛簸或抖動(dòng) 原因： ? 頁(yè)面淘汰算法不合理 ? 分配給進(jìn)程的物理頁(yè)面數(shù)太少 顛簸（抖動(dòng)） 154 2022/8/17 第六章 存儲(chǔ)管理 段表內(nèi)容 增加： ? 特征位（在 /不在內(nèi)存，是否可共享） ? 存取權(quán)限位（讀，寫，執(zhí)行） ? 標(biāo)志位（是否修改過(guò)，能否移動(dòng)） ? 擴(kuò)充位（固定長(zhǎng) /可擴(kuò)充 ） 虛擬段式存儲(chǔ)管理 155 2022/8/17 第六章 存儲(chǔ)管理 檢查內(nèi)存中是否有足夠的空閑空間 ①若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回 ②若沒(méi)有，檢查內(nèi)存中空閑區(qū)的總和是否滿足要求，是則應(yīng)采用緊縮技術(shù)，轉(zhuǎn)① ；否則，淘汰一（些）段，轉(zhuǎn)① 缺段中斷處理 156 2022/8/17 第六章 存儲(chǔ)管理 習(xí)題解答 515 分頁(yè)存儲(chǔ)管理中，信息的共享和保護(hù)有以下缺點(diǎn)： ? 共享和保護(hù)的單位要對(duì)應(yīng)多個(gè)頁(yè)表表目 ? 可能共享不該共享的內(nèi)容 157 2022/8/17 第六章 存儲(chǔ)管理 69： 10 1 7 3 4 2 5 0 塊號(hào) 頁(yè)號(hào) 1001011100 000010 1001011100 000100 頁(yè)表首址 + 0 9 程序地址 0A5C 物理地址為： 125C 158 2022/8/17 第六章 存儲(chǔ)管理 10 1 7 3 4 2 5 0 塊號(hào) 頁(yè)號(hào) 0100111100 000010 0100111100 000100 頁(yè)表首址 + 0 9 程序地址 093C 物理地址為： 113C 159 2022/8/17 第六章 存儲(chǔ)管理 作業(yè) 某程序在內(nèi)存中分配 3塊內(nèi)存 ， 初始為空 ，訪問(wèn)頁(yè)的走向?yàn)?2， 3， 2， 1， 5， 2， 4， 5，3， 2， 5， 2， 用 FIFO和 LRU算法分別計(jì)算缺頁(yè)次數(shù) 160 2022/8/17 第六章 存儲(chǔ)管理 FIFO 2 3 2 1 5 2 4 5 3 2 5 2 頁(yè) 1 2 3 3 1 5 2 4 4 3 3 5 2 頁(yè) 2 2 2 3 1 5 2 2 4 4 3 5 頁(yè) 3 2 3 1 5 5 2 2 4 3 x x ? x x x x ? x ? x x 共缺頁(yè)中斷 9次 161 2022/8/17 第六章 存儲(chǔ)管理 LRU 2 3 2 1 5 2 4 5 3 2 5 2 頁(yè) 1 2 3 2 1 5 2 4 5 3 2 5 2 頁(yè) 2 2 3 2 1 5 2 4 5 3 2 5 頁(yè) 3 3 2 1 5 2 4 5 3 3 x x ? x x ? x ? x x ? ? 共缺頁(yè)中斷 7次 162 2022/8/17 第六章 存儲(chǔ)管理 有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中。 (2) 若每個(gè)進(jìn)程在內(nèi)存有 4塊，又將產(chǎn)生幾次缺頁(yè)。在時(shí)間 T內(nèi)，訪問(wèn)過(guò)的頁(yè)其訪問(wèn)位為 1，反之為 0，淘汰為 0 的頁(yè)。 133 2022/8/17 第六章 存儲(chǔ)管理 頁(yè)面淘汰算法 ? 先進(jìn)先出頁(yè)面淘汰算法（ FIFO） 選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并淘汰之 ? 第二次機(jī)會(huì)淘汰算法 (SCR) 按照先進(jìn)先出算法選擇某一頁(yè)面，檢查其訪問(wèn)位，如果為 0，則淘汰該頁(yè)，如果為 1，則給第二次機(jī)會(huì)，并將訪問(wèn)位置 0 ? 理想淘汰算法 — 最佳頁(yè)面算法（ OPT） 淘汰以后不再需要的或最遠(yuǎn)的將來(lái)才會(huì)用到的頁(yè)面 134 2022/8/17 第六章 存儲(chǔ)管理 ? 最近最久未使用頁(yè)面淘汰算法（ LRU） 選擇最后一次訪問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之 即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè) 實(shí)現(xiàn)代價(jià)很高 軟件方法或硬件方法 135 2022/8/17 第六章 存儲(chǔ)管理 LRU的 硬件解法： 系統(tǒng)為每頁(yè)設(shè)置一個(gè)寄存器 R， 每當(dāng)訪問(wèn)這一頁(yè)時(shí)，將該頁(yè)對(duì)應(yīng)的寄存器 R置 1，以后每個(gè)時(shí)間間隔將所有的 R左移一位，當(dāng)淘汰一頁(yè)時(shí)就選擇 R值最大的頁(yè)。面頁(yè)長(zhǎng)是由系統(tǒng)決定的，各頁(yè)的長(zhǎng)度必須相等。 ? 根據(jù)段表首址指針找到段表 ， 查找段號(hào)為 S的表目 ， 得到該段的首地址 。 ? 更進(jìn)一步可形成多級(jí)頁(yè)表。 ? 快速存儲(chǔ)器是非常非常昂貴的。 81 2022/8/17 第六章 存儲(chǔ)管理 分頁(yè)存儲(chǔ)管理中的信息保護(hù) 分頁(yè)存儲(chǔ)管理中的存儲(chǔ)信息保護(hù)從兩個(gè)方面來(lái)實(shí)現(xiàn) 。 ? 當(dāng)然我們通過(guò)計(jì)算可以得到 P=2， W=452。 ? 塊號(hào)：登記相應(yīng)的頁(yè)所對(duì)應(yīng)的內(nèi)存塊號(hào) ? 其它：登記與存儲(chǔ)信息保護(hù)有關(guān)的信息 。 64 2022/8/17 第六章 存儲(chǔ)管理 ? 用戶程序劃分 把用戶程序按邏輯頁(yè)劃分成大小相等的部分 ， 稱為 頁(yè) （ page） 。 ? 這種不能被任何用戶使用的極小的空閑區(qū)稱為 碎片 。 ? 另一方面每次僅作一次查詢工作。 缺點(diǎn)： ? 空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來(lái)的空閑區(qū)一般情況下是很小的，以致無(wú)法使用。 ? 這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。 ? 釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑 ，首地址為釋放區(qū)首地址 ， 大小為二者大小之和 。 ? 其二是空閑區(qū)大小與 SIZE相等 ， 則修改空閑區(qū)表相應(yīng)表目 ， 向用戶返回該空閑區(qū)首址 ，表示此空閑區(qū)已分給了要求的用戶 。 ? 不同系統(tǒng)根據(jù)設(shè)計(jì)要求采用不同的結(jié)構(gòu) 。 30 2022/8/17 第六章 存儲(chǔ)管理 舉例 ? 某系統(tǒng)的內(nèi)存容量為 256K， 操作系統(tǒng)占用低地址的 20K， 其余空間劃分成 4個(gè)固定大小的分區(qū) 。 或稱虛地址空間 。 如棧的變化 。 ? 實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜 。 12 2022/8/17 第六章 存儲(chǔ)管理 0 3456 . . . . . . LOAD A 200 . . . . . . 0 100 200 300 . . . . . . . . . LOAD A 200 3456 1100 1200 1300 200 VR + 1000 BR 13 2022/8/17 第六章 存儲(chǔ)管理 地址映射的具體過(guò)程 ? 程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址 由系統(tǒng)送入基地址寄存器 BR中。 ? 地址映射的方式： 靜態(tài)地址映射 動(dòng)態(tài)地址映射 7 2022/8/17 第六章 存儲(chǔ)管理 靜態(tài)地址映射 ? 程序被裝入內(nèi)存時(shí)由操作系統(tǒng)的 連接裝入程序 完成程序的邏輯地址到內(nèi)存地址的轉(zhuǎn)換 。1 2022/8/17 第六章 存儲(chǔ)管理 第六章 存儲(chǔ)管理 ? 主存管理的功能 ? 分區(qū)存貯管理 ? 分頁(yè)存儲(chǔ)管理 ? 分段存儲(chǔ)管理 ? 段頁(yè)式存儲(chǔ)管理 ? 覆蓋技術(shù)與交換技術(shù) ? 虛擬存儲(chǔ) 2 2022/8/17 第六章 存儲(chǔ)管理 主存管理的功能 ? 地址映射 ? 主存分配 ? 存儲(chǔ)保護(hù) ? 主存擴(kuò)充 (虛擬內(nèi)存 ) 3 2022/8/17 第六章 存儲(chǔ)管理 地址映射 (地址重定位 ) ? 內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱為 內(nèi)存地址 （或稱為 物理地址 ， 絕對(duì)地址 ）。 8 2022/8/17 第六章 存儲(chǔ)管理 映射方法 ? 假定程序裝入內(nèi)存的首地址為 BR， 程序地址為 VR， 內(nèi)存地址為 MR， 則地址映射按下式進(jìn)行： MR=BR+VR 。 ? 在程序執(zhí)行的過(guò)程中，若要訪問(wèn)內(nèi)存，將訪問(wèn)的邏輯地址送入 VR中。 15 2022/8/17 第六章 存儲(chǔ)管理 主存分配與回收 要完成內(nèi)存的分配和回收工作 ， 要求設(shè)計(jì)者選擇和確定以下幾種策略和結(jié)構(gòu)： ? 調(diào)入策略 ? 放置策略 ? 置換策略 ? 分配結(jié)構(gòu) 16 2022/8/17 第六章 存儲(chǔ)管理 調(diào)入策略 ? 用戶程序在何時(shí)調(diào)入內(nèi)存的策略 。 ? 進(jìn)程映像在內(nèi)存和外存之間傳遞 。 27 2022/8/17 第六章 存儲(chǔ)管理 實(shí)現(xiàn)虛擬內(nèi)存的基本原理 ? 將程序正在使用的部分內(nèi)容放在內(nèi)存 ， 而暫時(shí)不用的部分放在外存 ， 在需要時(shí)由系統(tǒng)調(diào)入內(nèi)存 ， 并將不需要 （ 或暫不需要 ） 的部分調(diào)出內(nèi)存 。 如下圖 31 2022/8/17 第六章 存儲(chǔ)管理 圖示 32 2022/8/17 第六章 存儲(chǔ)管理 分區(qū)說(shuō)明表 分區(qū)號(hào) 大小(KB) 始址 狀態(tài) 1 8 20 已分配 2 32 28 已分配 3 64 60 已分配 4 132 124 未分配 33 2022/8/17 第六章 存儲(chǔ)管理 固定分區(qū)性能分析 ? 在作業(yè)大小和出現(xiàn)頻率均已知的情況下 ， 固定分區(qū)是合適的 。 常用的有 表結(jié)構(gòu)和隊(duì)列結(jié)構(gòu) 。 39 2022/8/17 第六章 存儲(chǔ)管理 ? 其三是空閑區(qū)大于 SIZE， 這時(shí)將空閑區(qū)一分為二 。 ? 釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置。 49 2022/8/17 第六章 存儲(chǔ)管理 最佳適應(yīng)法 ? 要求按 空閑區(qū)大小從小到大 的次序組成空閑區(qū)表（隊(duì)列）。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來(lái)越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。 57 2022/8/17 第六章 存儲(chǔ)管理 三種策略比較 ? 上述三種放置策略各有利弊 ， 到底哪種最好不能一概而論 ， 而應(yīng)針對(duì)具體作業(yè)序列來(lái)分析 。 碎片的出現(xiàn)造成了存儲(chǔ)空間的浪費(fèi) 。 從 0開始編制頁(yè)號(hào) ，頁(yè)內(nèi)地址是相對(duì)于 0編址 65 2022/8/17 第六章 存儲(chǔ)管理 ? 邏輯地址 用戶程序的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。 頁(yè)號(hào) 塊號(hào) 其它 0 5 … 1 65 … 2 13 … 73 2022/8/17 第六章 存儲(chǔ)管理 例 ? 如圖 ， 作業(yè) 1有 2頁(yè)分別裝入內(nèi)存的第 6塊；作業(yè) 2有 3頁(yè)裝入內(nèi)存的第 7塊；作業(yè) 3有 1 頁(yè)裝入內(nèi)存的第 8塊 。 78 2022/8/17 第六章 存儲(chǔ)管理 ? 根據(jù)頁(yè)號(hào) P=2， 硬件自動(dòng)查該進(jìn)程的頁(yè)表 ， 找到第 2頁(yè)對(duì)應(yīng)的塊號(hào)為 7， 將塊號(hào)送到內(nèi)存地址寄存器 MR的高 10位中 。 一 、 在分離程序地址字的頁(yè)號(hào)和頁(yè)內(nèi)地址時(shí)判別訪問(wèn)是否合法 ， 若產(chǎn)生的頁(yè)號(hào)滿足下式為合法： 0=頁(yè)號(hào) 程序地址空間的頁(yè)數(shù) 上述判斷由硬件自動(dòng)做 ， 若不合法 ， 硬件產(chǎn)生 越界中斷 ， 由操作系統(tǒng)的越界中斷處理程序進(jìn)行處理 。 86 2022/8/17 第六章 存儲(chǔ)管理 ? 實(shí)際上我們并不需要一個(gè)很大的快速存儲(chǔ)器 ， 有一個(gè)能存放 16個(gè)頁(yè)表表目的快速存儲(chǔ)器就夠了 。 90 2022/8/17 第六章 存儲(chǔ)管理 二級(jí)頁(yè)表結(jié)構(gòu)及地址映射 頁(yè)目錄地址 目錄位移 頁(yè)表位移 頁(yè)位移 虛擬地址 頁(yè)表地址 .