常用调度算法
调度的实质就是一种资源分配。不同的系统和系统目标,通常采用不同的调度算法——适合自己的才是最好的。
如批处理系统为照顾为数众多的短作业,应采用短作业优先的调度算法;
如分时系统为保证系统具有合理的响应时间,应采用轮转法进行调度。
目前存在的多种调度算法中,有的算法适用于作业调度,有的算法适用于进程调度;但有些算法作业调度和进程调度都可以采用。
1、先来先服务调度算法FCFS
一种最简单的调度算法,按先后顺序进行调度。既可用于作业调度,也可用于进程调度。
按照作业提交,或进程变为就绪状态的先后次序分派CPU;
新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
被唤醒的作业或进程不立即恢复执行,通常等到当前作业或进程出让CPU。
2、短作业(进程)优先调度算法SJF/SPF
优点:通过上表可见采用SJF/SPF算法,平均周转时间、平均带权周转时间都有明显改善。SJF/SPF调度算法能有效的降低作业的平均等待时间,提高系统吞吐量。
方式:分抢占和非抢占两种方式,上例为简单的非抢占式。
SJF/SPF的不足:
a.对短作业有利,但同时造成了对长作业的不利。
b.由于作业(进程)的长短含主观因素,不一定能真正做到短作业优先。
c.未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)的及时处理。
3、 高优先权优先调度算法HPF Highest Priority First
照顾紧迫性作业,使其获得优先处理而引入调度算法。常用于批处理系统中的作业调度算法,以及多种操作系统中的进程调度算法
1)分两种方式:非抢占式优先权算法;抢占式优先权算法 关键点:新作业产生时
2)优先权的类型:
静态优先权:创建进程时确定,整个运行期间保持不变。一般利用某一范围的一个整数来表示,又称为优先数。
动态优先权:创建进程时赋予的优先权可随进程的推进或随其等待时间的增加而改变。
3)高响应比优先调度算法HRRN Highest Response Raito Next
短作业优先算法是一种比较好的算法(相当于根据作业长度设定的静态优先权算法),适用于短作业较多的批处理系统中,其主要不足是长作业的运行得不到保证。
HRRN为每个作业引入动态优先权,使作业的优先级随着等待时间的增加而以速率a提高:
优先权 =(等待时间+要求服务时间)/要求服务时间= 响应时间 / 要求服务时间
4、基于时间片的轮转调度算法RR(Round Robin)
分时系统新需求:及时响应用户的请求;采用基于时间片的轮转式进程调度算法。
早期分时系统采用的是简单的时间片轮转法,进入90年代后广泛采用多级反馈队列调度算法。
几种常用调度方法的比较
网友评论