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

一.虛擬存儲器的基本概念

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

啟動要處理的指令給出虛地址

得到頁號該頁在主存?有空閑塊?

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

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

從外存讀入所需的頁

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

重新啟動被中斷的指令

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

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

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

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

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

入口檢查查詢指針指向的頁面移動指針指向下一個頁面

訪問位為0?選擇該頁淘汰，記錄該頁的頁號、塊號移動查詢指針指向下一個頁面返回置訪問位為0YN很關(guān)鍵簡單的clock置換算法：1210訪問位頁號塊號1311101216131514115150121603041730202181040000000案例：Linux的雙表針clock置換算法12101311101216131514115150121603040731202181040000例：在一個請求分頁系統(tǒng)中，假定系統(tǒng)分給一個作業(yè)的物理塊數(shù)為3，剛開始沒有一個頁面裝入內(nèi)存，并且此作業(yè)的頁面走向為2，3，2，1，5，2，4，5，3，2，5，2。采用Clock置換算法，則缺頁次數(shù)是（）。6789ABCD提交單選題10分②改進(jìn)型Clock置換算法：考慮置換代價訪問位A、修改位M，共同表示一個頁面的狀態(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)時，內(nèi)存中的頁面可以分為幾種狀態(tài)的頁面？②改進(jìn)型Clock置換算法：三輪掃描：第一輪：查找A=0,M=0頁面，未找到，下一步；第二輪：查找A=0,M=1頁面，A位復(fù)位為“0”，未找到，下一步；第三輪：把所有A置為“0”，重復(fù)第一輪，必要時再重復(fù)第二輪。（4）Clock置換算法5.頁面置換算法哪個小組來說說如何查找淘汰頁面？5.頁面置換算法可變分配局部置換策略，F(xiàn)IFO頁面置換算法給淘汰頁面再一次駐留內(nèi)存的機(jī)會空閑頁面鏈表：已修改頁面鏈表：空閑內(nèi)存塊空白內(nèi)存塊或未修改淘汰頁所在內(nèi)存塊已修改淘汰頁所在內(nèi)存塊淘汰頁未被修改已被修改（6）頁面緩沖置換算法本次課前學(xué)習(xí)中不理解的問題、希望老師重點講解的內(nèi)容有哪些？用彈幕給出1、分析說明最佳頁面置換算法的基本概念、性能特點？2、分析說明LRU頁面置換算法的基本概念、性能特點？如何實現(xiàn)LRU算法？3、分析說明clock頁面置換算法查找淘汰頁面的過程？4、分析說明頁面緩沖置換算法的基本思想？前期知識回顧4.6虛擬存儲系統(tǒng)案例：Windows2000空閑塊鏈表（1）零初始化鏈表；（2）空閑鏈表；（3）后備鏈表：未修改淘汰頁；（4）修改鏈表：已修改淘汰頁修改頁面寫回器零頁線程

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

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

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

請你分析一下，分析上述4種不同情況，回答：

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

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

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