第5章-虛擬存儲器

第5章虛擬存儲器5.1虛擬存儲器概述

5.2請求分頁存儲管理方式

5.3頁面置換算法

5.4“抖動”與工作集

5.5請求分段存儲管理方式1

虛擬存儲器物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是有限的。物理存儲器管理方式的特征：

一次性：程序要全部一次性裝入內(nèi)存后才能運(yùn)行

駐留性：程序裝入內(nèi)存后，一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)速。用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時候要大得多。如何將大于物理內(nèi)存容量的用戶程序裝入運(yùn)行？這就是提出研究虛擬存儲器的原因，或稱為虛擬存儲技術(shù)發(fā)展的原動力。2程序的局部性原理（p154）

指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。又可細(xì)分時間局部性和空間局部性。時間局限性

一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行?？臻g局限性

若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用。3虛擬存儲器的定義(p155)虛擬存儲器是采用請求調(diào)入功能和置換功能，把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從邏輯上為用戶提供一個比物理主存容量大得多的，可尋址的一種“主存儲器”

，這就是虛存。虛擬存儲器的容量

是有限的；由內(nèi)存容量和外存容量之和所決定，受計算機(jī)的地址結(jié)構(gòu)限制。以CPU時間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。4虛擬存儲器的特征(p155)常規(guī)存儲器的特征一次性駐留性虛擬存儲器特征多次性對換性虛擬性5

虛擬存儲器的實(shí)現(xiàn)實(shí)現(xiàn)虛擬存儲器必須解決好以下有關(guān)問題主存輔存統(tǒng)一管理問題邏輯地址到物理地址的轉(zhuǎn)換問題部分裝入和部分對換問題虛擬存儲管理主要采用以下技術(shù)實(shí)現(xiàn)請求分頁存儲管理請求分段存儲管理6請求分頁存儲管理方式(p157)基本原理在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入部分頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面。當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。

例怎樣才能發(fā)現(xiàn)頁面不在內(nèi)存中呢?怎樣處理這種情況呢?

采用的辦法是：擴(kuò)充頁表的內(nèi)容，增加駐留標(biāo)志位和頁面輔存的地址等信息。通過產(chǎn)生缺頁中斷來處理.7前進(jìn)請求分頁原理圖81/15/2023151413121110987654321060K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁頁框返回

擴(kuò)充頁表(p157)

頁號、內(nèi)存塊號、狀態(tài)位、外存地址、訪問位、修改位 狀態(tài)位（中斷位）：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過9頁號狀態(tài)位輔存地址訪問位修改位物理塊號頁表示例10110011100000011狀態(tài)位缺頁中斷機(jī)構(gòu)(p157)

在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存。此時應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成喚醒）如果內(nèi)存中有空閑塊，則分配一個塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號若此時內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）11缺頁中斷與一般中斷(p158)

缺頁中斷和一般中斷都是中斷。相同點(diǎn)：保護(hù)現(xiàn)場、中斷處理、恢復(fù)現(xiàn)場不同點(diǎn)：一般中斷是一條指令完成后檢查和處理中斷信號，缺頁中斷是一條指令執(zhí)行時產(chǎn)生和處理中斷信號。缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。

12內(nèi)存分配策略內(nèi)存分配策略分為兩種進(jìn)程保持頁框數(shù)固定不變，稱固定分配;進(jìn)程分得的頁框數(shù)可變，稱可變分配。固定分配進(jìn)程創(chuàng)建時，根據(jù)進(jìn)程類型和程序員的要求決定頁框數(shù)，只要有一個缺頁中斷產(chǎn)生，進(jìn)程就會有一頁被替換。即使內(nèi)存中有空閑的物理塊，也不分配給該進(jìn)程。可變分配先為每個進(jìn)程分配一定數(shù)目的物理塊，進(jìn)程執(zhí)行的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進(jìn)程目前局部性較好，可減少分給進(jìn)程的頁框數(shù)。13內(nèi)存分配策略分析固定分配缺少靈活性，而可變分配的性能會更好些，被許多操作系統(tǒng)采用。采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視活動進(jìn)程的行為和進(jìn)程缺頁中斷率的情況，會增加系統(tǒng)的開銷。

14頁面置換策略全局置換如果頁面置換算法的作用范圍是整個系統(tǒng)，稱全局頁面置換算法，它可以在運(yùn)行進(jìn)程間動態(tài)地分配頁框。被置換的頁可以是內(nèi)存中任一進(jìn)程的頁。局部置換如果頁面置換算法的作用范圍局限于本進(jìn)程，稱為局部頁面置換算法，它實(shí)際上需要為每個進(jìn)程分配固定的頁框。始終保持分配給該進(jìn)程的物理塊數(shù)不變。15固定分配和局部置換策略配合使用固定分配局部置換策略進(jìn)程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進(jìn)程的頁面中選頁置換，保證進(jìn)程的頁框總數(shù)不變。策略難點(diǎn)應(yīng)給每個進(jìn)程分配多少頁框?給少了，缺頁中斷率高；給多了，使內(nèi)存中能同時執(zhí)行的進(jìn)程數(shù)減少，進(jìn)而造成處理器和其它設(shè)備空閑。采用固定分配算法，系統(tǒng)把頁框分配給進(jìn)程，采用平均分配按比例分配優(yōu)先權(quán)分配16可變分配和全局置換策略配合使用先每個進(jìn)程分配一定數(shù)目頁框，os保留若干空閑頁框，進(jìn)程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中選一個給進(jìn)程，這樣產(chǎn)生缺頁中斷進(jìn)程的內(nèi)存空間會逐漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。系統(tǒng)擁有的空閑頁框耗盡時，會從內(nèi)存中選擇一頁淘汰，該頁可以是內(nèi)存中任一進(jìn)程的頁面，這樣又會使那個進(jìn)程的頁框數(shù)減少，缺頁中斷率上升。17可變分配和局部替換配合使用

其實(shí)現(xiàn)要點(diǎn)如下:新進(jìn)程裝入主存時，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目頁框。產(chǎn)生缺頁中斷時，從該進(jìn)程駐留集中選一個頁面替換。不時重新評價進(jìn)程的分配，增加或減少分配給進(jìn)程的頁框以改善系統(tǒng)性能。18

調(diào)頁策略(p161)何時頁面裝入主存請求調(diào)頁策略:需要訪問程序和數(shù)據(jù)時，才把所在頁面裝入主存。缺點(diǎn)是每次只調(diào)入一頁，處理缺頁中斷和調(diào)頁的系統(tǒng)開銷較大，增加磁盤I/O啟動頻率。預(yù)調(diào)頁策略:系統(tǒng)預(yù)測進(jìn)程將要使用的頁面，使用前預(yù)先調(diào)入主存，每次調(diào)入若干頁面，而不是僅調(diào)一頁。缺點(diǎn)是如果調(diào)入的一批頁面中多數(shù)未被使用，則效率就很低了，可見預(yù)調(diào)頁要建立在預(yù)測的基礎(chǔ)上。19影響缺頁中斷率的因素(p162)缺頁中斷率假定作業(yè)p共計n頁，系統(tǒng)分配給它的主存塊只有m塊（１≤m≤n）。如果作業(yè)p在運(yùn)行中成功的訪問次數(shù)為s，不成功的訪問次數(shù)為F，則總的訪問次數(shù)Ａ為：

A=S+F

又定義：f=F/A，稱f為缺頁中斷率。影響缺頁中斷率f的因素有：

(1)主存物理塊數(shù)

(2)頁面大小

(3)程序的編制方法

(4)頁面置換算法20缺頁中斷率的因素示例

程序要將128×128的數(shù)組置“0”。分給的主存只一塊，頁面尺寸為每頁128個字，數(shù)組中的元素每行存放在一頁中。若程序如下：

VarA:array[1..128]ofarray[1..128]ofinteger;forj:=1to128dofori:=1to128doA[i][j]:=0

總共產(chǎn)生（128*128－1）次缺頁中斷。如果重新編制程序如下：

VarA:array[1..128]ofarray[1..128]ofinteger;fori:=1to128doforj:=1to128doA[i][j]:=0

總共產(chǎn)生（128－1）次缺頁中斷。21頁面置換算法(p162)

當(dāng)要索取一頁面并送入到全滿的內(nèi)存中時，必須把已在內(nèi)存中的某一頁淘汰掉。用來選擇淘汰哪一頁的規(guī)則叫做置換算法。最佳置換算法（OPT）先進(jìn)先出頁面置換算法（FIFO）最近最久未使用算法（LRU）22最佳置換算法（OPT）(p163)

基本思想：淘汰以后不再需要的或最遠(yuǎn)的將來才會用到的頁面?？捎脕碜鳛楹饬扛鞣N具體算法的標(biāo)準(zhǔn)。

【例】采用固定分配局部置換策略，某程序在內(nèi)存中分配三個塊，訪問頁的走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，計算缺頁次數(shù)和缺頁中斷率，假設(shè)開始時所有頁均不在內(nèi)存。OPT432143543215塊1444444444

211塊233333333333塊32111555555xxxx

x

xx

共缺頁中斷7次缺頁中斷率=7/12=58.33%23先進(jìn)先出頁面置換算法（FIFO）(p163)

基本思想：淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常駐的除外）。

【例】采用固定分配局部置換策略，某程序在內(nèi)存中分配三個塊，訪問頁的走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，計算缺頁次數(shù)，假設(shè)開始時所有頁均不在內(nèi)存。FIFO432143543215塊1444111555555塊233344444222塊32223333311xxxxxxx

xx共缺頁中斷9次，缺頁中斷率=9/12=75%24這種算法實(shí)現(xiàn)簡單，但會淘汰經(jīng)常使用的頁面最近最久未使用算法（LRU）(p164)

基本思想：根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。當(dāng)需要淘汰某一頁時，算法選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。LRU432143543215塊1444111555222塊233344444411塊32223333335xxxxxxx

xxx共缺頁中斷10次缺頁