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

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

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

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

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

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

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

這種缺頁情況？發現后應如何處理？地址變換機構檢測到虛頁的狀態為1，由硬件產生缺頁中斷，轉去中斷處理第11頁/共38頁

所需的頁面從何處裝入？

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

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

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

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

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

不太實用第19頁/共38頁

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

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

例2

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

例3

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

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

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

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

第33頁/共38頁

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

C．駐留時間最長D．駐留時間最短若進程執行到某條指令時發生了缺頁中斷，經