Clock及改進(jìn)Clock置換算法實(shí)現(xiàn)

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告書 Clock及改進(jìn)Clock置換算法實(shí)現(xiàn)班 級 姓 名 學(xué) 號 指導(dǎo)老師 2014年3月12日 目 錄一 、課程設(shè)計(jì)目的 . 3 二、系統(tǒng)分析與設(shè)計(jì) . .3 三、算法流程圖： . .4四、函數(shù)模塊:.6 五、系統(tǒng)調(diào)試與結(jié)果： . .7 六、設(shè)計(jì)心得與體會(huì)： . .9 七 、源程序代碼: .15 一、課程設(shè)計(jì)目的操作系統(tǒng)課程設(shè)計(jì)是為了對學(xué)習(xí)的操作系統(tǒng)課程更深刻的理解和鞏固，對操作系統(tǒng)的整體進(jìn)行一個(gè)模擬。通過實(shí)踐加深對各個(gè)部分的管理功能的認(rèn)識，還能進(jìn)一步分析各個(gè)部分之間的聯(lián)系，最后達(dá)到對完整系統(tǒng)的理解。同時(shí)，可以提高運(yùn)用操作系統(tǒng)知識解決實(shí)際問題的能力；鍛煉實(shí)際的編程能力、創(chuàng)

2、新能力及團(tuán)隊(duì)組織、協(xié)作開發(fā)軟件的能力；還能提高調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料以及編寫軟件設(shè)計(jì)文檔的能力。課程設(shè)計(jì)是自己獨(dú)立完成一項(xiàng)任務(wù)的過程，編程過程中要充分調(diào)動(dòng)個(gè)人的積極性，提高自身解決實(shí)際問題的能力，發(fā)現(xiàn)自身的編程錯(cuò)誤習(xí)慣，提高編寫程序的質(zhì)量。同時(shí)，也為以后深入層次的學(xué)習(xí)及研究打基礎(chǔ)。編程中少不了難題，遇到難題時(shí)需要的是用程序員的思維方式去考慮問題解決問題，還需要很大的精力和耐心，對于我們來說都是磨練和提高。二、系統(tǒng)分析與設(shè)計(jì) 在采用請求分頁機(jī)制的操作系統(tǒng)中，當(dāng)運(yùn)行一個(gè)程序的時(shí)候，若要訪問的頁面不在內(nèi)存中而需要把它們調(diào)入內(nèi)存，但此時(shí)內(nèi)存已無空閑空間，為了保證該進(jìn)程能正常運(yùn)行，需選擇內(nèi)存中暫時(shí)

3、不用的頁面調(diào)出到磁盤交換區(qū)。選擇調(diào)出哪個(gè)頁面，由頁面算法決定。頁面置換算法的好壞，直接影響系統(tǒng)的性能，所以一個(gè)好的頁面置換算法，應(yīng)盡可能選擇調(diào)出較長時(shí)間內(nèi)不會(huì)再訪問的頁面，以保證較低的缺頁率。2.1 Clock頁面置換原理描述 Clock算法的思想：當(dāng)某一頁首次裝入內(nèi)存中時(shí)，則將該頁框的使用位設(shè)置為1；當(dāng)該頁隨后被訪問到時(shí)（在訪問產(chǎn)生缺頁中斷之后），它的使用位也會(huì)被設(shè)置為1。對于頁面置換算法，用于置換算法，用于置換的候選頁框集合（當(dāng)前進(jìn)程：局部范圍；整個(gè)內(nèi)存；全局范圍）被看做是一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)一頁被置換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一頁框。當(dāng)需要置換一頁時(shí)，操作

4、系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一頁框。每當(dāng)遇到一個(gè)使用位為1的頁框時(shí)，操作系統(tǒng)就將該位重新置為0；如果在這個(gè)過程開始時(shí)，緩沖區(qū)中所有頁框的使用位均為0時(shí)，則選擇遇到的第一個(gè)頁框置換；如果所有頁框的使用位均為1時(shí)，則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，置換該頁框中的頁。 2.2 改進(jìn)型 Clock頁面置換原理描述 改進(jìn)型的Clock算法的思想：在將一個(gè)頁面換出時(shí)，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時(shí)滿足這兩條件的頁面作為首先淘汰的頁。由訪問位A和修改位M可以組合成下面四種類型的頁面：1 類（A=

5、0，M=0）：表示該頁最近既未被訪問、又未被修改，是最佳淘汰頁。2 類（A=0，M=1）：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。3 類（A=1，M=0）：最近已被訪問，但未被修改，該頁有可能再被訪問。4 類（A=1，M=1）：最近已被訪問且被修改，該頁有可能再被訪問。 在內(nèi)存中的每個(gè)頁必定是這四類頁面之一，在進(jìn)行頁面置換時(shí)，其執(zhí)行過程可分成以下三步：（1）從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁面，將所遇到的第一個(gè)頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。 （2） 如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A

6、=0且M=1的第二類頁面，將所遇到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，將所有經(jīng)過的頁面的訪問位置0。 （3） 如果第二步也失敗，即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后，重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能夠找到被淘汰的頁。三、算法流程圖：Clock置換算法流程圖：改進(jìn)型置換算法流程圖：四、函數(shù)模塊主函數(shù)模塊函數(shù)名稱：int main()功能：顯示主菜單，調(diào)用函數(shù)檢測模塊函數(shù)名稱：bool inblock(int num) 、bool inblock2(int num)功能：檢測讀入的頁號是否存在內(nèi)存中、檢測頁號是否在內(nèi)存中并把訪問

7、位和修改位置1修改模塊函數(shù)名稱：bool change()、int whichpage()功能：判斷頁面是否已經(jīng)被修改、判斷內(nèi)存中第幾個(gè)需要被置換Clock模塊函數(shù)名稱：void CLOCK(int num)功能：實(shí)現(xiàn)Clock置換算法，完成頁面置換改進(jìn)型Clock模塊函數(shù)名稱：void LCOCK(int num)功能：實(shí)現(xiàn)改進(jìn)的ClockL置換算法，完成頁面置換五、系統(tǒng)調(diào)試與結(jié)果六、程序清單#include<iostream>#include<stdlib.h>#include<time.h>#define N 20 /虛擬內(nèi)存尺寸using names

8、pace std;int P; int const blockCount=3 ;/內(nèi)存中的物理塊數(shù)int count = 0;int blockblockCount;int const PageCount=15;/總的頁面數(shù)int PagePageCount;int stateblockCount;/clock置換算法中，內(nèi)存中的每個(gè)頁面號對應(yīng)的狀態(tài)int state2blockCount2;/ 二維數(shù)組，第一行第一列為訪問位，第一行的第二列為修改位double lost= 0.0;void generate_list(int *list,int e,int m,int t)int i,j=0

9、,q=P,r;srand(unsigned)time(NULL);while(j<e)for(i=j;i<j+m;i+)if(i=e)break;listi=(q+rand()%e)%N; /保證在虛擬內(nèi)存的頁號內(nèi)j=i;r=rand()%100;if(r<t)q=rand()%N;else q=(q+1)%N;/隨機(jī)生產(chǎn)是否被修改的情況，prop(0100),prop/100的概率為被修改void generate_modify(int *mo,int e,int prop)int i,t;for(i=0;i<e;i+)t=rand()%100;if(t>pro

10、p)moi=0;elsemoi=1;/檢測頁號是否在內(nèi)存中bool inblock(int num)for(int i=0; i<blockCount;i+)if(blocki = Pagenum)statei = 1;return true;return false;/判斷頁面是否已經(jīng)被修改bool change()if(rand()%2+1) = 1 )printf("該頁面被修改!n");return true;elsereturn false;/用于改進(jìn)型clock置換算法，檢測頁號是否在內(nèi)存中并把訪問位和修改位置1bool inblock2(int num)

11、for(int i=0;i<blockCount;i+)if(blocki = Pagenum)if(change()state2i0 = 1;state2i1 = 1;elsestate2i0 = 1;return true;return false;/用于改進(jìn)型clock置換算法，判斷內(nèi)存中第幾個(gè)需要被置換int whichpage()int j;for(j=0;j<blockCount;j+) if(state2j0 = 0&&state2j1 = 0)return j;for(j=0;j<blockCount;j+ ) if(state2j0 = 0&

12、amp;&state2j1 = 1)return j;state2j0 = 0 ;for(j=0;j<blockCount;j+ )state2j0 =0 ;return whichpage();/簡單Clock置換算法void CLOCK(int num)int j;if(inblock(num)printf("命中!n");lost+;for(int i=0;i<blockCount;i+) printf("物理塊%d#中內(nèi)容:%dn",i,block i);elseif(count = blockCount)/lost+;for

13、(j=0;j<blockCount; )if(statej = 0)break;elsestatej = 0;j+;j = j%3;blockj = Pagenum;statej = 1;for(int i=0;i<blockCount;i+) printf("物理塊%d#中內(nèi)容:%dn",i,blocki);elseblockcount = Pagenum;count+;for(int i=0;i<blockCount;i+) printf("物理塊%d#中內(nèi)容:%dn",i,blocki);/改進(jìn)型clock置換算法void LCL

14、OCK(int num)int j;if(inblock2(num)printf("命中!n"); lost+;for(int i=0;i<blockCount;i+) printf("物理塊%d#中內(nèi)容:%dn",i,blocki);elseif(count = blockCount) /lost+;j = whichpage();blockj = Pagenum;state2j0 = 1;for(int i=0;i<blockCount;i+) printf("物理塊%d#中內(nèi)容:%dn",i,blocki);else

15、blockcount = Pagenum;count+;for(int i=0;i<blockCount;i+) printf("物理塊%d#中內(nèi)容:%dn",i,blocki);int main() int aN;int moN; int A=10; int e,m,prop,t,j;printf("頁面走向?yàn)椋?quot;);generate_list(a, e,m,t);generate_modify(mo,e,prop); for(int i = 0;i<PageCount;i+) Pagei =rand()%9 + 1;printf(&quo

16、t;%d ",Pagei);char ch ;printf("n");printf("tt1 Clock置換算法n");printf("tt2 改進(jìn)型Clock置換算法n");printf("tt3 退出!nn");printf("請輸入算法序號:tn"); while(1) scanf("%c",&ch); switch(ch) case '1':lost=0;count=0;for(int m=0;m<blockCount;m+)s

17、tatem = 0;for(int j=0;j<blockCount;j+)blockj=0;for(int i=0;i<PageCount;i+) printf("讀入Page%dn",i); CLOCK(i); printf("頁面訪問次數(shù): %dn缺頁次數(shù): %0.lfn",PageCount,PageCount-lost); printf("缺頁率為:%0.001fn",(PageCount-lost)/PageCount); printf("n請輸入算法序號:t"); break; case

18、'2': lost = 0;count = 0;for(int m = 0; m < blockCount; m+) for(int n = 0; n < 2;n+)state2mn = 0;for(int j = 0; j < blockCount; j+) blockj = 0;for(int i = 0; i < PageCount; i+) printf("讀入Page%dn",i); LCLOCK(i); printf("頁面訪問次數(shù): %dn缺頁次數(shù): %0.lfn",PageCount,PageCount-lost);printf("缺頁率為:%0.001fn",(PageCount-lost)/PageCount); printf("n請輸入算法序號:t"); break;case '3':exit(0); return 0;七、實(shí)驗(yàn)心得 通過這兩周的課程設(shè)計(jì),讓我加深了對操作系統(tǒng)的認(rèn)識,了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn),特別是對虛擬存儲,頁面置換有了深入的了解,并能夠用高級語言進(jìn)行模擬演示。不僅提高對操作系統(tǒng)的了解，這次的課程設(shè)計(jì)也使自己的C語言編程能力加強(qiáng)了不少