頁(yè)面置換算法課件

第五章虛擬存儲(chǔ)器第五章虛擬存儲(chǔ)器本章要點(diǎn)（1/2）目標(biāo)：了解虛擬存儲(chǔ)器的相關(guān)概念和技術(shù)。虛擬存儲(chǔ)的基本概念為什么要引入虛擬存儲(chǔ)器？虛擬存儲(chǔ)器是如何擴(kuò)充內(nèi)存容量的？虛擬存儲(chǔ)器具有哪些特征？每種特征的具體含義是什么？它們相互之間存在著什么樣的關(guān)系？它們與離散分配之間又存在著什么樣的關(guān)系？實(shí)現(xiàn)虛擬存儲(chǔ)器的關(guān)鍵技術(shù)是什么？這些技術(shù)的實(shí)現(xiàn)需要得到哪些硬件支持和軟件支持？本章要點(diǎn)（1/2）目標(biāo)：了解虛擬存儲(chǔ)器的相關(guān)概念和技術(shù)。請(qǐng)求分頁(yè)系統(tǒng)的基本原理為實(shí)現(xiàn)虛擬存儲(chǔ)器，必須擴(kuò)充表項(xiàng)的內(nèi)容，除了內(nèi)存塊號(hào)和存取權(quán)限字段以外，頁(yè)表中還必須增加哪些字段，為什么要增加這些字段？請(qǐng)求分頁(yè)系統(tǒng)的地址變換也必須通過(guò)地址變換機(jī)構(gòu)進(jìn)行，請(qǐng)求分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)，是在基本分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上增加了哪些功能而形成？常用的頁(yè)面置換算法有哪些？為什么LRU算法具有比較好的性能？它的主要缺點(diǎn)是什么？可用什么方法實(shí)現(xiàn)LRU近似算法？本章要點(diǎn)（2/2）請(qǐng)求分頁(yè)系統(tǒng)的基本原理本章要點(diǎn)（2/2）5.1虛擬存儲(chǔ)器概述5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.3頁(yè)面置換算法5.4“抖動(dòng)”與工作集5.5請(qǐng)求分段存儲(chǔ)管理方式

本章內(nèi)容5.1虛擬存儲(chǔ)器概述本章內(nèi)容5.1虛擬存儲(chǔ)器概述5.1虛擬存儲(chǔ)器概述5.1虛擬存儲(chǔ)器概述簡(jiǎn)單存儲(chǔ)器管理方式，都要求將一個(gè)作業(yè)全部裝入內(nèi)存方能運(yùn)行。于是出現(xiàn)以下兩種情況：有的作業(yè)很大，所要求的內(nèi)存空間超過(guò)了內(nèi)存的總?cè)萘?；有大量的作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足，難以容納所有的作業(yè)。解決方法：從物理上增加內(nèi)容容量從邏輯上擴(kuò)充內(nèi)存容量5.1虛擬存儲(chǔ)器概述簡(jiǎn)單存儲(chǔ)器管理方式，都要求將一個(gè)作業(yè)全5.1.1常規(guī)存儲(chǔ)管理方式的特征和局部性原理簡(jiǎn)單存儲(chǔ)器的特征一次性：作業(yè)必須一次性全部裝入內(nèi)存才能開(kāi)始運(yùn)行，這是一種對(duì)內(nèi)存空間的浪費(fèi)。駐留性：作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存直至作業(yè)運(yùn)行結(jié)束，占據(jù)了寶貴的內(nèi)存資源一次性及駐留性帶來(lái)的問(wèn)題：會(huì)使許多在進(jìn)程運(yùn)行時(shí)不用的或暫時(shí)不用的程序（數(shù)據(jù)）占據(jù)大量的內(nèi)存空間;使一些需要運(yùn)行的作業(yè)無(wú)法裝入運(yùn)行。1、常規(guī)存儲(chǔ)器管理方式的特征5.1.1常規(guī)存儲(chǔ)管理方式的特征和局部性原理簡(jiǎn)單存儲(chǔ)器的特問(wèn)題的提出(P.Denning)程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短時(shí)間內(nèi)，程序的執(zhí)行僅限于某個(gè)部分；相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。論點(diǎn)程序在執(zhí)行時(shí)，大多數(shù)情況下是順序執(zhí)行的過(guò)程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一區(qū)域，但調(diào)用深度通常不超過(guò)5程序中存在許多循環(huán)結(jié)構(gòu)，它們雖由少數(shù)指令構(gòu)成，但多次執(zhí)行程序中對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，往往都局限于很小的范圍內(nèi)2、局部性原理一次性及駐留性是否是程序運(yùn)行時(shí)所必需的？問(wèn)題的提出(P.Denning)2、局部性原理一次性及駐留性局部性的表現(xiàn)方式時(shí)間局部性：一個(gè)數(shù)據(jù)結(jié)構(gòu)被訪問(wèn)，不久可能再次被訪問(wèn)。典型原因：程序中存在大量的循環(huán)操作空間局部性：一段時(shí)間訪問(wèn)的地址可能集中在一定范圍。典型原因：程序順序執(zhí)行2、局部性原理sum=0;for(i=0;i<n;i++) sum+=a[i];returnsum;局部性的表現(xiàn)方式2、局部性原理sum=0;1961年英國(guó)曼徹斯特大學(xué)Kilbrn等人提出70年代廣泛地應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)中目前許多微型機(jī)也開(kāi)始使用虛擬存儲(chǔ)器是進(jìn)一步完善主存-輔存存儲(chǔ)層次，解決主存容量提出的。實(shí)現(xiàn)思想：當(dāng)進(jìn)程運(yùn)行時(shí)，先將一部分程序裝入內(nèi)存，另一部分暫時(shí)留在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)，由系統(tǒng)自動(dòng)將它們從外存調(diào)入內(nèi)存。3、虛擬存儲(chǔ)器的基本工作情況1961年英國(guó)曼徹斯特大學(xué)Kilbrn等人提出3、虛擬存儲(chǔ)器什么是虛擬存儲(chǔ)？定義：具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。它把內(nèi)存與外存有機(jī)結(jié)合起來(lái)使用，構(gòu)成容量很大的“內(nèi)存”。目的：提高內(nèi)存利用率1、虛擬存儲(chǔ)器定義5.1.2虛擬存儲(chǔ)器的定義和特征什么是虛擬存儲(chǔ)？1、虛擬存儲(chǔ)器定義5.1.2虛擬存儲(chǔ)器的定虛擬存儲(chǔ)器管理應(yīng)解決以下問(wèn)題：主存和輔存的統(tǒng)一管理問(wèn)題邏輯地址到物理地址的轉(zhuǎn)換問(wèn)題部分裝入和部分對(duì)換問(wèn)題把哪一部分裝入內(nèi)存何時(shí)把頁(yè)面裝入裝入內(nèi)存什么位置當(dāng)內(nèi)存沒(méi)有空間時(shí)淘汰哪個(gè)頁(yè)面1、虛擬存儲(chǔ)器定義虛擬存儲(chǔ)器管理應(yīng)解決以下問(wèn)題：1、虛擬存儲(chǔ)器定義多次性：指一個(gè)作業(yè)中的程序和數(shù)據(jù)允許被分成多次調(diào)入內(nèi)存運(yùn)行，這是虛擬存儲(chǔ)器最重要的特征。對(duì)換性：指允許作業(yè)中的程序和數(shù)據(jù)在作業(yè)運(yùn)行過(guò)程中換入、換出。虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。這是虛擬存儲(chǔ)器表現(xiàn)出的最重要特征，是實(shí)現(xiàn)虛擬存儲(chǔ)器的最重要的目標(biāo)。虛擬性是以多次性和對(duì)換性為基礎(chǔ)，多次性和對(duì)換性是建立在離散分配的基礎(chǔ)上。2、虛擬存儲(chǔ)器的特征多次性：指一個(gè)作業(yè)中的程序和數(shù)據(jù)允許被分成多次調(diào)入內(nèi)存運(yùn)行，5.1.3虛擬存儲(chǔ)器的實(shí)現(xiàn)方法實(shí)現(xiàn)虛擬存儲(chǔ)的典型過(guò)程虛擬存儲(chǔ)器管理的技術(shù)支持必須有相應(yīng)的硬件支持，用以實(shí)現(xiàn)虛擬分頁(yè)和虛擬分段存儲(chǔ)管理；操作系統(tǒng)必須提供相應(yīng)的軟件支持，管理頁(yè)或段在內(nèi)存和外存之間的移動(dòng)。5.1.3虛擬存儲(chǔ)器的實(shí)現(xiàn)方法實(shí)現(xiàn)虛擬存儲(chǔ)的典型過(guò)程虛擬存在簡(jiǎn)單分頁(yè)基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能。置換時(shí)以頁(yè)面為單位進(jìn)行系統(tǒng)提供的硬件支持：請(qǐng)求分頁(yè)的頁(yè)表機(jī)制；缺頁(yè)中斷機(jī)構(gòu)；地址變換機(jī)構(gòu)。實(shí)現(xiàn)請(qǐng)求分頁(yè)的軟件：請(qǐng)求調(diào)頁(yè)軟件頁(yè)面置換軟件1、請(qǐng)求分頁(yè)系統(tǒng)

在簡(jiǎn)單分頁(yè)基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能。1、請(qǐng)求在分段的基礎(chǔ)上，增加了請(qǐng)求調(diào)段功能、分段置換功能置換時(shí)以段為單位進(jìn)行系統(tǒng)提供的硬件支持：請(qǐng)求分段的段表機(jī)制；缺段中斷機(jī)構(gòu)；地址變換機(jī)構(gòu)。實(shí)現(xiàn)請(qǐng)求分段的軟件：請(qǐng)求調(diào)段軟件段置換軟件2、請(qǐng)求分段系統(tǒng)

在分段的基礎(chǔ)上，增加了請(qǐng)求調(diào)段功能、分段置換功能2、請(qǐng)求分段5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式建立在基本分頁(yè)存儲(chǔ)管理之上，是目前比較常用的一種虛擬存儲(chǔ)管理技術(shù)5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式建立在基本分頁(yè)存儲(chǔ)管理之上，5.2.1請(qǐng)求分頁(yè)中的硬件支持1、請(qǐng)求頁(yè)表機(jī)制在請(qǐng)求分頁(yè)系統(tǒng)中所需要的主要數(shù)據(jù)結(jié)構(gòu)是請(qǐng)求頁(yè)表。作用：將用戶地址空間中的邏輯地址變換為內(nèi)存空間的物理地址。請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表項(xiàng)如下圖所示：頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址指示該頁(yè)是否已調(diào)入內(nèi)存記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或記錄本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，供選擇換出頁(yè)面時(shí)參考該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)，供置換頁(yè)面時(shí)參考指出該頁(yè)在外存上的地址，供調(diào)入該頁(yè)時(shí)參考5.2.1請(qǐng)求分頁(yè)中的硬件支持1、請(qǐng)求頁(yè)表機(jī)制頁(yè)號(hào)物理塊2、缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)與一般中斷相同的處理步驟：保護(hù)CPU環(huán)境、分析中斷原因、轉(zhuǎn)入中斷處理程序進(jìn)行處理、恢復(fù)CPU環(huán)境等幾個(gè)步驟。缺頁(yè)中斷和一般的中斷相比有如下區(qū)別：1）缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)；2）缺頁(yè)中斷返回到該指令的開(kāi)始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行；3）一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。2、缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)2.缺頁(yè)中斷機(jī)構(gòu)圖5-1涉及6次缺頁(yè)中斷的指令對(duì)硬件的要求：系統(tǒng)中的硬件機(jī)構(gòu)應(yīng)能夠保存多次中斷時(shí)的狀態(tài)，并保證最后能夠返回到中斷前產(chǎn)生缺頁(yè)中斷的指令處，繼續(xù)執(zhí)行。2.缺頁(yè)中斷機(jī)構(gòu)圖5-1涉及6次缺頁(yè)中斷的指令對(duì)硬圖5-2請(qǐng)求分頁(yè)中的地址變換過(guò)程3、地址變換機(jī)構(gòu)圖5-2請(qǐng)求分頁(yè)中的地址變換過(guò)程3、地址變換機(jī)構(gòu)5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配頁(yè)面分配原則缺頁(yè)中斷、I/O中斷頻繁會(huì)降低運(yùn)行效率，因此應(yīng)盡可能減少缺頁(yè)中斷的次數(shù)。為進(jìn)程分配物理塊時(shí)要考慮的問(wèn)題：保證進(jìn)程正常運(yùn)行所需要的最少物理塊；為進(jìn)程分配的物理塊數(shù)目是固定的還是可變的為進(jìn)程分配物理塊數(shù)是采取平均分配算法，還是根據(jù)進(jìn)程的大小比例予以分配。5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配頁(yè)面分配原則是指能保證進(jìn)程正常運(yùn)行所需最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。每個(gè)進(jìn)程的最小頁(yè)框數(shù)是由計(jì)算機(jī)結(jié)構(gòu)體系所定義的，最大數(shù)是由有效的物理內(nèi)存所定義的。PDP-11的移動(dòng)指令包括多個(gè)字，因此指令本身可能會(huì)跨2頁(yè)。另外，它的兩個(gè)操作數(shù)可能是間接引用，所以總共需要6個(gè)物理塊。

IBM370MVC指令。因?yàn)橹噶钍菑拇鎯?chǔ)器地址到存儲(chǔ)器地址，需要花費(fèi)6個(gè)字節(jié)，并且會(huì)跨2個(gè)頁(yè)面。要移動(dòng)的字符塊和將要移至的區(qū)域也都會(huì)跨2個(gè)頁(yè)面。這種情況就要求有6個(gè)頁(yè)框。1、最小物理塊數(shù)的確定是指能保證進(jìn)程正常運(yùn)行所需最小物理塊數(shù)。1、最小物理塊數(shù)的確分配策略：固定和可變分配策略。置換策略：全局置換和局部置換。三種適用的內(nèi)存分配策略：固定分配局部置換(FixedAllocation,LocalReplacement)可變分配全局置換(VariableAllocation,GlobalReplacement)可變分配局部置換(VariableAllocation,LocalReplacement)2、內(nèi)存分配策略

分配策略：固定和可變分配策略。2、內(nèi)存分配策略固定分配局部置換固定分配：為每個(gè)進(jìn)程分配固定數(shù)目的物理塊，整個(gè)運(yùn)行期間不再改變。局部置換：如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從在內(nèi)存中分配給該進(jìn)程的固定物理塊中選出一頁(yè)換出，然后再調(diào)入一頁(yè)。難點(diǎn)：為每個(gè)進(jìn)程分配多少物理塊難以確定太少，頻繁缺頁(yè)中斷，降低系統(tǒng)吞吐量。太多，內(nèi)存駐留進(jìn)程減少，可能造成資源空閑，而且實(shí)現(xiàn)進(jìn)程對(duì)換時(shí)，會(huì)花費(fèi)更多的時(shí)間。2、內(nèi)存分配策略

固定分配局部置換2、內(nèi)存分配策略可變分配全局置換（易于實(shí)現(xiàn)）可變分配：先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理塊，在進(jìn)程運(yùn)行期間可以適當(dāng)增減，而OS自身也保持一個(gè)空閑物理塊隊(duì)列。全局置換：當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)，由系統(tǒng)從空閑的物理塊隊(duì)列中，取出一物理塊分配該進(jìn)程，并將欲調(diào)入的缺頁(yè)裝入其中。當(dāng)空閑物理塊用完時(shí)，OS從內(nèi)存中任選一頁(yè)調(diào)出（任意進(jìn)程）。2、內(nèi)存分配策略

可變分配全局置換（易于實(shí)現(xiàn)）2、內(nèi)存分配策略可變分配局部置換根據(jù)進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的物理塊。當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的頁(yè)面中選擇一頁(yè)換出，這樣就不會(huì)影響其它進(jìn)程的運(yùn)行。如果進(jìn)程在運(yùn)行中頻繁地發(fā)生缺頁(yè)中斷，則系統(tǒng)再為該進(jìn)程分配附加的物理塊；反之，若一個(gè)進(jìn)程在運(yùn)行中缺頁(yè)頻率低，則此時(shí)適當(dāng)減少分配給該進(jìn)程的物理塊。2、內(nèi)存分配策略

可變分配局部置換2、內(nèi)存分配策略平均分配算法：物理塊平均分配給各進(jìn)程；缺點(diǎn)：未考慮到進(jìn)程本身的大小，不公平。按比例分配算法：按進(jìn)程大小的比例分配物理塊；n為系統(tǒng)內(nèi)的進(jìn)程數(shù)；Si為i進(jìn)程的頁(yè)面數(shù)；m為可用的物理塊總數(shù)；i進(jìn)程能分到的物理塊數(shù)為bi考慮優(yōu)先權(quán)的分配算法：按照作業(yè)的重要性、緊迫性進(jìn)行分配。一般將可供分配的物理塊分為兩部分：一部分按比例分配；另一部分按優(yōu)先權(quán)適當(dāng)增加份額。在重要的實(shí)時(shí)系統(tǒng)中，則可能是完全按優(yōu)先級(jí)為各進(jìn)程分配物理塊。3、物理塊分配算法

平均分配算法：物理塊平均分配給各進(jìn)程；3、物理塊分配算法5.2.3頁(yè)面調(diào)入策略應(yīng)解決從何時(shí)調(diào)入頁(yè)面、從何處調(diào)入頁(yè)面以及如何調(diào)入的問(wèn)題！1、何時(shí)調(diào)入頁(yè)面預(yù)調(diào)頁(yè)策略：根據(jù)空間局部性，將不久之后便會(huì)被訪問(wèn)的程序或數(shù)據(jù)所在的頁(yè)面，預(yù)先調(diào)入內(nèi)存。特點(diǎn)：預(yù)調(diào)頁(yè)的成功率僅有50%。主要用于進(jìn)程的首次調(diào)入。請(qǐng)求調(diào)頁(yè)策略：進(jìn)程在運(yùn)行時(shí)，發(fā)現(xiàn)其所訪問(wèn)的程序頁(yè)面不在內(nèi)存，請(qǐng)求系統(tǒng)將所需頁(yè)面調(diào)入內(nèi)存。特點(diǎn)：系統(tǒng)開(kāi)銷大；易實(shí)現(xiàn)。虛擬存儲(chǔ)器大多采用此策略。5.2.3頁(yè)面調(diào)入策略應(yīng)解決從何時(shí)調(diào)入頁(yè)面、從何處調(diào)入頁(yè)面

2、從何處調(diào)入頁(yè)面

系統(tǒng)有足夠的存儲(chǔ)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)的速度。系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；但對(duì)于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對(duì)換區(qū)，以后需要時(shí)再?gòu)膶?duì)換區(qū)調(diào)入。UNIX方式，凡是未運(yùn)行過(guò)的頁(yè)，都應(yīng)從文件區(qū)調(diào)入。對(duì)于曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，從對(duì)換區(qū)調(diào)入。2、從何處調(diào)入頁(yè)面系統(tǒng)有足夠的存儲(chǔ)空間，這時(shí)可以全部從缺頁(yè)中斷處理程序通過(guò)查找頁(yè)表，得到該頁(yè)所在外存的物理塊號(hào)。如果此時(shí)內(nèi)存空閑，能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須先按照某種置換算法，從內(nèi)存中選出一頁(yè)準(zhǔn)備換出；如果該頁(yè)未被修改過(guò)，可不必將頁(yè)寫入磁盤；但如果該頁(yè)已被修改，則必須將它重新寫入磁盤，然后再將缺頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，再將此頁(yè)表項(xiàng)寫入快表中。據(jù)修改后的頁(yè)表形成去訪問(wèn)數(shù)據(jù)的物理地址。3、頁(yè)面調(diào)入過(guò)程缺頁(yè)中斷處理程序通過(guò)查找頁(yè)表，得到該頁(yè)所在外存的物理塊號(hào)。3衡量指標(biāo)——缺頁(yè)率f假定作業(yè)p共計(jì)n頁(yè)，系統(tǒng)分配給它的主存塊為m(m<=n)。如果作業(yè)p在運(yùn)行中成功訪問(wèn)頁(yè)面的次數(shù)為S（所訪問(wèn)的頁(yè)面在主存中），不成功的訪問(wèn)次數(shù)為F，則總的訪問(wèn)次數(shù)為：A=S+Ff=F/A影響缺頁(yè)中斷率的因素：頁(yè)面大小、進(jìn)程所分配物理塊的數(shù)目、頁(yè)面替換算法、程序固有特性缺頁(yè)中斷處理時(shí)間：t=β×ta+(1-β)×tb其中被置換的頁(yè)面被修改的概率為β，缺頁(yè)中斷處理時(shí)間為ta，被置換頁(yè)面沒(méi)有被修改的缺頁(yè)中斷時(shí)間為tb。4、缺頁(yè)率衡量指標(biāo)——缺頁(yè)率f4、缺頁(yè)率5.3頁(yè)面置換算法5.3頁(yè)面置換算法5.3頁(yè)面置換算法在進(jìn)程運(yùn)行過(guò)程中，當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，則應(yīng)將它調(diào)入內(nèi)存。若此時(shí)內(nèi)存已無(wú)空閑空間，則應(yīng)選擇一頁(yè)調(diào)出。將哪個(gè)頁(yè)面調(diào)出，則須根據(jù)一定的算法來(lái)確定。功能：需要調(diào)入頁(yè)面時(shí)，選擇內(nèi)存中哪個(gè)物理頁(yè)面被置換，稱為replacementpolicy。不適當(dāng)?shù)乃惴赡軙?huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)”。抖動(dòng)：剛被換出的頁(yè)面很快又要被訪問(wèn)，需要重新調(diào)入，此時(shí)又需要再選一頁(yè)調(diào)出；而此剛被調(diào)出的頁(yè)很快又被訪問(wèn)，又需將它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分時(shí)間都花費(fèi)在頁(yè)面置換上，則稱該進(jìn)程發(fā)生了“抖動(dòng)”。5.3頁(yè)面置換算法在進(jìn)程運(yùn)行過(guò)程中，當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)5.3頁(yè)面置換算法目標(biāo)：把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面調(diào)出，通常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)；常用的頁(yè)面置換算法最佳置換算法(Optimal,OPT)先進(jìn)先出算法(FirstInFirstOut,FIFO)近期最久未用過(guò)算法（LeastRecentlyUsed,LRU）CLOCK置換算法（NotRecentlyUsed,NRU）頁(yè)面緩沖算法（PageBufferingAlgorithm,PBA）近期最少使用算法(LeastFrequentlyUsed,LFU)5.3頁(yè)面置換算法目標(biāo)：把未來(lái)不再使用的或短期內(nèi)較少使用的5.3.1最佳置換算法和先進(jìn)先出置換算法1、最佳置換算法（OPT）方法：根據(jù)未來(lái)使用情況將未來(lái)的近期里不用的頁(yè)替換出去。實(shí)現(xiàn)：確定要替換的時(shí)刻t。找出主存中每個(gè)頁(yè)將來(lái)要用到的時(shí)刻ti。ti-t最大的頁(yè)將被替換。特點(diǎn)：命中率高，但難于實(shí)現(xiàn)（必須運(yùn)行一遍，才能知道未來(lái)的時(shí)刻ti），是理想算法，用于評(píng)價(jià)其它替換算法。5.3.1最佳置換算法和先進(jìn)先出置換算法1、最佳置換算法（頁(yè)面

引用

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

7

7

7

2

2

2

2

2

7

0

0

0

0

4

0

0

0

物

理

塊

1

1

3

3

3

1

1

缺頁(yè)

x

x

x

x

x

x

x

x

x

置換

√

√

√

√

√

√

發(fā)生了6次頁(yè)面置換，9次缺頁(yè)中斷，總訪問(wèn)次數(shù)20次，缺頁(yè)率9/20＝45％

。1、最佳置換算法（OPT）圖5-3利用最佳頁(yè)面置換算法時(shí)的置換圖頁(yè)面引用701203042303方法：最早裝入主存的頁(yè)作為被替換的頁(yè)，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。實(shí)現(xiàn)：只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總可以指向最老的頁(yè)面。特點(diǎn)：利用歷史信息，但不反映程序的局部性（最先進(jìn)入的頁(yè)可能是現(xiàn)在經(jīng)常使用的頁(yè)）2、先進(jìn)先出(FIFO)頁(yè)面置換算法

方法：最早裝入主存的頁(yè)作為被替換的頁(yè)，即選擇在內(nèi)存中駐留時(shí)間發(fā)生了12次頁(yè)面置換，15次缺頁(yè)中斷，總訪問(wèn)次數(shù)20次，缺頁(yè)率15/20＝75％

。2、先進(jìn)先出(FIFO)頁(yè)面置換算法

頁(yè)面引用

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

7

7

7

2

2

2

4

4

4

0

0

0

7

7

7

0

0

0

3

3

3

2

2

2

1

1

1

0

0

物理塊

1

1

1

0

0

0

3

3

3

2

2

2

1

缺頁(yè)

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

圖5-4利用FIFO置換算法時(shí)的置換圖發(fā)生了12次頁(yè)面置換，15次缺頁(yè)中斷，總訪問(wèn)次數(shù)20次，缺頁(yè)5.3.2最近最久未使用和最少使用置換算法方法：近期最久未訪問(wèn)過(guò)的頁(yè)作為被替換的頁(yè)實(shí)現(xiàn)：賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的頁(yè)面予以淘汰。特點(diǎn)：計(jì)數(shù)器硬件較少，主存頁(yè)面表可由軟硬件實(shí)現(xiàn)修改，根據(jù)“歷史”預(yù)測(cè)“未來(lái)”。1、LRU(LeastRecentlyUsed)置換算法的描述5.3.2最近最久未使用和最少使用置換算法方法：近期最久未1、LRU(LeastRecentlyUsed)置換算法的描述7

7

7

2

2

4

4

4

0

1

1

1

0

0

0

0

0

0

3

3

3

0

0

物理塊

1

1

3

3

2

2

2

2

2

7

缺頁(yè)

x

x

x

x

x

x

x

x

x

x

x

x

頁(yè)面引用

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

發(fā)生了9次頁(yè)面置換，12次缺頁(yè)中斷，總訪問(wèn)次數(shù)20次，缺頁(yè)率12/20＝60％

。圖5-5利用LRU頁(yè)面置換算法時(shí)的置換圖1、LRU(LeastRecentlyUsed)置換算法LRU硬件機(jī)構(gòu)如下：每個(gè)頁(yè)面設(shè)立移位寄存器：被訪問(wèn)時(shí)左邊最高位置1，定期右移并且最高位補(bǔ)0，于是寄存器數(shù)值最小的是最久未使用頁(yè)面。一個(gè)特殊的棧：把被訪問(wèn)的頁(yè)面移到棧頂，于是棧底的是最久未使用頁(yè)面。2、LRU置換算法的硬件支持LRU硬件機(jī)構(gòu)如下：2、LRU置換算法的硬件支持圖5-6某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況圖5-6某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況2233222311235512225144255542圖5-7用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況335422355523225322323223123152512251425452543354235253522352×××××××2233222311235512225144255542圖5選擇到當(dāng)前時(shí)間為止被訪問(wèn)次數(shù)最少的頁(yè)面被置換；每頁(yè)設(shè)置移位寄存器，每當(dāng)頁(yè)面被訪問(wèn)時(shí)，將該移位寄存器的最高位置1，再每隔一定時(shí)間右移一次；發(fā)生缺頁(yè)中斷時(shí)，淘汰最小的頁(yè)面。這種算法不能真正反映出頁(yè)面的使用情況，因?yàn)樵诿恳粫r(shí)間間隔內(nèi)，只是用寄存器的一位來(lái)記錄頁(yè)面的使用情況，在該時(shí)間間隔內(nèi)，對(duì)某頁(yè)訪問(wèn)一次和訪問(wèn)1000次是完全等效的。3、最少使用(LFU：LeastFrequentlyUsed)置換算法選擇到當(dāng)前時(shí)間為止被訪問(wèn)次數(shù)最少的頁(yè)面被置換；3、最少使用(5.3.3Clock置換算法1、簡(jiǎn)單的Clock置換算法每頁(yè)設(shè)置一位訪問(wèn)位，若該頁(yè)被訪問(wèn)則其訪問(wèn)位被置1；內(nèi)存中所有頁(yè)面都通過(guò)鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列，置換時(shí)采用一個(gè)指針，從當(dāng)前指針位置開(kāi)始按地址先后檢查各頁(yè)，尋找訪問(wèn)位為0的頁(yè)面作為被置換頁(yè)；指針經(jīng)過(guò)的訪問(wèn)位為1的頁(yè)都將其訪問(wèn)位置0，最后指針停留在被置換頁(yè)的下一個(gè)頁(yè)。5.3.3Clock置換算法1、簡(jiǎn)單的Clock置換算法1、簡(jiǎn)單的Clock置換算法圖5-8簡(jiǎn)單Clock置換算法的流程入口查詢指針前進(jìn)一步，指向下一個(gè)表目選擇該頁(yè)面淘汰返回頁(yè)面使用位=0？置頁(yè)面使用位=0NY1、簡(jiǎn)單的Clock置換算法圖5-8簡(jiǎn)單Clock置換1、簡(jiǎn)單的Clock置換算法

1、簡(jiǎn)單的Clock置換算法1、簡(jiǎn)單的Clock置換算法

1、簡(jiǎn)單的Clock置換算法在將一個(gè)頁(yè)面換出時(shí)，對(duì)于修改過(guò)的頁(yè)面在換出時(shí)所付出的開(kāi)銷將比未修改過(guò)的頁(yè)面開(kāi)銷大。在改進(jìn)型Clock算法中，它既考慮到頁(yè)面的使用情況，又考慮頁(yè)面是否被修改過(guò)。即選擇換出頁(yè)面時(shí)，既要是未使用過(guò)的頁(yè)面，又要是未修改過(guò)的頁(yè)面，把同時(shí)滿足兩條件的頁(yè)面作為首選淘汰頁(yè)。訪問(wèn)位A

和修改位M

的四種組合情況：1類（A=0，M=0）：表示該頁(yè)最近既未被訪問(wèn)，又未被修改，是最佳淘汰頁(yè)2類（A=0，M=1）：表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好的淘汰頁(yè)3類（A=1，M=0）：最近已被訪問(wèn)，但未被修改，該頁(yè)有可能再被訪問(wèn)4類（A=1，M=1）：最近已被訪問(wèn)且被修改，該頁(yè)可能再被訪問(wèn)2、改進(jìn)型Clock置換算法

在將一個(gè)頁(yè)面換出時(shí)，對(duì)于修改過(guò)的頁(yè)面在換出時(shí)所付出的開(kāi)銷將比執(zhí)行過(guò)程：第一步，尋找第一類頁(yè)面(不修改A)；第二步，第一步失敗，尋找第二類頁(yè)面，同時(shí)置訪問(wèn)過(guò)的A=0；第三步，重復(fù)第一步或第二步，此時(shí)必能找到。特點(diǎn)：（與簡(jiǎn)單Clock算法比較）可減少磁盤I/O操作次數(shù)；可能須經(jīng)幾次掃描才能找到可置換的頁(yè),系統(tǒng)開(kāi)銷增加。2、改進(jìn)型Clock置換算法

執(zhí)行過(guò)程：2、改進(jìn)型Clock置換算法2、改進(jìn)型Clock置換算法

2、改進(jìn)型Clock置換算法頁(yè)面置換算法課件5.3.4頁(yè)面緩沖算法頁(yè)面置換算法寫回磁盤的頻率建立一個(gè)已修改換出頁(yè)面的鏈表，采用集中寫回的方式讀入內(nèi)存的頻率修改后未寫回磁盤的頁(yè)面，可以直接從已修改換出頁(yè)面鏈表中獲取1、影響頁(yè)面換進(jìn)換出效率的若干因素5.3.4頁(yè)面緩沖算法頁(yè)面置換算法1、影響頁(yè)面換進(jìn)換出效2、頁(yè)面緩沖算法(PBA：PageBufferingAlgorithm)內(nèi)存分配策略：可變分配局部置換被置換頁(yè)面的選擇和處理：用FIFO算法選擇被置換頁(yè)，把被置換的頁(yè)面放入兩個(gè)鏈表之一。如果頁(yè)面未被修改，就將其歸入到空閑頁(yè)面鏈表的末尾；否則將其歸入到已修改頁(yè)面鏈表。PBA算法的特點(diǎn)：顯著降低了頁(yè)面換進(jìn)、換出的頻率，減少磁盤I/O次數(shù)；置換策略簡(jiǎn)單，無(wú)須硬件支持，實(shí)現(xiàn)簡(jiǎn)單。2、頁(yè)面緩沖算法(PBA：PageBufferingA3、訪問(wèn)內(nèi)存的有效時(shí)間

請(qǐng)求分布管理方式的內(nèi)存有效訪問(wèn)時(shí)間：被訪問(wèn)的頁(yè)在內(nèi)存中，且其對(duì)應(yīng)的頁(yè)表項(xiàng)在快表中EAT=λ+t被訪問(wèn)的頁(yè)在內(nèi)存中，且其對(duì)應(yīng)的頁(yè)表項(xiàng)不在快表中EAT=2(λ+t)被訪問(wèn)的頁(yè)不在內(nèi)存中EAT=ε+2(λ+t)考慮快表的命中率和缺頁(yè)率EAT=λ+a×t+(1-a)×[t+f×(ε+λ+t)+(1-f)×(λ+t)]其中：λ為查找快表的時(shí)間；t為訪問(wèn)實(shí)際物理地址所需的時(shí)間；ε為缺頁(yè)中斷處理時(shí)間；a為快表命中率；f為缺頁(yè)率。3、訪問(wèn)內(nèi)存的有效時(shí)間請(qǐng)求分布管理方式的內(nèi)存有效訪問(wèn)時(shí)間5.4“抖動(dòng)”與工作集5.4“抖動(dòng)”與工作集5.4.1多道程序度與“抖動(dòng)”1、多道程序度與處理機(jī)利用率

圖5-9處理機(jī)的利用率5.4.1多道程序度與“抖動(dòng)”1、多道程序度與處理機(jī)利用產(chǎn)生抖動(dòng)的原因：同時(shí)在系統(tǒng)中運(yùn)行的進(jìn)程太多，由此分配給每一個(gè)進(jìn)程的物理塊太少，不能滿足進(jìn)程正常運(yùn)行的基本要求，致使每個(gè)進(jìn)程在運(yùn)行時(shí)，頻繁地出現(xiàn)缺頁(yè)。這種頻繁的換進(jìn)換出的活動(dòng)被稱為抖動(dòng)。如果一個(gè)進(jìn)程花費(fèi)在頁(yè)面置換的時(shí)間多于執(zhí)行時(shí)間，就是抖動(dòng)。2、產(chǎn)生“抖動(dòng)”的原因產(chǎn)生抖動(dòng)的原因：同時(shí)在系統(tǒng)中運(yùn)行的進(jìn)程太多，由此分配給每一個(gè)5.4.2工作集1、工作集的基本概念

進(jìn)程發(fā)生缺頁(yè)率的時(shí)間間隔與進(jìn)程獲得的物理塊數(shù)有關(guān)。工作集理論：1968年由Denning提出并推廣理論基礎(chǔ)：程序運(yùn)行時(shí)的局部性原理現(xiàn)象：程序在運(yùn)行期間，對(duì)頁(yè)面的訪問(wèn)是不均勻的，在一段時(shí)間內(nèi)僅局限于較少的頁(yè)面，在另一段時(shí)間內(nèi)，又可能局限于另一些較少的頁(yè)面進(jìn)行訪問(wèn)。5.4.2工作集1、工作集的基本概念進(jìn)程發(fā)生缺頁(yè)率的2、工作集的定義

工作集：是指在某段時(shí)間間隔里，進(jìn)程實(shí)際所要訪問(wèn)頁(yè)面的集合。工作集的產(chǎn)生：屬于預(yù)調(diào)頁(yè)策略，用程序過(guò)去某段時(shí)間內(nèi)的行為作為程序在將來(lái)某段時(shí)間內(nèi)行為的近似。進(jìn)程在時(shí)間t的工作集記作w(t,Δ)工作集的定義：進(jìn)程在時(shí)間間隔（t-Δ,t）中引用頁(yè)面的集合變量Δ為工作集的“窗口尺寸”。假定Δ=102、工作集的定義工作集：是指在某段時(shí)間間隔里，進(jìn)程實(shí)際所5.4.3“抖動(dòng)”的預(yù)防方法將“抖動(dòng)”造成的影響限制在較小的范圍效果不佳，“抖動(dòng)”進(jìn)程會(huì)延長(zhǎng)其他進(jìn)程缺頁(yè)的中斷的處理時(shí)間確定造成處理機(jī)利用率低的原因多道度不夠內(nèi)存中分配給已有作業(yè)的物理塊數(shù)不夠1、采用局部置換策略2、把工作集算法融入到處理機(jī)調(diào)度中5.4.3“抖動(dòng)”的預(yù)防方法將“抖動(dòng)”造成的影響限制在較L為缺頁(yè)之間的平均時(shí)間；S為平均缺頁(yè)服務(wù)時(shí)間L>>S，表示很少發(fā)生缺頁(yè)L<S，表示頻繁發(fā)生缺頁(yè)L≈S，表示磁盤與處理機(jī)均能達(dá)到它們的最大利用率當(dāng)多道程序度偏高，影響到處理機(jī)的利用率，則應(yīng)選擇掛起某些當(dāng)前活動(dòng)的進(jìn)程，將它們對(duì)換至外存。首先選擇優(yōu)先級(jí)最低的進(jìn)程其次選擇優(yōu)先級(jí)較低的進(jìn)程再選擇并不十分重要、但卻較大的進(jìn)程選擇剩余執(zhí)行時(shí)間最多的進(jìn)程……3、利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁(yè)率4、選擇暫停的進(jìn)程L為缺頁(yè)之間的平均時(shí)間；S為平均缺頁(yè)服務(wù)時(shí)間3、利用“L=S5.5請(qǐng)求分段存儲(chǔ)管理方式5.5請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段式管理需要請(qǐng)求段表機(jī)制、缺段中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。1、請(qǐng)求段表機(jī)制請(qǐng)求段表是請(qǐng)求分段管理方式的主要數(shù)據(jù)結(jié)構(gòu)。請(qǐng)求分段的段表項(xiàng)如圖所示。5.5.1請(qǐng)求分段中的硬件支持段名段長(zhǎng)段基址存取方式訪問(wèn)字段A修改字段M存在位P增補(bǔ)位外存始址請(qǐng)求分段式管理需要請(qǐng)求段表機(jī)制、缺段中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)在請(qǐng)求分段系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。進(jìn)程訪問(wèn)的段不在內(nèi)存，缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號(hào)，進(jìn)入OS后由缺段中斷處理程序?qū)⑺钡亩握{(diào)入內(nèi)存。2、缺段中斷機(jī)構(gòu)

在請(qǐng)求分段系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。2、缺段中斷機(jī)構(gòu)圖5-12請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程2、缺段中斷機(jī)構(gòu)

圖5-12請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程2、缺段中斷機(jī)構(gòu)缺段中段