兰州理工大学—操作系统课设—作业调度模拟程序说明书

1 目目 录录 前前 言言.2 摘摘 要要.3 正正 文文.4 1.设计思想.4 2.算法用到的主要数据结构（采用类C语言定义）.5 3.相关的各模块的伪码算法.5 4.调试分析.8 5.测试结果.14 6.源程序（带注释）.15 总总 结结.24 参考文献参考文献.25 致致 谢谢.26 2 前前 言言 每个用户请求计算机计算的一个计算任务叫做一个作业。一个作业从输入初 始数据到得到计算结果，要经过若干个步骤的相继执行。例如：编辑、编译、运 行等，其中每一个步骤称作一个作业步。用户向系统提出作业加工步骤的方式称 作业控制方式，作业控制方式有两种：终端控制方式（又称直接控制方式或联机 控制方式）和批处理控制方式（又称自动控制方式或脱机控制方式） 。 在批处理控制方式下，用户采用系统提供的作业控制语言（JCL）写好作业 说明书，说明作业加工的步骤。操作员把一批作业组织成输入流，通过“预输入” 手段使每个作业的信息（包括作业说明书、源程序、初始数据等）暂存在辅助存 储器的“输入井”中。 批处理多道程序操作系统的作业管理有两个任务：作业调度和作业控制。采 用多道程序设计方法的操作系统，在系统中要经常用保留多个运行的作业，以提 高系统效率。作业调度从系统已接纳的作业分配所需的系统资源。对被选中运行 的作业按照它们各自的作业说明书中规定的步骤进行控制。 3 摘摘 要要 对于成批进入系统的作业来说，根据作业控制块信息，按照一定的策略选取 若干个作业使它们可以去获得处理器运行，这项工作称为作业调度。而对于每个 用户来说，总希望自己的作业的周转时间尽可能小，最理想的情况是进入系统后 能立即运行，即希望作业的周转时间等于执行时间。对于系统来说，则希望进入 系统的作业的平均周转时间尽可能的小，是的 CPU 的利用率尽量高。于是，每 个计算机系统都必须选择适当的作业调度算法，既考虑用户的要求又要有利于系 统效率的提高。当选中一个作业后，首先要建立此作业的用户进程，同时为其分 配系统资源，接着就可以投入运行。当一个作业执行结束进入完成状态时，负责 收回资源，撤销其作业控制块。 本课设则模拟了作业调度的实现，通过 FCFS、SJF、HRF 几种算法的实现， 说明了作业调度在操作系统中的作用。 关键字：作业；调度；FCFS；SJF；HRF 4 正正 文文 1.1. 设计思想设计思想 作业调度是操作系统非常重要的内容，选择合适的算法可以提高计算机的运 行效率。根据操作系统的学习，我们采用 FCFS、SJF、HRF 算法各自处理相同的 作业，对比各自的平均周转时间和平均代权周转时间。 建立作业的控制块信息，利用多道程序设计，采用不同的策略运行，观察各 算法的优略性。 1.1 各模块及程序流程图 输入作业 J0J1J2J3 选择算法 FCFSSJFHRF 执行执行执行 打印结果 5 2.2. 算法用到的主要数据结构（采用类算法用到的主要数据结构（采用类 c c 语言定义）语言定义） 2.1 运行时间等控制块 struct worktime float Tb; /作业运行时刻 float Tc; /作业完成时刻 float Ti; /周转时间 float Wi; /带权周转时间 ; 2.2 作业控制块信息 struct jcb /*定义作业控制块 JCB */ char name10; /作业名 float subtime; /作业提交时间 float runtime; /作业所需的运行时间 / char resource; /所需资源 float Rp; /后备作业响应比 char state; /作业状态 struct worktime wt; struct jcb* link; /链指针 *jcb_ready=NULL,*j; 3.3. 相关的各模块的伪码算法相关的各模块的伪码算法 3.1 FCFS 算法的伪码算法 typedef struct jcb JCB; float T=0; void sort() /* 建立对作业进行提交时间排列函数*/ JCB *first, *second; 6 int insert=0; if(jcb_ready=NULL)|(j-subtime)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)subtime) /*若插入作业比当前作业提交 时间短,*/ /*插入到当前作业前面*/ j-link=second; first-link=j; second=NULL; insert=1; else /* 插入作业优先数最低,则插入到队尾*/ first=first-link; second=second-link; if (insert=0) first-link=j; 7 3.2 SJF 伪码算法 void SJFget()/* 获取队列中的最短作业 */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (rear!=NULL) mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_ready; jcb_ready=mintime; 3.3 HRF 算法的伪码算法 void HRNget()/* 获取队列中的最高响应作业 */ 8 JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (rear!=NULL) mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_ready; jcb_ready=mintime; 4.4. 调试分析调试分析 1、FCFS 1.1 根据提示并输入作业数。 9 1.2 输入第一号作业的作业名。 1.3 输入第二号作业的作业名。 10 1.4 输入第三号作业的作业名。 1.5 输入第四号作业的作业名。 11 1.6 选择作业调度算法。 1.7 选择 FCFS 算法，并执行完第一个作业。 12 1.8 执行完第二个作业。 1.9 执行完第三个作业。 13 1.10 执行完第四个作业。 1.11 显示所有作业执行完之后的平均周转时间和带权平均周转时间。 14 FCFS 算法作业调度测试完成，根据以上方法测试 SJF 和 HRF 算法的作业调 度。 5.5. 测试结果测试结果 一、FCFS 二、SJF 15 三、HRF HRF 算法下的作业调度结果如下。 6.6. 源程序（带注释）源程序（带注释） #include stdio.h #include #include 16 #define getpch(type) (type*)malloc(sizeof(type) /#define NULL 0 struct worktime float Tb; /作业运行时刻 float Tc; /作业完成时刻 float Ti; /周转时间 float Wi; /带权周转时间 ; struct jcb /*定义作业控制块 JCB */ char name10; /作业名 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)subtime) /*作业提交时 间最短的,插入队首*/ 17 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)subtime) /*若插入作业比当前作业提交 时间短,*/ /*插入到当前作业前面*/ j-link=second; first-link=j; second=NULL; insert=1; else /* 插入作业优先数最低,则插入到队尾*/ first=first-link; second=second-link; if (insert=0) first-link=j; 18 void SJFget()/* 获取队列中的最短作业 */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (rear!=NULL) mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_ready; jcb_ready=mintime; void HRNget()/* 获取队列中的最高响应作业 */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; 19 rear=mintime-link; while(rear!=NULL) if (rear!=NULL) mintime=rear; rear=rear-link; ipmove=1; else rear=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, for(i=0;iname); printf(n 输入作业提交时刻:); 20 scanf(%f, printf(n 输入作业运行时间:); scanf(%f, 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( |%st,jr-name); printf( |%.2ft ,jr-runtime); if (select=3) printf( |%.2f ,jr-Rp); 21 if (j=jr) printf( |%.2ft,jr-wt.Tb); printf( |%.2f ,jr-wt.Tc); printf( |%.2f t,jr-wt.Ti); printf( |%.2f,jr-wt.Wi); printf(n); void destroy() /*建立作业撤消函数(作业运行结束,撤消作业)*/ printf(n 作业 %s 已完成.n,j-name); free(j); 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(); 22 void running(JCB* jr) /* 建立作业就绪函数(作业运行时间到,置就绪状态*/ if (T=jr-subtime) jr-wt.Tb=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; void main() /*主函数*/ int select=0,len,h=0; float sumTi=0,sumWi=0; input(); len=space(); printf(nt1.FCFS 2.SJF 3.HRNnn 请选择作业调度算法:?); scanf(%d, while(len!=0) 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 23 if (select=3 printf(n 按任一键继续.n); getchar(); getchar(); printf(nn 作业已经完成.n); printf(t 此组作业的平均周转时间：%.2fn,sumTi/h); printf(t 此组作业的带权平均周转时间：%.2fn,sumWi/h); getchar(); 24 总总 结结 本次课设主要通过程序模拟实现批处理多道程序操作系统的作业调度。在课 设中遇到的主要问题有： 1、由于对设计要求理解的偏差，程序在执行过程中，用户每选择一个作业， 就要选择一次算法，这样是与实际情况不符的。通过分析程序，将程序改正过来， 即先选择算法，再进行作业的调度。 2、调试问题。由于程序比较长，出现错误调试起来很不方便，但通过单步 调试和分析都一一改正过来。 在课设过程中，我对操作系统有了更进一步的认识，尤其对作业调度问题， 进一步认识了作业在进程中的调度过程和执行过程。本次课设