Linux環(huán)境下幾種內(nèi)存調(diào)度算法模擬.doc

1、 課程設(shè)計(jì)（大作業(yè)）報(bào)告課程名稱(chēng)：操作系統(tǒng)課程設(shè)計(jì) 設(shè)計(jì)題目：linux環(huán)境下幾種內(nèi)存調(diào)度算法模擬 院 系： 班 級(jí)： 設(shè) 計(jì) 者： 學(xué) 號(hào)： 指導(dǎo)教師： 設(shè)計(jì)時(shí)間： 課程設(shè)計(jì)（大作業(yè)）任務(wù)書(shū)姓 名： 院（系）： 專(zhuān) 業(yè)： 學(xué) 號(hào)： 任務(wù)起止日期： 課程設(shè)計(jì)題目： linux環(huán)境下幾種內(nèi)存調(diào)度算法模擬課程設(shè)計(jì)要求及任務(wù)描述：（1）選擇其中兩種算法的原理進(jìn)行分析 fifo內(nèi)存調(diào)度算法的原理 （其他任選一個(gè)算法）內(nèi)存調(diào)度算法的原理（2）設(shè)計(jì)兩種算法的流程圖 設(shè)計(jì)fifo算法的流程圖。 其他任選一個(gè)算法設(shè)計(jì)流程圖。（3）使用vi編寫(xiě)實(shí)現(xiàn)兩種算法的程序 fifo內(nèi)存調(diào)度算法的代碼。 （其他任選一個(gè)算法

2、）內(nèi)存調(diào)度算法的代碼。（4）結(jié)果分析 分析設(shè)計(jì)結(jié)果是否達(dá)到預(yù)期目標(biāo)。 針對(duì)同一訪(fǎng)問(wèn)序列比較兩種算法的缺頁(yè)率。工作計(jì)劃及安排：（1）12月28日上午，課程設(shè)計(jì)相關(guān)事宜的安排，并選擇其中兩種算法的原理進(jìn)行分析（其中包括fifo內(nèi)存調(diào)度算法）。（2）12月28日下午，針對(duì)兩種算法進(jìn)行流程圖的繪制。（3）12月29日，提交流程圖并開(kāi)始初步編寫(xiě)代碼。（4）12月30日12月31日，代碼的調(diào)試并完成該課程設(shè)計(jì)的答辯。（5）1月1日1月2日，完成課程設(shè)計(jì)報(bào)告的書(shū)寫(xiě)并提交報(bào)告。指導(dǎo)教師簽字 年 月 日 課程設(shè)計(jì)（大作業(yè)）成績(jī)學(xué)號(hào)： 姓名： 指導(dǎo)教師： 課程設(shè)計(jì)題目：linux環(huán)境下幾種內(nèi)存調(diào)度算法模擬完成情況

3、總結(jié)：（1）就系統(tǒng)功能而言，基本實(shí)現(xiàn)了fifo算法和lru算法相應(yīng)的功能。（能夠計(jì)算置換次數(shù)，缺頁(yè)次數(shù)，缺頁(yè)率）（2）對(duì)于fifo和opt兩種內(nèi)存調(diào)度算法的原理和實(shí)現(xiàn)方式有了更好的了解，還學(xué)到了一個(gè)新的術(shù)語(yǔ)（命中率）=1-缺頁(yè)率。（雖然自己的算法中沒(méi)有直接涉及）（3）對(duì)#include <stdlib.h>的用法有了進(jìn)一步了解，它是c+中標(biāo)準(zhǔn)庫(kù)函數(shù)的定義，在置換算法中涉及的是size（），exit()函數(shù)等。（4）static int memery10=0定義中，要用到static，因?yàn)槌跏蓟瘯r(shí)值為0。（5）該次課程設(shè)計(jì)中,代碼的編寫(xiě)部分是參考了他人的程序，所以總體而言對(duì)代碼的編寫(xiě)

4、還有待進(jìn)一步提高。（6）對(duì)代碼中的細(xì)節(jié)理解有待進(jìn)一步加強(qiáng)，例如：/b、/t等。（7）針對(duì)不同的算法，它對(duì)物理塊數(shù)的大小都有限制，也就是能夠在輸入msize=3，執(zhí)行完成運(yùn)算后，在不退出運(yùn)行界面的同時(shí)，能夠繼續(xù)完成msize=4等的運(yùn)算。剛開(kāi)始時(shí)，程序無(wú)法進(jìn)行這樣的操作，通過(guò)對(duì)【printf("-請(qǐng)輸入物理塊的個(gè)數(shù)(m<=10)：");scanf("%d",&msize);】語(yǔ)句的調(diào)整，它完成了相應(yīng)的相應(yīng)的功能。指導(dǎo)教師評(píng)語(yǔ)：成績(jī)：填表時(shí)間：指導(dǎo)教師簽名：課程設(shè)計(jì)（大作業(yè)）報(bào)告一、 題目分析（1）選擇兩種置換算法的原理進(jìn)行分析（其中必須包括f

5、ifo內(nèi)存調(diào)度算法）。（2）根據(jù)課程設(shè)計(jì)的要求，其整個(gè)程序的功能如下：（主界面的設(shè)計(jì)包括）先輸入頁(yè)面號(hào)的總數(shù)；輸入所有頁(yè)面號(hào)；選擇置換算法；為系統(tǒng)分配物理塊；算法的執(zhí)行，依次進(jìn)行置換：（3）兩種算法的基本思想fifo算法：是用隊(duì)列存儲(chǔ)內(nèi)存中的頁(yè)面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁(yè)時(shí)，就從隊(duì)頭刪除一頁(yè)，而從隊(duì)尾加入缺頁(yè)?；蛘呓柚o助數(shù)組timemsize記錄物理塊中對(duì)應(yīng)頁(yè)面的進(jìn)入時(shí)間，每次需要置換時(shí)換出進(jìn)入時(shí)間最小的頁(yè)面。lru算法：是用一維數(shù)組pagepsize存儲(chǔ)頁(yè)面號(hào)序列，memerymsize是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組flag10標(biāo)記頁(yè)面的訪(fǎng)問(wèn)時(shí)間。每當(dāng)使用頁(yè)

6、面 時(shí)，刷新訪(fǎng)問(wèn)時(shí)間。發(fā)生缺頁(yè)時(shí)，就從物理塊中頁(yè)面標(biāo)記最小的一頁(yè)，調(diào)出該頁(yè)，換入所缺的頁(yè)面。二、 程序設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)int msize; /*定義物理塊數(shù)*/int psize; /*定義頁(yè)面總數(shù)*/static int memery10=0; /*初始化物理塊中的頁(yè)號(hào)*/static int page100=0; /*初始化頁(yè)面序列*/static int temp10010=0; /*輔助數(shù)組*/timemsize /*記錄物理塊中對(duì)應(yīng)頁(yè)面的進(jìn)入時(shí)間*/flag msize /*標(biāo)記頁(yè)面的訪(fǎng)問(wèn)時(shí)間*/int max=0; /*記錄換出頁(yè)*/int count=0; /*記錄置換次數(shù)*

7、/2、函數(shù)設(shè)計(jì)/*頭函數(shù)*/#include <stdio.h>/*函數(shù)頭部的定義和聲明*/#include <stdlib.h>/*c+中標(biāo)準(zhǔn)庫(kù)函數(shù)的定義，如size（），exit()函數(shù)等。/*輔助函數(shù)*/void print(unsigned int t);/*輸出界面的調(diào)用函數(shù)*/void download();/*相關(guān)數(shù)據(jù)的加載*/*置換算法函數(shù)*/void fifo();/*完成先進(jìn)先出算法的整個(gè)置換過(guò)程*/void lru();/*完成最近最久未使用算法的整個(gè)置換過(guò)程*/*主函數(shù)*/void main()/*完成輸出界面的顯示*/3、 流程圖（1）置換算法

8、的系統(tǒng)功能流程圖：(2)fifo算法的程序流程圖： （3）lru算法的流程圖：4、代碼#include <stdio.h>#include <stdlib.h>/*全局變量*/int msize; /*物理塊數(shù)*/int psize; /*頁(yè)面總數(shù)*/static int memery10=0; /*物理塊中的頁(yè)號(hào)*/static int page100=0; /*頁(yè)面序列*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void fifo();void lru();/*輔助函數(shù)*/void print(unsigned int t)

9、;void download();/*主函數(shù)*/void main() int i,k,code;printf("頁(yè)面置換算法演示，請(qǐng)按enter鍵完成對(duì)物理塊數(shù)和頁(yè)面序列的初始化操作.n"); printf("-");getchar();printf("-請(qǐng)輸入頁(yè)面總數(shù)(p<=100)：");scanf("%d",&psize);puts("-請(qǐng)依次輸入頁(yè)面序列(可連續(xù)輸入)：");for(i=0;i<psize;i+) scanf("%1d",&

10、;pagei);download();system("cls"); do puts("輸入的頁(yè)面序列為：");for(k=0;k<=(psize-1)/20;k+)for(i=20*k;(i<psize)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=psize-1)printf("%dn",pagei);elseprintf("%d ",pagei); printf("請(qǐng)輸入頁(yè)面置換算法的序號(hào)：ttt n&quo

11、t;); printf("- n"); printf(" 1.先進(jìn)先出(fifo) n"); printf(" 2.最近最久未使用(lru) n");printf(" 3.退出n");printf("- n"); printf("請(qǐng)選擇操作： bb"); scanf("%d",&code); switch(code) case 1: fifo(); break; case 2: lru(); break; case 3:printf("謝

12、謝使用頁(yè)面置換算法演示器!n"); exit(0);default:printf("輸入錯(cuò)誤，請(qǐng)重新輸入："); printf("按任意鍵重新選擇置換算法：-");getch();system("cls"); while (code!=3);getch();/*載入數(shù)據(jù)*/void download()printf("載入成功，按任意鍵進(jìn)入置換算法選擇界面：-");getch();void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k<=(p

13、size-1)/20;k+)for(i=20*k;(i<psize)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=psize-1)printf("%dn",pagei);elseprintf("%d ",pagei);for(j=0;j<msize;j+)for(i=20*k;(i<msize+20*k)&&(i<psize);i+)if(i>=j)printf(" |%d|",tempij);else pr

14、intf(" | |");for(i=msize+20*k;(i<psize)&&(i<20*(k+1);i+)for(flag=0,l=0;l<msize;l+)if(tempil=tempi-1l)flag+;if(flag=msize)/*頁(yè)面在物理塊中*/ printf(" ");elseprintf(" |%d|",tempij);/*每行顯示20個(gè)*/if(i%20=0)continue;printf("n");printf("-n");printf

15、("置換次數(shù)：%dtt n",t);printf("缺頁(yè)次數(shù)：%dtt n",t+msize);printf("缺頁(yè)率：%d/%d n",t+msize,psize);printf("-n"); /*先進(jìn)先出頁(yè)面置換算法*/void fifo() int memery10=0; int time10=0; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前msize個(gè)數(shù)直接放入*/ printf("-請(qǐng)輸入物

16、理塊的個(gè)數(shù)(m<=10)：");scanf("%d",&msize); for(i=0;i<msize;i+) memeryi=pagei; timei=i; for(j=0;j<msize;j+)tempij=memeryj; for(i=msize;i<psize;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j<msize;j+) if(memeryj!=pagei) k+; if(k=msize) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁(yè)*/ max=time0<time1?0

17、:1;for(m=2;m<msize;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/ for(j=0;j<msize;j+)tempij=memeryj; else for(j=0;j<msize;j+)tempij=memeryj; print(count);/*最近最久未使用置換算法*/void lru() int memery10=0; int flag10=0; /*記錄頁(yè)面的訪(fǎng)問(wèn)時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ int c

18、ount=0; /*記錄置換次數(shù)*/*前msize個(gè)數(shù)直接放入*/printf("-請(qǐng)輸入物理塊的個(gè)數(shù)(m<=10)：");scanf("%d",&msize); for(i=0;i<msize;i+) memeryi=pagei; flagi=i; for(j=0;j<msize;j+)tempij=memeryj; for(i=msize;i<psize;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j<msize;j+) if(memeryj!=pagei) k+; else flagj=

19、i; /*刷新該頁(yè)的訪(fǎng)問(wèn)時(shí)間*/ if(k=msize) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁(yè)*/ max=flag0<flag1?0:1;for(m=2;m<msize;m+)if(flagm<flagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁(yè)的訪(fǎng)問(wèn)時(shí)間*/ for(j=0;j<msize;j+)tempij=memeryj; else for(j=0;j<msize;j+)tempij=memeryj; print(count);三、結(jié)果分析1、就算法的思想而言，先進(jìn)先出算法總是先淘汰最先進(jìn)入內(nèi)

20、存的頁(yè)，最近最久未使用算法總是先淘汰最近最久未使用的頁(yè)。2、分析設(shè)計(jì)結(jié)果是否達(dá)到預(yù)期目標(biāo)：比較fifo和lru的命中率（命中率=1-缺頁(yè)率）相近，但是fifo的要低些，到達(dá)預(yù)期目標(biāo)。3、針對(duì)同一訪(fǎng)問(wèn)序列比較兩種算法的命中率：命中率=1-缺頁(yè)率，lru的命中率高于fifo的命中率。4、程序運(yùn)行結(jié)果如下：（1）該程序完成后，運(yùn)行結(jié)果時(shí)選用123412512345這12個(gè)數(shù)據(jù)來(lái)驗(yàn)證驗(yàn)證。界面如下：（2）進(jìn)入調(diào)用算法的界面后，首先選擇fifo算法，物理塊數(shù)為3。（3）當(dāng)物理塊m=3時(shí)，fifo算法的運(yùn)行結(jié)果如下，分別是有6次置換，9次缺頁(yè)。根據(jù)程序中的f=（msize+count+）/psize可得缺頁(yè)率為9/12。（4）物理塊數(shù)為3運(yùn)行完后，將其物理塊數(shù)改變?yōu)?。（5）當(dāng)物理塊m=4時(shí)，fifo算法的運(yùn)行結(jié)果如下，分別是有6次置換，10次缺頁(yè)。根據(jù)程序中的f=（msize+count+）/psize可得缺頁(yè)率為10/12。（6）進(jìn)入調(diào)用算法的界面后，選擇lru算法，物理塊數(shù)為3。（7）當(dāng)物理塊m=3