實(shí)驗(yàn)四+頁面置換算法

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

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

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

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

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