更多优质内容
请关注公众号

操作系统入门(十四)调度算法——时间片轮转算法、优先级调度算法 和 多级反馈队列算法-张柏沛IT博客

正文内容

操作系统入门(十四)调度算法——时间片轮转算法、优先级调度算法 和 多级反馈队列算法

栏目:Linux 系列:操作系统入门 发布时间:2022-02-15 14:55 浏览量:86
本系列文章目录
展开/收起

之前介绍了3种早期批处理的调度算法 调度算法——先来先服务算法、短作业优先算法 和 高响应比优先算法,本节要介绍的3种算法则常用于分时操作系统和实时操作系统等交互式系统。


时间片轮转 RR
算法思想:让每个进程公平的、轮流的得到运行机会,每个进程在一定时间间隔内都可以得到响应(即得到CPU运行),相比于先来先服务算法,RR除了公平外还考虑了让每个进程的响应时间尽量短;
算法规则:让每一个到达就绪队列的进程执行一个时间片,一开始按照进程进入队列的顺序执行,如果进程未在一个时间片内执行完,则剥夺CPU,将其重新放到就绪队列队尾;
用于作业/进程调度:仅用于进程调度;
是否可抢占:抢占式调度;
优点:公平;每个进程响应快;
缺点:没有考虑到作业/进程的紧急程度;时间片大小需要足够合适,否则会降低进程运行效率。
是否导致饥饿:不会。
适用于:分时操作系统。



上面是时间片大小为2的情况。

如果时间片大小太大,每个进程都能在一个时间片内完成,则RR算法会退化为先来先服务算法,增大进程的响应时间(即后到达的进程可能要等很久才能开始执行),进程变为串行,从而降低并发效率。

PS:增大响应时间是指,例如系统中有10个进程在并发执行,每个进程需要2个时间片才会运行完。如果时间片为1,则第10个进程需要等待9秒才被响应。如果时间片为2,则需要18秒才被响应。

如果时间片大小太小,进程频繁发生切换,CPU时间都消耗在进程切换而非用户任务处理,也会降低CPU效率,降低进程运行效率。切换进程的CPU时间应该小于CPU总运行时间的1%。




优先级调度算法

算法思想:根据任务的紧急程度来决定处理顺序;

算法规则:每个作业/进程有各自的优先级,选择优先级最高的 作业/进程最先运行;

用于作业/进程调度:皆可;

是否可抢占:非抢占式调度(只有在当前进程主动放弃CPU时才会引发调度),抢占式调度(每次就绪队列改变都会引发调度);

优点:区分进程的紧急程度,根据优先级决定调度顺序;也可以灵活设定 CPU/IO密集型进程的优先级;

缺点:若源源不断地有高优先级进程到来,则可能导致饥 饿。

是否导致饥饿:会。



就绪队列未必只有一个,可以按照不同优先级组织多个队列。也可以把优先级的进程排在更接近队头位置。

根据优先级是否可变,可将优先级分为静态优先级和动态优先级两种。

静态优先级:创建进程是确定,之后一直不变。

动态优先级:创建进程时有一个初始值,之后根据情况动态调整优先级。


如何合理设置各类进程的优先级?通常来说

系统进程优先级 高于 用户进程。

前台进程 高于 后台进程。

IO密集型进程 高于 CPU密集型进程。原因是IO设备和CPU可以并行工作,优先让IO密集型进程工作可以让IO设备尽早投入工作,并且CPU会在发出IO请求后立刻处理之后的CPU密集型进程,如此一来两种进程并行运行,IO设备处理IO密集型进程的请求,同时CPU也在运行CPU密集型的进程运算,IO设备和CPU都不会闲着。提高了资源利用率,系统吞吐量和并发率。


如果采用动态优先级,什么时候应该调整优先级?(可以从公平、提高资源利用率的角度考虑)

如果某进程在就绪队列等待了很长时间,可以提升其优先级。

如果某进程占用CPU时间很长,可以适当降低其优先级。

如果发现一个进程频繁的发生IO操作,可以提升其优先级。


其实 高响应比算法 本质也是一种动态优先级算法,根据进程的等待时间和运行时间调整哪个进程优先被调度。

小结:FCFS的特点是公平;SJF的特点是先处理短作业,追求最小的平均等待时间;RR的特点是在追求公平的前提下,还保证了每个进程被尽早响应(被尽早开始处理);优先级调度算法的特点是区分进程紧急程度,根据优先级决定调度顺序。

下面介绍的多级反馈队列调度算法折中了上述几种算法的优点。



多级反馈队列调度算法

算法思想:对其他调度算法的折中(公平性、每个进程及时响应、区分紧急程度);

算法规则:

1、设置多级就绪队列,各级队列优先级从高到低,时间片从小到大。

2、新进程到达时先进入第1级队列(最高优先级),分配最长时间片,按FCFS原则调度。

若时间片用完,进入下一级队列队尾。如果已经处于最低级队列,则时间片用完时,重新放到本队列队尾。

3、当第k级队列为空时,才会选择调度k+1级队列的进程。只有开始调度某一进程时,才会为这个队头进程分配时间片。

4、被抢占时,当前进程不降级,放回本队列的队尾。

5、主动让出CPU时,当前进程不降级,例如如果进程因IO阻塞而让出CPU,则放回本队列的队尾,如果多次因IO阻塞让出CPU,说明他是IO密集型进程,还可以被放入上一级队列中。

用于作业/进程调度:用于进程调度;

是否可抢占:抢占式,当k级队列的进程在运行时,若更上级的队列进入一个新进程,新进程会抢占处理机,原来的进程会返回k级队列尾部;

优点:该算法同时使用了FCFS、RR、SPF 和 优先级调度算法,也集合了他们的优点,即公平、快速响应、短进程快速完成(他们可能在第一级队列就完成了)、区分进程紧急程度、灵活调整系统对CPU/IO密集型进程的偏好;

缺点:可能导致饥饿。

是否导致饥饿:会,例如不停有新进程进入1级队列,而且这些进程都是短进程,在1个时间片内就可以完成,此时下级队列的进程就一直无法持有CPU。

UNIX系统使用的就是多级反馈队列算法。


这3种算法更适用于交互式系统。




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 操作系统入门(十四)调度算法——时间片轮转算法、优先级调度算法 和 多级反馈队列算法

热门推荐
推荐新闻