国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 操作系統幾種主要的頁面置換算法分別是用什么數據結構實現的?

操作系統幾種主要的頁面置換算法分別是用什么數據結構實現的?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 05:20:02 1696972802

一、操作系統幾種主要的頁面置換算法

算法通常只是描述解決問題的一個步驟,具體用什么數據結構實現則是視情況而定。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來設計各種的頁面替換算法。
通過模擬一個頁面置換的行為并且記錄產生頁缺失數的數量。一般情況下,產生的缺頁次數越少,性能就越高。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT