1、基本工作原理

1、基本工作原理 在進程開始運行之前，不是全部裝入頁面，而是裝入一個或者零個頁面，之后根據進程運行的需要，動態裝入其他頁面；當內存已滿，而又需要裝入 新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面。在使用虛擬頁式存儲管理時需要在頁表中增加一些內容： 頁號、駐留位（中斷位）、內存塊號、外存地址、訪問號、修改位駐留位：表示該頁在外存還是內存； 訪問位：表示該頁在內存期間是否被訪問過，又稱R位； 修改位：表示該頁在內存中是否被修改過，又稱M位；

2、缺頁中斷 在地址映射過程中，若在頁表中發現所要訪問的頁面不在內存，則產生中斷，當發生中斷時，系統必須在內存選擇一個頁面移出內存， 以便為調入新的頁面讓出空間，盡管每次可以隨機選選擇一個頁面置換，但選擇不常使用的頁面會是系統性能好的多，減少不必要的額外 開銷，就產生了頁面置換算法。3、頁面置換算法： 3.1理想頁面（Optimal， OPT)置換算法 發生缺頁時，有些頁面在內存中，其中有一頁將很快被訪問(包含緊接著 的下一條指令的那頁)，而其他頁則可能到10、 100或1000條指令后才會被訪問，每個頁都可以用在該頁面首次被訪問前所要執行的指令數進行標記。標記樹最大的頁應該被置換。舉例：如果某頁在八百萬條指令內不會被使用，另外一頁在六百萬條指令不會被使用，則置換前一個頁面。這個算法無法實現，因當缺頁 中斷時，系統無法知道各個頁面下一次在什么時候被訪問3.2先進先出置換算法（First In First Out, FIFO) 置換最先調入內存的頁面，即置換在內存中駐留時間最久的頁面。按照進入內存的先后次序排列成隊列，從隊尾進入，從隊首刪除。但是 該算法會淘汰經常訪問的頁面，不適應進程實際運行的規律，目前已經很少使用。3.3最近最久未使用置換算法（Least Recently Used， LRU） 剛被訪問的頁面，可能馬上又要被訪問；而較長時間內沒有被訪問的頁面，可能最近不會被訪問。 LRU算法普偏地適用于各種類型的程 序，但是系統要時時刻刻對各頁的訪問歷史情況加以記錄和更新，開銷太大，因此LRU算法必須要有硬件的支持。3.4第二次機會頁面置換算法 FIFO算法可能會把經常使用的頁面置換出去，為了避免這一問題，對該算法進行簡單的修改：檢查最老頁面的R位，如果R位是0，那么 這個頁面又老有沒用，可以立即置換出去，如果是1，就清零R位，并將該頁放到鏈表的尾端，修改它的裝入時間使它就像裝入的一樣， 然后繼續搜索。如果所有的頁面都被訪問過，那么該算法就被降為純粹的FIFO算法。3.5時鐘頁面置換算法 由于第二次機會頁面置換算法要經常在鏈表中移動頁面，降低了效率。一個更好的辦法，將所有的頁面存在一個類似鐘表面的環形鏈 表中。3.6最近未使用(NRU：Not Recently Used) 用R位和M位構造一個簡單的頁面置換算法：當啟動一個進程時，它的所有頁的兩個位都由操作系統設置成0，R位被定期的清零，以 區別最近沒有被訪問的頁和被訪問了的頁。 根據R位和M位，分為4類頁面 第0類：沒有被訪問，沒有被修改 第1類，沒有被訪問，被修改 第2類，被訪問，沒有被修改 第3類，被訪問，被修改。 NRU算法隨機地從編號最小的非空類中挑選一個頁淘汰之。這個算法隱含的意思是，淘汰一個在最近一個時鐘周期內沒有被訪問 的已修改頁要比淘汰一個被頻繁訪問的干凈的頁好。4、Belady異常現象 從直覺上看，在內存中的物理頁面數越多，程序的缺頁次數應該越少，但是實際情況并不是這樣。Belady在1969年發現一個反例， 使用FIFO算法時，四個頁框時缺頁次數比三個頁框時多。這種奇怪的情況稱為Belady異常現象。5、影響缺頁次數的因素 1）分配給程序的物理頁面數 2）頁面的大小 3）程序的編制方法 4）頁面置換算法

2、計算缺頁次數

理想頁面（Optimal， OPT)置換算法

先進先出置換算法（First In First Out, FIFO)

最近最久未使用置換算法（Least Recently Used， LRU）

在一個請求頁式存儲管理中，一個程序的頁面走向為3，4，2，1，4，5，4，3，5，1，2，并采用LRU算法。設分配給該程序的存儲塊 數 S 分別為3 和 4，在該訪問中發生的缺頁次數 F

總結

以上是生活随笔為你收集整理的操作系统：虚拟页式存储管理（缺页中断、页面置换算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。