第5章虛擬存儲(chǔ)器

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

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

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

4、循環(huán)操作。n空間局部性：空間局部性：一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，則不久后，其附近的存儲(chǔ)單元也將被訪問(wèn)，即則不久后，其附近的存儲(chǔ)單元也將被訪問(wèn)，即程序在一段時(shí)間內(nèi)訪問(wèn)的地址，可能集中在一程序在一段時(shí)間內(nèi)訪問(wèn)的地址，可能集中在一定的范圍內(nèi)，其典型情況是程序的順序執(zhí)行。定的范圍內(nèi)，其典型情況是程序的順序執(zhí)行。5.15.1虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)器的概念n基于程序的局部性考慮，就沒(méi)有必要把一個(gè)作基于程序的局部性考慮，就沒(méi)有必要把一個(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)和硬件配合來(lái)完成主存和輔存之間信息作系統(tǒng)和硬件配合來(lái)完成主存和輔存之間信息的調(diào)度。的調(diào)度。n這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)比實(shí)這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)比實(shí)際容量大得多的一個(gè)內(nèi)存，稱為際容量大得多的一個(gè)內(nèi)存，稱為虛擬存儲(chǔ)器虛擬存儲(chǔ)器。5.15.1虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)器的概念所謂虛擬存儲(chǔ)器，所謂虛擬存儲(chǔ)器， 是指具有請(qǐng)求調(diào)入功能和置換功是指具有請(qǐng)求調(diào)入功能和置換功能，能， 能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)系統(tǒng)其邏輯容量由內(nèi)存容量和外存容量之和所決定，其其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速

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

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

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

9、示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。(2) 訪問(wèn)字段：用于記錄本頁(yè)是否被訪問(wèn)，供選擇換出頁(yè)面時(shí)參考。(3) 修改位：表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)，供置換頁(yè)面時(shí)參考。(4) 外存地址：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考。 2）缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)n缺頁(yè)中斷與一般中斷的區(qū)別：缺頁(yè)中斷與一般中斷的區(qū)別：(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。5.3 5.3 請(qǐng)求式分頁(yè)存儲(chǔ)管理方式請(qǐng)求式分頁(yè)存儲(chǔ)管理方式 涉及6次缺頁(yè)中斷的指令 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)程將無(wú)法運(yùn)行。無(wú)法運(yùn)行。u 當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)過(guò)多時(shí)，影響并發(fā)進(jìn)當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)過(guò)多時(shí)，影響并發(fā)進(jìn)程數(shù)，內(nèi)存利用率降低程數(shù)，內(nèi)存利用率降低（2） 物理塊的分配策略物理塊的分配策略 在請(qǐng)求分頁(yè)系統(tǒng)中，可采取兩種內(nèi)存分配策略，在請(qǐng)求分頁(yè)系統(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)頁(yè)策略調(diào)頁(yè)策略 （1） 何時(shí)調(diào)入頁(yè)面何時(shí)調(diào)入頁(yè)面 1) 預(yù)調(diào)頁(yè)策略預(yù)調(diào)頁(yè)策略 2) 請(qǐng)求調(diào)頁(yè)策略請(qǐng)求調(diào)頁(yè)策略 n系統(tǒng)擁有足夠的對(duì)換區(qū)空間系統(tǒng)擁有足夠的對(duì)換區(qū)空間 n系統(tǒng)缺少足夠的對(duì)換區(qū)空間系統(tǒng)缺少足夠的對(duì)換區(qū)空間 nUNIX方式方式（2） 從何處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面 （2） 從何處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面 在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的的文件區(qū)文件區(qū)和用于存放對(duì)換頁(yè)面的和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)對(duì)換區(qū)。通常，由于對(duì)換。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而文件是采用離散分配方式，故

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

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

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

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

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

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

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

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

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

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

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

24、: 分給作業(yè)的物理塊太少或置換算法不當(dāng)引發(fā)的頻繁的產(chǎn)生缺頁(yè)中斷。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è)工作集總和超過(guò)可供使用的物理塊數(shù)若各作業(yè)工作集總和超過(guò)可供使用的物理塊數(shù),OS選選擇一個(gè)作業(yè)暫停執(zhí)行擇一個(gè)作業(yè)暫停執(zhí)行,頁(yè)面寫(xiě)回外存頁(yè)面寫(xiě)回外存2、工作集模型、工作集模

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

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

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

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

29、須在共享段表中增加一表項(xiàng)，填寫(xiě)有關(guān)數(shù)據(jù)，把享段表中增加一表項(xiàng)，填寫(xiě)有關(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í)無(wú)須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程的段內(nèi)存，故此時(shí)無(wú)須再為該段分配內(nèi)存，而只需在調(diào)用進(jìn)程的段表中，增加一表項(xiàng)，填寫(xiě)該共享段的物理地址；在共享段的段表中，增加一表項(xiàng)，填寫(xiě)該共享段的物理地址；在共享段的段表中，填上調(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)程段表中共享段所對(duì)應(yīng)的表項(xiàng)，以及執(zhí)行包括撤在該進(jìn)程段表中共享段所對(duì)應(yīng)的表項(xiàng)，以及執(zhí)行count =count-1操作。若操作。若結(jié)果為結(jié)果為0，則須由系統(tǒng)回收該，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對(duì)應(yīng)的共享段的物理內(nèi)存，以及取消在共享段表中該段所對(duì)應(yīng)的表項(xiàng)，表項(xiàng)， 表明此時(shí)已沒(méi)有進(jìn)程使用該段；表明此時(shí)已沒(méi)有進(jìn)程使用該段；否則否則(減減1結(jié)果不為結(jié)果不為0)， 則只是取消調(diào)用者進(jìn)程在共享段表中的有關(guān)記錄。則

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

32、 C完成的。在虛擬存貯系統(tǒng)中，采用完成的。在虛擬存貯系統(tǒng)中，采用D D提高提高E E的速度。的速度。 表一表一 虛頁(yè)號(hào)虛頁(yè)號(hào) 物理頁(yè)號(hào)物理頁(yè)號(hào) 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： 頁(yè)失效頁(yè)失效 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解：每頁(yè)大小 1KB，用16進(jìn)制表示為400H，由虛地址通過(guò)直接映象的地址轉(zhuǎn)換成物理地址步驟如下：n將虛地址分離成頁(yè)號(hào)p和頁(yè)內(nèi)地址d：頁(yè)號(hào)p（虛地址頁(yè)大?。┤≌?A5CH/400H）取整2頁(yè)內(nèi)地址d虛地址頁(yè)號(hào)p每頁(yè)大小0A5C(H)2400(H)25C(H)n根據(jù)頁(yè)號(hào)查頁(yè)表，由頁(yè)號(hào) p2查頁(yè)表得物理頁(yè)號(hào)為4n將物理頁(yè)號(hào)和頁(yè)內(nèi)地址構(gòu)成物理地址物理頁(yè)號(hào)頁(yè)大小頁(yè)內(nèi)地址4400(H)25

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

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

36、狀態(tài)位供在請(qǐng)求分頁(yè)內(nèi)存管理的頁(yè)表表項(xiàng)中，其中狀態(tài)位供A A時(shí)參考；修時(shí)參考；修改位供改位供B B時(shí)參考；訪問(wèn)位供時(shí)參考；訪問(wèn)位供C C時(shí)參考；外存始址供時(shí)參考；外存始址供D D時(shí)參考。時(shí)參考。 A A，B B，C C，D D：（：（l l）分配頁(yè)面；（）分配頁(yè)面；（2 2）置換算法；（）置換算法；（3 3）程序訪問(wèn)；（）程序訪問(wèn)；（4 4）換）換出頁(yè)面；（出頁(yè)面；（5 5）調(diào)入頁(yè)面。）調(diào)入頁(yè)面。4.4.在請(qǐng)求調(diào)頁(yè)系統(tǒng)中，凡未裝入過(guò)內(nèi)存的頁(yè)都應(yīng)從在請(qǐng)求調(diào)頁(yè)系統(tǒng)中，凡未裝入過(guò)內(nèi)存的頁(yè)都應(yīng)從A A調(diào)入；已運(yùn)行調(diào)入；已運(yùn)行過(guò)的頁(yè)主要是從過(guò)的頁(yè)主要是從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）對(duì)換區(qū)；（）對(duì)換區(qū)；（4 4）頁(yè)面緩沖池。）頁(yè)面緩沖池。5.5.詳述在設(shè)有快表的請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存詳述在設(shè)有快表的請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存地址的過(guò)程。地址的過(guò)程。習(xí)題習(xí)題-26在請(qǐng)求調(diào)頁(yè)系統(tǒng)中有著多種置換算法：（在請(qǐng)求調(diào)頁(yè)系統(tǒng)中有著多種置換算法：（1）選擇最先進(jìn)入內(nèi)存的頁(yè)面）選擇最先進(jìn)入內(nèi)存的頁(yè)面予以淘汰的算法稱為予以淘汰的算法稱為 A；（；（2）選擇在以后不再使用的頁(yè)面予以）選擇在以后不再使用的頁(yè)面予以淘汰的算法稱為淘汰的算法稱為B

38、；（；（3）選擇自上次訪問(wèn)以來(lái)所經(jīng)歷時(shí)間最長(zhǎng)）選擇自上次訪問(wèn)以來(lái)所經(jīng)歷時(shí)間最長(zhǎng)的頁(yè)面予以淘汰的算法稱為的頁(yè)面予以淘汰的算法稱為C。A，B，C，D：（：（1）FIFO算法；（算法；（2）OPT算法；（算法；（3）LRU算法；（算法；（4）NRU算法。算法。7在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，采用在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，采用 FIFO FIFO頁(yè)面置換算法時(shí)，假如一個(gè)作業(yè)的頁(yè)頁(yè)面置換算法時(shí)，假如一個(gè)作業(yè)的頁(yè)面訪問(wèn)順序?yàn)槊嬖L問(wèn)順序?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ì)算訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)分別為時(shí)，試計(jì)算訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)分別為A A和和B B，缺頁(yè)率分別為，缺頁(yè)率分別為A/CA/C和和B/CB/C，其中，其中C C為訪問(wèn)為訪問(wèn)次數(shù)。比較所得的結(jié)果為次數(shù)。比較所得的結(jié)果為D D。A A，B B，C C，D D：見(jiàn)：見(jiàn)8 8題題習(xí)題習(xí)題-38 8在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，采用在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，采用 LRULRU頁(yè)面置換算法時(shí)，假如一個(gè)作業(yè)的頁(yè)頁(yè)面置換算法時(shí)，假如一個(gè)作業(yè)的頁(yè)面訪問(wèn)順序?yàn)槊嬖L問(wèn)順序?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ì)算訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)時(shí)，試計(jì)算訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)A A和和B B，缺頁(yè)率分別為，缺頁(yè)率分別為A/CA/C和和B/CB/C，其中，其中C C為訪問(wèn)次數(shù)。為訪問(wèn)次數(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)象，即存儲(chǔ)塊增加，缺頁(yè)次數(shù)減少；正?，F(xiàn)象，即存儲(chǔ)塊增加，缺頁(yè)次數(shù)減少； (2) (2) 存在奇異現(xiàn)象，即存儲(chǔ)塊增加，缺

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