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

可編輯版/操作系統(tǒng)課程設(shè)計(jì)報(bào)告書(shū)Clock及改進(jìn)Clock置換算法實(shí)現(xiàn)班級(jí)姓名學(xué)號(hào)指導(dǎo)老師20XX3月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ì)是為了對(duì)學(xué)習(xí)的操作系統(tǒng)課程更深刻的理解和鞏固,對(duì)操作系統(tǒng)的整體進(jìn)行一個(gè)模擬。通過(guò)實(shí)踐加深對(duì)各個(gè)部分的管理功能的認(rèn)識(shí),還能進(jìn)一步分析各個(gè)部分之間的聯(lián)系,最后達(dá)到對(duì)完整系統(tǒng)的理解。同時(shí),可以提高運(yùn)用操作系統(tǒng)知識(shí)解決實(shí)際問(wèn)題的能力；鍛煉實(shí)際的編程能力、創(chuàng)新能力及團(tuán)隊(duì)組織、協(xié)作開(kāi)發(fā)軟件的能力；還能提高調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料以及編寫(xiě)軟件設(shè)計(jì)文檔的能力。課程設(shè)計(jì)是自己獨(dú)立完成一項(xiàng)任務(wù)的過(guò)程,編程過(guò)程中要充分調(diào)動(dòng)個(gè)人的積極性,提高自身解決實(shí)際問(wèn)題的能力,發(fā)現(xiàn)自身的編程錯(cuò)誤習(xí)慣,提高編寫(xiě)程序的質(zhì)量。同時(shí),也為以后深入層次的學(xué)習(xí)及研究打基礎(chǔ)。編程中少不了難題,遇到難題時(shí)需要的是用程序員的思維方式去考慮問(wèn)題解決問(wèn)題,還需要很大的精力和耐心,對(duì)于我們來(lái)說(shuō)都是磨練和提高。二、系統(tǒng)分析與設(shè)計(jì)在采用請(qǐng)求分頁(yè)機(jī)制的操作系統(tǒng)中,當(dāng)運(yùn)行一個(gè)程序的時(shí)候,若要訪問(wèn)的頁(yè)面不在內(nèi)存中而需要把它們調(diào)入內(nèi)存,但此時(shí)內(nèi)存已無(wú)空閑空間,為了保證該進(jìn)程能正常運(yùn)行,需選擇內(nèi)存中暫時(shí)不用的頁(yè)面調(diào)出到磁盤(pán)交換區(qū)。選擇調(diào)出哪個(gè)頁(yè)面,由頁(yè)面算法決定。頁(yè)面置換算法的好壞,直接影響系統(tǒng)的性能,所以一個(gè)好的頁(yè)面置換算法,應(yīng)盡可能選擇調(diào)出較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面,以保證較低的缺頁(yè)率。2.1Clock頁(yè)面置換原理描述Clock算法的思想：當(dāng)某一頁(yè)首次裝入內(nèi)存中時(shí),則將該頁(yè)框的使用位設(shè)置為1；當(dāng)該頁(yè)隨后被訪問(wèn)到時(shí)〔在訪問(wèn)產(chǎn)生缺頁(yè)中斷之后,它的使用位也會(huì)被設(shè)置為1。對(duì)于頁(yè)面置換算法,用于置換算法,用于置換的候選頁(yè)框集合〔當(dāng)前進(jìn)程：局部范圍；整個(gè)內(nèi)存；全局范圍被看做是一個(gè)循環(huán)緩沖區(qū),并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)一頁(yè)被置換時(shí),該指針被設(shè)置成指向緩沖區(qū)中的下一頁(yè)框。當(dāng)需要置換一頁(yè)時(shí),操作系統(tǒng)掃描緩沖區(qū),以查找使用位被置為0的一頁(yè)框。每當(dāng)遇到一個(gè)使用位為1的頁(yè)框時(shí),操作系統(tǒng)就將該位重新置為0；如果在這個(gè)過(guò)程開(kāi)始時(shí),緩沖區(qū)中所有頁(yè)框的使用位均為0時(shí),則選擇遇到的第一個(gè)頁(yè)框置換；如果所有頁(yè)框的使用位均為1時(shí),則指針在緩沖區(qū)中完整地循環(huán)一周,把所有使用位都置為0,并且停留在最初的位置上,置換該頁(yè)框中的頁(yè)。2.2改進(jìn)型Clock頁(yè)面置換原理描述改進(jìn)型的Clock算法的思想：在將一個(gè)頁(yè)面換出時(shí),如果該頁(yè)已被修改過(guò),便須將它重新寫(xiě)到磁盤(pán)上；但如果該頁(yè)未被修改過(guò),則不必將它拷回磁盤(pán)。同時(shí)滿足這兩條件的頁(yè)面作為首先淘汰的頁(yè)。由訪問(wèn)位A和修改位M可以組合成下面四種類型的頁(yè)面：1類〔A=0,M=0：表示該頁(yè)最近既未被訪問(wèn)、又未被修改,是最佳淘汰頁(yè)。2類〔A=0,M=1：表示該頁(yè)最近未被訪問(wèn),但已被修改,并不是很好的淘汰頁(yè)。3類〔A=1,M=0：最近已被訪問(wèn),但未被修改,該頁(yè)有可能再被訪問(wèn)。4類〔A=1,M=1：最近已被訪問(wèn)且被修改,該頁(yè)有可能再被訪問(wèn)。在內(nèi)存中的每個(gè)頁(yè)必定是這四類頁(yè)面之一,在進(jìn)行頁(yè)面置換時(shí),其執(zhí)行過(guò)程可分成以下三步：〔1從指針?biāo)甘镜漠?dāng)前位置開(kāi)始,掃描循環(huán)隊(duì)列,尋找A=0且M=0的第一類頁(yè)面,將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。如果第一步失敗,即查找一周后未遇到第一類頁(yè)面,則開(kāi)始第二輪掃描,尋找A=0且M=1的第二類頁(yè)面,將所遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間,將所有經(jīng)過(guò)的頁(yè)面的訪問(wèn)位置0。如果第二步也失敗,即未找到第二類頁(yè)面,則將指針?lè)祷氐介_(kāi)始的位置,并將所有的訪問(wèn)位復(fù)0。然后,重復(fù)第一步,如果仍失敗,必要時(shí)再重復(fù)第二步,此時(shí)就一定能夠找到被淘汰的頁(yè)。三、算法流程圖：Clock置換算法流程圖：改進(jìn)型置換算法流程圖：四、函數(shù)模塊主函數(shù)模塊函數(shù)名稱：intmain<>功能：顯示主菜單,調(diào)用函數(shù)檢測(cè)模塊函數(shù)名稱：boolinblock<intnum>、boolinblock2<intnum>功能：檢測(cè)讀入的頁(yè)號(hào)是否存在內(nèi)存中、檢測(cè)頁(yè)號(hào)是否在內(nèi)存中并把訪問(wèn)位和修改位置1修改模塊函數(shù)名稱：boolchange<>、intwhichpage<>功能：判斷頁(yè)面是否已經(jīng)被修改、判斷內(nèi)存中第幾個(gè)需要被置換Clock模塊函數(shù)名稱：voidCLOCK<intnum>功能：實(shí)現(xiàn)Clock置換算法,完成頁(yè)面置換改進(jìn)型Clock模塊函數(shù)名稱：voidLCOCK<intnum>功能：實(shí)現(xiàn)改進(jìn)的ClockL置換算法,完成頁(yè)面置換五、系統(tǒng)調(diào)試與結(jié)果六、程序清單#include<iostream>#include<stdlib.h>#include<time.h>#defineN20//虛擬內(nèi)存尺寸usingnamespacestd;intP;intconstblockCount=3;//內(nèi)存中的物理塊數(shù)intcount=0;intblock[blockCount];intconstPageCount=15;//總的頁(yè)面數(shù)intPage[PageCount];intstate[blockCount];//clock置換算法中,內(nèi)存中的每個(gè)頁(yè)面號(hào)對(duì)應(yīng)的狀態(tài)intstate2[blockCount][2];//二維數(shù)組,第一行第一列為訪問(wèn)位,第一行的第二列為修改位doublelost=0.0;voidgenerate_list<int*list,inte,intm,intt>{ inti,j=0,q=P,r; srand<<unsigned>time<NULL>>; while<j<e> { for<i=j;i<j+m;i++> { if<i==e> break; list[i]=<q+rand<>%e>%N;//保證在虛擬內(nèi)存的頁(yè)號(hào)內(nèi) } j=i; r=rand<>%100; if<r<t> q=rand<>%N; else q=<q+1>%N; }}//隨機(jī)生產(chǎn)是否被修改的情況,prop<0……100>,prop/100的概率為被修改voidgenerate_modify<int*mo,inte,intprop>{ inti,t; for<i=0;i<e;i++> { t=rand<>%100; if<t>prop> mo[i]=0; else mo[i]=1; }}//檢測(cè)頁(yè)號(hào)是否在內(nèi)存中boolinblock<intnum>{ for<inti=0;i<blockCount;i++> { if<block[i]==Page[num]> { state[i]=1; returntrue; } } returnfalse;}//判斷頁(yè)面是否已經(jīng)被修改boolchange<>{ if<<rand<>%2+1>==1> { printf<"該頁(yè)面被修改!\n">; returntrue; } else returnfalse;}//用于改進(jìn)型clock置換算法,檢測(cè)頁(yè)號(hào)是否在內(nèi)存中并把訪問(wèn)位和修改位置1boolinblock2<intnum>{ for<inti=0;i<blockCount;i++>{ if<block[i]==Page[num]>{ if<change<>>{ state2[i][0]=1; state2[i][1]=1; } else{ state2[i][0]=1; } returntrue; } } returnfalse;}//用于改進(jìn)型clock置換算法,判斷內(nèi)存中第幾個(gè)需要被置換intwhichpage<>{ intj; for<j=0;j<blockCount;j++> {if<state2[j][0]==0&&state2[j][1]==0> { returnj; } } for<j=0;j<blockCount;j++> {if<state2[j][0]==0&&state2[j][1]==1> { returnj; } state2[j][0]=0; } for<j=0;j<blockCount;j++> { state2[j][0]=0; } returnwhichpage<>;}//簡(jiǎn)單Clock置換算法voidCLOCK<intnum>{ intj; if<inblock<num>> { printf<"命中!\n">; lost++; for<inti=0;i<blockCount;i++>printf<"物理塊%d#中內(nèi)容:%d\n",i,block[i]>; } else if<count==blockCount> { //lost++; for<j=0;j<blockCount;> { if<state[j]==0> { break; } else{ state[j]=0; } j++; j=j%3; } block[j]=Page[num]; state[j]=1; for<inti=0;i<blockCount;i++>printf<"物理塊%d#中內(nèi)容:%d\n",i,block[i]>; } else{ block[count]=Page[num]; count++; for<inti=0;i<blockCount;i++>printf<"物理塊%d#中內(nèi)容:%d\n",i,block[i]>; }}//改進(jìn)型clock置換算法voidLCLOCK<intnum>{ intj; if<inblock2<num>> { printf<"命中!\n">;lost++; for<inti=0;i<blockCount;i++>printf<"物理塊%d#中內(nèi)容:%d\n",i,block[i]>; } else if<count==blockCount> { //lost++; j=whichpage<>; block[j]=Page[num]; state2[j][0]=1; for<inti=0;i<blockCount;i++>printf<"物理塊%d#中內(nèi)容:%d\n",i,block[i]>; } else{ block[count]=Page[num]; count++; for<inti=0;i<blockCount;i++>printf<"物理塊%d#中內(nèi)容:%d\n",i,block[i]>; }}intmain<>{inta[N]; intmo[N];intA=10;inte,m,prop,t,j; printf<"頁(yè)面走向?yàn)椋?>; generate_list<a,e,m,t>; generate_modify<mo,e,prop>;for<inti=0;i<PageCount;i++> { Page[i]=rand<>%9+1; printf<"%d",Page[i]>; } charch; printf<"\n">; printf<"\t\t1Clock置換算法\n">; printf<"\t\t2改進(jìn)型Clock置換算法\n">; printf<"\t\t3退出!\n\n">; printf<"請(qǐng)輸入算法序號(hào):\t\n">;while<1>{ scanf<"%c",&ch>; switch<ch>{case'1':{ lost=0; count=0; for<intm=0;m<blockCount;m++> { state[m]=0; } for<intj=0;j<blockCount;j++> { block[j]=0; } for<inti=0;i<PageCount;i++> {printf<"讀入Page[%d]\n",i>;CLOCK<i>; } printf<"頁(yè)面訪問(wèn)次數(shù):%d\n缺頁(yè)次數(shù):%0.lf\n",PageCount,PageCount-lost>; printf<"缺頁(yè)率為:%0.001f\n",<PageCount-lost>/PageCount>;printf<"\n請(qǐng)輸入算法序號(hào):\t">;}break;case'2':{lost=0; count=0; for<intm=0;m<blockCount;m++> {for<intn=0;n<2;n++> state2[m][n]=0; } for<intj=0;j<blockCount;j++> {block[j]=0; } for<inti=0;i<PageCount;i++> {printf<"讀入Page[%d]\n",i>;