⑴ 頁面置換演算法
在瞎啟虛程序的執行過程中,當所訪問的信息不在內存時,會由操作系統負責將所需信息從外存調入內存,然後再繼續執行程序,如果在調入內存時,發現內存空間不夠,會由操作系統負責將內存中暫時用不到的信息換出到外存,由於頻繁的進行IO操作會影響計算機性能,所以我們需要使用合適的演算法來進行頁面的置換。這里介紹幾種常見的頁面置換演算法:
每次選擇淘汰的頁面將是以後永不使用,或者在最長時間不再被訪問的頁面,這樣可以保證最低的缺頁率。但是實際上進程執行的過程才能知道接下來會訪問到的是哪個頁面,操作系統無法預知,因此最佳置換演算法是一種 理想化 演算法,無法實現。
每次旁純選擇淘汰的頁面是最早進入內存的頁面,這種演算法雖然實現簡單,但是該演算法與進程實際運行時的規律不適應,因為先進入的頁面也有可能最經常被訪問,因此該演算法性能磨燃很差。
每次淘汰的頁面是最近最久未被使用的頁面,需要有額外的內存空間來記錄該頁面自上次被訪問以來所經過的時間,但是性能很好。
該演算法是一種性能和開銷較均衡的演算法,又稱最近未使用演算法(NRU)。每個頁面需要額外添加兩個標志位:訪問位(0代表最近沒有被訪問,1代表最近被訪問)、修改位(0代表最近沒有被修改,1代表最近被修改過)。如果淘汰的頁面最近是被修改過,那麼淘汰該頁面前會進行寫入外存的IO操作,使性能變差,所以在其他條件都相同的情況下,應優先淘汰沒有修改過的頁面。
演算法規則:將所有可能被置換的頁面排成一個循環隊列 (訪問位, 修改位)
第一輪:從當前位置開始掃描到第一個(0,0)的頁用於替換。
第二輪:若第一輪掃描失敗,則重新掃描,查找第一個(0,1)的頁面用於替換,同時將掃描過的頁面的訪問位設為0。例如(1,0)變成(0,0)
第三輪:若第二輪掃描失敗,則重新掃描,查找第一個(0,0)的頁面用於替換。
第四輪:若第三輪掃描識別,則重新掃描,查找第一個(0,1)的頁面用於替換。本次掃描必定會有一個頁面被選中。
⑵ 頁面置換演算法
上文說到,請求分頁管理方式中,當需要調入頁面到內存中,但此時內存已滿,就需要從內存中按照一定的置換演算法決定將哪個頁面取出將內存給調入的頁面。本文將介紹幾種頁面置換算方法。
本文內容
演算法思想:每次選擇 淘汰的頁面 將是 以後永不使用 ,或者 在最長時間內不再被訪問的頁面 ,這樣可以保證最低的缺頁率。
舉例說明,假設系統為進程分配了三個內存塊,並考慮到有以下頁面號引用串(會依次訪問這些頁面):7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
....按照此演算法依次執行,最後的結果如下
結果圖
註:缺頁時未必發生頁面置換,若還有可用的空閑內存空間就不用進行頁面置換。
最佳置換演算法可以保證最低的缺頁率,但是實際上,只有進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法提前預判頁面的訪問序列。因此, 最佳置換演算法是無法實現的 。
演算法思想:每次選擇 淘汰的頁面是最早進入內存的頁面。
該演算法很簡單,每次淘汰最在內存中待時間最久的各個,下面分別給出系統為進程分為配三個內存塊和四個內存塊的執行情況圖。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4
分配三個內存塊的情況:
分配四個內存塊的情況:
當為進程分配的物理塊數增大時,缺頁次數不減反增的異常現象稱為 貝萊迪(Belay)異常 。
只有FIFO演算法會產生Belay異常。 另外,FIFO演算法雖然實現簡單,但是該演算法與進程實際運行時的規律不適應。因為先進入的頁面也有可能最經常被訪問。因此, 演算法性能差。
演算法思想: 每次淘汰的頁面是最近最久未使用的頁面。
實現方法:賦予每個頁面對應的頁表項中,用 訪問欄位記錄該頁面純虧自上次被訪問以來所經歷的時間t。 當需要淘汰一個頁面時,選擇現有頁面中t最大的頁面,即最近最久未使用。
舉例說明,加入某系統為某進程分配了四個內存塊,並考慮到有以下頁面號引用串:1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
這里先直接給出答案
結果圖
最佳置換演算法那性能最好,但無法實現。先進先出置換演算法實現簡單,但是演算法性能差。最近最久未使用置換演算法性能好,是最接近OPT演算法性能的,但是實現起來需要專門的硬體支持,演算法開銷大。 時鍾置換演算法 是一種 性能和開銷均春褲配平衡 的演算法。又稱 CLOCK演算法 ,或 最近未用演算法 ( NRU ,Not Recently Used)
簡單CLOCK演算法 演算法思想:為每個頁面設置一個 訪問位 ,再將內存中的頁面都通過 鏈接指針鏈接成一個循環隊列 。當某個頁被訪問時,其訪問位置1.當需要淘汰一個頁面時,只需檢查頁的訪問位。如果是0,就選擇該頁換出;如果是1,暫不換出,將訪問位改為0,繼續檢查下一個頁面,若第一輪掃描中所有的頁面都是1,則將這些頁面的訪問位一次置為0後,再進行第二輪掃描(第二輪掃描中一定會有訪問位為0的頁面,因此簡單的CLOCK演算法選擇一個扒指淘汰頁面最多會經過 兩輪掃描 )。
這個演算法指針在掃描的過程就像時鍾一樣轉圈,才被稱為時鍾置換演算法。
簡單的時鍾置換演算法僅考慮到了一個頁面最近是否被訪問過。事實上,如果淘汰的頁面沒有被修改過,就不需要執行I/O操作寫回外存。 只有淘汰的頁面被修改過時,才需要寫回外存。
因此,除了考慮一個頁面最近有沒有被訪問過之外,操作系統還需要考慮頁面有沒有被修改過。
改進型時鍾置換演算法的 演算法思想 : 在其他在條件相同時,應該優先淘汰沒有被修改過的頁面, 從而來避免I/O操作。
為了方便討論,用(訪問位,修改位)的形式表示各頁面的狀態。如(1,1)表示一個頁面近期被訪問過,且被修改過。
演算法規則 :將所有可能被置換的頁面排成一個循環隊列
由於第二輪已將所有的頁的訪問位都設為0,因此第三輪、第四輪掃描一定會選中一個頁,因此 改進型CLOCK置換演算法最多會進行四輪掃描。
假設系統為進程分配了5個內存塊,某時刻,各個頁的狀態如下圖
如果此時有新的頁要進入內存,開始第一輪掃描就找到了要替換的頁,即最下面的狀態為(0,0)的頁。
某一時刻頁面狀態如下
如果此時有新的頁要進入內存,開始第一輪掃描就發現沒有狀態為(0,0)的頁,第一輪掃描後不修改任何標志位。所以各個頁狀態和上圖一樣。
然後開始第二輪掃描,嘗試找到狀態為(0,1)的頁,並將掃描過後的頁的訪問位設為0,第二輪掃描找到了要替換的頁。
某一時刻頁面狀態如下
第一輪掃描沒有找到狀態為(0,0)的頁,且第一輪掃描不修改任何標志位,所以第一輪掃描後狀態和上圖一致。
然後開始第二輪掃描,嘗試找狀態為(0,1)的頁,也沒有找到,第二輪掃描需要將訪問位設為1,第二輪掃描後,狀態為下圖
某一時刻頁面狀態如下
具體的掃描過程和上面相同,這里只給出最後的結果,如下圖
所以,改進型的CLOCK置換演算法最多需要四輪掃描確定要置換的頁。從上面的分析可以看出,改進型的CLOCK置換演算法
(1) 第一優先順序淘汰的是 最近沒有訪問且沒有修改 的頁面。
(2) 第二優先順序淘汰的是 最近沒有訪問但修改 的頁面。
(3) 第三優先順序淘汰的是 最近訪問但沒有修改 的頁面。
(4) 第四優先順序淘汰的是 最近訪問且修改 的頁面。
⑶ FIFO可能會發生Belady異常,堆棧演算法不會發生Belady異常,如LRU。證明為何不會異常。
LRU置換演算法不會出現Belady異常:
在先進先出演算法(FIFO)——選擇裝入最早的頁面置換的過程中,可以通過鏈表來表示各頁的裝入時間先後。FIFO的性能較差,因為較早調入的頁往往是經常被訪問的頁,這些頁在FIFO演算法下被反復調入和調出,並且有Belady現象。所謂Belady現象是指:採用FIFO演算法時,如果對—個進程未分配它所要求的全部頁面,有時就會出現分配的頁面數增多但缺頁率反而提高的異常現象。
⑷ 最佳置換演算法最後一個怎麼辦
最佳置換演算法(OPT)(理想置換演算法):從主存中移出永遠不再需要的頁面;如無這樣的頁面存在,則選擇最長時間不需要訪問的頁面。於所選擇的被淘汰頁面將是以後永不使用的,或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。 最佳置換演算法可以用來評價其他演算法。