操作系统实验报告6-页面置换算法模拟.doc

-实验报告课程名称操作系统原理实验名称实验6：页面置换算法模拟实验时间年月日指导单位软件工程系指导教师 健学生*班级*学院(系)软件工程系专 业计算机软件与效劳外包. z.-实验名称实验1：Linu*操作、使用、编程与进程创立指导教师实验类型实验实验学时2实验时间0一、 实验目的1通过模拟实现几种根本页面置换的算法，了解虚拟存储技术的特点。2掌握虚拟存储请求页式存储管理中几种根本页面置换算法的根本思想，并至少用三种算法来模拟实现。3通过对几种置换算法页面的比拟，来比照他们的优缺点，并通过比拟更换频率来比照它们的效率。二、实验环境(实验设备)Windows 2000 Visual Studio三、实验容设计一个虚拟存储区和存工作区，并使用下述算法来模拟实现页面的置换：1. 先进先出的算法FIFO2. 最近最久未使用算法LRU3. 最正确置换算法OPT实验分析在进程运行过程中，假设其所访问的页面不存在存而需要把它们调入存，但存已无空闲时，为了保证该进程能够正常运行，系统必须从存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。 假设分给一作业的物理块数为3 ，页面数为20个。页面号为(20个)：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，11先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入存的页面，即选择在存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。2最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入存后的使用情况来进展决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最正确OPT置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间不再被访问的页面，采用最正确算法，通常可保证获得最低的缺页率。4FIFO页面置换算法当需要访问一个新的页面时，首先调用findE*ist(i)函数来查看物理块中是否就有这个页面，假设要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，假设存在有空闲物理块，则将页面放入；假设没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer+。5LRU页面置换算法当需要访问一个新的页面，首先调用findE*ist(i)函数查看物理块中是否就有这个页面。6. OPT页面置换算法 当需要访问一个新的页面，首先调用findE*ist(i)函数来查看物理块中是否有这个页面。7寻找置换页面函数findReplace比拟三个物理块中的时间标记timer，找到时间最久的。代码#include<stdio.h>#include<stdlib.h>#include<time.h>#define BLOCK_MA*_SIZE 20/最?大洙?物?理?块é大洙?小?enumFIFO=1,LRU,OPT;struct node_pageint address;/指?令?地?址·int page_num;/页?面?号?int ne*t_order;/下?一?次?访?问ê的?次?序ò*page;/物?理?块é定¨义?typedefstruct BlockNodeint page_inde*;/page数簓组哩?的?下?标括?struct BlockNode * ne*t;BlockNode;structint length;/当獭?前°物?理?块é长¤度èint miss_flag;/缺?页?标括?志?，?假设?为a1，?则ò缺?页?int miss_count;/缺?页?次?数簓 BlockNode*front; BlockNode*rear;Block;/本?程ì序ò中D全?局?变?量?名?均ù由?两?个?单蹋?词洙?组哩?成é，?且ò开a头?字?母?大洙?写int BlockSize = 5;/物?理?块é大洙?小?int PageCount = 200;/页?面?总哩?数簓int PageSize = 1024;/页?面?大洙?小?int AddrRange = 8*1024;/访?问ê地?址·?围§int get_num(int down,int up)/得?到?一?个?downup之?间?的?整?数簓int num;char str111;while(1)fgets(str,111*sizeof(int),stdin);num=atoi(str);/把?字?符?串?中D的?数簓字?转羇换?为a整?数簓if(num>=down&& num<=up) break;printf("输?入?围§有瓺误ó,请?重?新?输?入?:");/whilereturn num;void init_block()/构1造ì一?个?空?的?物?理?块é队ó列Block.rear=Block.front=(BlockNode*)malloc(sizeof(BlockNode);if(!Block.front)printf("ú存?分?配?失骸?败悒?n"); e*it(0);Block.length=0;Block.miss_count=0;Block.rear->ne*t=NULL;void enqueue(int page_inde*)/入?队óBlockNode*node=(BlockNode*)malloc(sizeof(BlockNode);if(!node)printf("ú存?分?配?失骸?败悒?n");e*it(0);node->page_inde*=page_inde*;node->ne*t=NULL;Block.length+;Block.rear->ne*t=node;Block.rear=node;void dequeue()/出?队óBlockNode*node;node=Block.front->ne*t;Block.front->ne*t=node->ne*t;if(node= Block.rear)Block.rear=Block.front;free(node);Block.length-;void clear_block()/清?空?物?理?块éwhile(Block.rear=Block.front->ne*t)Block.front->ne*t=Block.rear->ne*t; free(Block.rear);Block.length-;Block.rear=Block.front;Block.length=0;Block.miss_count=0;void destroy_block()/销ú毁ù物?理?块éwhile(Block.rear=Block.front)Block.front=Block.front->ne*t;free(Block.rear);free(page);void init_page()/初?始?化页?面?系列int i,j;srand(time(NULL);/用?当獭?前°系统?时骸?间?来?初?始?化随?机ú种?子哩?page=(struct node_page*) malloc(PageCount*sizeof(struct node_page);for(i=0;i<PageCount;i+)pagei.address=rand()%AddrRange;pagei.page_num=pagei.address/PageSize;for(i=0;i<PageCount;i+)for(j=i+1;j<PageCount;j+)if(pagei.page_num= pagej.page_num)pagei.ne*t_order=j;break;/if/forif(j= PageCount)/说明÷pagei以?后ó都?不?会á再ù访?问êpagei.ne*t_order= PageCount;/forvoid print_page()/打洙?印?页?面?系列int i;printf("n");printf("页?面?系列为a：阰n");for(i=0;i<PageCount;i+)printf("%-2d,%-4d",pagei.page_num,pagei.address%PageSize);if(i+1)%5= 0)printf("n");/ifprintf("n");void FIFO_Replace(int page_inde*)/FIFO置?换?BlockNode*node;if(!Block.length)enqueue(page_inde*);Block.miss_flag=0;return;node=Block.front;while(node=node->ne*t)if(pagenode->page_inde*.page_num=pagepage_inde*.page_num)Block.miss_flag=0;return;if(Block.length<BlockSize)enqueue(page_inde*);Block.miss_flag=0;return;dequeue();enqueue(page_inde*);Block.miss_flag=1;Block.miss_count+;void LRU_Replace(int page_inde*)/LRU置?换?BlockNode*node,*last_node;if(!Block.length)enqueue(page_inde*);Block.miss_flag=0;return;last_node=node=Block.front;while(node=node->ne*t)if(pagenode->page_inde*.page_num= pagepage_inde*.page_num)last_node->ne*t=node->ne*t;Block.length-;if(node= Block.rear)Block.rear=last_node;enqueue(node->page_inde*);free(node);Block.miss_flag=0;return;last_node=node;if(Block.length<BlockSize)enqueue(page_inde*);Block.miss_flag=0;return;dequeue();enqueue(page_inde*);Block.miss_flag=1;Block.miss_count+;void OPT_Replace(int page_inde*)/OPT置?换?BlockNode*node;BlockNode*ma*_node,*ma*_node_last;if(!Block.length)enqueue(page_inde*);Block.miss_flag=0;return;node=Block.front;while(node=node->ne*t)if(pagenode->page_inde*.page_num= pagepage_inde*.page_num)node->page_inde*=page_inde*;Block.miss_flag=0;return;if(Block.length<BlockSize)enqueue(page_inde*);Block.miss_flag=0;return;node=Block.front;ma*_node=node->ne*t;while(node=node->ne*t)/寻°找òBlock中Dne*t_order值最?大洙?的?节ú点?if(pagema*_node->page_inde*.ne*t_order<pagenode->page_inde*.ne*t_order)ma*_node=node;node=Block.front;ma*_node_last=node;while(node=node->ne*t)/寻°找òBlock中Dne*t_order值最?大洙?的?节ú点?的?上?一?个?节ú点?if(node= ma*_node)break;ma*_node_last=node;ma*_node_last->ne*t= ma*_node->ne*t;Block.length-;if(ma*_node= Block.rear)Block.rear=ma*_node_last;free(ma*_node);enqueue(page_inde*);Block.miss_flag=1;Block.miss_count+;void page_replace(int num)int i,j;BlockNode*node;char str35="FIFO","LRU ","OPT "printf("=%s=n",strnum-1);printf("页?面?号?*");for(i=0;i< BlockSize;i+)printf(" ");printf("* 是?否?缺?页? *n");printf("n");for(i=0;i<PageCount;i+)printf(" %-4d*",pagei.page_num);if(num= FIFO)FIFO_Replace(i);elseif(num = LRU)LRU_Replace(i);elseif(num = OPT)OPT_Replace(i);node=Block.front;while(node=node->ne*t)printf("%-2d",pagenode->page_inde*.page_num);for(j=Block.length;j<BlockSize;j+)printf(" ");printf("* %s *nn",(Block.miss_flag=1 ? "Yes" : "No");printf("nn");printf("缺?页?数簓:%d,缺?页?率ê:%.2fnn",Block.miss_count,(float)Block.miss_count/PageCount *100);printf("按恪?回?车键ü继ì续?!nn");getchar();void confige()/程ì序ò设?置?int num;while(1)printf("n*n");printf("* 程ì序ò设?置? *n");printf("*n");printf("* 1,设?置?物?理?块é大洙?小?(默?认?5) *n");printf("* 2,设?置?访?问ê地?址·?围§ (默?认?8K) *n");printf("* 3,设?置?页?面?大洙?小?(默?认?1K) *n");printf("* 4,设?置?页?面?总哩?数簓(默?认?200) *n");printf("* 5,显?示?各÷项?设?置?值 *n");printf("* 6,返?回? *n");printf("*n");printf("请?输?入?您ú的?选?择?:"); num=get_num(1,6);if(num=6)break;if(num=1)printf("请?输?入?物?理?块é大洙?小?(1%d):",BLOCK_MA*_SIZE);BlockSize=get_num(1,BLOCK_MA*_SIZE);printf("设?置?成é功|!nn");/ifelseif(num=2)printf("请?输?入?访?问ê地?址·?围§(1%d)K: ",999);AddrRange=get_num(1,999)* 1024;printf("设?置?成é功|!nn");/elseifelseif(num=3)printf("请?输?入?页?面?大洙?小?(1%d)K: ",AddrRange/1024);PageSize=get_num(1,AddrRange/1024)* 1024;printf("设?置?成é功|!nn");/elseifelseif(num=4)printf("请?输?入?页?面?总哩?数簓(1%d):",32767);PageCount=get_num(1,32767);printf("设?置?成é功|!nn");/elseifelseif(num=5)printf("-n");printf("*当獭?前°物?理?块é大洙?小?:%dn",BlockSize);printf("*当獭?前°访?问ê地?址·?围§:%d Kn",AddrRange/1024);printf("*当獭?前°页?面?大洙?小?:%d Kn",PageSize/1024);printf("*当獭?前°页?面?总哩?数簓%dn",PageCount);printf("-n");free(page);init_page();void begin()int num;print_page();while(1)printf("n*n");printf("* 页?面?置?换?算?法?*n");printf("*n");printf("* 1,先è进?先è出?置?换?算?法?FIFO) *n");printf("* 2,最?近ü最?久?未使?用?置?换?算?法?LRU) *n");printf("* 3,最?佳?置?换?算?法?OPT) *n");printf("* 4,返?回? *n");printf("*n");printf("请?输?入?您ú的?选?择?:");num=get_num(1,4);if(num= 4)break;page_replace(num);clear_block();free(page);init_page();int main()int num;init_block();init_page();while(1)printf("n*n");printf("* 存?储洹?器÷管ü理?模拟a系统? *n");printf("*n");printf("* 1,进?入?页?面?置?换?算?法?*n");printf("* 2,进?入?程ì序ò设?置? *n");printf("* 3,退?出? *n");printf("*n");printf("请?输?入?您ú的?选?择?:");num=get_num(1,3);if(num= 3)break;if(num= 1)begin();elseif(num = 2)confige();destroy_block();return 0;截图四、实验小结针对实验容逐项小结实验中发现的问题、自己的解决方法、心得体会等 一开场做这个实验时，首先是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺点和相互之间衍生互补关系。这四个算法中，难以实现的是LRU算法，因为它涉及到访问时间的计算，而且它的开销也比拟大。OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。而FIFO和CLOCK实现起来比拟容易，FIFO算法的实现和CLOCK算法的实现很相似，FIFO可视为CLOCK的退化版。我先写了CLOCK算法，再删去一些约束条件就退化为FIFO算法。这就是两者的一样之处。理论上，CLOCK算法需要维持一个循环的主存缓冲区，需要一个循环队列去实现，并且，FIFO算法保持先进先出，因此需要一个先进先出队列。但是，我实现这两个算法只用到了单向链表的数据构造，剩下的由其中的指针去把握了。因此，必须对指针使用有敏锐的感觉。五、指导教师评语成 绩批阅人日 期. z.