【正文】 ation, Local Replacement) ? 可變分配全局置換 (Variable Allocation, Global Replacement) ? 可變分配局部置換 (Variable Allocation, Local Replacemen Operating System Page 101 2022/8/16 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 ?請(qǐng)求分頁(yè)中的硬件支持 ?內(nèi)存分配策略和分配算法 ?調(diào)頁(yè)策略 Operating System Page 102 2022/8/16 1. 何時(shí)調(diào)入頁(yè)面 2. 從何處調(diào)入頁(yè)面 3. 頁(yè)面調(diào)入過(guò)程 Operating System Page 103 2022/8/16 調(diào)頁(yè)策略 ?何時(shí)調(diào)入頁(yè)面 ?預(yù)調(diào)頁(yè)策略 ? 采用一種以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問(wèn)的頁(yè)面預(yù)先調(diào)入內(nèi)存，成功率 50% ?請(qǐng)求調(diào)頁(yè)策略 ? 當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便提出請(qǐng)求，由 OS將其所需頁(yè)面調(diào)入內(nèi)存 ? 目前的虛擬存儲(chǔ)中大多采用此種策略 Operating System Page 104 2022/8/16 2. 從何處調(diào)入頁(yè)面 在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分： 通常 ， 由于對(duì)換區(qū)是采用連續(xù)分配方式 ， 而文件是采用離散分配方式 ， 故對(duì)換區(qū)的磁盤 I/O速度比文件區(qū)的高 。 為此，須利用以下兩類支持硬件： 1．移位寄存器： 定時(shí)右移 2．棧： 當(dāng)進(jìn)程訪問(wèn)某頁(yè)時(shí)，將其移出壓入“棧頂”，“棧底”換出。 （ 4）外存地址。 （ 3）修改位 M。 然后 重復(fù)第一步 ，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè) A = 0M = 0A = 0M = 1A = 1M = 0A = 1M = 1NN N換 出Operating System Page 120 2022/8/16 頁(yè)面置換算法 ?影響缺頁(yè)次數(shù)的因素 ? 分配給進(jìn)程的 物理頁(yè)面數(shù) ? 頁(yè)面本身的 大小 ? 程序的 編制方法 ? 頁(yè)面 淘汰算法 Operating System Page 121 2022/8/16 頁(yè)面置換算法 ?性能問(wèn)題 ?顛簸（抖動(dòng)） 在虛存中，頁(yè)面在內(nèi)存與外存之間 頻繁調(diào)度 ，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。 ? 如果頁(yè)面正在使用，它就落在工作集中；如果不再使用，它將不出現(xiàn)在相應(yīng)的工作集中，所以，工作集是程序局部性的近似表示。 ?如果所有工作集之和增加以至于超過(guò)了可用內(nèi)存塊的總數(shù)，則 OS就會(huì)選擇掛起一個(gè)進(jìn)程，把它 的頁(yè)寫出去，將它的內(nèi)存塊分配給其它其它進(jìn)程。 在環(huán)系統(tǒng)中，程序的訪問(wèn)和調(diào)用應(yīng)遵循以下規(guī)則： （ 1）一個(gè)程序可以訪問(wèn)駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)； (內(nèi)環(huán)可訪問(wèn)外環(huán)數(shù)據(jù) ) （ 2）一個(gè)程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。在該機(jī)制中規(guī)定：低編號(hào)的環(huán)具有高優(yōu)先權(quán)， OS核心處于 0環(huán)內(nèi)；某些重要的實(shí)用程序和操作系統(tǒng)服務(wù)，占居中間環(huán)；而一般的應(yīng)用程序，則被安排在外環(huán)上。 Operating System Page 126 2022/8/16 第四章 存儲(chǔ)器管理 ?程序的裝入和鏈接 ?連續(xù)分配方式 ?基本分頁(yè)存儲(chǔ)管理 ?基本分段存儲(chǔ)管理 ?虛擬存儲(chǔ)器的基本概念 ?請(qǐng)求分頁(yè)存儲(chǔ)管理方式 ?頁(yè)面置換算法 ?請(qǐng)求分段存儲(chǔ)管理方式 Operating System Page 127 2022/8/16 請(qǐng)求分段存儲(chǔ)管理方式 ?請(qǐng)求分段中的硬件支持 ?分段的共享與保護(hù) Operating System Page 128 2022/8/16 請(qǐng)求分段中的硬件支持 ?段表機(jī)制 ?存取方式 用于標(biāo)識(shí)本分段存取屬性是只執(zhí)行、只讀還是允許讀 /寫 ?存在位 P 用于指示該段是否已調(diào)入內(nèi)存 ?訪問(wèn)字段 A 用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或記錄本頁(yè)在最近多長(zhǎng)時(shí)間未被訪問(wèn) ?修改位 M 表示該段在調(diào)入內(nèi)存后是否被修改過(guò) ?外存地址 本段在外存上的地址，盤塊塊號(hào) ?增補(bǔ)位 本段在運(yùn)行過(guò)程中是否做過(guò)動(dòng)態(tài)增長(zhǎng) 段名 段長(zhǎng) 段的基址 存取方式 訪問(wèn)字段 A 修改位M 存在位P 增補(bǔ)位 外存始址 Operating System Page 129 2022/8/16 請(qǐng)求分段中的硬件支持 虛段 S 不在內(nèi)存阻塞請(qǐng)求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段 S修改段表及內(nèi)存空區(qū)鏈喚醒請(qǐng)求進(jìn)程返回空區(qū)容量總和能否滿足？空區(qū)拼接，以形成一個(gè)合適的空區(qū)淘汰一個(gè)或幾個(gè)實(shí)段，以形成一個(gè)合適空區(qū)否否是是 請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程 從中可以看出 ， 對(duì)缺段中斷的處理要比對(duì)缺頁(yè)中斷的處理復(fù)雜 ， 因?yàn)槎问遣欢ㄩL(zhǎng)的 。如果 ?太小，那么它不能包含整個(gè)局部；如果 ?為無(wú)窮大，那么工作集合是進(jìn)程執(zhí)行所碰到的所有頁(yè)的集合。如此反復(fù)，使得整個(gè)系統(tǒng)的頁(yè)面替換非常頻繁，使大部分機(jī)器時(shí)間都用在來(lái)回進(jìn)行的頁(yè)面調(diào)度上，這種局面稱為系統(tǒng)顛簸（ thrashing) ?結(jié)果： 缺頁(yè)率急劇增加，內(nèi)存有效存取時(shí)間加長(zhǎng)，系統(tǒng)吞吐量驟減；系統(tǒng)已基本不能完成什么任務(wù)。由于內(nèi)存中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，在置換該頁(yè)時(shí)就不須將該寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外存上，以保證外存中所保留的始終是最新副本 。 Operating System Page 115 2022/8/16 Operating System Page 116 2022/8/16 Operating System Page 117 2022/8/16 2. 改進(jìn)型 Clock置換算法 在將一個(gè)頁(yè)面換出時(shí) ， 如果該頁(yè)已被修改過(guò) ， 便須將它重新寫到磁盤上；但如果該頁(yè)未被修改過(guò) ， 則不必將它拷回磁盤 。 用于指示該頁(yè)是否調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。 文件區(qū) 對(duì)換區(qū) Operating System Page 105 2022/8/16 3. 頁(yè)面調(diào)入過(guò)程 頁(yè)面調(diào)入 頁(yè)面在內(nèi)存 頁(yè)面未在內(nèi)存 內(nèi)存能容納新頁(yè) 內(nèi)存已滿 該頁(yè)未被修改過(guò) 該頁(yè)已被修改 缺頁(yè)中斷 置換算法 寫回磁盤 Operating System Page 106 2022/8/16 第四章 存儲(chǔ)器管理 ?程序的裝入和鏈接 ?連續(xù)分配方式 ?基本分頁(yè)存儲(chǔ)管理 ?基本分段存儲(chǔ)管理 ?虛擬存儲(chǔ)器的基本概念 ?請(qǐng)求分頁(yè)存儲(chǔ)管理方式 ?頁(yè)面置換算法 ?請(qǐng)求分段存儲(chǔ)管理方式 Operating System Page 107 2022/8/16 頁(yè)面置換算法 ?最佳置換算法和先進(jìn)先出置換算法 ?最近最久未使用（ LRU）置換算法 ?CLOCK置換算法 ?其它置換算法 Operating System Page 108 2022/8/16 最佳置換算法和先進(jìn)先出置換算法 例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊 ， 并考慮有以下的頁(yè)面號(hào)引用串： 7， 0， 1， 2， 0， 3， 0， 4， 2， 3，0， 3， 2， 1， 2， 0， 1， 7， 0， 1進(jìn)程運(yùn)行時(shí) ， 先將 7， 0，1三個(gè)頁(yè)面裝入內(nèi)存 。 Operating System Page 90 2022/8/16 虛擬存儲(chǔ)器的引入 ?虛擬存儲(chǔ)器 定義 ?是指具有 請(qǐng)求調(diào)入功能 和 置換功能 ， 能從 邏輯上 對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng) 。 第一次訪問(wèn) ，是訪問(wèn)內(nèi)存中的段表。 ? STORE 1,[B]|C。 若給定一個(gè)邏輯地址空間中的地址為 A， 頁(yè)面的大小為 L， 則頁(yè)號(hào) P和頁(yè)內(nèi)地址 d可按下式求得： 例如：其系統(tǒng)的頁(yè)面大小為 1KB， 設(shè) A=2170B， 則由下式可以求得 P= ， d= 。 一般說(shuō)來(lái) ， 沒(méi)有硬件支持 ， 實(shí)現(xiàn)有效的存儲(chǔ)保護(hù)是困難的 。工作集。內(nèi)存保護(hù) ? 2. 交換與覆蓋 ? 3. 連續(xù)分配管理方式 ? 4. 非連續(xù)分配管理方式 ? 分頁(yè)管理方式 。 2022年新大綱 Operating System Page 4 2022/8/16 考查范圍與考查目標(biāo) ? 三、 內(nèi)存管理 ? (二 ) 虛擬內(nèi)存管理 ? 1. 虛擬內(nèi)存基本概念 ? 2. 請(qǐng)求分頁(yè)管理方式 ? 3. 頁(yè)面置換算法 ? 最佳置換算法 (OPT)。根據(jù)回收區(qū)的位置，有四種情況需處理： ? 回收區(qū)與插入點(diǎn)的 前一個(gè) 空閑分區(qū)相鄰接 ? 回收區(qū)與插入點(diǎn)的 后一個(gè) 空閑分區(qū)相鄰接 ? 回收區(qū)同時(shí)與插入點(diǎn)的 前、后 兩個(gè)分區(qū)相鄰接 ? 回收區(qū)不與任何空閑區(qū)鄰接 Operating System Page 25 2022/8/16 動(dòng)態(tài)分區(qū)分配 空閑區(qū) 回收區(qū) 回收區(qū) 空閑區(qū) 空閑區(qū) 回收區(qū) 空閑區(qū) 回收區(qū) 情況 1 情況 2 情況 3 情況 4 Operating System Page 26 2022/8/16 2) 回收內(nèi)存 回收區(qū) F1 F2 回收區(qū) F2 回收區(qū) F1 回收區(qū) 回收區(qū) Operating System Page 27 2022/8/16 動(dòng)態(tài)分區(qū)分配 ?碎片問(wèn)題 ?經(jīng)過(guò)一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。如果一個(gè)進(jìn)程對(duì)共享區(qū)域的訪問(wèn)違反了權(quán)限規(guī)定，則發(fā)生操作越權(quán) 即讀寫保護(hù) 可重定位分區(qū)分配 Operating System Page 40 2022/8/16 ?保護(hù)鍵方式 可重定位分區(qū)分配 Operating System Page 41 2022/8/16 基本分頁(yè)存儲(chǔ)管理方式 連續(xù)分配方式會(huì)形成許多“碎片”，通過(guò)“緊湊”方法將碎片拼接成可用的大塊空間，但須為此付出很大開銷。 161。 段則是信息的邏輯單位 ， 它含有一組其意義相對(duì)完整的信息 。 由于它的基本原理與分頁(yè)及分段時(shí)的情況相似，故在此不再詳述。其所表現(xiàn)出來(lái)的最重要的特征是虛擬性。即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè)。 （ 3）修改位 M。 用于指示該頁(yè)是否調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。 Operating System Page 119 2022/8/16 CLOCK置換算法 ? ? (1) 從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊(duì)列， 尋找 A=0且 M=0的第一類頁(yè)面， 將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。 Operating System Page 123 2022/8/16 系統(tǒng)顛簸（抖動(dòng)） Thrashing ?防止系統(tǒng)顛簸 (抖動(dòng) )方法： ?采用局部置換策略： 如果一個(gè)進(jìn)程出現(xiàn)抖動(dòng)，它不能從另外的進(jìn)程取幀、不會(huì)引發(fā)其它進(jìn)程出現(xiàn)抖動(dòng)，使抖動(dòng)局限于一個(gè)小范圍內(nèi)。 ?利用工作集模型可以防止抖動(dòng)。 在環(huán)系統(tǒng)中，程序的訪問(wèn)和調(diào)用應(yīng)遵循以下規(guī)則： （ 1）一個(gè)程序可以訪問(wèn)駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)； （ 2）一個(gè)程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的