【正文】 盾 ? 覆蓋技術(shù)主要用在早期的操作系統(tǒng)中 ? 交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn) 113 2022/8/17 第六章 存儲(chǔ)管理 ? 交換技術(shù)與覆蓋技術(shù)共同點(diǎn)： 進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換 ? 不同點(diǎn)：如何控制交換？ 114 2022/8/17 第六章 存儲(chǔ)管理 覆蓋技術(shù) ? 把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域 ? 程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存“擴(kuò)大”了） ? 覆蓋：一個(gè)作業(yè)的若干程序段，或幾個(gè)作業(yè)的某些部分共享某一個(gè)存儲(chǔ)空間 ? 一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動(dòng)覆蓋 115 2022/8/17 第六章 存儲(chǔ)管理 A 8K E 4K F 10K C 10K B 8K D 12K 作業(yè) X的調(diào)用結(jié)構(gòu) 作業(yè) X的常駐區(qū) A（ 8K） 覆蓋區(qū) 0 （ 10K） 覆蓋區(qū) 1 （ 12K） B C D E F 圖示 116 2022/8/17 第六章 存儲(chǔ)管理 缺點(diǎn)： 對(duì)用戶不透明，增加了用戶負(fù)擔(dān) 例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上， MSDOS的啟動(dòng)過(guò)程中，多次使用覆蓋技術(shù)；啟動(dòng)之后，用戶程序區(qū)TPA的高端部分與 塊也是一種覆蓋結(jié)構(gòu) 分析 117 2022/8/17 第六章 存儲(chǔ)管理 交換技術(shù) ? 為什么引入交換技術(shù)？ 當(dāng)內(nèi)存空間緊張時(shí)，系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移到外存，把外存中某些進(jìn)程換進(jìn)內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進(jìn)程在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度 多用于分時(shí)系統(tǒng)中 118 2022/8/17 第六章 存儲(chǔ)管理 交換技術(shù)實(shí)現(xiàn)中的幾個(gè)問(wèn)題 ? 選擇原則 即：將哪個(gè)進(jìn)程換出內(nèi)存？ 例子：分時(shí)系統(tǒng)，時(shí)間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算法，在選擇換出進(jìn)程時(shí)，換出要長(zhǎng)時(shí)間等待的進(jìn)程。 121 2022/8/17 第六章 存儲(chǔ)管理 換入回內(nèi)存時(shí)位置的確定 換出后再換入的內(nèi)存位置一定要在換出前的原來(lái)位置上嗎？ 受地址映射技術(shù)的影響，即絕對(duì)地址產(chǎn)生時(shí)機(jī)的限制 122 2022/8/17 第六章 存儲(chǔ)管理 分析 ? 與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)； ? 交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，準(zhǔn)備將該頁(yè)調(diào)入內(nèi)存 ? 此時(shí)應(yīng)將缺頁(yè)的進(jìn)程掛起（調(diào)頁(yè)完成喚醒） 130 2022/8/17 第六章 存儲(chǔ)管理 ? 如果內(nèi)存中有空閑塊，則分配一個(gè)塊，將要調(diào)入的頁(yè)裝入該塊，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào) ? 若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)（若被淘汰頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫回外存） 131 2022/8/17 第六章 存儲(chǔ)管理 思考 ? 缺頁(yè)中斷同一般中斷的區(qū)別？ 132 2022/8/17 第六章 存儲(chǔ)管理 缺頁(yè)中斷同一般中斷都是中斷，相同點(diǎn)是： ? 保護(hù)現(xiàn)場(chǎng) 中斷處理 恢復(fù)現(xiàn)場(chǎng) 不同點(diǎn)： ? 一般中斷是一條指令完成后中斷，缺頁(yè)中斷是一條指令執(zhí)行時(shí)中斷 ? 一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁(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è)。但系統(tǒng)硬件成本也就越高。 當(dāng)系統(tǒng)要淘汰一節(jié)時(shí) ， 總是從頁(yè)號(hào)棧底取出一個(gè)頁(yè)號(hào)淘汰 ， 即淘汰的頁(yè)是最久未使用的 。在時(shí)間 T內(nèi)，訪問(wèn)過(guò)的頁(yè)其訪問(wèn)位為 1，反之為 0，淘汰為 0 的頁(yè)。太小，訪問(wèn)位為 0的頁(yè)相當(dāng)多，所選的不一定是最久未用的。 138 2022/8/17 第六章 存儲(chǔ)管理 ? 最不經(jīng)常使用（ LFU） 選擇訪問(wèn)次數(shù)最少的頁(yè)面淘汰之 與 LRU的硬件解法類似。在內(nèi)存中為每個(gè)進(jìn)程分配 3塊。 (2) 若每個(gè)進(jìn)程在內(nèi)存有 4塊，又將產(chǎn)生幾次缺頁(yè)。 例 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)生異?，F(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。 內(nèi)存分配一頁(yè)，初始時(shí)矩陣數(shù)據(jù)均不在內(nèi)存； 頁(yè)面大小為 128個(gè)整數(shù)；矩陣 A128X128按行存放。 程序編制方法 2： for i:=1 to 128 for j:=1 to 128 A[i,j]:=0。這種現(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) 如系統(tǒng)有快表，平均命中率為 97%，假設(shè)訪問(wèn)快表的時(shí)間忽略為 0，問(wèn)此時(shí)一次頁(yè)面訪問(wèn)要多長(zhǎng)時(shí)間。 頁(yè)號(hào) 塊號(hào) 0 5 1 3 2 7 3 6 165 2022/8/17 第六章 存儲(chǔ)管理 3 1 6 3 7 2 5 0 塊號(hào) 頁(yè)號(hào) 01000011011 00010 01000011011 00111 頁(yè)表首址 + 0 10 物理地址為： 14875