单道批处理系统作业调度.doc

课程设计说明书 NO.18单道批处理系统作业调度1. 课程设计的目的 操作系统课程的一个非常重要的环节是培养计算机专业学生的系统程序设计能力。通过操作系统课程设计，可以培养程序设计的方法和技巧，提高编制清晰、合理、可读性好的系统程序的能力，加深对操作系统课程的理解。使我们更好地掌握操作系统的基本概念、基本原理、及基本功能，具有分析实际操作系统、设计、构造和开发现代操作系统的基本能力。本次课程设计要求用高级语言编写和调试一个单道批处理系统的作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解2. 课程设计的开发语言C语言3. 功能描述在批处理系统中，作业进入系统后，是先驻留在外存上的，因此需要有作业调度的过程，以便将它们分批装入内存。作业调度用于决定把外存上处于后备队列中的哪些作业调入内存，并为他们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。应将哪些作业从外存调入内存，取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指讲最早进度外存的作业最先调入内存；较常用的一种是短作业优先电镀算法，这是将外存上最短的作业最先调入内存；此外，还有基于响应比高者优先的调度算法，根据作业的响应时间和要求运行时间可计算出响应比。4. 方案论证4.1概要设计根据功能描述，单道批处理程序作业调度的模拟程序要求实现如下功能：建立作业、选择作业、运行作业、计算作业周转时间和带权周转时间，以及这组作业的平均周转时间和带权平均周转时间、显示运行结果，退出程序。各模块的功能介绍如下：（1）建立作业：输入作业数，建立一组作业，并对所建立的这组作业进行初始化，用以模拟作业调度。初始化的内容包括作业名，作业要求运行的时间。（2）选择作业：程序通过先来先服务调度算法、短作业优先调度算法和高响应比优先调度算法对建立的一组作业进行选择，决定把哪个作业从外存调入内存中。（3）运行作业：根据初始化中设置的作业要求运行时间来模拟作业的运行。（4）计算：计算作业周转时间和带权周转时间，以及这组作业的平均周转时间和带权平均周转时间。（5）显示结果：将计算所得的结果输出。（6）退出程序：当实验结束，不再需要模拟作业调度的时候，用来退出程序。作业调度模拟程序的系统功能结构如图1所示。作 业 调 度 系 统先来先服务算法短作业优先算法高响应比优先算法退出程序初始化运行作业输出运行结果初始化运行作业输出运行结果输出运行结果运行作业初始化图1 作业调度模拟程序系统功能结构图4.2 详细设计由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。对每种调度算法都要求输出每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。从以上分析可见，在这个模拟程序中作业控制块JCB的数据结构类型可定义为：struct jcb /作业控制块 char name10; /作业名 int reachtime; /作业到达时间 int starttime; /作业开始时间 int needtime; /作业需要运行的时间 float super; /作业的响应比 int finishtime; /作业完成时间 float cycletime; /作业周转时间 float cltime; /作业带权周转时间 char state; /作业状态 struct jcb *next; /结构体指针*ready=NULL,*p,*q; typedef struct jcb JCB; 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。流程图如图2所示。空结 束计算并打印这组作业的平均周转时间及带权平均周转时间等待队列空？更改时间量times的值；times:=times+服务时间计算并打印运行作业i的完成时刻finishtime，周转时间cycletime，带权周转时间cltime;完成时间：=开始运行时间+服务时间周转时间：=完成时间到达时间带权周转时间：=周转时间/服务时间调度队首的作业投入运行；更改队首指针，使作业的状态为R，记住作业运行的时刻starttime等初始化所有的JBC使JBC按作业提交的时刻的先后顺序排队时间量times:=0开 始不空图2 先来先服务调度算法流程图（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。流程图如图3所示。空结 束计算并打印这组作业的平均周转时间及带权平均周转时间等待队列空？更改时间量times的值；times:=times+服务时间计算并打印运行作业i的完成时刻finishtime，周转时间cycletime，带权周转时间cltime;完成时间：=开始运行时间+服务时间周转时间：=完成时间到达时间带权周转时间：=周转时间/服务时间调度队首的作业投入运行；更改队首指针，使作业的状态为R，记住作业运行的时刻starttime等初始化所有的JBC使JBC按作业提交的时刻的先后顺序排队时间量times:=0开 始不空图3 短作业优先调度算法流程图（3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。流程图如图4所示。空结 束计算并打印这组作业的平均周转时间及带权平均周转时间等待队列空？更改时间量times的值；times:=times+服务时间计算并打印运行作业i的完成时刻finishtime，周转时间cycletime，带权周转时间cltime;完成时间：=开始运行时间+服务时间周转时间：=完成时间到达时间带权周转时间：=周转时间/服务时间先计算队列中所有作业的响应比，总是选择响应比最高的走也作为此刻要运行的作业，并修改相应的指针，记下starttime等初始化所有的JBC使JBC按作业提交的时刻的先后顺序排队时间量times:=0开 始不空图4响应比高者优先算法流程图5. 设计结果与分析（1）选择操作的界面，如图5所示。图5 选择操作的界面（2）输入操作初始信息，建立一组作业，由5个作业组成，作业名分别为a，b，c，d，e。作业要运行的时间分别为5，2，7，3，4。如图6所示。图6 初始化（3）在选择操作的界面输入1，选择先来先服务算法进行作业调度，调度顺序为abcde。运行结果如图7、图8、图9所示。 图7 先来先服务算法调度 图8先来先服务算法调度图9先来先服务算法调度（4）在选择操作的界面输入2，选择最短作业优先算法进行作业调度，调度顺序:abdec。运行结果如图10、图11、图12所示。 图10 最短作业优先算法调度 图11 最短作业优先算法调度图12最短作业优先算法调度（5）在选择操作的界面输入3，选择响应比高者优先算法进行作业调度，调度顺序:bdeac。运行结果如图13、图14、图15所示。 图13响应比高者优先算法调度 图14响应比高者优先算法调度图15 响应比高者优先算法调度6. 设计心得体会计算机技术发展的飞速变化超过了人们想象的速度。但是操作系统作为一门计算机的基础课程，无论是对计算机等信息技术专业的学生活研究人员，还是对一般计算机应用人员，都是非常有益和重要的。通过本次课程设计我对在课堂上所学的有关操作系统的知识有了更加深刻的理解和掌握，尤其是单道批处理系统。进一步了解了该系统的主要特征：自动性，顺序性，单道性。批处理系统能提高系统资源的利用率和系统吞吐量。通过设计的模拟程序对三种调度算法的模拟，对先来先服务调度算法、短作业优先调度算法以及高响应比优先调度算法的基本概念、实现过程以及各个算法的优缺点有的了深刻的了解，知道了不同的算法类型适合不同的作业类型。本次课程设计结合了C语言程序设计语言，通过对作业调度模拟程序的设计，积累了程序设计的实战经验，锻炼了程序设计能力。通过这次课程设计，我拓宽了知识面，锻炼了能力，综合素质得到较大提高，把所学课程及相关知识加以融会贯通，理解了操作系统工作的方法，为今后从事实际工作打下了坚实的基础。7.附录源程序：#include #include #include #define getpch(type) (type*)malloc(sizeof(type) #define NULL 0int n;float T1=0,T2=0;int times=0;struct jcb /作业控制块 char name10; /作业名 int reachtime; /作业到达时间 int starttime; /作业开始时间 int needtime; /作业需要运行的时间 float super; /作业的响应比 int finishtime; /作业完成时间 float cycletime; /作业周转时间 float cltime; /作业带权周转时间 char state; /作业状态 struct jcb *next; /结构体指针*ready=NULL,*p,*q;typedef struct jcb JCB; void inize() /初始化界面 printf(nntt*ttn); printf(tttt作业调度n); printf(tt*ttn); printf(nnnttttt信息工程学院计算机2班n); printf(ttttt施佳达n); printf(ttttt完成日期：2010年7月17号); printf(nnntt请输入任意键进入演示过程n); getch();void inital() /建立作业控制块队列,先将其排成先来先服务的模式队列int i;printf(n输入作业数:);scanf(%d,&n);for(i=0;iname); getch(); p-reachtime=i; printf(作业默认到达时间:%d,i); printf(n输入作业要运行的时间:); scanf(%d,&p-needtime); p-state=W; p-next=NULL; if(ready=NULL) ready=q=p; else q-next=p; q=p; void disp(JCB* q,int m) /显示作业运行后的周转时间及带权周转时间等 if(m=3) /显示高响应比算法调度作业后的运行情况 printf(n作业%s正在运行，估计其运行情况：n,q-name); printf(开始运行时刻：%dn,q-starttime); printf(完成时刻：%dn,q-finishtime); printf(周转时间：%fn,q-cycletime); printf(带权周转时间：%fn,q-cltime); printf(相应比:%fn,q-super); getch(); else / 显示先来先服务,最短作业优先算法调度后作业的运行情况 printf(n作业%s正在运行，估计其运行情况：n,q-name); printf(开始运行时刻：%dn,q-starttime); printf(完成时刻：%dn,q-finishtime); printf(周转时间：%fn,q-cycletime); printf(带权周转时间：%fn,q-cltime); getch(); void running(JCB *p,int m) /运行作业 if(p=ready) /先将要运行的作业从队列中分离出来 ready=p-next; p-next=NULL; else q=ready; while(q-next!=p) q=q-next; q-next=p-next; p-starttime=times; /计算作业运行后的完成时间,周转时间等等 p-state=R; p-finishtime=p-starttime+p-needtime; p-cycletime=(float)(p-finishtime-p-reachtime); p-cltime=(float)(p-cycletime/p-needtime); T1+=p-cycletime; T2+=p-cltime; disp(p,m); /调用disp()函数,显示作业运行情况 times+=p-needtime; p-state=F; printf(n%s has been finished!npress any key to continue.n,p-name); free(p); /释放运行后的作业 getch();void super() /计算队列中作业的高响应比 JCB *padv; padv=ready; do if(padv-state=W&padv-reachtimesuper=(float)(times-padv-reachtime+padv-needtime)/padv-needtime; padv=padv-next; while(padv!=NULL);void final() /最后打印作业的平均周转时间,平均带权周转时间 float s,t; t=T1/n; s=T2/n; getch(); printf(nn作业已经全部完成!); printf(n%d个作业的平均周转时间是：%f,n,t); printf(n%d个作业的平均带权周转时间是%f：nnn,n,s); void hrn(int m) /高响应比算法 JCB *min; int i,iden; system(cls); inital(); for(i=0;istate=W&p-reachtimesupermin-super) min=p; p=p-next; while(p!=NULL); if(iden) i-;times+; /printf(ntime=%d:tno JCB submib.wait.,time); if(times1000)printf(nruntime is too long.error.);getch(); else running(min,m); /调用running()函数 /for final(); /调用running()函数void sjf(int m) / 最短作业优先算法 JCB *min; int i,iden; system(cls); inital(); for(i=0;istate=W&p-reachtimeneedtimeneedtime) min=p; p=p-next; while(p!=NULL) ; if(iden) i-; /printf(ntime=%d:tno JCB submib.wait.,time); times+; if(times100)printf(nruntime is too long.error);getch(); else running(min,m); /调用running()函数 /for final(); /调用running()函数void fcfs(int m) /先来先服务算法 int i,iden; system(cls); inital(); for(i=0;istate=W&p-reachtimenext; while(p!=NULL&iden) ; if(iden) i-; printf(n没有满足要求的进程,需等待); times+; if(times100)printf(n时间过长);getch(); else running(p,m); /调用running()函数 final(); /调用running()函数void mu