页面置换算法(操作系统试验).doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date页面置换算法(操作系统试验)页面置换算法(操作系统试验)实验4 页面置换算法（2学时）一、实验目的 通过实验加强对虚拟存储管理中页面置换算法的理解和掌握。二、实验内容 编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法。三、实验要求1、任意给出一组页面访问顺序（如页面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。2、分配给该作业一定的物理块（如3块、4块等）。3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。4、每访问一个页面均需给出内存中的内容（内存中的页面号），若有淘汰还需给出淘汰的页面号。5、通过给出特殊的页面访问顺序，分配不同的物理块，利用FIFO算法计算其缺页率，进一步理解Belady现象。6、（附加）实现CLOCK置换算法，修改位可在确定页面号时直接任意给出。代码部分：#include <stdlib.h> #include <iostream.h>#include <time.h> void rand(int n,int p)/这函数是产生n个110的随机数放到p数组里面 int START=1; int END=10; int v; int i;int a; srand(time(NULL); for(i=0; i<n; i+) v=rand()%(END-START+1)+START; pi=v; cout<<v; struct Pro int num,time; /num存放具体的内容，time在不同算法里面有不同的意义; /它们是物理块和页面的数据结构int Input(int m,int N,Pro *p,Pro *page)/完成p数组和page的初始化工作 /p数组是存放页面的空间，m是页面的长度 /page是可以使用的物理块，N是物理块的大小 cout<<endl<<"请输入各页面号"<<endl; int *p2=new intm; rand(m,p2); for(int i=0;i<m;i+) pi.num=p2i; pi.time=0; for(i=0;i<N;i+)/初试化页面基本情况 pagei.num=0; pagei.time=N+2-i; return m; int Search(int e,Pro *page,int N)/算法里面都要用到它。/它是找e页是否在page物理块中，N是物理块的大小 for(int i=0;i<N;i+) if(e=pagei.num) return i;/如果找到，就返回在物理块中的位置给Search return -1;/找不到，就返回-1 int Max(Pro *page,int N)/LRU算法用到的/找出在page块中，time最大的值和位置，同时位置返回/time最大，就代表了最久没被使用的数 int e=page0.time,i=0; int k=0; while(i<N)/找出离现在时间最长的页面 if(e<pagei.time) k=i; i+; return k; int Compfu(Pro *page,int i,int t,Pro p,int m)/OPT算法用到的/找出如果paget要等于p，并且zai pipm这个区间内，走的次数，最大的数 int count=0;/count是保存走的步数 for(int j=i;j<m;j+) if(paget.num=pj.num )break;/如果相等，跳出循环 else count+;/不等就步数加1 return count; int Min(Pro page,int N)/LFU算法用到的 /page是可以使用的物理块，N是物理块的大小 /找到出现次数最小的的数，并把位置返回 int k=0; int min=page0.time; for(int i=0;i<N;i+) if(min>pagei.time) k=i; return k; void FIFO(Pro p,Pro page,int m,int N)/p数组是存放页面的空间，m是页面的长度 /page是可以使用的物理块，N是物理块的大小 float n=0;/n用来保存缺页的次数 int i=0;/i是循环变量，它是表示走到页面的位置。 int t=0;/t是用来表示物理块走到的位置 cout<<"页面置换情况: "<<endl; for(i=0;i<m;i+) if(Search(pi.num,page,N)>=0) continue;/找到相同的页面，就跳到下一次循环，不做处理。 else /在找不到的时候，通过t=t%N,求出这次来替换物理块的位置 t=t%N; n+;/缺页数加1 paget.num=pi.num; t+;/位置加1 cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<" 命中率："<<1-n/m<<endl; void LFU(Pro p,Pro page,int m,int N)/p数组是存放页面的空间，m是页面的长度 /page是可以使用的物理块，N是物理块的大小， float n=0; int i=0; int t=0; for(i=0;i<N;i+) pagei.time=0; cout<<"页面置换情况: "<<endl; for(i=0;i<m;i+) if(Search(pi.num,page,N)>=0) pagei.time+;/找到相同的页面，time加1 continue;/ else /找出使用最少的页面进行调换 t=Min(page,N);/找到出现次数最小的的数，并把位置返回t paget.num=pi.num; paget.time=0;/该页time清零 n+;/缺页数加1 cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<" 命中率："<<1-n/m<<endl; void OPT(Pro p,Pro page,int m,int N)/p数组是存放页面的空间，m是页面的长度 /page是可以使用的物理块，N是物理块的大小 float n=0;/n用来保存缺页的次数 int i=0;/i是循环变量，它是表示走到页面的位置。 int t=0; /t是用来表示物理块走到的位置 while(i<m) if(Search(pi.num,page,N)>=0) i+;/如果找到了，就不做处理。 else/如果找不到 int temp=0,cn;/cn用来保存离后面最远的数 for(t=0;t<N;t+)/对物理块里面的每个数进行遍历 if(temp<Compfu(page,i,t,p,m)/temp用来保存 /paget= pipm这个区间内，走的次数，最大的数 temp=Compfu(page,i,t,p,m); cn=t; pagecn=pi;/把当前的值放要发生要走最远的数，也就最不可能最近出现的数 n=n+1;/缺页数加1 i+;/跳到下一次循环 cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<" 命中率："<<1-n/m<<endl; void LRU(Pro p,Pro page,int m,int N)/p数组是存放页面的空间，m是页面的长度 /page是可以使用的物理块，N是物理块的大小 float n=0;/n用来保存缺页的次数 int i=0;/i是循环变量，它是表示走到页面的位置。 int t=0; /t是用来表示物理块走到的位置 cout<<"页面置换情况: "<<endl; while(i<m) int k; k=t=Search(pi.num,page,N); if(t>=0) paget.time=0;/如果找到，就要把当前的paget.time次数 /清零 else/找不到的时候，发生缺页 n+; /缺页数加1 t=Max(page,N);/找出page物理块里面，最久没被时候的数 /同时把最久没被时候的数在物理块里的位置传给t paget.num=pi.num;/最久没被使用的是被现在的数代替 paget.time=0;/同时清零 for(int j=0;j<N;j+)/把缺页以外的数，把它没被使用的次数加1 if(j=t) continue; paget.time+; i+;/跳到下一次循环 cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<" 命中率："<<1-n/m<<endl; void main() int m=0,t=0,N=0; cout<<"请输入实际页数：" cin>>m; Pro *p=new Prom;/p是用来放页面的地方 cout<<"可用内存页面数"<<endl; cin>>N; Pro *page=new ProN;/page是放物理块的地方 char c; float n=0; Input(m,N,p,page);/m是页面的总长，N是物理块的长度 do cout<<"f:FIFO页面置换"<<endl; cout<<"l:LRU页面置换"<<endl; cout<<"o:OPT页面置换"<<endl; cout<<"u:LFU页面置换"<<endl; cout<<"按其它键结束"<<endl; cin>>c; if(c='f')/FIFO页面置换 FIFO(p,page,m,N); if(c='l')/LRU页面置换 LRU(p,page,m,N); if(c='o')/OPT页面置换 OPT(p,page,m,N); if(c='u')/OPT页面置换 LFU(p,page,m,N); while(c='f'|c='l'|c='o'|c='u'); 0805114下次预告(敬请期待)：实验5 设备管理（2学时）一、实验目的理解设备管理的概念和任务，掌握独占设备的分配、回收等主要算法的原理并编程实现。二、实验内容编写程序实现对独占设备的分配与回收的模拟。三、实验要求1、实现设备分配、回收、显示系统中设备信息的功能。2、通过设备类表和设备表记录系统中设备信息、以便进行设备分配。3、设备类表记录系统中全部设备的情况，每个设备类占一个表目，设备类表的数据结构如表1所示。设备类拥有设备数量可分配设备数量设备起始地址图1 设备类表4、为每一个设备配置一张设备控制表，用于记录本设备的情况。设备控制表的数据结构如图2所示。绝对号设备状态（好/坏）是否分配（是/否）占有作业名相对号图2 设备控制表4、程序中建立分配设备和回收设备函数。5、设系统有3类设备，每类设备的设备数分别为2、3、4。6、要求键盘输入作业名、作业所需设备类和设备相对号。-