3.4 实时调度
L17
学习目标
死锁有四个必要条件；预防、避免（银行家）、检测与解除是四条路。MCU 固件里更常见的是两个任务互相等锁——用设计避免，而不是上完整检测器。
- 四条件：互斥、占有且等待、不可抢占、循环等待。破坏任一条件即可预防。
- 银行家算法用安全序列避免进入不安全状态，实现代价高，适合动画理解。
- 固件实例：任务 A 持 UART 锁等 GPIO，任务 B 持 GPIO 锁等 UART。超时放弃是工程折中。
- 截止期错过=失败。
- 本课不实现完整 EDF。
原理 · 深入理解
3.4 实时调度
本节概览：先建立「实时调度」的框架，再依次展开下列小节。
- 实现实时调度的基本条件
- 实时调度算法的分类
- 最早截止时间优先EDF(Earliest Deadline First)算法
- 最低松弛度优先LLF(Least Laxity First)算法
- 优先级倒置（Priority Inversion Problem）
3.4.1 实现实时调度的基本条件
为了实现实时调度，系统应向调度程序提供有关任务的信息。
- 处理时间：任务从开始执行到完成所需的时间
- 资源要求：任务执行所需的一组资源
- 就绪时间：任务成为就绪状态的起始时间
- 开始截止时间和完成截止时间
- 优先级
假定系统中有 m 个周期性硬实时任务 HRT，处理时间 Ci，周期 Pi，单处理机下必须满足 ΣCi/Pi≤1 才可调度。
提高处理能力有两条路：一是增强单处理机能力以减少处理时间；二是采用多处理机系统，条件改为 ΣCi/Pi≤N。
为保证硬实时任务及时运行，系统还需具有快速切换机制，具备两方面的能力。
- 对中断的快速响应能力
- 快速的任务分派能力
3.4.2 实时调度算法的分类
实时调度算法可按不同方式分类：按任务性质分为硬实时和软实时；按调度方式分为非抢占和抢占。
非抢占式轮转调度用于控制多个相同对象；非抢占式优先调度为实时任务赋予较高优先级。
抢占式调度根据抢占时机分为两种。
- 基于时钟中断的抢占式优先级调度算法
- 立即抢占（Immediate Preemption）的优先级调度算法
3.4.3 最早截止时间优先EDF(Earliest Deadline First)算法
EDF 算法用于非周期实时任务的非抢占式调度：按截止时间先后安排执行顺序。
结合图 3-7 理解 EDF 算法用于抢占调度方式的示例。
EDF 算法用于周期实时任务的抢占式调度：每当新任务到达时，选择截止时间最早的进程执行。
3.4.4 最低松弛度优先LLF(Least Laxity First)算法
LLF 算法根据任务的紧急（松弛）程度确定优先级：任务越紧急优先级越高，主要用于可抢占调度方式。
以两个周期性实时任务 A（20ms 周期/10ms 执行）和 B（50ms 周期/25ms 执行）为例说明调度过程。
两个周期性实时任务的调度情况：根据松弛度计算各时间点的优先级，选择松弛度最小的任务执行。
结合图 3-9 理解利用 LLF 算法进行调度的情况。
3.4.5 优先级倒置（Priority Inversion Problem）
优先级倒置现象：高优先级进程被低优先级进程延迟或阻塞。
三个进程 P1（最高）、P2、P3（最低），P1 和 P3 共享一个临界资源。
P3 先执行进入临界区 CS-3，之后 P2 就绪抢占 P3。当 P1 就绪时，因 P3 占着临界资源，P1 被阻塞，而 P2 在运行——高优先级的 P1 被低优先级的 P2 延迟了。
解决方法：规定 P3 进入临界区后不允许被抢占；或采用动态优先级继承，让 P3 临时继承 P1 的优先级以尽快完成。
结合图 3-11 理解采用动态优先级继承方法后三个进程的运行情况。
做 · 交互动画
- 根据「学习目标」列出 3 个关键词，对照原理段落解释给自己听。
实时调度
用控件单步操作；日志区记下每一步发生了什么。
总结与提升
- 能默写死锁四条件，并举一个固件中的例子。
- 能用自己的话复述学习目标，并指出概念与板上实验的对应。
- 能区分硬实时与软实时。
延伸思考
- 超时放弃算不算「解除死锁」？
- 如果把本节机制拿到 Linux 或完整 OpenHarmony 上，会多出哪些硬件假设？
- 灯带刷新是硬实时还是软实时？