广东工业大学操作系统实验二――作业调度实验

实验二、作业调度实验实验项目名称：作业调度实验实验项目性质：验证性实验所属课程名称：《操作系统》实验计划学时：2学时一、实验目的本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。二、实验内容和要求为单道批处理系统设计一个作业调度程序(1)、编写并调试一个单道处理系统的作业调度模拟程序。(2)、作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。(3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的CPU时限等因素。(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。三、实验设计方案及原理假设在单道批处理环境下有四个作业JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法，计算出作业的平均周转时间和带权的平均周转时间。作业i的周转时间：Ti=Tci-Tpi作业的平均周转时间：T=作业i的带权周转时间：Wi=Ti/Tri作业的平均带权周转时间：W=先来先服务调度算法（FCFS）：每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，这每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。最短作业优先（SJF）：每次从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。响应比高者优先（HRN）：每次从后备队列中选择一个或若干个估计响应比最高的作业，将它们调入内存运行。响应比Rp=作业响应时间/运行时间=作业等待时间+作业运行时间=1+作业等待时间/作业运行时间对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。附件：#includestdio.h#includestdlib.h#includeconio.h#definegetpch(type)(type*)malloc(sizeof(type))#defineNULL0structworktime{floatTb;//作业运行时刻floatTc;//作业完成时刻floatTi;//周转时间floatWi;//带权周转时间};structjcb{/*定义作业控制块JCB*/charname[10];//作业名floatsubtime;//作业提交时间floatruntime;//作业所需的运行时间charresource;//所需资源floatRp;//后备作业响应比charstate;//作业状态structworktimewt;structjcb*link;//链指针}*jcb_ready=NULL,*j;typedefstructjcbJCB;floatT=0;voidsort()/*建立对作业进行提交时间排列函数*/{JCB*first,*second;intinsert=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;}}voidSJFget()/*获取队列中的最短作业*/{JCB*front,*mintime,*rear;intipmove=0;mintime=jcb_ready;rear=mintime-link;while(rear!=NULL)if((rear!=NULL)&&(T=rear-subtime)&&(mintime-runtime)(rear-runtime)){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;}voidHRNget()/*获取队列中的最高响应作业*/{JCB*front,*mintime,*rear;intipmove=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;}voidinput()/*建立作业控制块函数*/{inti,num;printf(\n请输入作业数:?);scanf(%d,&num);for(i=0;inum;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函数*/}}intspace(){intl=0;JCB*jr=jcb_ready;while(jr!=NULL){l++;jr=jr-link;}return(l);}voiddisp(JCB*jr,intselect)/*建立作业显示函数,用于显示当前作业*/{if(select==3)printf(\n作业服务时间响应比运行时刻完成时刻周转时间带权周转时间\n);elseprintf(\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);}intdestroy()/*建立作业撤消函数(作业运行结束,撤消作业)*/{printf(\n作业[%s]已完成.\n,j-name);free(j);return(1);}voidcheck(intselect)/*建立作业查看函数*/{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();}voidrunning(JCB*jr)/*建立作业就绪函数(作业运行时间到,置就绪状态*/{if(T=jr-subtime)jr-wt.Tb=T;elsejr-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;}intmain()/*主函数*/{intselect=0,len,h=0;floatsumTi=0,sumWi=0;input();len=space();printf(\n\t1.FCFS2.SJF3.HRN\n\n请选择作业调度算法:?);scanf(%d,&select);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&&hlen-1)SJFget();if(select==3&&hlen-1)HRNget();printf(\n按任一键继续......\n);getchar();getchar();}printf(\n\n作业已经完成.\n);printf(\t此组作业的平均周转时间：%.2f\n,sumTi/h);printf(\t此组作业的带权平均周转时间：%.2f\n,sumWi/h);getchar();}