课程设计-调度算法的程序实现举例.doc

计算机科学与技术专业03级
《操作系统原理》课程设计
课题名称:调度算法的程序实现举例
姓名:
课程设计起止时间:2005-12-26
指导教师: 成绩:
课程设计任务书
《操作系统原理》课程设计任务书
设计题目:调度算法的程序实现举例
任务下达时间:2005年12月26日
任务完成时间:2005年12月30日
指导教师:
指导教师评语
一、所得结果:
二、存在问题:
成绩
评阅人
调度算法的程序实现举例
设计说明:本文使用C语言实现了进程调度算法和作业调度算法,选取了几个典型调度算法进行了模拟:1. 先来先服务(FCFS)调度算法
2. 最短作业优先法(SJF)(HRN)。通过实验证明本程序可以有效的实现对这三种算法的模拟,直观的体现了这三种算法的运算过程。
工作原理:衡量调度策略的指标很多,最常用的几个指标是:周转时间、带权周转时间、吞吐率、相应时间以及设备利用率等。周转时间是指将一个作业提交给计算机系统后到该作业结果返回给用户所需要的时间。吞吐率是指在给定的时间内,一个计算机系统所完成的总工作量。响应时间则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。设备利用率主要指输入设备的使用情况,在有些要求I/O处理能力强的系统中,高的设备利用率也是一个衡量调度策略好坏的重要标准。
周转时间:ti=tc-ts
对于被测定作业所含有的几个作业来说,其平均周转时间为:
eti=(∑ti)/n
带权周转时间:wi=ti/ntime
对于被测定作业所含有的几个作业来说,其平均带权周转时间为:
ewi=(∑wi)/n
下面是几个典型的调度算法:
(e first serve)调度算法
将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列,并按照先来先服务(FCFS)的方式进行调度处理,是一种最普遍和简单的方法。在没有特殊理由要优先调度某类作业或进程时,从处理的角度来看,FCFS方式是一种最合适的方法,因为无论是追加还是取出一个队列元素在操作上都是最简单的。
直观看,该算法在一般意义下是公平的。即每个作业或进程都按照它们在队列中等待时间长短决定它们是否优先享受服务。不过对于那些执行时间较短的作业或进程来说,如果它们在某些执行时间很长的作业或进程之后到达,则它们将等待很长的时间。
(shortest job first)
在批处理为主的系统中,如果采用FCFS方式进程作业调度,虽然系统开销小,算法简单,但是,如果估计执行时间很短的作业在那些长作业的后面到达系统的话,则必须等待长作业执行完之后才有机会获得执行。这将造成不必要的等待和某种不公平。最短作业优先法(SJF)就是选择那些估计需要执行时间最短的作业投入执行,它们创建进程和分配资源。直观上来说,采用最短作业优先的调度算法,可使得系统在同一时间内处理的作业个数最多,从而吞吐量也就大于其他调度方式。但是,对于一个不断有作业进入的批处理系统来说,最短作业优先法有可能使得那些长作业得不到调度执行的机会。
(highest response_ratio next)
最高响应优先法(HRN)是对FCFS方式和SJF方式的一种综合平衡。FCFS只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF方式只考等待时间的长短。因此,这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。
响应比R定义如下:
R=(W+T)/T=1+W/T
其中T为该作业估计需要的执行时间,W为作业在后备状态队列中的等待时间。
每当要进行作业调度时,系统计算每个作业的响应比,选择其中R最大者投入执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行,在同一时间内处理的作业数显然要少于SJF法,从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。
另外,由于每次调度前要响应比,系统开销也要响应增加。
详细设计:
相关函数介绍
(int m);
功能:本函数实现先来先服务算法。
();
功能:本函数打开“”用来读。
()
功能:本函数在窗口上显示语句“adopts the file way to input the datas...y/n:”,并实现从键盘输入字符y/n,从而调用相应的函数。
(m)
功能:本函数实现最高响应比优先算法。
()
功能:用手工方式实现对一个作业控制块的初始化。