存儲(chǔ)管理4虛擬存儲(chǔ)請(qǐng)求頁(yè)式管理課件

1內(nèi)存的物理組織物理地址：把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存地址（物理地址,絕對(duì)地址,實(shí)地址）,存儲(chǔ)單元占8位，稱作字節(jié)（byte）。物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維的線性空間。1內(nèi)存的物理組織物理地址：把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元2程序的邏輯結(jié)構(gòu)程序地址：用戶編程序時(shí)所用的地址（或稱邏輯地址、虛地址），基本單位可與內(nèi)存的基本單位相同，也可以不相同。程序地址空間（邏輯地址空間、虛地址空間）:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開(kāi)始的，可以是一維線性空間，也可以是多維空間。2程序的邏輯結(jié)構(gòu)程序地址：用戶編程序時(shí)所用的地址（或稱邏輯地34.6虛擬存儲(chǔ)器的基本概念4.6.1虛擬存儲(chǔ)器的引入4.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法4.6.1虛擬存儲(chǔ)器的特征34.6虛擬存儲(chǔ)器的基本概念4.6.1虛擬存儲(chǔ)器的引入4.4.6.1虛擬存儲(chǔ)器引入1.常規(guī)存儲(chǔ)器管理方式的特征2.局部性原理3.虛擬存儲(chǔ)器定義4.6.1虛擬存儲(chǔ)器引入1.常規(guī)存儲(chǔ)器管理方式的特征451.前面討論的各種存儲(chǔ)管理方法雖各有特長(zhǎng)，但有一些共同的特點(diǎn):

首先是“一次性分配”。

其次是“駐留性”。

作業(yè)全部信息，必須一次性裝入內(nèi)存作業(yè)信息一旦裝入內(nèi)存便一直駐留到作業(yè)運(yùn)行結(jié)束一方面使大作業(yè)的運(yùn)行受到限制，另一方面又影響了多道程序的實(shí)現(xiàn)。51.前面討論的各種存儲(chǔ)管理方法雖各有特長(zhǎng)，但有一些共同的特62、局部性原理

程序的局部性規(guī)律，程序往往會(huì)不均勻地高度局部化地訪問(wèn)內(nèi)存。

62、局部性原理程序的局部性規(guī)律，程序往往會(huì)不均勻地7

（1）程序在執(zhí)行時(shí)，在大多數(shù)情況下仍是順序執(zhí)行的。這種特性使得程序的執(zhí)行在一段時(shí)間內(nèi)被限制在作業(yè)的某一局部范圍。P.Denning有以下一些論點(diǎn)：

（2）過(guò)程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過(guò)程調(diào)用的深度都不超過(guò)5。

在一段時(shí)間內(nèi)，程序?qū)?huì)被局限于這些過(guò)程的范圍內(nèi)運(yùn)行。7（1）程序在執(zhí)行時(shí)，在大多數(shù)情況下仍是順序執(zhí)行的。P8

（3）程序中存在許多循環(huán)結(jié)構(gòu)，它們可以多次重復(fù)執(zhí)行。fori:=1tona[i]:=a[i]+1;（4）程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，它們往往都局限于很小的范圍內(nèi)。8（3）程序中存在許多循環(huán)結(jié)構(gòu)，它們可以多次重復(fù)執(zhí)行。9局限性的表現(xiàn)：時(shí)間，空間

（1）時(shí)間局限性

時(shí)間局限性是指最近被訪問(wèn)的存儲(chǔ)位置，很可能不久的將來(lái)還要被訪問(wèn)。

支持這種現(xiàn)象的是：

(a)循環(huán)；

(b)子程序；

(c)棧；

(d)用于計(jì)數(shù)和總計(jì)的變量。

9局限性的表現(xiàn)：時(shí)間，空間

（1）時(shí)間局限性

時(shí)間局10（2）空間局限性

空間局限性是指存儲(chǔ)訪問(wèn)有集成一組的傾向，以致一旦某個(gè)位置被訪問(wèn)到，很有可能它附近的位置也要被訪問(wèn)。

支持這種現(xiàn)象的是：

a、數(shù)組遍歷；

b、代碼的順序執(zhí)行；

c、程序員傾向于將相關(guān)的變量定義相互靠近存放。

10（2）空間局限性

空間局限性是指存儲(chǔ)訪問(wèn)有集成11

基于局部性原理，作業(yè)沒(méi)有必要全部裝入內(nèi)存。

如果計(jì)算機(jī)系統(tǒng)把輔助存儲(chǔ)器當(dāng)做主存儲(chǔ)器的擴(kuò)充，當(dāng)作業(yè)運(yùn)行時(shí)，不是將其全部信息裝入內(nèi)存，而是將必須部分先裝入內(nèi)存，其它部分仍存于輔存中。作業(yè)運(yùn)行過(guò)程中隨時(shí)把需要但又不在內(nèi)存的信息裝入內(nèi)存，把暫時(shí)不用的信息淘汰出去，以確保作業(yè)的正確運(yùn)行。

好象這個(gè)計(jì)算機(jī)系統(tǒng)向他們提供了一個(gè)容量很大的主存11基于局部性原理，作業(yè)沒(méi)有必要全部裝入內(nèi)存。123、虛擬存儲(chǔ)器的定義

所謂虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。

虛擬存儲(chǔ)器的大小受計(jì)算機(jī)系統(tǒng)地址結(jié)構(gòu)和可用外存數(shù)量的限制，與實(shí)際內(nèi)存單元的數(shù)量無(wú)關(guān)。123、虛擬存儲(chǔ)器的定義所謂虛擬存儲(chǔ)器是指134.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方式

離散分配存儲(chǔ)管理方式是實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)。

1.分頁(yè)請(qǐng)求系統(tǒng)

2.分段請(qǐng)求系統(tǒng)134.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方式離散分配存儲(chǔ)管141、頁(yè)式虛擬存儲(chǔ)系統(tǒng)

是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的分頁(yè)請(qǐng)求系統(tǒng)。141、頁(yè)式虛擬存儲(chǔ)系統(tǒng)是在分頁(yè)系統(tǒng)的基礎(chǔ)上15硬件支持：

(1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。

(2)缺頁(yè)中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

軟件支持：

(1)實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)的軟件。

(2)實(shí)現(xiàn)頁(yè)面置換的軟件。

15硬件支持：(1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。(2)缺頁(yè)中162、請(qǐng)求分段系統(tǒng)

這是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后，所形成的段式虛擬存儲(chǔ)系統(tǒng)。

162、請(qǐng)求分段系統(tǒng)這是在分段系統(tǒng)的基礎(chǔ)上，增加了17為了實(shí)現(xiàn)請(qǐng)求分段，系統(tǒng)要提供硬件支持：

(1)請(qǐng)求分段的段表機(jī)制。

(2)缺段中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

同樣地，請(qǐng)求調(diào)段和段的置換功能的實(shí)現(xiàn)也需要得到OS的支持。

17為了實(shí)現(xiàn)請(qǐng)求分段，系統(tǒng)要提供硬件支持：(1)請(qǐng)求分段184.6.3虛擬存儲(chǔ)器的特征

離散性是虛擬存儲(chǔ)器最基本的要求，虛擬性是它的最重要特征，另外虛擬存儲(chǔ)器還具有多次性和對(duì)換性。

184.6.3虛擬存儲(chǔ)器的特征離散性是虛擬存儲(chǔ)器191、離散性

離散性是指在內(nèi)存分配時(shí)采用離散分配方式。2、多次性

作業(yè)分多次裝入內(nèi)存

3、對(duì)換性→運(yùn)行時(shí)換進(jìn)換出

4、虛擬性→邏輯上擴(kuò)充內(nèi)存容量

最基本特性191、離散性2、多次性3、對(duì)換性→運(yùn)行時(shí)換進(jìn)換出204.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式

請(qǐng)求分頁(yè)存儲(chǔ)管理方式是建立在純分頁(yè)基礎(chǔ)上的.

其基本思想:在進(jìn)程開(kāi)始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面204.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方214.7.1請(qǐng)求分頁(yè)中的硬件支持

一、頁(yè)表機(jī)制

二、缺頁(yè)中斷機(jī)構(gòu)三、地址變換機(jī)構(gòu)

頁(yè)表的作用是實(shí)現(xiàn)從用戶地址空間中的邏輯地址到內(nèi)存空間的物理地址的轉(zhuǎn)換。214.7.1請(qǐng)求分頁(yè)中的硬件支持一、頁(yè)表機(jī)制22

請(qǐng)求頁(yè)式管理中對(duì)地址空間分頁(yè)，內(nèi)存分塊與基本分頁(yè)管理一樣，但對(duì)虛頁(yè)的管理是不同的。

要訪問(wèn)的頁(yè)面不在內(nèi)存中，如何發(fā)現(xiàn)和處理這種情況？這是請(qǐng)求分頁(yè)存儲(chǔ)管理要解決的兩個(gè)基本問(wèn)題22請(qǐng)求頁(yè)式管理中對(duì)地址空間分頁(yè)，內(nèi)存分塊與23

在純分頁(yè)系統(tǒng)中，頁(yè)表的內(nèi)容為：頁(yè)號(hào)物理塊號(hào)針對(duì)第一個(gè)問(wèn)題：如何發(fā)現(xiàn)要訪問(wèn)的頁(yè)面不在內(nèi)存？擴(kuò)充頁(yè)表：頁(yè)號(hào)物理塊號(hào)狀態(tài)位P外存地址23在純分頁(yè)系統(tǒng)中，頁(yè)表的內(nèi)容為：頁(yè)號(hào)物理塊號(hào)針對(duì)第一24針對(duì)第二個(gè)問(wèn)題：怎樣調(diào)入頁(yè)面？

由地址變換機(jī)構(gòu)產(chǎn)生一個(gè)缺頁(yè)中斷信號(hào)，OS進(jìn)行中斷處理后，根據(jù)該頁(yè)的外存地址把它從外存調(diào)入內(nèi)存。

引進(jìn)修改位和訪問(wèn)字段。24針對(duì)第二個(gè)問(wèn)題：怎樣調(diào)入頁(yè)面？由地址變25請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表項(xiàng)如下：

頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A

修改位M外存地址(1)狀態(tài)位（駐留位）P:該頁(yè)是在內(nèi)存還是在外存(2)訪問(wèn)字段位A：記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù);根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定）(3)修改位M:該頁(yè)調(diào)入內(nèi)存后是否在被修改過(guò)(4)外存地址:該頁(yè)在外存上的地址,通常為外存物理塊號(hào).25請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表項(xiàng)如下：頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字26

在虛擬存儲(chǔ)系統(tǒng)中，當(dāng)一個(gè)作業(yè)被編譯或經(jīng)鏈接裝配后得到的地址空間，通常存在磁盤上。頁(yè)號(hào)物理塊號(hào)保護(hù)信息外頁(yè)面表

當(dāng)一個(gè)作業(yè)被調(diào)度到而裝入內(nèi)存時(shí)，系統(tǒng)為它在內(nèi)存建立一張頁(yè)表。26在虛擬存儲(chǔ)系統(tǒng)中，當(dāng)一個(gè)作業(yè)被編譯或經(jīng)272、缺頁(yè)中斷機(jī)構(gòu)

在請(qǐng)求分頁(yè)系統(tǒng)中，當(dāng)要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，硬件發(fā)一個(gè)缺頁(yè)中斷，轉(zhuǎn)交OS處理。272、缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，當(dāng)要訪問(wèn)的頁(yè)28(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。

(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。

它跟一般的中斷有著明顯的區(qū)別：28(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。(2)一條指令29頁(yè)面654321CopyAToBB：A：29頁(yè)面654321CopyAB：A：303、地址變換機(jī)構(gòu)

請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)是以分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)為基礎(chǔ)的，還增加了產(chǎn)生缺頁(yè)中斷、處理缺頁(yè)中斷，置換等功能。303、地址變換機(jī)構(gòu)請(qǐng)求分頁(yè)系統(tǒng)中的地址變換31

在進(jìn)行地址變換時(shí)，首先去檢索快表；

如果快表中沒(méi)有這一頁(yè)的頁(yè)表項(xiàng)，再到內(nèi)存中找頁(yè)表，根據(jù)狀態(tài)位P來(lái)判斷該頁(yè)是否在內(nèi)存中。在內(nèi)存，將該頁(yè)的頁(yè)表寫入快表；快表滿時(shí)，調(diào)出某頁(yè)表項(xiàng)，再寫入該頁(yè)的頁(yè)表項(xiàng)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫回外存,否則不寫31在進(jìn)行地址變換時(shí)，首先去檢索快表；32圖4-25

這里僅僅給出一個(gè)很粗略的框圖，具體的過(guò)程是很復(fù)雜的。因?yàn)樽鳂I(yè)的副本是以文件形式存于外存上，因而要求頁(yè)面?zhèn)鬏敃r(shí)，必然要涉及到文件系統(tǒng)，此外，還得調(diào)用輸入輸出進(jìn)程。在多道程序環(huán)境下，一個(gè)作業(yè)在等待傳輸頁(yè)時(shí)，它處于被阻塞的狀態(tài)。此時(shí)，由系統(tǒng)調(diào)度另一作業(yè)運(yùn)行。當(dāng)頁(yè)面?zhèn)鬏斖瓿珊?，才把原先被阻塞的那個(gè)作業(yè)重新置成就緒狀態(tài)，但要等到再次調(diào)度到它時(shí)，才能恢復(fù)到原先中斷的地方繼續(xù)運(yùn)行下去。32圖4-25334.7.2內(nèi)存分配策略和分配算法

在為進(jìn)程分配物理塊時(shí)，又要解決三個(gè)問(wèn)題：1、保證進(jìn)程正常運(yùn)行而需要的最少物理塊數(shù)；2、進(jìn)行分配時(shí)，物理塊數(shù)目是固定的還是可變的；（分配策略）3、是采取平均分配算法還是根據(jù)進(jìn)程的大小按比例分配物理塊。334.7.2內(nèi)存分配策略和分配算法在為進(jìn)程分配物理341、最小物理塊數(shù)的確定

最小的物理塊數(shù)，是指保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。

最少物理塊數(shù)與指令的格式、功能和尋址方式有關(guān)，也就是說(shuō)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)。如:單地址指令且直接尋址系統(tǒng),至少2塊指令塊/數(shù)據(jù)塊341、最小物理塊數(shù)的確定最小的物理塊數(shù)，352、物理塊的分配策略1)、固定分配局部置換（FixedAllocation,LocalReplacement）基于進(jìn)程的類型,為每個(gè)進(jìn)程分配一定數(shù)目的物理塊(n塊),在整個(gè)運(yùn)行其間不變;如缺頁(yè):n塊中置換一頁(yè),以保證該進(jìn)程在內(nèi)存中的頁(yè)面數(shù)不變;問(wèn)題:多少個(gè)物理塊合適?物理塊太多:資源空閑.物理塊太少:頻繁中斷

采取固定和可變分配策略

352、物理塊的分配策略1)、固定分配局部置換（Fixed362)、可變分配全局置換空閑物理塊隊(duì)列先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊,OS也保持一個(gè)空閑物理塊隊(duì)列,當(dāng)進(jìn)程缺頁(yè)時(shí),由系統(tǒng)從空閑物理塊隊(duì)列取出一個(gè)物理塊分配給該進(jìn)程,并將要調(diào)入的(缺)頁(yè)裝入內(nèi)存.僅當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí),OS才從內(nèi)存中任一進(jìn)程的一頁(yè)調(diào)出.問(wèn)題:會(huì)使被調(diào)出頁(yè)的進(jìn)程缺頁(yè),進(jìn)而使缺頁(yè)率增加,影響其它進(jìn)程的執(zhí)行.362)、可變分配全局置換空閑物理塊隊(duì)列先為每個(gè)進(jìn)程分配一定373)、可變分配局部置換要求保持適當(dāng)?shù)娜表?yè)率

基于進(jìn)程的類型,為每個(gè)進(jìn)程分配一定數(shù)目的物理塊,進(jìn)程如缺頁(yè):只從該進(jìn)程在內(nèi)存中的頁(yè)面中換出一頁(yè),這樣不會(huì)影響其它進(jìn)程;如果進(jìn)程在運(yùn)行其間頻繁發(fā)生缺頁(yè)中斷,則系統(tǒng)再為該進(jìn)程分配若干個(gè)附加物理塊,直至進(jìn)程的缺頁(yè)率減少到合適為止;若進(jìn)程的缺頁(yè)率特別低,可適當(dāng)減少已分配該進(jìn)程的物理塊數(shù)目.373)、可變分配局部置換要求保持適當(dāng)?shù)娜表?yè)率基于進(jìn)程的類383、物理塊分配算法

在固定分配策略中，系統(tǒng)在為各個(gè)進(jìn)程分配物理塊時(shí)，可采取：

1)、平均分配算法

383、物理塊分配算法在固定分配策略中，系統(tǒng)在為各39

系統(tǒng)中多進(jìn)程頁(yè)面數(shù)的總和為：

每個(gè)進(jìn)程所能分到的物理塊數(shù)bi=Si/S×m，m為可用的物理總數(shù)。

3)、考慮優(yōu)先權(quán)的分配算法

2)、按比例分配算法

，Si為某個(gè)進(jìn)程的頁(yè)面數(shù)。

39系統(tǒng)中多進(jìn)程頁(yè)面數(shù)的總和為：每個(gè)進(jìn)程所能分404.7.3調(diào)頁(yè)策略1、何時(shí)調(diào)入頁(yè)面2、從何處調(diào)入頁(yè)面3、頁(yè)面調(diào)入過(guò)程1）預(yù)調(diào)頁(yè)策略2）請(qǐng)求調(diào)頁(yè)策略用于首次調(diào)入404.7.3調(diào)頁(yè)策略1、何時(shí)調(diào)入頁(yè)面1）預(yù)調(diào)頁(yè)策略2）請(qǐng)412、從何處調(diào)入頁(yè)面

(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間。

當(dāng)缺頁(yè)時(shí)，全部從對(duì)換區(qū)把所需的頁(yè)面調(diào)入內(nèi)存，使調(diào)頁(yè)速度提高。要求:進(jìn)程運(yùn)行前,把進(jìn)程相關(guān)文件拷入對(duì)換區(qū)在請(qǐng)求分頁(yè)系統(tǒng)中,外存分為兩部分:文件區(qū)和對(duì)換區(qū)412、從何處調(diào)入頁(yè)面(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間。當(dāng)42剛開(kāi)始時(shí)，都放在文件區(qū)

文件區(qū)對(duì)換區(qū)不改改外存可能被修改

不會(huì)被修改內(nèi)存(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間。

42剛開(kāi)始時(shí)，都放在文件區(qū)文件區(qū)對(duì)換區(qū)不改改外存可能被修改43(3)UNIX方式

與進(jìn)程有關(guān)的文件都放在文件區(qū)。沒(méi)有運(yùn)行過(guò)的頁(yè)面，從文件區(qū)調(diào)入內(nèi)存；已經(jīng)運(yùn)行過(guò)又被換出的頁(yè)面，放在對(duì)換區(qū)，下次調(diào)入時(shí)，從對(duì)換區(qū)調(diào)入。文件區(qū)對(duì)換區(qū)第一次內(nèi)存外存43(3)UNIX方式與進(jìn)程有關(guān)的文件都放在文件區(qū)44外存物理塊號(hào)內(nèi)存有空：調(diào)入內(nèi)存不空：換出一頁(yè)修改位為1，重新寫入外存修改位為0，不必寫入外存將缺頁(yè)調(diào)入內(nèi)存修改頁(yè)表，寫入快表物理地址訪問(wèn)數(shù)據(jù)3、頁(yè)面調(diào)入過(guò)程44外存物理塊號(hào)內(nèi)存有空：調(diào)入內(nèi)存不空：換出一頁(yè)修改位為1，454.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法4.8.2最近最久未用置換算法4.8.3CLOCK置換算法4.8.4其他置換算法454.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法464.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法

假定作業(yè)p共計(jì)n頁(yè)，而系統(tǒng)分配給它的主存塊只有m塊（m,n均為正整數(shù)，１≤m≤n），即最多只能容納m頁(yè)。如果程序p在運(yùn)行中成功的訪問(wèn)次數(shù)為s,不成功的訪問(wèn)次數(shù)為f,那么，其總的訪問(wèn)次數(shù)a=s+f，若定義f’=f/a，稱f’為缺頁(yè)中斷率。缺頁(yè)中斷率:464.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法47影響缺頁(yè)中斷次數(shù)的因素（1）分配給進(jìn)程的物理頁(yè)面數(shù)物理頁(yè)面數(shù)多，缺頁(yè)中斷少，反之，則缺頁(yè)中斷多物理頁(yè)面數(shù)多，進(jìn)程數(shù)少（影響系統(tǒng)效率），反之，則進(jìn)程數(shù)多（缺頁(yè)中斷多）根據(jù)試驗(yàn)分析：對(duì)一共有n頁(yè)的進(jìn)程來(lái)說(shuō)，只要能分到n/2塊內(nèi)存空間，就可使系統(tǒng)獲得最高效率；（2）頁(yè)面本身的大小頁(yè)面大，進(jìn)程的頁(yè)數(shù)少，一頁(yè)的信息就大，缺頁(yè)中斷次數(shù)減少；不同的計(jì)算機(jī)系統(tǒng)，有不同頁(yè)面大??；47影響缺頁(yè)中斷次數(shù)的因素（1）分配給進(jìn)程的物理頁(yè)面數(shù)（2）48例：程序要把128×128的數(shù)組初值置“0”，數(shù)組中每一個(gè)元素為一個(gè)字，假定頁(yè)面大小為128個(gè)字，數(shù)組中的每一行元素存放一頁(yè)，能供該程序使用的主存塊只有1塊。初始時(shí)第一頁(yè)在內(nèi)存；程序編制方法1：

Forj:=1to128Fori:=1to128A[i][j]:=0;按列：缺頁(yè)中斷次數(shù)：128×128－1程序編制方法2：

Fori:=1to128Forj:=1to128A[i][j]:=0;按行：缺頁(yè)中斷次數(shù)128-1（3）程序的編制方法可見(jiàn)：缺頁(yè)中斷率與程序的局部化程度密切相關(guān)。希望編制的程序能經(jīng)常集中在幾個(gè)頁(yè)面上；48例：程序要把128×128的數(shù)組初值置“0”，數(shù)組中每一491,11,21,31,41,51,61,71,81,91,102,13,14,15,16,17,18,19,110,1491,11,21,31,41,51,61,71,81,9150(4)頁(yè)面淘汰算法理論的頁(yè)面淘汰算法應(yīng)該選擇的被淘汰頁(yè)面將是以后永不使用的，或在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。（OPT算法）。實(shí)際上，可以用理論的頁(yè)面淘汰算法作標(biāo)準(zhǔn)，選擇其它較好的頁(yè)面淘汰算法頁(yè)面淘汰算法選擇不合適，會(huì)使系統(tǒng)“抖動(dòng)”50(4)頁(yè)面淘汰算法頁(yè)面淘汰算法選擇不合適，會(huì)使系51

剛被換出的頁(yè)很快又被訪問(wèn)，需要重新調(diào)入，為此又需再選出一頁(yè)調(diào)出；而剛被換出的頁(yè)，很快又要被訪問(wèn)，又需把它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中，把大部分時(shí)間花費(fèi)在完成頁(yè)面的置換工作上，使得調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多.

我們稱該進(jìn)程發(fā)生了“抖動(dòng)”。抖動(dòng)51剛被換出的頁(yè)很快又被訪問(wèn)，需要重新調(diào)入，52

最佳置換算法是由Relady在1966年提出的，這種算法選擇的被淘汰頁(yè)面，將是永不使用的，或在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。最佳置換算法是指對(duì)于任意的內(nèi)存固定空間m和程序p,有缺頁(yè)中斷率最小。它是一個(gè)理論上的算法。1、最佳置換算法（OPT）

52最佳置換算法是由Relady在1966年提出的，53

假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串。

123456789101112131415161718192021701203042303122011710770071701423423×02120×023032×10212011×701701×30302×

采用最佳置換算法，只發(fā)生了6次頁(yè)面置換，發(fā)生了9次缺頁(yè)中斷。缺頁(yè)率=9/2153假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的542、先進(jìn)先出頁(yè)面置換算法（FIFO）

這是最早出現(xiàn)的置換算法，這種算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。542、先進(jìn)先出頁(yè)面置換算法（FIFO）這是最早出55

我們來(lái)看看采用FIFO算法進(jìn)行頁(yè)面置換時(shí)的情況。

717021703102×45123×6023×7430×8420×9423×10023×11-13013×14012×15-18712×19702×20701×21一共發(fā)生了12次頁(yè)面置換，比最佳置換算法多了1倍。缺頁(yè)率15/21=3/4，15次頁(yè)面中斷。

12345678910111213141516171819202170120304230312201171055我們來(lái)看看采用FIFO算法進(jìn)行頁(yè)面置換時(shí)的情況。56FIFO的兩個(gè)實(shí)現(xiàn)方法：1.在主存中建立一個(gè)有m(m是分配給該作業(yè)的存貯塊數(shù))個(gè)元素的頁(yè)號(hào)表和一個(gè)替換指針。P[i](i=0,1,2,…,m-1)指示在一個(gè)內(nèi)存中的頁(yè)面的頁(yè)號(hào)。替換指針K指向進(jìn)入主存最老的那一頁(yè)。每當(dāng)一頁(yè)新頁(yè)調(diào)入后，執(zhí)行語(yǔ)句：

p[k]=新的頁(yè)號(hào)；

k=(k+1)modm;替換指針指向最老的一頁(yè)2451頁(yè)號(hào)56FIFO的兩個(gè)實(shí)現(xiàn)方法：替換指針指向最老的一頁(yè)2頁(yè)號(hào)572.把進(jìn)入內(nèi)存的次序建立在存貯分塊表中（該表以塊號(hào)為序，依次登記各塊的分配情況）。

01246342^5657714塊號(hào)頁(yè)號(hào)指針2替換指針

0126^

34225657714塊號(hào)頁(yè)號(hào)指針6替換指針(a)替換之前(b)替換之后572.把進(jìn)入內(nèi)存的次序建立在存貯分塊表中（該表以塊號(hào)為序，58

FIFO是根據(jù)各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間來(lái)選擇被淘汰頁(yè)面，但頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。

FIFO算法只是在按線性順序訪問(wèn)地址空間才是理想的。未考慮到程序的動(dòng)態(tài)特性?？赡芤甬惓！?8FIFO是根據(jù)各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間來(lái)選擇59先進(jìn)先出置換算法的一個(gè)異常現(xiàn)象：對(duì)于一些特定的頁(yè)面訪問(wèn)序列，先進(jìn)先出置換算法有隨著分給的頁(yè)架數(shù)增加，缺頁(yè)頻率也增加的異常現(xiàn)象。ABCDABEEECDDABCDABBBECCABCDAAABEE+++++++++

頁(yè)面訪問(wèn)序列ABCDABEABCDE九次缺頁(yè)三個(gè)頁(yè)面ABCDDDEABCDEABCCCDEABCDABBBCDEABCAAABCDEAB++++++++++

頁(yè)面訪問(wèn)序列十次缺頁(yè)四個(gè)頁(yè)面59先進(jìn)先出置換算法的一個(gè)異?，F(xiàn)象：ABC604.8.2最近最久未使用LRU置換算法

1、LRU（LeastRecentlyUsed）算法的描述

基本思想：基于程序的局部性原理，在前面幾條指令中使用頻繁的頁(yè)面很可能在后面的幾條指令中頻繁使用，反之，已經(jīng)很久沒(méi)有使用的頁(yè)面很有可能在未來(lái)較長(zhǎng)一段時(shí)間內(nèi)不會(huì)使用；因此，在缺頁(yè)發(fā)生時(shí)，淘汰掉最久未使用的頁(yè)；選擇淘汰的頁(yè)面是最近最久未使用604.8.2最近最久未使用LRU置換算法1、LRU（L61

我們用“最近的過(guò)去”來(lái)直接推斷“最近的將來(lái)”。

7707007112120×030023×4043×2024×3243×0032×213213×2012×011701017×發(fā)生了9次頁(yè)面置換。

標(biāo)明訪問(wèn)時(shí)間

12345678910111213141516171819202170120304230312201171061我們用“最近的過(guò)去”來(lái)直接推斷“最近的將來(lái)”。622、LRU算法的硬件支持為了實(shí)現(xiàn)LRU算法必須解決：（1）一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)面各有多久時(shí)間未被進(jìn)程訪問(wèn)；（2）如何快速地知道哪一頁(yè)是最近最久未使用的頁(yè)面。622、LRU算法的硬件支持為了實(shí)現(xiàn)LRU算法必須解決：631、寄存器

為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，表示為：

R=Rn-1Rn-2Rn-3…R1R2R0

當(dāng)進(jìn)程訪問(wèn)某物理塊時(shí)，要將相應(yīng)的寄存器的Rn-1位置為1。

定時(shí)信號(hào)將每隔一定時(shí)間將寄存器右移一次，把n位寄存器的數(shù)看作是一個(gè)無(wú)符號(hào)的整數(shù)，最近最久未使用的頁(yè)面就對(duì)應(yīng)著具有最小數(shù)值的寄存器。用于記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況。631、寄存器為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存642、棧

LRU置換算法可用堆棧的方法來(lái)實(shí)現(xiàn)。

棧中存放當(dāng)前內(nèi)存中的頁(yè)面號(hào)，每當(dāng)訪問(wèn)一頁(yè)時(shí)就調(diào)整一次堆棧，總是使最近訪問(wèn)的那頁(yè)的頁(yè)面號(hào)保持在棧頂，然后根據(jù)當(dāng)前被訪問(wèn)時(shí)間的近遠(yuǎn)，依次排列，棧底總是最近最久未使用的那頁(yè)的頁(yè)面號(hào)。淘汰642、棧LRU置換算法可用堆棧的方法來(lái)實(shí)現(xiàn)。651121231234214312431234215621237651241256125612561265126313276327作業(yè)固定占用4塊主存

例如，某作業(yè)按下列頁(yè)號(hào)訪問(wèn)：

65112123123421431243123421562166

作業(yè)

某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。請(qǐng)分別用FIFO,LRU和OPT算法計(jì)算缺頁(yè)中斷次數(shù)。66作674.8.3CLock置換算法

CLock算法就是用得較多的一種LRU近似算法。

674.8.3CLock置換算法CLoc681、簡(jiǎn)單的CLock置換算法

這種算法的實(shí)質(zhì)是：當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間內(nèi)最久未用的頁(yè)予以淘汰，因此稱為最近未用的算法NRU（NotRecentlyUsed）。681、簡(jiǎn)單的CLock置換算法這種算法的實(shí)質(zhì)是：69

這種近似算法，要求為每一頁(yè)設(shè)置一位訪問(wèn)位，再將內(nèi)存中的所有頁(yè)面都通過(guò)指針按FIFO鏈成一個(gè)循環(huán)隊(duì)列。

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

1類

（A=0，M=0），最近既未被訪問(wèn)，又未被修改，是最佳淘汰頁(yè)。

2類

（A=0，M=1），最近未被訪問(wèn)，但已被修改，不是很好的淘汰頁(yè)。

3類

（A=1，M=0），最近已被訪問(wèn)，但未被修改，可能再被訪問(wèn)。

既要考慮到頁(yè)面的使用情況，還要考慮置換代價(jià)

4類

（A=1，M=1），最近已被訪問(wèn)且被修改，可能再被訪問(wèn)。

根據(jù)訪問(wèn)位A和修改位M的組合來(lái)確定712、改進(jìn)型CLock置換算法1類（72改進(jìn)型CLock算法，執(zhí)行過(guò)程可分為以下三步：

（1）從指針的當(dāng)前位置開(kāi)始，掃描按先進(jìn)先出循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面，將符合條件的第一個(gè)頁(yè)面作為淘汰頁(yè)，在第一次掃描期間A不改變。72改進(jìn)型CLock算法，執(zhí)行過(guò)程可分為以下三步：（1）從73（2）第一步失敗，開(kāi)始第二輪掃描，尋找A=0且M=1的第二類頁(yè)面，將符合條件的第一個(gè)頁(yè)面作為淘汰頁(yè)。將所有經(jīng)過(guò)的頁(yè)面的訪問(wèn)位置0。（3）第二步也失敗，把指針?lè)祷氐介_(kāi)始的位置，把所有的訪問(wèn)位A置為0，然后重復(fù)第一步，如還是失敗，重復(fù)第二步，就一定能找到被淘汰的頁(yè)。73（2）第一步失敗，開(kāi)始第二輪掃描，尋找A=0且M=1的第74改進(jìn)型Clock算法的特點(diǎn)該算法與簡(jiǎn)單Clock算法比較，可減少磁盤的I/O操作次數(shù)，但為了找到要淘汰的頁(yè)面，可能需要經(jīng)過(guò)幾輪掃描，使該算法本身的開(kāi)銷有所增加。74改進(jìn)型Clock算法的特點(diǎn)該算法與簡(jiǎn)單Clock算法比754.8.4其它置換算法1、最少使用（LeastFrequentlyUsed）置換算法（LFU）既可實(shí)現(xiàn)LRU，也可實(shí)現(xiàn)LFU

為內(nèi)存中的每個(gè)頁(yè)面設(shè)置一個(gè)移位寄存器，用來(lái)記錄頁(yè)面被訪問(wèn)的頻率，淘汰頁(yè)是最少使用或是訪問(wèn)次數(shù)最少的頁(yè)面。Σri最小的頁(yè)就是最近一段時(shí)間使用最少的頁(yè)面。754.8.4其它置換算法1、最少使用（LeastFre762、頁(yè)面緩沖算法（PageBufferingAlgorithm）

PBA淘汰頁(yè)面未修改修改過(guò)空閑頁(yè)面鏈表末尾已修改頁(yè)面的鏈表中末尾采用可變分配和局部置換方式，采用FIFO置換算法

實(shí)際上,頁(yè)面在內(nèi)存中并不做物理上的移動(dòng),只是將頁(yè)表中的表項(xiàng)移到上述鏈表;這種方法,修改或未修改的頁(yè)面還在內(nèi)存中,當(dāng)該進(jìn)程需要再次訪問(wèn)這些頁(yè)面時(shí),花費(fèi)很小就能使這些頁(yè)面返回到進(jìn)程中;當(dāng)被修改的頁(yè)面數(shù)目達(dá)到一定值時(shí),一起寫回磁盤上,從而顯著減少磁盤I/O的操作次數(shù);762、頁(yè)面緩沖算法（PageBufferingAlgo771、抖動(dòng)產(chǎn)生的原因和預(yù)防方法

不適當(dāng)?shù)靥岣叨嗟莱绦蚨?，不僅不會(huì)提高系統(tǒng)吞吐量，反而會(huì)出現(xiàn)“抖動(dòng)”現(xiàn)象，就是剛被換出頁(yè)很快要被訪問(wèn)，需重新調(diào)入，因此在調(diào)入前要先選一頁(yè)調(diào)出；而這個(gè)剛被換出的頁(yè)，很快又要被訪問(wèn)，又要將它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行時(shí)，把大部分時(shí)間花費(fèi)在頁(yè)面置換的工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)”。性能問(wèn)題分析771、抖動(dòng)產(chǎn)生的原因和預(yù)防方法不適當(dāng)?shù)靥岣叨嗟莱?81、抖動(dòng)產(chǎn)生的原因

調(diào)度程序一旦發(fā)現(xiàn)CPU的利用率降低，就立即提高多道程序度，引入新的進(jìn)程參加運(yùn)行，以提高CPU的利用率。當(dāng)新進(jìn)程進(jìn)入內(nèi)存時(shí)，由于空閑物理塊隊(duì)列中的物理塊都用完了，只能從其它運(yùn)行進(jìn)程處去獲得物理塊，于是又將進(jìn)一步加劇了另外一些進(jìn)程的缺頁(yè)情況，又使等待頁(yè)面調(diào)入/調(diào)出的進(jìn)程數(shù)目增多，這又降低了CPU的利用率。781、抖動(dòng)產(chǎn)生的原因調(diào)度程序一旦發(fā)現(xiàn)CPU的利用79

那么為了提高CPU的利用率，調(diào)度程序又去引入新的進(jìn)程，這就產(chǎn)生了惡性循環(huán)，使缺頁(yè)率急劇地上升。這時(shí)候，運(yùn)行進(jìn)程的大部分時(shí)間都用于進(jìn)行頁(yè)面的換入/換出，幾乎不能完成任何有效的工作，我們稱這時(shí)的進(jìn)程是處于“抖動(dòng)”狀態(tài)。79那么為了提高CPU的利用率，調(diào)度程序又去引入新的80CPU利用率多道程序度從圖中可看出CPU的利用率和多道程序度之間的關(guān)系。開(kāi)始時(shí)，CPU的利用率隨著程序度的提高而提高，達(dá)到某一峰值后，如果繼續(xù)增加多道程序度，將產(chǎn)生抖動(dòng)，從而導(dǎo)致CPU的利用率急劇下降。80CPU利用率多道程序度從圖中可看出CPU的利用率和多道程812、抖動(dòng)的預(yù)防

核心問(wèn)題:選擇合適的頁(yè)面置換算法。分配給進(jìn)程合適的物理頁(yè)面數(shù)。調(diào)整多道程序度。1、采取局部置換策略

2、在CPU調(diào)度程序中引入工作集算法

3、掛起若干進(jìn)程

頁(yè)面淘汰算法不合理分配給進(jìn)程的物理頁(yè)面數(shù)太少812、抖動(dòng)的預(yù)防核心問(wèn)題:1、采取局部置換策略2、在C822.工作集算法從充分地共享系統(tǒng)資源這一角度出發(fā)，當(dāng)然希望主存中的作業(yè)數(shù)越多越好。但是從保證作業(yè)順利執(zhí)行、使CPU能夠有效地得到利用的角度出發(fā)，就應(yīng)該限制主存中的作業(yè)數(shù)，以避免頻繁地進(jìn)行頁(yè)面調(diào)入/調(diào)出，導(dǎo)致系統(tǒng)的抖動(dòng)。為此，P.J.Denning認(rèn)為，應(yīng)該將處理機(jī)調(diào)度和主存管理結(jié)合起來(lái)進(jìn)行考慮，并在1968年提出了工作集模型。822.工作集算法從充分地共享系統(tǒng)資源這一角度出發(fā)，當(dāng)然希望83基本思想：根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)間內(nèi)總是集中訪問(wèn)一些頁(yè)面，這些頁(yè)面稱為活躍頁(yè)面，如果分配給一個(gè)進(jìn)程的物理頁(yè)面數(shù)太少了，使該進(jìn)程所需的活躍頁(yè)面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過(guò)程中將頻繁發(fā)生中斷.

如果能為進(jìn)程提供與活躍頁(yè)面數(shù)相等的物理頁(yè)面數(shù)，則可減少缺頁(yè)中斷次數(shù)。而物理頁(yè)面數(shù)大于活躍頁(yè)面數(shù)時(shí)，再增加物理頁(yè)面分配也不能顯著減少交換的次數(shù)，這個(gè)物理頁(yè)面要求的臨界值稱為工作集。所謂工作集，就是指在某一段時(shí)間內(nèi)作業(yè)運(yùn)行所要訪問(wèn)的那些活躍頁(yè)面的集合

83基本思想：根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)84可以想象，隨著作業(yè)的執(zhí)行，工作集不斷變化，所包含的頁(yè)面數(shù)時(shí)而增多，時(shí)而減少。

通常，用W(t,△)表示從時(shí)刻t－△到時(shí)刻t之間所訪問(wèn)的不同頁(yè)面的集合，這就是作業(yè)在時(shí)刻t時(shí)的工作集。用Nw(t,△)表示工作集中所包含的頁(yè)面數(shù)。如果系統(tǒng)能隨Nw(t,△)的大小來(lái)分配主存塊的話，就既能有效的利用主存，又可以使缺頁(yè)中斷盡量少地發(fā)生。通過(guò)工作集來(lái)管理主存的分配和使用，從理論上來(lái)說(shuō)是一件非常好的事情，但工作集算法的實(shí)現(xiàn)有很多困難，目前仍然在研究和試驗(yàn)中。

84可以想象，隨著作業(yè)的執(zhí)行，工作集不斷變化，所包含的頁(yè)面數(shù)85工作集W(t,△)是二元函數(shù)，它與時(shí)間t有關(guān)，在不同時(shí)間t的工作集的大小不同，所包含的頁(yè)面數(shù)也不相同；工作集又與窗口尺寸△有關(guān)，工作集W是工作集窗口的非降函數(shù)。程序尺寸工作集85工作集W(t,△)是二元函數(shù)，它與時(shí)間t有關(guān)，在不同時(shí)間86第一個(gè)工作集工作集之間的轉(zhuǎn)換第二個(gè)工作集第三個(gè)工作集第四個(gè)工作集工作集之間的轉(zhuǎn)換工作集之間的轉(zhuǎn)換時(shí)間分配給這個(gè)進(jìn)程的內(nèi)存實(shí)頁(yè)數(shù)目工作集存儲(chǔ)管理之下的內(nèi)存分配

86第一個(gè)工作集工作集之間的轉(zhuǎn)換第二個(gè)工作集第三個(gè)工作集第四87

從第一個(gè)工作集轉(zhuǎn)換到第二個(gè)工作集，最初曲線是在第一個(gè)工作集的頁(yè)面數(shù)上升高，因?yàn)檫M(jìn)程迅速地請(qǐng)求調(diào)進(jìn)它的新工作集的頁(yè)面，一旦進(jìn)程穩(wěn)定在它的后續(xù)工作集中，系統(tǒng)在窗口中觀察到較少頁(yè)面被訪問(wèn)，就將分配給進(jìn)程內(nèi)存量減少到它的第二個(gè)工作集的頁(yè)面數(shù)。87從第一個(gè)工作集轉(zhuǎn)換到第二個(gè)工作集，最初曲線是在第88內(nèi)存的物理組織物理地址：把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存地址（物理地址,絕對(duì)地址,實(shí)地址）,存儲(chǔ)單元占8位，稱作字節(jié)（byte）。物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維的線性空間。1內(nèi)存的物理組織物理地址：把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元89程序的邏輯結(jié)構(gòu)程序地址：用戶編程序時(shí)所用的地址（或稱邏輯地址、虛地址），基本單位可與內(nèi)存的基本單位相同，也可以不相同。程序地址空間（邏輯地址空間、虛地址空間）:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開(kāi)始的，可以是一維線性空間，也可以是多維空間。2程序的邏輯結(jié)構(gòu)程序地址：用戶編程序時(shí)所用的地址（或稱邏輯地904.6虛擬存儲(chǔ)器的基本概念4.6.1虛擬存儲(chǔ)器的引入4.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法4.6.1虛擬存儲(chǔ)器的特征34.6虛擬存儲(chǔ)器的基本概念4.6.1虛擬存儲(chǔ)器的引入4.4.6.1虛擬存儲(chǔ)器引入1.常規(guī)存儲(chǔ)器管理方式的特征2.局部性原理3.虛擬存儲(chǔ)器定義4.6.1虛擬存儲(chǔ)器引入1.常規(guī)存儲(chǔ)器管理方式的特征91921.前面討論的各種存儲(chǔ)管理方法雖各有特長(zhǎng)，但有一些共同的特點(diǎn):

首先是“一次性分配”。

其次是“駐留性”。

作業(yè)全部信息，必須一次性裝入內(nèi)存作業(yè)信息一旦裝入內(nèi)存便一直駐留到作業(yè)運(yùn)行結(jié)束一方面使大作業(yè)的運(yùn)行受到限制，另一方面又影響了多道程序的實(shí)現(xiàn)。51.前面討論的各種存儲(chǔ)管理方法雖各有特長(zhǎng)，但有一些共同的特932、局部性原理

程序的局部性規(guī)律，程序往往會(huì)不均勻地高度局部化地訪問(wèn)內(nèi)存。

62、局部性原理程序的局部性規(guī)律，程序往往會(huì)不均勻地94

（1）程序在執(zhí)行時(shí)，在大多數(shù)情況下仍是順序執(zhí)行的。這種特性使得程序的執(zhí)行在一段時(shí)間內(nèi)被限制在作業(yè)的某一局部范圍。P.Denning有以下一些論點(diǎn)：

（2）過(guò)程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過(guò)程調(diào)用的深度都不超過(guò)5。

在一段時(shí)間內(nèi)，程序?qū)?huì)被局限于這些過(guò)程的范圍內(nèi)運(yùn)行。7（1）程序在執(zhí)行時(shí)，在大多數(shù)情況下仍是順序執(zhí)行的。P95

（3）程序中存在許多循環(huán)結(jié)構(gòu)，它們可以多次重復(fù)執(zhí)行。fori:=1tona[i]:=a[i]+1;（4）程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，它們往往都局限于很小的范圍內(nèi)。8（3）程序中存在許多循環(huán)結(jié)構(gòu)，它們可以多次重復(fù)執(zhí)行。96局限性的表現(xiàn)：時(shí)間，空間

（1）時(shí)間局限性

時(shí)間局限性是指最近被訪問(wèn)的存儲(chǔ)位置，很可能不久的將來(lái)還要被訪問(wèn)。

支持這種現(xiàn)象的是：

(a)循環(huán)；

(b)子程序；

(c)棧；

(d)用于計(jì)數(shù)和總計(jì)的變量。

9局限性的表現(xiàn)：時(shí)間，空間

（1）時(shí)間局限性

時(shí)間局97（2）空間局限性

空間局限性是指存儲(chǔ)訪問(wèn)有集成一組的傾向，以致一旦某個(gè)位置被訪問(wèn)到，很有可能它附近的位置也要被訪問(wèn)。

支持這種現(xiàn)象的是：

a、數(shù)組遍歷；

b、代碼的順序執(zhí)行；

c、程序員傾向于將相關(guān)的變量定義相互靠近存放。

10（2）空間局限性

空間局限性是指存儲(chǔ)訪問(wèn)有集成98

基于局部性原理，作業(yè)沒(méi)有必要全部裝入內(nèi)存。

如果計(jì)算機(jī)系統(tǒng)把輔助存儲(chǔ)器當(dāng)做主存儲(chǔ)器的擴(kuò)充，當(dāng)作業(yè)運(yùn)行時(shí)，不是將其全部信息裝入內(nèi)存，而是將必須部分先裝入內(nèi)存，其它部分仍存于輔存中。作業(yè)運(yùn)行過(guò)程中隨時(shí)把需要但又不在內(nèi)存的信息裝入內(nèi)存，把暫時(shí)不用的信息淘汰出去，以確保作業(yè)的正確運(yùn)行。

好象這個(gè)計(jì)算機(jī)系統(tǒng)向他們提供了一個(gè)容量很大的主存11基于局部性原理，作業(yè)沒(méi)有必要全部裝入內(nèi)存。993、虛擬存儲(chǔ)器的定義

所謂虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。

虛擬存儲(chǔ)器的大小受計(jì)算機(jī)系統(tǒng)地址結(jié)構(gòu)和可用外存數(shù)量的限制，與實(shí)際內(nèi)存單元的數(shù)量無(wú)關(guān)。123、虛擬存儲(chǔ)器的定義所謂虛擬存儲(chǔ)器是指1004.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方式

離散分配存儲(chǔ)管理方式是實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)。

1.分頁(yè)請(qǐng)求系統(tǒng)

2.分段請(qǐng)求系統(tǒng)134.6.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方式離散分配存儲(chǔ)管1011、頁(yè)式虛擬存儲(chǔ)系統(tǒng)

是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的分頁(yè)請(qǐng)求系統(tǒng)。141、頁(yè)式虛擬存儲(chǔ)系統(tǒng)是在分頁(yè)系統(tǒng)的基礎(chǔ)上102硬件支持：

(1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。

(2)缺頁(yè)中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

軟件支持：

(1)實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)的軟件。

(2)實(shí)現(xiàn)頁(yè)面置換的軟件。

15硬件支持：(1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。(2)缺頁(yè)中1032、請(qǐng)求分段系統(tǒng)

這是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后，所形成的段式虛擬存儲(chǔ)系統(tǒng)。

162、請(qǐng)求分段系統(tǒng)這是在分段系統(tǒng)的基礎(chǔ)上，增加了104為了實(shí)現(xiàn)請(qǐng)求分段，系統(tǒng)要提供硬件支持：

(1)請(qǐng)求分段的段表機(jī)制。

(2)缺段中斷機(jī)構(gòu)。

(3)地址變換機(jī)構(gòu)。

同樣地，請(qǐng)求調(diào)段和段的置換功能的實(shí)現(xiàn)也需要得到OS的支持。

17為了實(shí)現(xiàn)請(qǐng)求分段，系統(tǒng)要提供硬件支持：(1)請(qǐng)求分段1054.6.3虛擬存儲(chǔ)器的特征

離散性是虛擬存儲(chǔ)器最基本的要求，虛擬性是它的最重要特征，另外虛擬存儲(chǔ)器還具有多次性和對(duì)換性。

184.6.3虛擬存儲(chǔ)器的特征離散性是虛擬存儲(chǔ)器1061、離散性

離散性是指在內(nèi)存分配時(shí)采用離散分配方式。2、多次性

作業(yè)分多次裝入內(nèi)存

3、對(duì)換性→運(yùn)行時(shí)換進(jìn)換出

4、虛擬性→邏輯上擴(kuò)充內(nèi)存容量

最基本特性191、離散性2、多次性3、對(duì)換性→運(yùn)行時(shí)換進(jìn)換出1074.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式

請(qǐng)求分頁(yè)存儲(chǔ)管理方式是建立在純分頁(yè)基礎(chǔ)上的.

其基本思想:在進(jìn)程開(kāi)始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面204.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方1084.7.1請(qǐng)求分頁(yè)中的硬件支持

一、頁(yè)表機(jī)制

二、缺頁(yè)中斷機(jī)構(gòu)三、地址變換機(jī)構(gòu)

頁(yè)表的作用是實(shí)現(xiàn)從用戶地址空間中的邏輯地址到內(nèi)存空間的物理地址的轉(zhuǎn)換。214.7.1請(qǐng)求分頁(yè)中的硬件支持一、頁(yè)表機(jī)制109

請(qǐng)求頁(yè)式管理中對(duì)地址空間分頁(yè)，內(nèi)存分塊與基本分頁(yè)管理一樣，但對(duì)虛頁(yè)的管理是不同的。

要訪問(wèn)的頁(yè)面不在內(nèi)存中，如何發(fā)現(xiàn)和處理這種情況？這是請(qǐng)求分頁(yè)存儲(chǔ)管理要解決的兩個(gè)基本問(wèn)題22請(qǐng)求頁(yè)式管理中對(duì)地址空間分頁(yè)，內(nèi)存分塊與110

在純分頁(yè)系統(tǒng)中，頁(yè)表的內(nèi)容為：頁(yè)號(hào)物理塊號(hào)針對(duì)第一個(gè)問(wèn)題：如何發(fā)現(xiàn)要訪問(wèn)的頁(yè)面不在內(nèi)存？擴(kuò)充頁(yè)表：頁(yè)號(hào)物理塊號(hào)狀態(tài)位P外存地址23在純分頁(yè)系統(tǒng)中，頁(yè)表的內(nèi)容為：頁(yè)號(hào)物理塊號(hào)針對(duì)第一111針對(duì)第二個(gè)問(wèn)題：怎樣調(diào)入頁(yè)面？

由地址變換機(jī)構(gòu)產(chǎn)生一個(gè)缺頁(yè)中斷信號(hào)，OS進(jìn)行中斷處理后，根據(jù)該頁(yè)的外存地址把它從外存調(diào)入內(nèi)存。

引進(jìn)修改位和訪問(wèn)字段。24針對(duì)第二個(gè)問(wèn)題：怎樣調(diào)入頁(yè)面？由地址變112請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表項(xiàng)如下：

頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A

修改位M外存地址(1)狀態(tài)位（駐留位）P:該頁(yè)是在內(nèi)存還是在外存(2)訪問(wèn)字段位A：記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù);根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定）(3)修改位M:該頁(yè)調(diào)入內(nèi)存后是否在被修改過(guò)(4)外存地址:該頁(yè)在外存上的地址,通常為外存物理塊號(hào).25請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表項(xiàng)如下：頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字113

在虛擬存儲(chǔ)系統(tǒng)中，當(dāng)一個(gè)作業(yè)被編譯或經(jīng)鏈接裝配后得到的地址空間，通常存在磁盤上。頁(yè)號(hào)物理塊號(hào)保護(hù)信息外頁(yè)面表

當(dāng)一個(gè)作業(yè)被調(diào)度到而裝入內(nèi)存時(shí)，系統(tǒng)為它在內(nèi)存建立一張頁(yè)表。26在虛擬存儲(chǔ)系統(tǒng)中，當(dāng)一個(gè)作業(yè)被編譯或經(jīng)1142、缺頁(yè)中斷機(jī)構(gòu)

在請(qǐng)求分頁(yè)系統(tǒng)中，當(dāng)要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，硬件發(fā)一個(gè)缺頁(yè)中斷，轉(zhuǎn)交OS處理。272、缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，當(dāng)要訪問(wèn)的頁(yè)115(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。

(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。

它跟一般的中斷有著明顯的區(qū)別：28(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。(2)一條指令116頁(yè)面654321CopyAToBB：A：29頁(yè)面654321CopyAB：A：1173、地址變換機(jī)構(gòu)

請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)是以分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)為基礎(chǔ)的，還增加了產(chǎn)生缺頁(yè)中斷、處理缺頁(yè)中斷，置換等功能。303、地址變換機(jī)構(gòu)請(qǐng)求分頁(yè)系統(tǒng)中的地址變換118

在進(jìn)行地址變換時(shí)，首先去檢索快表；

如果快表中沒(méi)有這一頁(yè)的頁(yè)表項(xiàng)，再到內(nèi)存中找頁(yè)表，根據(jù)狀態(tài)位P來(lái)判斷該頁(yè)是否在內(nèi)存中。在內(nèi)存，將該頁(yè)的頁(yè)表寫入快表；快表滿時(shí)，調(diào)出某頁(yè)表項(xiàng)，再寫入該頁(yè)的頁(yè)表項(xiàng)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫回外存,否則不寫31在進(jìn)行地址變換時(shí)，首先去檢索快表；119圖4-25

這里僅僅給出一個(gè)很粗略的框圖，具體的過(guò)程是很復(fù)雜的。因?yàn)樽鳂I(yè)的副本是以文件形式存于外存上，因而要求頁(yè)面?zhèn)鬏敃r(shí)，必然要涉及到文件系統(tǒng)，此外，還得調(diào)用輸入輸出進(jìn)程。在多道程序環(huán)境下，一個(gè)作業(yè)在等待傳輸頁(yè)時(shí)，它處于被阻塞的狀態(tài)。此時(shí)，由系統(tǒng)調(diào)度另一作業(yè)運(yùn)行。當(dāng)頁(yè)面?zhèn)鬏斖瓿珊螅虐言缺蛔枞哪莻€(gè)作業(yè)重新置成就緒狀態(tài)，但要等到再次調(diào)度到它時(shí)，才能恢復(fù)到原先中斷的地方繼續(xù)運(yùn)行下去。32圖4-251204.7.2內(nèi)存分配策略和分配算法

在為進(jìn)程分配物理塊時(shí)，又要解決三個(gè)問(wèn)題：1、保證進(jìn)程正常運(yùn)行而需要的最少物理塊數(shù)；2、進(jìn)行分配時(shí)，物理塊數(shù)目是固定的還是可變的；（分配策略）3、是采取平均分配算法還是根據(jù)進(jìn)程的大小按比例分配物理塊。334.7.2內(nèi)存分配策略和分配算法在為進(jìn)程分配物理1211、最小物理塊數(shù)的確定

最小的物理塊數(shù)，是指保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。

最少物理塊數(shù)與指令的格式、功能和尋址方式有關(guān)，也就是說(shuō)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)。如:單地址指令且直接尋址系統(tǒng),至少2塊指令塊/數(shù)據(jù)塊341、最小物理塊數(shù)的確定最小的物理塊數(shù)，1222、物理塊的分配策略1)、固定分配局部置換（FixedAllocation,LocalReplacement）基于進(jìn)程的類型,為每個(gè)進(jìn)程分配一定數(shù)目的物理塊(n塊),在整個(gè)運(yùn)行其間不變;如缺頁(yè):n塊中置換一頁(yè),以保證該進(jìn)程在內(nèi)存中的頁(yè)面數(shù)不變;問(wèn)題:多少個(gè)物理塊合適?物理塊太多:資源空閑.物理塊太少:頻繁中斷

采取固定和可變分配策略

352、物理塊的分配策略1)、固定分配局部置換（Fixed1232)、可變分配全局置換空閑物理塊隊(duì)列先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊,OS也保持一個(gè)空閑物理塊隊(duì)列,當(dāng)進(jìn)程缺頁(yè)時(shí),由系統(tǒng)從空閑物理塊隊(duì)列取出一個(gè)物理塊分配給該進(jìn)程,并將要調(diào)入的(缺)頁(yè)裝入內(nèi)存.僅當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí),OS才從內(nèi)存中任一進(jìn)程的一頁(yè)調(diào)出.問(wèn)題:會(huì)使被調(diào)出頁(yè)的進(jìn)程缺頁(yè),進(jìn)而使缺頁(yè)率增加,影響其它進(jìn)程的執(zhí)行.362)、可變分配全局置換空閑物理塊隊(duì)列先為每個(gè)進(jìn)程分配一定1243)、可變分配局部置換要求保持適當(dāng)?shù)娜表?yè)率

基于進(jìn)程的類型,為每個(gè)進(jìn)程分配一定數(shù)目的物理塊,進(jìn)程如缺頁(yè):只從該進(jìn)程在內(nèi)存中的頁(yè)面中換出一頁(yè),這樣不會(huì)影響其它進(jìn)程;如果進(jìn)程在運(yùn)行其間頻繁發(fā)生缺頁(yè)中斷,則系統(tǒng)再為該進(jìn)程分配若干個(gè)附加物理塊,直至進(jìn)程的缺頁(yè)率減少到合適為止;若進(jìn)程的缺頁(yè)率特別低,可適當(dāng)減少已分配該進(jìn)程的物理塊數(shù)目.373)、可變分配局部置換要求保持適當(dāng)?shù)娜表?yè)率基于進(jìn)程的類1253、物理塊分配算法

在固定分配策略中，系統(tǒng)在為各個(gè)進(jìn)程分配物理塊時(shí)，可采?。?/p>

1)、平均分配算法

383、物理塊分配算法在固定分配策略中，系統(tǒng)在為各126

系統(tǒng)中多進(jìn)程頁(yè)面數(shù)的總和為：

每個(gè)進(jìn)程所能分到的物理塊數(shù)bi=Si/S×m，m為可用的物理總數(shù)。

3)、考慮優(yōu)先權(quán)的分配算法

2)、按比例分配算法

，Si為某個(gè)進(jìn)程的頁(yè)面數(shù)。

39系統(tǒng)中多進(jìn)程頁(yè)面數(shù)的總和為：每個(gè)進(jìn)程所能分1274.7.3調(diào)頁(yè)策略1、何時(shí)調(diào)入頁(yè)面2、從何處調(diào)入頁(yè)面3、頁(yè)面調(diào)入過(guò)程1）預(yù)調(diào)頁(yè)策略2）請(qǐng)求調(diào)頁(yè)策略用于首次調(diào)入404.7.3調(diào)頁(yè)策略1、何時(shí)調(diào)入頁(yè)面1）預(yù)調(diào)頁(yè)策略2）請(qǐng)1282、從何處調(diào)入頁(yè)面

(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間。

當(dāng)缺頁(yè)時(shí)，全部從對(duì)換區(qū)把所需的頁(yè)面調(diào)入內(nèi)存，使調(diào)頁(yè)速度提高。要求:進(jìn)程運(yùn)行前,把進(jìn)程相關(guān)文件拷入對(duì)換區(qū)在請(qǐng)求分頁(yè)系統(tǒng)中,外存分為兩部分:文件區(qū)和對(duì)換區(qū)412、從何處調(diào)入頁(yè)面(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間。當(dāng)129剛開(kāi)始時(shí)，都放在文件區(qū)

文件區(qū)對(duì)換區(qū)不改改外存可能被修改

不會(huì)被修改內(nèi)存(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間。

42剛開(kāi)始時(shí)，都放在文件區(qū)文件區(qū)對(duì)換區(qū)不改改外存可能被修改130(3)UNIX方式

與進(jìn)程有關(guān)的文件都放在文件區(qū)。沒(méi)有運(yùn)行過(guò)的頁(yè)面，從文件區(qū)調(diào)入內(nèi)存；已經(jīng)運(yùn)行過(guò)又被換出的頁(yè)面，放在對(duì)換區(qū)，下次調(diào)入時(shí)，從對(duì)換區(qū)調(diào)入。文件區(qū)對(duì)換區(qū)第一次內(nèi)存外存43(3)UNIX方式與進(jìn)程有關(guān)的文件都放在文件區(qū)131外存物理塊號(hào)內(nèi)存有空：調(diào)入內(nèi)存不空：換出一頁(yè)修改位為1，重新寫入外存修改位為0，不必寫入外存將缺頁(yè)調(diào)入內(nèi)存修改頁(yè)表，寫入快表物理地址訪問(wèn)數(shù)據(jù)3、頁(yè)面調(diào)入過(guò)程44外存物理塊號(hào)內(nèi)存有空：調(diào)入內(nèi)存不空：換出一頁(yè)修改位為1，1324.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法4.8.2最近最久未用置換算法4.8.3CLOCK置換算法4.8.4其他置換算法454.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法1334.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法

假定作業(yè)p共計(jì)n頁(yè)，而系統(tǒng)分配給它的主存塊只有m塊（m,n均為正整數(shù)，１≤m≤n），即最多只能容納m頁(yè)。如果程序p在運(yùn)行中成功的訪問(wèn)次數(shù)為s,不成功的訪問(wèn)次數(shù)為f,那么，其總的訪問(wèn)次數(shù)a=s+f，若定義f’=f/a，稱f’為缺頁(yè)中斷率。缺頁(yè)中斷率:464.8.1最佳置換算法和先進(jìn)先出算法4.8頁(yè)面置換算法134影響缺頁(yè)中斷次數(shù)的因素（1）分配給進(jìn)程的物理頁(yè)面數(shù)物理頁(yè)面數(shù)多，缺頁(yè)中斷少，反之，則缺頁(yè)中斷多物理頁(yè)面數(shù)多，進(jìn)程數(shù)少（影響系統(tǒng)效率），反之，則進(jìn)程數(shù)多（缺頁(yè)中斷多）根據(jù)試驗(yàn)分析：對(duì)一共有n頁(yè)的進(jìn)程來(lái)說(shuō)，只要能分到n/2塊內(nèi)存空間，就可使系統(tǒng)獲得最高效率；（2）頁(yè)面本身的大小頁(yè)面大，進(jìn)程的頁(yè)數(shù)少，一頁(yè)的信息就大，缺頁(yè)中斷次數(shù)減少；不同的計(jì)算機(jī)系統(tǒng)，有不同頁(yè)面大?。?7影響缺頁(yè)中斷次數(shù)的因素（1）分配給進(jìn)程的物理頁(yè)面數(shù)（2）135例：程序要把128×128的數(shù)組初值置“0”，數(shù)組中每一個(gè)元素為一個(gè)字，假定頁(yè)面大小為128個(gè)字，數(shù)組中的每一行元素存放一頁(yè)，能供該程序使用的主存塊只有1塊。初始時(shí)第一頁(yè)在內(nèi)存；程序編制方法1：

Forj:=1to128Fori:=1to128A[i][j]:=0;按列：缺頁(yè)中斷次數(shù)：128×128－1程序編制方法2：

Fori:=1to128Forj:=1to128A[i][j]:=0;按行：缺頁(yè)中斷次數(shù)128-1（3）程序的編制方法可見(jiàn)：缺頁(yè)中斷率與程序的局部化程度密切相關(guān)。希望編制的程序能經(jīng)常集中在幾個(gè)頁(yè)面上；48例：程序要把128×128的數(shù)組初值置“0”，數(shù)組中每一1361,11,21,31,41,51,61,71,81,91,102,13,14,15,16,17,18,19,110,1491,11,21,31,41,51,61,71,81,91137(4)頁(yè)面淘汰算法理論的頁(yè)面淘汰算法應(yīng)該選擇的被淘汰頁(yè)面將是以后永不使用的，或在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。（OPT算法）。實(shí)際上，可以用理論的頁(yè)面淘汰算法作標(biāo)準(zhǔn)，選擇其它較好的頁(yè)面淘汰算法頁(yè)面淘汰算法選擇不合適，會(huì)使系統(tǒng)“抖動(dòng)”50(4)頁(yè)面淘汰算法頁(yè)面淘汰算法選擇不合適，會(huì)使系138

剛被換出的頁(yè)很快又被訪問(wèn)，需要重新調(diào)入，為此又需再選出一頁(yè)調(diào)出；而剛被換出的頁(yè)，很快又要被訪問(wèn)，又需把它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中，把大部分時(shí)間花費(fèi)在完成頁(yè)面的置換工作上，使得調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多.

我們稱該進(jìn)程發(fā)生了“抖動(dòng)”。抖動(dòng)51剛被換出的頁(yè)很快又被訪問(wèn)，需要重新調(diào)入，139

最佳置換算法是由Relady在1966年提出的，這種算法選擇的被淘汰頁(yè)面，將是永不使用的，或在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。最佳置換算法是指對(duì)于任意的內(nèi)存固定空間m和程序p,有缺頁(yè)中斷率最小。它是一個(gè)理論上的算法。1、最佳置換算法（OPT）

52最佳置換算法是由Relady在1966年提出的，140

假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串。

123456789101112131415161718192021701203042303122011710770071701423423×02120×023032×10212011×701701×30302×

采用最佳置換算法，只發(fā)生了6次頁(yè)面置換，發(fā)生了9次缺頁(yè)中斷。缺頁(yè)率=9/2153假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的1412、先進(jìn)先出頁(yè)面置換算法（FIFO）

這是最早出現(xiàn)的置換算法，這種算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。542、先進(jìn)先出頁(yè)面置換算法（FIFO）這是最早出142

我們來(lái)看看采用FIFO算法進(jìn)行頁(yè)面置換時(shí)的情況。

717021703102×45123×6023×7430×8420×9423×10023×11-13013×14012×15-18712×19702×20701×21一共發(fā)生了12次頁(yè)面置換，比最佳置換算法多了1倍。缺頁(yè)率15/21=3/4，15次頁(yè)面中斷。

12345678910111213141516171819202170120304230312201171055我們來(lái)看看采用FIFO算法進(jìn)行頁(yè)面置換時(shí)的情況。143FIFO的兩個(gè)實(shí)現(xiàn)方法：1.在主存中建立一個(gè)有m(m是分配給該作業(yè)的存貯塊數(shù))個(gè)元素的頁(yè)號(hào)表和一個(gè)替換指針。P[i](i=0,1,2,…,m-1)指示在一個(gè)內(nèi)存中的頁(yè)面的頁(yè)號(hào)。替換指針K指向進(jìn)入主存最老的那一頁(yè)。每當(dāng)一頁(yè)新頁(yè)調(diào)入后，執(zhí)行語(yǔ)句：

p[k]=新的頁(yè)號(hào)；

k=(k+1)modm;替換指針指向最老的一頁(yè)2451頁(yè)號(hào)56FIFO的兩個(gè)實(shí)現(xiàn)方法：替換指針指向最老的一頁(yè)2頁(yè)號(hào)1442.把進(jìn)入內(nèi)存的次序建立在存貯分塊表中（該表以塊號(hào)為序，依次登記各塊的分配情況）。

01246342^5657714塊號(hào)頁(yè)號(hào)指針2替換指針

0126^

34225657714塊號(hào)頁(yè)號(hào)指針6替換指針(a)替換之前(b)替換之后572.把進(jìn)入內(nèi)存的次序建立在存貯分塊表中（該表以塊號(hào)為序，145

FIFO是根據(jù)各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間來(lái)選擇被淘汰頁(yè)面，但頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。

FIFO算法只是在按線性順序訪問(wèn)地址空間才是理想的。未考慮到程序的動(dòng)態(tài)特性?？赡芤甬惓?。58FIFO是根據(jù)各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間來(lái)選擇146先進(jìn)先出置換算法的一個(gè)異?，F(xiàn)象：對(duì)于一些特定的頁(yè)面訪問(wèn)序列，先進(jìn)先出置換算法有隨著分給的頁(yè)架數(shù)增加，缺頁(yè)頻率也增加的異?，F(xiàn)象。ABCDABEEECDDABCDABBBECCABCDAAABEE+++++++++

頁(yè)面訪問(wèn)序列ABCDABEABCDE九次缺頁(yè)三個(gè)頁(yè)面ABCDDDEABCDEABCCCDEABCDABBBCDEABCAAABCDEAB++++++++++

頁(yè)面訪問(wèn)序列十次缺頁(yè)四個(gè)頁(yè)面59先進(jìn)先出置換算法的一個(gè)異?，F(xiàn)象：ABC1474.8.2最近最久未使用LRU置換算法

1、LRU（LeastRecentlyUsed）算法的描述

基本思想：基于程序的局部性原理，在前面幾條指令中使用頻繁的頁(yè)面很可能在后面的幾條指令中頻繁使用，反之，已經(jīng)很久沒(méi)有使用的頁(yè)面很有可能在未來(lái)較長(zhǎng)一段時(shí)間內(nèi)不會(huì)使用；因此，在缺頁(yè)發(fā)生時(shí)，淘汰掉最久未使用的頁(yè)；選擇淘汰的頁(yè)面是最近最久未使用604.8.2最近最久未使用LRU置換算法1、LRU（L148

我們用“最近的過(guò)去”來(lái)直接推斷“最近的將來(lái)”。

7707007112120×030023×4043×2024×