作業系統——虛拟存儲器（頁面置換算法）

文章目錄

• 一、最佳置換算法（OPT）
• 二、先進先出頁面置換算法（FIFO）
• 三、最近最久未使用置換算法（LRU）
• 四、最少使用置換算法（LFU）
• 五、Clock置換算法（最近未使用算法 NRU）
• 六、頁面緩沖算法（PBA）
• 七、通路記憶體的有效時間

位址映射過程中，若在頁面中發現所要通路的頁面不在記憶體中，則産生缺頁中斷。

當發生缺頁中斷時，如果作業系統記憶體中沒有空閑頁面，則作業系統必須在記憶體選擇一個頁面将其移出記憶體，以便為即将調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換算法。

一、最佳置換算法（OPT）

• 其所選擇的被淘汰頁面是以後永不使用的，或許是在未來最長時間内不再被通路的頁面。
• 采用最佳置換算法，通常可以保證獲得最低的缺頁率。
• 但由于人們目前無法預知，哪個頁面是未來最長時間不被通路的，是以該算法是無法實作的，但可以用該算法去評價其他算法。

  

二、先進先出頁面置換算法（FIFO）

• 該算法總是淘汰最先進入記憶體的頁面，即選擇在記憶體中駐留時間最久的頁面予以淘汰。
• 這種算法的實作和隊列是一樣，OS維護一個目前在記憶體中的所有頁面的連結清單，最新進入的頁面在尾部，最久的在頭部，每當發生缺頁中斷，就替換掉表頭的頁面并且把新調入的頁面加入到連結清單末尾。

  

三、最近最久未使用置換算法（LRU）

• 當需要淘汰一個頁面時，總是選擇最近最久未使用的頁面予以淘汰

  

• LRU 置換算法的硬體支援
  • 寄存器
    • 為了記錄某程序唉記憶體中各頁的使用情況，須為每個在記憶體中的頁面配置一個移位寄存器。

      

  • 棧
    • 每當程序通路某頁面時，便将該頁面的頁面号從棧中移出，将它壓入棧頂。
    • 是以，棧頂始終是最新被通路的頁面編号，棧底是最近最久未使用的頁面編号。

      

四、最少使用置換算法（LFU）

• 采用該算法時，應為在記憶體中的每個頁面設定一個移位寄存器，用來記錄該頁面被通路的頻率。
• 當需要淘汰一個頁面時，總是選擇最近時期使用最少的頁面予以淘汰。
• LFU 與 LRU 的通路圖完全相同。

五、Clock置換算法（最近未使用算法 NRU）

• LRU算法的性能接近于OPT，但是實作起來比較困難，且開銷大；
• FIFO算法實作簡單，但性能差。是以作業系統的設計者嘗試了很多算法，試圖用比較小的開銷接近LRU的性能，這類算法都是CLOCK算法的變體。
• 簡單的CLOCK算法
  • 給每一幀關聯一個附加位，稱為使用位。當某一頁首次裝入主存時，該幀的使用位設定為1；當該頁随後再被通路到時，它的使用位也被置為1。
  • 對于頁替換算法，用于替換的候選幀集合看做一個循環緩沖區，并且有一個指針與之相關聯。當某一頁被替換時，該指針被設定成指向緩沖區中的下一幀。當需要替換一頁時，作業系統掃描緩沖區，以查找使用位被置為0的一幀。
  • 每當遇到一個使用位為1的幀時，作業系統就将該位重新置為0；如果在這個過程開始時，緩沖區中所有幀的使用位均為0，則選擇遇到的第一個幀替換；如果所有幀的使用位均為1,則指針在緩沖區中完整地循環一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁。
  • 由于該算法循環地檢查各頁面的情況，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法。

    

• 改進的 Clock 算法
  • CLOCK算法的性能比較接近LRU，而通過增加使用的位數目，可以使得CLOCK算法更加高效。在使用位的基礎上再增加一個修改位，則得到改進型的CLOCK置換算法。這樣，每一幀都處于以下四種情況之一：
    • 最近未被通路，也未被修改(u=0, m=0)。
    • 最近被通路，但未被修改(u=1, m=0)。
    • 最近未被通路，但被修改(u=0, m=1)。
    • 最近被通路，被修改(u=1, m=1)。
  • 算法執行如下操作步驟：
    • 從指針的目前位置開始，掃描幀緩沖區。在這次掃描過程中，對使用位不做任何修改。選擇遇到的第一個幀(u=0, m=0)用于替換。
    • 如果第1)步失敗，則重新掃描，查找(u=0, m=1)的幀。選擇遇到的第一個這樣的幀用于替換。在這個掃描過程中，對每個跳過的幀，把它的使用位設定成0。
    • 如果第2)步失敗，指針将回到它的最初位置，并且集合中所有幀的使用位均為0。重複第1步，并且如果有必要，重複第2步。這樣将可以找到供替換的幀。
  • 改進型的CLOCK算法優于簡單CLOCK算法之處在于替換時首選沒有變化的頁。由于修改過的頁在被替換之前必須寫回，因而這樣做會節省時間。

六、頁面緩沖算法（PBA）

七、通路記憶體的有效時間