1/116存儲管理5請求頁式管理請求段式管理2-經(jīng)管營銷

操作系統(tǒng)課件ppt

第四章存儲器管理4.6虛擬存儲器4.7懇求分頁存儲管理方式4.8頁面置換算法4.9懇求分段存儲管理

操作系統(tǒng)課件ppt

復(fù)習(xí)程序的局部性規(guī)律，程序往往會不均勻地高度局部化地訪問內(nèi)存。這種特性使得程序的執(zhí)行在一段時(shí)間內(nèi)被限制在作業(yè)的某一局部范圍。(1)時(shí)間局限性:最近被訪問的存儲位置，很可能不久的將來還要被訪問。(2)空間局限性:存儲訪問有集成一組的傾向，以致一旦某個(gè)位置被訪問到，很有可能它四周的位置也要被訪問。2

虛擬存儲器的引入

操作系統(tǒng)課件ppt

虛擬存儲器的定義？所謂虛擬存儲器是指具有懇求調(diào)入功能和置換功能，能從規(guī)律上對內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲器系統(tǒng)。虛擬存儲器的大小受計(jì)算機(jī)系統(tǒng)地址結(jié)構(gòu)和可用外存數(shù)量的限制，與實(shí)際內(nèi)存單元的數(shù)量無關(guān)。3

操作系統(tǒng)課件ppt

頁式虛擬存儲系統(tǒng)分頁系統(tǒng)的基礎(chǔ)上，增加了懇求調(diào)頁功能、頁面置換功能所形成的分頁懇求系統(tǒng)。

懇求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加了懇求調(diào)段及分段置換功能后，所形成的段式虛擬存儲系統(tǒng)。4

操作系統(tǒng)課件ppt

4.7懇求分頁存儲管理方式懇求分頁存儲管理方式是建立在純分頁基礎(chǔ)上的.其基本思想是？

在進(jìn)程開頭運(yùn)行之前，不是裝入全部頁面，而是裝入一個(gè)或零個(gè)頁面，之后依據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則依據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面5

操作系統(tǒng)課件ppt

4.7.1懇求分頁中的硬件支持一、頁表機(jī)制的改進(jìn)頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址

(1)狀態(tài)位(駐留位)P:該頁是在內(nèi)存還是在外存(2)訪問字段位A:記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù);依據(jù)訪問位來打算淘汰哪頁(由不同的算法打算)(3)修改位M:該頁調(diào)入內(nèi)存后是否在被修改過(4)外存地址:該頁在外存上的地址,通常為外存物理塊號.6

操作系統(tǒng)課件ppt

2、缺頁中斷機(jī)構(gòu)在懇求分頁系統(tǒng)中，當(dāng)要訪問的頁面不在內(nèi)存時(shí)，硬件發(fā)一個(gè)缺頁中斷，轉(zhuǎn)交OS處理。3、地址變換機(jī)構(gòu)懇求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是以分頁系統(tǒng)

的地址變換機(jī)構(gòu)為基礎(chǔ)的，還增加了產(chǎn)生缺頁

中斷、處理缺頁中斷，置換等功能。7

操作系統(tǒng)課件ppt

4.7.2內(nèi)存安排策略和安排算法物理塊的安排策略1)、固定安排局部置換

2)、可變安排全局置換3)、可變安排局部置換

操作系統(tǒng)課件ppt

4.7.3調(diào)頁策略

1、何時(shí)調(diào)入頁面1、預(yù)調(diào)頁策略2、懇求調(diào)頁策略用于首次調(diào)入

操作系統(tǒng)課件ppt

4.8頁面置換算法4.8.1最佳置換算法和先進(jìn)先出算法缺頁中斷率:假定作業(yè)p共計(jì)n頁，而系統(tǒng)安排給它的主存塊只有m塊(m,n均為正整數(shù)，1≤m≤n),即最多只能容納m頁。假如程序p在運(yùn)行中成功的訪問次數(shù)為s,不勝利的訪問次數(shù)為f,那么

,其總的訪問次數(shù)a=s+f,若定義f’=f/a,稱f’為缺頁中斷率。10

操作系統(tǒng)課件ppt

影響缺頁中斷次數(shù)的因素(1)安排給進(jìn)程的物理頁面數(shù)物理頁面數(shù)多，缺頁中斷少，反之，則缺頁中斷多物理頁面數(shù)多，進(jìn)程數(shù)少(影響系統(tǒng)效率),反之，則進(jìn)程數(shù)多(缺頁中斷多)依據(jù)試驗(yàn)分析：對一共有n頁的進(jìn)程來說，只要能分到n/2塊內(nèi)存空間，就可使系統(tǒng)獲得最高效率；(2)頁面本身的大小頁面大，進(jìn)程的頁數(shù)少，一頁的信息就大，缺頁中斷

次數(shù)削減；不同的計(jì)算機(jī)系統(tǒng)，有不同頁面大??；

操作系統(tǒng)課件ppt

(3)程序的編制方法例：程序要把128128的數(shù)組初值置“0”,數(shù)組中每一個(gè)元素為一個(gè)字，假定頁面大小為128個(gè)字，數(shù)組中的每一行元素存放一頁，能供該程序使用的主存塊只有1塊。初始時(shí)第一頁在內(nèi)存；程序編制方法1:程序編制方法2:Forj:=1to128Fori:=1to128Fori:=1to128Forj:=1to128A[i][j]:=0;A[i][j]:=0;按列：缺頁中斷次數(shù)：按行：缺頁中斷次數(shù)128-1128128-1可見：缺頁中斷率與程序的局部化程度親密相關(guān)。盼望編制的12程序能常常集中在幾個(gè)頁面上；

操作系統(tǒng)課件ppt

1,11,21,31,41,51,61,71,81,91,102,13,14,15,16,17,18,19,1

10,1

操作系統(tǒng)課件ppt

(4)頁面淘汰算法

理論的頁面淘汰算法應(yīng)當(dāng)選擇的被淘汰頁面將是以后永不使用的，或在最長(將來)時(shí)間內(nèi)不再被訪問的頁面。(OPT算法)。實(shí)際上，可以用理論的頁面淘汰算法作標(biāo)準(zhǔn)，選擇其它較好的頁面淘汰算法

頁面淘汰算法選擇不合適，會使系統(tǒng)“抖動”14

操作系統(tǒng)課件ppt

抖動剛被換出的頁很快又被訪問，需要重新調(diào)入，為此又需再選出一頁調(diào)出；而剛被換出的頁，很快又要被訪問，又需把它調(diào)入，如此頻繁地更換頁面，以致一個(gè)進(jìn)程在運(yùn)行中，把大部分時(shí)間花費(fèi)在完成頁面的置換工作上，使得調(diào)度頁面

所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多.我們稱該進(jìn)程發(fā)生了“抖動”。15

操作系統(tǒng)課件ppt

1、最佳置換算法(OPT)

最佳置換算法是由Relady在1966年提出的，這種算法選擇的被淘汰頁面，將是永不

使用的，或在最長時(shí)間內(nèi)不再被訪問的頁面?！白罴选笔侵笇τ谌我獾膬?nèi)存固定空間m和程序p,缺頁中斷率最小。它是一個(gè)理論上的算法。16

操作系統(tǒng)課件ppt

假定系統(tǒng)為某進(jìn)程安排了三個(gè)物理塊，并考慮有以下的頁面號引用串。1234567891011121314151617181920217012030423032120117017707011222004133203042302033220112011701701

7

0

采納最佳置換算法，只發(fā)生了6次頁面置換，發(fā)生了9次缺頁中斷。缺頁率=9/2117

操作系統(tǒng)課件ppt

2、先進(jìn)先出頁面置換算法(FIFO)這是最早消失的置換算法，這種算法總是淘汰最先進(jìn)入內(nèi)存的頁面，選擇在

內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。

操作系統(tǒng)課件ppt

采納FIFO算法進(jìn)行頁面置換時(shí)的狀況。12345678910111213141516171819202170120304230321201170177072224440007770033322211100111000333222134567891011-131415-18192021

1

2

一共發(fā)生了12次頁面置換，比最佳置換算法多了1倍。缺頁率15/21=3/4,15次頁面中斷。19

操作系統(tǒng)課件ppt

FIFO是依據(jù)各個(gè)頁面調(diào)入內(nèi)存的時(shí)間來選擇被淘汰頁面，但頁面調(diào)入的先后并不

能反映頁面的使用狀況。FIFO算法只是在按線性挨次訪問地址空間才是抱負(fù)的。未考慮到程序的動態(tài)特性?？赡芤鹛貏e。20

操作系統(tǒng)課件ppt

先進(jìn)先出置換算法的一個(gè)特別現(xiàn)象：對于一些特定的頁面訪問序列，先進(jìn)先出置換算法有隨著分給的頁架數(shù)增加，缺頁頻率也增加的特別現(xiàn)象。頁面訪問序列ABCABCAB九次缺頁A+++頁面訪問序列十次缺頁ABCDABCABA++++DDEACCDEBBCD