操作系統(tǒng)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告模板

操作系統(tǒng)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告書題目：頁(yè)面置換算法之先進(jìn)先出題目編號(hào)：18院系：信息科學(xué)與技術(shù)學(xué)院班級(jí)：12級(jí)1班小組成員：組長(zhǎng)：張海洋學(xué)號(hào)：12051004組員：李奔學(xué)號(hào)：120510052014-12-31

目錄一、課程設(shè)計(jì)任務(wù)劃分 1二、基本原理 2（一）頁(yè)面置換算法定義（二）所使用的算法

（三）設(shè)計(jì)思想三、基本思路 3（一）流程圖（二）變量（三）所用函數(shù)四、調(diào)試及實(shí)驗(yàn)結(jié)果 4五、個(gè)人體會(huì) 5PAGEPAGE1一、課程設(shè)計(jì)任務(wù)劃分成員具體分工張海洋設(shè)計(jì)項(xiàng)目流程程序合并實(shí)驗(yàn)報(bào)告書書寫李奔程序調(diào)試網(wǎng)上搜索程序資料心得體會(huì)二、基本原理（題目所涉及課程內(nèi)容，用到了那種算法，該算法的基本原理是什么？500字以上，可加頁(yè)，下同）（一）頁(yè)面置換算法定義在地址映射過程中，若在頁(yè)面中發(fā)現(xiàn)所要訪問的頁(yè)面不再內(nèi)存中，則產(chǎn)生缺頁(yè)中斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)

存，以便為即將調(diào)入的頁(yè)面讓出空間。而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法。

（二）所使用的算法

1)最佳置換算法(OPT)：將以后永不使用的或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問的頁(yè)面換出。2)先進(jìn)先出算法(FIFO)：淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。3)最近最久未使用算法(LRU)：淘汰最近最久未被使用的頁(yè)面。（三）設(shè)計(jì)思想選擇置換算法，先輸入所有頁(yè)面號(hào)，為系統(tǒng)分配物理塊，依次進(jìn)行置換：OPT基本思想：是用一維數(shù)組page[pSIZE]存儲(chǔ)頁(yè)面號(hào)序列，memery[mSIZE]是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組next[mSIZE]記錄物理塊中對(duì)應(yīng)頁(yè)面的最后訪問時(shí)間。每當(dāng)發(fā)生缺頁(yè)時(shí)，就從物理塊中找出最后訪問時(shí)間最大的頁(yè)面，調(diào)出該頁(yè)，換入所缺的頁(yè)面。FIFO基本思想：是用隊(duì)列存儲(chǔ)內(nèi)存中的頁(yè)面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁(yè)時(shí)，就從隊(duì)頭刪除一頁(yè)，而從隊(duì)尾加入缺頁(yè)?；蛘呓柚o助數(shù)組time[mSIZE]記錄物理塊中對(duì)應(yīng)頁(yè)面的進(jìn)入時(shí)間，每次需要置換時(shí)換出進(jìn)入時(shí)間最小的頁(yè)面。LRU基本思想：是用一維數(shù)組page[pSIZE]存儲(chǔ)頁(yè)面號(hào)序列，memery[mSIZE]是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組flag[10]標(biāo)記頁(yè)面的訪問時(shí)間。每當(dāng)使用頁(yè)面時(shí)，刷新訪問時(shí)間。發(fā)生缺頁(yè)時(shí)，就從物理塊中頁(yè)面標(biāo)記最小的一頁(yè)，調(diào)出該頁(yè)，換入所缺的頁(yè)面。三、基本思路（1）流程圖將頁(yè)號(hào)放入物理塊中，編號(hào)加1將頁(yè)號(hào)放入物理塊中，編號(hào)加1引用串編號(hào)大于物理塊數(shù)?載入頁(yè)號(hào)序列，從第0個(gè)得到頁(yè)號(hào)開始頁(yè)號(hào)在物理塊中?根據(jù)選擇的置換算法完成置換頁(yè)號(hào)序列載完?結(jié)束是否是是是是變量/*全局變量*/intmSIZE;/*物理塊數(shù)*/intpSIZE;/*頁(yè)面號(hào)引用串個(gè)數(shù)*/staticintmemery[10]={0};/*物理塊中的頁(yè)號(hào)*/staticintpage[100]={0};/*頁(yè)面號(hào)引用串*/staticinttemp[100][10]={0};/*輔助數(shù)組*/inttime[10]={0};/*記錄進(jìn)入物理塊的時(shí)間*/intnext[10]={0};/*記錄下一次訪問時(shí)間*/intmax=0;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/所用函數(shù)/*置換算法函數(shù)*/voidFIFO();/*先進(jìn)先出頁(yè)面置換算法*/函數(shù)原型：voidFIFO(){intmemery[10]={0};inttime[10]={0};/*記錄進(jìn)入物理塊的時(shí)間*/inti,j,k,m;intmax=0;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/ /*前mSIZE個(gè)數(shù)直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理塊中*/{count++; /*計(jì)算換出頁(yè)*/max=time[0]<time[1]?0:1; for(m=2;m<mSIZE;m++) if(time[m]<time[max]) max=m;memery[max]=page[i];time[max]=i;/*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}voidLRU();/*最近最久未使用置換算法*/函數(shù)原型：voidLRU(){intmemery[10]={0};intflag[10]={0};/*記錄頁(yè)面的訪問時(shí)間*/inti,j,k,m;intmax=0;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/ /*前mSIZE個(gè)數(shù)直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;else flag[j]=i;/*刷新該頁(yè)的訪問時(shí)間*/}if(k==mSIZE)/*如果不在物理塊中*/{count++; /*計(jì)算換出頁(yè)*/max=flag[0]<flag[1]?0:1; for(m=2;m<mSIZE;m++) if(flag[m]<flag[max]) max=m;memery[max]=page[i];flag[max]=i;/*記錄該頁(yè)的訪問時(shí)間*/for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}voidOPT();/*最佳置換算法*/函數(shù)原型：voidOPT(){intmemery[10]={0};intnext[10]={0};/*記錄下一次訪問時(shí)間*/inti,j,k,l,m;intmax;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/ /*前mSIZE個(gè)數(shù)直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理塊中*/{ count++; /*得到物理快中各頁(yè)下一次訪問時(shí)間*/ for(m=0;m<mSIZE;m++) { for(l=i+1;l<pSIZE;l++) if(memery[m]==page[l]) break; next[m]=l; } /*計(jì)算換出頁(yè)*/ max=next[0]>=next[1]?0:1; for(m=2;m<mSIZE;m++) if(next[m]>next[max]) max=m; /*下一次訪問時(shí)間都為pSIZE,則置換物理塊中第一個(gè)*/ memery[max]=page[i]; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}2./*輔助函數(shù)*/voiddesignBy();/*顯示設(shè)計(jì)者信息*/函數(shù)原型：voiddesignBy(){ printf("┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃頁(yè)面置換算法┃\n"); printf("┃班級(jí)：┃\n"); printf("┃姓名：同學(xué)┃\n"); printf("┣━━━━━━━━━━━━━━━━━━━━┫\n");}voiddownload();/*載入數(shù)據(jù)*/函數(shù)原型：voiddownload(){ inti; system("color0D"); printf("╔════════════╗\n"); printf("║正在載入數(shù)據(jù)，請(qǐng)稍候!!!║\n"); printf("╚════════════╝\n"); printf("Loading...\n"); printf("O"); for(i=0;i<51;i++) printf("\b"); for(i=0;i<50;i++) { mDelay((pSIZE+mSIZE)/2); printf(">"); } printf("\nFinish.\n載入成功，按任意鍵進(jìn)入置換算法選擇界面：>>>"); getchar();}voidmDelay(unsignedintDelay);/*設(shè)置延遲*/函數(shù)原型：voidmDelay(unsignedintDelay){unsignedinti;for(;Delay>0;Delay--) { for(i=0;i<124;i++) { printf("\b"); } }voidcompute();/*計(jì)算過程延遲*/函數(shù)原型：voidcompute(){ inti; printf("正在進(jìn)行相關(guān)計(jì)算，請(qǐng)稍候"); for(i=1;i<20;i++) { mDelay(15); if(i%4==0) printf("\b\b\b\b\b\b\b\b\b\b\b\b"); else printf("Θ"); } for(i=0;i++<30;printf("\b")); for(i=0;i++<30;printf("")); for(i=0;i++<30;printf("\b"));}3./*主函數(shù)*/voidmain()四、調(diào)試及實(shí)驗(yàn)結(jié)果第一組數(shù)據(jù)：1.開始運(yùn)行2.按任意鍵進(jìn)行初始化：3.載入數(shù)據(jù)：4.進(jìn)入置換算法選擇界面：5.運(yùn)算中延遲操作：6.三種算法運(yùn)行結(jié)果7.退出算法第二組數(shù)據(jù)：1.開始運(yùn)行2．按任意鍵進(jìn)行初始化：3.載入數(shù)據(jù)：4.進(jìn)入置換算法選擇界面：5.運(yùn)算中延遲操作：6.三種算法運(yùn)行結(jié)果