OS短作业优先调度算法C语言.doc

采用短作业优先调度算法调度程序学 号： 姓 名： 专 业： 指导老师： 日 期： 目录一、实验题目3二、课程设计的目的3三、设计内容3四、设计要求3五、主要数据结构及其说明4六、程序运行结果5七、流程图7八、源程序文件9九、实验体会13十、参考文献13摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。 本次课程设计主要是模拟短作业优先(SJF)调度算法。一、实验题目 采用短作业优先算法的的进程调度程序二、课程设计的目的l 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。l 进一步巩固和复习操作系统的基础知识。l 培养学生结构化程序、模块化程序设计的方法和能力。l 提高学生调试程序的技巧和软件设计的能力。l 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。三、设计内容设计并实现一个采用短作业优先算的进程调度算法演示程序四、设计要求1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行 （由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 五、主要数据结构及其说明算法的基本概念和原理：本次课程设计主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求立即执行，因而可能造成难以预料的后果。因此，在要求比较严格的实时系统中，不宜采用这种调度方式。本课程设计主要是在满足要求多道单处理机的情况下进行短作业的优先调度。算法的简要说明：短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。优点是SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。缺点是该算法对长作业不利；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）长期不被调度；由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业游戏那调度。 该程序定义了一个进程数据块(struct Process_)，该数据块有进程名(name)、到达时间(arrivetime)、服务时间(servicetime)、开始执行时间(starttime)、完成时间(finishtime)、周转时间(zztime)、带权周转时间(dqzztime)、执行顺序（order）。用到的公式有：完成时间=到达时间+服务时间；周转时间=完成时间+到达时间；带权周转时间=周转时间/服务时间；(第一次执行的进程的完成时间=该进程的到达时间；下一个进程的开始执行时间=上一个进程的完成时间)。运行进程的顺序需要对进程的到达时间和服务时间进行比较。如果某一进程是从0时刻到达的，那么首先执行该进程；之后就比较进程的服务时间，谁的服务时间短就先执行谁（如果服务时间相同则看它们的到达时间，到达时间短的先执行）；如果到达时间和服务时间相同，则按先来先服务算法执行。六、程序运行结果1 进入操作界面如下2输入进程的信息3 各时刻进程的状态4 进程信息5 平均带权周转时间界面七、流程图本次课程设计主要是通过比较各个进程的优先级以及各进程所需要占用的CPU时间来确定哪个作业优先运行，短作业优先调度算法除了能保证优先级更高的作业优先运行外，还能使相同优先级的前提下，所需CPU时间最短的那个作业优先运行，次外，本次课程设计还增加了阻塞时间和被阻塞时间来对个进程的运行加以控制。 此次课程设计的总体流程图如下：开 始输入进程的个数:numr队列中是否只有一个进程？执行时间处理函数：Time()Y 结 束Sort()输入进程的信息:name starttime servicetimeN执行判断函数：Run()输出最后信息：Output()八、源程序文件#include#define MaxNum 100using namespace std; struct Process_structint Number; /进程编号char NameMaxNum; /进程名称 int ArrivalTime; /到达时间int ServiceTime; /开始运行时间int FinishTime; /运行结束时间int WholeTime; /运行时间 int run_flag; /调度标志int order; /运行次序double WeightWholeTime; /周转时间double AverageWT_FCFS,AverageWT_SJF; /平均周转时间 double AverageWWT_FCFS,AverageWWT_SJF; /平均带权周转时间ProcessMaxNum;int N; /实际进程个数int SJF(); /短作业优先int SJF() /短作业优先算法int temp_time=0; /当期那时间int i=0,j;int number_schedul,temp_counter; /进程编号，当前已执行进程个数float run_time;run_time=Processi.WholeTime;j=1;while(jN)&(Processi.ArrivalTime=Processj.ArrivalTime) /判断是否有两个进程同时到达if(Processj.WholeTimeProcessi.WholeTime)run_time=Processi.WholeTime;i=j;j+;/查找下一个被调度的进程/对找到的下一个被调度的进程求相应的参数number_schedul=i;Processnumber_schedul.ServiceTime=Processnumber_schedul.ArrivalTime;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime; Processnumber_schedul.order=1;temp_counter=1;while(temp_counterN)for(j=0;jN;j+)if(Processj.ArrivalTime=temp_time)&(!Processj.run_flag)run_time=Processj.WholeTime;number_schedul=j;break;for(j=0;jN;j+)if(Processj.ArrivalTime=temp_time)&(!Processj.run_flag)if(Processj.WholeTimerun_time)run_time=Processj.WholeTime;number_schedul=j;/查找下一个被调度的进程/对找到的下一个被调度的进程求相应的参数Processnumber_schedul.ServiceTime=temp_time;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime;temp_counter+;Processnumber_schedul.order=temp_counter;return 0;int Pinput(); /进程参数输入int Poutput(); /调度结果输出void main()int option;printf( *主菜单*n);printf( * 1 使用短作业优先 *n);printf( * 0 退出 *n);printf( *n);/system(cls);system(color 1f);scanf(%d,&option);switch(option)case 0:printf(运行结束。n);break;case 1:printf(对进程用短作业优先调度。nn); Pinput();SJF();Poutput();break;int Pinput() /进程参数输入int i;printf(请输入进程个数:n);scanf(%d,&N);for(i=0;iN;i+)printf(*n);printf(请输入一个进程:n,i+1);printf(请输入进程名称:n);scanf(%s,Processi.Name); printf(请输入到达时间:n);scanf(%d,&Processi.ArrivalTime);printf(请输入服务时间:n);scanf(%d,&Processi.WholeTime);Processi.ServiceTime=0;Processi.FinishTime=0;Processi.WeightWholeTime=0;Processi.order=0;Processi.run_flag=0;system(cls);return 0;int Poutput() /调度结果输出int i;float turn_round_time=0,f1,w=0;printf( 进程名称 到达T 运行T 开始运行T 结束T 执行顺序 周转T 带权周转Tn);for(i=0;iN;i+)Processi.WeightWholeTime=Processi.FinishTime-Processi.ArrivalTime;f1=Processi.WeightWholeTime/Processi.WholeTime;turn_round_time+=Processi.WeightWholeTime;w+=f1;printf(时刻%d :,Processi.ServiceTime,Processi.Name);printf( %s %d %d %d %d %d %f %fn,Processi.Name,Processi.ArrivalTime,Processi.WholeTime,Processi.ServiceTime,Processi.FinishTime,Processi.order,Processi.WeightWholeTime,f1);printf(average_turn_round_timer=%fn,turn_round_time/N);printf(weight_average_turn_round_timer=%fn,w/N);return 0;九、实验体会通过本次课程设计，使我对计算机操作系统短作业优先调度算法这一节的知识有了更深的了解 。短作业优先调度算法易于实现，并且效率很高，但是短作业只考虑到短作业的利益，而不顾长作业，这样就可能会使得长作业一直处于等待状态而不能运行。所以，短作业优先算法适用于系统中短作业较多的情况。此外，通过本次实验，进一步巩固和复习操