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

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

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

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

4、长度、进程优先级的初始化4. 可以在运行中显示各进程的状态：就绪、执行 （由于不要求设置互斥资源 与进程间同步关系，故只有两种状态）5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态 以及相应的阻塞队列五、主要数据结构及其说明算法的 基本概念和原理 ：本次课程设计主要是采用短作业优先算法进程的进 程调度过程。 短作业优先调度算法， 是指对短作业或短进程优先调度的算法。 他 们可以分别用于作业调度和进程调度， 短作业优先的调度算法是从后备队列中选 择一个或若干个估计运行时间最短的作业， 将他们调入内存运行。 而短进程优先 调度算法则是从就绪队列中选出一个估计运行时间最短的进

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

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

7、 业（进程）长期不被调度；由于作业（进程）的长短只是根据用户所提供的估 计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时 间，致使该算法不一定能真正做到短作业游戏那调度。该程序 定义了一个进程数据块 （struct Process_，） 该数据块有进程名 （name）、 到达时间（arrivetime）、服务时间（servicetime）、开始执行时间（starttime）、完成时 间（finishtime）、周转时间（zztime）、带权周转时间（dqzztime）、执行顺序（order）。 用到的公式有：完成时间=到达时间+服务时间；周转时间 =完成时间+到达时间； 带权

8、周转时间 =周转时间 /服务时间；（第一次执行的进程的完成时间 =该进程的到 达时间；下一个进程的开始执行时间 =上一个进程的完成时间 ）。运行进程的顺序 需要对进程的到达时间和服务时间进行比较。如果某一进程是从 0 时刻到达的， 那么首先执行该进程； 之后就比较进程的服务时间， 谁的服务时间短就先执行谁 （如果服务时间相同则看它们的到达时间，到达时间短的先执行） ；如果到达时 间和服务时间相同，则按先来先服务算法执行。六、程序运行结果1进入操作界面如下2输入进程的信息* 1便用短作业优先* 0退由*KNNXNfcrf NNK 1芬逬程用短作业优先调度。请输入进程个数：53各时刻进程的状态KK

9、KKWKKmtiMWKiMKKiMKKiMU 主 单 M：良 K ：K X t K* 1德用短作业优先* 0退由京进程用短作业优先调度。请输入进程个数:5备输入到达时间二 養输入服务时间三4Iff彌人一 T进住: 请藉入进程名糅 鲁输入到达时间:请输入服务时间:3:M MLlt JfMLJitWKJtKMMlltKMLKXMllCXMLX W今*具-KlC MllCK JtXlOtM：SIaSJII：c请输入到达时间：鲁输入服务时间：3请规入一个进程: 请貉入进程名杯 鲁输入到达时间= 鲁输入服务时间:2请赣入一个进拦= 请歳入进程名粘e请输入到达时间:请输入服务时间二24进程信息屮 *C:D

10、OCU1EHTS AND SETTIBGSADIINISTRATOR LXQzDebuEz_ exe进程名称到达T运行T开始运行T结東T执行顺序周转T带权周转T1za12i310Q.0000003:b2134200.0000004*C3246306.000000&:d4268466.0000008二e43B1150-0.000000average_tuin_iound_timcr =3 .600000we ig h t _a v e rage _t urn _io un d_t ime i*j_. 766SS7 Press an9 kesp to continue_5平均带权周转时间界面Cve

11、rae-turn-Found iner=J. bUUUUUe ight_ave rage _t urn _round_t imer=l 766667七、流程图本次课程设计主要是通过比较各个进程的优先级以及各进程所需 要占用的CPU寸间来确定哪个作业优先运行，短作业优先调度算法除 了能保证优先级更高的作业优先运行外，还能使相同优先级的前提 下，所需CPU寸间最短的那个作业优先运行，次外，本次课程设计还 增加了阻塞时间和被阻塞时间来对个进程的运行加以控制。 此次课 程设计的总体流程图如下：开始结束八、源程序文件#include#define MaxNum 100using namespace st

12、d; 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_SJF;

13、/平均带权周转时间 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.Whol

14、eTime) run_time=Processi.WholeTime;i=j;j+;/查找下一个被调度的进程/对找到的下一个被调度的进程求相应的参数number_schedul=i;Processnumber_schedul.ServiceTime=Processnumber_schedul.ArrivalTime;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Pr ocessnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1; temp_ti

15、me=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)

16、if(Processj.WholeTimerun_time) run_time=Processj.WholeTime; number_schedul=j;/查找下一个被调度的进程 /对找到的下一个被调度的进程求相应的参数 Processnumber_schedul.ServiceTime=temp_time;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Pr ocessnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1; temp_time=P

17、rocessnumber_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( *n);printf(*n);/system(cls);system(color 1f);scanf(%d,&option);switch(option)case 0:prin

18、tf( 运行结束。 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(f*n);printf( 请输入一个进程 :n,i+1);printf（ 请输入进程名称 :n）;scanf(%s,Processi.Name);printf( 请输入到达时间 :n); scanf(%d,&Processi.ArrivalTime); printf( 请输入

19、服务时间 :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+)

20、 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.WholeTi

21、me,Process i.ServiceTime,Processi.FinishTime,Processi.order,Processi.WeightWholeTime,f 1); printf(average_turn_round_timer=%fn,turn_round_time/N); printf(weight_average_turn_round_timer=%fn,w/N);return 0;九、实验体会通过本次课程设计，使我对计算机操作系统短作业优先调度算法这一节 的知识有了更深的了解 。短作业优先调度算法易于实现，并且效率很高，但 是短作业只考虑到短作业的利益， 而不顾长作业， 这样就可能会使得长作业一 直处于等待状态而不