操作系统课程设计实验报告用C实现页面调度算法.doc

操 作 系 统实验报告(3)学院：计算机科学与技术学院班级：计091学号：姓名：时间：2011/12/31目 录1. 实验名称32. 实验目的33. 实验内容34. 实验要求35. 实验原理36. 实验环境47. 实验设计47.1数据结构设计47.2算法设计57.3功能模块设计98. 实验运行结果99. 实验心得13附录：源代码（部分）13一、实验名称：用C+实现页面调度算法二、实验目的：通过自己编程来实现页面调度算法，进一步理解页面调度算法的概念及含义，提高对页面调度算法的认识，同时提高自己的动手实践能力。加深我们对主存与辅助存储器统一管理、逻辑地址与物理地址转换、部分装入和部分替换问题的理解，同时，有利于我们对虚拟存储技术的理解。三、实验内容：利用C+,实现页面调度算法1. 最优替换算法OPT2. 先进先出调度算法3. 最近最少调度算法四、实验要求：1.完成页面调度算法的设计2.分别计算每种算法的缺页次数和缺页中断率五、实验原理：不必装入进程的全部信息，仅将当前使用部分先装入主存，其余部分存放在磁盘中，待使用时由系统自动将其装起来。当进程所访问的程序和数据在主存中时，可顺利进行；如果处理器所访问的程序或数据不在主存中，为了继续执行，由系统自动将这部分信息从磁盘装入，叫做“部分装入”；如若此刻没有足够的空闲物理空间，便把主存中暂时不用的信息移至磁盘，叫做“部分替换”。目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。 1.最优替换算法OPT选择将来最久不被访问的页面作为被替换的页面，它就是一种比较好的页面替换算法。2. 先进先出调度算法 先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。 3.最近最少调度算法 先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。缺页中断次数是缺页时发出缺页中断的次数 缺页中断率=缺页中断次数/总的页面引用次数*100% 六、实验环境：Win-7系统Visual C+ 6.0七、实验设计：1.数据结构设计定义结构体：struct PageFrame/页框结构int id;/页框号int pageId;/驻留的页号int visitedCount;/驻留页计数器，访问加1int unvisitedCount;/最近访问，访问清零，未访问加1bool replace;/将被淘汰为trueint stayTime;/驻留时间计数int nextsite;struct Page/页结构int id;/页号struct Data/基本数据构成PageFrame *pf;/页框指针，用于指定个数页框申请int pfLength;/页框个数Page *p;/页指针，用于指定个数页申请int pLength;/页个数int *pfLogicRuler;/逻辑标尺，用于记录淘汰序列int pageLackCount;/缺页计数器;定义类对象：class Method/方法类private:public:Method()bool findPage(Data *db,int pid)bool flag=false;for(int i=0;i<db->pfLength;i+)if(db->pfi.pageId=pid)db->pfi.visitedCount+;db->pfi.unvisitedCount=1;db->pfi.replace=false;flag=true;elsedb->pfi.unvisitedCount+;db->pfi.stayTime+;return flag;2.算法设计 2.1 FIFO算法class FIFO:public Method/FIFO算法private:public:void setpfLogicRuler(Data *db)int *a2;a0=new intdb->pfLength;a1=new intdb->pfLength;for(int i = 0; i<db->pfLength;i+)a0i=db->pfi.pageId;a1i=db->pfi.stayTime;int t,h;for(i = 1; i<db->pfLength;i+)for(int j=0;j<db->pfLength-i;j+)if(a1j<a1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; i<db->pfLength;i+)db->pfLogicRuleri=a0i;for(i = 0; i<db->pfLength;i+)if(db->pfi.pageId=db->pfLogicRuler0)db->pfi.replace=true;2.2 LRU算法class LRU:public Method/LRU算法private:public:void setpfLogicRuler(Data *db)int *a2;a0=new intdb->pfLength;a1=new intdb->pfLength;for(int i = 0; i<db->pfLength;i+)a0i=db->pfi.pageId;a1i=db->pfi.unvisitedCount;int t,h;for(i = 1; i<db->pfLength;i+)for(int j=0;j<db->pfLength-i;j+)if(a1j<a1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; i<db->pfLength;i+)db->pfLogicRuleri=a0i;for(i = 0; i<db->pfLength;i+)if(db->pfi.pageId=db->pfLogicRuler0)db->pfi.replace=true;2.3 OPT算法class OPT:public Method/OPT算法private:public:void setpfLogicRuler(Data *db,int site)for(int i=0;i<db->pfLength;i+)if(db->pfi.pageId!=-1)db->pfi.nextsite=db->pLength+1;elsedb->pfi.nextsite=db->pLength+2;for(int j=site; j<db->pLength;j+)if(db->pfi.pageId=db->pj.id)db->pfi.nextsite=j+1;break;int *a2;a0=new intdb->pfLength;a1=new intdb->pfLength;for( i = 0; i<db->pfLength;i+)a0i=db->pfi.pageId;a1i=db->pfi.nextsite;int t,h;for(i = 1; i<db->pfLength;i+)for(int j=0;j<db->pfLength-i;j+)if(a1j<a1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; i<db->pfLength;i+)db->pfLogicRuleri=a0i;for(i = 0; i<db->pfLength;i+)if(db->pfi.pageId=db->pfLogicRuler0)db->pfi.replace=true;break;3.功能模块设计class Control/选择所需算法struct Data/基本数据构成struct Page/页结构struct PageFrame/页框结构class Display/输出class FIFO:public Method/FIFO算法class LRU:public Method/LRU算法class OPT:public Method/OPT算法class Method/方法类void main() /主函数八、 实验运行结果：1.选择OPT算法实现：2.选择FIFO算法实现3.选择LRU算法实现九、实验心得：通过此次的实验,我更加了解了全局替换策略,了解到先进先出页面替换算法总是淘汰最先调入主存的页面,淘汰在主存中驻留时间最长的页面。了解到最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页。在整体上加深了我对虚拟存储管理的理解，构件了一个系统的存储管理的体系。当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。附录：源代码（部分）#include<iostream>using namespace std;struct PageFrame/页框结构int id;/页框号int pageId;/驻留的页号int visitedCount;/驻留页计数器，访问加1int unvisitedCount;/最近访问，访问清零，未访问加1bool replace;/将被淘汰为trueint stayTime;/驻留时间计数int nextsite;struct Page/页结构int id;/页号struct Data/基本数据构成PageFrame *pf;/页框指针，用于指定个数页框申请int pfLength;/页框个数Page *p;/页指针，用于指定个数页申请int pLength;/页个数int *pfLogicRuler;/逻辑标尺，用于记录淘汰序列int pageLackCount;/缺页计数器;class Methodprivate:public:Method()bool findPage(Data *db,int pid)bool flag=false;for(int i=0;i<db->pfLength;i+)if(db->pfi.pageId=pid)db->pfi.visitedCount+;db->pfi.unvisitedCount=1;db->pfi.replace=false;flag=true;elsedb->pfi.unvisitedCount+;db->pfi.stayTime+;return flag;int replace(Data *db,int pfid,int pid)int p;p=db->pfpfid.pageId;db->pfpfid.pageId=pid;db->pfpfid.replace=false;db->pfpfid.unvisitedCount=1;db->pfpfid.visitedCount=1;db->pfpfid.stayTime=1;db->pageLackCount+;return p;int longestTime(Data *db)int lt,pfnum;pfnum=db->pf0.id;lt=db->pf0.stayTime;for(int i=1; i<db->pfLength;i+)if(lt<db->pfi.stayTime)lt=db->pfi.stayTime;pfnum=db->pfi.id;return pfnum;int mostUnvisited(Data *db)int mu=0;mu=db->pf0.unvisitedCount;for(int i=0;i<db->pfLength;i+)if(mu>db->pfi.unvisitedCount)mu=db->pfi.visitedCount;return mu;void setpfLogicRuler()int getDiePF(Data *db)for(int i=0;i<db->pfLength;i+)if(db->pfi.replace=true)return db->pfi.id;class OPT:public Methodprivate:public:void setpfLogicRuler(Data *db,int site)for(int i=0;i<db->pfLength;i+)if(db->pfi.pageId!=-1)db->pfi.nextsite=db->pLength+1;elsedb->pfi.nextsite=db->pLength+2;for(int j=site; j<db->pLength;j+)if(db->pfi.pageId=db->pj.id)db->pfi.nextsite=j+1;break;int *a2;a0=new intdb->pfLength;a1=new intdb->pfLength;for( i = 0; i<db->pfLength;i+)a0i=db->pfi.pageId;a1i=db->pfi.nextsite;int t,h;for(i = 1; i<db->pfLength;i+)for(int j=0;j<db->pfLength-i;j+)if(a1j<a1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; i<db->pfLength;i+)db->pfLogicRuleri=a0i;for(i = 0; i<db->pfLength;i+)if(db->pfi.pageId=db->pfLogicRuler0)db->pfi.replace=true;break;class FIFO:public Methodprivate:public:void setpfLogicRuler(Data *db)int *a2;a0=new intdb->pfLength;a1=new intdb->pfLength;for(int i = 0; i<db->pfLength;i+)a0i=db->pfi.pageId;a1i=db->pfi.stayTime;int t,h;for(i = 1; i<db->pfLength;i+)for(int j=0;j<db->pfLength-i;j+)if(a1j<a1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; i<db->pfLength;i+)db->pfLogicRuleri=a0i;for(i = 0; i<db->pfLength;i+)if(db->pfi.pageId=db->pfLogicRuler0)db->pfi.replace=true;class LRU:public Methodprivate:public:void setpfLogicRuler(Data *db)int *a2;a0=new intdb->pfLength;a1=new intdb->pfLength;for(int i = 0; i<db->pfLength;i+)a0i=db->pfi.pageId;a1i=db->pfi.unvisitedCount;int t,h;for(i = 1; i<db->pfLength;i+)for(int j=0;j<db->pfLength-i;j+)if(a1j<a1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; i<db->pfLength;i+)db->pfLogicRuleri=a0i;for(i = 0; i<db->pfLength;i+)if(db->pfi.pageId=db->pfLogicRuler0)db->pfi.replace=true;class Controlprivate:public:OPT opt;FIFO fifo;LRU lru;Control();class SetBaseInfoprivate:public:SetBaseInfo()void setPageFrame(Data *db)for(int i=0;i<db->pfLength;i+)db->pfi.id=i;db->pfi.pageId=-1;db->pfi.replace=false;db->pfi.stayTime=1;db->pfi.unvisitedCount=1;db->pfi.visitedCount=1;db->pfLogicRuleri=-1;db->pfi.nextsite=db->pLength+2;void setPage(Data *db)int pid;cout<<"设置页面访问顺序.n"for(int i=0;i<db->pLength;i+)cout<<"输入第"<<i<<"个页号: "cin>>pid;db->pi.id=pid;cout<<"设置页面访问顺序完毕n"class Displayprivate:public:Display()void displayPageList(Data*db)cout<<"页表顺序: "for(int i=0;i<db->pLength;i+)cout<<db->pi.id<<" "cout<<endl;void displayLogicRuler(Data*db)cout<<"淘汰序列: "for(int i=0;i<db->pfLength;i+)if(db->pfLogicRuleri=-1)continue;cout<<db->pfLogicRuleri<<" "cout<<endl;void displayPageLack(Data*db)cout<<"缺页数: "<<db->pageLackCount;cout<<" 缺页率: "<<db->pageLackCount/(1.0*db->pLength);cout<<endl;void displayPageFrame(Data*db)cout<<"页框"<<" "<<"页面 "<<"须淘汰 "<<"驻留时间 "<<"最少访问 "<<"最多访问 下一次出现位置n"for(int i=0;i<db->pfLength;i+)cout<<" "cout<<db->pfi.id<<" "if(db->pfi.pageId=-1)cout<<" "elsecout<<db->pfi.pageId<<" "cout<<db->pfi.replace<<" "cout<<db->pfi.stayTime<<" "cout<<db->pfi.unvisitedCount<<" "cout<<db->pfi.visitedCount<<" "if(db->pfi.nextsite>db->pLength)elsecout<<db->pfi.nextsite;cout<<endl;void main()cout<<"-页面调度算法模拟-n"cout<<"-预置信息-n"int choice=1;Data *db;db=new Data;int plength=9;cout<<"输入页表长度:n"cin>>plength;int pflength=3;cout<<"输入页框长度:n"cin>>pflength;db->pLength=plength;db->pfLength=pflength;db->p=new Pageplength;db->pf=new PageFramepflength;db->pageLackCount=0;db->pfLogicRuler=new intpflength;SetBaseInfo setBaseInfo;setBaseInfo.setPage(db);setBaseInfo.setPageFrame(db);Display display;Control control;cout<<"n选择页面调度算法n"cout<<" 1. 最佳页面替换算法(OPT)n"cout<<" 2. 先进先出页面替换算法(FIFO)n"cout<<" 3. 最近最少使用页面替换算法(LRU)n"cout<<" 0. 退出(exit)n"cin>>choice;switch(choice)case 1:control.opt.setpfLogicRuler(db,-3);display.displayLogicRuler(db);for(int i = 0; i< db->pLength;i+)if(!control.opt.findPage(db,db->pi.id)int lt=control.opt.getDiePF(db);control.opt.replace(db,lt,db->pi.id);control.opt.setpfLogicRuler(db,i);display.displayPageFrame(db);display.displayLogicRuler(db);display.displayPageLack(db);break;case 2:control.fifo.setpfLogicRuler(db);display.displayLogicRuler(db);for(int i = 0; i< db->pLength;i+)if(!control.fifo.findPage(db,db->pi.id)int lt=control.fifo.getDiePF(db);control.fifo.replace(db,lt,db->pi.id);display.displayPageFrame(db);control.fifo.setpfLogicRuler(db);display.displayLogicRuler(db);display.displayPageLack(db);break;case 3:control.lru.setpfLogicRuler(db);for(int i = 0; i< db->pLength;i+)if(!control.lru.findPage(db,db->pi.id)int lt=control.lru.getDiePF(db);control.lru.replace(db,lt,db->pi.id);control.lru.setpfLogicRuler(db);display.displayPageFrame(db);display.displayLogicRuler(db);display.displayPageLack(db);break;case 0:break; default:cout<<"输入错误! 退出n"break;cout<<"n页面调度算法模拟结束n"cin>>choice;