實驗五請求頁式存儲管理的頁面置換算法

操作系統實驗報告班級:計科0801班姓名：韓偉偉學號：08407106時間：2011-5-25實驗五請求頁式存儲管理的頁面置換算法實驗目的通過請求頁式存儲管理中頁面置換算法模擬程序，了解虛擬存儲技術的特點，掌握請求頁式存儲管理的頁面置換算法。實驗屬性設計實驗內容通過隨機數產生一個指令序列，共320條指令，指令的地址按下述原則生產：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分。將指令序列變換成為頁地址流設頁面大小為1K；用戶內存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條至第9條指令為第0頁；第10條至19條指令為第1頁；…第310條至319條指令為第31頁。計算并輸出下述各種算法在不同內存容量下的命中率。先進先出算法(FIFO)最近最少使用算法(LRU)最佳使用算(OPT)命中率=1一頁面失效次數/頁地址流長度本實驗中，頁地址流長度為320，頁面失效次數為每次訪問相應指令時，該指令所對應的頁不在內存的次數。思路關于隨機數的產生辦法。首先要初始化設置隨機數，產生序列的開始點，例如，通過下列語句實現：srand(400)；計算隨機數，產生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；}將指令序列變換成為頁地址流for(k=0；k<320；k++){pt=a[k]/10；pd=a[k]%10；???}計算不同算法的命中率rate=1-1.0*U/320；其中U為缺頁中斷次數，320是頁地址流長度。輸出格式kfifo1ru40.230.25?321.01.0實驗報告1.寫出你編寫的C語言程序。#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMyprintfprintf("|++++++++++++++++1\n")/*表格控制*/#definebsize4//物理塊大小#definepsize16//進程大小typedefstructpage{intnum;/*記錄頁面號*/inttime;/*記錄調入內存時間*/}Page;/*頁面邏輯結構，結構為方便算法實現設計*/Pageb[bsize];/*內存單元數*/intc[bsize][psize];/*暫保存內存當前的狀態(tài)：緩沖區(qū)*/intqueue[100];/*記錄調入隊列*/intK;/*調入隊列計數變量*/intphb[bsize]={0};//物理塊標號intpro[psize]={0};//進程序列號intflag[bsize]={0};//進程等待次數(存放最久未被使用的進程標志)inti=0,j=0,k=0;//i表示進程序列號,j表示物理塊號intm=-1,n=-1;//物理塊空閑和進程是否相同判斷標志intmax=-1,maxflag=0;//標記替換物理塊進程下標intcount=0;//統計頁面缺頁次數**************************************************************//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“//R5&4cl~lAP//個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個//vma'l-r.序列號函數//*個*個**********************************************************int*build(){printf("隨機產生一個進程序列號為：\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//個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個//H5XT/N物理塊//個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個intsearchpb(){for(j=0;j<bsize;j++){if(phb[j]==0){m=j;returnm;break;}}return-1;}**************************************************************進程//““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““**************************************************************intsearchpro(){for(j=0;j<bsize;j++){if(phb[j]==pro[i]){n=j;returnj;}}return-1;//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“//'ttF7/A/Um//**************************************************************/0、口141V、存//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://*個*個**********************************************************voidempty(){for(i=0;i<bsize;i++)phb[i]=0;〃計數器置零count=0;〃計數器置零}//“““““““““““““““““““““““““““““““““““““““““““““““““““““““"“““""“///~r.4ihAH山//個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個//-777htTHII頁面置換算法//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個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)//不存在相同進程{if(m!=-1)//存在空閑物理塊{phb[m]=pro[i];//進程號填入該空閑物理塊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//存在相同的進程{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("缺頁次數為：％d\n”,count);printf(〃\n〃)；}//*個*個**********************************************************//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個個/*初始化內存單元、緩沖區(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;}/*取得在內存中停留最久的頁面，默認狀態(tài)下為最早調入的頁面*/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;}/*判斷頁面是否已在內存中*/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記錄調入頁面*/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];/*記錄當前的內存單元中的頁面*/for(j=0;j<bsize;j++)c[j][i]=b[j].num;}/*結果輸出*/printf("內存狀態(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調入隊列為：")；for(i=0;i<K+1;i++)printf("%3d”,queue[i]);printf("\n缺頁次數為：%6d\n缺頁率：％16.6f”,K+1,(float)(K+1)/psize);}**************************************************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*個*個**********************************************************voidmain(){intsel;do{printf("\t\t\t\t\t\t");printf("\t\t\t☆☆"-”歡迎進入操作系統界面”-"☆☆\t\t\t");printf("\t\t\t\t\t\t\n");?「&"'['['[☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆'['['[〃)；printf("\t\t\t^虛擬內存☆\t\t\t");printf("\t\t\t^^\t\t\t");printf("\t\t\t^1、產生隨機序列☆\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、先進先出(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("請選擇所要執(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(〃先進先出算\n〃)；FIFO();empty();printf(〃\n〃)；break;case5:printf("先進先出算法\n");FIFO();empty();printf("最久未使用算法\n〃)；LRU();empty();break;default:printf("請輸入正確的選項號！〃)；printf(〃\n\n〃)；break;}}while(sel!=0);}產生的隨機序列：隨機產生二個進程序列號為:16296.54998298641最近最少使用算法執(zhí)行結果如下:清曙霸甑的操作皿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