15存儲(chǔ)管理4虛擬存儲(chǔ)請(qǐng)求頁式管理1

1、1內(nèi)存的物理組織物理地址：把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存地址（物理地址,絕對(duì)地址,實(shí)地址）,存儲(chǔ)單元占8位，稱作字節(jié)（byte）。物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維的線性空間。2程序的邏邏輯結(jié)構(gòu)構(gòu)程序地址址：用戶編程程序時(shí)所所用的地地址（或或稱邏輯地址址 、虛虛地址），基本本單位可可與內(nèi)存存的基本本單位相相同，也也可以不不相同。程序地址址空間（邏輯地地址空間間、虛地地址空間間）:用戶的程程序地址址的集合合稱為邏邏輯地址址空間，它的編編址總是是從0開始的，可以是是一維線線性空間間，也可可以是多多維空間間。34.6虛

2、擬存儲(chǔ)儲(chǔ)器的基基本概念念4.6.1虛擬存儲(chǔ)儲(chǔ)器的引引入4.6.2虛擬存儲(chǔ)儲(chǔ)器的實(shí)實(shí)現(xiàn)方法法4.6.1虛擬存儲(chǔ)儲(chǔ)器的特特征4.6.1虛擬擬存儲(chǔ)器器引入1.常規(guī)規(guī)存儲(chǔ)器器管理方方式的特特征2.局部部性原理理3.虛擬擬存儲(chǔ)器器定義51.前面討論論的各種種存儲(chǔ)管管理方法法雖各有有特長(zhǎng)，但有一一些共同同的特點(diǎn)點(diǎn):首先是“一次性分分配”。其次是“駐留性”。作業(yè)全部部信息，必須一一次性裝裝入內(nèi)存存作業(yè)信息息一旦裝裝入內(nèi)存存便一直直駐留到到作業(yè)運(yùn)運(yùn)行結(jié)束束一方面使使大作業(yè)業(yè)的運(yùn)行行受到限制，另另一方面面又影響響了多道程序序的實(shí)現(xiàn)現(xiàn)。62、局部性性原理程序的局局部性規(guī)規(guī)律，程程序往往往會(huì)不均勻地地高度局局部化地

3、地訪問內(nèi)存存。7（1）程序在在執(zhí)行時(shí)時(shí)，在大大多數(shù)情情況下仍仍是順序序執(zhí)行的的。這種特性性使得程程序的執(zhí)執(zhí)行在一段時(shí)時(shí)間內(nèi)被被限制在在作業(yè)的的某一局局部范圍圍。P.Denning有以下一一些論點(diǎn)點(diǎn)：（2）過程調(diào)調(diào)用將會(huì)會(huì)使程序序的執(zhí)行行軌跡由由一部分分內(nèi)存區(qū)區(qū)域轉(zhuǎn)至至另一部部分區(qū)域域。但在在大多數(shù)數(shù)情況下下，過程程調(diào)用的的深度都都不超過過5。在一段時(shí)時(shí)間內(nèi)，程序?qū)?huì)被局局限于這這些過程程的范圍圍內(nèi)運(yùn)行行。8（3）程序中中存在許許多循環(huán)環(huán)結(jié)構(gòu)，它們可可以多次次重復(fù)執(zhí)執(zhí)行。fori:=1tonai:=ai+1;（4）程序中中還包括括許多對(duì)對(duì)數(shù)據(jù)結(jié)結(jié)構(gòu)的處處理，它它們往往往都局限限于很小小的范圍圍

4、內(nèi)。9局限性的的表現(xiàn)：時(shí)間，空間（1）時(shí)間局限限性時(shí)間局限限性是指最近近被訪問問的存儲(chǔ)儲(chǔ)位置，很可能能不久的的將來還還要被訪訪問。支持這種種現(xiàn)象的的是：(a)循環(huán)；(b)子程序；(c)棧；(d)用于計(jì)數(shù)數(shù)和總計(jì)計(jì)的變量量。10（2）空間局限限性空間局限限性是指指存儲(chǔ)訪訪問有集集成一組組的傾向向，以致致一旦某某個(gè)位置置被訪問問到，很很有可能能它附近近的位置置也要被被訪問。支持這種種現(xiàn)象的的是：a、數(shù)組遍遍歷；b、代碼的的順序執(zhí)執(zhí)行；c、程序員員傾向于于將相關(guān)關(guān)的變量量定義相相互靠近近存放。11基于局部部性原理理，作業(yè)業(yè)沒有必必要全部部裝入內(nèi)內(nèi)存。如果計(jì)算算機(jī)系統(tǒng)統(tǒng)把輔助助存儲(chǔ)器器當(dāng)做主主存儲(chǔ)器器

5、的擴(kuò)充充，當(dāng)作作業(yè)運(yùn)行行時(shí)，不不是將其其全部信信息裝入入內(nèi)存，而是將必須部部分先裝裝入內(nèi)存存，其它部分分仍存于于輔存中中。作業(yè)運(yùn)運(yùn)行過程程中隨時(shí)時(shí)把需要要但又不不在內(nèi)存存的信息息裝入內(nèi)內(nèi)存，把把暫時(shí)不不用的信信息淘汰汰出去，以確保保作業(yè)的的正確運(yùn)運(yùn)行。好象這個(gè)個(gè)計(jì)算機(jī)機(jī)系統(tǒng)向向他們提提供了一一個(gè)容量量很大的的主存123、虛擬存儲(chǔ)儲(chǔ)器的定定義所謂虛擬擬存儲(chǔ)器器是指具具有請(qǐng)求調(diào)入入功能和置換功能能，能從邏邏輯上對(duì)對(duì)內(nèi)存容容量進(jìn)行行擴(kuò)充的的一種存存儲(chǔ)器系系統(tǒng)。虛擬存儲(chǔ)儲(chǔ)器的大大小受計(jì)算機(jī)系系統(tǒng)地址址結(jié)構(gòu)和可用外存存數(shù)量的限制，與實(shí)際際內(nèi)存單單元的數(shù)數(shù)量無關(guān)關(guān)。134.6.2虛擬存儲(chǔ)儲(chǔ)器的實(shí)實(shí)現(xiàn)方式式

6、離散分配配存儲(chǔ)管管理方式是實(shí)實(shí)現(xiàn)虛擬擬存儲(chǔ)器器的基礎(chǔ)礎(chǔ)。1.分頁請(qǐng)求求系統(tǒng)2.分段請(qǐng)求求系統(tǒng)141、頁式虛擬擬存儲(chǔ)系系統(tǒng)是在分頁頁系統(tǒng)的的基礎(chǔ)上上，增加加了請(qǐng)求調(diào)頁頁功能、頁面置置換功能能所形成的的分頁請(qǐng)求求系統(tǒng)。15硬件支持持：(1)請(qǐng)求分頁頁的頁表機(jī)機(jī)制。(2)缺頁中斷斷機(jī)構(gòu)。(3)地址變換換機(jī)構(gòu)。軟件支持持：(1)實(shí)現(xiàn)請(qǐng)求調(diào)頁頁的軟件。(2)實(shí)現(xiàn)頁面置換換的軟件。162、請(qǐng)求分段段系統(tǒng)這是在分分段系統(tǒng)統(tǒng)的基礎(chǔ)礎(chǔ)上，增增加了請(qǐng)求調(diào)段段及分段段置換功功能后，所形形成的段段式虛擬擬存儲(chǔ)系系統(tǒng)。17為了實(shí)現(xiàn)現(xiàn)請(qǐng)求分分段，系系統(tǒng)要提提供硬件件支持：(1)請(qǐng)求分段段的段表表機(jī)制。(2)缺段中斷斷機(jī)構(gòu)

7、。(3)地址變換換機(jī)構(gòu)。同樣地，請(qǐng)求調(diào)調(diào)段和段段的置換換功能的的實(shí)現(xiàn)也也需要得得到OS的支持。184.6.3虛擬存儲(chǔ)儲(chǔ)器的特特征離散性是虛擬存存儲(chǔ)器最最基本的的要求，虛擬性是它的最最重要特特征，另另外虛擬擬存儲(chǔ)器器還具有有多次性和和對(duì)換性性。191、離散性性離散性是是指在內(nèi)內(nèi)存分配配時(shí)采用用離散分分配方式式。2、多次性性作業(yè)分多多次裝入入內(nèi)存3、對(duì)換性性運(yùn)行行時(shí)換進(jìn)進(jìn)換出4、虛擬性性邏輯輯上擴(kuò)充充內(nèi)存容容量最基本特特性204.7請(qǐng)求分頁頁存儲(chǔ)管管理方式式請(qǐng)求分頁頁存儲(chǔ)管管理方式式是建立立在純分分頁基礎(chǔ)礎(chǔ)上的.其基本思思想:在進(jìn)程開開始運(yùn)行行之前，不是裝入入全部頁頁面，而是裝裝入一個(gè)個(gè)或零個(gè)個(gè)頁

8、面，之后根根據(jù)進(jìn)程程運(yùn)行的的需要，動(dòng)態(tài)裝入入其它頁頁面；當(dāng)內(nèi)存存空間已已滿，而而又需要要裝入新新的頁面面時(shí)，則則根據(jù)某種種算法淘淘汰某個(gè)個(gè)頁面，以便裝裝入新的的頁面214.7.1請(qǐng)求分頁頁中的硬硬件支持持一、頁表表機(jī)制二、缺頁頁中斷機(jī)機(jī)構(gòu)三、地址址變換機(jī)機(jī)構(gòu)頁表的作作用是實(shí)實(shí)現(xiàn)從用用戶地址址空間中中的邏輯地址址到內(nèi)存空空間的物理地址址的轉(zhuǎn)換。22請(qǐng)求頁式式管理中中對(duì)地址址空間分分頁，內(nèi)內(nèi)存分塊塊與基本本分頁管管理一樣樣，但對(duì)對(duì)虛頁的的管理是是不同的的。要訪問的的頁面不不在內(nèi)存存中，如如何發(fā)現(xiàn)和處處理這種情況況？這是請(qǐng)求求分頁存存儲(chǔ)管理理要解決決的兩個(gè)個(gè)基本問問題23在純分頁頁系統(tǒng)中中，頁表表的

9、內(nèi)容容為：頁號(hào)物理塊號(hào)針對(duì)第一一個(gè)問題題：如何何發(fā)現(xiàn)要要訪問的的頁面不不在內(nèi)存存？擴(kuò)充充頁表：頁號(hào)物理塊號(hào)狀態(tài)位P外存地址24針對(duì)第二二個(gè)問題題：怎樣樣調(diào)入頁頁面？由地址變變換機(jī)構(gòu)構(gòu)產(chǎn)生一一個(gè)缺頁中斷斷信號(hào)，OS進(jìn)行中斷斷處理后后，根據(jù)據(jù)該頁的的外存地地址把它它從外存存調(diào)入內(nèi)內(nèi)存。引進(jìn)修改位和和訪問字字段。25請(qǐng)求分頁頁系統(tǒng)中中，頁表表項(xiàng)如下下：頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A 修改位M外存地址(1)狀態(tài)位（駐留位位）P:該頁是在在內(nèi)存還還是在外外存(2)訪問字段段位A：記錄本本頁在一一段時(shí)間間內(nèi)被訪訪問的次次數(shù);根據(jù)訪問問位來決決定淘汰汰哪頁（由不同同的算法法決定）(3)修改位M:該頁調(diào)入入內(nèi)

10、存后后是否在在被修改改過(4)外存地址址:該頁在外外存上的的地址,通常為外外存物理理塊號(hào).26在虛擬存存儲(chǔ)系統(tǒng)統(tǒng)中，當(dāng)當(dāng)一個(gè)作作業(yè)被編編譯或經(jīng)經(jīng)鏈接裝裝配后得得到的地地址空間間，通常常存在磁磁盤上。頁號(hào)物理塊號(hào)保護(hù)信息外頁面表表當(dāng)一個(gè)作作業(yè)被調(diào)調(diào)度到而而裝入內(nèi)內(nèi)存時(shí)，系統(tǒng)為為它在內(nèi)內(nèi)存建立立一張頁頁表。272、缺頁中中斷機(jī)構(gòu)構(gòu)在請(qǐng)求分分頁系統(tǒng)統(tǒng)中，當(dāng)當(dāng)要訪問問的頁面面不在內(nèi)內(nèi)存時(shí)，硬件發(fā)發(fā)一個(gè)缺頁中斷斷，轉(zhuǎn)交OS處理。28(1)在指令執(zhí)行期間間產(chǎn)生和處處理中斷斷信號(hào)。(2)一條指令令在執(zhí)行行期間，可能產(chǎn)生多次次缺頁中斷斷。它跟一般般的中斷斷有著明明顯的區(qū)區(qū)別：29頁面654321Copy AT

11、oBB：A：303、地址變變換機(jī)構(gòu)構(gòu)請(qǐng)求分頁頁系統(tǒng)中中的地址址變換機(jī)機(jī)構(gòu)是以以分頁系系統(tǒng)的地地址變換換機(jī)構(gòu)為為基礎(chǔ)的，還增增加了產(chǎn)生缺頁頁中斷、處理缺缺頁中斷斷，置換換等功能。31在進(jìn)行地地址變換換時(shí)，首先去檢索快快表；如果快表表中沒有有這一頁頁的頁表表項(xiàng)，再再到內(nèi)存存中找頁頁表，根根據(jù)狀態(tài)位P來判斷該該頁是否在內(nèi)內(nèi)存中。在內(nèi)存，將該頁頁的頁表表寫入快快表；快快表滿時(shí)時(shí)，調(diào)出出某頁表表項(xiàng)，再再寫入該該頁的頁頁表項(xiàng)不在內(nèi)存存，則產(chǎn)產(chǎn)生缺頁中斷斷。操作系系統(tǒng)接到到此中斷斷信號(hào)后后，就調(diào)調(diào)出缺頁頁中斷處處理程序序，根據(jù)據(jù)頁表中中給出的的外存地地址，將將該頁調(diào)調(diào)入內(nèi)存存，使作作業(yè)繼續(xù)續(xù)運(yùn)行下下去如果內(nèi)

12、存存中有空空閑塊，則分配配一頁，將新調(diào)調(diào)入頁裝裝入內(nèi)存存，并修修改頁表表中相應(yīng)應(yīng)頁表項(xiàng)項(xiàng)目的駐駐留位及及相應(yīng)的的內(nèi)存塊塊號(hào)若此時(shí)內(nèi)內(nèi)存中沒有空閑閑塊，則要淘汰某某頁，若該頁頁在內(nèi)存存期間被被修改過過，則要要將其寫寫回外存存,否則不寫寫32圖4-25這里僅僅僅給出一一個(gè)很粗粗略的框框圖，具具體的過過程是很很復(fù)雜的的。因?yàn)闉樽鳂I(yè)的的副本是是以文件件形式存存于外存存上，因因而要求求頁面?zhèn)鱾鬏敃r(shí)，必然要要涉及到到文件系統(tǒng)統(tǒng)，此外，還得調(diào)調(diào)用輸入輸出出進(jìn)程。在多道道程序環(huán)環(huán)境下，一個(gè)作作業(yè)在等等待傳輸輸頁時(shí)，它處于于被阻塞塞的狀態(tài)態(tài)。此時(shí)時(shí)，由系系統(tǒng)調(diào)度度另一作作業(yè)運(yùn)行行。當(dāng)頁頁面?zhèn)鬏斴斖瓿珊蠛?，才把?/p>

13、原先被被阻塞的的那個(gè)作作業(yè)重新新置成就就緒狀態(tài)態(tài)，但要要等到再再次調(diào)度度到它時(shí)時(shí)，才能能恢復(fù)到到原先中中斷的地地方繼續(xù)續(xù)運(yùn)行下下去。334.7.2內(nèi)存分配策略略和分配配算法在為進(jìn)程程分配物物理塊時(shí)時(shí)，又要要解決三三個(gè)問題題：1、保證進(jìn)程程正常運(yùn)運(yùn)行而需需要的最少物理理塊數(shù)；2、進(jìn)行分分配時(shí)，物理塊塊數(shù)目是是固定的還還是可變變的；（分配策策略）3、是采取取平均分配配算法還是根據(jù)據(jù)進(jìn)程的的大小按比例分分配物理理塊。341、最小物物理塊數(shù)數(shù)的確定定最小的物物理塊數(shù)數(shù)，是指指保證進(jìn)進(jìn)程正常常運(yùn)行所所需的最最少物理理塊數(shù)。最少物理理塊數(shù)與與指令的的格式、功能和和尋址方方式有關(guān)關(guān)，也就就是說與與計(jì)算機(jī)機(jī)的

14、硬件件結(jié)構(gòu)有有關(guān)。如:單地址指指令且直直接尋址址系統(tǒng),至少2塊指令塊/數(shù)據(jù)塊352、物理塊塊的分配配策略1)、固定分配配局部置置換（FixedAllocation,LocalReplacement）基于進(jìn)程程的類型型,為每個(gè)進(jìn)進(jìn)程分配配一定數(shù)數(shù)目的物物理塊(n塊),在整個(gè)運(yùn)運(yùn)行其間間不變;如缺頁: n塊中置換換一頁,以保證該該進(jìn)程在在內(nèi)存中中的頁面面數(shù)不變變;問題:多少個(gè)物物理塊合合適?物理塊太太多:資源空閑閑.物理塊太太少:頻繁中斷斷采取固定定和可變變分配策策略362)、可變分配配全局置置換空閑物理理塊隊(duì)列列先為每個(gè)個(gè)進(jìn)程分分配一定定數(shù)目的的物理塊塊,OS也保持一一個(gè)空閑物理理塊隊(duì)列列,當(dāng)進(jìn)

15、程缺缺頁時(shí),由系統(tǒng)從從空閑物物理塊隊(duì)隊(duì)列取出出一個(gè)物物理塊分分配給該該進(jìn)程,并將要調(diào)調(diào)入的(缺)頁裝入內(nèi)內(nèi)存.僅當(dāng)空閑閑物理塊塊隊(duì)列中中的物理理塊用完完時(shí),OS才從內(nèi)存存中任一進(jìn)程程的一頁頁調(diào)出.問題:會(huì)使被調(diào)調(diào)出頁的的進(jìn)程缺缺頁,進(jìn)而使缺缺頁率增增加,影響其它它進(jìn)程的的執(zhí)行.373)、可變分配配局部置置換要求保持持適當(dāng)?shù)牡娜表撀事驶谶M(jìn)程程的類型型,為每個(gè)進(jìn)進(jìn)程分配配一定數(shù)數(shù)目的物物理塊,進(jìn)程如缺缺頁:只從該進(jìn)進(jìn)程在內(nèi)內(nèi)存中的的頁面中中換出一一頁,這樣不會(huì)會(huì)影響其其它進(jìn)程程;如果進(jìn)程程在運(yùn)行行其間頻頻繁發(fā)生生缺頁中中斷,則系統(tǒng)再為該進(jìn)進(jìn)程分配配若干個(gè)個(gè)附加物物理塊,直至進(jìn)程程的缺頁頁率減少少

16、到合適適為止;若進(jìn)程的的缺頁率率特別低低,可適當(dāng)減減少已分分配該進(jìn)進(jìn)程的物物理塊數(shù)數(shù)目.383、物理塊塊分配算算法在固定分分配策略略中，系系統(tǒng)在為為各個(gè)進(jìn)進(jìn)程分配配物理塊塊時(shí)，可可采?。?)、平均分分配算法法39系統(tǒng)中多多進(jìn)程頁頁面數(shù)的的總和為為：每個(gè)進(jìn)程程所能分分到的物物理塊數(shù)數(shù)bi=Si/S m，m為可用的的物理總總數(shù)。3)、考慮優(yōu)優(yōu)先權(quán)的的分配算算法2)、按比例例分配算算法，Si為某個(gè)進(jìn)進(jìn)程的頁頁面數(shù)。404.7.3調(diào)頁策略略1、何時(shí)調(diào)調(diào)入頁面面2、從何處處調(diào)入頁頁面3、頁面調(diào)調(diào)入過程程1）預(yù)調(diào)頁頁策略2）請(qǐng)求調(diào)調(diào)頁策略略用于首次次調(diào)入412、從何處處調(diào)入頁頁面(1)系統(tǒng)擁有有足夠的的對(duì)

17、換區(qū)區(qū)空間。當(dāng)缺頁時(shí)時(shí)，全部部從對(duì)換換區(qū)把所所需的頁頁面調(diào)入入內(nèi)存，使調(diào)頁頁速度提提高。要求:進(jìn)程運(yùn)行行前,把進(jìn)程相相關(guān)文件件拷入對(duì)對(duì)換區(qū)在請(qǐng)求分分頁系統(tǒng)統(tǒng)中,外存分為為兩部分分:文件區(qū)和對(duì)換區(qū)區(qū)42剛開始時(shí)時(shí)，都放放在文件件區(qū)文件區(qū)對(duì)換區(qū)不改改外存可能能被修改改不會(huì)被修修改內(nèi)存(2)系統(tǒng)缺少少足夠的的對(duì)換區(qū)區(qū)空間。43(3)UNIX方式與進(jìn)程有有關(guān)的文文件都放放在文件件區(qū)。沒沒有運(yùn)行行過的頁頁面，從從文件區(qū)區(qū)調(diào)入內(nèi)內(nèi)存；已已經(jīng)運(yùn)行行過又被被換出的的頁面，放在對(duì)對(duì)換區(qū)，下次調(diào)調(diào)入時(shí)，從對(duì)換換區(qū)調(diào)入入。文件區(qū)對(duì)換區(qū)第一次內(nèi)存外存44外存物理理塊號(hào)內(nèi)存有空空：調(diào)入入內(nèi)存不空：換換出一頁頁修改位為為

18、1，重新寫寫入外存存修改位為為0，不必寫寫入外存存將缺頁調(diào)調(diào)入內(nèi)存存修改頁表表，寫入入快表物理地址址訪問數(shù)據(jù)據(jù)3、頁面調(diào)調(diào)入過程程454.8.1最佳置換換算法和和先進(jìn)先先出算法法4.8頁面置換換算法4.8.2最近最久久未用置置換算法4.8.3CLOCK置換算法法4.8.4其他置換算法法464.8.1最佳置換換算法和和先進(jìn)先先出算法法4.8頁面置換換算法假定作業(yè)業(yè)p共計(jì)n頁，而系統(tǒng)統(tǒng)分配給給它的主主存塊只只有m塊（m,n均為正整整數(shù)，mn），即最最多只能能容納m頁。如果程序序p在運(yùn)行中中成功的的訪問次次數(shù)為s,不成功的的訪問次次數(shù)為f,那么，其其總的訪問問次數(shù)a=s+f，若定義義f =f/a，稱

19、f 為缺頁中中斷率。缺頁中斷斷率:47影響缺頁頁中斷次次數(shù)的因因素（1）分配給進(jìn)進(jìn)程的物物理頁面面數(shù)物理頁面面數(shù)多，缺頁中中斷少，反之，則缺頁頁中斷多多物理頁面面數(shù)多，進(jìn)程數(shù)數(shù)少（影影響系統(tǒng)統(tǒng)效率），反之之，則進(jìn)程數(shù)數(shù)多（缺缺頁中斷斷多）根據(jù)試驗(yàn)驗(yàn)分析：對(duì)一共共有n頁的進(jìn)程程來說，只要能能分到n/2塊內(nèi)存空間間，就可可使系統(tǒng)統(tǒng)獲得最最高效率率；（2）頁面本身身的大小小頁面大，進(jìn)程的的頁數(shù)少少，一頁頁的信息息就大，缺頁中中斷次數(shù)減少少；不同同的計(jì)算算機(jī)系統(tǒng)統(tǒng)，有不不同頁面面大?。?8例：程序序要把128128的數(shù)組初初值置“0”，數(shù)組中中每一個(gè)個(gè)元素為為一個(gè)字字，假定定頁面大大小為128個(gè)字，數(shù)

20、數(shù)組中的的每一行行元素存存放一頁頁，能供供該程序序使用的的主存塊塊只有1塊。初始始時(shí)第一一頁在內(nèi)內(nèi)存；程序編制制方法1：Forj:=1to128Fori:=1to128Aij:=0;按列：缺缺頁中斷斷次數(shù)：1281281程序編制制方法2：Fori:=1to128Forj:=1to128Aij:=0;按行：缺缺頁中斷斷次數(shù)128-1（3）程序的的編制方方法可見：缺缺頁中斷斷率與程程序的局局部化程程度密切切相關(guān)。希望編編制的程程序能經(jīng)經(jīng)常集中中在幾個(gè)個(gè)頁面上上；491,11,21,31,41,51,61,71,81,91,102,13,14,15,16,17,18,19,110,150(4)頁面淘

21、汰汰算法理論的頁頁面淘汰汰算法應(yīng)應(yīng)該選擇擇的被淘淘汰頁面面將是以后永不不使用的的，或在最最長(zhǎng)(未來)時(shí)間內(nèi)不不再被訪訪問的頁頁面。（OPT算法）。實(shí)際上，可以用用理論的的頁面淘淘汰算法法作標(biāo)準(zhǔn)，選擇其其它較好好的頁面面淘汰算算法頁面淘汰汰算法選選擇不合合適，會(huì)會(huì)使系統(tǒng)統(tǒng)“抖動(dòng)”51剛被換出出的頁很很快又被被訪問，需要重重新調(diào)入入，為此此又需再再選出一一頁調(diào)出出；而剛剛被換出出的頁，很快又又要被訪訪問，又又需把它它調(diào)入，如此頻頻繁地更更換頁面面，以致致一個(gè)進(jìn)進(jìn)程在運(yùn)運(yùn)行中，把大部部分時(shí)間間花費(fèi)在在完成頁頁面的置置換工作作上，使使得調(diào)度頁面面所需時(shí)時(shí)間比進(jìn)進(jìn)程實(shí)際際運(yùn)行的的時(shí)間還還多.我們稱該該進(jìn)

22、程發(fā)發(fā)生了“抖動(dòng)”。抖動(dòng)52最佳置換換算法是是由Relady在1966年提出的的，這種種算法選選擇的被被淘汰頁頁面，將將是永不使用用的，或或在最長(zhǎng)長(zhǎng)時(shí)間內(nèi)內(nèi)不再被被訪問的的頁面。最佳置換算法是指指對(duì)于任任意的內(nèi)內(nèi)存固定定空間m和程序p,有缺頁中中斷率最最小。它它是一個(gè)個(gè)理論上上的算法法。1、最佳置置換算法法（OPT）53假定系統(tǒng)統(tǒng)為某進(jìn)進(jìn)程分配配了三個(gè)個(gè)物理塊塊，并考考慮有以以下的頁頁面號(hào)引引用串。123456789101112131415161718192021701203042303122011710770071701423423021200230321021201170170130302

23、采用最佳佳置換算算法，只只發(fā)生了了6次頁面置置換，發(fā)發(fā)生了9次缺頁中中斷。缺缺頁率=9/21542、先進(jìn)先先出頁面面置換算算法（FIFO）這是最早早出現(xiàn)的的置換算算法，這這種算法法總是淘汰汰最先進(jìn)進(jìn)入內(nèi)存存的頁面面，選擇在在內(nèi)存中中駐留時(shí)間間最久的頁面予予以淘汰汰。55我們來看看看采用用FIFO算法進(jìn)行行頁面置置換時(shí)的的情況。7170217031024512360237430842094231002311-130131401215-18712197022070121一共發(fā)生生了12次頁面置置換，比比最佳置置換算法法多了1倍。缺頁頁率15/21=3/4，15次頁面中中斷。123456789101

24、11213141516171819202170120304230312201171056FIFO的兩個(gè)實(shí)實(shí)現(xiàn)方法法：1.在主存中中建立一一個(gè)有m(m是分配給給該作業(yè)業(yè)的存貯貯塊數(shù))個(gè)元素的的頁號(hào)表表和一個(gè)個(gè)替換指指針。Pi(i=0,1,2,m-1)指示在一一個(gè)內(nèi)存存中的頁頁面的頁頁號(hào)。替換指針針K指向進(jìn)入入主存最最老的那那一頁。每當(dāng)一頁頁新頁調(diào)調(diào)入后，執(zhí)行語語句：pk=新的頁號(hào)號(hào)；k=(k+1) modm;替換指針針指向最老老的一頁頁2451頁號(hào)號(hào)572.把進(jìn)入內(nèi)內(nèi)存的次次序建立立在存貯貯分塊表表中（該該表以塊塊號(hào)為序序，依次次登記各各塊的分分配情況況）。 0 1246 342 5657714

25、塊號(hào)頁頁號(hào)指指針2替換指針針 0 126 3422 5657714塊號(hào)頁頁號(hào)指指針6替換指針針(a)替換之前前(b)替換之后后58FIFO是根據(jù)各各個(gè)頁面面調(diào)入內(nèi)內(nèi)存的時(shí)時(shí)間來選選擇被淘淘汰頁面面，但頁面調(diào)入入的先后后并不能能反映頁頁面的使使用情況況。FIFO算法只是是在按線性順順序訪問問地址空空間才是理想想的。未考慮到到程序的的動(dòng)態(tài)特性性?？赡芤鹌甬惓?。59先進(jìn)先出出置換算算法的一一個(gè)異常常現(xiàn)象：對(duì)于一些些特定的的頁面訪訪問序列列，先進(jìn)進(jìn)先出置置換算法法有隨著著分給的的頁架數(shù)數(shù)增加，缺頁頻頻率也增增加的異異?，F(xiàn)象象。ABCDABEEECDDABCDABBBECCABCDAAABEE+頁面訪

26、問問序列ABCDABEABCDE九次缺頁頁三個(gè)頁面面ABCDDDEABCDEABCCCDEABCDABBBCDEABCAAABCDEAB+頁面訪問問序列十次缺頁頁四個(gè)頁面面604.8.2最近最久久未使用用LRU置換算法法1、LRU（LeastRecentlyUsed）算法的的描述基本思想想：基于于程序的的局部性原原理，在前面面幾條指指令中使使用頻繁繁的頁面面很可能能在后面面的幾條條指令中中頻繁使使用，反反之，已經(jīng)很久久沒有使使用的頁頁面很有有可能在在未來較較長(zhǎng)一段段時(shí)間內(nèi)內(nèi)不會(huì)使使用；因此，在缺頁頁發(fā)生時(shí)時(shí)，淘汰汰掉最久未使使用的頁；選擇淘汰汰的頁面面是最近近最久未未使用61我們用“最近的過過

27、去”來直接推推斷“最近的將將來”。770700711212003002340432024324300322132132012011701017發(fā)生了9次頁面置置換。標(biāo)明訪問問時(shí)間123456789101112131415161718192021701203042303122011710622、LRU算法的硬硬件支持持為了實(shí)現(xiàn)現(xiàn)LRU算法必須須解決：（1）一個(gè)進(jìn)進(jìn)程在內(nèi)內(nèi)存中的的各個(gè)頁頁面各有多久久時(shí)間未被被進(jìn)程訪訪問；（2）如何快快速地知知道哪一一頁是最近最久久未使用的的頁面。631、寄存器器為每個(gè)在在內(nèi)存中中的頁面面配置一一個(gè)移位寄存存器，表示為為：R=Rn-1Rn-2Rn-3R1R2R0當(dāng)

28、進(jìn)程訪訪問某物物理塊時(shí)時(shí)，要將將相應(yīng)的的寄存器器的Rn-1位置為1。定時(shí)信號(hào)號(hào)將每隔隔一定時(shí)時(shí)間將寄寄存器右移一次次，把n位寄存器器的數(shù)看看作是一一個(gè)無符符號(hào)的整整數(shù)，最最近最久久未使用用的頁面面就對(duì)應(yīng)應(yīng)著具有有最小數(shù)數(shù)值的寄寄存器。用于記錄錄某進(jìn)程程在內(nèi)存存中各頁頁的使用用情況。642、棧LRU置換算法法可用堆堆棧的方方法來實(shí)實(shí)現(xiàn)。棧中存放放當(dāng)前內(nèi)內(nèi)存中的的頁面號(hào)號(hào)，每當(dāng)當(dāng)訪問一一頁時(shí)就就調(diào)整一一次堆棧棧，總是是使最近訪訪問的那那頁的頁頁面號(hào)保保持在棧棧頂，然后根根據(jù)當(dāng)前前被訪問問時(shí)間的的近遠(yuǎn)，依次排排列，棧底總是最近近最久未未使用的的那頁的的頁面號(hào)號(hào)。淘汰65112123123421431

29、2431234215621237651241256125612561265126313276327作業(yè)固定定占用4塊主存例如，某某作業(yè)按按下列頁頁號(hào)訪問問：66作業(yè)業(yè)某程序在在內(nèi)存中中分配三三個(gè)頁面面，初始始為空，頁面走走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。請(qǐng)分別用用FIFO,LRU和OPT算法計(jì)算算缺頁中中斷次數(shù)數(shù)。674.8.3CLock置換算法法CLock算法就是是用得較較多的一一種LRU近似算法法。681、簡(jiǎn)單的的CLock置換算法法這種算法法的實(shí)質(zhì)質(zhì)是：當(dāng)當(dāng)需要置置換一頁頁時(shí)，選選擇在最最近一段段時(shí)間內(nèi)內(nèi)最久未用用的頁予以以淘汰，因此稱稱為最近未用用的算法NRU（No

30、tRecentlyUsed）。69這種近似似算法，要求為為每一頁頁設(shè)置一一位訪問問位，再再將內(nèi)存存中的所所有頁面面都通過過指針按按FIFO鏈成一個(gè)個(gè)循環(huán)隊(duì)隊(duì)列。當(dāng)某頁被被訪問時(shí)時(shí)，訪問問位由硬硬件自動(dòng)動(dòng)置“1”。我們可可以根據(jù)據(jù)訪問位位的狀態(tài)態(tài)來判斷斷各個(gè)頁頁面最近近使用的的情況。如果是是“0”，就選擇擇該頁換換出；若若為1，則重新新將它置置為0，再按照照FIFO算法檢查查下一個(gè)個(gè)頁面。該算法是是對(duì)FIFO算法的改改進(jìn)，考考慮到頁頁面是否否被訪問問。70塊號(hào)頁號(hào)訪問位指針0124034215650711替換指針針總是指向向最近被被替換的的頁所在在的存儲(chǔ)儲(chǔ)塊，缺缺頁時(shí)從從其后一一塊開始始。712

31、、改進(jìn)型型CLock置換算法法1類（A=0，M=0），最近近既未被被訪問，又未被被修改，是最佳淘汰汰頁。2類（A=0，M=1），最近近未被訪訪問，但但已被修修改，不不是很好好的淘汰汰頁。3類（A=1，M=0），最近近已被訪訪問，但但未被修修改，可可能再被被訪問。既要考慮慮到頁面面的使用用情況，還要考考慮置換換代價(jià)4類（A=1，M=1），最近近已被訪訪問且被被修改，可能再再被訪問問。根據(jù)訪問問位A和修改位位M的組合來來確定72改進(jìn)型CLock算法，執(zhí)執(zhí)行過程程可分為為以下三三步：（1）從指針針的當(dāng)前前位置開開始，掃掃描按先先進(jìn)先出出循環(huán)隊(duì)隊(duì)列，尋尋找A=0且M=0的第一類類頁面，將符合合條件的的

32、第一個(gè)個(gè)頁面作作為淘汰汰頁，在在第一次次掃描期期間A不改變。73（2）第一步步失敗，開始第第二輪掃掃描，尋尋找A=0且M=1的第二類類頁面，將符合合條件的的第一個(gè)個(gè)頁面作作為淘汰汰頁。將將所有經(jīng)經(jīng)過的頁頁面的訪訪問位置置0。（3）第二步步也失敗敗，把指指針返回回到開始始的位置置，把所有的的訪問位位A置為0，然后重復(fù)第一一步，如還是是失敗，重復(fù)第第二步，就一定定能找到到被淘汰汰的頁。74改進(jìn)型Clock算法的特特點(diǎn)該算法與與簡(jiǎn)單Clock算法比較較，可減少磁盤盤的I/O操作次數(shù)數(shù)，但為了了找到要要淘汰的的頁面，可能需需要經(jīng)過過幾輪掃掃描，使使該算法法本身的的開銷有有所增加加。754.8.4其它置

33、換換算法1、最少使使用（LeastFrequently Used）置換算算法（LFU）既可實(shí)現(xiàn)現(xiàn)LRU，也可實(shí)實(shí)現(xiàn)LFU為內(nèi)存中中的每個(gè)個(gè)頁面設(shè)設(shè)置一個(gè)個(gè)移位寄寄存器，用來記記錄頁面面被訪問問的頻率率，淘汰汰頁是最最少使用用或是訪訪問次數(shù)數(shù)最少的的頁面。ri最小的頁頁就是最最近一段段時(shí)間使使用最少少的頁面面。762、頁面緩緩沖算法法（Page BufferingAlgorithm）PBA淘汰頁面未修改修改過空閑頁面鏈表末尾已修改頁面的鏈表中末尾采用可變變分配和和局部置置換方式式，采用FIFO置換算法法實(shí)際上,頁面在內(nèi)內(nèi)存中并并不做物物理上的的移動(dòng),只是將頁頁表中的的表項(xiàng)移移到上述述鏈表;這種方

34、法法,修改或未未修改的的頁面還還在內(nèi)存存中,當(dāng)該進(jìn)程程需要再再次訪問問這些頁頁面時(shí),花費(fèi)很小小就能使使這些頁頁面返回回到進(jìn)程程中;當(dāng)被修改改的頁面面數(shù)目達(dá)達(dá)到一定定值時(shí),一起寫回回磁盤上上,從而顯著著減少磁磁盤I/O的操作次次數(shù);771、抖動(dòng)產(chǎn)產(chǎn)生的原原因和預(yù)預(yù)防方法法不適當(dāng)?shù)氐靥岣叨喽嗟莱绦蛐蚨龋徊粌H不會(huì)會(huì)提高系系統(tǒng)吞吐吐量，反反而會(huì)出出現(xiàn)“抖動(dòng)”現(xiàn)象，就就是剛被被換出頁頁很快要要被訪問問，需重重新調(diào)入入，因此此在調(diào)入入前要先先選一頁頁調(diào)出；而這個(gè)個(gè)剛被換換出的頁頁，很快快又要被被訪問，又要將將它調(diào)入入，如此此頻繁地地更換頁頁面，以以致一個(gè)個(gè)進(jìn)程在在運(yùn)行時(shí)時(shí)，把大大部分時(shí)時(shí)間花費(fèi)費(fèi)在頁面面

35、置換的的工作上上，我們們稱該進(jìn)進(jìn)程發(fā)生生了“抖動(dòng)”。性能問題題分析781、抖動(dòng)產(chǎn)產(chǎn)生的原原因調(diào)度程序序一旦發(fā)發(fā)現(xiàn)CPU的利用率率降低，就立即即提高多多道程序序度，引引入新的的進(jìn)程參參加運(yùn)行行，以提提高CPU的利用率率。當(dāng)新新進(jìn)程進(jìn)進(jìn)入內(nèi)存存時(shí)，由由于空閑物理理塊隊(duì)列列中的物物理塊都都用完了了，只能從其其它運(yùn)行行進(jìn)程處處去獲得得物理塊塊，于是是又將進(jìn)進(jìn)一步加加劇了另另外一些些進(jìn)程的的缺頁情情況，又又使等待待頁面調(diào)調(diào)入/調(diào)出的進(jìn)進(jìn)程數(shù)目目增多，這又降降低了CPU的利用率率。79那么為了了提高CPU的利用率率，調(diào)度度程序又又去引入入新的進(jìn)進(jìn)程，這這就產(chǎn)生生了惡性性循環(huán)，使缺頁頁率急劇劇地上升升。這時(shí)時(shí)候，運(yùn)運(yùn)行進(jìn)程程的大部部分時(shí)間間都用于于進(jìn)行頁頁面的換換入/換出，幾幾乎不能能完成任任何有效效的工作作，我們們稱這時(shí)時(shí)的進(jìn)程程是處于于“抖動(dòng)”狀態(tài)。80CPU利用率多道程序序度從圖中可可看出CPU的利用率率和多道道程序度度之間的關(guān)關(guān)系。開開始時(shí)，CPU的利用率率隨著程程序度的的提高而而提高，達(dá)到某某一峰值值后，如如果繼續(xù)續(xù)增加多多道程序序度，將將產(chǎn)生抖抖動(dòng)，從從而導(dǎo)致致CPU的利用率率急劇下下降。812、抖動(dòng)的的預(yù)防核心問題題:選擇合適適的頁面面置換算算法。分配給進(jìn)進(jìn)程合適適的物理理頁面數(shù)數(shù)。調(diào)整多道程序序度