操作系统作业调度实验报告-多道批处理

1计算机学院计算机科学与技术专业07班姓名学号教师评定_________________实验题目作业调度一、实验目的本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。二、实验内容和要求1、为单道批处理系统设计一个作业调度程序(1)、编写并调试一个单道处理系统的作业调度模拟程序。(2)、作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）的调度算法。(3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的CPU时限等因素。(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。2、模拟批处理多道操作系统的作业调度（1）写并调试一个作业调度模拟程序。（2）作业调度算法：分别采用先来服务（FCFS）调度算法。（3）在批处理系统中，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求，所需要的资源是否得到满足。作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理机运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业要求，那么，作业调度必须按一定的算法在这些作业中作出选择。当作业正常运行完毕或因发生错误非正常终止时，作业进入完成状态，此时，系统将收回该作业所占用的全部资源，并清除有关的JCB。并输出显示作业运行情况及作业输出结果。三、实验设计方案及原理假设在单道批处理环境下有四个作业JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务（FCFS），最短作业优先（SJF）调度算法，2计算出作业的平均周转时间和带权的平均周转时间。作业p的周转时间：p-ttime=p-ftime-p-atime作业的平均周转时间：total=全部进程的周转时间/进程个数作业p的带权周转时间：p-wtime=p-ttime/p-ntime作业的平均带权周转时间：W=全部进程的带权周转时间/进程个数1、先来先服务调度算法（FCFS）：每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，这每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。2、最短作业优先（SJF）：每次从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。3、多道作业调度算法：将作业按FCFS原则排好队，在输入井中按作业到达的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业，把不能满足要求的放回输入井尾部等待，当作业执行结束进入完成状态时，做好释放资源等善后工作。四、流程图1、FCFS算法和SJF算法:3结束开始初始化所有的JCB,使JCB按作业到达时间的先后顺序排队，队首指针ready，并初始化时间T=0调度队首的作业投入运行（更改队首指针，使作业的状态为R，记住作业开始运行的时刻btime等）计算并打印运行作业P的完成时间ftime，周转时间ttime，带权周转时间wtime（ftime=btime+ntime;ttime=ftime-atime;wtime=ttime/ntime）更改时间量T的值(T=ftime)选择算法i==1FCFS算法i==2SJF算法获取所需运行时间最短的作业就绪队列空？计算并打印这组作业的平均周转时间及带权平均周转时间空i==1i==2运行时间是否等于所需时间撤销进程，指向下一进程继续执行该进程(p-rtime)++YN42.多道作业调度算法五、给出程序中源程序名和执行程序名：源程序名：FCFSandSJF,执行程序名：fcfsandsjf.cpp源程序名：DUODAO执行程序名：duodao.cpp六、程序清单1.FCFS和SJF算法开始初始化JCB，使作业按到达时间大小排列计算剩下资源输入井空？N进入输入井中调度作业剩下资源满足先进入输入井的作业的要求Y作业调到内存，成为正在运行的作业运行时间服务时间Y释放资源继续执行N这作业插在输入井尾部判断下一个作业NY结束5#includestdio.h#includestdlib.h#includeconio.h#definegetpch(type)(type*)malloc(sizeof(type))structjcb{charname[10];charstate;intatime;//作业到达时间intbtime;//作业开始运行时间intftime;//作业完成时间intntime;//作业估计运行时间intrtime;//作业执行时间intttime;//周转时间floatwtime;//带权周转时间(周转时间/估计运行时间）structjcb*link;}*ready=NULL,*p;//ready指向队头，p指向正被调度的作业typedefstructjcbJCB;intT=0;//初始化时间量floattotal;//记录所有作业的总时间doubleweight;//记录所有作业的带权周转时间voidsort()/*建立对作业进行到达时间排列函数*/{JCB*first,*second;intinsert=0;if((ready==NULL)||((p-atime)(ready-atime)))/*作业到达时间最短的,插入队首*/{p-link=ready;ready=p;T=p-atime;//更改时间量}else/*作业比较到达时间,插入适当的位置中*/{first=ready;second=first-link;while(second!=NULL){if((p-atime)(second-atime))/*若插入作业比当前队尾作业到达时间短,*/{/*插入到当前队尾作业前面*/p-link=second;first-link=p;second=NULL;6insert=1;}else/*插入作业到达时间最长,则插入到队尾*/{first=first-link;second=second-link;}}if(insert==0)first-link=p;}}voidshortjob()//获取队列中的最短作业{JCB*pr,*min,*qr;min=ready;//min指向作业对头qr=ready;pr=ready-link;while(pr!=NULL){if((pr!=NULL)&&(T=pr-atime)&&(pr-ntime)(min-ntime)){//当插入作业到达时间要比时间量T小min=pr;//min指向prqr-link=pr-link;//qr的下一个指向pr的下一个pr-link=ready;pr=pr-link;}else//当pr的需要时间不小于min的需要时间{qr=pr;pr=pr-link;}ready=min;//把最终获取的min的需要时间赋给ready，开始执行}}voidinput()/*建立作业控制块函数*/{inti;printf(\n请输入4个作业：);for(i=0;i4;i++){printf(\n请输入作业号NO.%d：\n,i);p=getpch(JCB);printf(输入作业名：);7scanf(%s,p-name);printf(\n输入作业到达时间：);scanf(%d,&p-atime);printf(\n输入作业运行时间：);scanf(%d,&p-ntime);printf(\n);p-rtime=0;p-btime=0;p-ftime=0;p-ttime=0;p-wtime=0;p-state='W';p-link=NULL;sort();}}intspace()/*查看作业个数*/{intl=0;JCB*pr=ready;while(pr!=NULL){l++;pr=pr-link;}return(l);}voiddisp(JCB*pr)/*建立作业显示函数，用于显示当前作业*/{printf(\nqname\tstate\tatime\tntime\tbtime\trtime\tftime\tttime\twtime\n);printf(|%s\t,pr-name);printf(|%c\t,pr-state);printf(|%d\t,pr-atime);printf(|%d\t,pr-ntime);printf(|%d\t,pr-btime);printf(|%d\t,pr-rtime);printf(|%d\t,pr-ftime);printf(|%d\t,pr-ttime);printf(|%.2f\t,pr-wtime);printf(\n);}8voidcheck()/*建立作业查看函数*/{JCB*pr;printf(\n****当前正在运行的作业是:%s,p-name);/*显示当前运行作业*/disp(p);pr=ready;printf(\n****当前就绪队列状态为:\n);/*显示就绪队列状态*/while(pr!=NULL){disp(pr);pr=pr-link;}}voiddestroy(){printf(\n作业[%s]已完成。\n,p-name);free(p);}voidrunning(JCB*pr)//计算各个时间{if(T=pr-atime)pr-btime=T;//插入作业的到达时间比时间量小，T为该作业的开始时间elsepr-btime=pr-atime;//否则该作业到达时间为它的开始时间pr-ftime=pr-btime+pr-ntime;pr-ttime=p-ftime-p-atime;pr-wtime=(float)pr-ttime/(float)pr-ntime;total+=pr-ttime;weight+=pr-wtime;T=pr-ftime;//T为该上一个作业的完成时间}voidrunning1(JCB*pr)//分离出要执行的当前作业{if(T=pr-atime)pr-btime=T;elsepr-btime=pr-atime;}voidrunning2(JCB*pr)//判断运行时间和需要运行时间的关系{while(pr-rtimepr-ntime){pr-state='R';(pr-rtime)=(pr-ntime);9}printf(\n\n****该作业执行完毕时的状态：\n);pr-state='F';disp(pr);destroy();}intmain(){inti,len,h=0;charch;total=0;weight=0;printf(***********************************************