主存擴(kuò)充虛擬內(nèi)存教程文件

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

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

9

87

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

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

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

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

xxxxxxx

xx

共缺頁中斷9次FIFO2024/9/26第四章存儲管理訪問順序432143543215432143543215432143543214321435432

xxxxxxx

xxx共缺頁中斷10次

LRU2024/9/26第四章存儲管理

OPT432143543215432111555211433333335554444444444

xxxx

x

xx

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

xxxx

x

xxx共缺頁中斷8次2024/9/26第四章存儲管理OPT432143543215頁1432111555511頁243222222255頁34333333333頁4444444444

xxxx

x

x

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

2024/9/26第四章存儲管理2024/9/26第四章存儲管理改進(jìn)型Clock置換算法

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

2024/9/26第四章存儲管理頁面緩沖算法(PBA:PageBufferingAlgorithm)頁面緩沖算法中，被淘汰的頁存放在兩個鏈表（隊列）： 頁面未修改的淘汰頁

空閑頁鏈表（實質(zhì)：空閑物理塊鏈表） 頁面已修改的淘汰頁

已修改頁面鏈表。2024/9/26第四章存儲管理當(dāng)需要讀入一個頁面時，便利用空閑物理塊鏈表中的第一個物理塊來裝入。當(dāng)有一個未被修改的頁要換出時，并不將它換出內(nèi)存，而是直接把它所在的物理塊掛在空閑頁鏈表的末尾。換出一個已修改的頁面時，則將其所在的物理塊掛在修改頁面鏈表的末尾。注：換出頁面時，頁面在內(nèi)存并不做物理上的移動，只是將頁表中的表項移到上述兩個鏈表之一中。2024/9/26第四章存儲管理優(yōu)點(diǎn)：可使已被修改的頁面和未被修改的頁面，都仍留在內(nèi)存中。當(dāng)進(jìn)程以后再次訪問這些頁面時，就有可能只須花費(fèi)較小的開銷。

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

2024/9/26第四章存儲管理FIFO432143543215頁1432143555211頁243214333522頁34

3

2

1444

355

xxxxxxx

xx

共缺頁中斷9次m=32024/9/26第四章存儲管理FIFO432143543215頁1432111543215頁243222154321頁34333215432頁4444

3

2

1543

xxxx

xx

xxxx共缺頁中斷10次m=42024/9/26第四章存儲管理m=3時，缺頁中斷9次，缺頁率9/12=75%m=4時，缺頁中斷10次，缺頁率10/12=83%FIFO頁面淘汰算法會產(chǎn)生異常現(xiàn)象（稱為Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時，缺頁次數(shù)反而增加2024/9/26第四章存儲管理練習(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)生多少次缺頁中斷？2024/9/26第四章存儲管理解程序編制方法1：forj:=1to128fori:=1to128A[i,j]:=0;程序編制方法2：fori:=1to128forj:=1to128A[i,j]:=0;128*1281282024/9/26第四章存儲管理

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

4.8虛擬段式存儲管理2024/9/26第四章存儲管理1、段表內(nèi)容

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

P139圖4-313、地址變換

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

P140圖4-332024/9/26第四章存儲管理（1）共享進(jìn)程計數(shù)count整型變量，記錄共享該分段的進(jìn)程數(shù)。共享段只有當(dāng)所有共享該段的進(jìn)程全都不再需要它時，才由系統(tǒng)回收該段所占