操作系統(tǒng)原理與實踐教程(第四版) 第6章 虛擬存儲器

6.1虛擬存儲器引入6.2虛擬存儲器的實現(xiàn)方法6.3虛擬存儲器的特征6.4請求分頁存儲管理技術(shù)

6.5頁面置換算法6.6“抖動”與工作集6.7請求分段存儲管理方式第5章虛擬存儲器第6章

虛擬存儲器6.1虛擬存儲器引入前面所介紹的幾種存儲管理方式有一個共同的特點，都要求將一個作業(yè)全部裝入內(nèi)存之后才能運行，于是，就可能出現(xiàn)以下兩種情況：(1)有的作業(yè)很大，其要求的內(nèi)存空間超過了內(nèi)存總?cè)萘浚瑥亩鴮?dǎo)致作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運行。(2)有多個作業(yè)要求運行，其要求的內(nèi)存空間超過了可用的內(nèi)存空間，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運行，而將其它作業(yè)留在外存等待。6.1虛擬存儲器的引入1.傳統(tǒng)存儲管理方式的特征(1)一次性。前面介紹的幾種存儲管理方式有一個共同的特點，都要求將作業(yè)全部裝入內(nèi)存之后才能運行，即作業(yè)在運行前需要一次性地全部裝入內(nèi)存，正是這一特征導(dǎo)致了上述兩種情況的發(fā)生。另外，許多作業(yè)在每次運行時，并非要用到全部程序和數(shù)據(jù)，因此一次性地裝入全部程序和數(shù)據(jù)，對內(nèi)存空間是一種極大的浪費。(2)駐留性。作業(yè)裝入內(nèi)存直到運行結(jié)束，便一直駐留在內(nèi)存中。盡管進(jìn)程在運行中會因I/O等原因而長期處于阻塞狀態(tài)，或有的程序模塊在運行過一次后就不再需要，但它們都仍將繼續(xù)占用寶貴的內(nèi)存資源。6.1虛擬存儲器的引入2.局部性原理早在1968年，Denning.P就曾指出：程序的執(zhí)行表現(xiàn)出局部性特征，即程序在執(zhí)行過程中的一個時間段內(nèi)，程序的執(zhí)行僅局限于某個部分。相應(yīng)地，它所執(zhí)行的指令地址或操作數(shù)地址也局限于一定的存儲區(qū)域中。(1)程序執(zhí)行時，只有少量分支轉(zhuǎn)移和過程被調(diào)用，在大部分情況下仍是順序執(zhí)行的指令。(2)程序中包含許多循環(huán)結(jié)構(gòu)，由相對較少的指令組成，但是它們將多次執(zhí)行。在循環(huán)過程中，計算被限制在程序中很小的相鄰部分中。(3)程序中過程調(diào)用的深度限制在小范圍內(nèi)，很少出現(xiàn)連續(xù)的過程調(diào)用，大多數(shù)情況下都不超過5。一段時間內(nèi)，指令引用被局限在很少幾個過程中。(4)對于連續(xù)訪問數(shù)組之類的數(shù)據(jù)結(jié)構(gòu)，往往是對存儲區(qū)域中相鄰位置的數(shù)據(jù)進(jìn)行操作。(5)程序中有些部分是彼此互斥的，不是每次運行時都用到，如出錯處理程序。6.1虛擬存儲器的引入2.局部性原理局限性還表現(xiàn)在下述兩個方面；(1)時間局部性。如果程序中的某條指令正在執(zhí)行，則不久后，該指令可能會再次執(zhí)行。同樣，如果某數(shù)據(jù)被訪問過，則不久后，該數(shù)據(jù)可能會被再次訪問。時間局部性的產(chǎn)生原因是由于在程序中存在著大量的循環(huán)操作。(2)空間局部性。程序在運行過程中，一旦訪問了某個內(nèi)存單元，則在不久后，其鄰近的存儲單元也將可能被訪問，即程序在一段時間內(nèi)所訪問的內(nèi)存地址，可能集中在一定的范圍之內(nèi)?？臻g局部性的產(chǎn)生原因是由于程序的順序執(zhí)行。6.1虛擬存儲器的引入3.虛擬存儲器的概念虛擬存儲器是指在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中，具有請求調(diào)入和交換功能，為用戶提供一個比實際物理內(nèi)存容量大得多的可尋址的一種存儲器系統(tǒng)，它能從邏輯上對內(nèi)存容量進(jìn)行擴充。其邏輯容量由內(nèi)存容量和外存容量之和決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。虛擬存儲器的容量主要受到兩方面的限制：(1)指令中表示地址的字長。一個虛擬存儲器的最大容量是由計算機的地址結(jié)構(gòu)確定的。如：若CPU的有效地址長度為32位，則程序可以尋址的范圍就是0～232-1，即虛存容量為4GB。(2)外存的容量。虛擬存儲器的容量與主存的實際大小沒有直接關(guān)系，而是由主存與輔存的容量之和確定。虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，已被廣泛應(yīng)用于大、中、小型機器和微型機中。6.2虛擬存儲器的實現(xiàn)方法虛擬存儲器的實現(xiàn)都必須建立在離散分配的存儲管理方式基礎(chǔ)上。虛擬存儲系統(tǒng)需要具有請求調(diào)頁(段)功能和頁面(分段)置換功能。如果程序執(zhí)行時發(fā)生缺頁或缺段，此時程序就可以利用系統(tǒng)提供的請求調(diào)頁(段)功能，將它們調(diào)入內(nèi)存，以使程序能夠繼續(xù)執(zhí)行下去。如果內(nèi)存已滿，無法裝入新調(diào)入的頁(段)，則必須利用一定的頁(段)置換功能，將內(nèi)存中暫時不用的頁(段)換到外存中，以騰出足夠的空間來存放新調(diào)入的頁(段)，從而保證程序的順利執(zhí)行。虛擬存儲器根據(jù)地址空間結(jié)構(gòu)的不同可以分為分頁虛擬存儲器和分段虛擬存儲器兩類，也可以把兩者結(jié)合起來，構(gòu)成段頁式虛擬存儲器。6.3虛擬存儲器的特征(1)虛擬性。虛擬內(nèi)存不是擴大實際的物理內(nèi)存，而是從邏輯上擴充內(nèi)存的容量。(2)多次性。多次性是指一個作業(yè)可被分成多次調(diào)入內(nèi)存運行。(3)對換性。對換性是指允許在作業(yè)運行過程中進(jìn)行換進(jìn)和換出。虛擬性是以多次性和交換性為基礎(chǔ)的，或者說，只有系統(tǒng)允許作業(yè)分多次調(diào)入內(nèi)存，并能將內(nèi)存中暫時不運行的程序和數(shù)據(jù)交換到外存，系統(tǒng)才可能實現(xiàn)虛擬存儲器，而多次性和對換性，又必須建立在離散分配的基礎(chǔ)上。1)進(jìn)程地址空間分為虛頁實現(xiàn)原理之所以稱虛頁，因為運行時不一定在主存2)運行前裝入部分頁3)運行時訪問的頁面不在內(nèi)存,缺頁中斷,調(diào)入缺頁.4)缺頁中斷,調(diào)入新頁時,若內(nèi)存無空閑塊,則淘汰某頁,把新頁調(diào)入.5)地址變換(重定位):類似簡單分頁系統(tǒng),但頁表要增加4項（增加請求調(diào)頁、頁面置換功能）6.4請求分頁存儲管理方式第6章虛擬存儲器6.4在簡單頁式存儲管理的基礎(chǔ)上，PMT中增加請求調(diào)頁和頁面置換功能。簡單分頁PMT請求頁式進(jìn)程頁表(PMT)塊號頁號AM外存地址P塊號頁號淘汰此頁寫回外存

M修改位：該頁被寫過否0否,1是,淘汰此頁不寫回外存

A訪問字段：頁面訪問統(tǒng)計,在近期內(nèi)被訪問的次數(shù)，或最近一次訪問到現(xiàn)在的時間間隔.為淘汰算法提供依據(jù)

外存地址:通常是外存物理塊號。

P狀態(tài)位:該頁在主存否0否1在地址變換查表時發(fā)現(xiàn)P=0,硬件缺頁中斷第6章虛擬存儲器6.46.4.1請求分頁中的硬件支持產(chǎn)生缺頁中斷請求調(diào)頁缺頁中斷處理保留CPU現(xiàn)場選擇一頁換出確定缺頁外存地址此頁修改過否？該頁寫回外存缺頁換入內(nèi)存修改頁表NY程序請求訪問一頁CPU查快表訪問頁表頁在內(nèi)存？形成物理地址修改訪問字段和修改位修改快表組織讀缺頁命令啟動I/O開始頁號≧頁表長度？越界中斷頁表項在快表中？YNYN內(nèi)存滿否？NYNY6.4.2請求分頁中的內(nèi)存分配1.最小物理塊數(shù)的確定

是指能保證進(jìn)程正常運行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時，進(jìn)程將無法運行。進(jìn)程應(yīng)獲得的最小物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。為進(jìn)程分配內(nèi)存時，將涉及到三個問題：第一，最小物理塊數(shù)的確定；第二，物理塊的分配策略；第三，物理塊的分配算法。第6章虛擬存儲器6.42.內(nèi)存分配策略

固定分配局部置換為每個進(jìn)程分配一定數(shù)目的物理塊，整個運行期間都不再改變。

可變分配全局置換

先為系統(tǒng)中的每個進(jìn)程分配一定數(shù)目的物理塊，而OS自身也保持一定空閑物理塊隊列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中取出一個物理塊分配給該進(jìn)程，并將欲調(diào)入的頁裝入其中。

第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配2.內(nèi)存分配策略

可變分配局部置換

為每個進(jìn)程分配一定數(shù)目的物理塊，當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，這樣就不會影響其它進(jìn)程的運行。若進(jìn)程運行過程中頻繁地發(fā)生缺頁中斷，則系統(tǒng)為該進(jìn)程分配附加的物理塊，直至該進(jìn)程的缺頁率減少到適當(dāng)程度為止；反之，可適當(dāng)減少分配給該進(jìn)程的物理塊數(shù)。第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配并非一個進(jìn)程分配幾個物理塊就可運行,太少可能造成系統(tǒng)抖動。在采用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各進(jìn)程。可采用以下幾種算法：平均分配:將系統(tǒng)中所有可供分配的物理塊平均分配給各個進(jìn)程。

內(nèi)存塊平均分給各進(jìn)程。小進(jìn)程有利,長進(jìn)程中斷率高。3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配2)根據(jù)進(jìn)程大小按比例分配:根據(jù)進(jìn)程的大小按比例分配物理塊。

如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中個進(jìn)程頁面數(shù)的總和為：3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配再假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)bi可由下式計算：3)考慮優(yōu)先權(quán)的分配算法:為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它們分配較多的內(nèi)存空間。

通常將可供分配的所有物理塊分成兩部分：一部分按比例分配給各進(jìn)程。另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)進(jìn)行分配，可為高優(yōu)先級進(jìn)程適當(dāng)?shù)卦黾悠湎鄳?yīng)份額。在重要的實時系統(tǒng)中，則可能是完全按優(yōu)先權(quán)為各進(jìn)程分配其物理塊。

3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配6.4.3頁面調(diào)入策略1）

預(yù)調(diào)頁策略：以預(yù)測為基礎(chǔ)需要調(diào)入某頁時，一次調(diào)入該頁以及相鄰的幾個頁。(通常用于進(jìn)程首次調(diào)入內(nèi)存,可同時調(diào)入幾頁)優(yōu)點：提高調(diào)頁的I/O效率。缺點：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調(diào)頁。1.何時調(diào)入頁面第6章虛擬存儲器6.46.4.3頁面調(diào)入策略2）請求調(diào)頁策略：當(dāng)發(fā)生缺頁時，只調(diào)入發(fā)生缺頁時所需的頁面。調(diào)入的頁一定會被訪問。優(yōu)點：容易實現(xiàn)。缺點：對外存I/O次數(shù)多，開銷較大1.何時調(diào)入頁面第6章虛擬存儲器6.46.4.3頁面調(diào)入策略通常對換區(qū)的I/O效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，這里有三種做法：1）

從對換區(qū):進(jìn)程裝入前，將其全部頁面復(fù)制到對換區(qū)，以后總是從對換區(qū)調(diào)入。執(zhí)行時調(diào)入速度快，要求對換區(qū)空間較大。2）

未被修改的頁面從文件區(qū)讀入，而被置換時不需調(diào)出；已被修改的頁面從對換區(qū)調(diào)入,節(jié)省對換區(qū)空間.被修改過的頁面淘汰時送入對換區(qū)2.從何處調(diào)入頁面第6章虛擬存儲器6.46.4.3頁面調(diào)入策略通常對換區(qū)的I/O效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，這里有三種做法：2.從何處調(diào)入頁面3）

UNIX方式。未運行過的頁面都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運行過但又被換出的頁面，應(yīng)從對換區(qū)調(diào)入。又由于UNIX系統(tǒng)允許頁面共享，如果某進(jìn)程所請求的頁面已經(jīng)被其他進(jìn)程調(diào)入內(nèi)存，此時也無須從對換區(qū)調(diào)入。第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

頁面未在內(nèi)存時（存在位為“0”），程序向CPU發(fā)出一缺頁中斷申請。

轉(zhuǎn)入缺頁中斷處理程序調(diào)入新頁置換

修改快表訪問內(nèi)存數(shù)據(jù)3.頁面調(diào)入過程整個頁面的調(diào)入過程對用戶是透明的。第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

缺頁率：設(shè)一個進(jìn)程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(m≤n)。

如果在進(jìn)程的運行過程中，訪問頁面成功（即所訪問的頁面在內(nèi)存中）的次數(shù)為S。訪問頁面失?。此L問的頁面需從外存調(diào)入）的次數(shù)為F。

則總的頁面訪問數(shù)次為A=S+F，那么缺頁率為：4.缺頁率第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

影響缺頁率的因素

頁面大小進(jìn)程所分配物理塊的數(shù)據(jù)頁面置換算法程序固有特性4.缺頁率第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

事實上，在缺頁中斷處理時，當(dāng)由于空間不足，需要置換部分頁面到外存時，選擇置換頁面還需要考慮到置換的代價。

頁面未修改過，直接放棄。

頁面修改過，必須保存。4.缺頁率第6章虛擬存儲器6.4設(shè)被置換的頁面被修改的概率為β，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的的缺頁中斷時間為tb。則缺頁中斷處理時間的計算公式是：

請求分頁系統(tǒng)的評價優(yōu)點：請求分頁存儲管理具有分頁存儲管理的全部優(yōu)點，特別是它有效地緩解了碎片的問題。提供了大容量的多個虛擬存儲器；作業(yè)地址空間不再受實際存儲容量的限制；更有效地利用主存；有利于運行多道程序；提高了系統(tǒng)效率，方便了用戶，特別是大作業(yè)用戶；第6章虛擬存儲器6.4缺點：要求有相應(yīng)的硬件支持，從而增加了成本，如動態(tài)地址變換、快表、缺頁中斷的產(chǎn)生等都要求有相應(yīng)的硬件支持。缺頁中斷增加了處理機時間的開銷，如頁表的建立與管理、缺頁中斷處理等；頁面淘汰算法如選擇不當(dāng)，有可能產(chǎn)生抖動現(xiàn)象，為防止抖動，會增加系統(tǒng)的復(fù)雜性；雖然減少了碎片，但每個進(jìn)程的最后一頁內(nèi)總有一部分空間得不到利用；請求分頁系統(tǒng)的評價第6章虛擬存儲器6.4有一臺16位機，可訪問64K空間，給出的地址長度16位內(nèi)存為32K。在具有虛擬存儲功能的系統(tǒng)中，允許進(jìn)程的地址空間=64K（虛地址空間）64K地址空間不能全部裝入內(nèi)存，部分裝入外存有一個64K的地址空間映象運行時由MMU（MemoryManagementUnit）進(jìn)行地址變換頁面劃分為4K：64K的虛地址空間可分為0…15（16個頁面）物理空間分為8個塊討論：第6章虛擬存儲器6.4216043XXX5X7XXXX60K-64K…1556K-60K…1452K-56K…1348K-52K…1244K-48K…1140K-44K…1036K-40K…932K-36K…828K-32K…724K-28K…620K-24K…516K-20K…412K-16K…3

8K-12K…24K-8K…10K-4K…0虛地址空間}虛頁28K-32K…724K-28K…620K-24K…516K-20K…412K-16K…38K-12K…24K-8K……10K-4K……0物理地址空間物理塊（虛擬存儲器）第5章虛擬存儲器6.401234567891011121314010100111101000110010111X0X0X01011X01111X0X0X0X015110000000000100001000000000010110頁表VAMA0CPU執(zhí)行

loadR1，8196（2004H）CPU給出虛地址8196送VA，分離出P|W：2|4因存在位為1，故2頁在內(nèi)存中，其物理塊號為6塊號6送MA的高四位，W送MA的低12位，形成物理地址：24580（6004H）6004H送地址總線讀取數(shù)據(jù)到寄存器R1。第6章虛擬存儲器6.40缺頁中斷機構(gòu)：在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。缺頁中斷同樣需要經(jīng)歷保護CPU環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進(jìn)行處理、恢復(fù)CPU環(huán)境等幾步。但缺頁與一般中斷相比，有著明顯的區(qū)別，主要表現(xiàn)在：（1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號。（2）一條指令在執(zhí)行期間，可能產(chǎn)生多次中斷。如圖所示例子。123466頁面COPYATOBB:A:指令指令COPYATOB本身跨了兩頁，A和B分別各是一個數(shù)據(jù)塊，也都跨了兩頁。該指令的執(zhí)行可能產(chǎn)生6次缺頁中斷。第5章虛擬存儲器6.4產(chǎn)生缺頁中斷請求調(diào)頁缺頁中斷處理保留CPU現(xiàn)場選擇一頁換出確定缺頁外存地址此頁修改過否？該頁寫回外存缺頁換入內(nèi)存修改頁表NY程序請求訪問一頁CPU查快表訪問頁表頁在內(nèi)存？形成物理地址修改訪問字段和修改位修改快表組織讀缺頁命令啟動I/O開始頁號≧頁表長度？越界中斷頁表項在快表中？YNYN內(nèi)存滿否？NYNY6.5頁面置換算法功能：需要調(diào)入頁面時，選擇內(nèi)存中哪個物理頁面被置換。稱為replacementpolicy。目標(biāo)： ①把未來不再使用的調(diào)出 ②短期內(nèi)較少使用的頁面調(diào)出（根據(jù)局部性原理，依據(jù)過去的統(tǒng)計數(shù)據(jù)預(yù)測）頁面鎖定(framelocking)：

必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分，不允許調(diào)出，頁表項中加上鎖定標(biāo)志位(lockbit)。第6章虛擬存儲器6.5最佳置換算法(OPT,optimal)先進(jìn)先出頁面置換算法(FIFO)最近最久未使用置換算法(LRU,LeastRecentlyUsed)Clock置換算法(clock)其他置換算法最少使用置換算法 (LFU,LeastFrequentlyUsed)

頁面緩沖算法6.5頁面置換算法第6章虛擬存儲器6.51.最佳置換算法(OPT,optimal)選擇被置換頁面： “未來不再使用的” 或“在最長（未來）時間內(nèi)不再訪問的”這是一種理想情況，實際中是無法預(yù)知的，因而不能實現(xiàn)?？捎米髂乘惴ㄐ阅茉u價的依據(jù)。Example1:假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1第6章虛擬存儲器6.56.5.1最佳置換算法和先進(jìn)先出置換算法利用最佳置換算法時的置換圖70120304230321201701770701201201203203243243243203203203201201201201701701√√√√√√缺頁中斷9次，頁面置換6次頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√第6章虛擬存儲器6.5√√17012.先進(jìn)先出算法(FIFO)FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇進(jìn)入內(nèi)存中駐留時間最長的頁面進(jìn)行淘汰?？梢园岩粋€進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。

該算法性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復(fù)調(diào)入和調(diào)出，可能產(chǎn)生Belady（貝萊迪）異常。第6章虛擬存儲器6.52.先進(jìn)先出算法(FIFO)Belady（貝萊迪）異常：在分頁式虛擬存儲器管理中，發(fā)生缺頁時的置換算法采用FIFO（先進(jìn)先出）算法時，如果對一個進(jìn)程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的物理塊數(shù)目增多，但缺頁率反而提高的異?，F(xiàn)象。即替換策略不符合隨著物理塊數(shù)量的增大，缺頁率一定減少的規(guī)律。Belady異常的原因：

FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會訪問的。第6章虛擬存儲器6.5利用FIFO置換算法時的置換圖70120304230321201701770701201201231230430420423023023023013012012012712702√√√√√缺頁中斷16次，頁面置換12次701√√√√√√頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√√第6章虛擬存儲器6.5√√√√√6.5.2最近最久未使用和最少使用置換算法一個特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個頁面設(shè)立移位寄存器：被訪問時左邊最高位置1，周期右移并且最高位補0，于是寄存器數(shù)值最小的是最久未使用頁面。選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關(guān)系，硬件開銷太大。硬件機構(gòu)如：第6章虛擬存儲器6.51LRU(LeastRecentlyUsed)置換算法的描述利用LRU置換算法時的置換圖70120304230321201701770701201201203203403402432032032032132132102102107107√√√√√缺頁中斷12次，頁面置換9次107√√√√頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√第6章虛擬存儲器6.5√√√6.6頁面緩沖算法在請求分頁系統(tǒng)中，由于進(jìn)程在運行時經(jīng)常會發(fā)生頁面換進(jìn)換出的情況，所以一個十分明顯的事實就是，頁面換進(jìn)換出所付出的開銷將對系統(tǒng)性能產(chǎn)生重大的影響。在此，我們首先對影響頁面換進(jìn)換出效率的若干因素進(jìn)行分析。6.6.1影響頁面換進(jìn)換出效率的若干因素1.頁面置換算法。2.寫回磁盤的頻率。3.讀入內(nèi)存的頻率。6.6.2頁面緩沖算法PBAPBA算法的主要特點是：①顯著地降低了頁面換進(jìn)、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進(jìn)、換出的開銷；②正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進(jìn)先出（FIFO）算法，它不需要特殊硬件的支持，實現(xiàn)起來非常簡單。1.空閑頁面鏈表2.修改頁面鏈表6.7訪問內(nèi)存的有效時間（1）被訪問頁在內(nèi)存中，且其對應(yīng)的頁表項在快表中。顯然，此時不存在缺頁中斷情況，內(nèi)存的有效訪問時間（EAT）分為查找快表的時間（λ）和訪問實際物理地址所需的時間（t）:EAT=λ+t（2）被訪問頁在內(nèi)存中，且其對應(yīng)的頁表項不在快表中。顯然，此時也不存在缺頁中斷情況，但需要兩次訪問內(nèi)存，一次讀取頁表，一次讀取數(shù)據(jù)，另外還需要更新快表。所以，這種情況內(nèi)存的有效訪問時間可分為查找快表的時間、查找頁表的時間、修改快表的時間和訪問實際物理地址的時間：EAT=λ+t+λ+t=2*（λ+t）（3）被訪問頁不在內(nèi)存中。因為被訪問頁不在內(nèi)存中，需要進(jìn)行缺頁中斷處理，所以這種情況的內(nèi)存的有效訪問時間可分為查找快表的時間、查找頁表的時間、處理缺頁中斷的時間、更新快表的時間和訪問實際物理地址的時間：假設(shè)缺頁中斷處理時間為ε,則EAT=λ+t+ε+λ+t=ε+2*（λ+t）6.8工作集理論和抖動問題從主存中剛剛移走某頁面后，根據(jù)請求馬上又調(diào)入該頁。這種反復(fù)進(jìn)行入頁和出頁的現(xiàn)象稱為“抖動”，也叫系統(tǒng)顛簸。它會浪費大量的處理機時間，應(yīng)盡可能避免。產(chǎn)生抖動的直接原因是頁面置換算法選取不當(dāng)。第5章虛擬存儲器6.86.8“抖動”與工作集請求分頁系統(tǒng)能有效地減少內(nèi)存碎片，提高處理機的利用率和吞吐量，是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運行的進(jìn)程太多，進(jìn)程在運行中頻繁地發(fā)生缺頁情況，又會對系統(tǒng)的性能產(chǎn)生很大的影響。6.86.8.1多道程序度與“抖動”第5章虛擬存儲器6.8抖動與工作集1.多道程序度與處理機的利用率100%CPU飽和度利用率0N1NmaxN2N3L/S

抖動6.86.8.1多道程序度與“抖動”第5章虛擬存儲器6.8抖動與工作集1.多道程序度與處理機的利用率100%CPU飽和度利用率0N1NmaxN2N3L/S

抖動在橫軸的開始部分，隨著進(jìn)程數(shù)目的增加，處理機的利用率急劇增加；到達(dá)N1時，增速明顯減慢；到達(dá)Nmax時，處理機的利用率達(dá)到最大，之后開始緩慢下降；到達(dá)N2時，處理機的利用率下降加快之所以出現(xiàn)利用率趨于0的情況，是因為系統(tǒng)中出現(xiàn)了“抖動”。第5章虛擬存儲器6.8L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間6.8抖動與工作集2.產(chǎn)生“抖動”的原因同時在系統(tǒng)中運行的進(jìn)程太多，由此分配給每一個進(jìn)程的物理塊太少，不能滿足進(jìn)程正常運行的基本要求，致使每個進(jìn)程在運行時，頻繁地出現(xiàn)缺頁，造成每個進(jìn)程的大部分時間都用于頁面的換進(jìn)/換出，而幾乎不能再去做任何有效的工作，從而導(dǎo)致發(fā)生處理機的利用率急劇下降并趨于0的情況。第5章虛擬存儲器6.86.8抖動與工作集6.8.2工作集進(jìn)程發(fā)生缺頁率的時間間隔與進(jìn)程所獲得的物理塊數(shù)有關(guān)從圖中可以看出，缺頁率隨著所分配物理塊數(shù)的增加明顯地減少，當(dāng)物理塊數(shù)超過某個數(shù)目時，再為進(jìn)程增加一個物理塊，對缺頁率的改善已不明顯。已無必要再為它分配更多的物理塊。當(dāng)為某進(jìn)程所分配的物理塊數(shù)低于某個數(shù)目時，每減少一塊，對缺頁率的影響都變得十分明顯。應(yīng)為進(jìn)程分配更多的物理塊缺頁率上限下限0n物理塊數(shù)缺頁率與物理塊數(shù)之間的關(guān)系第5章虛擬存儲器6.86.8抖動與工作集6.8.2工作集是指在某段時間間隔Δ里，進(jìn)程實際所要訪問頁面的集合。24151823241718241817171524172418242424152415241524181524181524181524231815231815242318152424231824231815242318151724231724231817242318151817241817242318172423241817241817241817231824182417182417171824171824171824171817182417182415171517181517182424151724151724151718172415172415172415241724171524171518241718241718241715引用頁面序列窗口大小345第5章虛擬存儲器6.86.8抖動與工作集6.8.3“抖動”的預(yù)防方法1．采取局部置換策略當(dāng)某進(jìn)程發(fā)生缺頁時，只能在分配給自己的內(nèi)存空間內(nèi)進(jìn)行置換，不允許從其它進(jìn)程去獲得新的物理塊，即使“抖動”也不影響其它進(jìn)程。2．把工作集算法融入到處理機調(diào)度中從外存調(diào)入作業(yè)時，先檢查每個進(jìn)程在內(nèi)存的駐留頁面是否足夠多。如果已經(jīng)足夠多，新作業(yè)的調(diào)入不會導(dǎo)致缺頁率的增加；反之，如果某些進(jìn)程的頁面不足，應(yīng)首先為那些缺頁率居高的作業(yè)增加新的物理塊。第5章虛擬存儲器6.86.8抖動與工作集6.8.3“抖動”的預(yù)防方法3.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率利用“L=S”準(zhǔn)則調(diào)節(jié)多道程序度，L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間，即用于置換一個頁面所需的時間。L<S，頻繁發(fā)生缺頁；L>S，很少缺頁；L與S接近，磁盤和處理機都可達(dá)到它們的最大利用率。4．選擇暫停的進(jìn)程掛起某些暫停的進(jìn)程。第5章虛擬存儲器6.86.9請求分段存儲管理方式在簡單段式存儲管理的基礎(chǔ)上，SMT增加5項:1.請求段表機制1)地址空間分為若干虛段,運行前裝入部分段.2)當(dāng)訪問的段不在內(nèi)存時產(chǎn)生“缺段中斷”,把缺的段調(diào)入內(nèi)存.3)如果內(nèi)存無空閑空間,則置換出暫不用的某個段.很類似虛擬頁式。學(xué)習(xí)中注意二者差異段號段長內(nèi)存首址存取權(quán)限AMP增補位外存始址基本段式SMT增加的表項第5章虛擬存儲器外存始址增補位PMA存取權(quán)限內(nèi)存首址段長段號基本段式SMT增加的表項1)存取權(quán)限:如讀R，寫W，執(zhí)行X2)A訪問字段:段訪問統(tǒng)計,在近期內(nèi)被訪問的次數(shù)， 或近一次訪問到現(xiàn)在的時間間隔.為淘汰算法提供依據(jù)。3)M修改位:該段是否被修改過。4)P存在位(狀態(tài)位):該段在主存否。5)增補位:該段動態(tài)增長過否。6)外存始址:該段外存起始盤塊號。第5章虛擬存儲器

內(nèi)存分配:在虛擬段式管理中是按段對物理內(nèi)存進(jìn)行分配，可采用動態(tài)分區(qū)算法。2.缺段中斷處理:(參看圖5-12)1)當(dāng)指令給出訪問地址:S|W,地址變換機構(gòu)首先檢查SMT的存在位.2)當(dāng)存在位表示該段不在內(nèi)存,則產(chǎn)生缺段中斷請求：①CPU響應(yīng)中斷,進(jìn)入中斷處理，把缺的段調(diào)入內(nèi)存,修改SMT和內(nèi)存空閑區(qū)鏈表.②若內(nèi)存無合適空閑區(qū),則拼接或置換某段，形成合適的空閑區(qū)，調(diào)入新段，修改SMT和內(nèi)存空閑鏈表.第5章虛擬存儲器6.9圖5-12缺段中斷處理流程第5章虛擬存儲器6.93.地址變換機構(gòu):(參看圖5-13)訪問S|WW≦段長？N分段越界中斷處理Y符合存取方式？N分段保護中斷處理Y段S在內(nèi)存否？N缺段中斷處理Y修改訪問字段A，如果是寫訪問，則置修改位M=1返回形成物理地址：段始址+W是否出錯？E、R、W查P=1？同于基本段式地址變換機構(gòu)第5章虛擬存儲器6.9

1．共享段表為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項。表項中記錄了共享段的段號、段長、內(nèi)存始址、存在位等信息，并記錄了共享此分段的每個進(jìn)程的情況。共享段表如圖所示。其中各項說明如下。6.9.2分段的共享與保護第5章虛擬存儲器6.9共享進(jìn)程計數(shù)count。記錄有多少個進(jìn)程需要共享該分段。存取控制字段。不同進(jìn)程對該段的存取權(quán)限段號。對于一個共享段，不同的進(jìn)程可以各用不同的段號去共享該段。

圖5-14共享段表項

第5章虛擬存儲器6.9段名段長內(nèi)存始址狀態(tài)外存始址共享進(jìn)程計數(shù)進(jìn)程狀態(tài)進(jìn)程名進(jìn)程號段號存取控制權(quán)限……S2301002H1452就緒P1320R阻塞P2561RWN23501A2CH0693就緒P8682X阻塞P9971R阻塞P32003RD4602B00H12002就緒P201334RW阻塞P32002R共享段表示例第5章虛擬存儲器6.9

2．共享段的分配與回收

1)共享段的分配

對第一個請求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進(jìn)程的段表的相應(yīng)項中，還須在共享段表中增加一表項，填寫有關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進(jìn)程需要調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無