操作系统中的进程调度算法：实时调度算法 1. 问题描述 实时调度算法是操作系统为 实时任务 分配CPU时间的策略，其核心目标是确保任务在 截止时间（Deadline） 前完成。与通用调度算法（如CFS）不同，实时调度强调 可预测性 和 时间约束 ，适用于工业控制、自动驾驶等场景。实时任务分为两类： 硬实时任务 ：错过截止时间会导致系统失败（如刹车信号）。 软实时任务 ：偶尔错过截止时间可容忍，但需最小化延迟（如视频流）。 2. 实时调度的关键参数 每个实时任务包含以下属性： 执行时间（C） ：任务所需CPU时间。 周期（T） ：任务周期性触发的时间间隔。 截止时间（D） ：任务必须完成的最后期限（通常D ≤ T）。 优先级 ：根据任务紧急程度静态或动态分配。 3. 常见实时调度算法 3.1 速率单调调度（Rate-Monotonic Scheduling, RMS） 适用场景 ：周期性任务，且截止时间等于周期（D = T）。 规则 ：任务周期越短，优先级越高（优先级与周期成反比）。 可调度性测试 ：若任务数n满足以下条件，则任务集可调度： \[ \sum_ {i=1}^{n} \frac{C_ i}{T_ i} \leq n(2^{1/n} - 1) \] 举例：两个任务（T1=5ms, C1=2ms；T2=10ms, C2=3ms）。 计算利用率：2/5 + 3/10 = 0.7 ≤ 2(√2 -1) ≈ 0.828 → 可调度。 优先级：T1周期短，优先级更高。 3.2 最早截止时间优先（Earliest Deadline First, EDF） 适用场景 ：动态优先级调度，适用于周期性或非周期性任务。 规则 ：总是优先执行当前 截止时间最早 的任务。 可调度性测试 ：若任务总利用率满足以下条件，则任务集可调度： \[ \sum_ {i=1}^{n} \frac{C_ i}{T_ i} \leq 1 \] 举例：两个任务（T1=5ms, C1=2ms；T2=10ms, C2=4ms）。 利用率：0.4 + 0.4 = 0.8 ≤ 1 → 可调度。 调度过程：初始时，T1的截止时间（5ms）早于T2（10ms），先执行T1。 4. 算法对比与挑战 RMS ：静态优先级，实现简单，但CPU利用率较低（≤69%当n→∞）。 EDF ：动态优先级，CPU利用率可达100%，但需频繁计算截止时间，开销较大。 挑战 ： 优先级反转 ：高优先级任务被低优先级任务阻塞（需用优先级继承解决）。 上下文切换开销 ：频繁切换任务可能影响实时性。 5. 实际应用 Linux的实时调度器支持 SCHED_ FIFO （静态优先级，无时间片）和 SCHED_ RR （轮转分配时间片），两者均基于固定优先级调度，而EDF需通过补（如SCHED_ DEADLINE）实现。