一、基本概念

1. 实时系统

系统能够及时(即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

实时控制系统+实时信息处理系统

对于实时系统而言，系统的正确性不仅取决于计算的结果，而且还依赖于产生结果的时间。

2. 实时任务

具有及时性要求的、常常被重复执行的特定进程，在实时系统中习惯称为任务。

3. 截止时间

开始截止时间：任务在某时间以前，必须开始执行。

完成截止时间：任务在某时间以前必须完成。

二、实时任务分类

• 截止时间
  • 硬实时任务
  • 软实时任务
• 周期性
  • 周期性实时任务
  • 非周期性实时任务

三、实时操作系统特点

• 可确定性(determinism)：任务按照固定的、预先确定的时间或时间间隔进行

• 可响应性(responsiveness)：关注系统在知道中断后为中断提供服务的时间

• 用户控制(user control)：用户能够区分软、硬实时任务，并控制任务优先级

• 可靠性(reliability)：实时响应和控制事件，保障性能

• 失效弱化(fail-soft operation)：系统具有稳定性，当不能满足所有任务的实时性时，首先满足重要的、优先级高的任务的期限，减少系统故障

四、实时进程的调度方式

基于时间片的轮转调度

• 实时进程按时间片轮转的方式执行，到达的实时进程放在就绪队列尾
• 进程的时间片用完进行调度
• 响应时间一般为秒级
• 广泛用于分时系统及一般实时处理系统

基于优先级的非抢占调度

• 实时进程按优先级、非抢占方式执行，新到的实时进程放在就绪队列首部
• 当前进程阻塞或完成时，立即调度新到进程
• 响应时间一般在数百毫秒至数秒范围
• 多用于多道批处理系统及不太严格的实时系统

基于优先级的抢占点抢占调度

• 实时进程按优先级、抢占方式执行
• 当下一个剥夺点(时钟中断)到来时，立即占用CPU
• 响应时间一般在几毫秒至几十毫秒
• 用于一般实时系统

立即抢占式调度

• 实时进程按优先级、抢占方式执行
• 响应时间为微秒至毫秒级
• 可用于苛刻的实时系统

五、实时调度的方法分类

静态表驱动调度法

• 用于调度周期性实时任务。

• 按照任务周期到达的时间、执行时间、完成截止时间(ending deadline)以及任务的优先级，制订调度表，调度实时任务。

• 最早截止时间优先(EDF)调度算法即属于此类。

• 此类算法不灵活，任何任务的调度申请改动都会引起调度表的修改。

静态优先级抢占调度法

• 此类算法多用于非实时多道程序系统。

• 优先级的确定方法很多，例如在分时系统中，可以对I/O密集型和CPU密集型的进程赋予不同的优先级。

• 实时系统中一般根据对任务的限定时间赋予优先级，例如速度单调算法(RM)即是为实时任务赋予静态优先级。

基于动态规划的调度法

• 当实时任务到达以后，系统为新到达的任务和正在执行的任务动态创建一张调度表。

• 在当前执行进程不会错过其截止时间的条件下，如果也能使新到达任务在截止时间内完成，则立即调度执行新任务。

动态尽力调度法

• 实现简单，广泛用于非周期性实时任务调度。

• 当任务到达时，系统根据其属性赋予优先级，优先级高的先调度。例如最早截止时间优先EDF调度算法就采用了这种方法。这种算法总是尽最大努力尽早调度紧迫任务，因此称为“最大努力调度算法”。

• 缺点在于，当任务完成，或截止时间到达时，很难知道该任务是否满足其约束时间。

六、限期（deadline）调度

限期：deadline，即任务开始或结束的截止时间

调度所需的信息

• 就绪时间
• 启动的限期(starting deadline)
• 完成的限期(completion deadline)
• 处理的时间：任务执行到完成的时间
• 资源需求：任务执行过程中所需的资源集
• 优先级：度量任务的相对重要性
• 子任务结构：一个任务可分解为一个必须执行的子任务和一个可选执行子任务，前者有硬截止时间(hard deadline)

限期调度需要考虑的两个问题

• 问题一：下次调度哪个任务?

  • 根据任务的deadline，选择deadline最早的任务调度，这样可使超过deadline的任务数最少。

• 问题二：采用什么抢占方式?

  • 对于启动限期明确的任务，采用非抢占方式，如前述抢占方式二。当前实时任务在完成必须部分或关键任务后，阻塞自己，使其他实时任务得以启动,满足启动限期。
  • 对于具有完成限期的实时系统，采用抢占策略，如前述抢占方式三或方式四。

针对具有完成限制的周期性实时任务

Earliest Deadline First，EDF

• 此类任务是周期性的，可预测的
• 采用最早截止时间优先调度算法
• 根据任务的截止时间来确定任务的优先级

例子

针对具有开始限制的非周期性实时任务

此类任务是非周期性的，不可预测的，若采用EDF算法，存在危险性。

若在任务就绪前，预先知道任务的开始截止时间，则可以采用允许CPU空闲的EDF调度算法(Earliest Deadline with Unforced Idle Times)。

允许CPU空闲的EDF调度算法

优先调度截止时间最早的合格任务，并让该任务运行完毕。

合格任务可以是还未就绪，但是事先知道其开始截止时间任务。

尽管CPU的利用率不高，但这种调度算法可以保证系统中的任务都能按要求完成。

七、速率单调调度

• 速率单调调度算法（Rate Monotonic Scheduling，RMS）

• 周期性任务

• 任务速率：任务周期(以秒计)的倒数，以赫兹为单位

• 优先级的确定

  • 任务周期越短，优先级越高
  • 优先级函数是任务速度的单调递增的函数

• 系统按任务优先级的高低进行调度

八、实时系统处理能力限制

假定系统中有$m$个周期性的硬实时任务，任务$i$的处理时间为$C_i$，周期为$P_i$，则在单处理机情况下，必须满足下面的限制条件：

$\sum_{i=1}^{m} \leq 1$

CPU的利用率 = 任务执行时间 / 任务周期，上式表示系统中各个任务的处理器利用率总和不能超过1。

九、优先级反转

是一种不希望发生的任务调度状态。在该种状态下，一个高优先级任务间接被一个低优先级任务所抢先(preempted)，使得两个任务的相对优先级被倒置。

可发生于任何基于优先级的可抢占的调度方案中。

优先级反转例子

• T1：周期性检查太空船和软件状况
• T2：处理图片数据
• T3：随机检查设备状态
• 优先级：T3 < T2 < T1
• s：二元信号量，用以访问临界区

优先级反转解决

优先级继承：优先级较低的任务继承任何与其共享同一资源的优先级较高的任务的优先级