Page replacement 1：演算法介紹

 摘要

比較五種分頁替換演算法 (page replacement algorithm)在三種不同資料型態中的表現，演算法分別有Optimal、FIFO、ARB、LIFO、NRA，資料型態分別有均勻隨機、區域隨機、常態隨機。整體的排名為（差）ARB > FIFO > LIFO > NRA > Optimal（優），ARB和LIFO更新記憶體分頁較公平，故在區域隨機資料表現較佳；而LIFO和NRA更新記憶體分頁較不公平，故在常態隨機資料表現較佳。


壹、簡介

分頁 (paging)技術應用於虛擬記憶體 (virtual memory)上，頁框 (frame)為實體記憶體 (physical memory)切出來的區塊，分頁 (page)為虛擬記憶體切出來的區塊，而頁框與分頁的大小會一樣，最後分頁與頁框的對應表，就稱為分頁表 (page table)。

作業系統要存取分頁時，會先查詢分頁表此分頁是否存在記憶體中？如果不存在，就會發生分頁錯誤 (page fault)。如果記憶體還有餘裕的空間，分頁就會從硬碟中載入記憶體中，並更新分頁表；如果記憶體已經滿了，就會尋找一個犧牲者 (victim)，移除犧牲者，將新分頁從硬碟載入記憶體中，並更新分頁表。尋找恰當的犧牲者，就是分頁替換演算法 (page replacement algorithm)要處理的問題。

本次實驗會實作五種分頁替換演算法，分別為最佳演算法 (optimal algorithm)、先進先出演算法 (first in first out, FIFO)、後進先出演算法 (last in first out, LIFO) 、Additional reference bits algorithm (ARB)、常態隨機累積演算法 (normal random accumulation, NRA) 。NRA是我設計的分頁替換演算法，融合LIFO和常態分佈 (normal distribution)的概念。本次實驗的資料有三種型態，分別為均勻隨機 (uniform random)、區域隨機 (local random)、常態隨機 (normal random)。


貳、分頁替換演算法 (page replacement algorithm)

一、最佳演算法 (optimal algorithm)

最佳演算法的效能是所有演算法的天花板，犧牲者未來將不會再被使用或未來最久才再被使用。因此最佳演算法要能預知未來分頁被使用的情況，但實際上我們無法預知未來，故此演算法很難被實作與應用。

二、先進先出演算法 (first in first out, FIFO)

FIFO的核心理念是先來者先出去，故犧牲者為先來者，也就是存在記憶體中最久的分頁。FIFO可以使用佇列 (queue)來實作，是易實作且實用的演算法。FIFO的特性使得佇列中的分頁得以經常被更新，而且所有分頁都有機會被替換。

三、後進先出演算法 (last in first out, LIFO)

LIFO的核心理念剛好和FIFO相反，是先來者後出去，故犧牲者為後來者，也就是存在記憶體中最短的分頁。LIFO可以使用堆疊 (stack)來實作，也是易實作的演算法。LIFO的特性使得堆疊中的分頁除了頂端 (top)會頻繁更新外，其餘分頁都不會被更新，因此適合頻繁使用相同分頁的資料型態。

四、Additional reference bits algorithm (ARB)

ARB顧名思義即額外使用參考位元去決定犧牲者，通常會使用8位元並間隔一段時間，更新在記憶體內所有分頁的ARB。更新方式是用位元運算，每次更新位元會往左移1位元，而最近有被參考過的分頁，其最高位元會是1；而最近沒有被參考的分頁，其最高位元會是0，因此透過ARB的值可以粗略判斷分頁最近是否有被使用過？

五、常態隨機累積演算法 (normal random accumulation, NRA) 

此方法是我改良LIFO而來的，其核心理念和LIFO一致，都是預期資料會頻繁使用相同分頁。LIFO有個缺點就是，犧牲者永遠是堆疊中的頂端，也就是最後進來的分頁會不斷被替換。因此如果一開始載進來的分頁都是不常使用的，LIFO是無法把這些不常用的先來者替換掉，故我加入常態分佈的抽樣，使得非頂端的部分有機會被替換掉。

同時為了讓越靠近堆疊底部 (bottom)的分頁是使用次數越多的，也導入計數器 (counter)的機制。分頁被使用時，計數器會加1；分頁成為犧牲者時，計數器會減1，所以犧牲者一定是計數器為0者，且越頂端越容易成為犧牲者。


相關文章

  1. Page replacement 1：演算法介紹
  2. Page replacement 2：實驗結果與結論
  3. Page replacement source code
  4. 高等作業系統｜使用者的代理人｜王友群
  5. 排程力 Schedule Z 1：軟體使用說明
  6. 排程力 Schedule Z 2：演算法介紹｜VIG_VNS for TSPTW
  7. 排程力 Schedule Z 3：結果、結論與心得
  8. Schedule Z載點
  9. Schedule Z程式原始碼


引用文獻

  1. Magic Len。2015。分頁替換演算法(Page Replacement Algorithm)介紹與模擬。MagicLen [Accessed by Oct. 2021]

留言

張貼留言