当前位置:
文档之家› 操作系统页面置换算法和磁盘调度算法
操作系统页面置换算法和磁盘调度算法
物理与电子信息工程学院《操作系统》课程设计报告
题目:
1、页面淘汰算法
2、磁盘调度算法
班级:10计本
完成日期:2012-9-14
指导教师:曾令华
目录
一、页面淘汰算法(一) (1)
1.1 实验目的 (3)
1.2 概念原理 (3)
1.3 总体设计 (4)
1.4 详细设计 (6)
1.5 心得总结 (18)
二、磁盘调度算法(二) (19)
2.1 实验目的 (19)
2.2 概念原理 (19)
2.3 总体设计 (20)
2.4 详细设计 (21)
2.5 心得总结 (32)
一、页面淘汰算法(一)
1.1实验目的
加深对操作系统原理的进一步认识,加强实践动手能力和程序开发能力的培养,提高分析问题解决问题的能力,培养合作精神,以巩固和加深页面置换的概念。这次课程设计,就是通过模拟页面置换来加深对操作系统中页面置换概念的理解通过对页面置换算法的设计,深入理解页面淘汰算法的优劣性。
1.2概念原理
(1)先进先出页面置换算法(FIFO)
FIFO算法这是最早出现的置换算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如含有全局变量、常用函数、例程等的页面,FIFO算法并不能保证这些页面不被淘汰。
(2)最佳置换算法(OPT)
它是由Belady于1966 年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用此算法来评价其它算法。
(3)最近最久未使用置换算法(LRU)
最近最久未使用(LRU)置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。
1.3总体设计
1、根据要求设计页面淘汰算法的流程
运行程序进入主页面,选择输入模式,随机和手动输入两种模式
(1)随机模式
●输入物理块和页面号引用串长度的随机范围
●按要求随机生成页面号引用串
●进入页面置换算法选择模式
●1为FIFO,2为LRU,3为OPT,4为退出
●产生结果,分析数据正确型,完成后可以再次选择,进行不同的模
式来计算
●退出关闭程序
(2)手动模式
●手机输入物理块和页面号引用串长度的数值
●按要求生成页面号引用串
●进入页面置换算法选择模式
●1为FIFO,2为LRU,3为OPT,4为退出
●产生结果,分析数据正确型,完成可以再次选择,进行不同的模式
来计算
●退出关闭程序
FIFO算法流程图:
OPT算法流程图:
1.4详细设计
流程截图:
初始化欢迎说明
随机生成物理块跟页面号引用串个数,选择算法
选择1.FIFO算法
选择3.OPT算法
手动输入
选择算法
源代码:
#include
#include
#include
#include
#define L 20//页面走向长度最大为20
/*全局变量*/
int mSIZE; /*物理块数*/
int pSIZE; /*页面号引用串个数*/
static int memery[10]={0}; /*物理块中的页号*/ static int page[100]={0}; /*页面号引用串*/ static int temp[100][10]={0}; /*辅助数组*/
/*置换算法函数*/
void FIFO();
void LRU();
void OPT();
void Hwi();
/*辅助函数*/
void print(unsigned int t);
void zinstruction();
void sinstruction();
void mDelay(unsigned int Delay);
/*主函数*/
void main()
{
int eneration;
int code;
system("color 0D");
cout<<"|*********************************************|"<cout<<"||欢迎:||"<cout<<"|| 页面置换算法||"<cout<<"|| 包含FIFO/OPT/LRU ||"<cout<<"|| by-王力&&王运||"<cout<<"|*********************************************|"<cout<<"|**********************************************|"<cout<<"||说明:||"<cout<<"|| 选择物理块与页面号引用串个数生成方式||"<cout<<"|| 生成物理块与页面号引用串个数||"<cout<<"|| 选择何种算法||"<cout<<"|| ||"<system("pause");
system("cls");
printf("请选择物理块与页面号引用串个数的生成方式\n");
printf("(1—随机生成,2—手动输入):");
do{ //判断输入是否正确
scanf("%d",&eneration);
if(eneration!=1&&eneration!=2)
{
printf("请选择1或者2:");
}
}while(eneration!=1&&eneration!=2);
switch(eneration)
{
case 2:
{
system("cls");
sinstruction();
getchar();
system("color 0B");
printf("请输入物理块的个数(M<=10):");
scanf("%d",&mSIZE);
printf("请输入页面号引用串的个数(P<=100):");
scanf("%d",&pSIZE);
puts("请依次输入页面号引用串(连续输入,需用空格隔开):");
for(int i=0;i{
scanf("%d",&page[i]);
}
printf("\n");
system("pause");
}
break;
case 1:
{
system("cls");
zinstruction();
getchar();
int i,j,a,b,f,h;
system("color 0B");
srand(time(NULL));
printf("请输入物理块的随机参数的范围个数,两个数之间请用空格隔开(前者大于后者):");
do{
scanf("%d %d",&a,&b);
if(b>10)
printf("实际物理块必须小于10(即后者不得大于10),请重新输入:");
if(a>=b)
printf("输入的后者不得大于或等于前者,请重新输入:");
// else break;
}while(b>10||a>=b);
mSIZE=rand()%(b-a)+a;/*产生a-b(包括a和b)的随机数*/
srand(time(NULL));
printf("请输入页面号引用串的随机范围,两个数之间请用空格隔开(前者大于后者):");
do //判断psize不大于100
{
scanf("%d %d",&f,&h);/*产生f-h(包括f和h)的随机数*/
if(h>100)
printf("实际页面长度须小于100(即后者不得大于100),请重新输入:");
if(f>=h)
printf("输入的后者不得大于或等于前者,请重新输入:");
// else break;
}while(h>100||f>=h);
pSIZE=rand()%(h-f)+f;
printf("\n");
printf("随机产生的物理块数x=%d 和页面号引用串长度y=%d \n",mSIZE,pSIZE);
getchar();
j=time(NULL);//取时钟时间
srand(j);//以时钟时间x为种子,初始化随机数发生器
for(i=0;i{
page[i]=rand( )%10;//产生1到9之间的随即数放到page[i]中
}
printf("\n");
system("pause");
}
break;
// system("cls");
}
///////////////////////////////////////功能选择后的执行
do{
printf("\n");
printf("随机产生页面号引用串:");
for(int i=0;iprintf("%d ",page[i]);
printf("\n");
printf("|************************************|\n");
printf("|请选择何种算法:|\n");
printf("| 1.先进先出(FIFO) |\n");
printf("| 2.最近最久未使用(LRU) |\n");
printf("| 3.最佳(OPT) |\n");
printf("| 4.清楚界面|\n");
printf("| 0.退出|\n");
printf("|************************************|\n");
printf("请选择操作:[ ]\b\b");
scanf("%d",&code);
printf("\n");
///////////////////////////////////////////算法的选用
if(code!=1&&code!=2&&code!=3&&code!=4&&code!=0)
{
printf("输入错误,请看清选择\n");
}
else
{
switch(code)
{
case 1:
FIFO();
printf("\n");
system("pause");
break;
case 2:
LRU();
printf("\n");
system("pause");
break;
case 3:
OPT();
printf("\n");
system("pause");
break;
case 4:
system("cls");
break;
case 0:
system("cls");
system("color 0A");
printf("|*************************************|\n*");
printf("|| 感谢使用页面置换算法演示器! ||\n*");
printf("|| 如遇bug或有疑问联系||\n*");
printf("|| 本人不负任何责任||\n*");
printf("|| by-王力&&王运! ||\n*");
printf("|*************************************|\n*");
exit(0);
}
}
}while (code!=0);
///////////////////////////////////////功能选择后的执行end
}
/*显示程序的注意事项*/
void zinstruction()
{
printf("说明:\n");
printf(" 1、你选择的是随机输入,系统将随机生成页面号引用串\n");
printf(" 2、选择页面面置换算法FIFO/OPT/LRU\n");
printf(" 3、得出结果,关闭程序\n");
}
void sinstruction()
{
printf("说明:\n");
printf(" 1、你选择的是手动输入页面号引用串\n");
printf(" 2、选择页面面置换算法有FIFO/OPT/LRU\n");
printf(" 3、得出结果,关闭程序\n");
}
void print(unsigned int t)
{
int i,j,k,l;
int flag;
printf("置换顺序依次为:\n");
for(k=0;k<=(pSIZE-1)/20;k++)
{
for(i=20*k;(i{
if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
printf(" %d\n",page[i]);
else
printf(" %d ",page[i]);
}
for(j=0;j{
for(i=20*k;(i{
if(i>=j)
printf(" |%d|",temp[i][j]);
else
printf(" | |");
}
for(i=mSIZE+20*k;(i{
for(flag=0,l=0;lif(temp[i][l]==temp[i-1][l])
flag++;
if(flag==mSIZE)/*页面在物理块中*/
printf(" ");
else
printf(" |%d|",temp[i][j]);
}
/*每行显示20个*/
if(i%20==0)
continue;
printf("\n");
}
}
printf("输出结果:\n");
printf("缺页次数:%d\t\t",t+mSIZE);
printf("缺页率:%d/%d\t\t",t+mSIZE,pSIZE);
printf("置换次数:%d\t\t",t);
getchar();
}
/*FIFO算法*/
void FIFO()
{
int memery[10]={0};
int time[10]={0}; /*记录进入物理块的时间*/
int i,j,k,m;
int max=0; /*记录换出页*/
int count=0; /*记录置换次数*/
/*前mSIZE个数直接放入*/
for(i=0;i{
memery[i]=page[i];
time[i]=i;
for(j=0;jtemp[i][j]=memery[j];
}
for(i=mSIZE;i{
/*判断新页面号是否在物理块中*/
for(j=0,k=0;j{
if(memery[j]!=page[i])
k++;
}
if(k==mSIZE) /*如果不在物理块中*/
{
count++;
/*计算换出页*/
max=time[0]