实时系统的进程调度策略
摘要：本文说明实时系统的定义及分类。对各种实时系统进程调度策略进行了讨论，他们
是基于优先级，基于比例共享，基于时间的进程调度算法，其中第一种是大多数实时系统采
用的。再就四种实时操作系统采用的调度策略进行了分析比较，他们采用的策略是各种因素
的折中。

1实时系统概述
1.1实时系统定义

POSIX标准对实时系统作了这样的定义：指系统能够在限定的响应时间内提供所需水平的
服务。而一个更为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻
辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统
出错。

1.2实时系统分类

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统就
是系统必须及时地对事件做出反应，绝对不能发生错过事件处理或超出截止期的情况。例如
控制火箭发射的系统；而在软实时系统中，当系统负载较高时允许发生少数事件处理错过截
止期的情况，像实时多媒体系统就是一种软实时系统。

目前世界上比较有影响力的实时操作系统主要有Lynx实时系统公司的LynxOS、QNX软件
系统有限公司的QNX以及两种具有代表性的实时Linux--新墨西哥工学院的RT－Linux和
堪萨斯大学的KURT－Linux。

2实时系统调度策略

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于 CPU 和其他资源进行
有效的调度和管理。调度算法实际上就是系统所采取的调度策略。下面将先从分类的角度对
各种实时任务调度算法进行讨论，再就以上提及的四种实时操作系统采用的调度策略分析比
较。

各种实时操作系统的实时调度算法可以分为如下三种类别：基于优先级的调度算法
（Priority-driven scheduling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven
scheduling-SD）、以及基于时间的进程调度算法（Time-driven scheduling-TD），其中第一种
算法是大多数实时系统所采用的。下面对这三种调度算法逐一进行介绍。

2.1. 基于优先级的调度算法
基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那
个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以
分为如下两种类型：

 静态优先级调度算法：
这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。它是在系统开始
运行前进行调度的,严格的静态调度在系统运行时无法对任务进行重新调度.静态优先级的分
配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。
静态调度算法实现简单,调度的额外开销小,在系统超载时可预测性好. 但也具有很大的局限
性,例如资源利用率低、受系统支持的优先级个数限制以及灵活性和自适应性差等. 下面介绍
两种常见的静态调度算法.

 速率单调调度( Rate Monotonic Scheduling)
RMS算法将最高优先级赋予最高执行频率的任务,以单调的顺序对剩余的任务分配优
先级. 由于采用抢占式的调度方式,高优先级的任务就绪后立即抢占正在运行的任务.
RMS 算法的优点是开销小,灵活性好,可调度性测试简单. 在任务的截至时间等于其
周期的条件下,速率单调算法已被证明是静态最优的调度算法 .
 截止时间单调调度( Deadline Monotonic Scheduling)
DMS算法是在速率单调调度的基础上发展起来的.不同的是任务的优先级按截止时间
来分配. 截止时间短的任务优先级高,截止时间长的任务优先级低.截止时间调度具有
与速率单调算法相同的优点. 但DMS 算法放松了对任务的周期必须等于其截止时间
的限制. 在任务的截止时间小于或等于其周期的情况下,DMS 已被证明是静态最优
的调度算法.

 动态优先级调度算法：
这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调
度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。
下面介绍两种常见的动态调度算法

 最早截止时间优先算法( Earliest Deadline First)
抢占式EDF 调度算法是一个动态优先级驱动的调度算法,其中分配给每个任务的优先
级根据它们当前对最终期限的要求而定. 当前请求的最终期限最近的任务具有最高的
优先级,而请求最终期限最远的任务被分配最低优先级. 这个算法能够保证在出现某
个任务的最终期限不能满足之前,不存在处理器的空闲时间 .
抢占式EDF 调度算法最大的优势在于,对于任何给定的任务集,只要处理器的利用率
不超过100 % ,就能够保证它的可调度性. EDF 算法在系统的负载相对较低时非常有
效. 但在系统负载较重时,系统性能急剧下降,引起大量任务错过截止期,甚至可能导致
CPU 时间大量花费在调度上, 在这时系统的性能还不如FIFO方法.
 最小松弛时间算法(Least Slack Time First)
LSF 算法计算任务的松弛时间,其中松弛时间为任务截止时间与剩余执行时间之差.
该算法在任意时刻把最高优先级分配给具有最小松弛时间的任务,以此来保证紧急任
务的优先执行. 然而,由于等待任务的松弛时间是严格递减的,其等待执行的缓急程度
也随时间越来越紧迫,因此在系统执行过程中,等待任务随时可能会抢占当前执行的任
务.LSF 算法造成抖动现象较为严重. 抖动现象增大了系统开销,并限制了LSF 算法的
应用.

2.2. 基于比例共享调度算法
前面所述算法是硬实时操作系统的调度，对于软实时应用，使用的是比例共享式的资源
调度算法（SD 算法）。
比例共享调度算法指基于 CPU 使用比例的共享式的调度算法，其基本思想就是按照一
定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成
正比。
比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法
（Lottery）等。
比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它
们申请的比例共享 CPU 资源，当系统处于过载状态时，所有的任务的执行都会按比例地变
慢。所以为了保证系统中实时进程能够获得一定的 CPU 处理时间，一般采用一种动态调节
进程权重的方法。

2.3. 基于时间的进程调度算法
对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调
度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下
来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个
任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那
些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并
且会出现有任务需要被执行而 CPU 却保持空闲的情况。
应用举例
以上算法都有各自适应的场合，也存在一定的局限性，在商业产品中采用的实际策略常常是
各种因素的折中。以下列举上文提及的四种操作系统的调度策略

 QNX 提供POSIX.1b标准进程调度：
32个进程优先级；
抢占式的、基于优先级的正文切换；
可选调度策略：FIFO、轮转策略、适应性策略。

 LynxOS 其调度策略为：
LynxOS支持线程概念，提供256个全局用户线程优先级；
硬实时优先级调度：在每个优先级上实现了轮转调度、定量调度和FIFO调度策略；
快速正文切换和阻塞时间短；
抢占式的RTOS核心。

 RT－Linux
在操作系统之下实现了一个简单的实时核心，Linux本身作为一个可抢占的任务在核内
运行，优先级最低，随时会被高优先级任务抢占。
用户可自行编写调度程序，它们可实现为可加载的核心模块；
已实现的调度程序有：基于优先级的抢占式调度和EDF调度；
基于优先级的调度使用"单调率算法"，它直接支持周期任务。

 KURT－Linux
可运行在两种状态之下：通常状态和实时状态。在通常状态下，所有进程都可以运行，
但某些核心服务将带来中断屏蔽的不可预期性。实时模式只允许实时进程运行。
支持FIFO调度策略、轮转调度策略和UNIX分时调度策略；
增加了SCHED－KURT调度策略，这是一种静态调度策略，使用一个特殊的调度文件
记录预先定义好的待调度进程的参数。

结语
本文先说明实时系统的定义，列举目前有影响力的实施操作系统。再从分类的角度对各种
实时系统进程调度策略进行了讨论，他们是基于优先级，基于比例共享，基于时间的进程调
度算法，第一种是大多数实时系统采用的。再就四种实时操作系统采用的调度策略进行了分
析比较，他们采用的策略是各种因素的折中。