SCHEDULER / THEORY
调度理论 Scheduling Theory
调度算法决定任务如何获得处理器时间；调度理论进一步研究任务能否在执行时间、 优先级、资源阻塞与中断干扰等约束下满足截止时间。 从机制设计走向时间约束验证，是理解实时系统的重要一步。
调度理论研究什么
从任务按时执行，转向任务是否能够按时执行。
实时系统的正确性不仅取决于计算结果，也取决于结果是否在规定时间内产生。 调度理论研究在给定处理器能力、任务执行需求、调度策略和系统干扰条件下， 任务集合是否满足各自的时间约束。
任务需要多少处理器时间，以及最坏情况下需要多久。
任务何时就绪、何时运行，以及高优先级任务如何影响其他任务。
任务必须完成的时间边界，以及系统能否满足这一要求。
因此，实时性不能仅凭平均运行速度、较短的实测延迟或任务能够正常运行来判定。 这些数据可以提供证据，但是否满足时间约束，还取决于分析模型与覆盖范围。
实时任务模型
先明确任务的时间属性，才能讨论调度是否可行。
对一个具有明确时间约束的任务，可以使用以下参数描述其关键属性。 具体模型需要根据任务是周期执行、偶发执行还是一次性执行进行选择。
对周期任务，还需要描述任务的周期与可能的释放抖动； 对偶发任务，则通常需要明确最小到达间隔或到达模式。 固定优先级系统还需记录任务优先级，以及可能影响其执行的资源阻塞和中断干扰。
任务参数并非仅靠命名即可确定。尤其是 WCET，它必须对应明确的代码路径、 编译配置、处理器时序和系统执行条件。缺少这些条件时，估计值不等于已建立的最坏情况上界。
最坏执行时间与响应时间
任务执行成本只是分析起点，不是最终的截止时间结论。
最坏执行时间（WCET）
WCET 描述任务在指定硬件、软件构建和执行假设下， 完成相关计算所需处理器时间的可信上界。
- 识别代码路径与循环边界
- 分析指令执行成本及分支影响
- 明确编译器、时钟和硬件条件
- 考虑分析方法无法覆盖的路径与干扰
响应时间（Response Time）
响应时间衡量任务从释放到完成所经历的时间。 它可能包含等待调度、被更高优先级任务抢占、资源阻塞以及中断干扰。
对具有截止时间约束的任务，需要将分析得到的最坏响应时间与相应截止时间比较， 而不是只检查任务自身的执行时间。
可调度性分析
判据必须与调度算法、任务模型和分析假设一致。
可调度性分析（Schedulability Analysis）用于判断给定任务集合在指定系统模型下， 是否能够满足其时间约束。不存在适用于所有任务模型和调度策略的单一利用率公式。
处理器利用率
对周期任务，该式可用于描述长期平均处理器需求。 它是重要的系统负载指标，但单独使用时通常不足以证明任意任务集合可调度。
固定优先级响应时间分析
在经典单处理器、固定优先级、可抢占周期任务模型下， 该形式用于表达任务自身执行、高优先级任务干扰和阻塞的关系。 求解时通常需要迭代，并将适用的中断干扰等因素纳入模型。
上述响应时间公式是经典分析形式的简化表达，不是适用于所有 HRTOS 配置的通用公式。 其中 Bᵢ 表示任务可能遭遇的阻塞上界；求和项表示优先级高于任务 i 的任务所产生的干扰。 若存在非抢占区、复杂资源协议、任务释放抖动或其他中断源，就需要相应扩展模型。
对经典单处理器、抢占式 EDF 调度而言，在任务具有隐式截止时间 （Dᵢ = Tᵢ）且满足相应模型假设时，利用率不超过 1 可以作为可调度性判据。 这一结论不能直接推广到任意截止时间、任意任务模型或任意调度算法。
从系统建模到时间约束验证
每一步都需要明确输入、假设和可验证的输出。
确定释放模式、周期、截止时间、优先级与任务关系。
估计或分析 WCET，并明确硬件与构建条件。
考虑抢占、中断、临界区及共享资源等待。
使用匹配的判据或响应时间分析检查时间约束。
如果任务到达模式、执行成本上界或阻塞时间等关键参数尚未明确， 分析结论就必须保留相应限制。模型不完整并不意味着系统不能工作， 但意味着现有分析不足以支持完整的可调度性保证。
影响时间保证的系统因素
调度器之外的执行路径，同样可能决定最坏响应时间。
- 中断响应与中断干扰： 中断进入、处理和退出的成本，以及中断屏蔽区间，会影响任务可获得处理器时间的时刻。
- 临界区与资源阻塞： 共享资源访问、不可抢占区间和同步机制，可能延长任务的等待时间。
- 上下文切换与调度开销： 保存和恢复上下文、更新任务状态及执行调度逻辑，都属于系统运行成本。
- 内存与运行时行为： 动态内存操作、不可预测的等待以及运行时库行为，在确实影响执行路径时需要纳入分析。
- 硬件与编译配置： 指令时序、存储访问、时钟配置和生成的机器代码，都会影响执行时间的分析依据。
分析、测量与保证的边界
三者相互补充，但不能相互替代。
依赖明确的模型、假设和分析方法，目标是论证所覆盖条件下的时间约束。
帮助发现延迟、抖动和异常路径，但测试结果本身不证明所有执行情形均已覆盖。
需要结合任务、调度器、中断、资源协议、硬件与应用负载，核对分析假设是否成立。
实时性保证来自完整证据链
一个系统可以具备实时调度机制，也可以通过实测表现出良好的响应能力； 但要对特定任务集合提出严格的截止时间保证，还需要证明相应的执行时间上界、 干扰与阻塞边界、调度判据及其适用条件成立。 因此，应将内核机制能力、实测性能和已论证的实时性保证分别描述。
调度理论与 HRTOS 架构
从内核实现能力，连接到系统级时间行为分析。
对 8051 等资源受限平台而言，调度理论还需要面对有限的数据存储空间、 中断入口与返回开销、寄存器组与上下文保存策略，以及内核临界区等具体约束。 这些因素不能仅从抽象调度算法中推导出来，而需要结合实际内核实现与目标硬件分析。
对 HRTOS 来说，调度器、任务上下文、中断处理和内核执行路径构成了分析系统时间行为的基础。 通过对关键路径进行测量、分析与验证，可以逐步建立更可信的时间成本模型。 具体任务能否满足截止时间，仍需结合目标应用的任务参数、执行路径和干扰条件单独判断。