操作系统课程设计lru页面置换算法.doc

操作系统课程设计lru页面置换算法

26
2020年4月19日
文档仅供参考，不当之处，请联系改正。

操作系统功能模拟设计实验

题 目： lru置换算法（C编写）
 学生姓名：    计号  
学  号：    
　 专  业：  网络工程     
　　 班  级：  11网络工程二班  

实验题目LRU页面调度算法处理缺页中断

一、 实验目的：
了解和掌握寄存器分配和内存分配的有关技术
二、 实验内容
（1）首先对LRU页面调度算法原理进行深刻的理解和掌握；
（2）选择一种熟悉的编程语言来实现对一组访问序列进行内部的cache更新；
（3）根据LRU页面调度算法算法的要求设计相应的数据结构，如：记录访问序列的数组、模拟内存cache的数组等等；
（4）显示每个访问数进入cache的操作并显示出每次访问后内存中序列的状态。
三、 实验环境
Windows系统，c语言
四、 实验主要步骤（包括使用的数据结构的说明）
1、 初始化及使用数据结构
开始的阶段，产生随机的访问序列，并用了结构体：
struct page{
int pageframe[10]; // 表示页表
int flag; //标记是否有页面置换
int length; //用来访问序列的长度
int page_count; //页框的数目
int page_serial[20]; //存取随机产生的访问序列组
int count; //用来标识页框是否被装满
int k; //用于记录访问页表的指针
int pagetime[10]; //用来记录页框里面的数被访问的过后到再一次被访问所经历的的时间
}p;
并初始化这些量;
void init(){ //初始化所有页表
int i;
p.flag=0;
for(i=0;i<10;i++){
p.pageframe[i]=-1;
p.pagetime[i]=0;
}
for(i=0;i<20;i++){
p.page_serial[i]=-1;
}
}

2、 LRU页面调度算法原理
LRU页面调度算法是对要访问cache的访问序列进行更新的，当页表还是空的时候，进来要访问的页如果页表里面有的话，就对它的访问记录加一，如果也表里面没有切页表么有填满，就像页表里面添加。如果在页表填满以后，再一次有也要访问的时候，在判断页表里面有没有要访问的页，如果没有则看页表里面的的序列哪一个页是最近最长时间都没有被访问的，就将此页给替换程现在要访问的页。

3、 创立访问的序列和页框
void create(){
int i,s;

printf("\n请输入页框数目:\n");
scanf("%d",&p.page_count);
printf("\n请输入要随机生成访问序列的长度:\n"); //自定义随机生成访问序列的长度
scanf("%d",&p.length);
srand(rand()); //初始化随机数队列的"种子"
s=((float) rand() / 32767) * 50 + p.length; // 随机产生页面序列长度

for(i=0;i<s;i++) //产生随机访问序列
{
p.page_serial[i]=((float) rand() / 32767) * 16 ; //随机数的大小在0-10之间

}
printf("\n\n\n\n");
printf("<<<<<<<<<<访问序列为>>>>>>>>>>>:\n");
for(i=0;i<p.length;i++)
{
printf("%d ",p.page_serial[i]);

}
printf("\n\n\n\n");
printf("********************************");
printf("\n\n\n");
}
4、 在cache中查找要访问的页
int findpage(int k,int count){ //在这里k用于接收从lru函数传来的访问序列的数值
int m=k;
int n=count;
int i;
int j; //用来做标记

for(i=0;i<p.page_count;i++){
if(p.pageframe[i]>=0){
p.pagetime[i]++;
}
if(p.pageframe[i]==m){
p.pagetime[i]--;
j=1;
}

else{
if(i==p.page_count)
j=0;
}

}
if(j==1)
{
if(p.count<=p.page_count-1)
{
p.flag=-3;
return -3; //在这里表示页框里有要访问的页,可是页框没有填满，不需要置换因此返回-3
}
else
{
p.flag=-1; //表示在此时也表里有要访问的页，可是此时页表也满了，可是也不缺页，因此用flag来表示不缺页
return -1;
}
}

else
{
if(p.count<=p.page_count-1)
{
p.flag=0;
return 0; //在这里表示没有访问到页表里面的页，可是页表没有别填满，但不需要置换因此返回0
}
else
{
p.flag=-2; //在这里p.flag=-2表示没有访问到页表，且页框需要被置换因此返回-2
return -2;
}
}

}
六、 显示内存中的序列
void displayinfo(){
int n;
printf("访问%3d : 内存<",p.page_serial[t]);

for(n=0;n<p.page_count;n++) // 页框信息
{
if (p.pageframe[n] >=0)
printf("%3d",p.pageframe[n]);
else
printf(" ");
}
printf(" >");
if(p.flag==-2||p.flag==0) //p.flag==-1表示也表里面有访问的页，可是页框没有 满，p.flag==-2表示页表里面没有要访问的页，可是页框也被填满了
{
printf(" ==>缺页 ");

}
printf("\n");
}

七、 此实验的执行程序图

开始

初始化

产生访问序列、并定义页框大小

进行序列访问

判断页框里是否有有要访问的页？

无

判断页框是否被填满
有
则在此页的访问等待次数上减一
否

是

把此页添加进也表里面
找到最长时间没有被访问的页，把此页给更新成新访问的页

结束
序列是否访问完

否 是

五、 设计不同实验数据，记录实验结果并分析。

六、 实验总结及体会
经过这次的实验，我对LRU页面置换算法有了更深的了解，LRU置换算法是理想性的算法，因为使用LRU置换算法要花费很大的系统开销，因此在实际系统中并不会直接采用.经过这个LRU页面缺页调度算法的设计，我觉得对这个算法的原理理解的更加的深刻，虽然在设计的过程中也遇到了很多问题，例如怎么去判定内存cache中的每个数在访问后怎么去标记她的时间问题，还有怎样去表示开始时的内存cache中的页表没有被填满的缺页和页表被填满时候的缺页状态。
七、 源程序清单及注释。（打印一份源程序并附上注释。）
#include<stdio.h>
#include<stdlib.h>

int t;
struct page{
int pageframe[10]; // 表示页表
int vpage;
int flag; //标记是否有页面置换
int length; //用来访问序列的长度
int page_count; //页框的数目
int page_serial[20]; //存取随机产生的访问序列组
int count; //用来标识页框是否被装满
int k; //用于记录访问页表的指针
int pagetime[10]; //用来记录页框里面的数被访问的过后到再一次被访问所经历的的时间
}p;

void init(){ //初始化所有页表
int i;
p.flag=0;
for(i=0;i<10;i++){
p.pageframe[i]=-1;
p.pagetime[i]=0;
}
for(i=0;i<20;i++){
p.page_serial[i]=-1;
}
}

void create(){
int i,s;

printf("\n请输入页框数目:\n");
scanf("%d",&p.page_count);
printf("\n请输入要随机生成访问序列的长度:\n"); //自定义随机生成访问序列的长度
scanf("%d",&p.length);
srand(rand()); //初始化随机数队列的"种子"
s=((float) rand() / 32767) * 50 + p.length; // 随机产生页面序列长度

for(i=0;i<s;i++) //产生随机访问序列
{
p.page_serial[i]=((float) rand() / 32767) * 16 ; //随机数的大小在0-10之间

}
printf("\n\n\n\n");
printf("<<<<<<<<<<访问序列为>>>>>>>>>>>:\n");
for(i=0;i<p.length;i++)
{
printf("%d ",p.page_serial[i]);

}
printf("\n\n\n\n");
printf("********************************");
printf("\n\n\n");
}

int findpage(int k,int count){ //在这里k用于接收从lru函数传来的访问序列的数值
int m=k;
int n=count;
int i;
int j; //用来做标记

for(i=0;i<p.page_count;i++){
if(p.pageframe[i]>=0){
p.pagetime[i]++;
}
if(p.pageframe[i]==m){
p.pagetime[i]--;
j=1;
}

else{
if(i==p.page_count)
j=0;
}

}
if(j==1)
{
if(p.count<=p.page_count-1)
{
p.flag=-3;
return -3; //在这里表示页框里有要访问的页,可是页框没有填满，不需要置换因此返回-3
}
else
{
p.flag=-1; //表示在此时也表里有要访问的页，可是此时页表也满了，可是也不缺页，因此用flag来表示不缺页
return -1;
}
}

else
{
if(p.count<=p.page_count-1)
{
p.flag=0;
return 0; //在这里表示没有访问到页表里面的页，可是页表没有别填满，但不需要置换因此返回0
}
else
{
p.flag=-2; //在这里p.flag=-2表示没有访问到页表，且页框需要被置换因此返回-2
return -2;
}
}

}

void displayinfo(){
int n;
printf("访问%3d : 内存<",p.page_serial[t]);

for(n=0;n<p.page_count;n++) // 页框信息
{
if (p.pageframe[n] >=0)
printf("%3d",p.pageframe[n]);
else
printf(" ");
}
printf(" >");
if(p.flag==-2||p.flag==0) //p.flag==-1表示也表里面有访问的页，可是页框没有满，p.flag==-2表示页表里面没有要访问的页，可是页框也被填满了
{
printf(" ==>缺页 ");

}
printf("\n");
}

void lru(){
int i;
int time=0;
int m; //用于接收findpage返回的标
int count1=0; //这个只是用来记录缺页的次数
p.k=0;
init();
create();
p.count=0;
for(t=0;t<p.length;t++){

m=findpage(p.page_serial[t],p.count);
if(p.count<=p.page_count-1) // 开始时不计算缺页
{
if(m==0) // 页不存在则装入页面
{
p.pageframe[p.k]=p.page_serial[t]; //把要调入的页面放入一个空的页框里
//printf("%d",p.pageframe[p.k]);
p.k=(p.k+1) % p.page_count;
p.count++;

}
}
else // 正常缺页置换
{
if(m==-2)// 页不存在则置换页面
{
for(i=0;i<p.page_count;i++){
if(p.pagetime[i]>p.pagetime[time])
{
time=i;
}
}
p.k=time;
p.pagetime[p.k]=0;
p.pageframe[p.k]=p.page_serial[t];
//p.k=(p.k+1) % p.page_count;
//count1++; //缺页次数加一次
}
}

displayinfo(); // 显示当前页框里面的状态
}
}

void main(){
char ch;
printf("\n\n\n\n\n");
printf(" ***********操作系统实验***********\n\n\n");
printf(" 姓名：计号 \n\n");
printf(" 班级：11网工二班 \n\n");
printf(" 学号： ");
lru();
}

说明：
1. 一定要按照实验报告给出样式书写。
2. 上交纸质实验材料
3. 电子档资料用附件发送到
主题格式为１1网工X班+学号+姓名，
压缩文件格式为：１1网工X班+学号+姓名
源程序代码要单独为一个文件格式X班+学号+姓名+实验名称