主存擴充虛擬內(nèi)存教學(xué)課件

4.5主存擴充(虛擬內(nèi)存)為了使程序員在編程時不受內(nèi)存的結(jié)構(gòu)和容量的限制，系統(tǒng)為用戶構(gòu)造一種存儲器，其結(jié)構(gòu)可能與內(nèi)存結(jié)構(gòu)不同，容量可能遠遠超過內(nèi)存的實際容量。這種面向編程的存儲器稱為虛擬存儲器。由虛存構(gòu)成的存儲空間稱為虛存空間,或稱虛地址空間。2023/7/29第四章存儲管理程序局部性原理時間局部性一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行空間局部性若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元也可能被使用2023/7/29第四章存儲管理實現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，暫時不用的部分放在外存，在需要時由系統(tǒng)調(diào)入內(nèi)存，并將不需要（或暫不需要）的部分調(diào)出內(nèi)存。由操作系統(tǒng)結(jié)合相關(guān)硬件來完成上述工作計算機好象為用戶提供了一個容量遠大于內(nèi)存的存儲器，這個存儲器稱為虛擬存儲器。

2023/7/29第四章存儲管理4.6虛擬頁式存儲管理1、基本思想在進程開始運行之前，不是裝入全部頁面，而是裝入幾個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面2023/7/29第四章存儲管理XXXX7X5XXX340612虛地址空間物理地址空間}虛頁頁框2023/7/29第四章存儲管理2、頁表表項頁號、內(nèi)存塊號、駐留位、外存地址、訪問位、修改位 駐留位：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過頁號中斷位內(nèi)存塊號外存地址訪問位修改位2023/7/29第四章存儲管理151413121110

9

87

654321000000000000000011110000101100000000000001111001000111010011010100010000000000100011000000000100110在/不在內(nèi)存頁表虛地址8196物理地址245802023/7/29第四章存儲管理3、缺頁中斷（PageFault）處理在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準備將該頁調(diào)入內(nèi)存此時應(yīng)將缺頁的進程掛起（調(diào)頁完成再喚醒）2023/7/29第四章存儲管理缺頁中斷與一般中斷都是中斷相同點：保護現(xiàn)場中斷處理恢復(fù)現(xiàn)場不同點：一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時中斷一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。2023/7/29第四章存儲管理4.6.2頁面分配策略和算法為進程分配物理塊要解決三個問題：第一，確定最少物理塊數(shù)；第二，分配的物理塊數(shù)目是否可變；第三，不同的進程所分配的物理塊數(shù)是否相同2023/7/29第四章存儲管理1、最小物理塊數(shù)最少物理塊數(shù)是指能保證進程正常運行所需的最少物理塊數(shù)。若少于此值時，進程將無法運行。進程應(yīng)獲得的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式2023/7/29第四章存儲管理2、頁面分配和置換策略兩種分配策略：固定分配和可變分配。兩種置換策略：全局置換和局部置換。組合后有三種方式:固定分配局部置換可變分配全局置換可變分配局部置換2023/7/29第四章存儲管理固定分配局部置換(1)基于進程的類型或根據(jù)程序員的要求，為每個進程分配一定數(shù)目的內(nèi)存空間，如M個頁框，在整個運行期間都不再改變。(2)發(fā)現(xiàn)缺頁時從該進程在內(nèi)存的M個頁面中選出一頁換出。存在問題：一定數(shù)目的內(nèi)存空間難以確定，太少，會頻繁地出現(xiàn)缺頁中斷；太多，使內(nèi)存中駐留的進程數(shù)目減少。2023/7/29第四章存儲管理可變分配全局置換(1)OS保持一個空閑物理塊隊列，先為每個進程分配一定數(shù)目的物理塊。(2)發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中，取出一物理塊分配給該進程，并將欲調(diào)入的缺頁裝入其中。(3)當空閑物理塊隊列中的物理塊用完時，才從內(nèi)存中選擇一頁調(diào)出，該頁可能是系統(tǒng)中任一進程的頁。是最易于實現(xiàn)的一種策略。2023/7/29第四章存儲管理可變分配局部置換先根據(jù)進程的類型或程序員的要求，為每個進程分配一定數(shù)目的物理塊；發(fā)生缺頁時,只從該進程在內(nèi)存的頁面中選出一頁換出。如果頻繁地發(fā)生缺頁中斷，則再為之分配若干物理塊，直至缺頁率減低到適當程度為止；反之，若缺頁率特別低，則適當減少物理塊。2023/7/29第四章存儲管理3、物理塊分配算法平均分配算法按比例分配算法考慮優(yōu)先權(quán)的分配算法2023/7/29第四章存儲管理平均分配算法將可供分配的物理塊，平均分配給各個進程。這種方式未考慮到各進程本身的大小，表面公平造成實際不公平。2023/7/29第四章存儲管理按比例分配算法根據(jù)進程的大小按比例分配物理塊。n個進程，每個進程的頁面數(shù)是Si,則系統(tǒng)中頁面總數(shù)為：物理塊的總數(shù)為m，進程i所能分到的物理塊數(shù)注意：應(yīng)該取整，且必須大于最小物理塊數(shù)。2023/7/29第四章存儲管理考慮優(yōu)先權(quán)的分配算法為優(yōu)先權(quán)高的分配較多的內(nèi)存空間。通常把內(nèi)存中可供分配的物理塊分成兩部分： 一部分按比例地分配給各進程； 一部分則根據(jù)各進程的優(yōu)先權(quán)應(yīng)適當增加的物理塊數(shù)，分配給各進程。2023/7/29第四章存儲管理4.6.3頁面調(diào)入策略1、何時調(diào)入頁面2、從何處調(diào)入頁面3、頁面調(diào)入過程2023/7/29第四章存儲管理1、何時調(diào)入頁面預(yù)調(diào)頁和請求調(diào)頁（1）預(yù)調(diào)頁策略預(yù)調(diào)頁策略以預(yù)測為基礎(chǔ)，將那些預(yù)計在不久之后便會被訪問的程序或數(shù)據(jù)所在的頁面預(yù)先調(diào)入內(nèi)存，如一次調(diào)入若干個相鄰的頁。但預(yù)測很難準確，所以預(yù)調(diào)頁的成功率僅約一半。這種策略主要用于進程的首次調(diào)入時，由程序員指出應(yīng)該先調(diào)入哪些頁。2023/7/29第四章存儲管理（2）請求調(diào)頁策賂即進程在運行中發(fā)現(xiàn)所要訪問的頁面不在內(nèi)存時，立即提出請求，由系統(tǒng)將其所需頁面調(diào)入內(nèi)存。請求調(diào)頁策略易于實現(xiàn)，在目前的虛擬存儲器中，大多采用此策略。缺點：因為每次請求只調(diào)入一頁，增加了磁盤I／O的啟動頻率，系統(tǒng)開銷大。2023/7/29第四章存儲管理2、從何處調(diào)入頁面請求分頁系統(tǒng)中，外存分為文件區(qū)和對換區(qū)。分三種情況:(1)系統(tǒng)有足夠的對換區(qū)空間，在進程運行前，將與該進程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)，全部從對換區(qū)調(diào)入所需頁面，調(diào)頁速度快。2023/7/29第四章存儲管理(2)系統(tǒng)缺少足夠的對換區(qū)空間 不會被修改的文件，直接從文件區(qū)調(diào)入，換出時不寫回，再調(diào)入時仍從文件區(qū)直接調(diào)入； 對可能被修改的部分，換出時換到對換區(qū)，再調(diào)入時從對換區(qū)調(diào)入。(3)UNIX方式 未運行過的頁面，都從文件區(qū)調(diào)入;

曾經(jīng)運行過而又被換出的頁面被放在對換區(qū)，再次調(diào)入時從對換區(qū)調(diào)入。 允許頁面共享，某進程請求的頁面有可能已被其它進程調(diào)入內(nèi)存，不用再從對換區(qū)調(diào)入2023/7/29第四章存儲管理3、頁面調(diào)入過程程序所要訪問的頁面未在內(nèi)存時，向CPU發(fā)出缺頁中斷，由中斷處理程序首先保留CPU環(huán)境，分析中斷原因，轉(zhuǎn)入缺頁中斷處理程序。2023/7/29第四章存儲管理4.7頁面淘汰算法理想淘汰算法—最佳頁面算法（OPT）最近最久未使用頁面淘汰算法（LRU）先進先出頁面淘汰算法（FIFO）2023/7/29第四章存儲管理1、最佳置換算法最佳置換算法是一種理想化的理論算法，具有最好的性能，但在實際上卻難于實現(xiàn)。它選擇永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面作為淘汰頁面。但這是無法預(yù)知的，因而該算法無法實現(xiàn)。它在固定分配頁面方式中可保證獲得最低的缺頁率。主要用于評價其他算法

2023/7/29第四章存儲管理2、先進先出頁面置換算法該算法總是淘汰最先調(diào)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)時把一個進程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個隊列，并設(shè)置一個替換指針，指向最老頁面。實現(xiàn)簡單、性能差2023/7/29第四章存儲管理3最近最久未使用（LRU）選擇最后一次訪問時間距離當前時間最長的一頁并淘汰之即淘汰最長時間沒有使用的頁性能較好，實現(xiàn)代價很高軟件方法或硬件方法2023/7/29第四章存儲管理LRU的硬件實現(xiàn)：系統(tǒng)為每頁設(shè)置一個寄存器R，每當訪問這一頁時，將該頁對應(yīng)的寄存器R高位置1，以后每個時間間隔將所有的R右移一位，R值越小，對應(yīng)的頁未被使用的時間越長。當淘汰一頁時就選擇R值最小的頁。所以淘汰的是最久未使用的頁。R的位數(shù)越多越精確，但系統(tǒng)硬件成本也就越高。2023/7/29第四章存儲管理LRU軟件實現(xiàn)：設(shè)置一個頁號棧，當一個頁面被訪問時，就立即將它的頁號壓入頁號棧，并檢查頁號棧中是否有與剛壓入棧頂?shù)南嗤捻撎?，若有，則從頁號棧中抽出原有的，以保證頁號棧中無相同的頁號。當系統(tǒng)要淘汰一頁時，總是從頁號棧底取出一個頁號淘汰，即淘汰的頁是最久未使用的。2023/7/29第四章存儲管理LRU軟件實現(xiàn)：2023/7/29第四章存儲管理某程序在內(nèi)存中分配三個塊，訪問頁的順序為4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、

LRU、OPT算法分別計算缺頁次數(shù)假設(shè)開始時所有頁均不在內(nèi)存例12023/7/29第四章存儲管理FIFO432143543215432143555211432143335224321444355

xxxxxxx

xx共缺頁中斷9次FIFO2023/7/29第四章存儲管理訪問順序432143543215432143543215432143543214321435432

xxxxxxx

xxx共缺頁中斷10次

LRU2023/7/29第四章存儲管理

OPT432143543215432111555211433333335554444444444

xxxx

x

xx

共缺頁中斷7次OPT2023/7/29第四章存儲管理練習(xí)某程序在內(nèi)存中分配四個塊，訪問頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分別計算缺頁次數(shù)假設(shè)開始時所有頁均不在內(nèi)存2023/7/29第四章存儲管理LRU432143543215頁1432143543215頁243214354321頁34321435432頁4432111543

xxxxx

xxx共缺頁中斷8次2023/7/29第四章存儲管理OPT432143543215頁1432111555511頁243222222255頁34333333333頁4444444444

xxxxx

x共缺頁中斷6次2023/7/29第四章存儲管理LRU近似算法：Clock算法在頁表中增加一訪問位，每當訪問一頁時，將該頁的訪問位由硬件置1，軟件周期（T）性地將所有訪問位置0。在時間T內(nèi)，訪問過的頁訪問位為1，反之為0，淘汰為0的頁。缺點：T難定。太小，訪問位為0的頁相當多，所選的不一定是最久未用的。太大，所有頁的引用位可能都為1，找不到合適的淘汰頁。

2023/7/29第四章存儲管理2023/7/29第四章存儲管理改進型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：1類(A=0,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。2023/7/29第四章存儲管理最不經(jīng)常使用（LFU）選擇訪問次數(shù)最少的頁面淘汰之與LRU的硬件解法類似。

2023/7/29第四章存儲管理頁面緩沖算法(PBA:PageBufferingAlgorithm)頁面緩沖算法中，被淘汰的頁存放在兩個鏈表（隊列）： 頁面未修改的淘汰頁空閑頁鏈表（實質(zhì)：空閑物理塊鏈表） 頁面已修改的淘汰頁已修改頁面鏈表。2023/7/29第四章存儲管理當需要讀入一個頁面時，便利用空閑物理塊鏈表中的第一個物理塊來裝入。當有一個未被修改的頁要換出時，并不將它換出內(nèi)存，而是直接把它所在的物理塊掛在空閑頁鏈表的末尾。換出一個已修改的頁面時，則將其所在的物理塊掛在修改頁面鏈表的末尾。注：換出頁面時，頁面在內(nèi)存并不做物理上的移動，只是將頁表中的表項移到上述兩個鏈表之一中。2023/7/29第四章存儲管理優(yōu)點：可使已被修改的頁面和未被修改的頁面，都仍留在內(nèi)存中。當進程以后再次訪問這些頁面時，就有可能只須花費較小的開銷。

只有當被修改頁面達到一定數(shù)量，例如64個頁面時，再將它們一起寫回到磁盤，從而顯著地減少了磁盤I／O的操作次數(shù)。2023/7/29第四章存儲管理(1)分配給進程的物理塊數(shù)(2)頁本身的大小(3)程序的編制方法(練習(xí)）(4)頁淘汰算法影響缺頁次數(shù)的因素2023/7/29第四章存儲管理思考：分配給進程的物理塊數(shù)增加缺頁次數(shù)一定能夠減少？例2有一虛擬存儲系統(tǒng)，采用先進先出的頁面淘汰算法。在內(nèi)存中為每個進程分配3塊。進程執(zhí)行時使用頁號的順序為432143543215(1) 該進程運行時總共出現(xiàn)幾次缺頁。(2) 若每個進程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3) 如何解釋所出現(xiàn)的現(xiàn)象。

2023/7/29第四章存儲管理FIFO432143543215頁1432143555211頁243214333522頁34

3

2

1444

355

xxxxxxx

xx共缺頁中斷9次m=32023/7/29第四章存儲管理FIFO432143543215頁1432111543215頁243222154321頁34333215432頁4444

3

2

1543

xxxxxx

xxxx共缺頁中斷10次m=42023/7/29第四章存儲管理m=3時，缺頁中斷9次，缺頁率9/12=75%m=4時，缺頁中斷10次，缺頁率10/12=83%FIFO頁面淘汰算法會產(chǎn)生異?，F(xiàn)象（稱為Belady現(xiàn)象），即：當分配給進程的物理頁面數(shù)增加時，缺頁次數(shù)反而增加2023/7/29第四章存儲管理練習(xí)：程序?qū)θ表摰挠绊懗绦蚓幹品椒?：forj:=1to128fori:=1to128A[i,j]:=0;程序編制方法2：fori:=1to128forj:=1to128A[i,j]:=0;內(nèi)存分配一頁，初始時矩陣數(shù)據(jù)均不在內(nèi)存；頁面大小為128個整數(shù)；矩陣A128X128按行存放。這兩個程序執(zhí)行時分別會產(chǎn)生多少次缺頁中斷？2023/7/29第四章存儲管理解程序編制方法1：forj:=1to128fori:=1to128A[i,j]:=0;程序編制方法2：fori:=1to128forj:=1to128A[i,j]:=0;128*1281282023/7/29第四章存儲管理

在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動原因：頁面淘汰算法不合理分配給進程的物理頁面數(shù)太少顛簸（抖動）2023/7/29第四章存儲管理解決基本思想：根據(jù)程序局部性原理，一般進程在一段時間內(nèi)總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個進程的物理頁面數(shù)太少了，使該進程所需的活躍頁面不能全部裝入內(nèi)存，則進程在運行過程中將頻繁發(fā)生中斷如果能為進程提供與活躍頁面數(shù)相等的物理頁面數(shù)，則可減少缺頁中斷次數(shù)對于給定的訪問序列選取定長的區(qū)間，稱為工作集窗口，落在工作集窗口中的頁面集合稱為工作集2023/7/29第四章存儲管理例如工作集某段時間內(nèi)進程使用過的頁面的集合。N=105554777511623415341555343433312323444控制缺頁率范圍Ws(t1)=1,4,5,7}t1Ws(t1)={3,4,5}t22023/7/29第四章存儲管理1、基本機制2、分段共享3、分段保護

4.8虛擬段式存儲管理2023/7/29第四章存儲管理1、段表內(nèi)容

增加：存取方式：標識段的存取屬性是只執(zhí)行、只讀或允許讀／寫。訪問字段A：記錄該段被訪問的頻繁程度。修改位M：表示該段進入內(nèi)存后，是否已被修改過。存在位：指示是否已調(diào)入內(nèi)存。增補位：指示本段在運行過程中，是否進行過動態(tài)增長。外存始址：指示本段在外存中的起始地址，即起始盤塊號?；緳C制2023/7/29第四章存儲管理2、缺段中斷處理檢查內(nèi)存中是否有足夠的空閑空間①若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回②若沒有，內(nèi)存中空閑區(qū)的總和是否滿足要求？是，采用緊縮技術(shù)，轉(zhuǎn)①；否，淘汰一（些）段，轉(zhuǎn)①

P139圖4-313、地址變換

P140圖4-32基本機制2023/7/29第四章存儲管理2023/7/29第四章存儲管理2、分段共享與保護共享段表：在系統(tǒng)中配置一張共享段表，所有共享段都在共享段表中占有一表項，表項中記錄了共享段的段號和段長、內(nèi)存始址、存在位等信息，并記錄了共享此分段的每個進程的情況。

P140圖4-332023/7/29第四章存儲管理（1）共享進程計數(shù)count整型變量，記錄共享該分段的進程數(shù)。共享段只有當所有共享該段的進程全都不再需要它時，才由系統(tǒng)回收該段所占內(nèi)存區(qū)。（2