先进先出调度算法和最近最少用置换调度算法.doc
Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date先进先出调度算法和最近最少用置换调度算法江西师范大学计算机信息工程学院学生实验报告江西师范大学计算机信息工程学院学生实验报告专业 计算机科学与技术 姓名李洋_ 学号0908061086 日期2011/5/17课程名称计算机操作系统实验室名称X4313实验名称先进先出调度算法指导教师朱明华成绩1.实验目的 了解的先进先出调度算法的调度原理，再用数据结构和c语言，以程序的形式来实现该算法 2.实验原理和内容 先进先出调度算法的原理是把一个进程已调入内存的页面，按照先后测序链接成一个队列，并设置一个指针，使他总是指向最老的页面。3.实验步骤（1）在c-free中定义函数（2）根据原理进行编写（3）运行并验证 源程序：#include <iostream>#include <iomanip>/使用setw()时用到的头文件#include <stdio.h>#include <stdlib.h>#include <conio.h> /使用getchar()时用到的头文件using namespace std;#define Max 30/某进程调入内存中的最大页面数#define Size 10/系统为某进程分配的最大物理块数void Init(int Block,int m)/初始化物理块int i;for(i=0;i<m;i+)Blocki=-1;void creat(int Page,int n) /输入页面串引用号int i;for(i=0;i<n;i+)cin>>Pagei;void FIFO(int Page,int Block,int n,int m)/max_stay:比较当前内存中页面驻留的最久时间,count:统计页面置换次数/get:某物理块是否等待驻入新页面(-1:否)/flag:标记当前序号页面是否已驻入内存(-1:否)/block_num:驻留内存时间最长的页面所在的物理块序号/time标记对应序号的物理块中页面驻留时间int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int timeSize;for(i=0;i<m;i+)/初始化timetimei=0;for(i=0;i<n;i+)for(j=0;j<m;j+)/有空闲物理块时，页面直接驻入内存空闲块if(Blockj=-1)get=j;/物理块j即将(/等待)驻入新页面break;for(j=0;j<m;j+)/查找序号相同的页面if(Blockj=Pagei)/物理块j中页面与当前期望调入内存的页面相同flag=j;break;for(j=0;j<m;j+)/找到驻留内存时间最久的页面置换出if(timej>max_stay)max_stay=timej;block_num=j; /block_num标记当前序号物理块中页面驻留时间最久if(flag=-1)/不存在相同页面if(get!=-1)/物理块即将(/等待)驻入新页面Blockget=Pagei;/存入页面timeget=0;/当前物理块重新计时for(j=0;j<=get;j+)/已驻入页面的驻留时间加1timej+;get=-1;else/页面调度置换，序号block_num的物理块是驻留时间最久的Blockblock_num=Pagei;timeblock_num=0;for(j=0;j<Size;j+)timej+;block_num=-1;max_stay=0;count+;else/待调入页面与序号flag的物理块中页面相同for(j=0;j<m;j+)timej+;flag=-1;for(j=0;j<m;j+)/输出物理块中的页面驻入情况cout<<setw(3)<<Blockj;cout<<endl;if(n>m)count=count+m-3;cout<<"缺页中断次数为:"<<count<<endl;void main()int n,m,PageMax,BlockSize;cout<<"*先进先出FIFO页面置换算法*"<<endl;cout<<"-"<<endl;cout<<"*(默认:-1表示物理块空闲)*"<<endl;cout<<endl<<"请输入系统为进程分配的物理块数(m<=10):"while(1)cin>>m; if(m>Size|m<1) cout<<"警告：输入的数据错误！"<<endl; cout<<"请重新输入物理块数:" else break;Init(Block,m);cout<<"请输入总页面数(n<=30):"cin>>n;cout<<"n请输入页面号引用串:"creat(Page,n);cout<<"FIFO算法过程如下:"<<endl;FIFO(Page,Block,n,m);getchar();/直接执行exe文件时做停留查看结果之用getchar();江西师范大学计算机信息工程学院学生实验报告专业 计算机科学与技术 姓名李洋_ 学号0908061086 日期2011/5/18课程名称计算机操作系统实验室名称X4313实验名称最近最少用置换调度算法指导教师朱明华成绩1.实验目的 了解的最近最少用置换调度算法的调度原理，再用数据结构和c语言，以程序的形式来实现该算法 2.实验原理和内容在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中，从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会在访问的页面调出。3.实验步骤（1）在c-free中定义函数（2）根据原理进行编写（3）运行并验证源代码：#include<stdio.h>#include<iostream>#define num 20#define max 65535typedef struct PBint page;/当前页面号int seq_num;/对于页面最近一次被访问的序列号int fg;Pb;int k;int seek(int seq,int i,Pb a,int k);int test1(int seq_i,int Pn,Pb a);int test2(Pb a,int Pn);int LRU(int seq,int i,int Pn,Pb pb);/页块中的页面的最近最久未使用位置int seek(int seq,int i,Pb a,int k)int flag=0;for(int j=i-1;j>=0;j-)if(ak.page=seqj)flag=1;return j;break;if(flag=0)return -1;/检测当前页面在不在内存中，如果在内存中，返回所在页块号；如果不在，返回-1int test1(int seq_i,int Pn,Pb a)int flag=0;for(int j=0;j<Pn;j+)if(aj.page=seq_i)flag=1;return j;break;if(flag=0)return -1;/检测有没有空页块，如果有空页块，返回页块号；如果没有，返回-1int test2(Pb a,int Pn)int flag=0;for(int j=0;j<Pn;j+)if(aj.page=-1)flag=1;return j;break;if(flag=0)return -1; int LRU(int seq,int i,int Pn,Pb pb)int temp20;int j;for(k=0;k<Pn;k+)tempk=seek(seq,i,pb,k);pbk.fg=seek(seq,i,pb,k); for(k=1;k<Pn;k+)int lastX=1;int tem;for(j=0;j<Pn-k;j+)if(tempj>tempj+1)tem=tempj;tempj=tempj+1;tempj+1=tem;lastX=0;if(lastX=1) break;for(k=0;k<Pn;k+)if(pbk.fg=temp0)printf("%d ",pbk.page);return k;break;void PCB()Pb pb10;/最多只允许0-9共10个页块号int Pn;int an=0;int seq100;int i;float ar;printf("请输入页块数Pn：n");scanf("%d",&Pn);printf("请输入%d位长的页面访问序列seq%d：n",num,num);for(i=0;i<num;i+)scanf("%d",&seqi);for(i=0;i<10;i+)pbi.page=-1;pbi.seq_num=-1;pbi.fg=max;printf("淘汰页面号依次为：n");for(i=0;i<num;i+)/做20次int a,b;a=test1(seqi,Pn,pb);b=test2(pb,Pn);if(a=-1)/不在内存中if(b!=-1)/没满pbb.page=seqi;pbb.seq_num=i;an+;else/满了k=LRU(seq,i,Pn,pb);pbk.page=seqi; pbk.seq_num=i; an+;ar=(float)an/(float)num;printf("n缺页次数为：%dn缺页率为%fn",an,ar);void main()PCB();-
