操作系统课程设计报告LRU算法内含代码.doc

- .

操作系统课程设计

LRU页面调度算法

学 号：

姓 名：

学 院：

专 业：

班 级：
指导教师：

日 期：

. word.zl.
- .
目 录

一、实验题目1

二、课程设计的目的1

三、设计容1

四、设计要求1

五、设计思想1

六、主要数据构造及其说明2

七、硬件支持3

八、源程序文件3

九、程序运行结果7

十、实验体会8

. word.zl.
- .
一 实验题目
LRU页面调度算法
二 课程设计的目的
操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既
动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解
决实际问题的时机。
1.进一步稳固和复习操作系统的根底知识。
2. 培养学生构造化程序、模块化程序设计的方法和能力。
3.提高学生调试程序的技巧和软件设计的能力。
4.提高学生分析问题、解决问题以及综合利用C语言进展程序设计的能力。
三 设计容
程序应模拟实现LRU算法思想，对n个页面实现模拟调度。
四 设计要求
1．不同的功能使用不同的函数实现〔模块化〕，对每个函数的功能和调用接口要注释清楚。对程序其它局部也进展必要的注释。
2．对系统进展功能模块分析、画出总流程图和各模块流程图。
3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。
4．通过命令行相应选项能直接进入某个相应菜单项选择项的功能模块。
5．所有程序需调试通过。
五 设计思想
最近最久未使用〔LRU〕页调度算法是选择最近最久未使用的页面予以淘汰。算法赋予每个页面一个字段，用来记录一个页面自上次被以来所经历的时间，当所要的页面在存块中时，就不淘汰页面，否那么，淘汰页面中时间最长的，即淘汰最近最久未使用的页面。

Lru(a[i],b)

Init(b,c)

输入页面号

开场

输出queue[i] 缺页次数和缺页率

是否继 续?

y

n
完毕

算法流程图

六 主要数据构造及其说明
程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的记录项，且每一次这些记录项，叶面都必须更新这些记录项。这个记录项在此程序中为：
typedef struct page
{
int num;/*记录页面号*/
int time;/*记录调入存时间*/
}Page;//页面逻辑构造，构造为方便算法实现设计
如此，显然要花费较大的系统开销〔包括时间和空间上的〕，这也是实际系统中不采用LRU算法的直接原因，但由于其页面置换的优越性，实际系统中常使用LRU的近似算法。
七 硬件支持
为了了解一个进程在存中的各个页面各有多少时间未被进程，以及如何快速的知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：存放器或栈。
存放器：为了记录某进程在存中各页的使用情况，须为每个在存中的页面配置一个移位存放器。
栈：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程某页面时，便将该页面的页面号从战中移出，将它压入栈顶。因此，栈顶始终是最新被页面的编号，而栈底那么是最近最久未使用页面的页面号。
八 源程序文件
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define M 3 //物理块数
#define N 10 //页面数
#define Myprintf1
printf("\t************************\t\t\n\n");//表格控制
#define Myprintf2
printf("******************************\n\n");//表格控制

typedef struct page
{
int num;/*记录页面号*/
int time;/*记录调入存时间*/
}Page;//页面逻辑构造，构造为方便算法实现设计

Page b[M];//存单元数
int c[M][N];//暂保存存当前的状态：缓冲区
int queue[100];//记录调入队列
int K;//调入队列计数变量

//初始化存单元、缓冲区
void Init(Page *b,int c[M][N])
{
int i,j;
for(i=0;i<N;i++)
{
b[i].num=-1;
b[i].time=N-i-1;
}

for(i=0;i<M;i++)
for(j=0;j<N;j++)
c[i][j]=-1;
}

//取得在存中停留最久的页面，默认状态下为最早调入的页面
int GetMax(Page *b)
{
int i;
int max=-1;
int tag=0;
for(i=0;i<M;i++)
{
if(b[i].time>max)
{
max=b[i].time;
tag=i;
}
}
return tag;
}

//判断页面是否已在存中
int Equation(int fold,Page *b)
{
int i;
for(i=0;i<M;i++)
{
if(fold==b[i].num)
return i;
}
return -1;
}

//LRU核心局部
void Lru(int fold,Page *b)
{
int i;
int val;
val=Equation(fold,b);
if(val>=0)
{
b[val].time=0;
for(i=0;i<M;i++)
if(i!=val)
b[i].time++;
}

else
{
queue[++K]=fold;//记录调入页面
val=GetMax(b);
b[val].num=fold;
b[val].time=0;
for(i=0;i<M;i++)
if(i!=val)
b[i].time++;
}
}

//主程序
void main()
{
start:K=-1;
int i,j;
int a[N];
Myprintf1;
printf("\n\t\t\t欢送使用LRU页面调度算法\n\n");
Myprintf1;
printf("请输入所要的各个页面号：\n");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
Init(b,c); //调用
for(i=0;i<N;i++)
{
Lru(a[i],b);
c[0][i]=a[i];

//记录当前的存单元中的页面
for(j=0;j<M;j++)
c[j][i]=b[j].num;
}

//结果输出
printf("存状态为:\n");
Myprintf2;
for(j=0;j<N;j++)
printf("|%2d",a[j]);
printf("|\n");
Myprintf2;

for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
if(c[i][j]==-1)
printf("|%2c",32);
else
printf("|%2d",c[i][j]);
}
printf("|\n");
}
Myprintf2;
printf("\n调入队列为：");
for(i=0;i<K+1;i++)
printf("%3d",queue[i]);
printf("\n缺页次数为:%6d\n缺页率:%16.6f",K+1,(float)(K+1)/N);
printf("\n是否继续!\t y?");
char y;
if(getch()=='y')
{
system("cls");
printf("\n");
goto start;
}
else
printf("\n");
printf("程序完毕\n");

}
九 程序运行结果
十 实验体会
通过本次课程设计，对LRU页面调度算法有了更深入的理解和掌握，进一步的稳固和复习了操作系统中关于LRU页面调度算法的知识，进一步的了解了构造化、模块化程序设计的方法，提高了编写和调试程序的技巧，教师的细心指导。
. word.zl.