覃毅操作系统实习报告

操作系统实习报告桂林理工大学信息科学与工程学院计算机科学与技术（应用）专业-班覃毅页面置换系统设计设计目的：加深对祈求页式存储管理实现原理的理解，掌握最佳OPT置换算法、先进先出FIFO页面置换算法、近来最久未使用LRU页面置换算法，并运用程序设计语言模拟其过程。设计规定:1．顾客可认为程序指定内存块数2．顾客可以自由设置程序的页面访问次序3.顾客可在OPT、FIFO和LRU算法选择一种,并能观看到页面置换过程。设计内容：设计一种由顾客输入指定的链式队列设计一种由顾客指定块数的内存块链式队列分别设计OPT、FIFO、LRU算法开发环境：Windows环境，VC6.0平台分析设计：<一>试验原理：在进程运行过程中，若其所要访问的页面不在内存时，需要把它们调入内存，但内存已无空闲空间时，为了保证进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。OPT算法:每访问一种页面都先扫描内存块链式队列，若目前需访问页面已被调入内存则可访问下一种页面；否则，从内存块队列中选择一种（未来）最长时间内不再被访问的页面并将其换出。详细实现：用目前需访问页面扫描内存块队列，若已被调入则停止，否则将其计数器count加1。最终选择计数器值最大的内存块换出。FIFO算法：该算法在发生缺页时总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。详细实现：每个页面调入内存时总将其放在内存块队列的队尾，每当发生缺页时就将处在对头的内存块页面换出。LRU算法：该算法根据页面调入内存后近来最久未使用的页面予以淘汰。详细实现：每个页面调入内存时其时间计数器count开始计时，每当有页面被调入时内存中的页面的时间计数器均加1；新被调入的页面时间计数器初始化为1。发生缺页时，寻找时间计数器值最大的内存块页面换出。<二>程序构造：组建顾客输入的页面访问队列，q_new=newq_node;q_r->next=q_new;q_r=q_r->next;根据顾客输入指定的内存块数目m,组织m_node类型结点的内存队列。m_cp=newm_node;rear->mp=m_cp;寻找换出页面并换人新页面 m_cp->mpage=temp->page;或者调整内存块队列 for(m_temp=m_cp,m_cp=m_cp->mp;m_cp!=rear;m_cp=m_cp->mp) {m_temp->mpage=m_cp->mpage;m_temp=m_cp; } m_temp->mpage=m_cp->mpage; m_temp=m_cp; m_temp->mpage=new_mcp->mpage; rear=m_temp;<三>数据构造：顾客指定的访问页面序列构造体结点：structq_node{intpage;//访问页号 q_node*next;//指向下一种节点 q_node() {next=NULL;}};内存块构造体结点：structm_node//内存块结点{intmpage;//调入内存中的页面号 intcount;//用于计数 m_node*mp;//指向下一种结点 m_node() { count=0; mp=NULL; }};初始化，将顾客指定的访问页面组织成链式队列，并提醒顾客输入内存块数目调用初始化，将顾客指定的访问页面组织成链式队列，并提醒顾客输入内存块数目调用LRU算法：LRU(q_h,n)调用FIFO算法：FIFO(q_h,n)调用OPT算法：OPT(q_h,n)程序退出，return0；顾客选择退出，ch=q或者ch=Q判断顾客选择的是哪种算法，并调用对应的算法if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;switch(ch)顾客选择算法Cin>>ch 顾客选择算法顾客选择算法Cin>>ch顾客选择算法Cin>>ch判断顾客选择的是哪种算法，并调用对应的算法if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;判断顾客选择的是哪种算法，并调用对应的算法if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;switch(ch) 运行示例及成果分析:选用测试数据并调用对应算法，页面置模拟过程如下图所示：1.测试数据为12302，以111作为结束标志，运行测试成功2.测试数据为123564213，测试成功，页面置换模拟过程如下图所示：实习心得体会：通过两个星期的操作系统实习，我收获了诸多，也学到了诸多。为了完毕实习任务，我需要一次又一次地研究页面置换的有关算法，尤其是本次需要使用程序设计语言模拟设计的OPT、FIFO、LRU三种算法。在分析理解透这三个算法的基础上，我开始着手开始设计。我用了一天的时间完毕了程序设计，但实习任务绝不是仅此就结束的。我在调试程序过程中，碰到了诸多难题。在此期间我的情绪曾一度低落，甚至对自己能否独立完毕实习任务失去了信心。但很快我懂得编写程序、调试程序都不是一件轻易的事情，我不能太过于依赖他人的协助，而需要自己一步步地探索，一点点地积累，才能真正地学到东西，这这也是郭老师教会我的。因此，在操作系统实习过程中，我真正地理理解页面置换算法的原理与调度过程，加深了对指针的理解，学会了怎样灵活使用使用指针，同步也增强了自己的实践动手能力，到达了理论联络实际的效果！附录：源程序清单#include<iostream>usingnamespacestd;structq_node//顾客指定的访问页面序列{intpage;//页号q_node*next;//指向下一种节点q_node() {next=NULL;}};structm_node//内存块结点{intmpage;//调入内存中的页面号 intcount;//用于计数 m_node*mp;//指向下一种结点m_node(){count=0;mp=NULL;}};intmain(){voidOPT(q_node*h,intx);voidFIFO(q_node*h,intx);voidLRU(q_node*h,intx);q_node*q_h,*q_r,*q_new; intn;charch; cout<<"***************欢迎使用页面置换演示系统！***************"<<endl<<endl; cout<<"***************计算机（应用）-1班********************"<<endl <<"****************学号：*********************"<<endl <<"****************覃毅*********************"<<endl<<endl; cout<<"请你输入需要访问的页面队列:"<<endl;q_new=newq_node; cin>>q_new->page; q_h=q_new; q_r=q_h; while(q_r->page!=111)//创立顾客指定的访问队列 { q_new=newq_node;cin>>q_new->page; q_r->next=q_new; q_r=q_r->next; }cout<<"请输入你设置的内存块数：";cin>>n; cout<<endl<<"请您选择页面置换算法;"<<endl <<"O代表最佳置换算法;"<<endl <<"F代表先进先出页面置换算法;"<<endl <<"L代表近来最久未使用算法！"<<endl<<endl;while(1) { cout<<"请选择你需要调用的算法：";cin>>ch;//顾客选择页面置换算法 if(ch=='q'||ch=='Q') { cout<<"退出演示系统！"<<endl; break; } if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;switch(ch) { case'O':OPT(q_h,n);break; case'F':FIFO(q_h,n);break; case'L':LRU(q_h,n);break; default:cout<<"输入错误。"<<endl; } }return0;}/****************OPT算法:1.装入x个页面到内存块数组；2.判断待访问队列中的首元素，并进行对换或者访问下一页******/voidOPT(q_node*h,intx){q_node*temp,*cp;//temp指向访问队列中的对头，cp作为活动指针m_node*head,*rear,*m_cp;inti,max;boolfound;temp=h;head=newm_node;head->mpage=temp->page;//组建内块队列rear=head;temp=temp->next;for(i=2;i<=x;i++){ m_cp=newm_node; m_cp->mpage=temp->page; rear->mp=m_cp; rear=rear->mp; temp=temp->next;}//此时temp指向目前待访问页面while(temp->page!=111){ for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp)//**************扫描内存数组，寻找未来最久不会被访问的页面********************** { cp=temp; found=false; while(cp->page!=111) { if(m_cp->mpage==cp->page) { found=true; break; } else m_cp->count++; cp=cp->next; } }max=head->count;for(m_cp=head->mp;m_cp!=NULL;m_cp=m_cp->mp) if(m_cp->count>max) max=m_cp->count;cp=temp; for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp) if(cp->page==m_cp->mpage) { temp=temp->next; found=true; cout<<""<<m_cp->mpage<<"页已被调入内存,接着访问下一种页面！"<<endl; } if(found)//目前页已被调入内存，需访问下一种页面 continue; for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp) if(m_cp->count==max) { cout<<""<<m_cp->mpage<<"页被换出；" <<temp->page<<"页换人。"<<endl; m_cp->mpage=temp->page; m_cp->count=0;//****************** break; }temp=temp->next;for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp) m_cp->count=0;}cout<<"*****************OPT算法结束！******************"<<endl;}/******************FIFO算法：1.组织内存块队列；2.若目前待访问页面已存在内存中，则将它取出并移动到队尾，访问下一种元素；否则，用目前待访问页面置换对头内存块3.访问下一种元素****************/voidFIFO(q_node*h,intx){m_node*head,*rear,*m_cp;intj; boolfound;//标识目前待换人页面与否已在内存q_node*temp=h; head=newm_node; head->mpage=temp->page;//组织内存块队列 rear=head; temp=temp->next;for(j=2;j<=x;j++) { m_cp=newm_node; m_cp->mpage=temp->page;rear->mp=m_cp; rear=rear->mp; temp=temp->next; }//跳出循环时temp指向目前待访问页面while(temp->page!=111)//temp指向目前待访问的元素 { cout<<""<<temp->page<<"页被访问！"<<endl; found=false; m_cp=head;//m_cp用于扫描内存块队列for(j=1;j<=x;j++) { if(temp->page!=m_cp->mpage)//判断目前待访问元素与否已经调入内存，若没有调入则继续扫描内存块队列 m_cp=m_cp->mp; else//否则调整内存块队列 { cout<<""<<temp->page<<"页已被调入内存，修改内存块队列次序并访问下一种页面！"<<endl;m_node*m_temp,*new_mcp=newm_node;//new_mcp结点用于保留已被调入的页面信息new_mcp->mpage=m_cp->mpage;for(m_temp=m_cp,m_cp=m_cp->mp;m_cp!=rear;m_cp=m_cp->mp) {m_temp->mpage=m_cp->mpage; m_temp=m_cp; } m_temp->mpage=m_cp->mpage; m_temp=m_cp; m_temp->mpage=new_mcp->mpage; rear=m_temp; found=true; break; } } if(found) { temp=temp->next; continue; }//执行页面置换 m_node*m_temp,*new_mcp=head; cout<<""<<head->mpage<<"页被换出，"<<temp->page<<"页被换人！"<<endl; for(m_temp=head,new_mcp=head->mp;new_mcp!=rear;new_mcp=new_mcp->mp) { m_temp->mpage=new_mcp->mpage; m_temp=m_temp->mp; }m_temp->mpage=new_mcp->mpage; m_temp=m_temp->mp; m_temp->mpage=temp->page; rear=m_temp;temp=temp->next; }cout<<"*****************FIFO算法结束!*****************"<<endl;}/***************LRU算法：(备注：节点元素count用于内存块计算器)1.组织内存队列，每当有一种新页面从外存调入内存，需将其内存块计算器置12.扫描、换页。若目前待访问页面已被调入内存，则重新初始化其内存块计算器值；否则，寻找近来最久未被访问的内存块页面将其换出并将其计算器置1，同步使其他内存块页面计算器值加1***************/voidLRU(q_node*h,intx){m_node*head,*rear,*m_cp; intj,k,max; boolfound;//标识目前待换人页面与否已在内存q_node*temp=h; head=newm_node;head->mpage=temp->page;//第一模块：组织内存块队列 rear=head; temp=temp->next;for(j=2;j<=x;j++) {m_cp=newm_node;//m_cp指向目前内存块 m_cp->mpage=temp->page;rear->mp=m_cp; rear=rear->mp; temp=temp->next; m_cp=head; for(k=1;k<=j;k++)//将已调入内存的页面计算器值加1 {m_cp->count++; m_cp=m_cp->mp; }}