計(jì)算機(jī)操作系統(tǒng)（第二版）課件：虛擬存儲(chǔ)系統(tǒng)

一.虛擬存儲(chǔ)器的基本概念

虛擬存儲(chǔ)系統(tǒng)局部性特征？什么是虛擬存儲(chǔ)器？具有請(qǐng)求調(diào)入功能和置換功能，能夠利用外存空間從邏輯上擴(kuò)充內(nèi)存容量的一種存儲(chǔ)器系統(tǒng)。特征多次性置換性虛擬性與前面學(xué)習(xí)過的傳統(tǒng)存儲(chǔ)管理方式比較，虛擬存儲(chǔ)器有哪些不同的特征呢？說說你對(duì)局部性特征的理解？第0頁第1頁第2頁第0頁第1頁第2頁第3頁第4頁第5頁第6頁二.請(qǐng)求分頁存儲(chǔ)管理方式4.6虛擬存儲(chǔ)系統(tǒng)只裝入部分頁面1.擴(kuò)充頁表功能：頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存訪問字段A：記錄本頁在一段時(shí)間內(nèi)被訪問的情況修改位M：該頁在調(diào)入內(nèi)存后是否被修改過外存地址：指示該頁在外存上的地址0：不在內(nèi)存1：在內(nèi)存0：未被修改1：已被修改4.6虛擬存儲(chǔ)系統(tǒng)二.請(qǐng)求分頁存儲(chǔ)管理方式哪個(gè)小組來分析下這些字段的含義？什么時(shí)候會(huì)檢查這些字段的值？案例：Win2000中的頁表項(xiàng)二.請(qǐng)求分頁存儲(chǔ)管理方式2.缺頁中斷處理:所要訪問的頁不在內(nèi)存時(shí)，便引發(fā)一次缺頁中斷

啟動(dòng)要處理的指令給出虛地址

得到頁號(hào)該頁在主存?有空閑塊?

缺頁中斷執(zhí)行完該指令

準(zhǔn)備執(zhí)行下條指令選一頁淘汰

從外存讀入所需的頁

調(diào)整存儲(chǔ)分配表和頁表

重新啟動(dòng)被中斷的指令

調(diào)整存儲(chǔ)分配表和頁表要重寫入?該頁寫入外存YNNY硬件實(shí)現(xiàn)軟件實(shí)現(xiàn)YN二.請(qǐng)求分頁存儲(chǔ)管理方式普通中斷的處理過程是怎樣的？普通中斷與缺頁中斷有什么不同呢?執(zhí)行指令的過程中發(fā)生和處理的需要修改頁表項(xiàng)哪些信息？分析缺頁中斷處理過程？本次課前學(xué)習(xí)中不理解的問題、希望老師重點(diǎn)講解的內(nèi)容有哪些？用彈幕給出1、說明虛擬存儲(chǔ)器的基本概念，分析與常規(guī)存儲(chǔ)管理方式相比較的特點(diǎn)2、分析說明虛擬存儲(chǔ)系統(tǒng)中，頁表的字段設(shè)置及用途3、分析說明缺頁中斷處理過程前期知識(shí)回顧4.3頁式存儲(chǔ)管理方式思考題：某請(qǐng)求分頁系統(tǒng)中，若其指令系統(tǒng)指令長(zhǎng)16位，每個(gè)操作數(shù)的地址碼長(zhǎng)6位，操作碼4位，每個(gè)操作數(shù)16位，則執(zhí)行一條雙操作數(shù)指令，則最多可能發(fā)生幾次缺頁中斷？二.請(qǐng)求分頁存儲(chǔ)管理方式（1）固定分配局部置換（2）可變分配全局置換（3）可變分配局部置換3.內(nèi)存分配與頁面置換策略4.地址映射過程缺頁中斷處理需要修改頁表哪些信息？其實(shí)這里要先訪問快表哪個(gè)小組來分析地址映射過程？若某進(jìn)程訪問內(nèi)存時(shí)產(chǎn)生缺頁，則下列選項(xiàng)中，操作系統(tǒng)可能執(zhí)行的操作有（）置換頁面裝入缺頁處理越界錯(cuò)誤分配內(nèi)存ABCD提交多選題10分5.頁面置換算法選擇淘汰頁面的策略缺頁中斷率假定程序p共有n頁，系統(tǒng)分配m塊，有1≤m≤n；

若程序p在運(yùn)行中：成功的訪問次數(shù)為s，不成功的訪問次數(shù)為f；缺頁中斷率：f′=f/(s+f)f′=f(r，m，p)；

r：置換算法；m：系統(tǒng)分配的塊數(shù)；p：程序特征二.請(qǐng)求分頁存儲(chǔ)管理方式5.頁面置換算法（1）先進(jìn)先出頁面置換算法FIFO（2）最佳置換算法OPT（3）最近最久未使用置換算法LRU（4）最近最少使用置換算法LFU（5）時(shí)鐘置換算法CLOCK（講授）（6）改進(jìn)的CLOCK算法（7）頁緩沖思想二.請(qǐng)求分頁存儲(chǔ)管理方式基本概念、實(shí)現(xiàn)思路、性能優(yōu)缺點(diǎn)總是先淘汰那些最先進(jìn)入系統(tǒng)，即駐留主存時(shí)間最長(zhǎng)的頁。例1：在一個(gè)請(qǐng)求分頁系統(tǒng)中，假定系統(tǒng)分給一個(gè)作業(yè)的物理塊數(shù)為3，剛開始沒有一個(gè)頁面裝入內(nèi)存，并且此作業(yè)的頁面走向?yàn)?，3，2，1，5，2，4，5，3，2，5，2。用FIFO計(jì)算缺頁次數(shù)和缺頁率。缺頁次數(shù)：9，缺頁率：(9/12)*100%=75%特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單與進(jìn)程實(shí)際的運(yùn)行不相適應(yīng)5.頁面置換算法二.請(qǐng)求分頁存儲(chǔ)管理方式基本概念？如何實(shí)現(xiàn)？（1）先進(jìn)先出頁面置換算法（FIFO）性能優(yōu)缺點(diǎn)？例2：在一個(gè)請(qǐng)求分頁系統(tǒng)中，假如一個(gè)作業(yè)的頁面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5,當(dāng)分給該作業(yè)的物理塊數(shù)M分別為3和4時(shí)，請(qǐng)用FIFO計(jì)算缺頁次數(shù)和缺頁率，并比較所得的結(jié)果。5.頁面置換算法（1）先進(jìn)先出頁面置換算法（FIFO）物理塊數(shù)為3：缺頁次數(shù)為9物理塊數(shù)為4：缺頁次數(shù)為10這種異?，F(xiàn)象稱為Belady現(xiàn)象。結(jié)果分別是多少？5.頁面置換算法（2）最佳置換算法（OPT）選擇以后永遠(yuǎn)不會(huì)被訪問的頁面或?qū)碜铋L(zhǎng)時(shí)間內(nèi)不會(huì)被訪問的頁面淘汰出去?；靖拍?？如何實(shí)現(xiàn)？在一個(gè)請(qǐng)求分頁系統(tǒng)中，假定系統(tǒng)分給一個(gè)作業(yè)的物理塊數(shù)為3，剛開始沒有一個(gè)頁面裝入內(nèi)存，并且此作業(yè)的頁面走向?yàn)?，3，2，1，5，2，4，5，3，2，5，2。使用OPT置換算法，則缺頁次數(shù)是（）。5678ABCD提交單選題10分缺頁中斷32532532+532534534+534532+532+13232+32+21252354251232頁面走向OPT算法：缺頁次數(shù)：6，缺頁率：6/12特點(diǎn)：理論上，性能最佳；實(shí)際上，無法實(shí)現(xiàn)；通常用該算法來評(píng)價(jià)其他算法的優(yōu)劣。（3）最近最久未使用置換算法（LRU）選擇在最近一段時(shí)間內(nèi)最長(zhǎng)時(shí)間未被使用（訪問）的頁面淘汰出去。5.頁面置換算法缺頁中斷32253253+253+453452+452152+152+13232+32+21252354251232頁面走向缺頁次數(shù)：7缺頁率：7/12特點(diǎn)：性能較好，但精確實(shí)現(xiàn)較困難（3）最近最久未使用置換算法（LRU）5.頁面置換算法LRU算法的實(shí)現(xiàn)用引用位考察頁面的使用情況；當(dāng)訪問頁面時(shí)，將引用位置1，并記時(shí)；當(dāng)要淘汰一頁時(shí)，選擇時(shí)間最長(zhǎng)的一頁淘汰。硬件方法：采用移位寄存器軟件方法：采用頁號(hào)棧極偶爾的情況下，性能會(huì)很差假設(shè)一個(gè)進(jìn)程順序訪問N+1個(gè)頁面后再循環(huán)地訪問這些頁面，若進(jìn)程分配到的內(nèi)存塊數(shù)為N塊。如：順序訪問1,2,3,4,5,6,7，再循環(huán)訪問它們，進(jìn)程分配到的內(nèi)存塊為6個(gè)塊，缺頁情況如何？如果讓你來設(shè)計(jì)，你會(huì)怎么實(shí)現(xiàn)以便快速找到淘汰頁面？使用頁號(hào)棧實(shí)現(xiàn)LRU算法（3）最近最久未使用置換算法（LRU）5.頁面置換算法缺頁中斷252354251232頁面走向23223123512251425542354235523253+++++++缺頁次數(shù)：7，缺頁率：7/12你能使用鏈表來實(shí)現(xiàn)這個(gè)特殊的棧結(jié)構(gòu)嗎？本次課前學(xué)習(xí)中不理解的問題、希望老師重點(diǎn)講解的內(nèi)容有哪些？用彈幕給出1、分析說明最佳頁面置換算法的基本概念、性能特點(diǎn)？2、分析說明LRU頁面置換算法的基本概念、性能特點(diǎn)？如何實(shí)現(xiàn)LRU算法？前期知識(shí)回顧4.6虛擬存儲(chǔ)系統(tǒng)選擇過去一段時(shí)間里訪問次數(shù)最少的頁面進(jìn)行淘汰。

思考：如何實(shí)現(xiàn)該算法？（5）最近最少使用置換算法（LFU）5.頁面置換算法

①簡(jiǎn)單的clock置換算法：每頁設(shè)置一位訪問位。當(dāng)某頁被訪問了，則訪問位置“1”。內(nèi)存中的所有頁鏈接成一個(gè)循環(huán)隊(duì)列；再設(shè)置一個(gè)起始查詢指針置換算法：循環(huán)檢查各頁面的使用情況:若訪問位為“0”，選擇該頁淘汰；若訪問位為“1”，復(fù)位訪問位為“0”；查詢指針前進(jìn)一步。又稱為“最近未使用”置換算法（NRU）（4）Clock置換算法（引導(dǎo)講授）5.頁面置換算法CLOCK算法流程描述：

入口檢查查詢指針指向的頁面移動(dòng)指針指向下一個(gè)頁面

訪問位為0?選擇該頁淘汰，記錄該頁的頁號(hào)、塊號(hào)移動(dòng)查詢指針指向下一個(gè)頁面返回置訪問位為0YN很關(guān)鍵簡(jiǎn)單的clock置換算法：1210訪問位頁號(hào)塊號(hào)1311101216131514115150121603041730202181040000000案例：Linux的雙表針clock置換算法12101311101216131514115150121603040731202181040000例：在一個(gè)請(qǐng)求分頁系統(tǒng)中，假定系統(tǒng)分給一個(gè)作業(yè)的物理塊數(shù)為3，剛開始沒有一個(gè)頁面裝入內(nèi)存，并且此作業(yè)的頁面走向?yàn)?，3，2，1，5，2，4，5，3，2，5，2。采用Clock置換算法，則缺頁次數(shù)是（）。6789ABCD提交單選題10分②改進(jìn)型Clock置換算法：考慮置換代價(jià)訪問位A、修改位M，共同表示一個(gè)頁面的狀態(tài)頁面的四種狀態(tài)：

00：(A=0;M=0)最近未被訪問也未被修改

01：(A=0;M=1)最近未被訪問但已被修改

10：(A=1;M=0)最近已被訪問但未被修改

11：(A=1;M=1)最近已被訪問且被修改（4）Clock置換算法5.頁面置換算法當(dāng)用A、M兩位來表示頁面狀態(tài)時(shí)，內(nèi)存中的頁面可以分為幾種狀態(tài)的頁面？②改進(jìn)型Clock置換算法：三輪掃描：第一輪：查找A=0,M=0頁面，未找到，下一步；第二輪：查找A=0,M=1頁面，A位復(fù)位為“0”，未找到，下一步；第三輪：把所有A置為“0”，重復(fù)第一輪，必要時(shí)再重復(fù)第二輪。（4）Clock置換算法5.頁面置換算法哪個(gè)小組來說說如何查找淘汰頁面？5.頁面置換算法可變分配局部置換策略，F(xiàn)IFO頁面置換算法給淘汰頁面再一次駐留內(nèi)存的機(jī)會(huì)空閑頁面鏈表：已修改頁面鏈表：空閑內(nèi)存塊空白內(nèi)存塊或未修改淘汰頁所在內(nèi)存塊已修改淘汰頁所在內(nèi)存塊淘汰頁未被修改已被修改（6）頁面緩沖置換算法本次課前學(xué)習(xí)中不理解的問題、希望老師重點(diǎn)講解的內(nèi)容有哪些？用彈幕給出1、分析說明最佳頁面置換算法的基本概念、性能特點(diǎn)？2、分析說明LRU頁面置換算法的基本概念、性能特點(diǎn)？如何實(shí)現(xiàn)LRU算法？3、分析說明clock頁面置換算法查找淘汰頁面的過程？4、分析說明頁面緩沖置換算法的基本思想？前期知識(shí)回顧4.6虛擬存儲(chǔ)系統(tǒng)案例：Windows2000空閑塊鏈表（1）零初始化鏈表；（2）空閑鏈表；（3）后備鏈表：未修改淘汰頁；（4）修改鏈表：已修改淘汰頁修改頁面寫回器零頁線程

在某請(qǐng)求分頁管理系統(tǒng)中，一個(gè)作業(yè)共5頁，作業(yè)執(zhí)行時(shí)依次訪問如下頁面：1，4，3，1，2，5，1，4，2，1，4，5，若分配給該作業(yè)的主存塊數(shù)為4，剛開始沒有一個(gè)頁面在內(nèi)存，若分別采用LRU和Clock頁面置換算法，則缺頁中斷次數(shù)分別是（）。6，76，87，77，8ABCD提交單選題10分（1）缺頁率對(duì)有效訪問時(shí)間的影響：設(shè)缺頁率為P，則有效訪問時(shí)間為：=(1-P)*內(nèi)存訪問時(shí)間+P*缺頁中斷處理時(shí)間缺頁中斷處理時(shí)間保存和恢復(fù)現(xiàn)場(chǎng)信息所需時(shí)間讀入缺頁所需時(shí)間（可能置換）更新頁表和快表所需時(shí)間重新執(zhí)行訪存指令時(shí)間。6.請(qǐng)求分頁存儲(chǔ)管理的性能分析二.請(qǐng)求分頁存儲(chǔ)管理方式如果不缺頁，那么訪問一次內(nèi)存包含哪些時(shí)間？如果缺頁，訪問時(shí)間又包含哪些？例：（2009年統(tǒng)考真題）某請(qǐng)求分頁管理系統(tǒng)中，頁面大小為4KB，一次內(nèi)存的訪問時(shí)間為100納秒（ns），一次快表（TLB）的訪問時(shí)間是10ns，處理一次缺頁的平均時(shí)間為100毫秒（已含更新TLB和頁表的時(shí)間），進(jìn)程的駐留集大小固定為2個(gè)頁框，采用FIFO法置換頁面。假設(shè)1）TLB初始為空；2）地址轉(zhuǎn)換時(shí)，先訪問TLB，若TLB未命中時(shí)再訪問頁表（忽略TLB更新時(shí)間）；3）有效位為0表示頁面不在內(nèi)存中。請(qǐng)問：（1）該系統(tǒng)中，一次訪存的時(shí)間下限和上限各是多少？給出計(jì)算過程。（2）假設(shè)快表命中時(shí)一定不缺頁，若快表命中率為90%，缺頁率為10%，則一次內(nèi)存訪問的有效時(shí)間是多少？6.請(qǐng)求分頁存儲(chǔ)管理的性能分析（1）缺頁率對(duì)有效訪問時(shí)間的影響：大家計(jì)算一下，用彈幕給出答案解答：

（1）訪存的下限就是訪存的最短時(shí)間=一次快表（命中）+一次內(nèi)存訪問（數(shù)據(jù)）=10ns+100ns=110ns訪存的上限就是訪存的最長(zhǎng)時(shí)間=一次快表（不命中）+一次訪存（頁表）+一次缺頁+一次快表（命中）+一次訪存（數(shù)據(jù)）=10ns+100ns+100ms+10ns+100ns=100000.22us（2）快表未命中，但不缺頁時(shí)的內(nèi)存訪問是：210ns有效訪問時(shí)間：=90%*110ns+10%（210ns*90%+100000.22us*10%）6.請(qǐng)求分頁存儲(chǔ)管理的性能分析（1）缺頁率對(duì)有效訪問時(shí)間的影響：（2）抖動(dòng)（顛簸）的基本概念：在主存和輔存之間頻繁的頁面置換現(xiàn)像

原因：全局置換策略；置換算法選擇不當(dāng)抖動(dòng)的預(yù)防：①采取局部置換策略；②引入工作集概念：進(jìn)程在某段時(shí)間段Δ里實(shí)際要訪問的頁面集合Δ稱為工作集“窗口尺寸”（WindowsSize）。③掛起若干進(jìn)程，降低多道程序度。6.請(qǐng)求分頁存儲(chǔ)管理的性能分析二.請(qǐng)求分頁存儲(chǔ)管理方式哪個(gè)小組來分析下有哪些預(yù)防辦法？32.針對(duì)某虛擬存儲(chǔ)系統(tǒng)，進(jìn)行了CPU利用率和頁面交換磁盤的利用率的檢測(cè)，發(fā)現(xiàn)有四種情況：（1）CPU利用率低，磁盤利用率高；（2）CPU利用率高，磁盤利用率低；（3）CPU利用率低，磁盤利用率低；（4）CPU利用率高，磁盤利用率高。

請(qǐng)你分析一下，分析上述4種不同情況，回答：

（1）系統(tǒng)可能發(fā)生了什么事情？

（2）當(dāng)CPU利用率低的時(shí)候，如果增加進(jìn)程并發(fā)數(shù)能提高CPU利用率嗎？

（3）虛擬存儲(chǔ)器是否起到作用了？課堂練習(xí)：教材P209：32題哪個(gè)小組來分析一下？小組討論：8分鐘在虛擬分頁系統(tǒng)中，對(duì)系統(tǒng)性能影響較大的因素主要有兩點(diǎn)：頁面調(diào)入策略和頁面置換算法。頁面調(diào)入策略主要考慮兩方面的事情：一是什么時(shí)候調(diào)入頁面，二是從哪里調(diào)入頁面。請(qǐng)你設(shè)計(jì)一種頁面調(diào)入策略，