实时系统中的任务

实时操作系统 (RTOS) 为实时应用程序提供服务，这些应用程序在没有任何缓冲延迟的情况下处理数据。在 RTOS 中，处理时间要求以十分之一秒为增量计算。它是一个有时间限制的系统，被定义为具有固定时间约束。在这种类型的系统中，处理必须在规定的约束内完成。否则，系统将失败。

实时任务 是与时间定量表达式相关的任务。这种时间定量表达式描述了实时任务的行为。实时任务被调度以在时间约束内完成其中涉及的所有计算事件。与实时任务相关的时间约束是截止日期。所有实时任务都需要在截止日期前完成。例如，与设备的输入-输出交互、网页浏览等。

实时系统中的任务类型

实时系统中的任务类型如下：

1. 周期任务

在周期任务中，作业以固定的时间间隔释放。周期任务会在固定的时间间隔后重复自身。周期任务由五个元组表示：T_i = < Φ_i, P_i, e_i, D_i >

其中，

• Φ_i: 这是任务的相位，相位是任务中第一个作业的释放时间。如果未指定相位，则假定第一个作业的释放时间为零。
• P_i: 这是任务的周期，即两个连续作业释放时间之间的时间间隔。
• e_i: 这是任务的执行时间。
• D_i: 这是任务的相对截止日期。

例如：考虑周期为 5 且执行时间为 3 的任务 T_i

未给出相位，因此假设第一个作业的释放时间为零。所以这个任务的作业在 t = 0 时首次释放，然后执行 3 秒，然后下一个作业在 t = 5 时释放，执行 3 秒，下一个作业在 t = 10 时释放。因此，作业在 t = 5k（其中 k = 0, 1, . . . N）时释放。

一组周期任务的超周期是该集合中所有任务的最小公倍数。例如，两个周期分别为 4 和 5 的任务 T₁ 和 T₂ 的超周期为 H = lcm(p1, p2) = lcm(4, 5) = 20。超周期是作业释放时间模式开始重复后的时间。

2. 动态任务

它是一个由事件发生而调用的顺序程序。事件可能由系统外部的进程或系统内部的进程生成。动态到达的任务可以根据其重要性和对其发生时间的了解进行分类。

1. Aperiodic Tasks（非周期任务）: 在此类任务中，作业以任意时间间隔释放。非周期任务具有软截止日期或没有截止日期。
2. Sporadic Tasks（突发任务）: 它们类似于非周期任务，即它们在随机实例中重复。唯一的区别是突发任务具有硬截止日期。突发任务由三个元组表示：T_i =(e_i, g_i, D_i)
   • 其中
   • e_i: 这是任务的执行时间。
   • g_i: 这是任务两次连续发生实例之间的最小间隔。
   • D_i: 这是任务的相对截止日期。

3. 关键任务

关键任务是指那些及时执行至关重要的任务。如果错过截止日期，将导致灾难。

例如，生命支持系统和飞机的稳定性控制。如果关键任务以更高的频率执行，那么这是必要的。

4. 非关键任务

非关键任务是实时任务。顾名思义，它们对应用程序并不关键。但是，它们可以处理时间，变化的数据，因此如果未在截止日期内完成，它们就毫无用处。调度这些任务的目标是最大化在截止日期内成功执行的作业的百分比。

任务调度

实时任务调度本质上是指操作系统如何选择各种任务进行执行。每个操作系统都依赖一个或多个任务调度程序来准备运行各种任务所需的执行计划。每个任务调度程序都由其采用的调度算法来表征。到目前为止，已经开发了大量的实时调度任务算法。

任务调度分类

实时系统中的任务调度类型如下：

1. 有效调度 (Valid Schedule): 一组任务的有效调度是指在任何时候最多只有一个任务被分配给一个处理器，没有任务在到达时间之前被调度，并且满足所有任务的优先和资源约束。
2. 可行调度 (Feasible Schedule): 有效调度只有在所有任务都在调度中满足各自的时间约束时，才称为可行调度。
3. 高效调度器 (Proficient Scheduler): 如果任务调度程序 S1 可以可行地调度 S2 可以调度的所有任务集，而 S2 不能（反之亦然），则 S1 比 S2 更高效。S1 可以可行地调度 S2 可以调度的所有任务集，但至少有一个任务集 S2 无法可行地调度，而 S1 可以。如果 S1 可以可行地调度 S2 可以调度的所有任务集，并且反之亦然，则 S1 和 S2 称为同样高效的调度程序。
4. 最优调度器 (Optimal Scheduler): 实时任务调度程序如果在任何其他调度程序可以可行调度的任何任务集都可以可行地调度，则称为最优调度程序。换句话说，不可能找到比最优调度程序更高效的调度算法。如果最优调度程序无法调度某个任务集，那么任何其他调度程序都不应为该任务集产生可行调度。
5. 调度点 (Scheduling Points): 调度程序的调度点是时间线上的点，调度程序在这些点上就下一个要运行的任务做出决策。重要的是要注意，任务调度程序不需要连续运行，并且操作系统仅在调度点激活它以决定下一个要运行的任务。在时钟驱动的调度程序中，调度点被定义为由时钟的周期性定时器生成的中断标记的瞬时。在事件驱动的调度程序中，某些事件的发生决定了调度点。
6. 可抢占调度程序 (Preemptive Scheduler): 可抢占调度程序是指，当较高优先级的任务到达时，它会挂起任何可能正在执行的较低优先级任务，并接管较高优先级的任务进行执行。因此，在可抢占调度程序中，不能出现较高优先级的任务已准备好并等待执行，而较低优先级的任务正在执行的情况。被抢占的较低优先级任务只有在没有较高优先级的任务准备好时才能恢复执行。
7. 利用率 (Utilization): 任务的处理器利用率（或简称为利用率）是指它在每个时间间隔内执行的平均时间。用符号表示
   对于周期任务 T_i，利用率 u_i = e_i/p_i，其中
   • e_i 是执行时间，
   • p_i 是 T_i 的周期。
   
   对于一组周期任务 {T_i}：所有任务的总利用率 U = i=1∑ n e_i/p_i。
   任何好的调度算法的目标是即使是那些利用率非常高的任务集（即利用率接近 1）也能可行地调度。当然，在单处理器上，不可能调度利用率超过 1 的任务集。
8. 抖动
   抖动 (Jitter) 是周期任务偏离其严格周期行为的偏差。到达时间抖动是任务偏离精确周期到达时间。它可能由不精确的时钟或其他因素（如网络拥塞）引起。类似地，完成时间抖动是任务完成时间偏离精确周期点。
   完成时间抖动可能由所采用的特定调度算法引起，该算法根据便利性和瞬时负载来调度任务，而不是在某些严格的时间点进行调度。对于某些应用程序来说，抖动是不可取的。
   有时作业的实际释放时间是未知的。只知道 r_i 在范围 [r_i-, r_i+] 内。此范围称为释放时间抖动。此处
   • r_i- 是作业最早可以释放的时间，
   • r_i+ 是作业最晚可以释放的时间。
   只知道作业的执行时间范围 [e_i-, e_i+]。此处
   • e_i- 是作业完成执行所需的最短时间，
   • e_i+ 是作业完成执行所需的最长时间。

作业的优先约束

如果作业可以按任何顺序执行，则任务中的作业是独立的。如果作业必须按特定顺序执行，则称作业具有优先约束。为了表示作业的优先约束，使用偏序关系 <，这称为优先关系。如果 J_i < J_j，则作业 J_i 是作业 J_j 的前驱，即 J_j 在 J_i 完成之前不能开始执行。如果 J_i < J_j，并且不存在其他作业 J_k 使得 J_i < J_k < J_j，则 J_i 是 J_j 的直接前驱。如果 J_i < J_j 或 J_j < J_i 都不成立，则 J_i 和 J_j 是独立的。

表示优先约束的有效方法是使用有向图 G = (J, <)，其中 J 是作业集。此图称为优先图。图的顶点表示作业，优先约束使用有向边表示。如果从 J_i 到 J_j 有一条有向边，则表示 J_i 是 J_j 的直接前驱。

例如：考虑一个任务 T，它有 5 个作业 J₁, J₂, J₃, J₄ 和 J₅，使得 J₂ 和 J₅ 在 J₁ 完成之前不能开始执行，并且没有其他约束。此示例的优先约束是

J₁ < J₂ 和 J₁ < J₅

优先图的集合表示

1. < (1) = { }
2. < (2) = {1}
3. < (3) = { }
4. < (4) = { }
5. < (5) = {1}

再举一个例子，给出了一个优先图，需要找出优先约束。

从上面的图，我们得出以下优先约束

1. J₁< J₂
2. J₂< J₃
3. J₂< J₄
4. J₃< J₄