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

1、第五章第五章 虛擬存儲(chǔ)器虛擬存儲(chǔ)器n重點(diǎn)重點(diǎn)n理解理解虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念 n掌握掌握請(qǐng)求分頁系統(tǒng)的基本原理請(qǐng)求分頁系統(tǒng)的基本原理 n掌握頁面置換算法掌握頁面置換算法n頁面抖動(dòng)的工作集模型頁面抖動(dòng)的工作集模型n難點(diǎn)難點(diǎn)n請(qǐng)求分頁系統(tǒng)的地址轉(zhuǎn)換請(qǐng)求分頁系統(tǒng)的地址轉(zhuǎn)換n頁面置換算法頁面置換算法第五章第五章 虛擬存儲(chǔ)器虛擬存儲(chǔ)器n知識(shí)點(diǎn)知識(shí)點(diǎn)n虛擬存儲(chǔ)器的基本概念、特征虛擬存儲(chǔ)器的基本概念、特征n頁面置換技術(shù)頁面置換技術(shù) n請(qǐng)求分頁系統(tǒng)，頁表機(jī)制、地址變換請(qǐng)求分頁系統(tǒng)，頁表機(jī)制、地址變換n頁面置換算法頁面置換算法n頁面抖動(dòng)工作集模型頁面抖動(dòng)工作集模型第五章虛擬存儲(chǔ)器 5.1 虛擬

2、存儲(chǔ)器概述虛擬存儲(chǔ)器概述 5.2請(qǐng)求分頁存儲(chǔ)管理方式請(qǐng)求分頁存儲(chǔ)管理方式 5.3頁面置換算法頁面置換算法5.4“抖動(dòng)抖動(dòng)”與工作集與工作集5.5請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述n5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原常規(guī)存儲(chǔ)管理方式的特征和局部性原理理n5.1.2 虛擬存儲(chǔ)器的定義和特征虛擬存儲(chǔ)器的定義和特征n5.1.3 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理連續(xù)分配連續(xù)分配 離散分配離散分配 (基本基本)分頁分頁 (基本基本)分段分段段頁式段頁式方便程序裝入方便

3、程序裝入提高內(nèi)存利用率提高內(nèi)存利用率n程序裝入內(nèi)存時(shí)可能出現(xiàn)的問題程序裝入內(nèi)存時(shí)可能出現(xiàn)的問題n程序太大，要求的空間超出了內(nèi)存總?cè)萘砍绦蛱螅蟮目臻g超出了內(nèi)存總?cè)萘縩大量作業(yè)要求運(yùn)行，但內(nèi)存不能容下所有作業(yè)大量作業(yè)要求運(yùn)行，但內(nèi)存不能容下所有作業(yè)n常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征n一次性一次性n要求作業(yè)全部裝入內(nèi)存才能運(yùn)行要求作業(yè)全部裝入內(nèi)存才能運(yùn)行n駐留性駐留性n程序裝入內(nèi)存后便一直駐留內(nèi)存，直至運(yùn)行結(jié)束程序裝入內(nèi)存后便一直駐留內(nèi)存，直至運(yùn)行結(jié)束許多不用或暫時(shí)不用的程序占用了大量?jī)?nèi)存空許多不用或暫時(shí)不用的程序占用了大量?jī)?nèi)存空間，而其他程序卻無法裝入！間，而其他程序卻無法裝

4、入！是否必要？是否必要？5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理n局部性原理（局部性原理（1968年，年， Denning.P） n程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是令外，在大多數(shù)情況下仍是順序執(zhí)行順序執(zhí)行的；的；n過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都的深度在大多數(shù)情況下都不超過不超過5；n程序中存在許多程序中存在許多循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)，這些雖

5、然只由少數(shù)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行；指令構(gòu)成，但是它們將多次執(zhí)行；n程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)數(shù)程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)數(shù)組進(jìn)行操作，它們往往都組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)局限于很小的范圍內(nèi)5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理n局限性的表現(xiàn)局限性的表現(xiàn)n時(shí)間局限性時(shí)間局限性n某條指令被執(zhí)行某條指令被執(zhí)行= 不久以后該指令可能再次執(zhí)行不久以后該指令可能再次執(zhí)行n數(shù)據(jù)被訪問過數(shù)據(jù)被訪問過=不久以后該數(shù)據(jù)可能再次被訪問不久以后該數(shù)據(jù)可能再次被訪問n典型原因：因在程序中存在著大量典型原因：因在程序中

6、存在著大量循環(huán)操作循環(huán)操作n空間局限性空間局限性n存儲(chǔ)單元被訪問存儲(chǔ)單元被訪問=不久之后，其附近的存儲(chǔ)單元也不久之后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)間內(nèi)所將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址訪問的地址，可可能集中能集中在一定的范圍之內(nèi)在一定的范圍之內(nèi)n典型情況：程序的順序執(zhí)行。典型情況：程序的順序執(zhí)行。5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理n虛擬存儲(chǔ)器的基本工作情況虛擬存儲(chǔ)器的基本工作情況n程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，操作系統(tǒng)把程序當(dāng)前使用的

7、部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換。存和磁盤之間動(dòng)態(tài)交換。n虛擬存儲(chǔ)器支持多道程序設(shè)計(jì)技術(shù)虛擬存儲(chǔ)器支持多道程序設(shè)計(jì)技術(shù)5.1.1 常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理5.1.2 虛擬存儲(chǔ)器的定義和特征虛擬存儲(chǔ)器的定義和特征n虛擬存儲(chǔ)器定義虛擬存儲(chǔ)器定義n具有具有請(qǐng)求調(diào)入功能請(qǐng)求調(diào)入功能和和置換功能置換功能， 能從能從邏輯上邏輯上對(duì)對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯。其邏輯容量由容量由內(nèi)存容量和外存容量之和內(nèi)存容量和外存容量之和所決定，其運(yùn)所

8、決定，其運(yùn)行行速度速度接近于接近于內(nèi)存速度，而其內(nèi)存速度，而其成本成本卻又接近于卻又接近于外存。外存。n注意：注意：虛擬存儲(chǔ)器的最大容量是由計(jì)算機(jī)的地虛擬存儲(chǔ)器的最大容量是由計(jì)算機(jī)的地址結(jié)構(gòu)確定的。如：若址結(jié)構(gòu)確定的。如：若CPU的的有效地址長(zhǎng)度有效地址長(zhǎng)度為為32位，則程序可以尋址范圍是位，則程序可以尋址范圍是0(232-1) ，即，即虛存容量為虛存容量為 4GB。5.1.2 虛擬存儲(chǔ)器的定義和特征虛擬存儲(chǔ)器的定義和特征n虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征n多次性多次性 n一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行n對(duì)換性對(duì)換性n允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出允許在作業(yè)

9、的運(yùn)行過程中進(jìn)行換進(jìn)、換出n虛擬性虛擬性 n能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量容量遠(yuǎn)大于實(shí)際內(nèi)存容量注意注意：以：以CPUCPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。資源轉(zhuǎn)換技術(shù)。5.1.3 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法n虛擬存儲(chǔ)器的實(shí)現(xiàn)虛擬存儲(chǔ)器的實(shí)現(xiàn)n建立在建立在離散分配離散分配的存儲(chǔ)管理方式基礎(chǔ)上。的存儲(chǔ)管理方式基礎(chǔ)上。n主要實(shí)現(xiàn)方式主要實(shí)現(xiàn)方式n請(qǐng)求分頁系統(tǒng)請(qǐng)求分頁系統(tǒng)n請(qǐng)求分段系統(tǒng)請(qǐng)求分段系統(tǒng)5.1.3 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛

10、擬存儲(chǔ)器的實(shí)現(xiàn)方法n請(qǐng)求分頁系統(tǒng)：請(qǐng)求分頁系統(tǒng)：在分頁系統(tǒng)的基礎(chǔ)上增加了在分頁系統(tǒng)的基礎(chǔ)上增加了請(qǐng)請(qǐng)求調(diào)頁求調(diào)頁功能和功能和頁面置換頁面置換功能功能n硬件支持硬件支持n頁表機(jī)制頁表機(jī)制。在純分頁的頁表機(jī)制上增加若干項(xiàng)。在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請(qǐng)求分頁的數(shù)據(jù)結(jié)構(gòu)；而形成的，作為請(qǐng)求分頁的數(shù)據(jù)結(jié)構(gòu)；n缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu)。每當(dāng)用戶程序要訪問的頁面尚。每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí)未調(diào)入內(nèi)存時(shí) 便產(chǎn)生一缺頁中斷，以請(qǐng)求便產(chǎn)生一缺頁中斷，以請(qǐng)求OS將將所缺的頁調(diào)入內(nèi)存；所缺的頁調(diào)入內(nèi)存；n地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)。在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)。在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上

11、發(fā)展形成的上發(fā)展形成的n軟件支持軟件支持n實(shí)現(xiàn)實(shí)現(xiàn)請(qǐng)求調(diào)頁請(qǐng)求調(diào)頁的軟件和實(shí)現(xiàn)的軟件和實(shí)現(xiàn)頁面置換頁面置換的軟件的軟件5.1.3 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法n請(qǐng)求分段系統(tǒng)請(qǐng)求分段系統(tǒng)n系統(tǒng)同樣需要必要的硬件支持：系統(tǒng)同樣需要必要的硬件支持：n段表機(jī)制。段表機(jī)制。在純分段的段表機(jī)制基礎(chǔ)上，增加在純分段的段表機(jī)制基礎(chǔ)上，增加若干項(xiàng)而形成的；若干項(xiàng)而形成的；n缺段中斷機(jī)構(gòu)。缺段中斷機(jī)構(gòu)。每當(dāng)用戶程序所要訪問的段尚每當(dāng)用戶程序所要訪問的段尚未調(diào)入內(nèi)存時(shí)，產(chǎn)生一缺段中斷，請(qǐng)求未調(diào)入內(nèi)存時(shí)，產(chǎn)生一缺段中斷，請(qǐng)求OS將所將所缺的段調(diào)入內(nèi)存；缺的段調(diào)入內(nèi)存；n地址變換機(jī)構(gòu)。地址變換機(jī)構(gòu)。與請(qǐng)求調(diào)

12、頁類似，實(shí)現(xiàn)請(qǐng)求調(diào)與請(qǐng)求調(diào)頁類似，實(shí)現(xiàn)請(qǐng)求調(diào)段和置換功能也需要得到段和置換功能也需要得到OS的支持。的支持。5.2 請(qǐng)求分頁存儲(chǔ)管理方式請(qǐng)求分頁存儲(chǔ)管理方式n5.2.1 請(qǐng)求分頁中的硬件支持請(qǐng)求分頁中的硬件支持n5.2.2 請(qǐng)求式分頁中的內(nèi)存分配請(qǐng)求式分頁中的內(nèi)存分配n5.2.3 頁面調(diào)入策略頁面調(diào)入策略5.2.1 請(qǐng)求分頁中的硬件支持請(qǐng)求分頁中的硬件支持n系統(tǒng)系統(tǒng)需要解決的問題需要解決的問題n如何獲知進(jìn)程當(dāng)前所需頁面不在主存？如何獲知進(jìn)程當(dāng)前所需頁面不在主存？n如何把所缺頁面調(diào)入主存？如何把所缺頁面調(diào)入主存？n采用什么策略選擇欲淘汰的頁面？采用什么策略選擇欲淘汰的頁面？n當(dāng)主存中沒有空閑的頁

13、框時(shí)，為了要接受一個(gè)新頁，當(dāng)主存中沒有空閑的頁框時(shí)，為了要接受一個(gè)新頁，需要需要把老的一頁淘汰出去。把老的一頁淘汰出去。5.2.1 請(qǐng)求分頁中的硬件支持請(qǐng)求分頁中的硬件支持n請(qǐng)求頁表機(jī)制請(qǐng)求頁表機(jī)制n狀態(tài)位狀態(tài)位P（中斷位）指示該頁是在內(nèi)存還是在（中斷位）指示該頁是在內(nèi)存還是在外存外存n訪問位訪問位A 用于記錄本頁在一段時(shí)間內(nèi)用于記錄本頁在一段時(shí)間內(nèi)被訪問的被訪問的次數(shù)次數(shù)或記錄本頁在最近多長(zhǎng)時(shí)間或記錄本頁在最近多長(zhǎng)時(shí)間未被訪問未被訪問n修改位修改位M 表示該頁在內(nèi)存中是否表示該頁在內(nèi)存中是否被修改過被修改過n外存地址外存地址 該頁在外存上的地址，通常是物理該頁在外存上的地址，通常是物理塊號(hào)。

14、塊號(hào)。頁號(hào)頁號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P 訪問位訪問位A 修改位修改位M外存地址外存地址 5.2.1 請(qǐng)求分頁中的硬件支持請(qǐng)求分頁中的硬件支持n缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu)n在請(qǐng)求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在在請(qǐng)求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時(shí)，便產(chǎn)生一內(nèi)存時(shí)，便產(chǎn)生一缺頁中斷。缺頁中斷。相應(yīng)的中斷處理相應(yīng)的中斷處理程序把控制轉(zhuǎn)向缺頁中斷子程序，執(zhí)行此子程程序把控制轉(zhuǎn)向缺頁中斷子程序，執(zhí)行此子程序，即把所缺頁面裝入主存，然后處理機(jī)重新序，即把所缺頁面裝入主存，然后處理機(jī)重新執(zhí)行缺頁時(shí)打斷的指令。這時(shí)，就將順利形成執(zhí)行缺頁時(shí)打斷的指令。這時(shí)，就將順利形成物理地址。物理地址。n

15、缺頁中斷與一般中斷的區(qū)別缺頁中斷與一般中斷的區(qū)別n在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)n一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。涉及涉及6次缺頁中斷的指令次缺頁中斷的指令 例例. COPY, 能夠移動(dòng)能夠移動(dòng)256B塊可能跨越頁邊界；塊可能跨越頁邊界；移動(dòng)部分字符后出現(xiàn)頁錯(cuò)誤；移動(dòng)部分字符后出現(xiàn)頁錯(cuò)誤；如果源和目的塊有重疊，如果源和目的塊有重疊，源塊可能已被修改。源塊可能已被修改。解決方案解決方案試圖存取兩個(gè)塊的兩端；試圖存取兩個(gè)塊的兩端；使用臨時(shí)寄存器保存被覆蓋使用臨時(shí)寄存器保存被覆蓋位置的值。位置的值。5.2.1 請(qǐng)求分頁

16、中的硬件支持請(qǐng)求分頁中的硬件支持5.2.1 請(qǐng)求分頁中的硬件支持請(qǐng)求分頁中的硬件支持n地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)n在分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，增加實(shí)現(xiàn)虛擬存在分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，增加實(shí)現(xiàn)虛擬存儲(chǔ)器某些功能形成的，如產(chǎn)生和處理缺頁中斷，以及儲(chǔ)器某些功能形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等。從內(nèi)存中換出一頁的功能等等。n地址變換過程地址變換過程n檢索快表，試圖從中找出所要訪問的頁。若找到，便檢索快表，試圖從中找出所要訪問的頁。若找到，便修改頁表項(xiàng)中的訪問位。對(duì)于寫指令，還須將修改位修改頁表項(xiàng)中的訪問位。對(duì)于寫指令，還須將修改位置成置成“1”；n然后利用頁表項(xiàng)中給

17、出的物理塊號(hào)和頁內(nèi)地址形成物然后利用頁表項(xiàng)中給出的物理塊號(hào)和頁內(nèi)地址形成物理地址，結(jié)束。理地址，結(jié)束。 n內(nèi)存中去查找頁表，再從找到的頁表項(xiàng)中的狀態(tài)位內(nèi)存中去查找頁表，再從找到的頁表項(xiàng)中的狀態(tài)位P，來了解該頁是否已調(diào)入內(nèi)存。來了解該頁是否已調(diào)入內(nèi)存。請(qǐng)請(qǐng)求求分分頁頁中中的的地地址址變變換換過過程程 缺頁中斷處理缺頁中斷處理保留保留CPU現(xiàn)場(chǎng)現(xiàn)場(chǎng)從外存中找到缺頁從外存中找到缺頁內(nèi)存滿否？?jī)?nèi)存滿否？選擇一頁換出選擇一頁換出該頁被修改否？該頁被修改否？將該頁寫回外存將該頁寫回外存啟動(dòng)啟動(dòng)I/O硬件硬件將一頁從外存換入內(nèi)存將一頁從外存換入內(nèi)存修改頁表修改頁表否否是是是是否否頁表項(xiàng)在快表中？頁表項(xiàng)在快表

18、中？CPU檢索快表檢索快表訪問頁表訪問頁表否否頁在內(nèi)存？頁在內(nèi)存？修改訪問位和修改位修改訪問位和修改位形成物理地址形成物理地址地址變換結(jié)束地址變換結(jié)束否否頁號(hào)頁頁號(hào)頁表長(zhǎng)度表長(zhǎng)度?開始開始程序請(qǐng)求訪問一頁程序請(qǐng)求訪問一頁產(chǎn)生缺頁中產(chǎn)生缺頁中斷請(qǐng)求調(diào)頁斷請(qǐng)求調(diào)頁修改快表修改快表是是越界中斷越界中斷是是是是OS命令命令CPU從外存讀缺頁從外存讀缺頁5.2.2 請(qǐng)求分頁中的內(nèi)存分配請(qǐng)求分頁中的內(nèi)存分配n最小物理塊數(shù)的確定最小物理塊數(shù)的確定 n指保證進(jìn)程正常運(yùn)行所需的指保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)最小物理塊數(shù)。當(dāng)系。當(dāng)系統(tǒng)分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行統(tǒng)分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將

19、無法運(yùn)行n與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、 功能和尋址方式功能和尋址方式n單地址指令單地址指令且采用且采用直接尋址方式直接尋址方式的機(jī)器，則所需最少的機(jī)器，則所需最少2個(gè)個(gè)物理塊。其中，一塊存放指令頁面，另一塊則存放數(shù)據(jù)物理塊。其中，一塊存放指令頁面，另一塊則存放數(shù)據(jù)頁面頁面n允許間接尋址允許間接尋址的機(jī)器，至少要求有的機(jī)器，至少要求有3個(gè)個(gè)物理塊物理塊n兩個(gè)或多于兩個(gè)字節(jié)指令兩個(gè)或多于兩個(gè)字節(jié)指令的機(jī)器，其指令本身可能跨兩的機(jī)器，其指令本身可能跨兩個(gè)頁面，且源和目標(biāo)地址所涉及的區(qū)域也可能跨兩個(gè)頁個(gè)頁面，且源和目標(biāo)地址所涉及的區(qū)域也可能跨兩個(gè)

20、頁面，至少需要面，至少需要6個(gè)個(gè)物理塊物理塊5.2.2 請(qǐng)求分頁中的內(nèi)存分配請(qǐng)求分頁中的內(nèi)存分配n最小物理塊數(shù)的確定最小物理塊數(shù)的確定n不同的作業(yè)要求不同。不同的作業(yè)要求不同。n如：允許間接尋址：則至少要求如：允許間接尋址：則至少要求3個(gè)物理塊。個(gè)物理塊。nMov A, BnLoad 1, 1000n 方式，方式，n 則所需的最少則所需的最少n 物理塊數(shù)為物理塊數(shù)為25.2.2 請(qǐng)求分頁中的內(nèi)存分配請(qǐng)求分頁中的內(nèi)存分配n物理塊的分配策略物理塊的分配策略 n在請(qǐng)求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，在請(qǐng)求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即即固定固定和和可變可變分配策略。在進(jìn)行置換時(shí)，也可分配

21、策略。在進(jìn)行置換時(shí)，也可采取兩種策略，即采取兩種策略，即全局置換全局置換和和局部置換局部置換。于是。于是可組合出以下三種適用的策略可組合出以下三種適用的策略n固定分配局部置換固定分配局部置換(Fixed Allocation, Local Replacement) n可變分配全局置換可變分配全局置換(Variable Allocation, Global Replacement) n可變分配局部置換可變分配局部置換(Variable Allocation, Local Replacemen問題：分配塊數(shù)難確定，太少，問題：分配塊數(shù)難確定，太少，缺頁頻繁，吞吐量降低；太多，缺頁頻繁，吞吐量降低；

22、太多，內(nèi)存駐留進(jìn)程數(shù)減少，內(nèi)存駐留進(jìn)程數(shù)減少，CPU或或其它資源可能空閑其它資源可能空閑先分配給各進(jìn)程一定數(shù)先分配給各進(jìn)程一定數(shù)的物理塊，系統(tǒng)有一空的物理塊，系統(tǒng)有一空閑物理塊隊(duì)列，缺頁時(shí)閑物理塊隊(duì)列，缺頁時(shí)從空閑隊(duì)列取，若空閑從空閑隊(duì)列取，若空閑隊(duì)列空時(shí)，再選頁調(diào)出隊(duì)列空時(shí)，再選頁調(diào)出先分配給各進(jìn)程一定先分配給各進(jìn)程一定數(shù)的物理塊，缺頁時(shí)數(shù)的物理塊，缺頁時(shí)從該進(jìn)程在內(nèi)存的頁從該進(jìn)程在內(nèi)存的頁選一換出，若其頻繁選一換出，若其頻繁缺頁，系統(tǒng)再分配若缺頁，系統(tǒng)再分配若干附加物理塊干附加物理塊5.2.2 請(qǐng)求分頁中的內(nèi)存分配請(qǐng)求分頁中的內(nèi)存分配n物理塊分配算法物理塊分配算法n平均分配算法平均分配算法

23、n將系統(tǒng)中所有可供分配的物理塊，平均分配將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程給各個(gè)進(jìn)程n 例：當(dāng)系統(tǒng)中有例：當(dāng)系統(tǒng)中有100個(gè)物理塊，有個(gè)物理塊，有5個(gè)進(jìn)程在個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。個(gè)物理塊。n不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為小。如有一個(gè)進(jìn)程其大小為200頁，只分配頁，只分配給它給它20個(gè)塊，這樣，它必然會(huì)有很高的缺頁個(gè)塊，這樣，它必然會(huì)有很高的缺頁率；而另一個(gè)進(jìn)程只有率；而另一個(gè)進(jìn)程只有10頁，卻有頁，卻有10個(gè)物理個(gè)物理塊閑置未用塊閑置未用5.2.2 請(qǐng)求分頁中的內(nèi)存分

24、配請(qǐng)求分頁中的內(nèi)存分配n物理塊分配算法物理塊分配算法n按比例分配算法按比例分配算法n根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：中各進(jìn)程頁面數(shù)的總和為： n又假定系統(tǒng)中可用的物理塊總數(shù)為又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為所能分到的物理塊數(shù)為bi，將有：，將有：n b應(yīng)該取整，它必須大于最小物理塊數(shù)應(yīng)該取整，它必須大于最小物理塊數(shù)niiSS1mSSbii5.2.2 請(qǐng)求分頁中的內(nèi)存分配請(qǐng)求分頁中的內(nèi)

25、存分配n物理塊分配算法物理塊分配算法n考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法n在實(shí)際應(yīng)用中，為了使在實(shí)際應(yīng)用中，為了使重要的、緊迫重要的、緊迫的用戶的用戶程序能盡快地完成，為它分配較多的內(nèi)存空程序能盡快地完成，為它分配較多的內(nèi)存空間。間。n通常方法是把內(nèi)存中可供分配的所有物理塊通常方法是把內(nèi)存中可供分配的所有物理塊分成分成兩部分兩部分：一部分：一部分按比例按比例地分配給各進(jìn)程；地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)優(yōu)先權(quán)，適當(dāng)?shù)卦鲞m當(dāng)?shù)卦黾蛹悠湎鄳?yīng)份額后，分配給各進(jìn)程。其相應(yīng)份額后，分配給各進(jìn)程。n在重要的系統(tǒng)，如在重要的系統(tǒng)，如實(shí)時(shí)控制系統(tǒng)實(shí)時(shí)控制系統(tǒng)，則可能是

26、，則可能是完全按優(yōu)先權(quán)完全按優(yōu)先權(quán)為各進(jìn)程分配其物理塊的。為各進(jìn)程分配其物理塊的。5.2.3 頁面調(diào)入策略頁面調(diào)入策略n調(diào)入頁面的時(shí)機(jī)調(diào)入頁面的時(shí)機(jī)n預(yù)調(diào)頁策略預(yù)調(diào)頁策略n采用一種以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁策略，將那采用一種以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問的頁面預(yù)先調(diào)些預(yù)計(jì)在不久之后便會(huì)被訪問的頁面預(yù)先調(diào)入內(nèi)存，成功率入內(nèi)存，成功率50%n請(qǐng)求調(diào)頁策略請(qǐng)求調(diào)頁策略n當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便提出時(shí)，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便提出請(qǐng)求，由請(qǐng)求，由OS將其所需頁面調(diào)入內(nèi)存將其所需頁面調(diào)入內(nèi)存n

27、目前的虛擬存儲(chǔ)中大多采用此種策略目前的虛擬存儲(chǔ)中大多采用此種策略5.2.3 頁面調(diào)入策略頁面調(diào)入策略n從何處調(diào)入頁面從何處調(diào)入頁面n外存分為兩部分外存分為兩部分n通常，對(duì)換區(qū)采用連續(xù)分配方式，文件采用離通常，對(duì)換區(qū)采用連續(xù)分配方式，文件采用離散分配方式。系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，散分配方式。系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，分成三種情況分成三種情況n系統(tǒng)擁有足夠的對(duì)換區(qū)空間系統(tǒng)擁有足夠的對(duì)換區(qū)空間n系統(tǒng)缺少足夠的對(duì)換區(qū)空間系統(tǒng)缺少足夠的對(duì)換區(qū)空間nUNIX方式方式5.2.3 頁面調(diào)入策略頁面調(diào)入策略n所需的頁面全部從對(duì)換區(qū)調(diào)入，以提高調(diào)頁速度。為所需的頁面全部從對(duì)換區(qū)調(diào)入，以提高調(diào)頁速度。為此，在

28、進(jìn)程運(yùn)行前，此，在進(jìn)程運(yùn)行前， 將與該進(jìn)程有關(guān)的文件，從文件將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。區(qū)拷貝到對(duì)換區(qū)。n凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。n對(duì)于那些可能被修改的部分，在將它們換出時(shí)，調(diào)到對(duì)于那些可能被修改的部分，在將它們換出時(shí)，調(diào)到對(duì)換區(qū)，以后需要時(shí)，再從對(duì)換區(qū)調(diào)入。對(duì)換區(qū)，以后需要時(shí)，再從對(duì)換區(qū)調(diào)入。5.2.3 頁面調(diào)入策略頁面調(diào)入策略n由于與進(jìn)程

29、有關(guān)的文件都放在文件區(qū)，故凡是由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。n由于由于UNIX系統(tǒng)允許頁面共享，因此，某進(jìn)程系統(tǒng)允許頁面共享，因此，某進(jìn)程所請(qǐng)求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，所請(qǐng)求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再從對(duì)換區(qū)調(diào)入。此時(shí)也就無須再從對(duì)換區(qū)調(diào)入。5.2.3 頁面調(diào)入策略頁面調(diào)入策略n頁面調(diào)入過程頁面調(diào)入過程n每當(dāng)程序

30、所要訪問的頁面未在內(nèi)存時(shí)，便向每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPU發(fā)出一發(fā)出一缺頁中斷缺頁中斷。 n查找所需頁在磁盤上的位置；查找所需頁在磁盤上的位置；n查找一空閑幀；查找一空閑幀；ni) 如果有空閑幀，那么就使用它；如果有空閑幀，那么就使用它；nii) 如果沒有空閑幀，那么就使用頁置換算法以如果沒有空閑幀，那么就使用頁置換算法以選擇一個(gè)選擇一個(gè)“犧牲犧牲”幀（幀（victim frame）；）；niii) 將將“犧牲犧牲”幀的內(nèi)容寫到磁盤上，改變頁表幀的內(nèi)容寫到磁盤上，改變頁表和幀表。和幀表。n將所需頁讀入（新）空閑幀，改變頁表和幀表；將所需頁讀入（新）空閑幀，改變頁表和幀表；n重啟

31、用戶進(jìn)程。重啟用戶進(jìn)程。請(qǐng)求分頁中的地址變換過程請(qǐng)求分頁中的地址變換過程缺頁中斷處理缺頁中斷處理保留保留CPU現(xiàn)場(chǎng)現(xiàn)場(chǎng)從外存中找到缺頁從外存中找到缺頁內(nèi)存滿否？?jī)?nèi)存滿否？選擇一頁換出選擇一頁換出該頁被修改否？該頁被修改否？將該頁寫回外存將該頁寫回外存啟動(dòng)啟動(dòng)I/O硬件硬件將一頁從外存換入內(nèi)存將一頁從外存換入內(nèi)存修改頁表修改頁表否否是是是是否否頁表項(xiàng)在快表中？頁表項(xiàng)在快表中？CPU檢索快表檢索快表訪問頁表訪問頁表否否頁在內(nèi)存？頁在內(nèi)存？修改訪問位和修改位修改訪問位和修改位形成物理地址形成物理地址地址變換結(jié)束地址變換結(jié)束否否頁號(hào)頁頁號(hào)頁表長(zhǎng)度表長(zhǎng)度?開始開始程序請(qǐng)求訪問一頁程序請(qǐng)求訪問一頁產(chǎn)生缺頁

32、中產(chǎn)生缺頁中斷請(qǐng)求調(diào)頁斷請(qǐng)求調(diào)頁修改快表修改快表是是越界中斷越界中斷是是是是OS命令命令CPU從外存讀缺頁從外存讀缺頁頁置換例子頁置換例子n訪問頁訪問頁f頁置換例子（頁置換例子（cont.）5.2.3 頁面調(diào)入策略頁面調(diào)入策略頁面調(diào)入頁面調(diào)入頁面在內(nèi)存頁面在內(nèi)存頁面未在內(nèi)存頁面未在內(nèi)存內(nèi)存能容納新頁內(nèi)存能容納新頁內(nèi)存已滿內(nèi)存已滿該頁未被修改過該頁未被修改過該頁已被修改該頁已被修改5.2.3 頁面調(diào)入策略頁面調(diào)入策略n缺頁率缺頁率n進(jìn)程在運(yùn)行過程中，訪問頁面失敗的次數(shù)進(jìn)程在運(yùn)行過程中，訪問頁面失敗的次數(shù)F F，與對(duì)頁面訪問次數(shù)與對(duì)頁面訪問次數(shù)A A的比值的比值f,f,即即n影響缺頁次數(shù)的因素影響

33、缺頁次數(shù)的因素n 分配給進(jìn)程的分配給進(jìn)程的物理頁面數(shù)物理頁面數(shù)n 頁面本身的頁面本身的大小大小n 程序的程序的編制方法編制方法n 頁面頁面淘汰算法淘汰算法5.3 頁面置換算法頁面置換算法n5.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法n5.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法n5.3.3 CLOCK置換算法置換算法n5.3.4 頁面緩存算法頁面緩存算法n5.3.5 訪問內(nèi)存的有效時(shí)間訪問內(nèi)存的有效時(shí)間5.3 頁面置換算法頁面置換算法n評(píng)價(jià)標(biāo)準(zhǔn)評(píng)價(jià)標(biāo)準(zhǔn)n最低的缺頁率。最低的缺頁率。n評(píng)價(jià)方法評(píng)價(jià)方法n通過運(yùn)行一個(gè)特殊的頁面引用串檢驗(yàn)算

34、法，計(jì)通過運(yùn)行一個(gè)特殊的頁面引用串檢驗(yàn)算法，計(jì)算其頁錯(cuò)誤率；算其頁錯(cuò)誤率；n基本條件：事先知道可用幀的數(shù)量；基本條件：事先知道可用幀的數(shù)量；n測(cè)試用例：可用幀的數(shù)量為測(cè)試用例：可用幀的數(shù)量為3，頁面引用串如，頁面引用串如下：下：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 15.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法n先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法 n選擇在內(nèi)存中選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)駐留時(shí)間最長(zhǎng)的頁并淘汰之。的頁并淘汰之。n優(yōu)點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存：實(shí)

35、現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。的頁面。n缺點(diǎn)缺點(diǎn)：與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)椋号c進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有在進(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，不能保全局變量、常用函數(shù)、例程等的頁面，不能保證這些頁面不被淘汰。證這些頁面不被淘汰。引用次序引用次序7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 177070120

36、1231230430420423頁幀（頁框）頁幀（頁框） 3次次 12次次 缺頁缺頁 0230130127127027015.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法n先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法1234125349 page faults213 4215 1324 51235.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法n先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法n引用頁：引用頁：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。n3個(gè)幀（每個(gè)進(jìn)程最多只有個(gè)幀（每個(gè)進(jìn)程最多只有3個(gè)頁面同

37、時(shí)在內(nèi)存）個(gè)頁面同時(shí)在內(nèi)存）n先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法n引用頁：引用頁：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。n4個(gè)幀個(gè)幀nBelady異常：幀越多，頁錯(cuò)誤越多。異常：幀越多，頁錯(cuò)誤越多。10 page faults1235124543213 4215 1324 512345.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法5.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法n最佳最佳(Optimal)置換算法置換算法n最佳置換算法是由最佳置換算法是由Belady于于1966年提出的一種年提出的

38、一種理論上理論上的算法。的算法。n其其所選擇的被淘汰頁面，將是所選擇的被淘汰頁面，將是以后永不使用以后永不使用的，的，或許是在或許是在最長(zhǎng)最長(zhǎng)(未來未來)時(shí)間時(shí)間內(nèi)內(nèi)不再被訪問不再被訪問的頁面。的頁面。n優(yōu)點(diǎn)優(yōu)點(diǎn)：采用最佳置換算法，通?？杀ＷC獲得最：采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。低的缺頁率。n缺點(diǎn)缺點(diǎn)：無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面：無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪一個(gè)頁面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問中，哪一個(gè)頁面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的。的。引用次序引用次序7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 177070120120324

39、3203201701頁幀（頁框）頁幀（頁框） 3次次 6次次 缺頁缺頁 5.3.1 先進(jìn)先出置換算法和最佳置換算法先進(jìn)先出置換算法和最佳置換算法n最佳最佳(Optimal)置換算法置換算法5.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法nLRU(Least Recently Used)置換算法的描述置換算法的描述n利用利用“最近的過去最近的過去”作為作為“最近的將來最近的將來”的近的近似，即，選擇最近最久未使用的頁面予以淘汰。似，即，選擇最近最久未使用的頁面予以淘汰。n選擇選擇最后一次訪問時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)最后一次訪問時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一的一頁并淘汰之。即淘汰

40、沒有使用的時(shí)間最長(zhǎng)的頁。頁并淘汰之。即淘汰沒有使用的時(shí)間最長(zhǎng)的頁。實(shí)現(xiàn)代價(jià)很高（時(shí)間戳或硬件方法）實(shí)現(xiàn)代價(jià)很高（時(shí)間戳或硬件方法）引用次序引用次序7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201203403402432頁幀（頁框）頁幀（頁框） 3次次 9次次 缺頁缺頁 0321321021075.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法nLRU(Least Recently Used)置換算法置換算法5.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法nLRU置換算法的硬件支持置換算法的硬件

41、支持n優(yōu)點(diǎn)：對(duì)于各種類型的程序都能適用；優(yōu)點(diǎn)：對(duì)于各種類型的程序都能適用；n缺點(diǎn)：要求系統(tǒng)具有較多的支持硬件，實(shí)現(xiàn)難度大；缺點(diǎn)：要求系統(tǒng)具有較多的支持硬件，實(shí)現(xiàn)難度大；n主要問題主要問題n 一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多久時(shí)間未被進(jìn)一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多久時(shí)間未被進(jìn)程訪問；程訪問；n 如何快速地知道哪一頁最近最久未使用的頁面。如何快速地知道哪一頁最近最久未使用的頁面。n硬件支持硬件支持n移位寄存器移位寄存器n棧棧5.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法nLRU置換算法的硬件支持置換算法的硬件支持n寄存器寄存器n為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況

42、，為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為器，可表示為 n訪問訪問時(shí)將時(shí)將Rn-1位置成位置成1，定時(shí)信號(hào)，定時(shí)信號(hào)每隔一時(shí)間每隔一時(shí)間間隔右移一位間隔右移一位，則具有，則具有最小數(shù)值最小數(shù)值的寄存器所的寄存器所對(duì)應(yīng)的頁面，對(duì)應(yīng)的頁面，就是最近最久未使用就是最近最久未使用的頁面的頁面R=Rn-1Rn-2Rn-3 R2R1R0 實(shí)頁實(shí)頁R7R6R5R4R3R2R1R0101010010210101100實(shí)頁實(shí)頁R7R6R5R4R3R2R1R010010100102010101100t0t1實(shí)頁實(shí)頁R7R6R5R

43、4R3R2R1R010001010012001010110t2實(shí)頁實(shí)頁R7R6R5R4R3R2R1R0110010100200101011訪問訪問1實(shí)頁實(shí)頁R7R6R5R4R3R2R1R010100101002000101011t35.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法5.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法n棧棧n訪問某頁時(shí)，將該頁面的頁號(hào)從棧中移出或直訪問某頁時(shí)，將該頁面的頁號(hào)從棧中移出或直至?？?，再依次入棧，最后訪問頁入棧頂。至?？?，再依次入棧，最后訪問頁入棧頂。47407470417040174107421074

44、120742107462107470710121265.3.2 最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法n最少使用最少使用(LFU: Least Frequently Used)置換算法置換算法n為內(nèi)存中的每個(gè)頁面設(shè)置一個(gè)為內(nèi)存中的每個(gè)頁面設(shè)置一個(gè)移位寄存器移位寄存器，用來記，用來記錄該頁面錄該頁面被訪問的頻率被訪問的頻率n該算法選擇在最近使用最少的頁面作為淘汰頁該算法選擇在最近使用最少的頁面作為淘汰頁n與最近最少用算法與最近最少用算法LRU的區(qū)別的區(qū)別n只考慮一段時(shí)間內(nèi)使用的次數(shù)，而不管其使用的只考慮一段時(shí)間內(nèi)使用的次數(shù)，而不管其使用的時(shí)間時(shí)間iR這種算法并不能真正反

45、映出頁面的使用情況，因在每一時(shí)間這種算法并不能真正反映出頁面的使用情況，因在每一時(shí)間間隔內(nèi)只是用寄存器的一位來記錄頁的使用情況，因此訪問間隔內(nèi)只是用寄存器的一位來記錄頁的使用情況，因此訪問1次和次和10000次是等效的。次是等效的。5.3.3 Clock置換算法置換算法n簡(jiǎn)單的簡(jiǎn)單的Clock置換算法置換算法（近似的近似的LRU） n為每頁設(shè)置一位為每頁設(shè)置一位訪問位訪問位，再將內(nèi)存中的所有頁，再將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個(gè)循環(huán)隊(duì)列。面都通過鏈接指針鏈成一個(gè)循環(huán)隊(duì)列。n當(dāng)某頁被訪問時(shí)，其訪問位被置當(dāng)某頁被訪問時(shí)，其訪問位被置1。n置換算法在選擇一頁淘汰時(shí)，只需檢查其訪問置換算法在選

46、擇一頁淘汰時(shí)，只需檢查其訪問位。位。頁號(hào)頁號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M外存地址外存地址 5.3.3 Clock置換算法置換算法n簡(jiǎn)單的簡(jiǎn)單的Clock置換算法置換算法n狀態(tài)位狀態(tài)位(存在位存在位)P。n修改位修改位M。表示該頁在調(diào)入內(nèi)存后是否被修改過。由。表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時(shí)就不須將該寫回到外存上；若未被修改，在置換該頁時(shí)就不須將該寫回到外存上；若已被修改，則必須將該頁重寫到外存上，以保證外若已被修改，則必須將該頁重寫到

47、外存上，以保證外存中所保留的始終是最新副本。存中所保留的始終是最新副本。n外存地址。外存地址。5.3.3 Clock置換算法置換算法n簡(jiǎn)單的簡(jiǎn)單的CLOCK置換算法置換算法n置換算法在選擇一頁淘汰時(shí)，只需檢查頁的置換算法在選擇一頁淘汰時(shí)，只需檢查頁的訪訪問位，是問位，是0換出，是換出，是1重新置重新置0且暫不換出，再且暫不換出，再按按FIFO檢查下一個(gè)頁面。檢查到最后一個(gè)頁檢查下一個(gè)頁面。檢查到最后一個(gè)頁面，若其訪問位仍為面，若其訪問位仍為1，則，則再返到隊(duì)首再返到隊(duì)首檢查。檢查。n由于該算法是循環(huán)地檢查各頁面的訪問情況，由于該算法是循環(huán)地檢查各頁面的訪問情況，故稱為故稱為CLOCK算法算法，

48、置換的是未使用過的頁，置換的是未使用過的頁，又稱為又稱為最近未用算法最近未用算法NRU（Not Recently Used）5.3.3 Clock置換算法置換算法n簡(jiǎn)單的簡(jiǎn)單的CLOCK置換算法置換算法入口入口查尋指針前進(jìn)一步，指查尋指針前進(jìn)一步，指向下一個(gè)表目向下一個(gè)表目頁面訪問位頁面訪問位0?選擇該頁面淘汰選擇該頁面淘汰是是返回返回置頁面訪置頁面訪問位問位“0”否否塊號(hào)塊號(hào)頁號(hào)頁號(hào)訪問位訪問位指針指針0124034215650711替換替換指針指針注意：是循環(huán)注意：是循環(huán)隊(duì)列！隊(duì)列！5.3.3 Clock置換算法置換算法5.3.3 Clock置換算法置換算法n改進(jìn)型改進(jìn)型Clock置換算法

49、置換算法n在將一個(gè)頁面換出時(shí)，如果該頁已被修改過，在將一個(gè)頁面換出時(shí)，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。改過，則不必將它拷回磁盤。n同時(shí)滿足兩條件的頁面作為首選淘汰的頁。同時(shí)滿足兩條件的頁面作為首選淘汰的頁。頁號(hào)頁號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M外存地址外存地址 5.3.3 Clock置換算法置換算法n改進(jìn)型改進(jìn)型Clock置換算法置換算法n狀態(tài)位狀態(tài)位(存在位存在位)P。n外存地址。外存地址。5.3.3 Clock置換算法置換算法n改進(jìn)型改進(jìn)型Clock置換算法

50、置換算法n考慮考慮使用情況使用情況和和置換代價(jià)，置換代價(jià)，換出的最好是未使用且未換出的最好是未使用且未被修改過的頁面被修改過的頁面n由由訪問位訪問位A和和修改位修改位M組合：組合：n1類類(A=0, M=0)：最近既未被訪問，又未被修改，是最近既未被訪問，又未被修改，是最佳淘汰頁；最佳淘汰頁；n2類類(A=0, M=1)：最近未被訪問，但已被修改，并不最近未被訪問，但已被修改，并不是很好的淘汰頁；是很好的淘汰頁；n3類類(A=1, M=0)：最近已被訪問，但未被修改，最近已被訪問，但未被修改， 該該頁有可能再被訪問；頁有可能再被訪問；n4類類(A=1, M=1)：最近已被訪問且被修改，該頁可能

51、：最近已被訪問且被修改，該頁可能再被訪問。再被訪問。5.3.3 Clock置換算法置換算法n改進(jìn)型改進(jìn)型Clock置換算法置換算法n執(zhí)行過程執(zhí)行過程n從指針?biāo)甘镜漠?dāng)前位置開始，從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊(duì)列，掃描循環(huán)隊(duì)列， 尋尋找找A=0且且M=0的頁面，的頁面， 將所遇到的第一個(gè)頁面作為將所遇到的第一個(gè)頁面作為所選中的淘汰頁。所選中的淘汰頁。 在在本次掃描期間不改變?cè)L問位本次掃描期間不改變?cè)L問位An如果第一步失敗，即查找一周后未遇到第一類頁面，如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，則開始第二輪掃描，尋找尋找A=0且且M=1的頁面，將所的頁面，將所遇到

52、的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描遇到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，期間，將所有掃描過的頁面的訪問位將所有掃描過的頁面的訪問位A都置都置0n如果第二步也失敗，亦即未找到第二類頁面，則將如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始指針返回到開始的位置，并將的位置，并將所有的訪問位所有的訪問位A復(fù)復(fù)0。 然后然后回到第一步?；氐降谝徊?。5.3.3 Clock置換算法置換算法n改進(jìn)型改進(jìn)型Clock置換算法置換算法-示例示例頁號(hào)頁號(hào)塊號(hào)塊號(hào)AM05001301210103111141411最佳淘汰頁最佳淘汰頁次佳淘汰頁次佳淘汰頁0005.3.4 頁面緩沖算法頁面緩

53、沖算法(PBA： Page Buffering Algorithm)n影響頁面換進(jìn)換出效率的若干因素影響頁面換進(jìn)換出效率的若干因素n頁面置換算法頁面置換算法n寫回磁盤的效率寫回磁盤的效率n讀入內(nèi)存的頻率讀入內(nèi)存的頻率5.3.4 頁面緩沖算法頁面緩沖算法(PBA： Page Buffering Algorithm)n頁面緩存算法頁面緩存算法PBAn采用了采用了可變分配可變分配和和局部置換局部置換方式，置換算法采用方式，置換算法采用FIFOn將一個(gè)被淘汰的頁放入將一個(gè)被淘汰的頁放入兩個(gè)鏈表中的一個(gè)，即如兩個(gè)鏈表中的一個(gè)，即如果頁面果頁面未被修改未被修改，就將它直接，就將它直接放進(jìn)空閑鏈表放進(jìn)空閑鏈

54、表中；中；否則，便放入否則，便放入已修改頁面的鏈表已修改頁面的鏈表中中 空閑鏈表空閑鏈表已修改鏈表已修改鏈表5.3.5 訪問內(nèi)存的有效時(shí)間訪問內(nèi)存的有效時(shí)間n頁面在內(nèi)存中，也在快表中頁面在內(nèi)存中，也在快表中nEAT=+n頁面在內(nèi)存中，不在快表中頁面在內(nèi)存中，不在快表中nEAT=+ +=2(+)n頁面不在內(nèi)存中頁面不在內(nèi)存中nEAT=+ += +2(+)n考慮缺頁率考慮缺頁率f，命中率，命中率nEAT=+ +(1- )+f(+ +)+(1-f)（+）5.4 “抖動(dòng)抖動(dòng)”與工作集與工作集n5.4.1 多道程序度與多道程序度與“抖動(dòng)抖動(dòng)”n5.4.2 工作集工作集n5.4.3 “抖動(dòng)抖動(dòng)”的預(yù)防方法

55、的預(yù)防方法5.4.1 多道程序度與多道程序度與“抖動(dòng)抖動(dòng)”n多道程序度與處理機(jī)的利用率多道程序度與處理機(jī)的利用率5.4.1 多道程序度與多道程序度與“抖動(dòng)抖動(dòng)”n抖動(dòng)，又稱為顛簸抖動(dòng)，又稱為顛簸n在虛存中，頁面在內(nèi)存與外存之間在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度頻繁調(diào)度，以至于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)以至于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng)。統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng)。n原因原因n頁面淘汰算法不合理頁面淘汰算法不合理n分配給進(jìn)程的物理頁面數(shù)太少分配給進(jìn)程的物理頁面數(shù)太少

56、5.4.2 工作集工作集n工作集的基本概念工作集的基本概念n1968年由年由Denning提出，并定義了局部模型。提出，并定義了局部模型。它表明進(jìn)程執(zhí)行時(shí)，從一個(gè)局部移到另一個(gè)局它表明進(jìn)程執(zhí)行時(shí)，從一個(gè)局部移到另一個(gè)局部。局部就是一個(gè)經(jīng)常使用的頁的集合。部。局部就是一個(gè)經(jīng)常使用的頁的集合。5.4.2 工作集工作集n缺頁率與物理內(nèi)存塊數(shù)的關(guān)系缺頁率與物理內(nèi)存塊數(shù)的關(guān)系5.4.2 工作集工作集n工作集的定義工作集的定義n工作集窗口（工作集窗口（Working set window）：最近）：最近個(gè)個(gè)頁面引用頁面引用n最近最近個(gè)引用的頁集合稱為工作集合個(gè)引用的頁集合稱為工作集合（Working se

57、t）nWSSi (進(jìn)程進(jìn)程Pi的工作集的工作集) = 最近所引用的所有頁最近所引用的所有頁面的總數(shù)（不同時(shí)刻值不同）面的總數(shù)（不同時(shí)刻值不同）n如果如果太小，則不能包含整個(gè)局部；太小，則不能包含整個(gè)局部；n如果如果太大，則可能包含多個(gè)局部；太大，則可能包含多個(gè)局部；n如果如果=，則包含了整個(gè)程序。，則包含了整個(gè)程序。5.4.2 工作集工作集n工作集的定義工作集的定義nD WSSi 表示總的幀需求量表示總的幀需求量nm=可分配的頁幀可分配的頁幀n如果如果 D 大于大于m，那么有的進(jìn)程就得不到足夠幀，那么有的進(jìn)程就得不到足夠幀，從而會(huì)出現(xiàn)顛簸從而會(huì)出現(xiàn)顛簸n策略：可以懸掛某些進(jìn)程，以消除顛簸現(xiàn)象策

58、略：可以懸掛某些進(jìn)程，以消除顛簸現(xiàn)象5.4.3 “抖動(dòng)抖動(dòng)”的預(yù)防方法的預(yù)防方法n采用局部置換策略采用局部置換策略n把抖動(dòng)影響局限在單個(gè)進(jìn)程內(nèi)把抖動(dòng)影響局限在單個(gè)進(jìn)程內(nèi)n把工作集算法融入到處理機(jī)調(diào)度中把工作集算法融入到處理機(jī)調(diào)度中n調(diào)度前檢查每個(gè)進(jìn)程在內(nèi)存中駐留頁面是否足夠多，調(diào)度前檢查每個(gè)進(jìn)程在內(nèi)存中駐留頁面是否足夠多，如果夠則調(diào)入新的作業(yè)，否則為缺頁率高的進(jìn)程增加如果夠則調(diào)入新的作業(yè)，否則為缺頁率高的進(jìn)程增加物理塊。物理塊。n利用利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率準(zhǔn)則調(diào)節(jié)缺頁率nL是缺頁之間的平均時(shí)間，是缺頁之間的平均時(shí)間，S處理一次缺頁的時(shí)間。處理一次缺頁的時(shí)間。n選擇暫停的進(jìn)程選擇暫停的進(jìn)程

59、n降低多道程序度降低多道程序度5.5 請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式n5.5.1 請(qǐng)求分段中的硬件支持請(qǐng)求分段中的硬件支持n5.5.2 分段的共享與保護(hù)分段的共享與保護(hù)5.5.1 請(qǐng)求分段中的硬件支持請(qǐng)求分段中的硬件支持n段表機(jī)制段表機(jī)制n存取方式存取方式 用于標(biāo)識(shí)本分段存取屬性是只執(zhí)行、只讀還用于標(biāo)識(shí)本分段存取屬性是只執(zhí)行、只讀還是允許讀是允許讀/寫寫n存在位存在位P 用于指示該段是否已調(diào)入內(nèi)存用于指示該段是否已調(diào)入內(nèi)存n訪問字段訪問字段A 用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或記錄本頁在最近多長(zhǎng)時(shí)間未被訪問或記錄本頁在最近多長(zhǎng)時(shí)間未被訪問n

60、修改位修改位M 表示該段在調(diào)入內(nèi)存后是否被修改過表示該段在調(diào)入內(nèi)存后是否被修改過n外存地址外存地址 本段在外存上的地址，盤塊塊號(hào)本段在外存上的地址，盤塊塊號(hào)n增補(bǔ)位增補(bǔ)位 本段在運(yùn)行過程中是否做過動(dòng)態(tài)增長(zhǎng)本段在運(yùn)行過程中是否做過動(dòng)態(tài)增長(zhǎng)段名段名 段長(zhǎng)段長(zhǎng) 段的段的基址基址 存取存取方式方式 訪問字訪問字段段A 修改修改位位M 存在存在位位P 增補(bǔ)增補(bǔ)位位 外存外存始址始址 5.5.1 請(qǐng)求分段中的硬件支持請(qǐng)求分段中的硬件支持n缺段中斷機(jī)構(gòu)缺段中斷機(jī)構(gòu)n每當(dāng)發(fā)現(xiàn)運(yùn)行進(jìn)程所要訪問的段尚未調(diào)入內(nèi)存每當(dāng)發(fā)現(xiàn)運(yùn)行進(jìn)程所要訪問的段尚未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號(hào)，時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生