實驗四+頁面置換算法

1、頁面置換算法模擬實驗【實驗目的】1 ）進一步掌握虛擬存儲器的工作原理。2）通過實驗理解和掌握 FIFO, LRU，OPT三種頁面置換算法。3）比較各種頁面置換算法的優(yōu)缺點?！緦嶒炓蟆?）認真閱讀和掌握預備知識。2）上機操作?！绢A備知識】在采用請求分頁機制的操作系統(tǒng)中，當運行一個進程的時侯， 若所要訪問的頁面不在內(nèi)存中而需要把它們調(diào)入內(nèi)存，但此時內(nèi)存已無空閑空間，為了保證該進程能正常運行，需選 擇內(nèi)存中暫時不用的一個頁面調(diào)出到磁盤交換區(qū)。選擇調(diào)出哪個頁面，由頁面置換算法決定。頁面置換算法的好壞， 直接影響著系統(tǒng)的性能。 一個好的頁面置換算法， 應盡可能選擇 調(diào)出較長時間內(nèi)不會再訪問的頁面， 以

2、保證較低的缺頁率。 常見的頁面置換算法有 OPT （最 佳置換算法），F(xiàn)IFO （先進先出算法）及 LRU （最近最久未使用算法）。一、OPT算法1. 原理簡述1） 在分配內(nèi)存頁面數(shù)（B）小于進程頁面數(shù)（P）時，最先用到的 B個頁面依次放入內(nèi) 存；2）這時若需要處理新的頁面，而當前分配的內(nèi)存頁面全部不空閑時，選擇換出以后永遠不再使用的頁。如沒有這樣的頁面存在， 則應選擇下次訪問距離現(xiàn)在最久的頁換出，以空出內(nèi)存來放置新調(diào)入的頁面；3） 以后如果有新頁面需要調(diào)入，按“2）”之規(guī)則進行。該算法能保證有最低的缺頁率，所以稱為最佳置換算法。但是該算法僅僅是一種理想狀 況下的算法，因為在進程實際運行過程中

3、， 將來會執(zhí)行到哪個頁是不可預知的，所以無法選擇該置換哪個頁出去。 因此，本算法在實際中無法使用， 只能作為一種標準來衡量其他算法 的性能。2. 圖表描述假設某個進程在交換區(qū)被分為 5個頁面（P=5 ），分別以1，2，3，4，5表示。在該 進程運行過程中，處理機調(diào)用它們的順序即頁地址流為：2，3，2，1，5，2，4，5，3，2，5，2而系統(tǒng)分配給該進程的內(nèi)存空間只有3 （ B= 3 ）個頁面，那么在使用 OPT算法時，這3個頁面的內(nèi)存使用情況應該是：本例共缺頁6次，缺頁率為6/12()()5、FIFO算法1. 原理簡述1） 在分配內(nèi)存頁面數(shù)（B）小于進程頁面數(shù)（P）時，最先用到的 B個頁面依次

4、放入內(nèi) 存；2） 這時若需要處理新的頁面，則從當前內(nèi)存中的B個頁面中選擇調(diào)出最先進入的那個頁（所以稱為FIFO）,然后放入新頁面；3） 以后如果有新頁面需要調(diào)入，按“2）”之規(guī)則進行。該算法將所使用的內(nèi)存頁面構(gòu)成一個循環(huán)隊列，每次置換時將隊列中的隊首換出， 隊首指針后移一位即可， 算法容易實現(xiàn)。但是最先進入內(nèi)存的頁未必將來就不再用到，甚至可能很快就會用到，所以不能保證有較低的缺頁率，算法性能較差。2. 圖表描述為了便于比較學習，例子和前面的一樣。在使用FIFO算法時，這3個頁面的內(nèi)存使用情況應該是:52335542(f)標記本例共缺頁9次，缺頁率為9/12三、LRU算法1. 原理簡述1）在分配

5、內(nèi)存頁面數(shù)（B）小于進程頁面數(shù)（P）時，最先用到的 B個頁面依次放入內(nèi) 存；2）這時若需要處理新的頁面，而當前分配的內(nèi)存頁面全部不空閑時，選擇調(diào)出其中最長時間沒有用到的那個頁面，用空出的內(nèi)存來放置新調(diào)入的頁面，所以稱為LRU （最近最久未使用）算法；3） 以后如果有新頁面需要調(diào)入，按“2）”之規(guī)則進行。該算法根據(jù)局部性原理， 認為最近一段時間內(nèi)， 最長時間沒有用到的那個頁將來用到的可能性也很小，所以替換這樣的頁出去，也能保證比較低的缺頁率，其性能接近OPT算法。 但是需要有專門的存儲單元來記錄每個頁面有多久未被使用，并且要隨時更新該記錄， 所以算法的開銷比較大。2. 圖表描述：為了便于比較學習，例子和前面的一樣。情況應該是：在使用FIFO算法時，這3個頁面的內(nèi)存使用5352本例共缺頁7次，缺頁率為7/12 ?！緦嶒瀮?nèi)容】1）編譯opt.c，實現(xiàn)OPT置換算法。（源程序已給） 多次執(zhí)行，查看OPT置換算法的詳細置換過程及結(jié)果。2）編輯lru.c，實現(xiàn)LRU置換算法。（源程序已給）多次執(zhí)行exam16b ，查看LRU置換算法的詳細置換過程及結(jié)果。3） 代碼參照前兩個算法自行編寫，實現(xiàn)FIFO置換算法。（自行設計，需在報告中給出）編譯并多次執(zhí)行“ fifo.c ”，查看FIFO置換算法的詳細