操作系统短作业优先调度算法

1、采用短作业优先调度算法调度程序学号：姓名：专业：指导老师：日期:一、实验题目3二、课程设计的目的3三、设计内容3四、设计要求3五、主要数据结构及其说明 4六、程序运行结果5七、流程图7八、源程序文件9九、实验体会13十、参考文献13摘要在多道程序环境下，主存中有着多个进程，其数目往往多于处理机 数目这就要求系统能按某种算法，动态地把处理机分配给就绪队列中 的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成 的。由于处理机是最重要的计算机资源，提高处理机的利用率及改 善系 统性能（吞吐量、响应时间），在很大程度上取决于处理机调度 性能的 好坏，因而，处理机调度便成为操作系统设计的中心问

2、题之一。在多道程序系统中，一个作业被提交后必须经过处理机调度后，方 能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和 进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用 户作业，根据作业控制块的信息，按一定的策略选取若干个作业使 它 们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的 作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方 法。本次课程设计主要是模拟短作业优先（SJF）调度算法。9、实验题目采用短作业优先算法的的进程调度程序二、课程设计的目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手 又动脑，将课本上的理论知

3、识和实际有机的结合一起，独立分析和解决实际问题 的机会。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。三、设计内容设计并实现一个采用短作业优先算的进程调度算法演示程序四、设计要求1. 每一个进程有一个PCB，其内容可以根据具体情况设定。2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片 长度、进程优先级的初始化4. 可以在运行中显示各进程的状态：就绪、执行（由于

4、不要求设置互斥资源与进程 间同步尖系，故只有两种状态）5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及 相应的阻塞队列五、主要数据结构及其说明算法的 基本概念和原理：本次课程设计主要是采用短作业优先算法进程的进 程 调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们 可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一 个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算 法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，使它 立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度

5、重新调度。 本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦 把处理机分配 给某进程后，便让该进程一直执行，直至该进程完成或发生某事件 而被阻塞时， 才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去 的处理机。这种 调度方式的优点是实现简单，系统开销小，适用于大多数的批处 理系统环境。但 它难以满足紧急任务的要求一一立即执行，因而可能造成难以预 料的后果。因此， 在要求比较严格的实时系统中，不宜采用这种调度方式。本课 程设计主要是在满足要 求多道单处理机的情况下进行短作业的优先调度。算法的简要说明：短作业(进程)优先调度算法SJ (P) F，是指对短作业 或短进程优先调度

6、的算法。它们可以分别用于作业调度和进程调度。短作业优先 (SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作 业，将它们调入内存运行。而短进程(SPF)调度算法则是从就绪队列中选出一 个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完 成，或发生某事件而被阻塞放弃处理机再重新调度。优点是SJ (P) F调度算法 能有效地降低作业(进程)的平均等待时间，提高系统吞吐量。缺点是该算法对 长作业不利；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)长 期不被调度；由于作业(进程)的长短只是根据用户所提供的估计执行时间而定 的，而用户又可能会有意或无意地缩

7、短其作业的估计运行时间，致使该算法不一定 能真正做到短作业游戏那调度。该程序定义了一个进程数据块(struct Process.，)该数据块有进程名(name)、到达时间 (arrivetime)、服务时间 (servicetime)、开始执行时间 (starttime)、完成时 间(finishtime)、周转时间(zztime)、带权周转时间 (dqzztime)、执行顺序(order)。用到的公式有：完成时间二到达时间+服务 时间；周转时间二完成时间+到达时间；带权周转时间二周转时间/服务时间；(第 一次执行的进程的完成时间二该进程的到达时间；下一个进程的幵始执行时间二上一 个进程的完成

8、时间)。运行进程的顺序需要对进程的到达时间和服务时间进行比 较。如果某一进程是从0时刻到达的，那么首先执行该进程；之后就比较进程的服务时间，谁的服务时间短就先执行谁(如果服务时间相同则看它们的到达时间，到达时间短的先执行)；如果到达时间 和服务时间相同，则按先来先服务算法执行。六、程序运行结果 x|1进入操作界面如下C:DOCUEinS AND SETTIKGSADlIMISTRATORffiLXQzDebugz. exe-w*r Bjw * 丄 j * 1 傻用短作业优先* 0 退由2输入进程的信息ca *C:DOCUIEMTS AND SETTINGSADlIMISTRATORBfiLXQ

9、zDebugz. exe*3各时刻进程的状态C弋八DOCUMENTS AJTO SETTIMGSADIIBISTRATORffiLXQzDebugx4进程信息5平均带权周转时间界面七、流程图本次课程设计主要是通过比较各个进程的优先级以及各进程所需要占 用的CPU时间来确定哪个作业优先运行，短作业优先调度算法除了能 保证优先级更高的作业优先运行外，还能使相同优先级的前提 下，所需 CPU时间最短的那个作业优先运行，次外，本次课程设计还增加了阻塞 时间和被阻塞时间来对个进程的运行加以控制。此次课程设计的总体 流程图如下：八、源程序文件进程编号/进程名称到达时间开始运行时间运行结束时间 运行时间调度

10、标志运行次序#in clude #define MaxNum 100 using namespace std; struct Process_struct int 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

11、_SJF; 平均带权周转时 间ProcessMaxNum;int N;实际进程个数int SJF();短作业优先int SJF()短作业优先算法int temp_time=0;当期那时间int i=0,j;int number_schedul,temp_counter;进程编号5当前已执行进程个数float run_time;run _tinie=Processi.WholeTime;j=1；while(jN)&(Processi.ArrivalTime=Processj.ArrivalTime)/ 判断是否有两个进程同时到达(if(Processj.WholeTimeProcessi.Who

12、leTime)(run _time=Processi.WholeTime; 匸j;)j+;)查找下一个被调度的进程对找到的下一个被调度的进程求相应的参数nu mber_schedul=i;Processnumber_schedul.ServiceTime=Processnumber_schedul.ArrivalTime;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime4-Pr ocessnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp

13、_time=Processnumber_schedul.FinishTime;Process nu mber_schedul.order=1;temp_counter=1; while(temp_counterN)ifor(j=0;jN;j+)df(Processj.ArrivalTime=temp_time)&(!Processj.run_flag) run_time=Processj.WholeTime; number_schedul=j; break;)for(j=0;jN;j+)df(Processj.ArnvalTime=temp_time)&(!Processj.run_flag)

14、 if(Processj.WholeTimeru n_time)run_time=ProcessjWholeTime; number_schedul=j;)查找下一个被调度的进程对找到的下一个被调度的进程求相应的参数Processnumber_schedul.ServiceTime=temp_time;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Pr ocessnumber_schedul.WholeTime;Process nu mber_schedul.run_flag=1; temp_time=Pr

15、ocessnumber_schedul.FinishTime; temp_counter+; Processnumber_schedul.order=temp_counter; return 0;int Pinput(); 进程参数输入 int Poutput(); 调度结果输出 void main()(int option;printf(”printf(”主菜单1使用短作业优先1printfC*nH);printf(”/system(” cis”)； system(color If*);scanf(%d,&option);switch(option)case 0: printf(H 运行结束

16、。nH); break;case 1: printf(”对进程用短作业优先调度。nrf); Pinput(); SJF();Poutput();break;int Pinput()进程参数输入inti;printf(” 请输入进程个数:nn)； scanf(”cT,&N);for(i=0;iN;i+)printf(” printf(n 请输入一个进*nH)；程:nn,i+1);printf (”请输入进程名称:nn);scanf(H%sM, Processi.Name);printf(”请输入到达时间:rT); scanf(,%d,&Processi.ArrivalTime); printf(

17、” 请 输入服务时间：nn); scanf(,%d,&Processi.WholeTime);Processi.ServiceTime=0; Processi.FinishTime=0; Processi.WeightWholeTime=0; Processi.order=0; Processi.r un _flag=O;system(HclsH);return 0;int Poutput() /调度结果输出(int i;float turn_round_time=0,f1 ,w=0;printf(”进程名称 到达T运行T开始运行T结束T执行顺序周转T带权周转 Tnn)；for(i=0;iN;

18、i+) Processi.WeightWholeTime=Processi.FinishTime-Processi.ArrivalTime;f1=Processi.WeightWholeTime/Processi.WholeTime; turn_round_time+=Processi.WeightWholeTime;w+=f1;printf(” 时刻 %d :”,ProcessiServiceTime,ProcessiName);printf(H %s %d %d %d %d %d %f %fn,Processi.Name,Processi.ArrivalTime,Pr ocessi.Who

19、leTime,Process i.ServiceTime,Processi.FinishTime,Processi.order,Pro cessi.WeightWholeTime,f 1);)pri ntf (” average_turn_round_timer=%frT,turn_round_time/N);prin tf(nweight_average_turn_ro un d_timer=%fnn,w/N); return 0;九、实验体会通过本次课程设计，使我对计算机操作系统短作业优先调度算法这一节 的知识 有了更深的了解。短作业优先调度算法易于实现，并且效率很高，但 是短作业只考 虑到短作业的利益，而不顾长作业，这样就可能会使得长作业一直处于等待状态 而不能运行。所以，短作业优先算法适用于系统中短作业较多的情况。此外，通