計(jì)算機(jī)操作系統(tǒng)第四版第5章虛擬存儲(chǔ)器

1、第五章 虛擬存儲(chǔ)器 第五章第五章 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 5.1虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.3頁(yè)面置換算法頁(yè)面置換算法5.4 “抖動(dòng)抖動(dòng)”與工作集與工作集5.5請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式第五章 虛擬存儲(chǔ)器 常規(guī)存儲(chǔ)器管理方式的特征：常規(guī)存儲(chǔ)器管理方式的特征： 一次性作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。 駐留性作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。 上述特征，使許多在程序運(yùn)行中不用或暫不用的程序(數(shù)據(jù))占據(jù)了大量的內(nèi)存空間，使得一些需要運(yùn)行的作業(yè)無(wú)法裝入運(yùn)行。5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述第五章 虛擬

2、存儲(chǔ)器 1968年，Denning. P提出局部性原理局部性原理：程序在執(zhí)行時(shí)呈現(xiàn)出局部性規(guī)律，即在一較短時(shí)間內(nèi)，程序的執(zhí)行僅限于某個(gè)部分，相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。(論點(diǎn)見P154) 局部性又表現(xiàn)為時(shí)間局部性和空間局部性。v時(shí)間局部性是指如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行。如果某數(shù)據(jù)被訪問(wèn)，則不久以后該數(shù)據(jù)可能再次被訪問(wèn)。(循環(huán))v空間局部性是指一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問(wèn)。(程序的順序執(zhí)行) 5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述局部性原理局部性原理第五章 虛擬存儲(chǔ)器 基于程序局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒(méi)有

3、必要全部裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段先裝入內(nèi)存，就可以啟動(dòng)運(yùn)行。這樣就可以使一個(gè)較大的程序在較小的內(nèi)存空間中運(yùn)行，同時(shí)還可以裝入更多的程序并發(fā)執(zhí)行。從用戶角度來(lái)看，該系統(tǒng)所具有的內(nèi)存容量比實(shí)際內(nèi)存容量大得多。通常把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。 所謂虛擬存儲(chǔ)器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)管理系統(tǒng)。它具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充。其邏輯容量取決于內(nèi)存與外存的容量之和。其運(yùn)行速度接近于內(nèi)存，而其每位的成本卻接近于外存。5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述第五章 虛擬存儲(chǔ)器 v 多次性指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行。是虛擬存儲(chǔ)器最重要的

4、特征。v 對(duì)換性指允許在作業(yè)的運(yùn)行過(guò)程中進(jìn)行換進(jìn)、換出。v 虛擬性指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶看到的容量遠(yuǎn)大于實(shí)際內(nèi)存容量。5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征第五章 虛擬存儲(chǔ)器 1、分頁(yè)請(qǐng)求系統(tǒng)（請(qǐng)求分頁(yè)存儲(chǔ)管理方式）在基本分頁(yè)系統(tǒng)的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。 當(dāng)一個(gè)用戶程序要調(diào)入內(nèi)存時(shí)，不是將該程序全部裝入內(nèi)存，而是只裝入部分頁(yè)到內(nèi)存，就可啟動(dòng)程序運(yùn)行。在運(yùn)行的過(guò)程中，如果發(fā)現(xiàn)要運(yùn)行的程序或要訪問(wèn)數(shù)據(jù)不在內(nèi)存，則向系統(tǒng)發(fā)出缺頁(yè)中斷請(qǐng)求缺頁(yè)中斷請(qǐng)求，系統(tǒng)在處理這個(gè)中斷時(shí)，將外存中相應(yīng)的頁(yè)調(diào)入內(nèi)存，該程序繼續(xù)運(yùn)行。當(dāng)一

5、些頁(yè)調(diào)入內(nèi)存時(shí)，若內(nèi)存沒(méi)有空閑空間，則利用頁(yè)面置換功能頁(yè)面置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)面換出到外存上，再將這些要訪問(wèn)的頁(yè)調(diào)入內(nèi)存，該程序繼續(xù)運(yùn)行。 硬件支持：硬件支持：請(qǐng)求頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)、地址變換機(jī)構(gòu) 軟件支持：軟件支持：實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能的軟件2、請(qǐng)求分段系統(tǒng)（請(qǐng)求分段存儲(chǔ)管理方式）類似于請(qǐng)求分頁(yè)，以段為單位進(jìn)行請(qǐng)求和置換。5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法第五章 虛擬存儲(chǔ)器 頁(yè)號(hào) 物理塊號(hào)狀態(tài)位P 訪問(wèn)字段A 修改位M 外存地址 頁(yè)表機(jī)制頁(yè)表中除了有頁(yè)號(hào)、物理塊號(hào)兩項(xiàng)外，還需要狀態(tài)位、訪問(wèn)字段、修改位、外存地址等信息。狀態(tài)位指

6、示該頁(yè)是否已調(diào)入內(nèi)存。訪問(wèn)字段記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)或本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問(wèn)。供選擇換出頁(yè)面時(shí)參考。修改位表示該頁(yè)調(diào)入內(nèi)存后是否被修改過(guò)。外存地址指示該頁(yè)在外存的地址。5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式(頁(yè)式虛擬存儲(chǔ)管理頁(yè)式虛擬存儲(chǔ)管理)5.2.1 硬件支持硬件支持 請(qǐng)求頁(yè)表機(jī)制第五章 虛擬存儲(chǔ)器 缺頁(yè)中斷機(jī)構(gòu)每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)將所缺的頁(yè)面調(diào)入內(nèi)存。5.2.1 硬件支持硬件支持缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷與一般中斷的區(qū)別，在于在指令的執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而且一條指令執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷（如: copy A to B

7、 ）。缺頁(yè)中斷的處理過(guò)程是，保留CPU現(xiàn)場(chǎng)，分析中斷原因，轉(zhuǎn)入缺頁(yè)中斷處理程序進(jìn)行處理；從外存中找到缺的頁(yè)面；若內(nèi)存已滿，則選擇一頁(yè)換出；從外存讀入缺頁(yè)，寫入內(nèi)存，修改頁(yè)表；中斷處理完成，恢復(fù)CPU現(xiàn)場(chǎng)。 第五章 虛擬存儲(chǔ)器 地址變換機(jī)構(gòu)(見P158圖5-2)（在基本分頁(yè)系統(tǒng)具有快表的地址變換機(jī)構(gòu)的基礎(chǔ)上增加缺頁(yè)處理功能）在進(jìn)行地址變換時(shí)，首先檢索快表。若找到，則直接用快表中給出的物理塊號(hào)與邏輯地址中的頁(yè)內(nèi)地址形成物理地址。若未找到，則應(yīng)去內(nèi)存中查找頁(yè)表(慢表)，將有兩種可能。 (1)若該頁(yè)已調(diào)入內(nèi)存，此時(shí)則應(yīng)將該頁(yè)的頁(yè)表項(xiàng)寫人快表(快表滿時(shí)，調(diào)出一個(gè)頁(yè)表項(xiàng)，然后寫入)，用頁(yè)表中給出的物理塊號(hào)

8、與邏輯地址中的頁(yè)內(nèi)地址形成物理地址； (2)若該頁(yè)未調(diào)入內(nèi)存，則產(chǎn)生缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)從外存中調(diào)入。 5.2.1 硬件支持硬件支持地址變換機(jī)構(gòu)第五章 虛擬存儲(chǔ)器 在為進(jìn)程分配內(nèi)存時(shí)，涉及到三個(gè)問(wèn)題：最小物理塊數(shù)的確定(2)內(nèi)存分配策略(3)物理塊的分配算法5.2.2 請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配第五章 虛擬存儲(chǔ)器 最小物理塊數(shù)能保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。 當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。 它與計(jì)算機(jī)硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。 5.2.2 請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配最小物理塊數(shù)的確定最小物理塊數(shù)的確定第五章 虛擬

9、存儲(chǔ)器 分配策略可以是固定分配和可變分配。分配策略可以是固定分配和可變分配。 固定分配固定分配:為每個(gè)進(jìn)程分配一組固定數(shù)目的物理塊，在進(jìn)程運(yùn)行期間不再改變。 可變分配可變分配：先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，在進(jìn)程運(yùn)行期間可根據(jù)情況根據(jù)情況做適當(dāng)?shù)脑黾踊驕p少。 置換策略可以是全局置換和局部置換。置換策略可以是全局置換和局部置換。 局部置換局部置換:進(jìn)程在運(yùn)行過(guò)程中發(fā)生缺頁(yè)時(shí)，只能從當(dāng)前缺頁(yè)進(jìn)程當(dāng)前缺頁(yè)進(jìn)程在內(nèi)存的頁(yè)面在內(nèi)存的頁(yè)面中選出一頁(yè)進(jìn)行淘汰，然后再調(diào)入所缺頁(yè)面。 全局置換全局置換：進(jìn)程在運(yùn)行過(guò)程中發(fā)生缺頁(yè)時(shí)，由OS從系統(tǒng)管理的空閑物理塊隊(duì)列中取出一塊分配給該進(jìn)程。當(dāng)空閑物理塊隊(duì)列中的物

10、理塊用完時(shí)，OS從系統(tǒng)中任一進(jìn)程中選出一頁(yè)系統(tǒng)中任一進(jìn)程中選出一頁(yè)進(jìn)行淘汰，然后再調(diào)入所缺頁(yè)面。（以所有進(jìn)程的全部物理塊為選擇目標(biāo)）（以所有進(jìn)程的全部物理塊為選擇目標(biāo)）5.2.2 請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配內(nèi)存分配策略內(nèi)存分配策略第五章 虛擬存儲(chǔ)器 分配策略和置換策略可以組合出三種內(nèi)存分配內(nèi)存分配策略策略： 固定分配局部置換固定分配局部置換:為每個(gè)進(jìn)程分配一組固定數(shù)目的物理塊，在進(jìn)程運(yùn)行期間不再改變。進(jìn)程在運(yùn)行過(guò)程中發(fā)生缺頁(yè)時(shí)，只能從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)進(jìn)行淘汰。 可變分配全局置換可變分配全局置換：先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，在進(jìn)程運(yùn)行期間可根據(jù)情況做適當(dāng)?shù)脑黾踊驕p

11、少。進(jìn)程在運(yùn)行過(guò)程中發(fā)生缺頁(yè)時(shí)，由系統(tǒng)從管理的空閑物理塊隊(duì)列中取出一塊分配給該進(jìn)程。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才從系統(tǒng)中任一進(jìn)程中選出一頁(yè)進(jìn)行淘汰。 可變分配局部置換可變分配局部置換：先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊。進(jìn)程在運(yùn)行過(guò)程中發(fā)生缺頁(yè)時(shí)，從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)進(jìn)行淘汰。但如果進(jìn)程在運(yùn)行過(guò)程中缺頁(yè)頻繁，系統(tǒng)將再為該進(jìn)程但如果進(jìn)程在運(yùn)行過(guò)程中缺頁(yè)頻繁，系統(tǒng)將再為該進(jìn)程分配若干附加的空閑物理塊，直到該進(jìn)程的缺頁(yè)率減少到適當(dāng)程分配若干附加的空閑物理塊，直到該進(jìn)程的缺頁(yè)率減少到適當(dāng)程度為止。反之，若進(jìn)程在運(yùn)行過(guò)程中的缺頁(yè)率特別低，則系統(tǒng)可度為止。反之，若進(jìn)程在運(yùn)行過(guò)程中的缺頁(yè)

12、率特別低，則系統(tǒng)可適當(dāng)減少分配給該進(jìn)程的物理塊。適當(dāng)減少分配給該進(jìn)程的物理塊。 5.2.2 請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配內(nèi)存分配策略內(nèi)存分配策略第五章 虛擬存儲(chǔ)器 在采用固定分配策略時(shí)，物理塊分配算法有： 平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。 按比例分配算法：根據(jù)進(jìn)程的大小按比例分配物理塊。 考慮優(yōu)先權(quán)的分配算法：將系統(tǒng)中所有可供分配的物理塊分成兩部分：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)進(jìn)行分配，適當(dāng)?shù)卦黾痈邇?yōu)先權(quán)進(jìn)程的內(nèi)存份額。5.2.2 請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配物理塊的分配算法物理塊的分配算法第五章 虛擬存儲(chǔ)器 1

13、、何時(shí)調(diào)入所需頁(yè)面2、從何處調(diào)入所需頁(yè)面3、如何調(diào)入所需頁(yè)面5.2.3 頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略 第五章 虛擬存儲(chǔ)器 1 1、預(yù)調(diào)頁(yè)策略、預(yù)調(diào)頁(yè)策略 系統(tǒng)根據(jù)作業(yè)系統(tǒng)根據(jù)作業(yè)( (進(jìn)程進(jìn)程) )運(yùn)行的情況，預(yù)測(cè)哪些頁(yè)面將要在不久之運(yùn)行的情況，預(yù)測(cè)哪些頁(yè)面將要在不久之后被訪問(wèn)，在其被訪問(wèn)之前預(yù)先調(diào)入內(nèi)存，這樣在程序運(yùn)行的過(guò)后被訪問(wèn)，在其被訪問(wèn)之前預(yù)先調(diào)入內(nèi)存，這樣在程序運(yùn)行的過(guò)程中就不會(huì)出現(xiàn)缺頁(yè)中斷。程中就不會(huì)出現(xiàn)缺頁(yè)中斷。 這樣方法與預(yù)測(cè)準(zhǔn)確度有關(guān)。從表面上看起來(lái)很好，但系統(tǒng)很這樣方法與預(yù)測(cè)準(zhǔn)確度有關(guān)。從表面上看起來(lái)很好，但系統(tǒng)很難準(zhǔn)確預(yù)測(cè)作業(yè)的運(yùn)行情況，難以實(shí)現(xiàn)。目前預(yù)調(diào)頁(yè)的成功率僅難準(zhǔn)確預(yù)

14、測(cè)作業(yè)的運(yùn)行情況，難以實(shí)現(xiàn)。目前預(yù)調(diào)頁(yè)的成功率僅約約50%50%。2 2、請(qǐng)求調(diào)頁(yè)策略、請(qǐng)求調(diào)頁(yè)策略 進(jìn)程在執(zhí)行的過(guò)程中，發(fā)現(xiàn)要執(zhí)行的程序或處理的數(shù)據(jù)所在的頁(yè)面不在內(nèi)存，向系統(tǒng)提出調(diào)入相應(yīng)頁(yè)面的請(qǐng)求，系統(tǒng)響應(yīng)用戶的請(qǐng)求，將其所需頁(yè)面調(diào)入內(nèi)存。 這種方法所確定調(diào)入的頁(yè)面是一定會(huì)被訪問(wèn)的，易于實(shí)現(xiàn)。目這種方法所確定調(diào)入的頁(yè)面是一定會(huì)被訪問(wèn)的，易于實(shí)現(xiàn)。目前虛擬存儲(chǔ)器大多采用此策略。前虛擬存儲(chǔ)器大多采用此策略。5.2.3 頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略 何時(shí)調(diào)入頁(yè)面第五章 虛擬存儲(chǔ)器 在具有對(duì)換功能的OS中，通常把外存分為文件區(qū)和對(duì)換區(qū)。文件區(qū)用于存放文件，采取離散分配方式；對(duì)換區(qū)用于存放從內(nèi)存換出的進(jìn)程

15、頁(yè)面，采取連續(xù)分配方式。 從何處調(diào)入頁(yè)面可分成三種情況：1、全部從對(duì)換區(qū)調(diào)入所需頁(yè)面 （在進(jìn)程運(yùn)行之前，將與該進(jìn)程有關(guān)的文件從文件區(qū)拷貝到對(duì)換區(qū)）2、凡是不會(huì)被修改的文件，直接從文件區(qū)調(diào)入；對(duì)于那些可能被修改的部分，在將它們換出時(shí)調(diào)到對(duì)換區(qū)，以后需要時(shí)從對(duì)換區(qū)調(diào)入。3、UNIX方式 凡是未運(yùn)行過(guò)的頁(yè)面，從文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，從對(duì)換區(qū)調(diào)入。5.2.3 頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略 從何處調(diào)入頁(yè)面第五章 虛擬存儲(chǔ)器 每當(dāng)程序所要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)（狀態(tài)位為“0”），便向CPU發(fā)出缺頁(yè)中斷請(qǐng)求，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺頁(yè)中斷處理程序。缺頁(yè)中斷處理程序

16、通過(guò)查找頁(yè)表得到該頁(yè)在外存的物理塊后， 如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O，將所缺頁(yè)面調(diào)入內(nèi)存，然后修改頁(yè)表，將此表項(xiàng)寫入快表中。 如果此時(shí)內(nèi)存已滿，則須先按照某種置換算法，從內(nèi)存中選出一頁(yè)準(zhǔn)備換出: 如果該頁(yè)未被修改過(guò)（修改位為“0”），可不必將該頁(yè)寫回磁盤； 但如果該頁(yè)已被修改（修改位為“1”），則必須將它寫回磁盤，然后再把所缺頁(yè)面調(diào)入內(nèi)存，并修改頁(yè)表，且將此表項(xiàng)寫入快表中。在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表形成所要訪問(wèn)的物理地址，再去訪問(wèn)內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過(guò)程對(duì)用戶是透明的。5.2.3 頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略 如何調(diào)入所需頁(yè)面（頁(yè)面調(diào)入過(guò)程）第五章 虛擬存儲(chǔ)器 假定程序p共

17、有n頁(yè)，而系統(tǒng)分配給它的內(nèi)存只有m塊(1mn),訪問(wèn)的頁(yè)在內(nèi)存，稱訪問(wèn)成功，否則為訪問(wèn)失敗。設(shè)A:頁(yè)面訪問(wèn)的總次數(shù) S:頁(yè)面訪問(wèn)成功的次數(shù) F:頁(yè)面訪問(wèn)失敗的次數(shù)，則： A = S + F 缺頁(yè)率 f = F/A 5.2.3 頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略缺頁(yè)率缺頁(yè)率第五章 虛擬存儲(chǔ)器 當(dāng)進(jìn)程運(yùn)行過(guò)程中，如果發(fā)現(xiàn)要訪問(wèn)的頁(yè)面不在內(nèi)存而需要把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出(淘汰掉)一頁(yè)程序或數(shù)據(jù)，送入外存對(duì)換區(qū)中。用來(lái)選擇淘汰頁(yè)面的規(guī)則叫做頁(yè)面置換算法。 最佳（OPT）置換算法(理想置換算法) 先進(jìn)先出(FIFO)頁(yè)面置換算法 最近最久未使用(LRU)

18、置換算法5.3 頁(yè)面置換算法頁(yè)面置換算法第五章 虛擬存儲(chǔ)器 基本思想：選擇永不使用或在未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面予以替換。該算法無(wú)法實(shí)現(xiàn)，只能作為其他算法的衡量標(biāo)準(zhǔn)。例：假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系統(tǒng)分配給該作業(yè)的物理塊數(shù)為3。 缺頁(yè)中斷率為：f=F/A=9/20=45% 5.3 頁(yè)面置換算法頁(yè)面置換算法最佳置換算法最佳置換算法(理想置換算法理想置換算法OPT)第五章 虛擬存儲(chǔ)器 基本思想：選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以替換。例：假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?，0，1，2，0，3，0，4，2，3，0，3，2，1，

19、2，0，1，7，0，1。系統(tǒng)分配給該作業(yè)的物理塊數(shù)為3。缺頁(yè)中斷率為：f=F/A=15/20=75% 5.3 頁(yè)面置換算法頁(yè)面置換算法先進(jìn)先出先進(jìn)先出(FIFO)頁(yè)面替換算法頁(yè)面替換算法 第五章 虛擬存儲(chǔ)器 基本思想：選擇過(guò)去最長(zhǎng)時(shí)間未被訪問(wèn)的頁(yè)面予以替換。 例：假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系統(tǒng)分配給該作業(yè)的物理塊數(shù)為3。缺頁(yè)中斷率為：f=F/A=12/20=60% 5.3 頁(yè)面置換算法頁(yè)面置換算法最近最久未使用最近最久未使用(LRU)置換算法置換算法第五章 虛擬存儲(chǔ)器 在請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，可能會(huì)出現(xiàn)這樣的現(xiàn)象，

20、即對(duì)于剛被替換出去的頁(yè)，可能馬上又要被訪問(wèn)，需要將它調(diào)入，因無(wú)空閑內(nèi)存又要替換另一頁(yè)，而后者可能是即將被訪問(wèn)的頁(yè)。于是造成了系統(tǒng)需花費(fèi)大量的時(shí)間忙于進(jìn)行這種頻繁的頁(yè)面交換，致使系統(tǒng)的實(shí)際效率很低，嚴(yán)重時(shí)導(dǎo)致系統(tǒng)癱瘓。這種現(xiàn)象稱為抖動(dòng)現(xiàn)象抖動(dòng)現(xiàn)象。 防止抖動(dòng)現(xiàn)象可以有多種辦法，例如，采取局部替換策略、引入工作集算法、掛起若干進(jìn)程等。 所謂工作集工作集是指在某段時(shí)間間隔里，進(jìn)程實(shí)際要訪問(wèn)的頁(yè)面的集合。引入虛擬存儲(chǔ)器后，雖然程序只須有少量的內(nèi)存就可以運(yùn)行，但為了使程序有效運(yùn)行，較少產(chǎn)生缺頁(yè)，就必須使程序的工作集全部在內(nèi)存中。 5.4 抖動(dòng)與工作集抖動(dòng)與工作集第五章 虛擬存儲(chǔ)器 段表中除了有段號(hào)、段長(zhǎng)、段的基址三項(xiàng)外，還需要存取方式、訪問(wèn)字段、修改位、存在位、增補(bǔ)位、外存起始地址等信息。 段號(hào) 段長(zhǎng) 段的基址 存取方式 訪問(wèn)字段 修改位 存在位 增補(bǔ)位 外存始址 5.5 請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式(段式虛擬存儲(chǔ)管理段式虛擬存儲(chǔ)管理) 請(qǐng)求分段中的硬件支持請(qǐng)求分段中的硬件支持一段表機(jī)制第五章 虛擬存儲(chǔ)器 與缺頁(yè)中斷類似，每當(dāng)所要訪問(wèn)的段不在內(nèi)存時(shí)，便要產(chǎn)生缺