頁(yè)面置換算法操作系統(tǒng)課程設(shè)計(jì)

1、<p>　　《操作系統(tǒng)課程設(shè)計(jì)報(bào)告 》</p><p>　　專 業(yè)： 計(jì)算機(jī) </p><p>　　班 級(jí)： 網(wǎng)絡(luò)工程班 </p><p>　　姓 名： </p><p>　　

2、指導(dǎo)教師： </p><p>　　學(xué) 號(hào)： </p><p>　　目 錄</p><p>　　1.課程設(shè)計(jì)目的……………………………………………………2</p><p>　　2.課程設(shè)計(jì)題目描述和要求………………………………………3&l

3、t;/p><p>　　3.課程設(shè)計(jì)內(nèi)容……………………………………………………3</p><p>　　3.1頁(yè)面置換原理描述………………………………………………3</p><p>　　3.2 模擬頁(yè)面置換算法的代碼……………………………………6</p><p>　　4.課程設(shè)計(jì)實(shí)驗(yàn)總結(jié)………………………………………………8</p>

4、<p>　　5.參考文獻(xiàn)…………………………………………………………9</p><p>　　Clock頁(yè)面置換算法</p><p><b>　　1.課程設(shè)計(jì)目的</b></p><p>　　本實(shí)驗(yàn)主要對(duì)操作系統(tǒng)中應(yīng)用的一些關(guān)鍵算法進(jìn)行模擬。學(xué)生通過設(shè)計(jì)與實(shí)現(xiàn)相關(guān)算法，能夠加強(qiáng)對(duì)相應(yīng)理論的理解，并對(duì)了解操作系統(tǒng)內(nèi)部的基本處理原理與過程也

5、有很多益處。</p><p>　　2.課程設(shè)計(jì)題目描述和要求</p><p>　　基本要求：描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實(shí)現(xiàn)。</p><p>　　1）初始化：輸入作業(yè)可占用的總頁(yè)框數(shù)，初始化置空。</p><p>　　2）輸入請(qǐng)求序列：輸入一個(gè)作業(yè)頁(yè)號(hào)訪問請(qǐng)求序列，依次占用相應(yīng)頁(yè)框，直至全部占用；<

6、;/p><p>　　3）Clock算法：當(dāng)頁(yè)框全部占用后，對(duì)于后續(xù)新的頁(yè)號(hào)訪問請(qǐng)求，執(zhí)行Clock算法，淘汰1個(gè)頁(yè)面后裝入新的頁(yè)號(hào)。</p><p>　　4）顯示當(dāng)前分配淘汰序列：顯示淘汰的頁(yè)號(hào)序列。</p><p><b>　　3.課程設(shè)計(jì)內(nèi)容</b></p><p>　　3.1頁(yè)面置換原理描述</p>&l

7、t;p>　　在采用請(qǐng)求分頁(yè)機(jī)制的操作系統(tǒng)中，當(dāng)運(yùn)行一個(gè)程序的時(shí)候，若要訪問的頁(yè)面不在內(nèi)存中而需要把它們調(diào)入內(nèi)存，但此時(shí)內(nèi)存已無(wú)空閑空間，為了保證該進(jìn)程能正常運(yùn)行，需選擇內(nèi)存中暫時(shí)不用的頁(yè)面調(diào)出到磁盤交換區(qū)。選擇調(diào)出哪個(gè)頁(yè)面，由頁(yè)面算法決定。頁(yè)面置換算法的好壞，直接影響系統(tǒng)的性能，所以一個(gè)好的頁(yè)面置換算法，應(yīng)盡可能選擇調(diào)出較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問的頁(yè)面，以保證較低的缺頁(yè)率。</p><p>　　改進(jìn)型的Clock

8、算法的思想：在將一個(gè)頁(yè)面換出時(shí)，如果該頁(yè)已被修改過，便須將它重新寫到磁盤上；但如果該頁(yè)未被修改過，則不必將它拷回磁盤。同時(shí)滿足這兩條件的頁(yè)面作為首先淘汰的頁(yè)。由訪問位A和修改位M可以組合成下面四種類型的頁(yè)面：</p><p>　　1 類（A=0，M=0）：表示該頁(yè)最近既未被訪問、又未被修改，是最佳淘汰頁(yè)。</p><p>　　2 類（A=0，M=1）：表示該頁(yè)最近未被訪問，但已被修改，并不

9、是很好的淘汰頁(yè)。</p><p>　　3 類（A=1，M=0）：最近已被訪問，但未被修改，該頁(yè)有可能再被訪問。</p><p>　　4 類（A=1，M=1）：最近已被訪問且被修改，該頁(yè)有可能再被訪問。</p><p>　　在內(nèi)存中的每個(gè)頁(yè)必定是這四類頁(yè)面之一，在進(jìn)行頁(yè)面置換時(shí)，可采用與簡(jiǎn)單Clock算法相類似的算法，其差別在于須同時(shí)檢查訪問位和修改位，以確定該頁(yè)是四

10、類頁(yè)面中的哪一種。此算法稱為改進(jìn)型Clock算法。其執(zhí)行過程可分成以下三步：</p><p>　?。?）從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問位A。</p><p>　?。?）如果第一步失敗，即查找一周后未遇到第一類頁(yè)面，則開始第二輪掃描，尋找A=0且M=1的第二類頁(yè)面，將所遇到的第一個(gè)這

11、類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有經(jīng)過的頁(yè)面的訪問位置0。</p><p>　?。?）如果第二步也失敗，即未找到第二類頁(yè)面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后，重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能夠找到被淘汰的頁(yè)。</p><p><b>　　3.2 流程圖實(shí)現(xiàn)</b></p><p>　　3.2

12、模擬頁(yè)面置換算法的代碼</p><p>　　定義頁(yè)面表的數(shù)據(jù)結(jié)構(gòu)，它包括頁(yè)號(hào)（info）,訪問位（A），修改標(biāo)志（M）和指針4個(gè)屬性。代碼如下：</p><p>　　template<typename T>class Node//結(jié)點(diǎn)類模板，不同數(shù)據(jù)類型，編譯時(shí)生成不同的類 </p><p><b>　　{ public:</b>

13、</p><p>　　T info; //定義三個(gè)變量</p><p>　　int A; //訪問頁(yè)變量，引用位的值</p><p>　　int M; //修改頁(yè)變量，引用位的值</p><p>　　Node<T> *link;//定義類的基地址 </p><p><b>　　};

14、</b></p><p>　　（2）通過界面接收的頁(yè)面數(shù)（K），在主程序中先對(duì)K個(gè)頁(yè)面通過調(diào)用方法Insertrear(T data)進(jìn)行初始化，代碼如下：</p><p><b>　　while(1)</b></p><p><b>　　{if(n<k)</b></p><p>

15、　　{cout<<"請(qǐng)輸入要訪問的頁(yè)面號(hào)："<<endl;</p><p><b>　　cin>>num;</b></p><p>　　cout<<endl;</p><p>　　www->Insertrear(num);</p><p><

16、b>　　n++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　初始化頁(yè)面之后會(huì)提示是否對(duì)內(nèi)存中存在的頁(yè)面進(jìn)行修改，選擇Y，就會(huì)調(diào)用方法change(),并對(duì)你選擇的頁(yè)面的修改標(biāo)志（M）進(jìn)行修改，把它改為1（說明該頁(yè)面已被修改過了）。選擇N，就

17、會(huì)提示你“請(qǐng)輸入訪問的頁(yè)面號(hào)”，當(dāng)你輸入一個(gè)頁(yè)面號(hào)：</p><p>　　a、通過調(diào)用方法find0(T data)判斷你輸入的頁(yè)面號(hào)是否跟內(nèi)存中存在的頁(yè)面號(hào)是否相同，如果相同，通過調(diào)用方法tihuan(Node<T>*p,T data)來(lái)進(jìn)行置換頁(yè)面。代碼如下：</p><p>　　find0(T data)</p><p>　　{Node<T&

18、gt; *tempb;</p><p>　　tempb=head->link;</p><p>　　while(tempb!=head)</p><p>　　{if(tempb->info==data)</p><p>　　return tempb;</p><p>　　tempb=tempb->li

19、nk;</p><p><b>　　}</b></p><p>　　return NULL;</p><p><b>　　}</b></p><p>　　b、如果不是相同的兩個(gè)頁(yè)面，通過調(diào)用find1(T data)來(lái)尋找內(nèi)存中是否存在訪問位為0，修改標(biāo)志為0的頁(yè)號(hào)，如果找到了，通過調(diào)用方法tihu

20、an(Node<T>*p,T data)來(lái)進(jìn)行置換頁(yè)面。如果沒有找到就調(diào)用find2(T data)來(lái)進(jìn)行第二次掃描，并把掃描過的頁(yè)面的訪問為改為1。如果在內(nèi)存中找到訪問為為0，修改標(biāo)志為1的頁(yè)號(hào)，通過調(diào)用方法tihuan(Node<T>*p,T data)來(lái)進(jìn)行置換頁(yè)面，否則，繼續(xù)循環(huán)find1(T data)的查找直到置換為止。代碼如下：</p><p><b>　　第一次掃

21、描：</b></p><p>　　find1(T data)</p><p><b>　　{</b></p><p>　　Node<T> *tempb;</p><p>　　tempb=head->link;</p><p>　　while(tempb!=head)&

22、lt;/p><p><b>　　{</b></p><p>　　if(tempb->A==0&&tempb->M==0)</p><p>　　return tempb;</p><p>　　tempb=tempb->link;</p><p><b>　　}

23、</b></p><p>　　return NULL;</p><p><b>　　} </b></p><p><b>　　第二次掃描：</b></p><p>　　find2(T data) </p><p><b>　　{</b><

24、;/p><p>　　Node<T> *tempb;</p><p>　　tempb=head->link;</p><p>　　while(tempb!=head)</p><p><b>　　{</b></p><p>　　if(tempb->A==0&&te

25、mpb->M==1)</p><p>　　return tempb;</p><p>　　tempb->A=0;</p><p>　　tempb=tempb->link;</p><p><b>　　}</b></p><p>　　return NULL;</p>

26、<p><b>　　}</b></p><p>　　找到內(nèi)存中存在訪問位為0，修改標(biāo)志為0的頁(yè)號(hào)，如下：</p><p>　　頁(yè)號(hào) 訪問位 修改標(biāo)志</p><p>　　2 1 0</p><p>　　3 1 1<

27、/p><p>　　1 1 0</p><p>　　找到內(nèi)存中存在訪問為0，修改標(biāo)志為1的頁(yè)號(hào)，如下：</p><p>　　頁(yè)號(hào) 訪問位 修改標(biāo)志</p><p>　　5 0 1</p><p>　　7

28、 1 1</p><p>　　14 1 1</p><p>　　請(qǐng)輸入要訪問的頁(yè)面號(hào)</p><p><b>　　12</b></p><p>　　找到內(nèi)存訪問位為0，修改位為1的頁(yè)號(hào)，修改后：</p><p>　　頁(yè)號(hào)

29、訪問位 修改標(biāo)志</p><p>　　12 1 0 </p><p>　　7 1 1 </p><p>　　14 1 1</p><p><b>　　四、實(shí)驗(yàn)總結(jié) </b></p&

30、gt;<p>　　通過這幾周的課程設(shè)計(jì),加深了對(duì)操作系統(tǒng)的認(rèn)識(shí),了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn),特別是對(duì)虛擬存儲(chǔ),頁(yè)面置換有了深入的了解,并能夠用高級(jí)語(yǔ)言進(jìn)行模擬演示。在這短短的幾周時(shí)間里，通過瀏覽、閱讀有關(guān)的資料，學(xué)到了很多東西，同時(shí)也發(fā)現(xiàn)僅僅書本的知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，需要把知識(shí)運(yùn)用到實(shí)踐中去，能力才能得到提高。 不僅提高對(duì)操作系統(tǒng)的了解，這次的課程設(shè)計(jì)也使自己的C編程能力加強(qiáng)了不少。一分耕耘，一分收獲，這次的課程

31、設(shè)計(jì)讓我受益匪淺。雖然自己所做的很少也不夠完善，但畢竟也是努力的結(jié)果。另外，使我體會(huì)最深的是：任何一門知識(shí)的掌握，僅靠學(xué)習(xí)理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，要與實(shí)際動(dòng)手操作相結(jié)合才能達(dá)到功效。</p><p><b>　　5參考文獻(xiàn)</b></p><p>　　[1] 譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì).第三版 清華大學(xué)出版社</p><p>　　[2] 嚴(yán)蔚敏。數(shù)據(jù)