操作系统设计性实验报告-作业调度算法.docx

课题：作业调度算法班级：1620702姓名：黄钰量学号：201620130408时间：11月27日（在小组中负责时间片轮调度算法）目录：一、实验目的二、实验内容三、实验设计方案及其原理四、实验代码五、实验结果六、实验总结概述：调度算法是指：根据系统的资源分配策略所规定的资源分配算法，如任务A在执行完后，选择哪个任务来执行，使得某个因素（如进程总执行时间，或者磁盘寻道时间等）最小。对于不同的系统目标，通常采用不同的调度算法。1、 实验目的1.用高级语言编写和调试单道环境下的作业调度的模拟程序，以加深对作业调度的理解。单道环境的特点是被调度的作业占有所有资源。2.在完成了单道环境的作业调度后，有余力的同学可以完成多道环境下的作业调度，多道的特点是：内存中可以同时存在一道以上的进程，所有进程共享系统资源，这样作业调度过程中还要考虑资源分配情况。3.通过两种环境下作业调度的模拟，比较两种环境下作业调度的异同，从而达到理解作业调度的功能。2、 实验内容 1.常见的作业调度算法有：（1） 短作业（进程）优先调度算法（SJF:Shorest Job First）（2） 时间片轮转算法(RR: Round Robin)（3） 动态优先级算法2.由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的CPU时限等因素。每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W（wait）、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。3.在批处理系统中，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求，所需要的资源是否得到满足。作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理机运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业要求，那么，作业调度必须按一定的算法在这些作业中作出选择。当作业正常运行完毕或因发生错误非正常终止时，作业进入完成状态，此时，系统将收回该作业所占用的全部资源，并清除有关的JCB。并输出显示作业运行情况及作业输出结果。三、实验设计方案及其原理假设在单道批处理环境下有四个作业JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用短作业（进程）优先调度算法（SJF：Shorest Job First），时间片轮转算法（RR: Round Robin），动态优先级算法计算出作业的平均周转时间和带权的平均周转时间。1.时间片轮调度算法： 用法描述： 用于分时系统中的进程调度。 算法介绍：在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。原理： 每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。执行时间例图：根据执行时间图就可以计算各个进程的带权周转时间和平均带权周转时间了。带权周转时间和平均带权周转时间的算术公式：带权周转时间W，即：W = T/R其中T为周转时间，R为实际运行时间。平均带权周转时间为：采用时间片轮调度算法，算法的性能指标如下：本次实验的流程图：四、实验代码#include #include #include #include #define N 20struct pcbchar name8; /进程名称int arrive_time; /到达时间int run_time; /运行时间int finish_time; /完成时间 int zhouzhuan_time; /周转时间float daiquan_time; /带权周转时间 bool finished; /是否运行完成pcbN; typedef struct node char name20; /进程的名字 int prio; /进程的优先级 int round;/分配cpu的时间片 int cputime;/cpu执行时间 int needtime;/进程执行所需要的时间 char state;/进程的状态，w 就绪态，R 执行态，F 完成态 int count;/记录执行次数 struct node *next;/链表指针PCB; PCB *ready=NULL,*run=NULL,*finish=NULL; int num; void GetFirst();/从就绪队列取得第一个节点void Output();/输出队列信息void InsertPrio(PCB *in); /创建优先级队列，优先数越小，优先级越高void InsertTime(PCB *in); /时间片队列 就绪队列void InsertFinish(PCB *in); /时间片队列 完成队列void PrioCreate();/优先级输入函数void TimeCreate();/时间片输入函数void Priority();/按照优先级调度void RoundRun();/时间片轮转调度void input();void output();void SJF(); int main(void) printf(-n);printf(-欢迎使用本系统-n);printf(- 本系统提供的调度算法有： -n);printf(- P. 动态优先级算法 -n);printf(- R. 时间片轮转算法 -n);printf(- S. 短进程优先算法 -n);printf(-n); char chose; printf(请输入要创建的进程数目:n); scanf(%d,&num); getchar(); printf(输入进程的调度方法：(PRS)n); scanf(%c,&chose); switch(chose) case P: case p: PrioCreate(); Priority(); Output(); break; case R: case r: TimeCreate(); RoundRun();Output();break; case S: case s: SJF(); break; default:break; return 0; void Output() PCB *p; p = ready; printf(进程名t优先级t轮数tcpu时间t需要时间t进程状态t计数器n); while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; p = finish; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; p = run; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; void InsertPrio(PCB *in) PCB *fst,*nxt; fst = nxt = ready; if(ready = NULL) in-next = ready; ready = in; else if(in -prio = fst -prio) in-next = ready; ready = in; else while(fst-next != NULL) nxt = fst; fst = fst-next; if(fst -next = NULL) in -next = fst -next; fst -next = in; else nxt = in; in -next = fst; void InsertTime(PCB *in) PCB *fst; fst = ready; if(ready = NULL) in-next = ready; ready = in; else while(fst-next != NULL) fst = fst-next; in -next = fst -next; fst -next = in; void InsertFinish(PCB *in) PCB *fst; fst = finish; if(finish = NULL) in-next = finish; finish = in; else while(fst-next != NULL) fst = fst-next; in -next = fst -next; fst -next = in; void PrioCreate() PCB *tmp; int i; printf(输入进程名字和进程所需时间：n); for(i = 0;i name); getchar(); scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 50 - tmp-needtime; tmp -round = 0; tmp -count = 0; InsertPrio(tmp); void TimeCreate() PCB *tmp; int i; printf(输入进程名字和进程时间片所需时间：n); for(i = 0;i name); getchar(); scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 0; tmp -round = 2; tmp -count = 0; InsertTime(tmp); void Priority() int flag = 1; GetFirst(); while(run != NULL) Output(); while(flag) run-prio -= 3; run-cputime+; run-needtime-; if(run-needtime = 0) run -state = F; run-count+; InsertFinish(run); flag = 0; else run-state = W; run-count+; InsertTime(run); flag = 0; flag = 1; GetFirst(); void RoundRun() int flag = 1; GetFirst(); while(run != NULL) Output(); while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) run -state = F; InsertFinish(run); flag = 0; else if(run-count = run-round) run-state = W; run-count = 0; InsertTime(run); flag = 0; flag = 1; GetFirst(); /*插入*/void SJF()input();int i,j,k,min_time,index; int last_finishedPCB_index; /记录上一次已经运行的进程的数组下标float zhouzhuanhe_time=0 ; /周转时间之和float daiquanhe_time=0;/ 运行第一个到达的进程 得到它的完成时间、周转时间等,并设置为已访问 pcb0.finish_time=pcb0.arrive_time+pcb0.run_time; pcb0.zhouzhuan_time=pcb0.finish_time-pcb0.arrive_time; pcb0.daiquan_time=(float)pcb0.zhouzhuan_time/pcb0.run_time;/带权周转时间 pcb0.finished=true; last_finishedPCB_index=0;/下面在剩下的进程中循环找出运行时间最小的进程，/计算它的完成时间、周转时间等，并设置为已访问。 for(i=0;inum;i+) /先找出没有访问过的运行时间最小的进程的下标 index=-1; min_time=100; for(j=0;jnum;j+) if(pcbj.arrive_timepcbj.run_time&pcbj.finished=false)min_time=pcbj.run_time;index=j; /运行找到的最短进程 得到它的完成时间、周转时间等,并设置为已访问 pcbindex.finish_time=pcblast_finishedPCB_index.finish_time+pcbindex.run_time; pcbindex.zhouzhuan_time=pcbindex.finish_time-pcbindex.arrive_time; pcbindex.daiquan_time=(float)pcbindex.zhouzhuan_time/pcbindex.run_time;/带权周转时间 pcbindex.finished =true; last_finishedPCB_index=index; for(i=0;i=pcblast_finishedPCB_index.finish_time)/检测是否有进程未运行并且到达时间大于最后一个进程的完成时间 pcbi.finish_time=pcbi.arrive_time+pcbi.run_time; pcbi.zhouzhuan_time=pcbi.finish_time-pcbi.arrive_time; pcbi.daiquan_time=(float)pcbi.zhouzhuan_time/pcbi.run_time;/带权周转时间 pcbi.finished=true; last_finishedPCB_index=i; if(pcbi.finished=false&pcbi.arrive_timepcblast_finishedPCB_index.finish_time)/进程未运行且到达时间小于最后一个进程的完成时间 pcbi.finish_time=pcblast_finishedPCB_index.finish_time+pcbi.run_time; pcbi.zhouzhuan_time=pcbi