操作系统最佳置换算法实验报告

1实验报告系别班级学号姓名时间地点计算机科学系课程名称操作系统实验名称最佳置换算法实验过程一．实验目的1.了解内存管理的功能。2.掌握进程可变内存管理的几种内存分配与回收算法。3.掌握可变分区算法中空闲分区的合并方法二．实验内容实现内存分配算法——最佳置换算法。三．实验程序#defineMAX100#defineMIX10#includestdio.h//最佳置换算法（前提：给出页面号引用窜）//数据结构intrecent=0;//将被装入内存的页号的标号（从0开始计）intcount;//序列号总数intload_number;//装入内存的页面数//序列号intarray[MAX];//页面structpageTable{intpageNum;2intwuliNum;//...};structpageTablepage_t[MIX];//页表structpageTable*recentP;//传递内存页面数组、数组长度、命中索引号三个参数；并将该数组按最近最久排序，//前面元素为最久未使用，而末尾元素为最近未使用voidgetline(structpageTablea[],intn,intindex){inti,temp;//for(i=0;in;i++)//找命中页面号temp=a[index].pageNum;for(i=index;in-1;i++)a[i].pageNum=a[i+1].pageNum;a[n-1].pageNum=temp;}//input页面号引用窜(空格结束）voidinput(){charch;inti;//页面号printf(pleaseinputananykeynotinclude'q',andthenbegin.\n);scanf(%c,&ch);while(ch!='q'){printf(pleaseinputacount:\n);scanf(%d,&count);//printf(\n);printf(pleaseinputpagenumbers:\n);3for(i=0;icount;i++)scanf(%d,&array[i]);//printf(\n);for(i=0;icount;i++)printf(%d,array[i]);printf(\n);printf(pleaseinputthenumbersofpagetoload:\n);scanf(%d,&load_number);////for(i=0;istructpage_tablecount;i++)printf(pleaseinputa'q'toexitinput!\n);scanf(%c,&ch);scanf(%c,&ch);}recentP=page_t;}//装载至内存函数//voidfirstLoad(){inti,nCount=0,flag=0;recentP-pageNum=array[recent];recent++;recentP++;nCount++;while(nCountload_number){//扫描是否有相等的页号for(i=0;inCount;i++)if(page_t[i].pageNum==array[recent]){flag=1;break;}//*{}isimportant*4if(flag){recent++;flag=0;printf(%d命中\n,array[recent-1]);}//*importanceelse{recentP-pageNum=array[recent];recent++;recentP++;nCount++;}}//show()for(i=0;inCount;i++)printf(%d,page_t[i].pageNum);printf(\n);}//search函数找一个要替换的页号voidsearch()//给replace_p，replace_n赋值！{inti,j,no=0,k=0;intflag=0,flag1=0;//有该页号，则置1//记录与进入内存的页号相等的将被装入的页号的最大次数inttime_count1=0,time_count2=0;//先检查是否与array[recent]命中,是则n置1for(i=0;iload_number;i++)if(page_t[i].pageNum==array[recent]){no=1;break;}//*{}isimportant*if(!no){printf(%d命中\n,array[recent-1]);//*importance5recent++;getline(page_t,load_number,i);}else{no=0;//important//检查是否有与内存中页号相同的页号在等待，有则falg置1，无则falg置0for(i=0;iload_number;i++){for(j=recent;jcount;j++)if(page_t[i].pageNum==array[j]){flag=1;break;}if(flag){flag=0;//importantfor(k=recent;page_t[i].pageNum!=array[k];k++);time_count2=k-recent+load_number-i;//?可能出错if(time_count1time_count2){time_count1=time_count2;flag1=i;//}}for(k=0;kload_number;k++)if(page_t[k].pageNum==array[recent+time_count1-load_number+flag1]){recentP=&page_t[k];break;}}}if(j==count)//采用先进先出算法recentP=page_t;recentP-pageNum=array[recent];6recent++;}//voidmain(){//初始化数据input();while(recent=count){firstLoad();search();}}7四．运行截图8五．实验总结通过这次实验，我对最佳置换算法的掌握更加熟练了。最佳置换算法是用一维数组存储页面号序列，存储装入物理块中的页面。并记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。