操作系統(tǒng)4 5虛擬存儲管理

1主要內(nèi)容：一、虛擬存儲器的概念二、請求分頁虛擬存儲管理三、請求分段虛擬存儲管理四、請求段頁式虛擬存儲管理4.5虛擬存儲管理2一、虛擬存儲器的概念(1)1、虛擬存儲器的定義在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中，采用自動實現(xiàn)部分裝入和部分對換功能，為用戶提供一個比物理主存容量大得多的，可尋址的一種“主存儲器”。虛擬存儲器的容量取決于計算機的地址結(jié)構(gòu)和可用的物理內(nèi)存和外存的容量之和。3一、虛擬存儲器的概念(2)邏輯地址空間處理器虛擬地址存儲管理部件物理地址主存輔存物理地址空間虛擬存儲器的概念圖4一、虛擬存儲器的概念(3)2、虛擬存儲器引入的動機（1）存儲管理分類連續(xù)存儲管理：包括固定分區(qū)和可變分區(qū)離散存儲管理：包括分頁和分段實存管理：包括固定分區(qū)、可變分區(qū)、分頁和分段虛存管理：包括請求分頁、請求分段和請求段頁從一個進程占用的內(nèi)存區(qū)域數(shù)及連續(xù)性可分為從進程是否能夠部分裝入來分可分為5一、虛擬存儲器的概念(4)（2）虛擬存儲器的好處對于同樣大小的內(nèi)存空間，虛擬存儲器可以比實存管理運行更多的進程，虛擬存儲器還可以運行超過內(nèi)存空間大小以及當前可用內(nèi)存空間的大進程，內(nèi)存利用率高、內(nèi)存配置可以更經(jīng)濟。前面了解的各種存儲管理方式都要求作業(yè)全部裝入內(nèi)存方可運行，如果內(nèi)存空間不足以容納作業(yè)時，該作業(yè)就不能運行。虛擬存儲器允許進程部分裝入即可運行，運行過程中進程的部分可以在內(nèi)外存之間對換，從邏輯上擴充內(nèi)存容量，使得程序員的編程空間大于內(nèi)存容量。這就是虛擬存儲管理的主要思想。6一、虛擬存儲器的概念(5)（3）實現(xiàn)虛擬存儲器的基礎(chǔ)—程序執(zhí)行的局部性原理程序執(zhí)行的局部性是指在一段時間內(nèi)，程序訪問的存儲空間僅限于某個區(qū)域（這稱為空間局部性），或者最近訪問過的程序代碼和數(shù)據(jù)很快會再被訪問（這稱為時間局部性）。在較小的一段時間內(nèi)，整個作業(yè)空間中只有某一局部模塊的指令和數(shù)據(jù)會被執(zhí)行和訪問到。作業(yè)其它部分暫時不會訪問到。這就允許這部分暫時不用的作業(yè)部分不必占據(jù)內(nèi)存空間,可以先留在外存上，待以后需要訪問時再裝入內(nèi)存。7一、虛擬存儲器的概念(6)內(nèi)存中一些暫時不用的部分還可以臨時調(diào)出到外存上，這樣就可將內(nèi)存空間優(yōu)先分配給當前急需使用的作業(yè)進程，能夠提高內(nèi)存利用率。8一、虛擬存儲器的概念(7)（4）與局部性相關(guān)的代碼和數(shù)據(jù)結(jié)構(gòu)第一、程序中只有少量分支和過程調(diào)用，大都是順序執(zhí)行的指令；第二、程序含有若干循環(huán)結(jié)構(gòu)，由少量代碼組成，而被多次執(zhí)行；第三、過程調(diào)用的深度限制在小范圍內(nèi)，因而，指令引用通常被局限在少量過程中；第四、涉及數(shù)組、記錄之類的數(shù)據(jù)結(jié)構(gòu)，對它們的連續(xù)引用是對位置相鄰的數(shù)據(jù)項的操作；第五、程序中有些部分彼此互斥，不是每次運行時都用到。9一、虛擬存儲器的概念(8)3、實現(xiàn)虛擬存儲器需要解決的問題（1）主存輔存統(tǒng)一管理問題（2）邏輯地址到物理地址的轉(zhuǎn)換問題（3）部分裝入和部分對換問題虛擬存儲器的實現(xiàn)技術(shù)主要有（1）請求分頁式（2）請求分段式（3）請求段頁式虛擬存儲管理10二、請求分頁虛擬存儲管理(1)1、請求分頁虛擬存儲系統(tǒng)基本原理在進程開始運行之前，不是裝入全部頁面，而是裝入一個或幾個頁面，進程運行過程中，訪問的頁面不在內(nèi)存時，再裝入所需頁面；若內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。因此請求分頁系統(tǒng)的頁表機制需要記住頁面是否在內(nèi)存，若不在內(nèi)存則在外存什么位置。11二、請求分頁虛擬存儲管理(2)2、請求分頁系統(tǒng)的頁表結(jié)構(gòu)頁表分為內(nèi)存頁表和外頁表。（1）內(nèi)存頁表在實存頁表基礎(chǔ)上增加調(diào)頁、淘汰頁有關(guān)的標志位，頁表如下：頁號物理塊號駐留標志位引用位R修改位M訪問權(quán)限位駐留標志位—又稱中斷位，狀態(tài)位，指示頁面是否在內(nèi)存引用位R—指示頁面最近是否被訪問過，幫助頁面淘汰修改位M—指示頁面最近是否被修改過，決定頁面調(diào)出內(nèi)存時是否寫回外存訪問權(quán)限位—規(guī)定頁面的訪問權(quán)限12二、請求分頁虛擬存儲管理(3)（2）外頁表是頁面與磁盤物理地址的對應(yīng)表，由操作系統(tǒng)管理，進程啟動運行前系統(tǒng)為其建立外頁表，并把進程程序頁面裝入輔存。該表按進程頁號的順序排列，為節(jié)省主存，外頁表可存放在磁盤中，當發(fā)生缺頁中斷需要查用時才被調(diào)入。外頁表結(jié)構(gòu)如下：頁號外存地址13二、請求分頁虛擬存儲管理(4)3、分頁式虛擬存儲系統(tǒng)的硬件支撐需要內(nèi)存管理部件MMUMMU通常由一個或一組芯片組成，它接受虛擬地址（邏輯地址）作為輸入，輸出物理地址。（分頁系統(tǒng)也需要）14二、請求分頁虛擬存儲管理(5)CPUMMU內(nèi)存CPU把邏輯地址送至MMUMMU把物理地址送至主存MMU的位置、功能和16個4KB頁面情況下MMU的內(nèi)部操作CPU送入的邏輯地址(8196)0010000000000100110000000000100MMU送出的物理地址00101100112110130001410015011160000700008101190000…

頁號頁框號在主存否15二、請求分頁虛擬存儲管理(6)MMU的主要功能主要有：①管理硬件頁表寄存器：負責裝入將要占用處理器的進程的頁表。②分解邏輯地址為頁號和頁內(nèi)地址③管理快表：查找快表、裝入表目和清除表目④訪問頁表⑤當要訪問的頁面不在內(nèi)存時發(fā)出缺頁中斷，頁面訪問越界時發(fā)出越界中斷。⑥設(shè)置和檢查頁表中的引用位、修改位、有效位和保護權(quán)限位等各個特征位16二、請求分頁虛擬存儲管理(7)缺頁中斷與普通中斷的差異（小問題，忽略不影響主題內(nèi)容的完整性，但考研可能會涉及特殊的、陌生的概念和問題）：（1）普通中斷在兩條指令之間才會響應(yīng)；缺頁中斷涉及的指令在執(zhí)行期間（例如開頭，甚至取不到指令或數(shù)據(jù)）就需要響應(yīng)缺頁中斷。17二、請求分頁虛擬存儲管理(8)將要順序執(zhí)行的下一條指令位于不在內(nèi)存的頁1上，PC指向的指令地址超過了頁0的范圍，該地址位于頁1上。頁0在內(nèi)存頁1不在內(nèi)存MEMADDAX，BXMOV0::MEM,AX0頁倒數(shù)第2條指令0頁最后一條指令A(yù)DDAX，1:DATA2DATA21頁第1條指令18二、請求分頁虛擬存儲管理(9)（2）當指令本身或者指令所處理的數(shù)據(jù)跨頁時，在執(zhí)行一條指令的過程中可能發(fā)生多次缺頁中斷。數(shù)據(jù)跨頁：該條指令訪問了不在內(nèi)存的頁1中的數(shù)據(jù)，發(fā)生缺頁中斷，調(diào)入頁面后，該條指令需要重新執(zhí)行。MOVAX，0::DATA1ADDAX，1:DATA2頁0在內(nèi)存DATA1MOVCX,1:DATA2頁1不在內(nèi)存DATA219二、請求分頁虛擬存儲管理(10)指令跨頁：指令A(yù)DDAX，2:DATA2跨越了頁0和頁1，頁1不在內(nèi)存，發(fā)生缺頁中斷，調(diào)入頁面1后，該條指令需要重新執(zhí)行。數(shù)據(jù)DATA2不在內(nèi)存，再次缺頁中斷，調(diào)入頁2，該條指令再次重新執(zhí)行。頁0在內(nèi)存DATA1ADDDX，2:DATA2頁1不在內(nèi)存ADDAX，2:DATA2DATA2頁2不在內(nèi)存20二、請求分頁虛擬存儲管理(11)4、請求分頁的地址變換過程當進程被調(diào)度到CPU上運行時，操作系統(tǒng)自動把該進程PCB中的頁表始址裝入到硬件頁表基址寄存器中，此后，進程開始執(zhí)行并要訪問某個虛擬地址，內(nèi)存管理部件MMU開始工作：①MMU接受CPU傳送過來的虛地址并分解為兩部分：頁號和頁內(nèi)地址；②以頁號為索引搜索快表；③如果命中快表，則立即送出物理塊號（頁框號），并與頁內(nèi)地址拼接形成物理地址，然后訪問相應(yīng)內(nèi)存單元；21二、請求分頁虛擬存儲管理(12)④如果不命中快表，則以頁號為索引搜索內(nèi)存頁表，頁表的基址由硬件頁表寄存器指出；⑤在頁表中查找相應(yīng)表項，如果其狀態(tài)位指示該頁已在內(nèi)存，則送出物理塊號與頁內(nèi)地址拼接形成物理地址訪問相應(yīng)內(nèi)存單元，同時要將該表項裝入快表；⑥如果在頁表中找到的相應(yīng)表項，其狀態(tài)位指示該頁不在內(nèi)存，則發(fā)出缺頁中斷，請求操作系統(tǒng)處理；⑦存儲管理軟件將所缺頁面調(diào)入內(nèi)存，修改頁表。22二、請求分頁虛擬存儲管理(13)5、缺頁中斷處理過程步1掛起請求缺頁的進程；步2根據(jù)頁號查外頁表，找到該頁存放的磁盤物理地址；步3查看主存是否有空閑頁框，如有則找出一個，修改主存管理表和相應(yīng)頁表項內(nèi)容，轉(zhuǎn)步6；，步4如主存中無空閑頁框，按替換算法選擇淘汰頁面，檢查它曾被寫過或修改過嗎？若未則轉(zhuǎn)步6；若是則轉(zhuǎn)步5；23二、請求分頁虛擬存儲管理(14)步5該淘汰頁面被寫過或修改過，則把它的內(nèi)容寫回磁盤原先位置；步6進行調(diào)頁，把頁面裝入主存所分配的頁框中，同時修改進程頁表項；步7返回進程斷點，重新啟動被中斷的指令。24二、請求分頁虛擬存儲管理(15)概括：①查看內(nèi)存是否有空閑物理塊，如有則可以裝入頁面到空閑物理塊，同時修改頁表相應(yīng)項以及內(nèi)存分配表；②如果內(nèi)存中沒有空閑物理塊，則按替換算法選擇一個頁面淘汰，若該頁面被寫過或修改過，則寫回外存，否則只簡單淘汰該頁面。淘汰頁面之后要修改頁表相應(yīng)項，然后調(diào)入頁面到淘汰頁面釋放的物理塊中。25二、請求分頁虛擬存儲管理(16)邏輯地址空間主存(用戶區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū))運行進程頁表輔存缺頁中斷處理①分解地址③⑤訪問MMU②查快表③命中④不命中⑤頁表命中⑦發(fā)缺頁中斷⑧調(diào)頁⑨裝入、改表④查頁表運行進程頁表基址⑥裝入快表運行進程映象進程切換時裝入物理地址頁框頁內(nèi)地址頁號頁內(nèi)地址對象(實體):CPU(包含MMU,快表,頁表寄存器)內(nèi)存:存放頁表和進程實體輔存:存放外頁表和進程實體26二、請求分頁虛擬存儲管理(17)6、頁面裝入策略和清除策略頁裝入策略決定何時把一個頁面裝入內(nèi)存,有兩種策略：請頁式調(diào)入和預(yù)調(diào)式調(diào)入。（1）請頁式調(diào)入在需要訪問程序和數(shù)據(jù)時,才把所在頁面裝入主存。缺點是處理缺頁中斷和調(diào)頁的系統(tǒng)開銷較大，每次僅調(diào)一頁，增加了磁盤I/O次數(shù)。27二、請求分頁虛擬存儲管理(18)（2）預(yù)調(diào)式調(diào)入由系統(tǒng)預(yù)測進程將要使用的頁面,使用前預(yù)先調(diào)入主存,每次調(diào)入若干頁面,而不是僅調(diào)一頁。一次調(diào)入多頁能減少磁盤I/O啟動次數(shù),節(jié)省尋道和搜索時間。28二、請求分頁虛擬存儲管理(19)清除策略考慮何時把一個修改過的頁面寫回外存,常用的方法是:請頁式清除和預(yù)約式清除。（1）請頁式清除是僅當一頁選中被替換，且之前它又被修改過，才把這個頁面寫回輔存。（2）預(yù)約式清除對所有更改過的頁面，在需要之前就把它們都寫回外存。29二、請求分頁虛擬存儲管理(20)7、頁面分配策略（1）頁面分配策略主要有兩種：固定分配和可變分配。固定分配使進程在生命周期中保持固定數(shù)目的物理塊。進程創(chuàng)建時，根據(jù)進程類型和程序員的要求決定頁框數(shù)。固定分配時，每個進程物理塊的分配方式主要有：平均分配、比例分配、優(yōu)先權(quán)分配。30二、請求分頁虛擬存儲管理(21)進程分得的頁框數(shù)可變，稱可變分配。進程執(zhí)行的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進程目前的局部性較好，可減少分給進程的頁框數(shù)。31二、請求分頁虛擬存儲管理(22)（2）頁面替換策略有兩種：局部替換和全局替換。局部替換在進程發(fā)生缺頁時僅從該進程的物理塊中淘汰頁面，以調(diào)入所缺頁面；全局替換則在進程發(fā)生缺頁時可從系統(tǒng)中任一進程的物理塊中淘汰頁面。32二、請求分頁虛擬存儲管理(23)（3）頁面分配和替換常用的組合策略有三種：固定分配局部置換可變分配全局置換可變分配局部置換經(jīng)驗表明：對每個程序，要使其有效工作，它在主存中的頁面數(shù)不應(yīng)低于它的總頁面數(shù)的一半。33二、請求分頁虛擬存儲管理(24)可變分配全局置換先為每個進程分配一定數(shù)目頁框，OS保留若干空閑頁框進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中選一個給進程，這樣產(chǎn)生缺頁中斷進程的主存空間會逐漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。系統(tǒng)擁有的空閑頁框耗盡時，會從主存中選擇一頁淘汰，該頁可以是主存中任一進程的頁面，這樣又會使那個進程的頁框數(shù)減少，缺頁中斷率上升。34二、請求分頁虛擬存儲管理(25)可變分配局部置換其實現(xiàn)要點：(1)新進程裝入主存時，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目頁框，可用請頁式或預(yù)調(diào)式完成這個分配。(2)產(chǎn)生缺頁中斷時，從該進程駐留頁面集中選一個頁面替換。(3)不時重新評價進程的缺頁率，增加或減少分配給進程的頁框以改善系統(tǒng)性能。35二、請求分頁虛擬存儲管理(26)8、缺頁中斷率（1）抖動的概念在請求分頁虛擬存儲管理機制中，剛被淘汰的頁面立即又要訪問，而調(diào)入不久即被淘汰，淘汰不久再被調(diào)入，如此反復(fù)，使得系統(tǒng)的頁面調(diào)度非常頻繁，以致大部分時間消耗在頁面調(diào)度上，而不是執(zhí)行計算任務(wù)，這種現(xiàn)象稱為“抖動”。36二、請求分頁虛擬存儲管理(27)（2）缺頁中斷率假定進程P共計n頁，該進程分得的主存塊為m塊（１≤m≤n）。如果進程P在運行中成功的訪問次數(shù)為S，不成功的訪問次數(shù)為F，則總的訪問次數(shù)Ａ為：A=S+F定義：f=F/A稱f為缺頁中斷率。37二、請求分頁虛擬存儲管理(28)影響缺頁中斷率f的因素有：(1)主存頁框數(shù)：多則低，少則高。(2)頁面大小：大則低，小則高。(3)頁面替換算法：優(yōu)劣決定缺頁率。(4)程序特性：局部性要好。38二、請求分頁虛擬存儲管理(29)程序局部性例子程序?qū)?shù)組置為“0”，假定僅分得一個主存塊，頁面尺寸為128個字，數(shù)組元素按行存放，開始時第一頁在主存。intA[128][128];for(intj=0;j<128;j++)for(inti=0;i<128;i++)A[i][j]=0;按列訪問，缺頁中斷次數(shù)為128×128-1intA[128][128];for(inti=0;i<128;i++)for(intj=0;j<128;j++)A[i][j]=0;按行訪問，缺頁中斷次數(shù)為128-139二、請求分頁虛擬存儲管理(30)A0,0A0,1……A0,126A0,127A1,0A1,1……A1,126A1,127…………………………A126,0A126,1……A126,126A126,127A127,0A127,1……A127,126A127,127A0,0A0,1……A0,126A0,127數(shù)組主存塊011261270112612701126127如果按行訪問，第0行事先以非中斷的方式裝入內(nèi)存，只有其余127行以缺頁中斷方式裝入內(nèi)存。40二、請求分頁虛擬存儲管理(31)A0,0A0,1……A0,126A0,127A1,0A1,1……A1,126A1,127…………………………A126,0A126,1……A126,126A126,127A127,0A127,1……A127,126A127,127A0,0A0,1……A0,126A0,127數(shù)組主存塊011261270112612701126127如果按列訪問，每訪問一個元素需要裝入一行元素，但僅能訪問其中一個元素。例如訪問A0,0需裝入第0行，接下來訪問A1,0就需要裝入第1行，…，將來再訪問第0行的其它元素，如A0,1等，則需要再次裝入第0行。缺頁中斷次數(shù)與元素數(shù)一樣多，除了第0個元素。41二、請求分頁虛擬存儲管理(32)9、局部頁面替換策略及其全局頁面替換擴展最佳頁面算法(OPT)先進先出頁面淘汰算法(FIFO)最近最久未使用頁面淘汰算法(LRU)第二次機會頁面替換算法Clock置換算法這些算法都是基于系統(tǒng)對物理塊的分配策略采用固定分配局部置換。42二、請求分頁虛擬存儲管理(33)（1）最佳頁面算法（OPT）調(diào)入一頁而必須淘汰一個舊頁時，所淘汰的頁應(yīng)該是以后不再訪問的頁或距現(xiàn)在最長時間后再訪問的頁。OPT可用于衡量各種具體算法的標準。例：某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。用最佳頁面算法分析頁面置換過程。二、請求分頁虛擬存儲管理(34)443432432143543215431435235215共缺頁中斷7次44二、請求分頁虛擬存儲管理(35)最佳頁面算法（OPT）的全局替換擴展調(diào)入一頁而必須淘汰一個舊頁時，所淘汰的頁應(yīng)該是所有進程中以后不再訪問的頁或距現(xiàn)在最長時間后再訪問的頁。該進程獲得的主存塊逐漸增多，缺頁中斷率逐漸下降。理論上，全局最佳頁面替換算法性能優(yōu)于局部最佳頁面替換算法性能。45二、請求分頁虛擬存儲管理(36)（2）先進先出頁面淘汰算法(FIFO)算法總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁（常駐的除外）。例：某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。用先進先出頁面算法分析頁面置換過程。二、請求分頁虛擬存儲管理(37)443432432143543215132142143543523521共缺頁中斷9次47二、請求分頁虛擬存儲管理(38)先進先出頁面淘汰算法(FIFO)的全局擴展算法總是淘汰所有進程中最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁。記住頁面駐留內(nèi)存時間長短的方法類似于上述方法。對于FIFO算法，增加進程主存塊數(shù)，缺頁中斷率可能不降反升。48二、請求分頁虛擬存儲管理(39)頁緩沖技術(shù)是對FIFO替換算法的一種改進，策略如下：在頁緩沖中，淘汰了的頁面進入兩個隊列：修改頁面和非修改頁面隊列。修改頁面隊列中的頁不時地成批寫出并加入到非修改頁面隊列；非修改頁面隊列中的頁面，當它被再次引用時回收，或者淘汰掉以作替換。49二、請求分頁虛擬存儲管理(40)123修改頁面隊列456非修改頁面隊列456非修改頁面隊列123修改頁面隊列空圖1、頁緩沖寫回修改頁面前的狀態(tài)123圖2、頁緩沖寫回修改頁面后的狀態(tài)非修改頁面隊列中的內(nèi)存塊要么未修改過，要么已保存到外存，以后可直接覆蓋其中信息456外存50二、請求分頁虛擬存儲管理(41)（3）最近最久未使用頁面淘汰算法(LRU)算法淘汰的頁面是在最近一段時間里較久未被訪問的那頁。例：某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。用最近最久未使用頁面算法分析頁面置換過程。二、請求分頁虛擬存儲管理(42)443432432143543215共缺頁中斷10次13214214354324321321552二、請求分頁虛擬存儲管理(43)最近最久未使用頁面淘汰算法(LRU)的幾種實現(xiàn)方法：方法1—引用位法每頁設(shè)置一個引用標志位R，訪問某頁時，由硬件將頁標志位R置1，隔一定時間t將所有頁的標志R均清0。發(fā)生缺頁中斷時，從標志位R為0的頁中挑選一頁淘汰。挑選到要淘汰的頁后，也將所有頁的標志位R清0。t太大，缺頁中斷時，所有標志位為1；t太小，缺頁中斷時，所有標志位為053二、請求分頁虛擬存儲管理(44)方法2—計數(shù)器法每個頁面設(shè)置一個計數(shù)器，又叫最不常用頁面替換算法LFU。每當訪問一頁時，就使它對應(yīng)的計數(shù)器加１。當發(fā)生缺頁中斷時，可選擇計數(shù)值最小的對應(yīng)頁面淘汰，并將所有計數(shù)器全部清０。上述幾種方法均只是對最近最久未使用頁面淘汰算法(LRU)的近似實現(xiàn)，這些方法在某一頁訪問頻率較高時，很難精確地記住其它頁面最近訪問的情況。54二、請求分頁虛擬存儲管理(45)方法3—計時器法為每個頁面設(shè)置一個計時器，每當頁面被訪問時，系統(tǒng)的絕對時間記入計時器。比較各頁面的計時器的值，選最小值的未使用的頁面淘汰，因為，它是最“老”的未使用的頁面。55二、請求分頁虛擬存儲管理(46)（4）第二次機會頁面替換算法改進FIFO算法，把FIFO與頁表中的”引用位”結(jié)合起來使用：

?檢查FIFO中的隊首頁面(最早進入主存頁面)，如果它的”引用位”是0，這個頁面既老又沒有用，選擇該頁面淘汰；

?如果”引用位”是1，說明它進入主存較早，但最近仍在使用。把它的”引用位”清0，并把這個頁面移到隊尾，把它看作是一個新調(diào)入的頁。

?算法含義：最先進入主存的頁面，如果最近還在被使用的話，仍然有機會作為像一個新調(diào)入頁面一樣留在主存中。56二、請求分頁虛擬存儲管理(47)（5）時鐘頁面替換算法算法實現(xiàn)要點：一個頁面首次裝入主存，其“引用位”置1

。主存中的任何頁面被訪問時，”引用位”置1。淘汰頁面時，從指針當前指向的頁面開始掃描循環(huán)隊列，把遇到的”引用位”是1的頁面的”引用位”清0，跳過這個頁面；把所遇到的”引用位”是0的頁面淘汰掉，指針推進一步。57二、請求分頁虛擬存儲管理(48)掃描循環(huán)隊列時，如果遇到的所有頁面的”引用位”為1，指針就會繞整個循環(huán)隊列一圈，把碰到的所有頁面的”引用位”清0；指針停在起始位置，并淘汰掉這一頁，然后，指針推進一步。注意：在掃描隊列時，缺頁進程處于掛起狀態(tài)，不可能再訪問頁面，因此進程不會使頁面的訪問狀態(tài)發(fā)生改變，只有掃描頁面訪問狀態(tài)的系統(tǒng)內(nèi)核才會改變頁面訪問狀態(tài)位。因此，頁面引用位不會被并發(fā)訪問。58二、請求分頁虛擬存儲管理(49)時鐘頁面替換算法的改進算法把”引用位”和”修改位”結(jié)合起來使用，共組合成四種情況：(1)最近沒有被引用，沒有被修改(r=0，m=0)(2)最近被引用，沒有被修改(r=1，m=0)(3)最近沒有被引用，但被修改(r=0，m=1)(4)最近被引用過，也被修改過(r=1，m=1)59二、請求分頁虛擬存儲管理(50)步1：選擇最佳淘汰頁面，從指針當前位置開始，掃描循環(huán)隊列。掃描過程中不改變”引用位”，把找到的第一個r=0，m=0的頁面作為淘汰頁面。步2：如果步1失敗，再次從原位置開始，查找r=0且m=1的頁面，把找到的第一個這樣的頁面作為淘汰頁面，而在掃描過程中把指針所掃過的頁面的”引用位”r置0。步3：如果步2失敗，指針再次回到了起始位置，由于此時所有頁面的”引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時再做步2操作，這次一定可以挑出一個可淘汰的頁面。60二、請求分頁虛擬存儲管理(51)10、局部頁面替換算法的工作集模型（1）工作集—在某一段時間間隔內(nèi)進程運行所需訪問的頁面集合。工作集是為確保每個進程每一時刻能夠執(zhí)行下去，在物理存儲器中必須有的最少頁面數(shù)。61二、請求分頁虛擬存儲管理(52)（2）局部最佳頁面替換算法實現(xiàn)思想：在時刻t，對進程即將訪問的頁面決定是否進行裝入處理；對于已訪問且在內(nèi)存的歷史頁面集合S決定是否進行淘汰處理。對于即將訪問的頁面P，如果P不在主存中，則導(dǎo)致一次缺頁中斷，把該頁面P裝入一個空閑頁框。對于已訪問且在內(nèi)存的歷史頁面集合S，如果頁面X∈S在時間間隔(t，t+τ)內(nèi)不會被再次引用，那么就移出。62二、請求分頁虛擬存儲管理(53)τ為一個系統(tǒng)常量，間隔(t，t+τ)稱作滑動窗口。這里分給進程的頁框數(shù)不是固定的。算法實例：例子中τ=3。開始時P4已被裝入。每一時刻的動作規(guī)則：1）在時刻t，若需訪問頁P，而P不在內(nèi)存，則裝入P到內(nèi)存；2）在時間段t~t+

內(nèi)，若已在內(nèi)存的頁面X在這段時間內(nèi)不被訪問，則淘汰頁面X。63二、請求分頁虛擬存儲管理(54)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1--P2--P3-√P4√√P5--裝入P3淘汰

=3滑動窗口(1,1+3)即時間段1-4的工作集W={P2,P3,P4}t=1√為駐留集M={P3,P4},M-W=

,不從M中淘汰頁64二、請求分頁虛擬存儲管理(55)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1---P2---P3-√√P4√√√P5---裝入P3淘汰

=3滑動窗口(2,2+3)即時間段2-5的工作集W={P2,P3,P4}t=2√為駐留集M={P3,P4},M-W=

,不從M中淘汰頁65二、請求分頁虛擬存儲管理(56)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1----P2----P3-√√√P4√√√√P5----裝入P3淘汰

=3滑動窗口(3,3+3)即時間段3-6的工作集W={P2,P3,P4,P5}t=3√為駐留集M={P3,P4},M-W=

,不從M中淘汰頁66二、請求分頁虛擬存儲管理(57)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1-----P2----√P3-√√√√P4√√√√-P5-----裝入P3P2淘汰P4滑動窗口(4,4+3)即時間段4-7的工作集W={P2,P3,P5}t=4,

=3淘汰頁=時刻3的駐留集M3-W={P3,P4}-{P2,P3,P5}={P4}時刻4的駐留集M4=(M3-淘汰頁)∪{裝入頁}=({P2,P3}67二、請求分頁虛擬存儲管理(58)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1------P2----√-P3-√√√√√P4√√√√--P5------裝入P3P2淘汰P4P2τ=3P2在滑動窗口（5，5+3）內(nèi)將不被訪問，淘汰t=5√為駐留集={P3}68二、請求分頁虛擬存儲管理(59)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1-------P2----√--P3-√√√√√√P4√√√√---P5------√裝入P3P2P5淘汰P4P2τ=3滑動窗口（6，6+3）t=6√為駐留集={P3,P5}69二、請求分頁虛擬存儲管理(60)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1--------P2----√---P3-√√√√√√√P4√√√√----P5------√√裝入P3P2P5淘汰P4P2τ=3滑動窗口（7，7+3）t=7√為駐留集={P3,P5}70二、請求分頁虛擬存儲管理(61)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1---------P2----√----P3-√√√√√√√-P4√√√√-----P5------√√√裝入P3P2P5淘汰P4P2P3τ=3P3在滑動窗口（8，8+3）內(nèi)將不被訪問，淘汰t=8√為駐留集={P5}71二、請求分頁虛擬存儲管理(62)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1---------√P2----√-----P3-√√√√√√√--P4√√√√------P5------√√√-裝入P3P2P5P1淘汰P4P2P3P5τ=3P5在滑動窗口（9，9+3）內(nèi)將不被訪問，淘汰t=9√為駐留集={P1}72二、請求分頁虛擬存儲管理(63)時刻t012345678910引用串P4P3P3P4P2P3P5P3P5P1P4P1---------√-P2----√------P3-√√√√√√√---P4√√√√------√P5------√√√--裝入P3P2P5P1P4淘汰P4P2P3P5P1τ=3P1在滑動窗口（10，10+3）內(nèi)將不被訪問，淘汰t=10√為駐留集={P4}73二、請求分頁虛擬存儲管理(64)（3）請求分頁虛擬存儲管理的目標在局部性假定下，找出最近一段時間內(nèi)進程要訪問的頁面即工作集并加載到內(nèi)存，這樣，近期，該進程不會發(fā)生缺頁中斷；最近一段時間過去后，進程在接下來的一段時間內(nèi)要訪問的頁面集合即工作集可能不同于先前的工作集，這時才會發(fā)生缺頁中斷，缺頁中斷發(fā)生時，將下一時間段的工作集一次性裝入內(nèi)存，進程在下一時間段也不會再發(fā)生缺頁中斷。74二、請求分頁虛擬存儲管理(65)（4）工作集的缺頁中斷特征在工作集模型下，缺頁中斷不是以頁為單位發(fā)生，而是以工作集為單位發(fā)生，當工作集發(fā)生變化時，才會發(fā)生一次缺頁中斷。而工作集是由若干頁面構(gòu)成的。75二、請求分頁虛擬存儲管理(66)（5）工作集模型工作集模型用來對局部最佳頁面替換算法進行模擬實現(xiàn)，不向前查看頁面引用串，而是基于程序局部性原理向后看。任何給定時刻，進程不久的將來所需主存頁框數(shù)，可通過考查其過去最近的時間內(nèi)的主存需求做出估計。76二、請求分頁虛擬存儲管理(67)作業(yè)占用的主存塊數(shù)目小于工作集，運行中會不斷出現(xiàn)缺頁中斷，為保證作業(yè)有效運行，應(yīng)該根據(jù)工作集大小分給它主存塊，以保證工作集中所需要的頁面能夠進入主存。為了避免系統(tǒng)發(fā)生抖動，就應(yīng)該限制系統(tǒng)內(nèi)的作業(yè)數(shù)，使它們的工作集總尺寸不超過主存塊總數(shù)。77二、請求分頁虛擬存儲管理(68)工作集和工作集窗口進程工作集指“在某一段時間間隔內(nèi)進程運行所需訪問的頁面集合”。用W(t,△)表示從時刻t-△到時刻t之間所訪問的頁面的集合；△是時間窗口尺寸。W(t,△)就是作業(yè)在時刻t的工作集，表示在最近△個時間單位內(nèi)進程所引用過的頁面的集合；∣W(t,△)∣表示工作集中的頁面數(shù)目，稱工作集尺寸。78二、請求分頁虛擬存儲管理(69)如果系統(tǒng)能隨∣W(t,△)∣的大小來分配主存塊，就既能有效利用主存，又可使缺頁中斷盡量少地發(fā)生，或者說程序要有效運行，其工作集必須在主存中。工作集W是t的函數(shù)，隨時間不同，工作集也不同。其一是不同時間的工作集包含的頁面數(shù)可能不同(工作集尺寸不同)；其二是不同時間的工作集包含的頁面可能不同(頁面內(nèi)容不同)。工作集W又是工作集窗口尺寸△的函數(shù)，而且工作集尺寸∣W（t，△）∣是工作集窗口尺寸△的非遞減函數(shù)。79二、請求分頁虛擬存儲管理(70)正確選擇工作集窗口尺寸如果△過大，甚至把作業(yè)地址空間全包括在內(nèi)，就成了實存管理如果△過小，則會引起頻繁缺頁，降低了系統(tǒng)的效率。實例：工作集窗口尺寸△=3。在時刻t=-2，P5被引用；在時刻t=-1，P4被引用。在時刻t=0，初始工作集為(P1，P4，P5)。80二、請求分頁虛擬存儲管理(71)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1-P2-P3-P4-P5√裝入P5淘汰窗口（-2-3，-2）81二、請求分頁虛擬存儲管理(72)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--P2--P3--P4-√P5√√裝入P5P4淘汰窗口（-1-3，-1）82二、請求分頁虛擬存儲管理(73)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√P2---P3---P4-√√P5√√√裝入P5P4P1淘汰窗口（0-3，0）83二、請求分頁虛擬存儲管理(74)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√P2----P3---√P4-√√√P5√√√√裝入P5P4P1P3淘汰窗口（1-3，1）84二、請求分頁虛擬存儲管理(75)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√P2-----P3---√√P4-√√√√P5√√√√-裝入P5P4P1P3淘汰P5窗口（2-3，2）85二、請求分頁虛擬存儲管理(76)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√P2------P3---√√√P4-√√√√√P5√√√√--裝入P5P4P1P3淘汰P5窗口（3-3，3）86二、請求分頁虛擬存儲管理(77)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√-P2------√P3---√√√√P4-√√√√√√P5√√√√---裝入P5P4P1P3P2淘汰P5P1窗口（4-3，4）87二、請求分頁虛擬存儲管理(78)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√--P2------√√P3---√√√√√P4-√√√√√√√P5√√√√----裝入P5P4P1P3P2淘汰P5P1窗口（5-3，5）88二、請求分頁虛擬存儲管理(79)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√---P2------√√√P3---√√√√√√P4-√√√√√√√√P5√√√√----√裝入P5P4P1P3P2P5淘汰P5P1窗口（6-3，6）89二、請求分頁虛擬存儲管理(80)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√----P2------√√√√P3---√√√√√√√P4-√√√√√√√√-P5√√√√----√√裝入P5P4P1P3P2P5淘汰P5P1P4窗口（7-3，7）90二、請求分頁虛擬存儲管理(81)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√-----P2------√√√√-P3---√√√√√√√√P4-√√√√√√√√--P5√√√√----√√√裝入P5P4P1P3P2P5淘汰P5P1P4P2窗口（8-3，8）91二、請求分頁虛擬存儲管理(82)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√-----√P2------√√√√--P3---√√√√√√√√√P4-√√√√√√√√---P5√√√√----√√√√裝入P5P4P1P3P2P5P1淘汰P5P1P4P2窗口（9-3，9）92二、請求分頁虛擬存儲管理(83)時刻t-2-1012345678910引用串P5P4P1P3P3P4P2P3P5P3P5P1P4P1--√√√√-----√√P2------√√√√---P3---√√√√√√√√√√P4-√√√√√√√√---√P5√√√√----√√√√√裝入P5P4P1P3P2P5P1P4淘汰P5P1P4P2窗口（10-3，10）93二、請求分頁虛擬存儲管理(84)工作集模型的實質(zhì)當△=3時，分給進程的物理塊數(shù)最多為4塊。工作集模型實質(zhì)上屬于基于可變分配局部替換的先進先出算法