第5章虛擬存儲器

1、5 5 虛擬存儲器管理虛擬存儲器管理n前面介紹的分區(qū)（固定分區(qū)和可變分區(qū)）存儲前面介紹的分區(qū)（固定分區(qū)和可變分區(qū)）存儲管理和分頁、分段存儲管理技術(shù)，都要求作業(yè)管理和分頁、分段存儲管理技術(shù)，都要求作業(yè)在執(zhí)行之前必須將其全部信息裝入內(nèi)存，并且在執(zhí)行之前必須將其全部信息裝入內(nèi)存，并且作業(yè)的邏輯地址空間不能比內(nèi)存空間大，否則作業(yè)的邏輯地址空間不能比內(nèi)存空間大，否則該作業(yè)就無法裝入內(nèi)存。該作業(yè)就無法裝入內(nèi)存。n為了解決大作業(yè)與小內(nèi)存的矛盾，人們采用了為了解決大作業(yè)與小內(nèi)存的矛盾，人們采用了虛擬存儲管理技術(shù)虛擬存儲管理技術(shù)，對內(nèi)存在邏輯上進(jìn)行擴(kuò)充。，對內(nèi)存在邏輯上進(jìn)行擴(kuò)充。5 5 虛擬存儲器虛擬存儲器n基

2、本實(shí)現(xiàn)思想基本實(shí)現(xiàn)思想n技術(shù)支持技術(shù)支持n內(nèi)存物理頁面分配方式內(nèi)存物理頁面分配方式n調(diào)頁策略調(diào)頁策略n缺頁中斷的處理過程缺頁中斷的處理過程n頁面置換算法頁面置換算法5 5 虛擬存儲器管理虛擬存儲器管理n 引入：常規(guī)方式下引入：常規(guī)方式下“一次性一次性”和和“駐留性駐留性” 依據(jù)：程序局部性依據(jù)：程序局部性 含義：虛擬存儲器含義：虛擬存儲器 特征：多次性、對換性、虛擬性特征：多次性、對換性、虛擬性 實(shí)現(xiàn)方法：虛擬頁式、虛擬段式、虛擬段頁式實(shí)現(xiàn)方法：虛擬頁式、虛擬段式、虛擬段頁式局部性原理：局部性原理：n程序在執(zhí)行時(shí)將呈現(xiàn)局部性規(guī)律，即在一較短程序在執(zhí)行時(shí)將呈現(xiàn)局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序

3、的執(zhí)行僅局限于某個(gè)部分，它的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，它所訪問的存儲空間也局限于某個(gè)區(qū)域。所訪問的存儲空間也局限于某個(gè)區(qū)域。n局限性又表現(xiàn)在下述兩個(gè)方面：局限性又表現(xiàn)在下述兩個(gè)方面：時(shí)間局部性時(shí)間局部性和和空間局部性空間局部性局部性原理：局部性原理：n時(shí)間局部性：時(shí)間局部性：如果程序中的某條指令一旦執(zhí)行，如果程序中的某條指令一旦執(zhí)行，則不久以后該可能再次執(zhí)行；如果某數(shù)據(jù)被訪則不久以后該可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因是程序中存在著大量生時(shí)間局限性的典型原因是程序中存在著大量的循環(huán)操作。的

4、循環(huán)操作。n空間局部性：空間局部性：一旦程序訪問了某個(gè)存儲單元，一旦程序訪問了某個(gè)存儲單元，則不久后，其附近的存儲單元也將被訪問，即則不久后，其附近的存儲單元也將被訪問，即程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一定的范圍內(nèi)，其典型情況是程序的順序執(zhí)行。定的范圍內(nèi)，其典型情況是程序的順序執(zhí)行。5.15.1虛擬存儲器的概念虛擬存儲器的概念n基于程序的局部性考慮，就沒有必要把一個(gè)作基于程序的局部性考慮，就沒有必要把一個(gè)作業(yè)全部都調(diào)入內(nèi)存再執(zhí)行，而只需把當(dāng)前運(yùn)行業(yè)全部都調(diào)入內(nèi)存再執(zhí)行，而只需把當(dāng)前運(yùn)行所需要的信息放入內(nèi)存，其余根據(jù)需要，所需要的信息放入內(nèi)存，其余

5、根據(jù)需要，由操由操作系統(tǒng)和硬件配合來完成主存和輔存之間信息作系統(tǒng)和硬件配合來完成主存和輔存之間信息的調(diào)度。的調(diào)度。n這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)比實(shí)這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)比實(shí)際容量大得多的一個(gè)內(nèi)存，稱為際容量大得多的一個(gè)內(nèi)存，稱為虛擬存儲器虛擬存儲器。5.15.1虛擬存儲器的概念虛擬存儲器的概念所謂虛擬存儲器，所謂虛擬存儲器， 是指具有請求調(diào)入功能和置換功是指具有請求調(diào)入功能和置換功能，能， 能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)系統(tǒng)其邏輯容量由內(nèi)存容量和外存容量之和所決定，其其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速

6、度接近于內(nèi)存，而每位的成本又接近于外存。運(yùn)行速度接近于內(nèi)存，而每位的成本又接近于外存。虛擬存儲技術(shù)是一虛擬存儲技術(shù)是一種性能優(yōu)越的存儲器管理技術(shù)，種性能優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、故被廣泛地應(yīng)用于大、 中、中、 小型機(jī)器和微型機(jī)中。小型機(jī)器和微型機(jī)中。 5.25.2虛擬存儲器的實(shí)現(xiàn)方法虛擬存儲器的實(shí)現(xiàn)方法n基本思想：基本思想： 部分頁面在內(nèi)存，部分在外存上（程序部分頁面在內(nèi)存，部分在外存上（程序部分裝入），當(dāng)訪問到不在內(nèi)存頁時(shí)，產(chǎn)部分裝入），當(dāng)訪問到不在內(nèi)存頁時(shí)，產(chǎn)生缺頁中斷，由生缺頁中斷，由OSOS負(fù)責(zé)進(jìn)行頁面的動(dòng)態(tài)調(diào)負(fù)責(zé)進(jìn)行頁面的動(dòng)態(tài)調(diào)度。度。n 需要考慮的問題：需要考慮的問

7、題： （1）進(jìn)程訪問的頁不在內(nèi)存時(shí)，何時(shí)調(diào)頁？）進(jìn)程訪問的頁不在內(nèi)存時(shí)，何時(shí)調(diào)頁？ （ 2）需要調(diào)頁時(shí)，內(nèi)存無空閑頁面怎么辦？）需要調(diào)頁時(shí)，內(nèi)存無空閑頁面怎么辦？必須建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上。必須建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上。請求分頁系統(tǒng)請求分頁系統(tǒng) 基本分頁系統(tǒng)基本分頁系統(tǒng) + 請求調(diào)頁功能請求調(diào)頁功能 + 頁面置換功能頁面置換功能 頁式虛擬存儲系統(tǒng)頁式虛擬存儲系統(tǒng) 硬件支持：請求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)、動(dòng)硬件支持：請求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)、動(dòng)態(tài)地址變換機(jī)構(gòu)。態(tài)地址變換機(jī)構(gòu)。 軟件支持：請求分頁、頁面置換軟件支持：請求分頁、頁面置換5.25.2虛擬存儲器的實(shí)現(xiàn)方

8、法虛擬存儲器的實(shí)現(xiàn)方法1、硬件支持 請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)； 缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí)，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存； 地址變換機(jī)構(gòu)，它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。 5.3 5.3 請求式分頁存儲管理方式請求式分頁存儲管理方式5.3 5.3 請求式分頁存儲管理方式請求式分頁存儲管理方式1) 一般來說，一個(gè)頁表包括以下信息：一般來說，一個(gè)頁表包括以下信息：頁號頁號塊號塊號狀態(tài)位狀態(tài)位修改位修改位訪問位訪問位外存地址外存地址存取控制存取控制其它其它(1) 狀態(tài)位：用于指

9、示該頁是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考。(2) 訪問字段：用于記錄本頁是否被訪問，供選擇換出頁面時(shí)參考。(3) 修改位：表示該頁在調(diào)入內(nèi)存后是否被修改過，供置換頁面時(shí)參考。(4) 外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時(shí)參考。 2）缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu)n缺頁中斷與一般中斷的區(qū)別：缺頁中斷與一般中斷的區(qū)別：(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。5.3 5.3 請求式分頁存儲管理方式請求式分頁存儲管理方式 涉及6次缺頁中斷的指令 654321A:B:Copy Ato B指令指令3） 地址地址變換變換機(jī)構(gòu)機(jī)構(gòu)2、內(nèi)存分配

10、策略和分配算法內(nèi)存分配策略和分配算法 （1） 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能保證進(jìn)程正常運(yùn)行所需的最小物理是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。塊數(shù)。u 當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。無法運(yùn)行。u 當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)過多時(shí)，影響并發(fā)進(jìn)當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)過多時(shí)，影響并發(fā)進(jìn)程數(shù)，內(nèi)存利用率降低程數(shù)，內(nèi)存利用率降低（2） 物理塊的分配策略物理塊的分配策略 在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，即固定和可變分配策略。在進(jìn)

11、行置換時(shí)， 也可采取也可采取兩種策略，即全局置換和局部置換。于是可組合出兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。以下三種適用的策略。 1) 固定分配局部置換固定分配局部置換 2) 可變分配全局置換可變分配全局置換 3) 可變分配局部置換可變分配局部置換 l平均分配算法平均分配算法l將空閑物理塊，平均分配給各個(gè)進(jìn)程將空閑物理塊，平均分配給各個(gè)進(jìn)程l按比例分配算法按比例分配算法l根據(jù)進(jìn)程的大小按比例分配物理塊根據(jù)進(jìn)程的大小按比例分配物理塊l考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法l按比例分配給各進(jìn)程按比例分配給各進(jìn)程l優(yōu)先權(quán)高的一次分得的物理塊數(shù)多優(yōu)先權(quán)高的一次分得的物理塊

12、數(shù)多（3） 物理塊分配算法物理塊分配算法 3、 調(diào)頁策略調(diào)頁策略 （1） 何時(shí)調(diào)入頁面何時(shí)調(diào)入頁面 1) 預(yù)調(diào)頁策略預(yù)調(diào)頁策略 2) 請求調(diào)頁策略請求調(diào)頁策略 n系統(tǒng)擁有足夠的對換區(qū)空間系統(tǒng)擁有足夠的對換區(qū)空間 n系統(tǒng)缺少足夠的對換區(qū)空間系統(tǒng)缺少足夠的對換區(qū)空間 nUNIX方式方式（2） 從何處調(diào)入頁面從何處調(diào)入頁面 （2） 從何處調(diào)入頁面從何處調(diào)入頁面 在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的的文件區(qū)文件區(qū)和用于存放對換頁面的和用于存放對換頁面的對換區(qū)對換區(qū)。通常，由于對換。通常，由于對換區(qū)是采用連續(xù)分配方式，而文件是采用離散分配方式，故

13、區(qū)是采用連續(xù)分配方式，而文件是采用離散分配方式，故對換區(qū)的磁盤對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：種情況： 1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。 2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時(shí)凡是不會(huì)被修改系統(tǒng)缺少足夠的對換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時(shí)，由的文件，都直接從文件區(qū)調(diào)入；而當(dāng)

14、換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對換區(qū)，以后需要時(shí)，再從對換區(qū)它們換出時(shí)，便須調(diào)到對換區(qū)，以后需要時(shí)，再從對換區(qū)調(diào)入。調(diào)入。 3) UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在運(yùn)行過但又被換出的頁面，

15、由于是被放在對換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對換區(qū)調(diào)入。由于下次調(diào)入時(shí)，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面系統(tǒng)允許頁面共享，因此，共享，因此， 某進(jìn)程所請求的頁面有某進(jìn)程所請求的頁面有可能已被其它進(jìn)程可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再從對換區(qū)調(diào)入。調(diào)入內(nèi)存，此時(shí)也就無須再從對換區(qū)調(diào)入。 (3) 頁面調(diào)入過程頁面調(diào)入過程 每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPU發(fā)出一發(fā)出一缺頁中斷，中斷處理程序首先保留缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因環(huán)境，分析中斷原因后，后， 轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該轉(zhuǎn)入缺頁中斷處

16、理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，頁在外存的物理塊后， 如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，修改， 則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存， 并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為并

17、修改頁表中的相應(yīng)表項(xiàng)，置其存在位為“1”，并將此頁表，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表， 去去形成所要訪問數(shù)據(jù)的形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)物理地址，再去訪問內(nèi)存數(shù)據(jù)。 l向向CPU發(fā)出缺頁中斷發(fā)出缺頁中斷l(xiāng)中斷處理程序保存中斷處理程序保存CPU環(huán)境轉(zhuǎn)中斷處理程序環(huán)境轉(zhuǎn)中斷處理程序l該程序查找頁表，得到該頁在外存中的塊號該程序查找頁表，得到該頁在外存中的塊號l若內(nèi)存未滿，啟動(dòng)磁盤若內(nèi)存未滿，啟動(dòng)磁盤I/O讀入；若內(nèi)存已滿，讀入；若內(nèi)存已滿，先置換，再調(diào)入先置換，再調(diào)入l最后修改頁表對應(yīng)項(xiàng)的內(nèi)容，并將此頁

18、表項(xiàng)寫入最后修改頁表對應(yīng)項(xiàng)的內(nèi)容，并將此頁表項(xiàng)寫入快表快表 (3) 頁面調(diào)入過程頁面調(diào)入過程4、 頁面置換算法頁面置換算法 （1） 最佳最佳(Optimal)置換算法置換算法選擇永不再被使用或很久才被訪問的頁面淘汰選擇永不再被使用或很久才被訪問的頁面淘汰特點(diǎn)：特點(diǎn)：理論上，性能最佳；理論上，性能最佳；實(shí)際上實(shí)際上，無法實(shí)現(xiàn)；，無法實(shí)現(xiàn)；通常用該算法來評價(jià)其他算法的優(yōu)劣通常用該算法來評價(jià)其他算法的優(yōu)劣P351231512341315M=3335351321321321521521521531431431431431435Fvvvvvvvv （1） 最佳最佳(Optimal)置換算法置換算法缺頁率

19、 f = 8 / 15 = 53% 先進(jìn)入內(nèi)存的頁，先退出內(nèi)存。先進(jìn)入內(nèi)存的頁，先退出內(nèi)存。實(shí)質(zhì)上是淘汰在內(nèi)存駐留時(shí)間最長的頁。實(shí)質(zhì)上是淘汰在內(nèi)存駐留時(shí)間最長的頁。其其理由理由是：最早調(diào)入內(nèi)存的頁，不再被使用的可是：最早調(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。能性比近期調(diào)入內(nèi)存的大。 這種算法簡單，實(shí)現(xiàn)容易。這種算法簡單，實(shí)現(xiàn)容易。它是一種最直觀，性能最差的算法，它是一種最直觀，性能最差的算法，它有它有BELADYBELADY異?，F(xiàn)象異?，F(xiàn)象：當(dāng)當(dāng)物理塊數(shù)增加時(shí)，缺頁次數(shù)增加。物理塊數(shù)增加時(shí)，缺頁次數(shù)增加。（2） 先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法 有一虛擬存儲系

20、統(tǒng)，采用先進(jìn)先出的頁面淘汰算法。在內(nèi)存中為每個(gè)進(jìn)程分配3塊。進(jìn)程執(zhí)行時(shí)使用頁號的順序?yàn)?4 3 2 1 4 3 5 4 3 2 1 5(1)該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)幾次缺頁。(2)若每個(gè)進(jìn)程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3)如何解釋所出現(xiàn)的現(xiàn)象。 例1（3） LRU(Least Recently Used)置換算法置換算法選擇在最近一段時(shí)間內(nèi)不常用的頁面進(jìn)行選擇在最近一段時(shí)間內(nèi)不常用的頁面進(jìn)行淘汰淘汰需要周期性地對需要周期性地對“頁面訪問位頁面訪問位”進(jìn)行檢查進(jìn)行檢查,記錄上次訪問以來經(jīng)歷的時(shí)間記錄上次訪問以來經(jīng)歷的時(shí)間該類算法實(shí)現(xiàn)較困難該類算法實(shí)現(xiàn)較困難,常用近似該算法的常用近似該算法的Cl

21、ock算法算法P351231512341315M=3335351251231231531531521321324314314314315Fvvvvvvvvvvv（3） LRU(Least Recently Used)置換算法置換算法缺頁率 f = 11 / 15 = 75% 練習(xí)練習(xí)：在一個(gè)請求分頁系統(tǒng)中，假定系統(tǒng)分給一個(gè)作：在一個(gè)請求分頁系統(tǒng)中，假定系統(tǒng)分給一個(gè)作業(yè)的業(yè)的物理塊數(shù)為物理塊數(shù)為3，并且此作業(yè)的頁面走向?yàn)?，并且此作業(yè)的頁面走向?yàn)?，3，2，1，5，2，4，5，3，2，5，2。用。用FIFO、LRU、OPT計(jì)計(jì)算缺頁次數(shù)和缺頁率。算缺頁次數(shù)和缺頁率。 分析：分析：如果所訪問的頁還沒

22、有裝入內(nèi)存，將發(fā)生一如果所訪問的頁還沒有裝入內(nèi)存，將發(fā)生一次缺頁中斷。次缺頁中斷。訪問過程中發(fā)生缺頁中斷的次數(shù)就是缺頁訪問過程中發(fā)生缺頁中斷的次數(shù)就是缺頁次數(shù)。缺頁次數(shù)除以總的訪問次數(shù)，就是缺頁率。次數(shù)。缺頁次數(shù)除以總的訪問次數(shù)，就是缺頁率。(4) 簡單的簡單的Clock算法算法 每頁設(shè)置一位訪問位。當(dāng)某頁被訪問了，則訪問位置每頁設(shè)置一位訪問位。當(dāng)某頁被訪問了，則訪問位置“1”。 將內(nèi)存中的頁鏈成一個(gè)循環(huán)隊(duì)列將內(nèi)存中的頁鏈成一個(gè)循環(huán)隊(duì)列,查詢指針循環(huán)移動(dòng)查詢指針循環(huán)移動(dòng)入口查尋指針前進(jìn)一步指向下一個(gè)表目訪問位=0?選擇該頁淘汰返回訪問位置 0YF 又稱為又稱為“最近未最近未使用使用”置換算法置

23、換算法（NRU）nClock算法加上置換代價(jià)(盡量選擇未修改過的頁面淘汰)n每頁有訪問頁u 和 修改位mnu=0 m=0 未用過,未修改過,最佳淘汰頁面nu=0 m=1 未用過,但改過,不是最佳淘汰頁面 nu=1 m=0 最近用過,但未被修改,可能被再次使用nu=1 m=1 最近用過,被修改過,可能被再次使用n算法需要重復(fù)多次Clock算法n從當(dāng)前位置找u=0,m=0的頁面,有則淘汰n否則第二遍找u=0,m=1的頁面,同時(shí)將u置為0,有則淘汰n否則第三遍找u=0,m=0的頁面,有則淘汰n否則第四遍找u=0,m=1的頁面,(肯定會(huì)找到)(5) 改進(jìn)型改進(jìn)型Clock算法算法性能分析1、抖動(dòng)n抖動(dòng)

24、: 分給作業(yè)的物理塊太少或置換算法不當(dāng)引發(fā)的頻繁的產(chǎn)生缺頁中斷。n工作集“”是程序局部性的一個(gè)近似.161567675162324124234343432332.=10t1WS(t1)=1,5,6,7 WS(t2)=2,3,4=10t2操作系統(tǒng)管理每一作業(yè)的工作集操作系統(tǒng)管理每一作業(yè)的工作集,為作業(yè)分配足夠的為作業(yè)分配足夠的物理塊物理塊,以容納它的工作集以容納它的工作集若有空閑塊可考慮引入新進(jìn)程若有空閑塊可考慮引入新進(jìn)程若各作業(yè)工作集總和超過可供使用的物理塊數(shù)若各作業(yè)工作集總和超過可供使用的物理塊數(shù),OS選選擇一個(gè)作業(yè)暫停執(zhí)行擇一個(gè)作業(yè)暫停執(zhí)行,頁面寫回外存頁面寫回外存2、工作集模型、工作集模

25、型拐點(diǎn)缺頁率 w 工作集的理論是在1968年由Denning提出來的。他認(rèn)為，程序在運(yùn)行時(shí)對頁面的訪問是不均勻的，即往往在某段時(shí)間內(nèi)的訪問僅局限于較少的若干個(gè)頁面，如果能夠預(yù)知程序在某段時(shí)間間隔內(nèi)要訪問哪些頁面，并能將它們提前調(diào)入內(nèi)存，將會(huì)大大地降低缺頁率，從而減少置換工作，提高 CPU的利用率。w 圖中可以看出，缺頁率隨著所分得的物理塊數(shù)目的減少而遞增，并在所分到的物理塊數(shù)目較少處，出現(xiàn)一個(gè)拐點(diǎn)。在拐點(diǎn)上限以左時(shí)，隨著分到的物理塊數(shù)目的增加，缺頁率明顯地減少；而過了拐點(diǎn)，在下限以右時(shí)，隨著分到的物理塊數(shù)目的增加，卻對缺頁率的改善并不明顯。所以，為進(jìn)程分配的物理塊數(shù)，應(yīng)取在該曲線的拐點(diǎn)左右。

26、所分得的物理塊數(shù)訪問順序1,3,2,4,5,6,1,2,4,5,4,3分配3個(gè)塊, OPT, FIFO , LRU計(jì)算缺頁次數(shù)和缺頁率5.4 請求分段存儲管理方式請求分段存儲管理方式 1 、請求分段中的硬件支持、請求分段中的硬件支持 （1） 段表機(jī)制段表機(jī)制 段名段名 段長段長 段的段的基址基址 存取存取方式方式 訪問訪問字段字段A 修改修改位位M 存在存在位位P 增補(bǔ)增補(bǔ)位位 外存外存始址始址 在段表項(xiàng)中，在段表項(xiàng)中， 除了段名除了段名(號號)、 段長、段長、 段在內(nèi)存中的起段在內(nèi)存中的起始地址外，始地址外， 還增加了以下諸項(xiàng)：還增加了以下諸項(xiàng)：存取方式存取方式 訪問字段訪問字段A 修改位修

27、改位M 存在位存在位P 增補(bǔ)位增補(bǔ)位 外存始址外存始址 （2） 缺段中斷機(jī)構(gòu)缺段中斷機(jī)構(gòu) 虛段S不在內(nèi)存阻塞請求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空區(qū)鏈喚醒請求進(jìn)程返回空區(qū)容量總和能否滿足？空區(qū)拼接，以形成一個(gè)合適的空區(qū)淘汰一個(gè)或幾個(gè)實(shí)段，以形成一個(gè)合適空區(qū)否否是是請求分段系統(tǒng)中的中斷處理過程請求分段系統(tǒng)中的中斷處理過程（3） 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 訪問 sw w 段長?符合存取方式?段 S在主存?修改訪問字段,如寫訪問,置修改位 1形成訪問主存地址(A ) (主存始址)(位移量w )返回分段越界中斷處理分段保護(hù)中斷處理缺段中斷處理是是是否否否圖圖 請求分段系統(tǒng)的地址

28、變換過程請求分段系統(tǒng)的地址變換過程2、 分段的共享與保護(hù)分段的共享與保護(hù) （1） 共享段表共享段表 圖 4-33 共享段表項(xiàng) 段名段長內(nèi)存始址狀態(tài)外存始址共享進(jìn)程計(jì)數(shù)count狀態(tài)進(jìn)程名進(jìn)程號段號存取控制共享段表（2） 共享段的分配與回收共享段的分配與回收 1) 共享段的分配共享段的分配 在為共享段分配內(nèi)存時(shí)，對第一個(gè)請求使用該共享段的進(jìn)在為共享段分配內(nèi)存時(shí)，對第一個(gè)請求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時(shí)將該區(qū)的始址填入請求進(jìn)程的段表的相應(yīng)項(xiàng)中，還須在共同時(shí)將該區(qū)的始址填入請求進(jìn)程的段表的相應(yīng)項(xiàng)中，還

29、須在共享段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，把享段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，把count置為置為1；之后，；之后，當(dāng)又有其它進(jìn)程需要調(diào)用該共享段時(shí)，由于該共享段已被調(diào)入當(dāng)又有其它進(jìn)程需要調(diào)用該共享段時(shí)，由于該共享段已被調(diào)入內(nèi)存，故此時(shí)無須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程的段內(nèi)存，故此時(shí)無須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程的段表中，增加一表項(xiàng)，填寫該共享段的物理地址；在共享段的段表中，增加一表項(xiàng)，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進(jìn)程的進(jìn)程名、存取控制等，再執(zhí)行表中，填上調(diào)用進(jìn)程的進(jìn)程名、存取控制等，再執(zhí)行count =count+1操作，以表明有兩個(gè)進(jìn)程共享該段。操作，以表

30、明有兩個(gè)進(jìn)程共享該段。 2) 共享段的回收共享段的回收 當(dāng)共享此段的某進(jìn)程不再需要該段時(shí)，應(yīng)將該段釋放，當(dāng)共享此段的某進(jìn)程不再需要該段時(shí)，應(yīng)將該段釋放， 包括撤在該進(jìn)程段表中共享段所對應(yīng)的表項(xiàng)，以及執(zhí)行包括撤在該進(jìn)程段表中共享段所對應(yīng)的表項(xiàng)，以及執(zhí)行count =count-1操作。若操作。若結(jié)果為結(jié)果為0，則須由系統(tǒng)回收該，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的表項(xiàng)，表項(xiàng)， 表明此時(shí)已沒有進(jìn)程使用該段；表明此時(shí)已沒有進(jìn)程使用該段；否則否則(減減1結(jié)果不為結(jié)果不為0)， 則只是取消調(diào)用者進(jìn)程在共享段表中的有關(guān)記錄。則

31、只是取消調(diào)用者進(jìn)程在共享段表中的有關(guān)記錄。 （3） 分段保護(hù)分段保護(hù) 1) 越界檢查越界檢查 2) 存取控制檢查存取控制檢查 例題例題某虛擬存儲器的用戶編程空間共某虛擬存儲器的用戶編程空間共3232個(gè)頁面，每頁個(gè)頁面，每頁1KB1KB，主存為，主存為16KB16KB。假定某時(shí)刻用戶頁表中已調(diào)入主存的頁面的虛擬頁號。假定某時(shí)刻用戶頁表中已調(diào)入主存的頁面的虛擬頁號和物理頁表對照表為表一，則下表中與虛擬地址相對應(yīng)的物和物理頁表對照表為表一，則下表中與虛擬地址相對應(yīng)的物理地址為表二（如果主存找不到，即為該頁失效）。虛擬存理地址為表二（如果主存找不到，即為該頁失效）。虛擬存貯存的功能是由貯存的功能是由C

32、 C完成的。在虛擬存貯系統(tǒng)中，采用完成的。在虛擬存貯系統(tǒng)中，采用D D提高提高E E的速度。的速度。 表一表一 虛頁號虛頁號 物理頁號物理頁號 0 50 5 1 10 1 10 2 4 2 4 8 7 8 7 表二表二 虛地址虛地址 物理地址物理地址 0A5C0A5C（H H） A A 1A5C1A5C（H H） B B例題例題-1供選擇的答案：供選擇的答案：A A，B B： 頁失效頁失效 1E5C 1E5C（H H） 2A5C 2A5C（H H） 165C 165C（H H） 125C 125C（H H） 1A5C 1A5C（H H）C C： 硬件硬件 軟件軟件 軟、硬件結(jié)合軟、硬件結(jié)合D

33、D： 高速輔助存貯器高速輔助存貯器 高速光盤存貯器高速光盤存貯器 快速通道快速通道 高速緩沖存貯器高速緩沖存貯器E E： 連接編輯連接編輯 虛地址分配虛地址分配 動(dòng)態(tài)地址翻譯動(dòng)態(tài)地址翻譯 動(dòng)態(tài)連接動(dòng)態(tài)連接例題例題-2解：每頁大小 1KB，用16進(jìn)制表示為400H，由虛地址通過直接映象的地址轉(zhuǎn)換成物理地址步驟如下：n將虛地址分離成頁號p和頁內(nèi)地址d：頁號p（虛地址頁大?。┤≌?A5CH/400H）取整2頁內(nèi)地址d虛地址頁號p每頁大小0A5C(H)2400(H)25C(H)n根據(jù)頁號查頁表，由頁號 p2查頁表得物理頁號為4n將物理頁號和頁內(nèi)地址構(gòu)成物理地址物理頁號頁大小頁內(nèi)地址4400(H)25

34、C(H)125C(H)同理虛擬地址1A5CH分離成頁號P6和頁內(nèi)位移25CH.查頁表知該頁不在內(nèi)存，頁失效產(chǎn)生缺頁中斷調(diào)入內(nèi)存。習(xí)題習(xí)題1虛擬存儲管理系統(tǒng)的基礎(chǔ)是程序的局部性理論。此理論的基虛擬存儲管理系統(tǒng)的基礎(chǔ)是程序的局部性理論。此理論的基本含義是本含義是A A。局部性有兩種表現(xiàn)形式：時(shí)間局限性和。局部性有兩種表現(xiàn)形式：時(shí)間局限性和B B。它們的意義分別為。它們的意義分別為C C和和D D。 A A、B B，程序執(zhí)行時(shí)對主存和訪問是不均勻的程序執(zhí)行時(shí)對主存和訪問是不均勻的 代碼的順代碼的順序執(zhí)行序執(zhí)行 變量的連續(xù)訪問變量的連續(xù)訪問 指令的局部性指令的局部性 數(shù)據(jù)的局部性數(shù)據(jù)的局部性 空間局部

35、性空間局部性C C、D D： 最近被訪問的單元，很可能在不久的將來還要被訪問最近被訪問的單元，很可能在不久的將來還要被訪問 最近被訪問的單元，很可能在它附近的單元也即將被訪問最近被訪問的單元，很可能在它附近的單元也即將被訪問 結(jié)構(gòu)化程序設(shè)計(jì)，很少出現(xiàn)轉(zhuǎn)移語句結(jié)構(gòu)化程序設(shè)計(jì)，很少出現(xiàn)轉(zhuǎn)移語句 程序中循環(huán)語句的執(zhí)行時(shí)間一般很長程序中循環(huán)語句的執(zhí)行時(shí)間一般很長 程序中使用的數(shù)據(jù)局部于各子程序程序中使用的數(shù)據(jù)局部于各子程序 習(xí)題習(xí)題-12.2.什么叫虛擬存貯器什么叫虛擬存貯器? ?試述虛擬存貯器的實(shí)現(xiàn)原理和它的物質(zhì)基礎(chǔ)。試述虛擬存貯器的實(shí)現(xiàn)原理和它的物質(zhì)基礎(chǔ)。3 3在請求分頁內(nèi)存管理的頁表表項(xiàng)中，其中

36、狀態(tài)位供在請求分頁內(nèi)存管理的頁表表項(xiàng)中，其中狀態(tài)位供A A時(shí)參考；修時(shí)參考；修改位供改位供B B時(shí)參考；訪問位供時(shí)參考；訪問位供C C時(shí)參考；外存始址供時(shí)參考；外存始址供D D時(shí)參考。時(shí)參考。 A A，B B，C C，D D：（：（l l）分配頁面；（）分配頁面；（2 2）置換算法；（）置換算法；（3 3）程序訪問；（）程序訪問；（4 4）換）換出頁面；（出頁面；（5 5）調(diào)入頁面。）調(diào)入頁面。4.4.在請求調(diào)頁系統(tǒng)中，凡未裝入過內(nèi)存的頁都應(yīng)從在請求調(diào)頁系統(tǒng)中，凡未裝入過內(nèi)存的頁都應(yīng)從A A調(diào)入；已運(yùn)行調(diào)入；已運(yùn)行過的頁主要是從過的頁主要是從B B調(diào)入，有時(shí)也可以從調(diào)入，有時(shí)也可以從C C調(diào)入

37、。調(diào)入。 A A，B B，C C：（：（1 1）系統(tǒng)區(qū)；（）系統(tǒng)區(qū)；（2 2）文件區(qū)；（）文件區(qū)；（3 3）對換區(qū)；（）對換區(qū)；（4 4）頁面緩沖池。）頁面緩沖池。5.5.詳述在設(shè)有快表的請求分頁存儲管理系統(tǒng)中，一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存詳述在設(shè)有快表的請求分頁存儲管理系統(tǒng)中，一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程。地址的過程。習(xí)題習(xí)題-26在請求調(diào)頁系統(tǒng)中有著多種置換算法：（在請求調(diào)頁系統(tǒng)中有著多種置換算法：（1）選擇最先進(jìn)入內(nèi)存的頁面）選擇最先進(jìn)入內(nèi)存的頁面予以淘汰的算法稱為予以淘汰的算法稱為 A；（；（2）選擇在以后不再使用的頁面予以）選擇在以后不再使用的頁面予以淘汰的算法稱為淘汰的算法稱為B

38、；（；（3）選擇自上次訪問以來所經(jīng)歷時(shí)間最長）選擇自上次訪問以來所經(jīng)歷時(shí)間最長的頁面予以淘汰的算法稱為的頁面予以淘汰的算法稱為C。A，B，C，D：（：（1）FIFO算法；（算法；（2）OPT算法；（算法；（3）LRU算法；（算法；（4）NRU算法。算法。7在一個(gè)請求分頁系統(tǒng)中，采用在一個(gè)請求分頁系統(tǒng)中，采用 FIFO FIFO頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面訪問順序?yàn)槊嬖L問順序?yàn)? 4，3 3，2 2，1 1，4 4，3 3，5 5，4 4，3 3，2 2， l l，5 5，當(dāng)分配給該作業(yè)，當(dāng)分配給該作業(yè)的物理塊數(shù)的物理塊數(shù)M M分別為分別為3 3和和4 4時(shí)

39、，試計(jì)算訪問過程中所發(fā)生的缺頁次數(shù)分別為時(shí)，試計(jì)算訪問過程中所發(fā)生的缺頁次數(shù)分別為A A和和B B，缺頁率分別為，缺頁率分別為A/CA/C和和B/CB/C，其中，其中C C為訪問為訪問次數(shù)。比較所得的結(jié)果為次數(shù)。比較所得的結(jié)果為D D。A A，B B，C C，D D：見：見8 8題題習(xí)題習(xí)題-38 8在一個(gè)請求分頁系統(tǒng)中，采用在一個(gè)請求分頁系統(tǒng)中，采用 LRULRU頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面訪問順序?yàn)槊嬖L問順序?yàn)? 4，3 3，2 2，1 1，4 4，3 3，5 5，4 4，3 3，2 2， l l，5 5，當(dāng)分配給該作業(yè)，當(dāng)分配給該作業(yè)的物理塊數(shù)的物理

40、塊數(shù)M M分別為分別為3 3和和4 4時(shí)，試計(jì)算訪問過程中所發(fā)生的缺頁次數(shù)時(shí)，試計(jì)算訪問過程中所發(fā)生的缺頁次數(shù)A A和和B B，缺頁率分別為，缺頁率分別為A/CA/C和和B/CB/C，其中，其中C C為訪問次數(shù)。為訪問次數(shù)。比較所得的結(jié)果為比較所得的結(jié)果為D D。 A A，B B，C C：（：（1 1）7 7；（；（2 2）8 8；（；（3 3）9 9；（；（4 4）1010；(5)11(5)11；(6)12(6)12；(7)13(7)13。 D: (1) D: (1) 正?，F(xiàn)象，即存儲塊增加，缺頁次數(shù)減少；正常現(xiàn)象，即存儲塊增加，缺頁次數(shù)減少； (2) (2) 存在奇異現(xiàn)象，即存儲塊增加，缺

41、頁次數(shù)反而增加；存在奇異現(xiàn)象，即存儲塊增加，缺頁次數(shù)反而增加； (3) (3) 存儲塊增加，缺頁次數(shù)不變。存儲塊增加，缺頁次數(shù)不變。9.在分頁系統(tǒng)環(huán)境下,程序員編制的程序,其地址空間是連續(xù)的,分頁是由( )完成的A. 程序員 B編譯地址 C用戶 D系統(tǒng)10.在請求分頁存儲管理系統(tǒng)中，若采用FIFO頁面淘汰算法，則當(dāng)分配的頁面數(shù)增加時(shí)，缺頁中斷的次數(shù)（ ）A減少 B 增加 C無影響 D可能增加也可能減少11.采用段式存儲管理的系統(tǒng)中，若地址用24位表示，其中8位表示段號，D則允許每段的最大長度是（ ） A 2 24 B 2 16 C 28 D 2 3212.作業(yè)在執(zhí)行中發(fā)生了缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行（ ）