• 欢迎光临~

操作系统调度程序

开发技术 开发技术 2022-10-13 次浏览

本篇介绍操作系统如何调度应用程序,一个我们必须考虑的问题是,应用程序究竟是什么样的,比如它是:

  1. 经常需要与用户交互(等待用户输入)的交互型应用程序(或者说IO密集型应用)
  2. 长时间占用CPU,基本没有IO的应用程序

这引出了两个指标,交互型应用程序比较重视响应性,即任务多久会被响应,长时间占用CPU的程序比较重视周转时间,即任务从到达开始多久会完成。

先进先出FIFO

对于每个到达的任务,维护队列进行排队,先到达的先运行,直到停止。

它很简单,但无论是哪个指标,它都没办法较好的保证,它的好处就是简单且公平。

操作系统调度程序

假设ABC按顺序到达,它们的到达时间相差很小,由于任务A很长,导致BC不能及时的执行,所以拖慢了他们两个的周转时间,而从响应性来说,BC必须等待A执行完,响应性也不是那么好。

最短任务优先SJF

最短任务优先是一个改进的FIFO,它在多个任务同时到达的情况下,将短任务排到前面。

操作系统调度程序

情况依然不乐观,从左图看,如果ABC同时到达,BC的周转时间和响应时间都有了改善,平均周转时间也有了改善,而从右图看,如果BC比A稍晚到10ms,就回到了之前的情况。

最短任务优先(包括我们后面看到的部分算法)必须清楚地知道任务的长度,但这很难,在实际应用中,系统几乎对此一无所知

最短完成时间优先STCF

我们貌似陷入了僵局,要从僵局中跳出,我们必须想办法打断正在执行的任务,否则,一旦执行起长任务,无论使用多么优秀的算法都没用。

STCF是添加抢占后的SJF,在任务到达时,它会执行新工作和系统中当前剩余的工作中剩余时间较少的那个

操作系统调度程序

轮转RR

STCF还是无法解决当ABC同时到达时的问题,按照STCF的办法,A必须等待BC执行完,对A来说,它的响应性很低。

轮转算法在固定的时间片内运行一个任务,并且在下个时间片切换到其他任务,这样,每个任务都能尽快得到运行,但每个任务都运行的比之前慢点,响应性就提高了。

操作系统调度程序

轮转算法要考虑的就是时间片长度,短的时间片可以带来更好的响应性,但也会带来更多的额外开销(切换执行任务需要保存上下文,并可能使得之前程序的缓存失效),长的时间片会节省这种开销,但是会降低响应性

轮转算法的周转时间表现不佳

考虑IO

上面并未提到IO操作,程序在遇到IO操作时,它会暂停使用CPU,此时应该让其它的任务占用CPU。对于轮转算法来说,就是任务可能在没使用完它的时间片时就放弃了CPU。

多级反馈队列MLFQ

前面的SJF和STCF算法都要求知道任务的实际执行时间,而且前面没有一种算法能够同时保证响应性和周转时间。

操作系统调度程序

MLFQ维护若干队列:

  1. 如果任务A的优先级>任务B的优先级,执行任务A
  2. 如果任务A的优先级=任务B的优先级,轮转执行AB
  3. 任务到来,先放到最高优先级队列中
  4. 任务用完在某一层的时间配额,降低优先级
  5. 经过一段时间后,所有工作都重新放到最高优先级队列

为什么分优先级

考虑两种任务的特性:

  1. 交互型任务(或者IO密集型任务)经常在轮转时间片内放弃CPU,去等待用户输入(或IO)
  2. CPU密集型任务通常执行完整个时间片

我们希望交互型任务能尽快的得到执行,而在MLFQ中,任务首先都被认为是交互型的,它们都放在最高优先级队列中。而CPU密集型任务倾向于用完时间配额,所以它会被逐步降级,交互型应用倾向于在配额内主动放弃CPU,所以它降级的较CPU密集型的更慢。

为什么重新放回最高优先级

考虑一个已经在最低优先级工作的任务,现在上面又很多的交互型任务,那么这个处于最低优先级的任务会处于饥饿状态,它总是得不到CPU的时间,因为它的上面总有任务在运行。

而且,即使是交互型任务,当它不断地用完在每一层的配额,也会下降到最低优先级。

就像RR中时间片长度的选择,这个重回最高优先级的时间间隔S的选择也需要仔细权衡,设置得太高会产生饥饿,设置得太低会使得重回最高优先级时(至少有那么一会儿)调度算法退化成RR

比例份额

程序员灯塔
转载请注明原文链接:操作系统调度程序
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com