实时系统中的任务

系统具有实时性，即应保证在指定的时间约束内响应或系统应满足指定的期限。例如飞行控制系统、实时监视器等。  实时系统中有两种类型的任务： 

1. 定期任务
2. 动态任务

• 周期性任务：在周期性任务中，作业会定期发布。周期性任务是在固定时间间隔后重复自身的任务。周期性任务由四个元组表示：T _i = < Φ _i , P _i , e _i , D _i > 其中， 
  • Φ _i – 是任务的阶段。Phase 是任务中第一个作业的发布时间。如果未提及阶段，则假定第一个作业的发布时间为零。
  • P _i – 是任务的周期，即两个连续作业的发布时间之间的时间间隔。
  • e _i – 是任务的执行时间。
  • D _i – 是任务的相对截止日期。

例如：考虑周期 = 5 和执行时间 = 3的任务 T _i 没有给出阶段，因此假设第一个作业的发布时间为零。所以这个任务的作业首先在 t = 0 释放，然后执行 3s，然后下一个作业在 t = 5 释放，执行 3s，然后下一个作业在 t = 10 释放。所以作业在t = 5k 其中 k = 0, 1, . . ., n 一组周期性任务的超周期是该集合中所有任务的周期的最小公倍数。例如，分别具有周期 4 和 5 的两个任务 T ₁和 T ₂将有一个超周期，H = lcm(p1, p2) = lcm(4, 5) = 20。超周期是工作发布时间开始重复。

• 动态任务：它是一个由事件发生调用的顺序程序。事件可能由系统外部的进程或系统内部的进程生成。动态到达的任务可以根据它们的重要性和关于它们的发生时间的知识进行分类。 
  1. 非周期性任务：在这种类型的任务中，作业以任意时间间隔发布，即随机发布。非周期性任务有软期限或没有期限。
  2. 零星任务：它们类似于非周期性任务，即它们在随机实例中重复。唯一的区别是零星的任务有严格的截止日期。零星任务由三个元组表示：T _i =(e _i , g _i , D _i ) 其中  e _i – 任务的执行时间。  g _i – 任务的两个连续实例的出现之间的最小间隔。  D _i - 任务的相对截止日期。

抖动：有时不知道作业的实际发布时间。只知道 r _i在 [ r _i -, r _i + ] 范围内。这个范围被称为释放时间抖动。这里 r _i – 是可以多早发布工作，而 r _i + 是可以多晚发布工作。只有作业执行时间的范围 [ e _i -, e _i + ] 是已知的。这里 e _i – 是作业完成其执行所需的最短时间， e _i + 是作业完成其执行所需的最长时间。  作业的优先级约束：任务中的作业如果可以按任何顺序执行，则它们是独立的。如果任务中的作业必须执行的特定顺序，则称作业具有优先约束。为了表示作业的优先约束，使用了偏序关系 <。这称为优先关系。如果 J _i < J _j即 J _{j在 J i}完成之前无法开始执行，则作业 J _i是作业 J _{j的前身。}如果 J _i < J _j并且没有其他工作 J _k满足 J _i ，则J _{i是 J j}的直接前任< J _k < 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 _{5在 J 1}完成并且没有其他约束 之前不能开始执行。 此示例的优先约束为：  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 ₄