经典调度算法的实现
经典调度算法的实现
学 号：
姓 名： 专 业： 指导教师：
日 期：
目录
一、 课设简介 . ....................................... 3 1、 课程设计题目 .................................. 3 2、 课程设计目的 .................................. 3 3、 课程设计内容 .................................. 3 4、 时间安排 ...................................... 3 二、 实验原理分析 .................................... 4 1、问题描述 ....................................... 4 2、问题分析 ....................................... 5 3、解决方法 ....................................... 6 三、 主要的功能模块 .................................. 7 1、数据结构 ....................................... 7 2、主要的函数 .................................... 13 3、 测试用例及运行结果 ........................... 14 四、 源代码 . ........................ 错误！未定义书签。 五、 总结及参考文献 ................................. 24 1、总结 .......................................... 24 2、参考文献 ...................................... 24
一、 课设简介
1、 课程设计题目
经典调度算法的实现
2、 课程设计目的
操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。
1）进一步巩固和复习操作系统的基础知识。
2）培养学生结构化程序、模块化程序设计的方法和能力。 3）提高学生调试程序的技巧和软件设计的能力。
4）提高学生分析问题、解决问题以及综合利用C 语言进行程序设计的能力。
3、 课程设计内容
实现以下几种调度算法
1 FCFS 2 SJF
3 高响应比优先调度算法。
4、 时间安排
1）分析设计贮备阶段 （1 天） 2）编程调试阶段 （7 天） 3）写课程设计报告、考核（2 天）
二、 实验原理分析
1、设计要求：
1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。
2．对系统进行功能模块分析、画出总流程图和各模块流程图。
3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。
4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。
5. 所有程序需调试通
2、进程调度模拟程序流程图
图1、主函数流程图
图2、先来先服务算法调度
图3、短作业优先调度
图4、高相应比算法调度
三、 主要的功能模块
1、数据结构
先来先服务算法调度
#include struct fcfs{ char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; };
fcfs a[100];
void input(fcfs *p,int N) { int i;
printf("intput the process's name & arrivetime & servicetime:\nfor exmple: a 0 100\n");
for(i=0;i
printf("input the %dth process's information:\n",i+1);
scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime); } }
void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) {int k;
printf("run order:"); printf("%s",p[0].name); for(k=1;k
{printf("-->%s",p[k].name); }
printf("\nthe process's information:\n");
printf("\nname\tarrive\tservice\tstart\tfinish\tzz\tdqzz\n");
for(k=0;k
{ printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); }
pai xu
void sort(fcfs *p,int N) {
for(int i=0;i
if(p[i].arrivetime
fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } }
//yun xing jieduan
void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) { int k;
for(k=0;k
if(k==0) {
p[k].starttime=p[k].arrivetime;
p[k].finishtime=p[k].arrivetime+p[k].servicetime;}
else {
p[k].starttime=p[k-1].finishtime;
p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} }
for(k=0;k
p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } }
void FCFS(fcfs *p,int N) {
float
arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N);
deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); }
void main() { int N;
printf("------先来先服务调度算法------\n"); printf("input the process's number:\n"); scanf("%d",&N); input(a,N); FCFS(a,N); }
短作业优先调度算法
int sjf() { turn();
float temp_time=0; int i=0,j;
int temp_counter; float servicetime;
servicetime=tasks[i].servicetime; j=1;
while ((j
{
if (tasks[j].servicetime
{
servicetime=tasks[j].servicetime;
i=j;
}
j++;
} /*查找第一个被调度的进程*/ /*对第一个被调度的进程求相应的参数*/ //number_schedul=i;
tasks[i].begintime=tasks[i].arrivetime;
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime; tasks[i].run_flag=1;
temp_time=tasks[i].finishtime; tasks[i].order=1; temp_counter=1;
while (temp_counter
for(j=0;j
{
if((tasks[j].arrivetime
{
servicetime=tasks[j].servicetime;i=j;break;
for(j=0;j
{
}
}
if((tasks[j].arrivetime
if(tasks[j].servicetime
{
servicetime=tasks[j].servicetime;
i=j;
}
}
/*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/ tasks[i].begintime=temp_time;
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime; tasks[i].run_flag=1;
temp_time=tasks[i].finishtime; temp_counter++;
tasks[i].order=temp_counter; } return 0; }
高响应比优先算法调度
int hrrn() { turn();
int j,i,temp_counter;
float temp_time,respond_rate,max_respond_rate; /*第一个进程被调度*/
tasks[0].begintime=tasks[0].arrivetime;
tasks[0].finishtime=tasks[0].begintime+tasks[0].servicetime; temp_time=tasks[0].finishtime; tasks[0].run_flag=1; tasks[0].order=1; temp_counter=1; /*调度其他进程*/
while(temp_counter
max_respond_rate=0;
for(j=1;j
{
注
意
if((tasks[j].arrivetime
{
respond_rate=(temp_time-tasks[j].arrivetime)/tasks[j].servicetime;//等待时间/运行时间
if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate; i=j;
}
}
}
/*找响应比高的进程*/
tasks[i].begintime=temp_time;//把第一个进程的结束时间赋值于下一个进程的开始时间, 前提是必须满足上面条件
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime;
temp_time=tasks[i].finishtime;//改换到进程的结束时间，比较下一轮的(等待时间/运行时间) tasks[i].run_flag=1; temp_counter+=1;
tasks[i].order=temp_counter; } return 0; }
int pinput() /*进程参数输入*/ { int i;
printf("请输入实际进程的个数：\n"); scanf("%d",&counter);
for(i=0;i
{ printf("******************************************\n");
printf("请输入第 %d个进程 :\n",i+1); printf("请输入该进程名字:\n"); scanf("%s",tasks[i].name);
printf("请输入该进程到达时间 arrivetime:\n"); scanf("%f",&tasks[i].arrivetime);
printf("请输入该进程运行时间 servicetime:\n"); scanf("%f",&tasks[i].servicetime); tasks[i].begintime=0; tasks[i].finishtime=0; tasks[i].order=0; tasks[i].run_flag=0;
}
for(i=0;i
strcpy(a[i].name,tasks[i].name); a[i].arrivetime=tasks[i].arrivetime; a[i].servicetime =tasks[i].servicetime ;
a[i].begintime=0; a[i].finishtime=0; a[i].order=0; a[i].run_flag=0;
}
return 0; }
3、 测试用例及运行结果（先来先服务测试）
四、 代码
#include #include using namespace std; #define MAX 8 struct task_struct {
char name[10]; /*进程名称*/ float arrivetime; /*到达时间*/ float begintime; /*开始运行时间*/ float servicetime; /*运行时间*/ float finishtime; /*运行结束时间*/ int order; /*运行次序*/ int run_flag; /*调度标志*/ }tasks[MAX],a[MAX];
int counter; /*实际进程个数*/ int fcfs(); /*先来先服务*/ int sjf();
/*短作业优先*/
/*高响应比优先*/ /*进程参数输入*/
int hrrn(); int pinput(); int poutput();
void main() {
//system("color aa"); int option;
pinput();
while(1)
{
printf("请选择调度算法（1~3）:\n"); printf("1.先来先服务\n"); printf("2.短作业优先\n"); printf("3.响应比高优先\n"); printf("0.退出\n"); scanf("%d",&option); switch (option) { case 0:
//save();
printf("运行结束。\n");
exit(0);
break; case 1:
printf("对进程按先来先服务调度。\n\n"); fcfs(); poutput(); break;
case 2:
printf("对进程按短作业优先调度。\n\n"); sjf(); poutput(); break; case 3:
printf("对进程按高响应比优先调度。\n\n"); hrrn(); poutput();
break; } } }
void turn(){
for(int i=0;i
{
strcpy(tasks[i].name,a[i].name); tasks[i].arrivetime=a[i].arrivetime; tasks[i].servicetime =a[i].servicetime ;
tasks[i].begintime=0; tasks[i].finishtime=0; tasks[i].order=0; tasks[i].run_flag=0; } //}
int fcfs() /*先来先服务*/ {turn();
float time_temp=0; int i;
time_temp=tasks[0].arrivetime; for(i=0;i
tasks[i].begintime=time_temp;
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime; tasks[i].run_flag=1;
time_temp=tasks[i].finishtime; tasks[i].order=i+1;
}
} return 0; }
int sjf() /*短作业优先*/ {turn();
float temp_time=0; int i=0,j;
int temp_counter; float servicetime;
servicetime=tasks[i].servicetime; j=1;
while ((j
{
if (tasks[j].servicetime
{
servicetime=tasks[j].servicetime; i=j;
}
j++;
} /*查找第一个被调度的进程*/ /*对第一个被调度的进程求相应的参数*/ //number_schedul=i;
tasks[i].begintime=tasks[i].arrivetime;
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime; tasks[i].run_flag=1;
temp_time=tasks[i].finishtime; tasks[i].order=1; temp_counter=1;
while (temp_counter
for(j=0;j
{
if((tasks[j].arrivetime
{
servicetime=tasks[j].servicetime;i=j;break;
for(j=0;j
{
}
}
if((tasks[j].arrivetime
if(tasks[j].servicetime
{
servicetime=tasks[j].servicetime;
i=j;
}
}
/*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/ tasks[i].begintime=temp_time;
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime; tasks[i].run_flag=1;
temp_time=tasks[i].finishtime; temp_counter++;
tasks[i].order=temp_counter; } return 0; }
int hrrn() /*高响应比优先*/
{ turn();
int j,i,temp_counter;
float temp_time,respond_rate,max_respond_rate;
/*第一个进程被调度*/
tasks[0].begintime=tasks[0].arrivetime;
tasks[0].finishtime=tasks[0].begintime+tasks[0].servicetime;
temp_time=tasks[0].finishtime;
tasks[0].run_flag=1;
tasks[0].order=1;
temp_counter=1;
/*调度其他进程*/
while(temp_counter
{
max_respond_rate=0;
for(j=1;j
{
if((tasks[j].arrivetime
{
respond_rate=(temp_time-tasks[j].arrivetime)/tasks[j].servicetime; if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate;
i=j;
} } }
tasks[i].begintime=temp_time;//把第一个进程的结束时间赋值于下一个进程的开始时间, 前提是必须满足上面条件
tasks[i].finishtime=tasks[i].begintime+tasks[i].servicetime;
temp_time=tasks[i].finishtime;//改换到进程的结束时间，比较下一轮的(等待时间/运行时间)
tasks[i].run_flag=1;
temp_counter+=1;
tasks[i].order=temp_counter;
}
return 0;
}
int pinput() /*进程参数输入*/
{
int i;
printf("请输入实际进程的个数：\n");
scanf("%d",&counter);
for(i=0;i
{ printf("******************************************\n");
printf("请输入第 %d个进程 :\n",i+1);
printf("请输入该进程名字:\n");
scanf("%s",tasks[i].name);
printf("请输入该进程到达时间 arrivetime:\n");
scanf("%f",&tasks[i].arrivetime);
printf("请输入该进程运行时间 servicetime:\n");
scanf("%f",&tasks[i].servicetime);
tasks[i].begintime=0;
tasks[i].finishtime=0;
tasks[i].order=0;
tasks[i].run_flag=0;
} for(i=0;i
a[i].arrivetime=tasks[i].arrivetime; a[i].servicetime =tasks[i].servicetime ;
a[i].begintime=0;
a[i].finishtime=0;
a[i].order=0;
a[i].run_flag=0;
}
return 0;
}
int poutput() /*调度结果输出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("进程名 到达时间 服务时间 开始时间 完成时间 运行次序 周转时间\n");
for(i=0;i
{
f1=tasks[i].finishtime-tasks[i].arrivetime;
turn_round_time+=f1;
w+=(f1/tasks[i].servicetime);
printf(" %s\t %5.3f\t %5.3f\t %5.3f\t %5.3f \t %d\t %5.3f\t\n",tasks[i].name,tasks[i].arrivetime,tasks[i].servicetime,tasks[i].begintime,tasks[i].finishtime,tasks[i].order,f1);
}
printf("平均周转时间=%5.2f\n",turn_round_time/counter);
printf("带权周转时间=%5.2f\n",w/counter);
return 0;
}
}
第5部分 总结及参考文献
1、 总结
通过此次课程设计，更深入的理解了先来先服务调度算法、短作业优先调度算法、高响应比优先调度算法，及实现过程。在此过程中，遇到了困难，能及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，将会在今后学习中更加努力。
2、 参考文献
1）宗大华，宗涛，陈吉人著 操作系统 北京：人民邮电出版社，2009
2）李爱华，程磊著 面相对象程序设计（C++语言） 北京: 清华大学出版社，2010
3）宋晓宇 ， windows操作系统核心编程实验教程 中国铁道出版社
4）张丽芬 刘利雄 王金玉编著 操作系统实验教程 清华大学出版社