頁面替換演算法


頁面替換演算法決定哪個記憶體頁面將被替換。 替換過程有時稱為換出或寫入磁碟。在主記憶體儲器中找不到請求的頁面時(頁面錯誤),完成頁面替換。

虛擬記憶體有兩個主要方面,即影格分配和頁面替換。 擁有最佳的影格分配和頁面替換演算法是非常重要的。 影格分配全部是關於將多少影格分配給進程,而頁面替換則是確定需要替換的頁碼,以便為請求的頁面留出空間。

如果演算法不是最優的?

  1. 如果分配給進程的影格數量不夠或不準確,則可能會出現抖動問題。 由於缺少影格,大部分頁面將駐留在主記憶體中,因此會出現更多頁面錯誤。但是,如果作業系統將更多的影格分配給進程,則可能會出現內部碎片。

  2. 如果頁面替換演算法不是最優的,那麼也會出現抖動問題。 如果在不久的將來會參照被請求的頁面替換的頁面數量,那麼將會有更多的插入和換出數量,因此作業系統必須執行更多的替換操作,這會導致效能不足。

因此,最佳頁面替換演算法的任務是選擇可限制抖動的頁面。

頁面替換演算法的型別

有各種頁面替換演算法。 每種演算法都有一個不同的方法,用來替換頁面。

  1. 最佳頁面替換演算法- 這種演算法取代了將來不會被參照的頁面。 雖然它不能實際實行,但可以用作基準。 其他演算法在最優性方面與此相比較。

  2. 最近使用過的(LRU)頁面替換演算法 - 該演算法替代長時間未被參照的頁面。 該演算法與最佳頁面替換演算法相反。

  3. FIFO - 在這個演算法中,維護一個佇列。 首先分配影格的頁面將首先被替換。 換句話說,在佇列稀有端的頁面將被替換為每個頁面錯誤。