操作系统中的实时调度算法

描述
实时调度算法是操作系统为实时任务分配CPU时间的策略，需在严格时间限制内完成任务，否则可能导致系统失效。分为硬实时（错过截止时间即失败）和软实时（允许偶尔超时）。核心目标是最小化任务错过截止时间的概率，常用算法包括速率单调调度（RMS）和最早期限优先（EDF）。

知识点详解

1. 实时任务的关键参数

   • 周期（T）：任务周期性触发的时间间隔（如每10ms执行一次）。
   • 执行时间（C）：任务单次执行所需的最长CPU时间。
   • 截止时间（D）：任务必须完成的最后期限（通常D=T，即周期结束时截止）。
   • 任务利用率（U）：U = C/T，表示任务占用CPU的比例。

2. 可调度性条件
   系统可调度的前提是总利用率不超过理论上限：

   • 所有任务利用率之和 ≤ 1（CPU不超载）。
   • 具体上限取决于算法（如RMS为69%，EDF为100%）。

解题过程：以速率单调调度（RMS）为例

1. 算法规则

   • 任务优先级与周期成反比：周期越短，优先级越高。
   • 优先级固定，调度器总是运行就绪任务中周期最短的一个。

2. 可调度性测试
   假设系统有两个周期性任务：

   • 任务A：T₁=5ms, C₁=2ms
   • 任务B：T₂=10ms, C₂=3ms
     步骤1：计算利用率
     U₁ = 2/5 = 0.4, U₂ = 3/10 = 0.3, 总利用率 U = 0.7
     步骤2：检查RMS上限
     RMS的理论上限为 n(2^(1/n)-1)，n=2时上限≈0.828。
     ∵ 0.7 < 0.828 ∴ 可能可调度（需进一步验证）。
     步骤3：时间点分析
     检查每个任务的最坏响应时间（任务就绪后到完成的最长时间）：
   • 任务A的响应时间等于C₁=2ms（因优先级最高，不会被抢占）。
   • 任务B的响应时间需计算其被高优先级任务（A）抢占的影响：
     响应时间 R₂ = C₂ + 抢占时间。
     首次计算：R₂ = 3 + ceil(3/5)×2 = 3 + 2 = 5ms（ceil表示向上取整）。
     由于5ms < T₂=10ms，任务B可调度。

3. 对比EDF算法

   • EDF动态分配优先级：截止时间越早，优先级越高。
   • 可调度条件更宽松：总利用率≤100%即可调度。
   • 上例中若任务B的C₂增至4ms（U=0.4+0.4=0.8），RMS不可调度（0.8>0.828），但EDF仍可调度。

总结

• RMS适合优先级固定的场景，实现简单但利用率低。
• EDF利用率高，但动态优先级可能增加调度开销。
• 选择算法需权衡实时性要求与系统负载。