第五章虛擬存儲器,重點(diǎn)理解虛擬存儲器的基本概念掌握請求分頁系統(tǒng)的基本原理掌握頁面置換算法頁面抖動的工作集模型難點(diǎn)請求分頁系統(tǒng)的地址轉(zhuǎn)換頁面置換算法,第五章虛擬存儲器,知識點(diǎn)虛擬存儲器的基本概念、特征頁面置換技術(shù)請求分頁系統(tǒng)，頁表機(jī)制、地址變換頁面置換算法頁面抖動工作集模型,第五章虛擬存儲器,5.1虛擬存儲器概述5.2請求分頁存儲管理方式5.3頁面置換算法5.4“抖動”與工作集5.5請求分段存儲管理方式,5.1虛擬存儲器概述,5.1.1常規(guī)存儲管理方式的特征和局部性原理5.1.2虛擬存儲器的定義和特征5.1.3虛擬存儲器的實(shí)現(xiàn)方法,5.1.1常規(guī)存儲管理方式的特征和局部性原理,連續(xù)分配,離散分配,(基本)分頁,(基本)分段,段頁式,方便程序裝入提高內(nèi)存利用率,程序裝入內(nèi)存時可能出現(xiàn)的問題程序太大，要求的空間超出了內(nèi)存總?cè)萘看罅孔鳂I(yè)要求運(yùn)行，但內(nèi)存不能容下所有作業(yè)常規(guī)存儲器管理方式的特征一次性要求作業(yè)全部裝入內(nèi)存才能運(yùn)行駐留性程序裝入內(nèi)存后便一直駐留內(nèi)存，直至運(yùn)行結(jié)束,許多不用或暫時不用的程序占用了大量內(nèi)存空間，而其他程序卻無法裝入！是否必要？,5.1.1常規(guī)存儲管理方式的特征和局部性原理,局部性原理（1968年，Denning.P）程序執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的；過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5；程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行；程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi),5.1.1常規(guī)存儲管理方式的特征和局部性原理,局限性的表現(xiàn)時間局限性某條指令被執(zhí)行=不久以后該指令可能再次執(zhí)行數(shù)據(jù)被訪問過=不久以后該數(shù)據(jù)可能再次被訪問典型原因：因在程序中存在著大量循環(huán)操作空間局限性存儲單元被訪問=不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)典型情況：程序的順序執(zhí)行。,5.1.1常規(guī)存儲管理方式的特征和局部性原理,虛擬存儲器的基本工作情況程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換。虛擬存儲器支持多道程序設(shè)計技術(shù),5.1.1常規(guī)存儲管理方式的特征和局部性原理,5.1.2虛擬存儲器的定義和特征,虛擬存儲器定義具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而其成本卻又接近于外存。注意：虛擬存儲器的最大容量是由計算機(jī)的地址結(jié)構(gòu)確定的。如：若CPU的有效地址長度為32位，則程序可以尋址范圍是0(232-1)，即虛存容量為4GB。,5.1.2虛擬存儲器的定義和特征,虛擬存儲器的特征多次性一個作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行對換性允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出虛擬性能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量注意：以CPU時間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。,5.1.3虛擬存儲器的實(shí)現(xiàn)方法,虛擬存儲器的實(shí)現(xiàn)建立在離散分配的存儲管理方式基礎(chǔ)上。主要實(shí)現(xiàn)方式請求分頁系統(tǒng)請求分段系統(tǒng),5.1.3虛擬存儲器的實(shí)現(xiàn)方法,請求分頁系統(tǒng)：在分頁系統(tǒng)的基礎(chǔ)上增加了請求調(diào)頁功能和頁面置換功能硬件支持頁表機(jī)制。在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；缺頁中斷機(jī)構(gòu)。每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；地址變換機(jī)構(gòu)。在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的軟件支持實(shí)現(xiàn)請求調(diào)頁的軟件和實(shí)現(xiàn)頁面置換的軟件,5.1.3虛擬存儲器的實(shí)現(xiàn)方法,請求分段系統(tǒng)系統(tǒng)同樣需要必要的硬件支持：段表機(jī)制。在純分段的段表機(jī)制基礎(chǔ)上，增加若干項(xiàng)而形成的；缺段中斷機(jī)構(gòu)。每當(dāng)用戶程序所要訪問的段尚未調(diào)入內(nèi)存時，產(chǎn)生一缺段中斷，請求OS將所缺的段調(diào)入內(nèi)存；地址變換機(jī)構(gòu)。與請求調(diào)頁類似，實(shí)現(xiàn)請求調(diào)段和置換功能也需要得到OS的支持。,5.2請求分頁存儲管理方式,5.2.1請求分頁中的硬件支持5.2.2請求式分頁中的內(nèi)存分配5.2.3頁面調(diào)入策略,5.2.1請求分頁中的硬件支持,系統(tǒng)需要解決的問題如何獲知進(jìn)程當(dāng)前所需頁面不在主存？如何把所缺頁面調(diào)入主存？采用什么策略選擇欲淘汰的頁面？當(dāng)主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去。,5.2.1請求分頁中的硬件支持,請求頁表機(jī)制狀態(tài)位P（中斷位）指示該頁是在內(nèi)存還是在外存訪問位A用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)或記錄本頁在最近多長時間未被訪問修改位M表示該頁在內(nèi)存中是否被修改過外存地址該頁在外存上的地址，通常是物理塊號。,5.2.1請求分頁中的硬件支持,缺頁中斷機(jī)構(gòu)在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷。相應(yīng)的中斷處理程序把控制轉(zhuǎn)向缺頁中斷子程序，執(zhí)行此子程序，即把所缺頁面裝入主存，然后處理機(jī)重新執(zhí)行缺頁時打斷的指令。這時，就將順利形成物理地址。缺頁中斷與一般中斷的區(qū)別在指令執(zhí)行期間產(chǎn)生和處理中斷信號一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。,涉及6次缺頁中斷的指令,例.COPY,能夠移動256B塊可能跨越頁邊界；移動部分字符后出現(xiàn)頁錯誤；如果源和目的塊有重疊，源塊可能已被修改。解決方案試圖存取兩個塊的兩端；使用臨時寄存器保存被覆蓋位置的值。,5.2.1請求分頁中的硬件支持,5.2.1請求分頁中的硬件支持,地址變換機(jī)構(gòu)在分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上，增加實(shí)現(xiàn)虛擬存儲器某些功能形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等。地址變換過程檢索快表，試圖從中找出所要訪問的頁。若找到，便修改頁表項(xiàng)中的訪問位。對于寫指令，還須將修改位置成“1”；然后利用頁表項(xiàng)中給出的物理塊號和頁內(nèi)地址形成物理地址，結(jié)束。內(nèi)存中去查找頁表，再從找到的頁表項(xiàng)中的狀態(tài)位P，來了解該頁是否已調(diào)入內(nèi)存。,請求分頁中的地址變換過程,5.2.2請求分頁中的內(nèi)存分配,最小物理塊數(shù)的確定指保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)分配的物理塊數(shù)少于此值時，進(jìn)程將無法運(yùn)行與計算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式單地址指令且采用直接尋址方式的機(jī)器，則所需最少2個物理塊。其中，一塊存放指令頁面，另一塊則存放數(shù)據(jù)頁面允許間接尋址的機(jī)器，至少要求有3個物理塊兩個或多于兩個字節(jié)指令的機(jī)器，其指令本身可能跨兩個頁面，且源和目標(biāo)地址所涉及的區(qū)域也可能跨兩個頁面，至少需要6個物理塊,5.2.2請求分頁中的內(nèi)存分配,最小物理塊數(shù)的確定不同的作業(yè)要求不同。如：允許間接尋址：則至少要求3個物理塊。MovA,BLoad1,1000直接尋址方式，則所需的最少物理塊數(shù)為2,5.2.2請求分頁中的內(nèi)存分配,物理塊的分配策略在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略固定分配局部置換(FixedAllocation,LocalReplacement)可變分配全局置換(VariableAllocation,GlobalReplacement)可變分配局部置換(VariableAllocation,LocalReplacemen,問題：分配塊數(shù)難確定，太少，缺頁頻繁，吞吐量降低；太多，內(nèi)存駐留進(jìn)程數(shù)減少，CPU或其它資源可能空閑,先分配給各進(jìn)程一定數(shù)的物理塊，系統(tǒng)有一空閑物理塊隊(duì)列，缺頁時從空閑隊(duì)列取，若空閑隊(duì)列空時，再選頁調(diào)出,先分配給各進(jìn)程一定數(shù)的物理塊，缺頁時從該進(jìn)程在內(nèi)存的頁選一換出，若其頻繁缺頁，系統(tǒng)再分配若干附加物理塊,5.2.2請求分頁中的內(nèi)存分配,物理塊分配算法平均分配算法將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進(jìn)程例：當(dāng)系統(tǒng)中有100個物理塊，有5個進(jìn)程在運(yùn)行時，每個進(jìn)程可分得20個物理塊。不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個進(jìn)程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進(jìn)程只有10頁，卻有10個物理塊閑置未用,5.2.2請求分頁中的內(nèi)存分配,物理塊分配算法按比例分配算法根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)為bi，將有：b應(yīng)該取整，它必須大于最小物理塊數(shù),5.2.2請求分頁中的內(nèi)存分配,物理塊分配算法考慮優(yōu)先權(quán)的分配算法在實(shí)際應(yīng)用中，為了使重要的、緊迫的用戶程序能盡快地完成，為它分配較多的內(nèi)存空間。通常方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在重要的系統(tǒng)，如實(shí)時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)為各進(jìn)程分配其物理塊的。,5.2.3頁面調(diào)入策略,調(diào)入頁面的時機(jī)預(yù)調(diào)頁策略采用一種以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計在不久之后便會被訪問的頁面預(yù)先調(diào)入內(nèi)存，成功率50%請求調(diào)頁策略當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便提出請求，由OS將其所需頁面調(diào)入內(nèi)存目前的虛擬存儲中大多采用此種策略,5.2.3頁面調(diào)入策略,從何處調(diào)入頁面外存分為兩部分用于存放文件的文件區(qū)用于存放對換頁面的對換區(qū)通常，對換區(qū)采用連續(xù)分配方式，文件采用離散分配方式。系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，分成三種情況系統(tǒng)擁有足夠的對換區(qū)空間系統(tǒng)缺少足夠的對換區(qū)空間UNIX方式,5.2.3頁面調(diào)入策略,系統(tǒng)擁有足夠的對換區(qū)空間所需的頁面全部從對換區(qū)調(diào)入，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前，將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。系統(tǒng)缺少足夠的對換區(qū)空間凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時，由于它們未被修改而不必再將它們換出，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。對于那些可能被修改的部分，在將它們換出時，調(diào)到對換區(qū)，以后需要時，再從對換區(qū)調(diào)入。,5.2.3頁面調(diào)入策略,UNIX方式由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。,5.2.3頁面調(diào)入策略,頁面調(diào)入過程每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷。查找所需頁在磁盤上的位置；查找一空閑幀；i)如果有空閑幀，那么就使用它；ii)如果沒有空閑幀，那么就使用頁置換算法以選擇一個“犧牲”幀（victimframe）；iii)將“犧牲”幀的內(nèi)容寫到磁盤上，改變頁表和幀表。將所需頁讀入（新）空閑幀，改變頁表和幀表；重啟用戶進(jìn)程。,請求分頁中的地址變換過程,頁置換例子,訪問頁f,頁置換例子（cont.）,5.2.3頁面調(diào)入策略,頁面調(diào)入,頁面在內(nèi)存,頁面未在內(nèi)存,內(nèi)存能容納新頁,內(nèi)存已滿,該頁未被修改過,該頁已被修改,缺頁中斷,置換算法,寫回磁盤,5.2.3頁面調(diào)入策略,缺頁率進(jìn)程在運(yùn)行過程中，訪問頁面失敗的次數(shù)F，與對頁面訪問次數(shù)A的比值f,即影響缺頁次數(shù)的因素分配給進(jìn)程的物理頁面數(shù)頁面本身的大小程序的編制方法頁面淘汰算法,5.3頁面置換算法,5.3.1先進(jìn)先出置換算法和最佳置換算法5.3.2最近最久未使用和最少使用置換算法5.3.3CLOCK置換算法5.3.4頁面緩存算法5.3.5訪問內(nèi)存的有效時間,5.3頁面置換算法,評價標(biāo)準(zhǔn)最低的缺頁率。評價方法通過運(yùn)行一個特殊的頁面引用串檢驗(yàn)算法，計算其頁錯誤率；基本條件：事先知道可用幀的數(shù)量；測試用例：可用幀的數(shù)量為3，頁面引用串如下：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,5.3.1先進(jìn)先出置換算法和最佳置換算法,先進(jìn)先出(FIFO)頁面置換算法選擇在內(nèi)存中駐留時間最長的頁并淘汰之。優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊(duì)列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。缺點(diǎn)：與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，不能保證這些頁面不被淘汰。,引用次序70120304230321201701,頁幀（頁框）,3次,12次,缺頁,5.3.1先進(jìn)先出置換算法和最佳置換算法,先進(jìn)先出(FIFO)頁面置換算法,1,2,3,4,1,2,5,3,4,9pagefaults,2,1,3,4,2,1,5,1,3,2,4,5,1,2,3,5.3.1先進(jìn)先出置換算法和最佳置換算法,先進(jìn)先出(FIFO)頁面置換算法引用頁：1,2,3,4,1,2,5,1,2,3,4,5。3個幀（每個進(jìn)程最多只有3個頁面同時在內(nèi)存）,先進(jìn)先出(FIFO)頁面置換算法引用頁：1,2,3,4,1,2,5,1,2,3,4,5。4個幀Belady異常：幀越多，頁錯誤越多。,10pagefaults,1,2,3,5,1,2,4,5,4,3,2,1,3,4,2,1,5,1,3,2,4,5,1,2,3,4,5.3.1先進(jìn)先出置換算法和最佳置換算法,5.3.1先進(jìn)先出置換算法和最佳置換算法,最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。優(yōu)點(diǎn)：采用最佳置換算法，通常可保證獲得最低的缺頁率。缺點(diǎn)：無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的。,引用次序70120304230321201701,頁幀（頁框）,3次,6次,缺頁,5.3.1先進(jìn)先出置換算法和最佳置換算法,最佳(Optimal)置換算法,5.3.2最近最久未使用和最少使用置換算法,LRU(LeastRecentlyUsed)置換算法的描述利用“最近的過去”作為“最近的將來”的近似，即，選擇最近最久未使用的頁面予以淘汰。選擇最后一次訪問時間距離當(dāng)前時間最長的一頁并淘汰之。即淘汰沒有使用的時間最長的頁。實(shí)現(xiàn)代價很高（時間戳或硬件方法）,引用次序70120304230321201701,頁幀（頁框）,3次,9次,缺頁,5.3.2最近最久未使用和最少使用置換算法,LRU(LeastRecentlyUsed)置換算法,5.3.2最近最久未使用和最少使用置換算法,LRU置換算法的硬件支持優(yōu)點(diǎn)：對于各種類型的程序都能適用；缺點(diǎn)：要求系統(tǒng)具有較多的支持硬件，實(shí)現(xiàn)難度大；主要問題一個進(jìn)程在內(nèi)存中的各個頁面各有多久時間未被進(jìn)程訪問；如何快速地知道哪一頁最近最久未使用的頁面。硬件支持移位寄存器棧,5.3.2最近最久未使用和最少使用置換算法,LRU置換算法的硬件支持寄存器為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為訪問時將Rn-1位置成1，定時信號每隔一時間間隔右移一位，則具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面,R=Rn-1Rn-2Rn-3R2R1R0,t0,t1,t2,訪問1,t3,5.3.2最近最久未使用和最少使用置換算法,5.3.2最近最久未使用和最少使用置換算法,棧訪問某頁時，將該頁面的頁號從棧中移出或直至?？?，再依次入棧，最后訪問頁入棧頂。,5.3.2最近最久未使用和最少使用置換算法,最少使用(LFU:LeastFrequentlyUsed)置換算法為內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率該算法選擇在最近使用最少的頁面作為淘汰頁與最近最少用算法LRU的區(qū)別只考慮一段時間內(nèi)使用的次數(shù)，而不管其使用的時間,這種算法并不能真正反映出頁面的使用情況，因在每一時間間隔內(nèi)只是用寄存器的一位來記錄頁的使用情況，因此訪問1次和10000次是等效的。,5.3.3Clock置換算法,簡單的Clock置換算法（近似的LRU）為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊(duì)列。當(dāng)某頁被訪問時，其訪問位被置1。置換算法在選擇一頁淘汰時，只需檢查其訪問位。,5.3.3Clock置換算法,簡單的Clock置換算法狀態(tài)位(存在位)P。訪問字段A。用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問。修改位M。表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不須將該寫回到外存上；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址。,5.3.3Clock置換算法,簡單的CLOCK置換算法置換算法在選擇一頁淘汰時，只需檢查頁的訪問位，是0換出，是1重新置0且暫不換出，再按FIFO檢查下一個頁面。檢查到最后一個頁面，若其訪問位仍為1，則再返到隊(duì)首檢查。由于該算法是循環(huán)地檢查各頁面的訪問情況，故稱為CLOCK算法，置換的是未使用過的頁，又稱為最近未用算法NRU（NotRecentlyUsed）,5.3.3Clock置換算法,簡單的CLOCK置換算法,入口,查尋指針前進(jìn)一步，指,向下一個表目,頁面訪問位,0,?,選擇該頁面淘汰,是,返回,置頁面訪,問位“,0,”,否,塊號,頁號,訪問位,指針,0,1,2,4,0,3,4,2,1,5,6,5,0,7,1,1,替換,指針,注意：是循環(huán)隊(duì)列！,5.3.3Clock置換算法,5.3.3Clock置換算法,改進(jìn)型Clock置換算法在將一個頁面換出時，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時滿足兩條件的頁面作為首選淘汰的頁。,5.3.3Clock置換算法,改進(jìn)型Clock置換算法狀態(tài)位(存在位)P。訪問字段A。用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問。修改位M。該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不比將該寫回到外存上；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址。,5.3.3Clock置換算法,改進(jìn)型Clock置換算法考慮使用情況和置換代價，換出的最好是未使用且未被修改過的頁面由訪問位A和修改位M組合：1類(A=0,M=0)：最近既未被訪問，又未被修改，是最佳淘汰頁；2類(A=0,M=1)：最近未被訪問，但已被修改，并不是很好的淘汰頁；3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問；4類(A=1,M=1)：最近已被訪問且被修改，該頁可能再被訪問。,5.3.3Clock置換算法,改進(jìn)型Clock置換算法執(zhí)行過程從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在本次掃描期間不改變訪問位A如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位A都置0如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位A復(fù)0。然后回到第一步。,5.3.3Clock置換算法,改進(jìn)型Clock置換算法-示例,最佳淘汰頁,次佳淘汰頁,0,0,0,5.3.4頁面緩沖算法(PBA：PageBufferingAlgorithm),影響頁面換進(jìn)換出效率的若干因素頁面置換算法寫回磁盤的效率讀入內(nèi)存的頻率,5.3.4頁面緩沖算法(PBA：PageBufferingAlgorithm),頁面緩存算法PBA采用了可變分配和局部置換方式，置換算法采用FIFO將一個被淘汰的頁放入兩個鏈表中的一個，即如果頁面未被修改，就將它直接放進(jìn)空閑鏈表中；否則，便放入已修改頁面的鏈表中,空閑鏈表,已修改鏈表,5.3.5訪問內(nèi)存的有效時間,頁面在內(nèi)存中，也在快表中EAT=+頁面在內(nèi)存中，不在快表中EAT=+=2(+)頁面不在內(nèi)存中EAT=+=+2(+)考慮缺頁率f，命中率EAT=+(1-)+f(+)+(1-f)（+）,5.4“抖動”與工作集,5.4.1多道程序度與“抖動”5.4.2工作集5.4.3“抖動”的預(yù)防方法,5.4.1多道程序度與“抖動”,多道程序度與處理機(jī)的利用率,5.4.1多道程序度與“抖動”,抖動，又稱為顛簸在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進(jìn)程實(shí)際運(yùn)行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動。原因頁面淘汰算法不合理分配給進(jìn)程的物理頁面數(shù)太少,5.4.2工作集,工作集的基本概念1968年由Denning提出，并定義了局部模型。它表明進(jìn)程執(zhí)行時，從一個局部移到另一個局部。局部就是一個經(jīng)常使用的頁的集合。,5.4.2工作集,缺頁率與物理內(nèi)存塊數(shù)的關(guān)系,5.4.2工作集,工作集的定義工作集窗口（Workingsetwindow）：最近個頁面引用最近個引用的頁集合稱為工作集合（Workingset）WSSi(進(jìn)程Pi的工作集)=最近所引用的所有頁面的總數(shù)（不同時刻值不同）如果太小，則不能包含整個局部；如果太大，則可能包含多個局部；如果=，則包含了整個程序。,5.4.2工作集,工作集的定義DWSSi表示總的幀需求量m=可分配的頁幀如果D大于m，那么有的進(jìn)程就得不到足夠幀，從而會出現(xiàn)顛簸策略：可以懸掛某些進(jìn)程，以消除顛簸現(xiàn)象,5.4.3“抖動”的預(yù)防方法,采用局部置換策略把抖動影響局限在單個進(jìn)程內(nèi)把工作集算法融入到處理機(jī)調(diào)度中調(diào)度前檢查每個進(jìn)程在內(nèi)存中駐留頁面是否足夠多，如果夠則調(diào)入新的作業(yè)，否則為缺頁率高的進(jìn)程增加物理塊。利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率L是缺頁之間的平均時間，S處理一次缺頁的時間。選擇暫停的進(jìn)程降低多道程序度,5.5請求分段存儲管理方式,5.5.1請求分段中的硬件支持5.5.2分段的共享與保護(hù),5.5.1請求分段中的硬件支持,段表機(jī)制存取方式用于標(biāo)識本分段存取屬性是只執(zhí)行、只讀還是允許讀/寫存在位P用于指示該段是否已調(diào)入內(nèi)存訪問字段A用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本頁在最近多長時間未被訪問修改位M表示該段在調(diào)入內(nèi)存后是否被修改過外存地址本段在外存上的地址，盤塊塊號增補(bǔ)位本段在運(yùn)行過程中是否做過動態(tài)增長,5.5.1請求分段中的硬件支持,缺段中斷機(jī)構(gòu)每當(dāng)發(fā)現(xiàn)運(yùn)行進(jìn)程所要訪問的段尚未調(diào)入內(nèi)存時，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號，進(jìn)入OS后由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。由于分段是信息的邏輯單位，因而不可能出現(xiàn)一條指令被分割在兩個分段中和一組信息被分割在兩個分段中的情況。由于段不是定長的，這使對缺段中斷的處理要比對缺頁中斷的處理復(fù)雜。,5.5.1請求分段中的硬件支持,從中可以看出，對缺段中斷的處理要比對缺頁中斷的處理復(fù)雜，因?yàn)槎问遣欢ㄩL的。,5.5.1請求分段中的硬件支持,地址變換機(jī)構(gòu)在分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存，必須先將所缺的段調(diào)入內(nèi)存，并修改段表，然后才能再利用段表進(jìn)行地址變換。為此，在地址變換機(jī)構(gòu)中又增加了某些功能，如缺段中斷的請求及處理等。,請求分段系統(tǒng)的地址變換過程,5.5.2分段的共享與保護(hù),共享段表為了實(shí)現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表所有各共享段都在共享段表中占有一表項(xiàng)共享進(jìn)程計數(shù)count記錄有多少個進(jìn)程需要共享該分段存取控制字段對于一個共享段，應(yīng)給不同的進(jìn)程以不同的權(quán)限段號對于一個共享段，不同的進(jìn)程可以各用不同的段號去共享該段,共享段表項(xiàng),5.5.2分段的共享與保護(hù),共享段表,非共享段僅為一個進(jìn)程所需要。當(dāng)進(jìn)程不再需要該段時，可立即釋放該段，并由系統(tǒng)回收該段所占用的空間。而共享段是為多個進(jìn)程