操作系统短作业优先调度算法1
- 格式:doc
- 大小:81.59 KB
- 文档页数:11
操作系统实验
题目:
实现非抢占式短作业优先调度算法
要求:
1.系统共有100个随机到达的作业。要求为每个作业设定到达时间和需要运行的时间。
2.按照短作业优先进行调度,直到所有作业完成。
3.计算每个作业的周转时间,计算平均周转时间。
提交报告
1.实验报告打印稿(参照学校有关报告格式)。
2.刻录一张光盘。光盘内容:用学号+姓名为每个同学建立目录,文件包括报告的电子版,
程序源代码。
一、主要数据结构及其说明
算法的基本概念和原理:本次课程设计主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法,是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度,短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给他,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式,一旦把处理机分配给某进程后,便让该进程一直执行,直至该进程完成或发生某事件而被阻塞时,才再把处理机分配给其它进程,决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单,系统开销小,适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行,因而可能造成难以预料的后果。因此,在要求比较严格的实时系统中,不宜采用这种调度方式。本课程设计主要是在满足要求多道单处理机的情况下进行短作业的优先调度。
算法的简要说明:短作业(进程)优先调度算法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时间最短的那个作业优先运行,次外,本次课程设计还增加了阻塞时间和被阻塞时间来对个进程的运行加以控制。此次课程设计的总体流程图如下:
四、源程序文件
#include
#define MaxNum 100
using namespace std;
struct Process_struct{
int Number; //进程编号
char Name[MaxNum]; //进程名称
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; //平均带权周转时间
}Process[MaxNum];
int N; //实际进程个数
int SJF(); //短作业优先
int SJF(){ //短作业优先算法
int temp_time=0; //当期那时间
int i=0,j;
int number_schedul,temp_counter; //进程编号,当前已执行进程个数float run_time;
run_time=Process[i].WholeTime;
j=1;
while((j { if(Process[j].WholeTime { run_time=Process[i].WholeTime; i=j; } j++; } //查找下一个被调度的进程 //对找到的下一个被调度的进程求相应的参数 number_schedul=i; Process[number_schedul].ServiceTime=Process[number_schedul].ArrivalTime; Process[number_schedul].FinishTime=Process[number_schedul].ServiceTime+Pr