操作系統(tǒng)請求分頁

會計學(xué)1操作系統(tǒng)請求分頁虛擬存儲器虛擬存儲器（VirtualMemory），簡稱虛存，是指對內(nèi)存的虛擬，一種實際并不存在的內(nèi)存空間，包括一級存儲器概念和作業(yè)地址空間概念。虛擬并不是無限的，取決于機(jī)器的CPU地址結(jié)構(gòu)，虛存容量不能大于外存容量。第1頁/共38頁請求分頁管理請求分頁管理是動態(tài)分頁管理，是在靜態(tài)分頁管理基礎(chǔ)上發(fā)展而來的。在簡單分頁管理中，如果作業(yè)所要求的頁面數(shù)比內(nèi)存空閑的塊數(shù)多，則該作業(yè)不能裝入運行。在虛擬存儲器技術(shù)的支持下，可以進(jìn)行請求分頁管理。那么請求分頁管理的基本思想是什么？作業(yè)要訪問的頁面不在內(nèi)存時，該如何處理？如何知道哪些頁面在內(nèi)存，哪些不在？如何決定把作業(yè)的哪些頁面留在內(nèi)存中呢？將虛頁調(diào)入內(nèi)存時，沒有空閑塊又怎么處理？在虛擬存儲系統(tǒng)中，將對邏輯空間和物理空間的考慮截然分開，邏輯空間的容量由系統(tǒng)提供的有效地址長度決定。

第2頁/共38頁請求分頁管理就能實現(xiàn)這種虛存空間，基本方法是在分頁管理的基礎(chǔ)上，在作業(yè)開始執(zhí)行前，只裝入作業(yè)的一部分頁面到內(nèi)存，其它的頁面在作業(yè)執(zhí)行過程中根據(jù)需要，動態(tài)地從輔存裝入內(nèi)存。當(dāng)內(nèi)存塊已經(jīng)占滿時，再根據(jù)某種策略交換出部分頁面到輔存。根據(jù)作業(yè)的執(zhí)行情況裝入作業(yè)的部分實體，顯然節(jié)省了內(nèi)存空間。請求分頁管理和分頁管理的數(shù)據(jù)結(jié)構(gòu)、地址映射和存儲保護(hù)、存儲分配與回收等都類似，但請求分頁管理的實現(xiàn)過程復(fù)雜很多，需要由硬件和軟件的相互配合才能完成。1.請求調(diào)入及缺頁中斷處理2.淘汰算法3.抖動與工作集第3頁/共38頁請求分頁存儲管理鋪墊作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全部地址空間的一部分。例如用戶編制的出錯處理子程序，在作業(yè)正常運行情況下不會執(zhí)行這些程序，沒有必要把它們調(diào)入內(nèi)存。即程序中往往會有一些彼此互斥的部分不是每次運行時都能執(zhí)行到。

程序的局部性。順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù)據(jù)(如數(shù)組)。它們通常被限定在某一連續(xù)區(qū)域。一旦某一位置被訪問后，那么它附近的位置很快也會被訪問。第4頁/共38頁

基于上述情況，就沒有必要把一個作業(yè)一次性全部裝入內(nèi)存再開始運行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時調(diào)入，由操作系統(tǒng)和硬件相配合來完成主存和輔存之間信息的動態(tài)調(diào)度。這樣的計算機(jī)系統(tǒng)好像為用戶提供了一個存儲容量比實際主存大得多的存儲器，就稱為虛擬存儲器。第5頁/共38頁虛擬存儲器的概念P61虛擬存儲技術(shù)的基本思想是利用大容量的外存來擴(kuò)充內(nèi)存，產(chǎn)生一個比有限的實際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間，以有效地支持多道程序設(shè)計的實現(xiàn)和大型程序運行的需要，增強(qiáng)系統(tǒng)的處理能力。請求分頁系統(tǒng)支持虛擬存儲技術(shù)第6頁/共38頁

請求分頁存儲管理名詞作業(yè)的邏輯地址空間劃分的頁，稱為虛頁主存稱為實存實存中的塊稱為實頁第7頁/共38頁

請求分頁存儲管理基本原理請求分頁系統(tǒng)對地址空間和內(nèi)存空間的管理采用與分頁存儲管理系統(tǒng)相同的方式，但是它只將作業(yè)的部分頁面裝入內(nèi)存，便可開始運行作業(yè)，作業(yè)的其他部分被存放在輔助存儲器上。第8頁/共38頁請求分頁存儲管理必須解決的問題一個作業(yè)不全部裝入，該作業(yè)能否開始運行，并運行一段時間？當(dāng)程序要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn)這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？缺頁時，所需的頁面從何處裝入？裝入到何處？若此時實存中沒有空閑塊應(yīng)怎么辦？第9頁/共38頁一個作業(yè)不全部裝入，該作業(yè)能否開始運行，并運行一段時間？作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全部地址空間的一部分。例如用戶編制的出錯處理子程序，在作業(yè)正常運行情況下不會執(zhí)行這些程序，沒有必要把它們調(diào)入內(nèi)存。即程序中往往會有一些彼此互斥的部分不是每次運行時都能執(zhí)行到。

程序的局部性。順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù)據(jù)(如數(shù)組)。它們通常被限定在某一連續(xù)區(qū)域。一旦某一位置被訪問后，那么它附近的位置很快也會被訪問。因此，沒有必要把一個作業(yè)一次性全部裝入內(nèi)存再開始運行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時調(diào)入，由操作系統(tǒng)和硬件相配合來完成主存和輔存之間信息的動態(tài)調(diào)度。第10頁/共38頁當(dāng)程序要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn)

這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？地址變換機(jī)構(gòu)檢測到虛頁的狀態(tài)為1，由硬件產(chǎn)生缺頁中斷，轉(zhuǎn)去中斷處理第11頁/共38頁

所需的頁面從何處裝入？

在請求分頁管理系統(tǒng)中，當(dāng)一個作業(yè)完成編譯鏈接后，所形成的裝配模塊通常以文件形式存入作為輔存的磁盤上，當(dāng)該頁需要裝入實存時，就從磁盤上調(diào)進(jìn)來。為此，需建立一個作業(yè)的輔助頁表，也稱為外頁表。虛頁號輔存地址第12頁/共38頁新調(diào)入的頁面裝入何處？實存中有空閑實頁，直接將其裝入?？臻e已滿，則必須淘汰（頁面置換算法）實存中的某一頁。

被淘汰的頁，以后可能還要用，是否需要寫回輔存，這取決于該頁進(jìn)入實存后是否被修改，如未被修改，因輔存上已有副本則不必寫回輔存。否則，要重新寫回輔存。因此頁表中還可以增加一個“修改位”，以反映該頁是否已被修改過。為了便于系統(tǒng)管理頁面置換，增加“引用位”，表示該頁最近是否被訪問過。第13頁/共38頁虛頁號主存塊號改變位引用位狀態(tài)位輔存地址0/11該頁已被修改過0該頁未被修改0/11最近已被訪問過主存塊號0/10在內(nèi)存1不在內(nèi)存輔助頁表虛頁號輔存地址保護(hù)信息擴(kuò)充后的PMT表第14頁/共38頁圖缺頁中斷的發(fā)生及其處理抖動/系統(tǒng)顛簸第15頁/共38頁抖動/系統(tǒng)顛簸出頁：將某一頁從實存移到輔存入頁：將某一頁從輔存調(diào)入實存這種反復(fù)進(jìn)行入頁和出頁的現(xiàn)象稱為“抖動/系統(tǒng)顛簸”第16頁/共38頁

先進(jìn)先出算法(FIFO)淘汰駐留主存時間最長的頁面最近最久未用置換算法(LRU)淘汰在最近一段時間最久未用的頁面最近最不常用算法最近未使用算法頁面置換算法/淘汰算法第17頁/共38頁1.先進(jìn)先出算法（FIFO算法）

這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪問的可能性最大。

第18頁/共38頁2．最近最久未使用頁面置換算法（LeastRecentlyUsed/LRU算法）這種算法的基本思想是，如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮了程序設(shè)計的局部性原理。其實質(zhì)是，當(dāng)需要置換一頁時，選擇在最近一段時間最久未使用的頁面予以淘汰。實現(xiàn)這種算法可通過周期性地對“引用位”進(jìn)行檢查，并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時間t，淘汰時選擇t最大的頁面。

不太實用第19頁/共38頁

性能分析為了盡可能地減少缺頁中斷的次數(shù)，應(yīng)從程序設(shè)計的質(zhì)量頁面的大小主存的容量頁面置換算法等幾方面來考慮。第20頁/共38頁程序設(shè)計的質(zhì)量(主要指程序的局部化程度)程序的局部化程度包括時間局部化和空間局部化時間局部化是指一旦某個位置----數(shù)據(jù)或指令----被訪問了，它常常很快又要再次被訪問。這可通過循環(huán)、經(jīng)常用到的變量和子程序等程序結(jié)構(gòu)來實現(xiàn)?？臻g局部化是指一旦某個位置被訪問到，那么它附近的位置很快也要用到。這可以盡量采用順序的指令列、線形的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。局部化程度隨程序而異，一般來說，總希望編制的程序具有較高的局部化程度。這樣，程序執(zhí)行時可經(jīng)常集中在幾個頁面上進(jìn)行訪問，以減少缺頁中斷的次數(shù)。第21頁/共38頁頁面的大小頁面大小應(yīng)根據(jù)實際情況來確定，它和計算機(jī)的性能以及用戶的要求都有關(guān)系。頁面大，頁表小，占用空間小，缺頁中斷次數(shù)少，但換頁時間長，頁內(nèi)碎片也大，浪費空間頁面小時，正好相反第22頁/共38頁主存的容量一個作業(yè)的執(zhí)行所產(chǎn)生缺頁的次數(shù)是存放頁面的實際存儲容量的函數(shù)。當(dāng)存儲容量達(dá)到某一程度時，缺頁中斷的次數(shù)的減少就不明顯了。試驗分析表明：對所有程序來說，要使之有效地工作，它在主存中的頁面數(shù)不低于它的總頁面數(shù)的一半。第23頁/共38頁圖存儲容量與缺頁中斷次數(shù)的關(guān)系第24頁/共38頁4．頁面置換算法性能三個參數(shù)：頁面走向：每個作業(yè)的虛頁調(diào)入實存的順序，稱為頁面軌跡，或頁面走向，用P表示。主存容量：是指分配給作業(yè)的主存塊數(shù)，M表示。置換算法：包括FIFO，LRU等第25頁/共38頁例1

設(shè)頁面走向為P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置換算法采用FIFO，求訪問過程中發(fā)生缺頁中斷的次數(shù)和缺頁率？假設(shè)開始時，主存未裝入任何塊。表1FIFO性能分析例(M=3)缺頁中斷次數(shù)F=9缺頁率f=9/12=75%P行表示頁面走向，M行表示在主存中的頁面號，其中帶有+的表示新調(diào)入頁面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時刻將被淘汰頁面，F(xiàn)行表示是否引起缺頁中斷，帶+號的表示引起缺頁中斷。第26頁/共38頁

例2

設(shè)M=4，其余同例1。則缺頁中斷次數(shù)和缺頁率？表2FIFO性能分析例(M=4)缺頁中斷次數(shù)F=10缺頁率f=10/12=83%第27頁/共38頁由表1，表2得出：對于FIFO算法，內(nèi)存增加，缺頁率反而增加！異常現(xiàn)象（Belady異常）第28頁/共38頁

例3

設(shè)頁面走向如上，M=3，置換算法為LRU，則缺頁中斷次數(shù)和缺頁率？由于采用LRU算法，M中各列按訪問的時間順序排列，最近被訪問的頁面在最前。表3LRU性能分析例(M=3)缺頁中斷次數(shù)F=10，缺頁率f=10/12=83%。第29頁/共38頁例4

設(shè)M=4，其余同例3，則缺頁中斷次數(shù)和缺頁率？表4LRU性能分析例(M=4)第30頁/共38頁34第31頁/共38頁

由表3，表4可得如下事實：設(shè)G(P,M,t)表示當(dāng)頁面走向為P，主存容量為M，在時刻t的頁面集合，對于LRU算法，存在如下關(guān)系，即成立。即對于任何時刻t(t=1,2,…,12),G(P,M,t)所選中的頁號必定包含在G(P,M+1,t)之中。這種關(guān)系說明了增加主存容量不會增加缺頁中斷次數(shù)，然而對FIFO算法，此關(guān)系并不成立。第32頁/共38頁

請求分頁存儲管理方案的評價它提供了大容量的多個虛擬存儲器，作業(yè)地址空間不再受實存容量的限制；更有效地利用了主存，一個作業(yè)的地址空間不必全部同時都裝入主存，只裝入其必要部分，其它部分根據(jù)請求裝入，或者根本就不裝入(如錯誤處理程序等)；更加有利于多道程序的運行，從而提高了系統(tǒng)效率；方便了用戶，特別是大作業(yè)用戶。

第33頁/共38頁

缺點為處理缺頁中斷，增加了處理機(jī)時間的開銷，即請求分頁系統(tǒng)是用時間的代價換取了空間的擴(kuò)大；可能因作業(yè)地址空間過大或多道程序道數(shù)過多以及其它原因而造成系統(tǒng)抖動；為防止系統(tǒng)抖動所采取的各種措施會增加系統(tǒng)的復(fù)雜性。第34頁/共38頁復(fù)習(xí)LRU頁面調(diào)度算法是選擇（）的頁面先調(diào)出。A．最近才使用B．最久未被使用

C．駐留時間最長D．駐留時間最短若進(jìn)程執(zhí)行到某條指令時發(fā)生了缺頁中斷，經(jīng)