进程调度是Linux中的一个重要的话题,在多道程序设计系统中,经常会发生多个进程或者线程同时竞争CPU。所以,一定要有一个程序来决定由哪个进程来占用CPU,这个程序就是我们所说的调度程序。本文简要地总结了Linux下常见的调度机制及相关的问题。

处理机分配

处理机分配包含两个方面的内容:

  • 调度:组织和维护就绪进程队列,包括确定调度算法,按调度算法组织和维护就绪进程队列。
  • 分配:处理机空闲时,从就绪队列移动一个进程控制块(PCB),并将该进程投入运行。

进程的的类型也分为三种:

  • 批处理进程
  • 交互式进程
  • 实时进程

什么时候需要调度

进程调度一般发生在以下几个情形

  • 创建一个新进程时
  • 一个进程正常退出时
  • 由于一个系统调用而阻塞时
  • I/O中断发生时
  • 分时系统中,进程使用完了分配的时间片
  • 更高优先级的进程抢占时

这里涉及到了两种进程调度,非抢占式调度和抢占式调度。

非抢占式调度会等待正在运行的进程,直到前五种情形发生时,才会转而进行调度。

抢占式调度允许优先级更高的进程抢占资源,一旦优先级高的进程进入就绪状态,就会引发一个中断,将资源马上分配给优先级更高的进程。因此,使用抢占式调度的系统中,正在运行的始终是优先级最高的进程。

调度的目标

  • 公平 – 调度算法必须是对相同优先级的每个进程公平公正
  • 保证可以执行 – 调度不能出现问题,否则系统将崩溃
  • 资源高效利用 – 尽可能要使得系统的所有部分忙碌

为衡量调度性能,我们常考虑一下几个指标:吞吐量、CPU利用率和周转时间,等待时间和响应时间。

  • 吞吐量:系统每小时完成的作业数量
  • CPU利用率:CPU不闲置的时间百分比
  • 周转时间:从一个作业提交时刻开始知道该作业完成时刻为止的时间
  • 等待时间:作业从在就绪队列中的时间
  • 相应时间:相应延迟
  • 带权周转时间:周转时间/运行时间

批处理系统的调度

批处理系统主要的特点就是不允许抢占式调度。

先来先服务(FIFC)

最简单的一种非抢占式算法,所有的进程按照他们请求的顺序使用CPU,早就绪的进程在就绪队列前面,后来的进程在就绪队列后面。

例如:

进程 进入时间 运行时间 开始时间 结束时间
A 8:00 120 8:00 10:00
B 8:50 50 10:00 10:50
C 9:00 10 10:50 11:00
D 9:50 20 11:00 11:20

这种调度的优点和缺点很明显,有利于长作业而不利于短作业。靠后的短作业可能等待靠前的长作业很长时间。

最短作业优先(SPF)

这种算法在每次进行调度时,总是选择所需时间最短的作业运行。

例如:

进程 进入时间 运行时间 开始时间 结束时间
A 8:00 120 8:00 10:00
B 8:50 50 10:30 11:20
C 9:00 10 10:00 10:10
D 9:50 20 10:10 10:30

下面证明,这种调度算法的平均周转时间是最小的。

假设n个进程运行需要的时间从小到大为 t1 t2 t3 … tn,它们的周转时间分别为 a1 a2 a3 … an,那么按照SPF算法得到的平均周转时间为:

(a1 + a2 + a3 + … + an)/n

= (n - 1) * t1 + (n - 2) * t2 + … + 2 * tn-2 + 1 * tn

这是一个排序不等式的反序和,因此任意交换两项乘积中的因子,结果必然大于上式。

这种方法虽然平均周转时间最小,但却被长作业很不利

最短相应比优先(HRRN)

定义:

相应比 = 周转时间 / 运行时间

= 1 +(等待时间 / 运行时间)

例如:

进程 进入时间 运行时间 开始时间 结束时间
A 8:00 120 8:00 10:00
B 8:50 50 10:10 11:00
C 9:00 10 10:00 10:10
D 9:50 20 11:00 11:20

这种方法既考虑作业等待时间又考虑作业运行时间,既照顾短作业又不使长作业等待时间过长,相比之前很好的改进了调度性能。

交互式系统调度

轮转调度

这种方法让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。这是一种古老,简单,公平而且使用很广的算法。每个进程被分配一个时间片,时间片使用完毕就轮到下一个进程。系统维护这一个队列,总是让队列第一个进程运行,在时间片用完之后将其放到对尾。

时间片的选择:

  • 不能太小 – 因为进程切换需要开销,过多的开销使得这部分消耗不可忽略
  • 不能太大 – 否则几乎等同于FIFC

一般来说,选择时间片为20~50毫秒左右比较适宜,上下文切换时间少于10微妙。

优先级队列调度

这种算法的基本思想是,系统给每个进程赋予了一个优先级,同时对每个优先级维护一个就绪队列,如图所示:

系统总是先让高优先级队列中的进程执行,以此类推。

多级反馈队列

这是对上一种算法的改进,很好的解决了高优先级但是运行时间很长的进程对整个任务的影响。其基本思想是,所有的作业会随着运行而逐渐降低优先级。

系统给每个进程分配一个时间片,仍然按照高优先级先运行的方式调度,不过在每个进程的时间片使用完毕之后,就降低一个优先级放在低以及的就绪队列尾部。

这种负反馈的方式在保证了优先级调度的同时又很好的解决了高优先级但时间很长的进程的问题。

彩票调度

这种方法可以近似地实现对于不同的进程去保证其应有的性能。

系统为进程提供了各种系统资源的彩票,一旦需要做出一项调度决策时,就随机抽出一张彩票,拥有该彩票的进程将获得资源。

这种方法的好处是可以量化优先级,从而解决一些不好解决的问题,例如:在某一个视频服务器上,有若干进程正在向客户提供视频流,假设这些进程需要的帧速率为10,20和25帧每秒,那么给这些进程10,20,25张彩票,他们就会大致的按照合理的比例获得CPU的资源。

实时系统调度

实时系统相比其他两种系统,多用于过程控制,军事指挥,自动驾驶等等,也就是嵌入式系统方面。因此,其更要保证的是实时精确控制,保证期限内完成,迅速相应等等功能,其多使用的也是抢占式调度。公平性和相应时间并不是最重要的。

实时系统必要的能力:

  • 很快的上下文切换速度
  • 快速的中断中断响应能力
  • 基于优先级的抢占策略

实时系统通常分为以下两种:

  • 硬实时 - 必须满足绝对的截止时间
  • 软实时 - 不希望错过截止时间,但是可以容忍

事件按照响应方式又可以分为以下两种

  • 周期性 - 以规则的时间间隔发生
  • 非周期性 - 发生时间不可预知

其中大部分的事件是周期性事件,这也就是我们接下来要讨论的。

CPU处理能力

如果m是实时任务的数目,每个任务以pi为周期发生,并且CPU需要ci秒来处理这个事件,那么可以处理负载的条件如下。

不满足这个检验条件的进程不能被调度,因为它是不可实现的(超出了CPU的处理能力)。

静态表/优先级调度

这是在某些固定的执行周期性任务的嵌入式系统中的调度策略,在设计者已经知道用途和确切的周期之后,事先定义好了优先级来调度的一种不灵活的策略

最早截止时间优先

这种算法根据任务的开始截止时间和完成截止时间来确定任务的优先级。截止时间越早,其优先级越高。就绪队列中任务按其截止时间排列,队首任务先分配处理机。

  • 非抢占式调度方式用于非周期实时任务
  • 抢占式调度方式用于周期实时任务

最低松弛度优先算法

定义松弛度如下:

松弛度 = 截止时间 - 本身剩余运行时间 - 当前时间

实际上就是完成该任务之后,距离其deadline剩余的时间。这种算法仅使用抢占式调度。

无保障动态调度

这种调度在任务到来时分配优先级,可能有多种分配优先级的方式,但这种调度策略保证在某个进程的deadline到来时取消进程的运行,这种算法适用于非周期性的调度,尤其是很多任务都很重要的情形。

优先级倒置时的调度

在实时系统的调度中经常会出现这样的问题,同样是周期性的重要任务,某高优先级任务A和低优先级任务C共享了同一个临界区,倒置任务A被C阻塞,出现了高优先级任务晚于低优先级任务执行的情况。这种情况下实时系统会有一个优先级继承(Priority Inheritance)的策略,共享统一临界区的所有进程继承最高优先级的进程的优先级,直到某一进程退出临界区后重新按照这一策略分配优先级