经典调度算法的实现学院：专业：姓名：学号：指导老师：2014-3-18目录一、课设简介 (3)1. 课程设计题目 (3)2. 课程设计目的 (3)3. 课程设计的内容 (3)4. 课程设计要求 (3)二、原理分析 (4)1. 先来先服务算法介绍与分析 (4)2. 短作业优先算法介绍与分析 (4)3. 高响应比优先调度算法介绍与分析 (4)4. 流程图 (5)三、主要功能模块 (7)1. 先来先服务算法实现代码 (7)2. 短作业优先算法实现代码 (8)3. 高响应比优先调度算法实现代码 (8)四、测试与运行结果 (9)1. 主界面 (9)2. 先来先服务算法测试 (10)3. 短作业优先算法测试 (11)4. 高响应比优先调度算法测试 (13)五、总结 (16)六、参考文献 (16)七、附录 (16)一、课设简介1.课程设计题目经典调度算法的实现2.课程设计目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。

●进一步巩固和复习操作系统的基础知识。

●培养学生结构化程序、模块化程序设计的方法和能力。

●提高学生调试程序的技巧和软件设计的能力。

●提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。

3.课程设计的内容实现以下几种调度算法1 FCFS2 SJF3 高响应比优先调度算法。

4.课程设计要求1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。

对程序其它部分也进行必要的注释。

2．对系统进行功能模块分析、画出总流程图和各模块流程图。

3．用户界面要求使用方便、简洁明了、美观大方、格式统一。

所有功能可以反复使用，最好使用菜单。

4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。

5．所有程序需调试通过。

二、原理分析1.先来先服务算法介绍与分析先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。

当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。

在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。

该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。

2.短作业优先算法介绍与分析短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。

它们可以分别用于作业调度和进程调度。

短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。

SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。

该算法对长作业不利，完全未考虑作业的紧迫程度。

3.高响应比优先调度算法介绍与分析在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足之处是长作业的运行得不到保证。

如果我们能为每个作业引人动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。

该优先权的变化规律可描述为:优先权=（等待时间+要求服务时间）/要求服务时间即优先权=响应时间/要求服务时间如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因而该算法有利于短作业。

当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间越长，优先权越高，因而它实现的是先来先服务对于长作业，作业的优先级可以随着等待时间的增加而提高，当其等待时间足够长时，其优先级便可以升到很高，从而也可获得处理机。

4.流程图图1、主函数流程图图2、先来先服务算法调度图3、短作业优先调度图4、高相应比算法调度三、主要功能模块1.先来先服务算法实现代码void sort() /* 建立对作业进行提交时间排列函数*/ {JCB *first, *second;int insert=0;if((jcb_ready==NULL)||((j->subtime)<(jcb_ready->subtime))) /*作业提交时间最短的,插入队首*/{j->link=jcb_ready;jcb_ready=j;T=j->subtime;j->Rp=1;}else /* 作业比较提交时间,插入适当的位置中*/{first=jcb_ready;second=first->link;while(second!=NULL){if((j->subtime)<(second->subtime)) /*若插入作业比当前作业提交时间短,*/{ /*插入到当前作业前面*/j->link=second;first->link=j;second=NULL;insert=1;}else /* 插入作业优先数最低,则插入到队尾*/ {first=first->link;second=second->link;}}if (insert==0) first->link=j;}}2.短作业优先算法实现代码void SJFget() /* 获取队列中的最短作业 */{JCB *front,*mintime,*rear;int ipmove=0;mintime=jcb_ready;rear=mintime->link;while(rear!=NULL)if((rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtim e)){front=mintime;mintime=rear;rear=rear->link;ipmove=1;}elserear=rear->link;if (ipmove==1){front->link=mintime->link;mintime->link=jcb_ready;}jcb_ready=mintime;}3.高响应比优先调度算法实现代码void HRNget() /* 获取队列中的最高响应作业 */{JCB *front,*mintime,*rear;int ipmove=0;mintime=jcb_ready;rear=mintime->link;while(rear!=NULL)if((rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp)){front=mintime;mintime=rear;rear=rear->link;ipmove=1;}elserear=rear->link;if (ipmove==1){front->link=mintime->link; mintime->link=jcb_ready;}jcb_ready=mintime;}四、测试与运行结果1.主界面2.先来先服务算法测试3.短作业优先算法测试4.高响应比优先调度算法测试五、总结通过本次课程设计，更加深入的理解了先来先服务调度算法、短作业优先调度算法、高响应比优先调度算法的原理，及实现过程。

通过本次课设对这三种算法的优缺点有了进一步的理解。

进一步巩固和复习操作系统的基础知识，更进一步的了解了结构化模块化程序设计的方法，提高了调试程序的技巧。

同时在本次课设过程中，遇到了许多困难，通过请教同学，查询相关资料，及时解决了问题，但仍存在不足之处，将会在今后学习中更加努力。

六、参考文献1）宗大华，宗涛，陈吉人著操作系统北京：人民邮电出版社，20092）李爱华，程磊著面相对象程序设计（C++语言）北京: 清华大学出版社，20103）宋晓宇， windows操作系统核心编程实验教程中国铁道出版社4）张丽芬刘利雄王金玉编著操作系统实验教程清华大学出版社七、附录源代码#include <stdio.h>#include<conio.h>#include <stdlib.h>#define getpch(type) (type*)malloc(sizeof(type))struct worktime{float Tb; //作业运行时刻float Tc; //作业完成时刻float Ti; //周转时间float Wi; //带权周转时间};struct jcb { /*定义作业控制块JCB */char name[10]; //作业名float subtime; //作业提交时间float runtime; //作业所需的运行时间char resource; //所需资源float Rp; //后备作业响应比char state; //作业状态struct worktime wt;struct jcb* link; //链指针}*jcb_ready=NULL,*j;typedef struct jcb JCB;float T=0;void sort() /* 建立对作业进行提交时间排列函数*/{JCB *first, *second;int insert=0;if((jcb_ready==NULL)||((j->subtime)<(jcb_ready->subtime))) /*作业提交时间最短的,插入队首*/{j->link=jcb_ready;jcb_ready=j;T=j->subtime;//更改时间量j->Rp=1;}else /* 作业比较提交时间,插入适当的位置中*/{first=jcb_ready;second=first->link;while(second!=NULL){if((j->subtime)<(second->subtime)) /*若插入作业比当前作业提交时间短,*/{ /*插入到当前作业前面*/j->link=second;first->link=j;second=NULL;insert=1;}else /* 插入作业优先数最低,则插入到队尾*/{first=first->link;second=second->link;}}if (insert==0) first->link=j;}}void SJFget() /* 获取队列中的最短作业*/{JCB *front,*mintime,*rear;int ipmove=0;mintime=jcb_ready;//mintime指向作业对头rear=mintime->link;while(rear!=NULL)if((rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime)) {//当插入作业到达时间要比时间量T小front=mintime;mintime=rear;//mintime指向rearrear=rear->link;ipmove=1;}elserear=rear->link;if (ipmove==1){front->link=mintime->link;mintime->link=jcb_ready;}jcb_ready=mintime;//把最终获取的min的需要时间赋给jcb_ready，开始执行}void HRNget() /* 获取队列中的最高响应作业*/{JCB *front,*mintime,*rear;int ipmove=0;mintime=jcb_ready;rear=mintime->link;while(rear!=NULL)if ((rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp)){front=mintime;mintime=rear;rear=rear->link;ipmove=1;}elserear=rear->link;if (ipmove==1){front->link=mintime->link;mintime->link=jcb_ready;}jcb_ready=mintime;}void input() /* 建立作业控制块函数*/{ int i,num;printf("\n 请输入作业数:");scanf("%d",&num);for(i=0;i<num;i++){printf("\n 作业号No.%d:\n",i);j=getpch(JCB);printf("\n 输入作业名:");scanf("%s",j->name);printf("\n 输入作业提交时刻:");scanf("%f",&j->subtime);printf("\n 输入作业运行时间:");scanf("%f",&j->runtime);printf("\n");j->state='w';j->link=NULL;sort(); /* 调用sort函数*/}}int space()/*查看作业个数*/{int l=0; JCB* jr=jcb_ready;while(jr!=NULL){l++;jr=jr->link;}return(l);}void disp(JCB* jr,int select) /*建立作业显示函数,用于显示当前作业*/{if (select==3) printf("\n 作业服务时间响应比运行时刻完成时刻周转时间带权周转时间\n");else printf("\n 作业服务时间运行时刻完成时刻周转时间带权周转时间\n");printf(" %s\t",jr->name);printf(" %.2f\t ",jr->runtime);if (select==3) printf(" |%.2f ",jr->Rp);if (j==jr){printf(" %.2f\t",jr->wt.Tb);printf(" %.2f ",jr->wt.Tc);printf(" %.2f \t",jr->wt.Ti);printf(" %.2f",jr->wt.Wi);}printf("\n");}int destroy() /*建立作业撤消函数(作业运行结束,撤消作业)*/{printf("\n 作业[%s] 已完成.\n",j->name);free(j);return(1);}void check(int select) /* 建立作业查看函数*/{ JCB* jr;printf("\n **** 当前正在运行的作业是:%s",j->name); /*显示当前运行作业*/disp(j,select);jr=jcb_ready;printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/while(jr!=NULL){jr->Rp=(T-jr->subtime)/jr->runtime;disp(jr,select);jr=jr->link;}destroy();}void running(JCB* jr) /* 建立作业就绪函数(作业运行时间到,置就绪状态*/{if (T>=jr->subtime) jr->wt.Tb=T;//插入作业的到达时间比时间量小，T为该作业的开始时间else jr->wt.Tb=jr->subtime;//否则该作业到达时间为它的开始时间jr->wt.Tc=jr->wt.Tb+jr->runtime;jr->wt.Ti=jr->wt.Tc-jr->subtime;jr->wt.Wi=jr->wt.Ti/jr->runtime;T=jr->wt.Tc;}int main() /*主函数*/{A:int select=0,len,h=0;float sumTi=0,sumWi=0;printf("\t---*****************---\n"); printf("请选择作业调度算法的方式:\n");printf("\t1.FCFS 2.SJF 3.HRN 4.退出\n\n");printf("\t---*****************---\n");printf("请输入作业调度算法序号(1-4):");scanf("%d",&select);if (select==4){ exit(0);}else{input();len=space();while((len!=0)&&(jcb_ready!=NULL)){ h++;printf("\n 执行第%d个作业\n",h);j=jcb_ready;jcb_ready=j->link;j->link=NULL;j->state='R';running(j);sumTi+=j->wt.Ti;sumWi+=j->wt.Wi;check(select);if (select==2&&h<len-1) SJFget();if (select==3&&h<len-1) HRNget();printf("\n 按任一键继续......\n");getchar();getchar();}printf("\n\n 作业已经完成.\n");printf("\t 此组作业的平均周转时间：%.2f\n",sumTi/h); printf("\t 此组作业的带权平均周转时间：%.2f\n",sumWi/h); getchar();system("cls");}goto A;return(0);}。