第5章虛擬存儲(chǔ)器管理

第五章虛擬存儲(chǔ)器管理5.1虛擬存儲(chǔ)器概述5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.3頁(yè)面置換算法15.1虛擬存儲(chǔ)器概述

一、常規(guī)存儲(chǔ)管理方式的特征和局部性原理

常規(guī)存儲(chǔ)器管理方式的特征我們把前一章中所介紹的各種存儲(chǔ)器管理方式統(tǒng)稱為傳統(tǒng)存儲(chǔ)器管理方式，它們?nèi)季哂腥缦聝蓚€(gè)共同的特征：

(1)一次性

(2)駐留性22.局部性原理在一較短的時(shí)間內(nèi)，程序的執(zhí)行總是集中地訪問(wèn)程序中的某一部分而不是均勻地對(duì)程序所有部分進(jìn)行訪問(wèn)。表現(xiàn)形式空間局部性時(shí)間局部性結(jié)論：作業(yè)運(yùn)行時(shí)其整個(gè)虛擬空間中的信息不必全部調(diào)入主存中，而可以只將其最近要執(zhí)行的部分裝入主存，其余部分到要用到時(shí)再調(diào)入主存，而這時(shí)又可以把暫時(shí)不用的部分調(diào)出主存，這使得虛擬存儲(chǔ)技術(shù)的實(shí)現(xiàn)成為可能。3

3.虛擬存儲(chǔ)的基本思想

系統(tǒng)將主、輔存實(shí)施統(tǒng)一管理，將程序的整個(gè)副本放在輔存，只將程序的一部分裝入主存便開(kāi)始執(zhí)行，在執(zhí)行的過(guò)程中，如果要訪問(wèn)的信息不在主存再通過(guò)換進(jìn)換出使程序繼續(xù)執(zhí)行下去。4二、虛擬存儲(chǔ)器的定義和特征虛擬存儲(chǔ)器的定義指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)主存容量加以擴(kuò)充的一種存儲(chǔ)系統(tǒng)。虛擬存儲(chǔ)器不考慮物理存儲(chǔ)器的大小和信息存放的實(shí)際位置，只規(guī)定每個(gè)進(jìn)程中互相關(guān)聯(lián)的信息的相對(duì)位置。2.虛擬存儲(chǔ)器的特征

(1)多次性——基礎(chǔ)：程序部分裝入

(2)對(duì)換性——關(guān)鍵：換進(jìn)換出

(3)虛擬性——效果：從邏輯上擴(kuò)充了主存前提：邏輯空間與物理空間分離——離散分配53.制約虛擬存儲(chǔ)器容量的條件：每個(gè)程序的虛擬存儲(chǔ)器的最大容量由計(jì)算機(jī)的地址結(jié)構(gòu)確定，受輔助存儲(chǔ)器容量的限制。5.虛擬存儲(chǔ)器的實(shí)現(xiàn)方法請(qǐng)求分頁(yè)存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理請(qǐng)求段頁(yè)式存儲(chǔ)管理4.實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)需要解決的問(wèn)題：程序裝入主存的時(shí)機(jī)——請(qǐng)求調(diào)入、預(yù)調(diào)入存儲(chǔ)的位置選擇淘汰出主存的信息——置換算法65.2請(qǐng)求分頁(yè)存儲(chǔ)管理一、請(qǐng)求分頁(yè)技術(shù)基本思想

當(dāng)一個(gè)用戶(或進(jìn)程)的程序調(diào)入系統(tǒng)運(yùn)行時(shí)，只裝入這個(gè)用戶程序的一部分頁(yè)就啟動(dòng)運(yùn)行。在運(yùn)行的過(guò)程中，若發(fā)現(xiàn)要訪問(wèn)的頁(yè)不在內(nèi)存，就向系統(tǒng)發(fā)出缺頁(yè)中斷請(qǐng)求，系統(tǒng)處理中斷時(shí)，把要求訪問(wèn)的頁(yè)調(diào)入內(nèi)存，然后繼續(xù)運(yùn)行。系統(tǒng)必須解決兩個(gè)問(wèn)題：1、如何檢測(cè)所訪問(wèn)的頁(yè)在不在主存？2、系統(tǒng)如何處理缺頁(yè)中斷調(diào)入缺頁(yè)？7頁(yè)號(hào)塊號(hào)狀態(tài)位P外存始址三、缺頁(yè)中斷處理過(guò)程＝0頁(yè)在主存＝1頁(yè)不在主存狀態(tài)位P對(duì)頁(yè)表進(jìn)行擴(kuò)充，擴(kuò)充后的頁(yè)表結(jié)構(gòu)為：二、擴(kuò)充頁(yè)表當(dāng)缺頁(yè)中斷發(fā)生時(shí)，中斷用戶程序的執(zhí)行，控制轉(zhuǎn)到操作系統(tǒng)的調(diào)頁(yè)程序，由調(diào)頁(yè)程序把所需的頁(yè)面從輔存調(diào)入主存，修改該頁(yè)表面的存在位，然后繼續(xù)執(zhí)行被中斷的程序。8

邏輯地址①

d

P控制寄存器

頁(yè)表始址頁(yè)表長(zhǎng)度

③

操作系統(tǒng)⑤

物理地址

P’

d頁(yè)表②

存在位塊號(hào)頁(yè)號(hào)

P…

1+四、地址轉(zhuǎn)換過(guò)程通常當(dāng)作業(yè)被調(diào)入運(yùn)行時(shí)，將相應(yīng)進(jìn)程的第一頁(yè)裝入主存，所需的其它各頁(yè)，將按要求依次裝入。

④

主存

P’09①將當(dāng)前指令中的邏輯地址分解為頁(yè)號(hào)P和頁(yè)內(nèi)地址d。②根據(jù)頁(yè)號(hào)P查頁(yè)表，判斷該頁(yè)是否在主存（該頁(yè)“存在位”是否為“0”）③若該頁(yè)“存在位”為“1”（該頁(yè)不在主存），則產(chǎn)生缺頁(yè)中斷，否則執(zhí)行步驟⑤。

④操作系統(tǒng)處理缺頁(yè)中斷，將該頁(yè)從磁盤(pán)中調(diào)入主存，并修改頁(yè)表中對(duì)應(yīng)表目的“存在位”信息為“0”，表示該頁(yè)已在主存，然后繼續(xù)執(zhí)行被中斷的指令。⑤將塊號(hào)P’與頁(yè)內(nèi)地址d拼接為物理地址。10啟動(dòng)要處理的指令給出虛地址得到頁(yè)號(hào)該頁(yè)在主存？軟件硬件有空閑塊？調(diào)整存儲(chǔ)分塊表和頁(yè)表重新啟動(dòng)被中斷的指令調(diào)整存儲(chǔ)分塊表和頁(yè)表要重寫(xiě)入？準(zhǔn)備執(zhí)行下條指令執(zhí)行完該指令Y缺頁(yè)中斷N從輔存讀入所需的頁(yè)Y選一頁(yè)淘汰NN該頁(yè)寫(xiě)入外存Y11作業(yè)1地址空間01KB2KB3KB-1作業(yè)3地址空間01KB2KB3KB-1OS主存01KB2KB3KB4KB5KB6KB7KB8KB9KB-1OS盤(pán)區(qū)地址盤(pán)區(qū)地址盤(pán)區(qū)地址01200156…頁(yè)號(hào)輔存地址存在位塊號(hào)作業(yè)1頁(yè)表盤(pán)區(qū)地址盤(pán)區(qū)地址盤(pán)區(qū)地址01200183…作業(yè)3頁(yè)表作業(yè)2地址空間01KB2KB3KB4KB-1movr1,[2120]addr1,[3410]盤(pán)區(qū)地址盤(pán)區(qū)地址盤(pán)區(qū)地址0120014…盤(pán)區(qū)地址3…2作業(yè)2頁(yè)表1movr1,[2120]addr1,[3410]2120分解為：p=2,d=723410分解為：p=3,d=3080712當(dāng)作業(yè)2相應(yīng)進(jìn)程運(yùn)行時(shí)，當(dāng)程序執(zhí)行到“movr1,[2120]”這條指令，虛地址為2120，由分頁(yè)機(jī)構(gòu)得p=2,d=72,查頁(yè)表中該頁(yè)的存在位為1，該頁(yè)不在主存，發(fā)生缺頁(yè)中斷，因此時(shí)主存中有空白區(qū)，故直接調(diào)入，放到第7塊上，修改頁(yè)表后,程序從斷點(diǎn)處繼續(xù)執(zhí)行。當(dāng)執(zhí)行到“addr1,[3410]”這條指令虛地址為3410，由分頁(yè)機(jī)構(gòu)得p=3,需要訪問(wèn)第3頁(yè)，查頁(yè)表中該頁(yè)的存在位為1，該頁(yè)也不在主存，發(fā)生缺頁(yè)中斷。但是,此時(shí)主存中沒(méi)有空白塊，故需要淘汰一個(gè)頁(yè)面信息,選擇淘汰的頁(yè)面需要確定淘汰的原則。13五、請(qǐng)求分頁(yè)中的內(nèi)存分配2.內(nèi)存分配策略1)固定分配局部置換

2)可變分配全局置換

3)可變分配局部置換最小物理塊數(shù)的確定最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。3.物理塊分配算法

1)平均分配算法

2)按比例分配算法3)考慮優(yōu)先權(quán)的分配算法145.3頁(yè)面置換(淘汰)算法頁(yè)面置換算法性能的優(yōu)劣直接影響到系統(tǒng)的效率，若選用不當(dāng)會(huì)導(dǎo)致剛淘汰出內(nèi)存的頁(yè)面又要再次調(diào)入內(nèi)存，這樣使處理器大部分時(shí)間都用于頁(yè)面調(diào)度上。15一、常用的頁(yè)面置換(淘汰)算法1、最佳置換算法（OPT）基本思想：從主存移出永遠(yuǎn)不再需要的頁(yè)面，若無(wú)這樣的頁(yè)面存在，則應(yīng)選擇最長(zhǎng)時(shí)間不再需要訪問(wèn)的頁(yè)面。這種最佳策略本身不是一種實(shí)際的方法，因?yàn)轫?yè)面訪問(wèn)的未來(lái)順序是不知道的。但是，可將其它的實(shí)用方法與之比較來(lái)評(píng)價(jià)這些方法的優(yōu)劣。所以，這種最佳策略具有理論上的意義。16432143543215443432432143251325++++==缺頁(yè)次數(shù)為:6次缺頁(yè)中斷率:f=6/12=50%432143543215443432431435235215+++====缺頁(yè)次數(shù)為:7次缺頁(yè)中斷率:f=7/12=58%當(dāng)分配的頁(yè)面數(shù)為3時(shí):當(dāng)分配的頁(yè)面數(shù)為4時(shí):17

2、先進(jìn)先出頁(yè)面置換算法（FIFO）基本思想：最先進(jìn)入內(nèi)存的頁(yè)面不再被使用的可能性最大。算法實(shí)現(xiàn)：分配給一個(gè)作業(yè)的存儲(chǔ)塊數(shù)為m，建立一張m個(gè)元素的隊(duì)列表Q(0)，Q(1)，…，Q(M－1)和一個(gè)替換指針，這個(gè)隊(duì)列是按頁(yè)面調(diào)入主存的先后順序排列的，而這個(gè)指針始終指向最早調(diào)入主存的一頁(yè)。頁(yè)號(hào)先進(jìn)先出算法圖例替換指針（指向最老的一頁(yè)）184321435432154434324321532154215431543214321532++++======缺頁(yè)次數(shù)為:10次缺頁(yè)中斷率:f=10/12=83%432143543215443432132142143543523521+++======缺頁(yè)次數(shù)為:9次缺頁(yè)中斷率:f=9/12=75%當(dāng)分配的頁(yè)面數(shù)為3時(shí):當(dāng)分配的頁(yè)面數(shù)為4時(shí):19特點(diǎn)：1）這種算法實(shí)現(xiàn)簡(jiǎn)單，只是在按線性順序訪問(wèn)地址空間時(shí)才是理想的，否則效率不高。特別是遇到循環(huán)執(zhí)行的程序段，往往把頻繁重復(fù)訪問(wèn)的頁(yè)面被周期地選擇為淘汰的對(duì)象。2）存在Belady現(xiàn)象（缺頁(yè)中斷率隨著被分配的頁(yè)架數(shù)的增加反而上升）。產(chǎn)生Belady現(xiàn)象的原因在于該算法根本沒(méi)有考慮程序執(zhí)行的動(dòng)態(tài)特征。203、最近最久未用算法（LRU）基本思想：選擇最近一段時(shí)間內(nèi)最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)過(guò)的頁(yè)淘汰。這種算法認(rèn)為某一頁(yè)被訪問(wèn)過(guò)，它很可能馬上還要被訪問(wèn)，相反若某頁(yè)長(zhǎng)期未被使用，則它可能在最近的將來(lái)一段時(shí)間也不會(huì)被使用。2143214354321544343243214351435243125321++++====缺頁(yè)次數(shù)為:8次缺頁(yè)中斷率:f=8/12=67%432143543215443432132142143543243213215+++=======缺頁(yè)次數(shù)為:10次缺頁(yè)中斷率:f=10/12=83%當(dāng)分配的頁(yè)面數(shù)為3時(shí):當(dāng)分配的頁(yè)面數(shù)為4時(shí):224、最近最少用算法（LFU）基本思想：在需要淘汰某一頁(yè)時(shí)，首先淘汰到當(dāng)前時(shí)間為止，被訪問(wèn)次數(shù)最少的那一頁(yè)。特點(diǎn)：通過(guò)設(shè)置訪問(wèn)計(jì)數(shù)器實(shí)現(xiàn)。這類算法比較普遍地適用于各種類型的程序。但是，實(shí)現(xiàn)起來(lái)比較困難，因?yàn)橐獙?duì)先前的訪問(wèn)歷史時(shí)時(shí)加以記錄和更新。由軟件實(shí)現(xiàn)，系統(tǒng)開(kāi)銷(xiāo)太大；如由硬件執(zhí)行，則會(huì)增加機(jī)器成本。23LRU的近似算法:5、最近不用算法（NRU）基本思想：在需要淘汰某一頁(yè)時(shí)，從那些最近一段時(shí)間內(nèi)未被訪問(wèn)的頁(yè)中任選一頁(yè)淘汰。特點(diǎn)：只要在頁(yè)表中增設(shè)一個(gè)頁(yè)面訪問(wèn)位即可實(shí)現(xiàn)。為了表示淘汰置換狀態(tài)，頁(yè)表的表目還需要擴(kuò)充。頁(yè)號(hào)塊號(hào)存在位外存始址訪問(wèn)位修改位訪問(wèn)位0——該頁(yè)未被訪問(wèn)過(guò)。1——該頁(yè)已被訪問(wèn)過(guò)。修改位0——該頁(yè)未被修改過(guò)。1——該頁(yè)已被修改過(guò)。24

優(yōu)點(diǎn)：算法實(shí)現(xiàn)比較簡(jiǎn)單。缺點(diǎn)：1）將所有存儲(chǔ)塊的訪問(wèn)位置0的周期T的大小選擇不易確定。T太大，所有塊的訪問(wèn)位可能都為1，確定不了哪個(gè)是最近最久末用的頁(yè)；若T太小，訪問(wèn)位為0的塊可能相當(dāng)多，因而所選擇的不一定是最近最久未用的頁(yè)。2）如缺頁(yè)中斷剛巧發(fā)生在系統(tǒng)對(duì)所有引用位重置0之后，則幾乎所有塊的引用位為0，因而也有可能把常用的頁(yè)不適當(dāng)?shù)靥蕴鋈ァ?52.缺頁(yè)中斷率（頁(yè)面失效率）:欲訪問(wèn)的頁(yè)面不在主存稱為缺頁(yè)故障（或頁(yè)面失效）。缺頁(yè)故障的次數(shù)占全部訪問(wèn)頁(yè)數(shù)的百分比即為缺頁(yè)中斷率（頁(yè)面失效率）。f=（缺頁(yè)次數(shù)）/（訪問(wèn)頁(yè)面總數(shù)）×100%二、淘汰算法的性能評(píng)價(jià)1.頁(yè)面走向（頁(yè)地址流）:一個(gè)程序在其運(yùn)行過(guò)程中所訪問(wèn)的頁(yè)號(hào)的序列稱為頁(yè)面走向。3.抖動(dòng)：導(dǎo)致系統(tǒng)效率急劇下降的主輔存之間的頻繁的頁(yè)面置換現(xiàn)象稱為抖動(dòng)（顛簸）。抖動(dòng)現(xiàn)象花費(fèi)了系統(tǒng)的大量開(kāi)銷(xiāo)，但收效甚微。26

1.頁(yè)面的大小頁(yè)面增大，可減少缺頁(yè)中斷的次數(shù)，但頁(yè)內(nèi)的浪費(fèi)增大。

三、影響缺頁(yè)中斷率的因素缺頁(yè)次數(shù)主存容量工作集任何程序在局部性放入主存時(shí)都有一個(gè)臨界值的要求，這個(gè)主存要求的臨界值被稱為工作集

2.分配給作業(yè)的主存容量分配給作業(yè)的頁(yè)面數(shù)增多可減少缺頁(yè)中斷的次數(shù)。27

3.頁(yè)面調(diào)度算法的性能好的調(diào)度算法應(yīng)盡量避免或減少抖動(dòng)現(xiàn)象的出現(xiàn)。例如：如果有一個(gè)程序要把50×50的數(shù)組賦初值形成單位矩陣，每個(gè)主存塊為200個(gè)字節(jié)，每個(gè)數(shù)組元素占2個(gè)字節(jié)，若已分配到2個(gè)主存塊可供使用，數(shù)組中的元素按行編址，其初始狀態(tài)為空，程序編制如下：?jiǎn)枺焊鲿?huì)產(chǎn)生多少次缺頁(yè)中斷？4.用戶程序編制的方法不合適提高程序的局部性程度，可減少缺頁(yè)中斷的次數(shù)分析：整個(gè)數(shù)組所占地址空間為（50×50）×2=5000字節(jié)，分為5000/200=25個(gè)頁(yè)。每個(gè)頁(yè)中有兩行、100個(gè)數(shù)組元素。28（1）

VARA:ARRAY[1..50,1..50]ofinteger;i,j:integer;BEGINFORi:=1to50DOFORj:=1to50DOIFi=jTHENA[i,j]:=1ELSEA[i,j]:=0;END.（2）

VARA:ARRAY[1..50,1..50]ofinteger;i,j:integer;BEGINFORj:=1to50DOFORi:=1to50DOIFi=jTHENA[i,j]:=1ELSEA[i,j]:=0;END.缺頁(yè)中斷的次數(shù)為:25次缺頁(yè)中斷的次數(shù)為:1250次29四、請(qǐng)求式分頁(yè)系統(tǒng)優(yōu)點(diǎn)(1)可提供大容量的多個(gè)虛擬存儲(chǔ)器。作業(yè)的地址空間不再受實(shí)際主存大小的限制。便于大、中、小計(jì)算機(jī)更好地兼容。(2)更有效地利用了主存。作業(yè)中不常使用的頁(yè)不會(huì)長(zhǎng)期駐留在主存，而這次運(yùn)行用不到的信息則不會(huì)裝入主存。這樣，通常有25％或更多一些的作業(yè)地址空間不被裝入主存