一、操作系統幾種主要的頁面置換算法
算法通常只是描述解決問題的一個步驟,具體用什么數據結構實現則是視情況而定。LRU“實現起來比較困難,且開銷大是因為LRU算法希望淘汰最后未使用的頁面,而CLOCK算法則放低的要求,較久未使用即可,不一定是最久的。CLOCK算法恰好可以充分使用現有的為“請求分頁存儲管理“設計的硬件機構,所以也會更加高效,而LRU則難以使用現成的硬件機構來加速算法執行。
LRU又稱最近最少使用,意為每次都淘汰最久未使用的頁面。按照LRU的思想,一種實現思路如下三點:
開辟一塊內存空間用來記錄每個頁面最后一次使用的時間(這里假如使用heap或者無序array來記錄);每次訪存都要去維護這個時間;要淘汰頁面的時候選擇出最久未使用的頁面予以淘汰;下面來逐一分析這三點:
名列前茅點:這塊內存空間不能太小,否則極易導致數據溢出,尤其是對于運行在server上OS來說,可能一開機就很久不關機,溢出的可能性更大。這段內存空間也不能太大,不然會造成空間浪費;
第二點:每執行一條指令必定帶來至少一次訪存,甚至更多,每次訪存都要去維護這個時間開銷無疑是很大的(CLOCK算法也要去維護一個bit,但是開銷卻小得多,原因后面再討論),因為使用數組記錄則需要線性的時間來維護,使用heap記錄則需要對數時間來維護,而訪存則是十分頻繁的,這個代價是不能接受的;值得一提的是雖然看起來heap開銷小一些,但是數據量很大的話heap相對無序array來說對緩存不友好,這也是一個問題,不過我不知道是否可以忽略;
第三點:選擇出最久未使用的頁面的開銷也很大,使用無序array記錄則需要線性的時間來查找,使用heap記錄則需要對數時間來查找;
綜合上述三點可知LRU具體實現起來確實很困難開銷也很大。那么CLOCK算法和LRU相比優勢在哪里?
未改進CLOCK算法需要維護一個bit,用來標志該頁面是否被使用過;很自然地想到同樣需要三點,即存儲,維護和查找,但是前兩點(存儲和維護)的實現和開銷相對LRU則簡單很多。
延伸閱讀:
二、全局頁面置換算法
工作集模型工作集頁置換算法缺頁率置換算法功能:
當缺頁中斷發生,需要調入新的頁面而內存已滿時,選擇內存當中哪個物理頁面被置換。
目標:
盡可能地減少頁面的換進換出次數(既缺頁中斷的次數)。具體來說,把未來不再使用的或短期內較少使用的頁面換出,通常只能在局部性原理指導下依據過去的統計數據來進行預測。
頁面鎖定(frame locking):
用于描述必須常駐內存的操作系統的關鍵部分或時間關鍵(time-critical)的應用程序。實現的方法是L在頁表中添加鎖定標志位(lock bit)。使其不在頁面置換算法范圍之內,也就說不會被換入換出。
通常只需要考慮頁號,因為偏移號一般不起作用。只保留頁號。基于這個list來設計各種的頁面替換算法。
通過模擬一個頁面置換的行為并且記錄產生頁缺失數的數量。一般情況下,產生的缺頁次數越少,性能就越高。