页面置换算法实验(共10页).doc
精选优质文档-倾情为你奉上操作系统原理实验报告实验三 页面置换算法实验专业：计算机科学与技术学号：姓名：简郸实验日期：2010-5-22一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验要求设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1最佳淘汰算法（OPT）2先进先出的算法（FIFO）3最近最久未使用算法（LRU）三、实验方法内容1. 算法设计思路1假设分给一作业的内存块数为 4 ，每条指令占一个存储单元，每个页面中可存放 10 条指令；2设计一个程序，模拟一作业的执行过程。设该作业共有 160 条指令，即它的地址空间为16页，最初作业的所有页面都还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果 4 个内存块中均已装入该作业的虚页面，则需进行页面置换；在所有 160条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3 作业中指令的访问次序要求按下述原则生成：具体的实施办法是： (1)在0，159之间随机选取一条起始执行指令，其序号为 m ； (2)顺序执行两条指令，即序号为 m+1、m+2 的指令； (3)通过随机数，跳转到前地址部分0，m-1中的某条指令处，其序号为 m1 ； (4)顺序执行两条指令，即序号为 m1+1 ，m1+2的指令； (5)通过随机数，跳转到后地址部分 m1+3，159 中的某条指令处，其序号为 m2 ； (6)顺序执行两条指令，即序号为 m2+1，m2+2 的指令；若m2+2>159只执行一条指令；(7)重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部160条指令2. 算法流程图3. 算法中用到的数据结构4. 主要的常量变量5. 主要模块四、实验代码#include<stdlib.h>#include<iostream.h>#include<time.h> #include<stdio.h>#define total_instruction 200 /*指令流长*/#define M 16 /*实际页数*/#define N 4 /可用页面数struct Proint num,time;int atotal_instruction;int pageN;void Input(Pro ptotal_instruction) int m,i,m1,m2; srand( (unsigned int )time(NULL); m=rand( )%160; / for(i=0;i<total_instruction;) /*产生指令队列*/ if(m<0|m>159) printf("When i=%d,Error,m=%dn",i,m); exit(0); ai=m; /*任选一指令访问点m*/ ai+1=ai+1; ai+2=ai+2; /*顺序执行两条指令*/ int m1=rand( )%m; /*执行前地址指令m1 */ ai+3=m1; ai+4=m1+1; ai+5=m1 + 2;/*顺序执行两条指令*/ / s=(158-ai+5)*rand( )/32767/32767/2+ai+5+2; m2 = rand()%(157-m1)+m1+3; ai+6=m2; if( (m2+2) > 159 ) ai+7 = m2+1; i +=8; else ai+7 = m2+1; ai+8 = m2+2; i = i+9; m = rand()%m2; for (i=0;i<total_instruction;i+) /*将指令序列变换成页地址流*/ pi.num=ai/10; pi.time = 0; void print(Pro *page1)/打印当前的页面 Pro *page=new ProN; page=page1; for(int i=0;i<N;i+) cout<<pagei.num<<" " cout<<endl;int Search(int e,Pro *page1 ) Pro *page=new ProN; page=page1; for(int i=0;i<N;i+)if(e=pagei.num)return i; return -1;int Max(Pro *page1) Pro *page=new ProN; page=page1; int e=page0.time,i=0; while(i<N)/找出离现在时间最长的页面 if(e<pagei.time)e=pagei.time; i+; for( i=0;i<N;i+)if(e=pagei.time)return i; return -1;int Compfu(Pro *page1,int i,int t,Pro pM) Pro *page=new ProN; page=page1; int count=0; for(int j=i;j<M;j+) if(paget.num=pj.num )break; else count+; return count;int main() Pro ptotal_instruction; Pro *page=new ProN; char c; int t=0; float n=0; Input(p); do for(int i=0;i<N;i+)/初试化页面基本情况 pagei.num=0; pagei.time=2-i; i=0; cout<<"f:FIFO页面置换"<<endl; cout<<"l:LRU页面置换"<<endl; cout<<"o:OPT页面置换"<<endl; cout<<"按其它键结束"<<endl; cin>>c; if(c='f')/FIFO页面置换 n=0; cout<<"页面置换情况: "<<endl; while( i< total_instruction) if(Search(pi.num,page)>=0) i+;/找到相同的页面 else if(t=N)t=0; else n+;/ paget.num=pi.num; print(page); t+; cout<<"缺页次数："<<n<<" 缺页率："<<n/total_instruction<<endl; if(c='l')/LRU页面置换 n=0; cout<<"页面置换情况: "<<endl; while(i<total_instruction) int k; k=t=Search(pi.num,page); if(t>=0) paget.time=0; else n+; t=Max(page); paget.num=pi.num; paget.time=0; if(t=0)paget+1.time+;paget+2.time+; if(t=1)page2.time+;page0.time+; if(t=2)page1.time+;page0.time+; if(k=-1) print(page); i+; cout<<"缺页次数："<<n<<" 缺页率："<<n/total_instruction<<endl; if(c='o')/OPT页面置换 n=0; while(i<total_instruction) if(Search(pi.num,page)>=0)i+; else int temp=0,cn; for(t=0;t<N;t+) if(temp<Compfu(page,i,t,p) temp=Compfu(page,i,t,p); cn=t; pagecn=pi; n+; print(page); i+; cout<<"缺页次数："<<n<<" 缺页率："<<n/total_instruction<<endl; while(c='f'|c='l'|c='o'); return 0;五、实验结果1. 执行结果专心-专注-专业
