學習目標理解并掌握請求分頁存儲管理系統(tǒng)中的硬件支持理解請求分頁存儲管理系統(tǒng)中的內存分配策略和分配算法掌握主要頁面置換算法1§4.7請求分頁存儲管理方式請求分頁存儲管理的基本思想請求分頁存儲管理方式是實現(xiàn)虛擬存儲器的一種常用技術；基本思想：在進程開始運行之前，僅裝入當前要執(zhí)行的部分頁面即可運行；在執(zhí)行過程中，可使用請求調入中斷動態(tài)裝入要訪問但又不在內存的頁面；當內存空間已滿，而又需要裝入新的頁面時，者根據置換功能適當調出某個頁面，以便騰出空間而裝入新的頁面。為了實現(xiàn)頁式虛存，系統(tǒng)需要解決下面三個問題：

1）系統(tǒng)如何感知進程當前所需頁面不在主存（頁表機制）；

2）當發(fā)現(xiàn)缺頁時，如何把所缺頁面調入主存（缺頁中斷機構）；

3）在置換頁面時，根據什么策略選擇欲淘汰的頁面（置換算法）。24.7.1請求分頁的硬件支持狀態(tài)位（中斷位）：標識該頁是否在內存（0或1）；訪問位：標識該頁面的近來的訪問次數(shù)或時間（換出）；修改位：標識此頁是否在內存中被修改過；外存地址：記錄該頁面在外存上的地址，即(外存而非內存的)物理塊號。頁號狀態(tài)位物理塊號外存地址訪問位修改位1、頁表機制3

程序在執(zhí)行時，首先檢查頁表，當狀態(tài)位指示該頁不在主存時，則引起一個缺頁中斷發(fā)生，其中斷執(zhí)行過程與一般中斷相同：保護現(xiàn)場（CPU環(huán)境）；中斷處理（中斷處理程序裝入頁面）；恢復現(xiàn)場，返回斷點繼續(xù)執(zhí)行。2.缺頁中斷機構4缺頁中斷與一般中斷的不同點：一般中斷是一條指令完成后檢查是否有中斷缺頁中斷是在指令執(zhí)行期間產生和處理中斷，一條指令執(zhí)行時可能產生多個缺頁中斷(如指令可能訪問多個內存地址，這些地址在不同的頁中)。相應的中斷處理程序把控制轉向缺頁中斷子程序。執(zhí)行此子程序，即把所缺頁面裝入主存。然后處理機重新執(zhí)行缺頁時打斷的指令。這時，就將順利形成物理地址。缺頁中斷的處理過程是由硬件和軟件共同實現(xiàn)的。5缺頁中斷引發(fā)的連續(xù)中斷674.7.2內存分配策略和分配算法

1．最小物理塊數(shù)的確定這里所說的最小物理塊數(shù)，是指能保證進程正常運行所需的最小物理塊數(shù)。當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。進程應獲得的最少物理塊數(shù)與計算機的硬件結構有關，取決于指令的格式、功能和尋址方式。8

2．物理塊的分配策略

1)固定分配局部置換(FixedAllocation，LocalReplacement)

為每個進程分配一定數(shù)目的物理塊，在整個運行期間都不再改變。采用該策略時，如果進程在運行中發(fā)現(xiàn)缺頁，則只能從該進程在內存的n個頁面中選出一個頁換出，然后再調入一頁，以保證分配給該進程的內存空間不變。實現(xiàn)這種策略的困難在于：應為每個進程分配多少個物理塊難以確定。若太少，會頻繁地出現(xiàn)缺頁中斷，降低了系統(tǒng)的吞吐量；若太多，又必然使內存中駐留的進程數(shù)目減少，進而可能造成CPU空閑或其它資源空閑的情況，而且在實現(xiàn)進程對換時，會花費更多的時間。

9

2)可變分配全局置換(VariableAllocation，GlobalReplacement)這可能是最易于實現(xiàn)的一種物理塊分配和置換策略，已用于若干個OS中。在采用這種策略時，先為系統(tǒng)中的每個進程分配一定數(shù)目的物理塊，而OS自身也保持一個空閑物理塊隊列。當某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中取出一個物理塊分配給該進程，并將欲調入的(缺)頁裝入其中。這樣，凡產生缺頁(中斷)的進程，都將獲得新的物理塊。僅當空閑物理塊隊列中的物理塊用完時，OS才能從內存中選擇一頁調出，該頁可能是系統(tǒng)中任一進程的頁，這樣，自然又會使那個進程的物理塊減少，進而使其缺頁率增加。

10

3)可變分配局部置換(VariableAllocation，LocalReplacement)

為每個進程分配一定數(shù)目的物理塊，但當某進程發(fā)現(xiàn)缺頁時，只允許從該進程在內存的頁面中選出一頁換出，這樣就不會影響其它進程的運行。如果進程在運行中頻繁地發(fā)生缺頁中斷，則系統(tǒng)須再為該進程分配若干附加的物理塊，直至該進程的缺頁率減少到適當程度為止；反之，若一個進程在運行過程中的缺頁率特別低，則此時可適當減少分配給該進程的物理塊數(shù)，但不應引起其缺頁率的明顯增加。

11

3．物理塊分配算法

1)平均分配算法這是將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程。例如，當系統(tǒng)中有100個物理塊，有5個進程在運行時，每個進程可分得20個物理塊。這種方式貌似公平，但實際上是不公平的，因為它未考慮到各進程本身的大小。如有一個進程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進程只有10頁，卻有10個物理塊閑置未用。

12

2)按比例分配算法這是根據進程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中各進程頁面數(shù)的總和為：

又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi，將有：b應該取整，它必須大于最小物理塊數(shù)。

13

3)考慮優(yōu)先權的分配算法在實際應用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應為它分配較多的內存空間。通常采取的方法是把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據各進程的優(yōu)先權，適當?shù)卦黾悠湎鄳蓊~后，分配給各進程。在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權來為各進程分配其物理塊的。

144.7.3調頁策略

1．調入頁面的時機

1)預調頁策略如果進程的許多頁是存放在外存的一個連續(xù)區(qū)域中，則一次調入若干個相鄰的頁，會比一次調入一頁更高效些。但如果調入的一批頁面中的大多數(shù)都未被訪問，則又是低效的?？刹捎靡环N以預測為基礎的預調頁策略，將那些預計在不久之后便會被訪問的頁面預先調入內存。如果預測較準確，那么，這種策略顯然是很有吸引力的。但遺憾的是，目前預調頁的成功率僅約50%。故這種策略主要用于進程的首次調入時，由程序員指出應該先調入哪些頁。

15

2)請求調頁策略當進程在運行中需要訪問某部分程序和數(shù)據時，若發(fā)現(xiàn)其所在的頁面不在內存，便立即提出請求，由OS將其所需頁面調入內存。由請求調頁策略所確定調入的頁，是一定會被訪問的，再加之請求調頁策略比較易于實現(xiàn)，故在目前的虛擬存儲器中大多采用此策略。但這種策略每次僅調入一頁，故須花費較大的系統(tǒng)開銷，增加了磁盤I/O的啟動頻率。

162、從何處調入請求分頁系統(tǒng)中把外存分成兩部分：一是文件區(qū)，用于存放文件；二是對換區(qū)（swap），用于存放對換頁面。當發(fā)生換頁時，從缺的頁從何處調入通常有3種實現(xiàn)：（1）全部從對換區(qū)調入。這要求系統(tǒng)有足夠的對換區(qū)空間，進程裝入時全部復制到對換區(qū)（2）只將修改過的頁放在對換區(qū)。適合對換區(qū)空間小的情形（3）首次從文件區(qū)調入，運行后所有換出的頁面都放在對換區(qū)，以后再次調入是從對換區(qū)調入。Unix系統(tǒng)采用此方式。17§4.8頁面置換算法4.8.1最佳置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。實現(xiàn):無法實現(xiàn)，對衡量其他算法有理論上的指導意義，實際上無法實現(xiàn)（需要能看見未來！）。假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

18192.先進先出(FIFO)頁面置換算法

FIFO算法是最早出現(xiàn)的頁面置換算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存中停留時間最長（年齡最老）的一頁予以淘汰

。實現(xiàn)時可以引入一個替換指針指向最老的頁面置換次數(shù)？缺頁中斷次數(shù)？算法名稱、思想及實現(xiàn)是關鍵！20

為了說明FIFO頁面置換算法相關的可能問題，考慮一下引用串：1，2，3，4，1，2，5，1，2，3，4，5。注意到對4個可用內存塊的缺頁次數(shù)（10）比3個內存塊的缺頁次數(shù)（9）還要大。這種令人難以相信的結果稱為Belady異?，F(xiàn)象，即缺頁次數(shù)隨內存塊增加而增加。213.最近最久未使用(LRU)置換算法

最近最久未使用置換算是用過去的引用串的情況來預測將要到來的引用串的情況（以“最近的過去”作為“不久將來”的近似），選擇過去的最近一段時間內最久沒有使用的頁面淘汰掉。它的實質是：當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰。222.LRU置換算法的硬件支持1)寄存器為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為R=Rn-1Rn-2Rn-3…R2R1R0

LRU算法實現(xiàn)時需要為每個頁面設置一個時間項，用來記錄該頁面上次被訪問的時間，每次將時間數(shù)值最小的頁面淘汰掉。23圖4-28某進程具有8個頁面時的LRU訪問情況242)棧：棧頂始終存放最新被訪問的頁面，而棧底則存放最近最久未訪問的頁面圖4-29用棧保存當前使用頁面時棧的變化情況25LRU近似算法要完全實現(xiàn)LRU算法是一件十分困難的事情。因為要找出最近最久未被使用的頁面的話，就必須對每一個頁面都設置有關的訪問記錄項，而且每一次訪問都必須更新這些記錄。這顯然要花費巨大的系統(tǒng)開銷（包括硬件開銷和時間開銷）。因此，在實際系統(tǒng)中往往使用LRU的近似算法，包括NRU（最近未使用）算法和LFU（最少使用）算法。

26NRU算法——Clock置換算法

NRU（NotRecentlyUsed）：最近未使用頁面淘汰算法該算法在需要淘汰某一頁時，從那些最近一個時期內未被訪問的頁中任選一頁淘汰。只要在頁表中增設一個訪問位即可實現(xiàn)。當某頁被訪問時，訪問位置1。否則，訪問位置O。系統(tǒng)周期性地對所有引用位清零。當需淘汰一頁時，從那些訪問位為零的頁中選一頁進行淘汰。

274.8.3Clock置換算法1.簡單的Clock置換算法圖4-31簡單Clock置換算法的流程和示例又稱為二次機會算法、NRU最近未使用算法實現(xiàn)：需要構建循環(huán)隊列，引入一個查找指針282.改進型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。29

其執(zhí)行過程可分成以下三步：

(1)從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。

(2)如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。

(3)如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復0。然后重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。304.7.4其它置換算法最少使用(LFU：LeastFrequentlyUsed)置換算法：該算法在需要淘汰某一頁時，首先淘汰到當前時間為止，被訪問次數(shù)最少的那一頁。這只要在頁表中給每一頁增設一個訪問計數(shù)器即可實現(xiàn)。每當該頁被訪問時，訪問計數(shù)器加1，而發(fā)生一次缺頁中斷時，則淘汰計數(shù)值最小的那一頁，并將所有的計數(shù)器清零。

31在虛存中，頁面在內存與外存之間頻繁調度，以至于調度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動。