作业调度模拟程序设计说明书.doc

1、*实践教学实践教学* 兰州理工大学兰州理工大学计算机与通信学院2012 年秋季学期操作系统原理操作系统原理课程设计课程设计 题 目： 作业调度模拟程序 专业班级： 计算机科学与技术 1 班 姓 名： 陈万鹏 学 号: 10240125 指导教师： 李明 成 绩： 目目 录录前前 言言.2摘要及关键字摘要及关键字.4正正 文文.51。设计思想：.52。用类 C 语言定义相关的数据类型:.73.各模块伪码：.84。调度算法的流程图 ：.105.测试结果：.11总结总结.14参考文献参考文献.16致致 谢谢.17源程序：源程序：.18前前 言言实验设计方案及原理：假设在单道批处理环境下有四个作业 J

2、OB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务（FCFS） ，最短作业优先(SJF） 、响应比高者优先（HRN)的调度算法，计算出作业的平均周转时间和带权的平均周转时间 。 作业 i 的周转时间：Ti=Tci-Tsi作业的平均周转时间：T=作业 i 的带权周转时间：Wi=Ti/Tri作业的平均带权周转时间：W=先来先服务调度算法（FCFS）：每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列.在进程调度中采用 FCFS 算法时,这每次调度是从就绪队列中，选择一个最先进入该队

3、列的进程,为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。短作业(进程）优先调度算法 SJ（P)F,是指对短作业或短进程优先调度的算法。它们可分别用于作业调度和进程调度。该调度算法是从后备（就绪）队列中选择一个或若干个估计运行时间最短的作业（进程）,将它们调度内存运行。响应比高者优先（HRN）：每次从后备队列中选择一个或若干个估计响应比最高的作业,将它们调入内存运行。响应比 Rp=作业响应时间/运行时间 =作业等待时间+作业运行时间 =1+作业等待时间每个作业由一个作业控制块 JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资

4、源、作业状态、链指针等等。 作业的状态可以是等待 W（Wait)、运行 R(Run)和完成 F（Finish)三种状态之一.每个作业的最初状态总是等待 W。 各个等待的作业按照提交时刻的先后次序排队,总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。摘要摘要及关键字及关键字 编写作业调度程序,允许多个作业共行的作业调度程序。进程调度算法 先来先服务调度算法、最短作业优先调度算法、和最高相应比优先调度算法。 设有作业 J0、J1、J2、J3，其估计运行时间分别为 2

5、，20，8，12，打印出三种算法下平均周转时间比较表.根据运行结果分析各个算法的优缺点。关键词：作业关键词：作业 调度调度 先来先服务先来先服务 最短作业优先最短作业优先 最高相应比优先最高相应比优先正正 文文1。设计思想：。设计思想：先来先服务算法比较有利于长作业，而不利于短作业。 （1）短作业（SJF）的调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它能比长作业优先执行。SPF 优先调度算法：是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。为了和 FCFS 调度算法进行比较，我们利用 FCFS 算法

6、中所使用的实例并改用 SJ（P）F 算法重新调度，再进行性能分析。采用 SJF 算法后,不论是平均周转时间还是平均带权周转时间都有较明显的改善,尤其是对短作业 D，其周转时间由 FCFS 算法的 11 降为 SJF 算法中的 3；而平均带权周转时间是从 5.5 降到 1。5。这说明 SJF 调度算法能有效地降低作业的平均等待时间和提高系统的吐量。短作业优先调度算法对比先来先服务，不论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业.该算法对长作业不利,而且未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。 如作业 C 的周转时间由 10 增至 16，带权周转时间由

7、2 增至3。1。更严重的是，如果有一长作业(进程)进入系统的后备队列（就绪队列）,由于调度程序总是优先调度那些（即使是后进来的）短作业(进程） ，将致使长作业（进程）得不到调度。 （2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）,会得到及时处理； （3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。 高响应比优先调度算法在批处理系统中,用作作业调度的短作业优先算法是一个比较好的算法。其主要缺点是作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权机制，并

8、使以速率 a 增加，则长作业在等待一定的时间后，必须有机会分配到处理机。该优先权的变化可描述为： 优先权=（等待时间+要求服务时间)/要求服务时间 由于等待时间加上要求服务时间，就是系统对该作业的响应时间，故该优先权又相当于响应比 Rp = 等待时间加要求服务时间/要求服务时间=响应时间/要求服务时间 由上式可以看出: （1）如果作业的等待时间相同,则要求服务的时间愈短，其优先权愈高,因而该算法有利于短作业; (2）当要求服务的时间相同时，作业的优先权决定于其等待时间，因而实现了先来先服务； （3)对于长作业，当其等待时间足够长时，其优先权便可升到很高,从而也可获得处理机。 该算法既照顾了短作

9、业，又考虑了作业到达的先后顺序,也不会使作业长期得不到服务.因此，该算法实现了一种较好的折衷。当然，再利用该算法时，每要进行调度之前，都需先进行响应应比的计算,这会增加系统的开销。 假设在单道批处理环境下有四个作业 JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务(FCFS） ，最短作业优先（SJF)、响应比高者优先(HRN）的调度算法,计算出作业的平均周转时间和带权的平均周转时间 . 作业 i 的周转时间：Ti=Tci-Tsi 作业的平均周转时间：T= 作业 i 的带权周转时间：Wi=Ti/Tri 作业的平均带权周转时间：W= 先来先服务调度算

10、法（FCFS）:每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业,将它们调入内存，为它们分配资源、创建进程,然后放入就绪队列。 在进程调度中采用 FCFS 算法时，这每次调度是从就绪队列中,选择一个最先进入该队列的进程,为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。 短作业（进程）优先调度算法 SJ(P)F，是指对短作业或短进程优先调度的算法。它们可分别用于作业调度和进程调度.该调度算法是从后备（就绪）队列中选择一个或若干个估计运行时间最短的作业（进程） ，将它们调度内存运行。 响应比高者优先（HRN）：每次从后备队列中选择一个或若干个估计

11、响应比最高的作业，将它们调入内存运行。 响应比 Rp=作业响应时间/运行时间 =作业等待时间+作业运行时间 =1+作业等待时间 每个作业由一个作业控制块 JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待 W（Wait） 、运行 R(Run）和完成 F(Finish)三种状态之一。每个作业的最初状态总是等待 W. 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间

12、、带权平均周转时间.2.用类 C 语言定义相关的数据类型:定义头文件：#include #define getpch(type) （type*)malloc（sizeof(type） ）定义结构体：struct worktime float Tb; /作业运行时刻 float Tc； /作业完成时刻 float Ti; /周转时间 float Wi； /带权周转时间 ；struct jcb /定义作业控制块 JCB char name10； /作业名 float subtime; /作业提交时间 float runtime; /作业所需的运行时间 char resource; /所需资源 fl

13、oat Rp; /后备作业响应比 char state； /作业状态 struct worktime wt； struct jcb* link； /链指针*jcb_ready=NULL,*j；3.各模块伪码：void SJFget(） / 获取队列中的最短作业 JCB front,mintime，*rear;/定义 JCB 指针 int ipmove=0； mintime=jcb_ready; rear=mintime-link; while（rear!=NULL) if（rear！=NULL）&(T=rear-subtime）&(mintime-runtime） (rear-

14、runtime）) /队列不空时，给作业排队 front=mintime； mintime=rear; rear=rearlink; ipmove=1; else rear=rear-link； if （ipmove=1)/队首作业完成，后续作业重新排队 front-link=mintimelink; mintimelink=jcb_ready; jcb_ready=mintime；void HRNget(）/ 获取队列中的最高响应作业 JCB *front，mintime，*rear; int ipmove=0;/初始化 mintime=jcb_ready; rear=mintime-lin

15、k； while(rear!=NULL) if (rear！=NULL)&（T=rear-subtime）(mintime-Rp）link； if (ipmove=1） /队首作业完成,改变指针 frontlink=mintime-link； mintime-link=jcb_ready; jcb_ready=mintime；4.调度算法的流程图 ： 开 始初始化所有的 JCB使 JCB 按作业提交的时刻的先后顺序排队时间量：调度队首的作业投入运行：（更改队首指针,使作业的状态为 R，记住作业开始运行的时刻Tb 等）计算并打印运行作业 i 的完成时刻 Tc，周转时间 Ti，带权周转时间

16、 Wi（完成时刻 Tc=开始运行时刻+运行时间周转时间 Ti=完成时刻提交时刻带权周转时间 Wi=周转时间运行时间)更改时间量 T 的值（T：=T+作业 i 的运行时间）队列为空 ?5.测试结果:计算并打印这组作业的平均周转时间及带权平均周转时间结 束main()Input()FCFS()SJF()HRN()check()disp ()总结总结 短作业(SJF）的调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它能比长作业优先执行。SPF 优先调度算法：是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。为了

17、和 FCFS 调度算法进行比较，我们利用 FCFS 算法中所使用的实例并改用 SJ（P）F 算法重新调度，再进行性能分析。采用 SJF 算法后，不论是平均周转时间还是平均带权周转时间都有较明显的改善，尤其是对短作业 D，其周转时间由 FCFS 算法的 11 降为 SJF 算法中的 3；而平均带权周转时间是从 5.5 降到 1.5.这说明 SJF 调度算法能有效地降低作业的平均等待时间和提高系统的吐量。短作业优先调度算法对比先来先服务，不论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业。该算法对长作业不利，而且未考虑作业的紧迫程度,因而不能保证紧迫性作业会被及时处理.如作业

18、 C 的周转时间由 10 增至 16，带权周转时间由 2 增至 3.1。更严重的是,如果有一长作业（进程）进入系统的后备队列（就绪队列）,由于调度程序总是优先调度那些（即使是后进来的)短作业（进程） ，将致使长作业（进程）得不到调度。（2）该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业（进程） ，会得到及时处理；（3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间,致使该算法不一定能真正做到短作业优先调度。3.高响应比优先调度算法在批处理系统中，用作作业调度的短作业优先算法是一个比较好的算法。其主要缺点是作业的运行得不到保

19、证。如果我们能为每个作业引入前面所述的动态优先权机制，并使以速率 a 增加，则长作业在等待一定的时间后，必须有机会分配到处理机。该优先权的变化可描述为:优先权=（等待时间+要求服务时间）/要求服务时间 由于等待时间加上要求服务时间,就是系统对该作业的响应时间，故该优先权又相当于响应比 Rp=等待时间加要求服务时间/要求服务时间=响应时间/要求服务时间由上式可以看出:（1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业;（2）当要求服务的时间相同时，作业的优先权决定于其等待时间，因而实现了先来先服务；（3）对于长作业，当其等待时间足够长时，其优先权便可升到很高

20、，从而也可获得处理机.该算法既照顾了短作业，又考虑了作业到达的先后顺序，也不会使作业长期得不到服务。因此,该算法实现了一种较好的折衷。当然，再利用该算法时，每要进行调度之前,都需先进行响应应比的计算，这会增加系统的开销。参考文献参考文献1。汤子瀛。 计算机操作系统.西安电子科技大学出版社2.王清，李光明。 计算机操作系统 。冶金工业出版社3。孙中秀等。 操作系统教程.高等教育出版社4。曾明。 linux 操作系统教程.陕西科学技术出版社5.张丽芬，刘利雄。 操作系统教程.清华大学出版社6.孟静.操作系统原理和实例分析.高等教育出版社7.周长林.计算机操作系统教程.高等教育出版社8。张尧学.计算

21、机操作系统教程.清华大学出版社9.任满杰。 操作系统教程 。电子工业出版社致致 谢谢经过两周的上机实践，我的课程设计基本完成了，这次课程设计培养了我耐心、慎密、全面地考虑问题的能力,从而加快了问题解决的速度、提高了个人的工作效率，以及锻炼围绕问题在短时间内得以解决的顽强意志。在编写程序的过程中，我得到了王旭阳老师的指导和孜孜不倦的教诲，在老师的指导下，我的能力得到了提高，同时养成了科学、严谨的作风和习惯。为此我要感谢计通学院开设了这门操作系统课程设计，为我们提供了进一步学习算法、操作系统和巩固 C 语言程序计设这个平台并对王旭阳老师的精心栽培表示衷心的感谢。同时还要感谢对同一题目进行攻关的同学

22、们给予的帮助,没他们的帮助可能有很多问题我个人不能进行很好的解决.在此我对他们帮助给予衷心的感谢。源程序：源程序：#include ”stdio。h” include define getpch（type) (type)malloc（sizeof(type）) struct worktime float Tb； /作业运行时刻 float Tc； /作业完成时刻 float Ti; /周转时间 float Wi； /带权周转时间 ；struct jcb /*定义作业控制块 JCB */ char name10; /作业名 float subtime; /作业提交时间 float runtime

23、； /作业所需的运行时间 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)(（jsubtime） （jcb_ready-subtime)） /*作业提交时间最短的，插入队首*/

24、 jlink=jcb_ready； jcb_ready=j； T=j-subtime; j-Rp=1; else /* 作业比较提交时间,插入适当的位置中*/ first=jcb_ready; second=firstlink； while(second!=NULL) if(（jsubtime） （second-subtime) /*若插入作业比当前作业提交时间短，*/ /*插入到当前作业前面*/ jlink=second; firstlink=j； second=NULL； insert=1; else /* 插入作业优先数最低,则插入到队尾/ first=first-link; secon

25、d=secondlink； if (insert=0) first-link=j； void SJFget()/ 获取队列中的最短作业 */ JCB front,*mintime,rear； int ipmove=0； mintime=jcb_ready; rear=mintimelink; while（rear！=NULL)if(（rear!=NULL）(T=rearsubtime）&（mintimeruntime） （rear-runtime)） front=mintime; mintime=rear; rear=rearlink； ipmove=1; else rear=rear

26、link； if (ipmove=1） frontlink=mintime-link; mintimelink=jcb_ready； jcb_ready=mintime;void HRNget（)/* 获取队列中的最高响应作业 */ JCB front,mintime，*rear； int ipmove=0; mintime=jcb_ready； rear=mintimelink; while(rear！=NULL) if (rear！=NULL)（T=rear-subtime）&（mintimeRp)（rear-Rp)） front=mintime； mintime=rear; re

27、ar=rearlink; ipmove=1; else rear=rearlink； if (ipmove=1） frontlink=mintimelink; mintime-link=jcb_ready； jcb_ready=mintime；void input(） / 建立作业控制块函数*/ int i,num； printf（n 请输入作业数:？”)； scanf（”%d，&num） ； for（i=0;iruntime）; printf(”n”） ； j-state=w； jlink=NULL； sort（）; /* 调用 sort 函数*/ int space（) int l

28、=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(” |st,jrname)； printf(” |%.2ft ”,jrruntime） ； if (select=3） printf（” %。2f ,jr-Rp） ； if (j=jr） printf（” 。2ft”，jr-wt.Tb); printf（” |.2f ,jr-wt。Tc） ； printf（” %。2f t”,jr-wt.Ti）; printf（” |%。2f，jrwt.Wi）; printf(”n） ； void check（int select) /* 建立作业查看函数 / JCB jr; printf(”n * 当前正在运行的作业是:s”,j-name）; /显示当前运行作业*/ disp（j，select）; jr=j