操作系统页面调度算法

1、实验报告参考格式（实验一）实验项目名称：操作系统页面调度算法 教师评分：一、实验目的和要求目的：对操作系统中使用的页面调度算法进行设计。要求：对教材中所讲述的几种页面调度算法进行深入的分析，通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。二、实验环境1、pc兼容机2、windows2000/xp系统三、实验内容1、设计两个程序模拟实现一个作业在内存中执行的页面置换，并计算缺页中断次数。3、编制两种页面置换算法：1）fifo页面置换算法；2）lru页面置换算法四、实验原理：1、fifo页面置换算法：总是选择在内存中驻留时间最长的一页将其淘汰

2、。2、lru页面置换算法：选择最近一段时间内最长时间没有被访问过的页面予以淘汰。五、实验操作过程及实验结果记录1、fifo页面置换算法：此算法的思想是按照作业到来的顺序进行处理，以下是源代码，代码已经调试，可上机运行。#include <stdio.h>#define m 4/*m为系统分配给作业的主存中的页面数*/#define n 9int count=0;int m=0;int bef_arrfull(int am,int bn,int cn)/a中未满之前的处理int k;printf("发生缺页的面号分别为：");printf("%d &qu

3、ot;,b0);for(int n=0;n<m;n+) an=0;/初始化 a0=b0;count+;int j,ii=0;for(j=1;j<n;j+)int f=0;for( k=0;k<=ii;k+)if(bj=ak) f=1;break;/包含在中间找到，在末尾找到if(!f)/未找到值发生中断printf("%d ",bj);/打印缺页的页号count+;a+ii=bj;if(ii=3) break;/内存中的页面数已满 return j;void after_arrfull(int am,int bn,int cn,int j) /a中页面数满

4、了之后的处理 int i,flag; int k; for(i=j+1;i<n;i+) flag=0; for(k=0;k<m;k+)if(ak=bi)flag=1; if(flag=0) cm=a0; m+; for(k=0;k<m-1;k+) ak=ak+1; am-1=bi; count+; printf("%3d,",bi); void main()int am;/*定义内存页面数*/int bn;/*定义总页面数*/ int cn;/*定义被淘汰的页面号*/int i;int n;printf("请输入作业序号:n");for

5、(i=0;i<n;i+)/*输入作业依次要访问的页号*/scanf("%d",&bi); n=bef_arrfull(a,b,c);after_arrfull(a,b,c,n);/a中页面数满了之后的处理printf("n发生缺页的次数=%dn",count);printf("n缺页中断率=%.2f%n",(float)count/n*100);printf("n驻留内存的页号分别为：");for(i=0;i<m;i+)printf("%3d,",ai); printf(&q

6、uot;n被淘汰的页号分别为：");for(i=0;i<m;i+) printf("%3d,",ci);测试：请输入作业序号(9个作业):2 2 2 3 4 5 6 7 8发生缺页的面号分别为：2 3 4 5 6, 7, 8,发生缺页的次数=7缺页中断率=77.78%驻留内存的页号分别为： 5, 6, 7, 8,被淘汰的页号分别为： 2, 3, 4,press any key to continue测试：请输入作业序号(9个作业):3 4 3 4 5 6 7 8 9发生缺页的面号分别为：3 4 5 6 7, 8, 9,发生缺页的次数=7缺页中断率=77.78

7、%驻留内存的页号分别为： 6, 7, 8, 9,被淘汰的页号分别为： 3, 4, 5,press any key to continue2、lru算法：此算法的思想是为每一个页面分配一个使用频度falg，用以表明该页号的使用频度，在发生缺页中断时，利用循环来遍历数组a的每个页面的使用频度，找到最小的频度所对应的页面号，并把他的下标值和标号分别存入结构体min的ye_hao和falg中。以下是详细的实现过程，代码已经调试，可直接运行。#include <stdio.h>#define m 4 /*m为在主存中的页面数*/#define n 9struct yeint ye_hao;i

8、nt falg; /id,标识使用的频度;int count=0;struct ye min; /内存中使用频度最低的页面/内存页面数未满之前int bfor_arryfull(struct ye bn,struct ye am,int cn) int i;printf("请输入作业序号(9个页面并用空格隔开):n");for(i=0;i<n;i+) scanf("%d",&bi.ye_hao); printf("发生缺页的面号分别为：n"); a0.ye_hao=b0.ye_hao;a0.falg=0;b0.falg=

9、0;printf("%d ",b0.ye_hao);int ii=0;int k,j;count+;for(j=1;j<n;j+)int flag=0;for( k=0;k<=ii;k+)if(bj.ye_hao=ak.ye_hao) flag=1;break;/包含在中间找到，在末尾找到if(!flag)/未找到值发生中断printf("%d ",bj.ye_hao);/打印缺页的页号count+;a+ii.ye_hao=bj.ye_hao;aii.falg=count;bj.falg=count;if(ii=3) break;/内存中的页

10、面数已满 return j;/j表示内存页面数满之后,下一个是第几个进入内存/内存页面数已满之后void after_arryfull(struct ye bn,struct ye am,int j,int cn) int i;int temp=0;for(int p=j+1;p<n;p+) for(i=0;i<m;+i)if(bp.ye_hao=ai.ye_hao)ai.falg=bp-1.falg+1;bp.falg=ai.falg;break;if(i=4)/内存中不存在，发生缺页中断printf("%d ",bp.ye_hao);min.falg=a0.

11、falg;min.ye_hao=0;/存储最近最久未使用的下标号for(int n=1;n<m;n+)/找到最不经常使用if(an.falg<min.falg) min.falg=an.falg;min.ye_hao=n;ctemp+=amin.ye_hao.ye_hao;amin.ye_hao.ye_hao=bp.ye_hao;amin.ye_hao.falg=bp-1.falg+1;bp.falg=amin.ye_hao.falg;count+; void main()struct ye am; /定义内存页面数struct ye bn; /页面序列 int cn;/定义被淘汰

12、的页面号int j,i;j=bfor_arryfull(b,a,c);/for(k=0;k<m;k+) printf("%d ",ak.ye_hao); after_arryfull(b,a,j,c);printf("n发生缺页的次数=%dn",count); printf("n缺页中断率=%.2f%n",(float)count/n*100);printf("n驻留内存的页号分别为：");for(i=0;i<m;i+)printf("%d,",ai.ye_hao); printf("n被淘汰的页号分别为：");for(i=0;i<count-m;i+)printf("%3d,",ci); 测试： 输入 1 2 3 2 3 4 5 6 7 理论上分析可知在a满时，a数组中的元素应为1,2,3,4发生4次中断，在所有作业请求都进入时，驻留在a中的页面应为 5，6，7，4，被淘汰的页面号应为1，2，3，图示可以证明这一点。输入2，3，