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

计算机 学院 计算机科学与技术 专业 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）调度算法，计算出作业的平均周转时间和带权的平均周转时间 。作业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算法: 结束开始初始化所有的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)+YN2.多道作业调度算法开始初始化JCB，使作业按到达时间大小排列计算剩下资源输入井空？N进入输入井中调度作业剩下资源满足先进入输入井的作业的要求Y作业调到内存，成为正在运行的作业运行时间服务时间Y释放资源继续执行N这作业插在输入井尾部判断下一个作业NY结束五、给出程序中源程序名和执行程序名：源程序名：FCFS and SJF,执行程序名：fcfs and sjf.cpp源程序名：DUODAO 执行程序名：duodao.cpp六、程序清单1.FCFS和SJF算法#include stdio.h#include #include #define getpch(type) (type*)malloc(sizeof(type)struct jcb char name10; char state; int atime;/作业到达时间 int btime;/作业开始运行时间 int ftime;/作业完成时间 int ntime;/作业估计运行时间 int rtime;/作业执行时间 int ttime;/周转时间 float wtime;/带权周转时间(周转时间/估计运行时间） struct jcb* link;*ready=NULL, *p;/ready指向队头，p指向正被调度的作业typedef struct jcb JCB; int T=0; /初始化时间量 float total;/记录所有作业的总时间 double weight;/记录所有作业的带权周转时间 void sort() /* 建立对作业进行到达时间排列函数*/ JCB *first, *second; int insert=0; if(ready=NULL)|(p-atime)atime) /*作业到达时间最短的,插入队首*/ p-link=ready; ready=p; T=p-atime; /更改时间量 else /* 作业比较到达时间,插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) if(p-atime)atime) /*若插入作业比当前队尾作业到达时间短,*/ /*插入到当前队尾作业前面*/ p-link=second; first-link=p; second=NULL; insert=1; else /* 插入作业到达时间最长,则插入到队尾*/ first=first-link; second=second-link; if (insert=0) first-link=p; void shortjob() / 获取队列中的最短作业 JCB *pr,*min,*qr; min=ready;/min指向作业对头 qr=ready; pr=ready-link;while(pr!=NULL) if(pr!=NULL)&(T=pr-atime)&(pr-ntime)ntime) /当插入作业到达时间要比时间量T小 min=pr; /min指向pr qr-link=pr-link;/qr的下一个指向pr的下一个 pr-link=ready; pr=pr-link; else /当pr的需要时间不小于min的需要时间 qr=pr; pr=pr-link; ready=min;/把最终获取的min的需要时间赋给ready，开始执行 void input() /*建立作业控制块函数*/ int i; printf(n 请输入4个作业：); for(i = 0; i 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(); int space() /*查看作业个数*/ int l = 0; JCB *pr = ready; while(pr != NULL) l+; pr = pr-link; return(l);void disp(JCB *pr) /*建立作业显示函数，用于显示当前作业*/ printf(n qname t state t atime t ntime t btime t rtime t ftime t ttime t wtime 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);void check() /* 建立作业查看函数 */ JCB* pr; printf(n * 当前正在运行的作业是:%s,p-name); /*显示当前运行作业*/ disp(p); pr=ready; printf(n *当前就绪队列状态为:n); /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr-link; void destroy() printf(n 作业%s 已完成。n,p-name); free(p);void running(JCB *pr) /计算各个时间 if(T=pr-atime) pr-btime=T;/插入作业的到达时间比时间量小，T为该作业的开始时间else pr-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为该上一个作业的完成时间void running1(JCB *pr) /分离出要执行的当前作业 if(T=pr-atime) pr-btime=T;else pr-btime=pr-atime;void running2(JCB *pr) /判断运行时间和需要运行时间的关系 while(pr-rtimentime) pr-state = R; (pr-rtime)=(pr-ntime); printf(nn *该作业执行完毕时的状态：n); pr-state=F; disp(pr); destroy();int main() int i,len, h = 0; char ch; total=0; weight=0; printf(*n); printf( n); printf( FCFS算法或SJF算法 n); printf(*n); input(); len = space(); printf(n选择算法: ); scanf(%d,&i); switch(i) case 1: printf(FCFS算法：n);break; case 2: printf(SJF算法：n);break; default:printf(FAULSE); if(i=1|i=2) while(len != 0) & (ready != NULL) ch = getchar(); if(i=2) shortjob(); h+; printf(n The execute number:%dn,h); p = ready; /*将队首指针赋给p*/ ready = p-link; /*ready指向原p的下一个进程*/ p-link = NULL; /*p的link赋空*/ p-state = R; p-btime=p-atime; running1(p); check(); running(p); running2(p); printf(n 按任一键继续.); ch = getchar(); printf(nn作业已完成。n); ch = getchar(); printf(n*n); printf(n平均周转时间：%f,total/(float)4); printf(n平均带权周转时间：%lf,weight/(float)4); printf(n*n); 2.多道作业调度算法：#include stdio.h#include #include #define getpch(type) (type*)malloc(sizeof(type)#define source 15struct jcb char username10; char jobname10; char state; int atime;/作业到达时间 int ntime;/作业估计运行时间 int rtime; /作业的运行时间 int nsource;/作业所需系统资源 int asource;/已分配的资源 int need1; struct jcb* link;*ready=NULL, *p;/ready指向就绪队列的队头，p指向正被调度的作业typedef struct jcb JCB; int rsource=15;/剩下资源int num,i=0;/num为作业个数，i为记录不能满足作业要求调度的次数void destroy(JCB *pr) free(pr);void sort() /* 建立对作业进行到达时间排列函数*/ JCB *first, *second; int insert=0; if(p-nsource=0)&(p-nsourcep-asource) /需要资源要在系统资源范围内，分配资源要在需要资源范围内，剩下资源不能小于0 if(ready=NULL)|(p-atime)atime) /*作业到达时间最短的,插入队首*/ p-link=ready; ready=p; else /* 作业比较到达时间,插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) if(p-atime)atime) /*若插入作业比当前队尾作业到达时间短,*/ /*插入到当前队尾作业前面*/ p-link=second; first-link=p; second=NULL; insert=1; else /* 插入作业到达时间最长,则插入到队尾*/ first=first-link; second=second-link; if (insert=0) first-link=p; else destroy(p); void sort1() /*对作业进行排列函数 */ JCB *first; if(ready=NULL) /*如果就绪队列为空*/ ready=p; /*将新建作业放入队列中，将ready指向队首作业 */ else /*队列中有作业在等待，将新建作业插入到队尾 */ first=ready; /*first指针指向队首作业 */ while(first-link!=NULL) first=first-link; /*当first指针没有指向队尾时，指针后移 */ first-link=p;/*将p指向的作业插入队尾*/ void input() /*建立作业控制块函数*/ int i; printf(n 请输入作业个数:); scanf(%d,&num); for(i=0;iusername); printf(n输入作业名:); scanf(%s,p-jobname); printf(n输入作业到达时间:); scanf(%d,&p-atime); printf(n 输入作业运行时间:); scanf(%d,&p-ntime); printf(n 输入作业所需资源:); scanf(%d,&p-nsource); printf(n 输入作业已分配资源:); scanf(%d,&p-asource); printf(n); p-need1=p-nsource-p-asource;/还需要资源=需要资源-已分配资源 p-state=W; p-link=NULL; sort(); int space() /*查看作业个数*/ int l=0; JCB *pr=ready; while(pr!=NULL) l+; pr=pr-link; return(l);void disp(JCB *pr) /*建立作业显示函数，用于显示当前作业*/ printf(n 用户N t 作业N t 状态S t 到达T t 服务T t 所需S t 已分S t 还需S n); printf( |%s t,pr-username); printf( |%s t,pr-jobname); printf( |%c t,pr-state); printf( |%d t,pr-atime); printf( |%d t,pr-ntime); printf( |%d t,pr-nsource); printf( |%d t,pr-asource); printf( |%d t,pr-need1); printf(n);void check() JCB *pr; printf(n*当前正在运行的作业是：%s,p-jobname); disp(p); pr=ready; printf(n*当前输入井队列状态为：n); /*显示就绪队列状态*/ while(pr != NULL) disp(pr); pr = pr-link; void running(JCB *p)/对输入井队列中满足资源要求的作业进行服务 while(p-rtimentime) (p-rtime)+; p-state=F; printf(n*作业运行完成后状态:n); disp(p); printf(n 用户名%s的作业%s 已完成。n,p-username,p-jobname); void running1()/ 计算剩下资源 JCB *pr; for(pr=ready;pr!=NULL;pr=pr-link) rsource=rsource-pr-asource;void running2(JCB *pr) if(pr-need1need1; pr-asource+=pr-need1; pr-need1 =0; printf(t*n); printf(n分配给作业后所剩的资源是：%d n,rsource); running(pr); rsource = rsource + pr-nsource; printf(n释放后的资源是：%dn,rsource); destroy(pr); else printf(该作业不能满足要求，调度下一个作业); sort1(); i+; void main() int len, h=0;/h表示执行的次数 int flag=0;/用来记录排在前面却没被调用的作业个数 char ch; printf(*n); printf( n); printf( 多道作业调度算法 n); printf(*n); input(); len = space(); running1(); if(rsource=0) while(ilink; p-link=NULL; p-state =R; running2(p); printf(n 按任一键继续.); ch=getchar(); if(i2) printf(n*剩下系统资源不能满足作业需要要求了n); printf(n*退出程序); else printf(n作业已完成n); ch=getchar(); else printf(nn*因为输入已分配的资源与系统资源不符合错误，所以退出程序*);七、运行结果1FCFS算法2.SJF算法3.多道作业调度算法八、结果分析与调试过程小结在调试FCFS算法中重要的是怎么按到达时间先后插入就绪队列，其中还要考虑到当前有进程在运行的情况的。但由于进程是先来先服务的，所以需要定义另一指针first来确定要进来的进程插入的位置。在调试SJF算法中，它是基于FCFS算法的基础上，利用shortjob()来查询已排好队的作业中所需运行时间最短的作业，从而把把它指向ready指针的，但由于一开始遗忘了C语言中指针的链接，导致程序出现了了一系列的问题，如无法出现JCB控制块等等。在多道作业调度中我总共想到了三个问题，第一个是输入的信息中要防止出错，就用来if(p-nsource=0)&(p-nsourcep-asource)来判断，如果有错就不让它进入输入井；第二个是当第一个先到作业因为不能满足要求而不能执行时如何处置，怎么再次调用它，就再调用一次sort()函数；第三个是在第二问题上因为调用了sort(),会导致不能满足要求的作业一直重复着判断作业这一步骤，也就出现了死循环。我想了很久只找到了个愚蠢的办法，就是每次调用作业若不能满足要求，都用i来记录着，然后给定条件（i=2*作业个数）来缩短循环次数。十、思考题1、写出每种算法的调度策略，最后比较各种算法的优缺点。答：先来先服务算法是根据作业的到达时间先后来排序,到达时间短的先运行，优点是实现简单，利于长作业，缺点是运行时间慢，不利于短作业。短作业优先算法是先根椐作业的到达时间先后来排序，然后查找所需运行时间短的先运行，优点是运行时间快,缺点是实现起来比较复杂，对长作业不利。2、选择调度算法的依据是什么？答：如果作业要求的速度不高，而且作业比较小型，那就最好用先来先服务算法。