實(shí)驗(yàn)五請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法

操作系統(tǒng)實(shí)驗(yàn)報(bào)告班級(jí):計(jì)科0801班姓名：韓偉偉學(xué)號(hào)：08407106時(shí)間：2011-5-25實(shí)驗(yàn)五請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法模擬程序，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。實(shí)驗(yàn)屬性設(shè)計(jì)實(shí)驗(yàn)內(nèi)容通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令，指令的地址按下述原則生產(chǎn)：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分。將指令序列變換成為頁(yè)地址流設(shè)頁(yè)面大小為1K；用戶內(nèi)存容量為4頁(yè)到32頁(yè)；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條至第9條指令為第0頁(yè)；第10條至19條指令為第1頁(yè)；…第310條至319條指令為第31頁(yè)。計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。先進(jìn)先出算法(FIFO)最近最少使用算法(LRU)最佳使用算(OPT)命中率=1一頁(yè)面失效次數(shù)/頁(yè)地址流長(zhǎng)度本實(shí)驗(yàn)中，頁(yè)地址流長(zhǎng)度為320，頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存的次數(shù)。思路關(guān)于隨機(jī)數(shù)的產(chǎn)生辦法。首先要初始化設(shè)置隨機(jī)數(shù)，產(chǎn)生序列的開始點(diǎn)，例如，通過(guò)下列語(yǔ)句實(shí)現(xiàn)：srand(400)；計(jì)算隨機(jī)數(shù)，產(chǎn)生320條指令序列m=160；for(i=0；i<80；i++={j=i*4；a[j]=m；a[j+1]=m+1；a[j+2]=a[j]*1.0*rand()/32767；a[j+3]=a[j+2]+1m=a[j+3]+(319-a[j+3])*1.0*rand()/32767；}將指令序列變換成為頁(yè)地址流for(k=0；k<320；k++){pt=a[k]/10；pd=a[k]%10；???}計(jì)算不同算法的命中率rate=1-1.0*U/320；其中U為缺頁(yè)中斷次數(shù)，320是頁(yè)地址流長(zhǎng)度。輸出格式kfifo1ru40.230.25?321.01.0實(shí)驗(yàn)報(bào)告1.寫出你編寫的C語(yǔ)言程序。#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMyprintfprintf("|++++++++++++++++1\n")/*表格控制*/#definebsize4//物理塊大小#definepsize16//進(jìn)程大小typedefstructpage{intnum;/*記錄頁(yè)面號(hào)*/inttime;/*記錄調(diào)入內(nèi)存時(shí)間*/}Page;/*頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/Pageb[bsize];/*內(nèi)存單元數(shù)*/intc[bsize][psize];/*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/intqueue[100];/*記錄調(diào)入隊(duì)列*/intK;/*調(diào)入隊(duì)列計(jì)數(shù)變量*/intphb[bsize]={0};//物理塊標(biāo)號(hào)intpro[psize]={0};//進(jìn)程序列號(hào)intflag[bsize]={0};//進(jìn)程等待次數(shù)(存放最久未被使用的進(jìn)程標(biāo)志)inti=0,j=0,k=0;//i表示進(jìn)程序列號(hào),j表示物理塊號(hào)intm=-1,n=-1;//物理塊空閑和進(jìn)程是否相同判斷標(biāo)志intmax=-1,maxflag=0;//標(biāo)記替換物理塊進(jìn)程下標(biāo)intcount=0;//統(tǒng)計(jì)頁(yè)面缺頁(yè)次數(shù)**************************************************************//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“//R5&4cl~lAP//個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)//vma'l-r.序列號(hào)函數(shù)//*個(gè)*個(gè)**********************************************************int*build(){printf("隨機(jī)產(chǎn)生一個(gè)進(jìn)程序列號(hào)為：\n");inti=0;for(i=0;i<psize;i++){pro[i]=10*rand()/(RAND_MAX+1)+1;printf("%d”,pro[i]);}printf(〃\n〃)；return(pro);}//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“/44^i-j^l//個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)//H5XT/N物理塊//個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)intsearchpb(){for(j=0;j<bsize;j++){if(phb[j]==0){m=j;returnm;break;}}return-1;}**************************************************************進(jìn)程//““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““**************************************************************intsearchpro(){for(j=0;j<bsize;j++){if(phb[j]==pro[i]){n=j;returnj;}}return-1;//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“//'ttF7/A/Um//**************************************************************/0、口141V、存//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://*個(gè)*個(gè)**********************************************************voidempty(){for(i=0;i<bsize;i++)phb[i]=0;〃計(jì)數(shù)器置零count=0;〃計(jì)數(shù)器置零}//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“///~r.4ihAH山//個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)//-777htTHII頁(yè)面置換算法//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)voidFIFO(){for(i=0;i<psize;i++){m=searchpb();n=searchpro();//找flag值最大的for(j=0;j<bsize;j++){if(flag[j]>maxflag){maxflag=flag[j];max=j;}}if(n==-1)//不存在相同進(jìn)程{if(m!=-1)//存在空閑物理塊{phb[m]=pro[i];//進(jìn)程號(hào)填入該空閑物理塊count++;flag[m]=0;for(j=0;j<=m;j++){flag[j]++;}m=-1;}else//不存在空閑物理塊{phb[max]=pro[i];flag[max]=0;for(j=0;j<bsize;j++){flag[j]++;}max=-1;maxflag=0;count++;}}else//存在相同的進(jìn)程{phb[n]=pro[i];for(j=0;j<bsize;j++){flag[j]++;}n=-1;}for(j=0;j<bsize;j++){printf("%d",phb[j]);}printf(〃\n〃)；}printf("缺頁(yè)次數(shù)為：％d\n”,count);printf(〃\n〃)；}//*個(gè)*個(gè)**********************************************************//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)/*初始化內(nèi)存單元、緩沖區(qū)*/voidInit(Page*b,intc[bsize][psize]){inti,j;for(i=0;i<psize;i++){b[i].num=-1;b[i].time=psize-i-1;}for(i=0;i<bsize;i++)for(j=0;j<psize;j++)c[i][j]=-1;}/*取得在內(nèi)存中停留最久的頁(yè)面，默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面*/intGetMax(Page*b)inti;intmax=-1;inttag=0;for(i=0;i<bsize;i++){if(b[i].time>max){max=b[i].time;tag=i;}}returntag;}/*判斷頁(yè)面是否已在內(nèi)存中*/intEquation(intfold,Page*b){inti;for(i=0;i<bsize;i++){if(fold==b[i].num)returni;}return-1;}/*LRU核心部分*/voidLruu(intfold,Page*b){inti;intval;val=Equation(fold,b);if(val>=0){b[val].time=0;for(i=0;i<bsize;i++)if(i!=val)b[i].time++;}else{queue[++K]=fold;/*i記錄調(diào)入頁(yè)面*/val=GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<bsize;i++)if(i!=val)b[i].time++;}}voidLRU(){inti,j;K=-1;Init(b,c);for(i=0;i<psize;i++){Lruu(pro[i],b);c[0][i]=pro[i];/*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/for(j=0;j<bsize;j++)c[j][i]=b[j].num;}/*結(jié)果輸出*/printf("內(nèi)存狀態(tài)為：\n");Myprintf;for(j=0;j<psize;j++)printf("|%2d",pro[j]);printf(〃|\n〃)；Myprintf;for(i=0;i<bsize;i++){for(j=0;j<psize;j++){if(c[i][j]==-1)printf("|%2c”,32);elseprintf("|%2d”,c[i][j]);}printf(〃|\n〃)；}Myprintf;printf("\n調(diào)入隊(duì)列為：")；for(i=0;i<K+1;i++)printf("%3d”,queue[i]);printf("\n缺頁(yè)次數(shù)為：%6d\n缺頁(yè)率：％16.6f”,K+1,(float)(K+1)/psize);}**************************************************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*個(gè)*個(gè)**********************************************************voidmain(){intsel;do{printf("\t\t\t\t\t\t");printf("\t\t\t☆☆"-”歡迎進(jìn)入操作系統(tǒng)界面”-"☆☆\t\t\t");printf("\t\t\t\t\t\t\n");?「&"'['['[☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆'['['[〃)；printf("\t\t\t^虛擬內(nèi)存☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^1、產(chǎn)生隨機(jī)序列☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^2、最久未使用(LRU)☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^3、先進(jìn)先出(FIFO)☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^4、最佳置換算法(OPT)☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^5、三種算法的比較()☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^0、退出(Exit)☆\t\t\t");?「&"'['['[☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆'['['['/);printf("請(qǐng)選擇所要執(zhí)行的操作(0/1/2/3/4/5):");scanf(〃%d〃,&sel);switch(sel){case0:printf(〃\t\t\t"-"再見！"-"\t\t\t\n〃)；system(〃pause〃)；break;case1:build();break;case2:printf("最久未使用算\n〃)；LRU();empty();printf(〃\n〃)；break;case3:printf(〃先進(jìn)先出算\n〃)；FIFO();empty();printf(〃\n〃)；break;case5:printf("先進(jìn)先出算法\n");FIFO();empty();printf("最久未使用算法\n〃)；LRU();empty();break;default:printf("請(qǐng)輸入正確的選項(xiàng)號(hào)！〃)；printf(〃\n\n〃)；break;}}while(sel!=0);}產(chǎn)生的隨機(jī)序列：隨機(jī)產(chǎn)生二個(gè)進(jìn)程序列號(hào)為:16296.54998298641最近最少使用算法執(zhí)行結(jié)果如下:清曙霸甑的操作皿Ill6I2l?I6l5I4l?I9l8t2l?IBI6I4llI：L：1：L：1：1：5：5：5：5：S：2：2：2：2：4：4：!!6J5!6J6S6J6>6i6>8iB>8!8!8!8!8!IIISI2I2I2I4I4E4I4I4I4I4IGIGI6I:::：9：3：9：9：9：9：9