一、概述

嵌入式系统中的任务调度算法是实时操作系统（RTOS）的核心功能之一，负责决定何时执行哪个任务，以确保系统资源的高效利用和实时性需求的满足。而现如今常用的实时调度算法有三种：单调速率调度（RMS），最早截止时间优先（EDF），最低松弛时间优先（LLF）。这也是本篇文章要详细讲一讲的东西，当然这里提一嘴与其对应的目前常用的非实时调度算法，有以下几种：最低松弛时间优先（LLF），短作业优先（SJF），时间片轮转（RR），优先级调度。

当然也要详细讲一讲不同的调度算法的选择，我们开发人员会因为系统的实时性需求、任务特性（如周期性和非周期性）、资源限制等因素，选择合适的调度算法。

二、详解

1. 单调速率调度（RMS）1)是什么

单调速率调度（RMS）是1973年Liu和Layland提出来的，它是一种经典的静态优先级实时任务调度算法，通过将任务的优先级与周期建立单调递减关系，确保高优先级任务能够及时完成。就目前看来单调速率调度已经成为在单处理器环境下最优的静态优先级调度算法，目前，广泛应用于航空航天、工业控制、医疗设备等对实时性要求极高的领域。

2)模型

RMS调度算法基于严格的周期性任务模型，每个任务定义为三元组(Ti, Ci, Di)，其中：

Ti：任务的周期，表示任务请求的间隔时间

Ci：任务的执行时间，指处理器在无中断情况下执行该任务所需的时间

Di：任务的截止时间，通常等于周期Ti，即任务必须在下一个周期开始前完成

这些任务必须满足以下基本约束条件：0 ≤ Ci ≤ Ti ≤ Di，确保任务执行时间不超过周期，并且有明确的截止时间要求。

3)调度思想

RMS的核心思想是任务的优先级与周期成反比，周期越短，优先级越高。这种单调递减的优先级分配策略保证了系统中执行频率最高的任务能够获得最高的执行权限，从而满足其严格的实时性要求。

具体而言，调度器遵循以下原则：

1.当高优先级任务到达时，可以抢占正在执行的低优先级任务

2.任务一旦开始执行，必须连续执行直到完成或被更高优先级任务抢占

3.任务在周期起点被激活，周期性地重复执行

4)分配机制

RMS采用静态优先级分配，即在系统启动或任务创建时确定优先级，之后不再改变。优先级分配规则如下：

将所有任务按周期长短排序：T1 < T2 < T3 < ... < Tn

为周期最短的任务T1分配最高优先级

依次为周期较长的任务分配较低优先级

这种优先级分配机制确保了在任何时刻，处理器总是执行当前可用的最高优先级任务，从而在资源受限的情况下最大化系统实时性。

5)调度过程

RMS调度过程可以分为以下几个关键步骤：

任务激活：在每个周期的起点，任务被激活并加入就绪队列。

优先级比较：调度器检查就绪队列中的所有任务，选择优先级最高的任务执行。

任务执行：选定的高优先级任务开始执行，执行时间固定。

抢占机制：如果有更高优先级的任务到达，可以抢占当前正在执行的任务。

任务完成：任务执行完毕后，调度器继续选择下一个最高优先级的任务执行。

这种可抢占的静态优先级调度机制确保了高优先级任务能够及时获得处理器资源，满足其严格的实时性要求。

6)优缺点

优点：

可预测性强：静态优先级分配使得调度行为可预测，便于系统设计和验证。

实现简单：无需动态调整优先级，降低算法复杂度和运行时开销。

理论支持充分：通过Liu & Layland定理提供严格的可调度性分析方法。

确定性高：在满足可调度性条件时，能够保证所有任务在截止时间内完成。

抗干扰能力强：高优先级任务能够及时响应中断，避免关键任务被延迟。

缺点：

利用率上限低：当任务数n→∞，利用率上限趋近于69.3%，导致处理器资源利用率受限。

饥饿问题：低优先级任务可能因频繁被高优先级任务抢占而长时间无法执行。

仅适用于周期性任务：无法直接处理非周期性或动态变化的任务。

对任务参数敏感：任务参数(周期、执行时间)的微小变化可能导致整个任务集的可调度性分析失效。

缺乏灵活性：静态优先级在任务执行过程中不可调整，难以适应动态变化的系统需求。

2.最早截止时间优先（EDF）

1) 是什么

最早截止时间优先调度算法（Earliest Deadline First, EDF）是一种基于动态优先级的实时任务调度策略，其核心思想是根据任务的截止时间进行优先级排序，确保截止时间最早的高优先级任务能够优先获得处理器资源。与传统的静态优先级调度算法（如速率单调调度RMS）不同，EDF能够灵活适应任务截止时间的变化，为实时系统提供更高效的资源利用和更可靠的截止时间保证。本文将从算法原理、实现机制、优缺点分析及实际应用案例等方面，系统阐述EDF调度算法的完整技术框架。

2) 核心思想

最早截止时间优先调度算法的核心思想是：在调度时，优先选择截止时间最早的任务进行执行。这种动态优先级分配机制使得调度器能够根据任务的紧迫程度实时调整执行顺序，特别适合处理截止时间变化或任务到达时间不固定的实时系统。

EDF算法的数学基础是任务的松弛度（Slack）计算，即松弛度=截止时间-当前时间-剩余执行时间。算法总是选择松弛度最小（即截止时间最近）的任务执行，从而最大限度地减少任务错过截止时间的风险。

3) 任务模型

EDF算法适用于以下类型的任务模型：

周期性任务：具有固定周期和执行时间的任务，如传感器数据采集、控制系统等。

非周期性任务：到达时间不确定、执行时间可变的任务，如事件触发的报警处理。

混合任务集：同时包含周期性和非周期性任务的系统，EDF能够统一处理。

每个任务在EDF系统中通常被描述为四元组(Ti, Ai, Ci, Di)，其中：

Ti：任务的到达时间或周期（对于周期性任务）

Ai：任务的激活时间

Ci：任务的执行时间

Di：任务的截止时间

对于周期性任务，通常Di = Ai + Ti，即任务必须在下一个周期开始前完成。

4) 调度原则

EDF算法遵循以下调度原则：

动态优先级分配：任务的优先级由其截止时间决定，截止时间越早，优先级越高。

抢占式调度：当新任务的截止时间早于当前正在执行任务的截止时间时，可立即抢占处理器资源。

任务就绪队列管理：系统维护一个就绪队列，队列按任务截止时间从早到晚排序。

时间敏感性：调度决策基于实时计算，确保系统能够及时响应任务截止时间的变化。

与静态优先级调度算法（如RMS）相比，EDF的最大优势在于其能够适应任务截止时间的动态变化，而无需在任务创建时确定固定优先级。

5) 实现的机制

①　就绪队列管理

EDF算法的关键实现机制是高效的就绪队列管理。就绪队列按照任务截止时间的早晚进行排序，确保调度器能够快速选择具有最早截止时间的任务。

就绪队列通常采用以下数据结构实现：

优先队列（堆结构）：使用最小堆（Min-Heap）存储任务，堆顶始终是截止时间最早的任务。

时间轮（Time-W轮）：适用于具有固定周期的任务，通过轮转机制快速定位下一个到期任务。

链表结构：对于任务数量较少的系统，可使用简单链表按截止时间排序。

就绪队列的操作包括：

任务插入：当新任务到达或周期性任务激活时，将其插入队列并按截止时间排序。

任务删除：当任务完成执行或被阻塞时，从队列中移除。

队列更新：在时钟中断或任务状态变化时，更新队列中的任务排序。

②　抢占条件与上下文切换

在抢占式EDF实现中，调度器需要确定何时触发抢占：

任务到达抢占：当新任务到达时，如果其截止时间早于当前正在执行任务的截止时间，则立即抢占。

时钟中断抢占：在固定时间间隔（如时钟嘀嗒）触发调度检查，重新评估任务优先级。

任务完成抢占：当前任务完成后，调度器立即选择队列中下一个最早截止时间的任务执行。

抢占过程中，系统需要执行上下文切换操作，保存当前任务的寄存器状态（PCB）、程序计数器和栈指针等信息，并加载新任务的上下文。上下文切换的开销是EDF算法的一个重要考量因素，尤其在高频率抢占场景中。

③　动态优先级调整

EDF算法的核心在于动态调整任务优先级，这主要体现在以下几个方面：

任务到达时的调整：新任务到达后，立即计算其截止时间并插入就绪队列的适当位置。

任务执行过程中的调整：周期性任务在每个周期开始时生成新实例，赋予新的截止时间。

时间推进引起的调整：随着系统时间的推进，各任务的松弛度（截止时间-当前时间）不断变化，需要定期重新计算优先级。

动态优先级调整的实现方式包括：

显式排序：在每个调度决策点重新排序整个队列。

增量更新：仅在任务状态变化时更新队列中的相关位置。

预计算截止时间：对于周期性任务，可预先计算未来多个周期的截止时间，减少实时计算开销。

④　非抢占式EDF实现

在非抢占式EDF实现中，任务一旦获得处理器资源，必须执行完毕或主动放弃才能释放资源。这种实现方式适用于以下场景：

低抢占开销环境：如资源受限的嵌入式系统，减少上下文切换的开销。

非周期性任务调度：如医疗设备中的紧急报警处理，需要确保任务执行完整性。

硬件支持不足：当处理器不支持快速抢占时，采用非抢占式实现。

非抢占式EDF的调度过程：

1.当前任务执行完毕或主动释放处理器。

2.调度器检查就绪队列，选择截止时间最早的任务执行。

3.任务开始执行，直到完成或主动阻塞。

非抢占式EDF的缺点是可能导致长任务阻塞短截止时间任务，从而增加任务错过截止时间的风险。

6) 优缺点

优点：

高资源利用率：理论上可以达到100%的处理器利用率，特别适合资源受限的嵌入式系统。

灵活性：能够处理周期性和非周期性任务的混合调度场景。

动态适应性：根据任务截止时间动态调整优先级，适应任务到达时间的变化。

最优调度保证：在单处理器环境下，EDF被证明是最优的动态调度算法。

缺点：

调度开销大：动态优先级计算和频繁的上下文切换增加了系统开销。

过载风险：当系统总利用率超过1时，EDF无法保证所有任务都能在截止时间内完成。

实现复杂度高：需要维护复杂的就绪队列结构，并实时计算任务截止时间。

确定性不足：动态调度可能导致系统行为难以预测，增加验证难度。

1. 最低松弛时间优先（LLF）

1) 是什么

最低松弛度优先调度算法（Least Slack Time First，简称LSTF，也称为Lowest Laxity First，LLF）是一种在实时系统中广泛应用的动态优先级调度算法，通过精确计算任务的松弛度来确定执行顺序，确保系统能够高效处理周期性实时任务。本文将全面解析LSTF算法的核心原理、实现机制、特点优势及实际应用场景，为理解这一算法提供系统性认知。

2) 松弛度是什么

松弛度（Slack Time）是LSTF算法的核心指标，表示任务从当前时间起，到必须完成之前所剩余的可用时间。松弛度越小，任务越紧急，优先级越高。

3) 未执行任务的松弛度怎么算

对于尚未开始执行的新任务，松弛度计算公式为：

Slack Time = Deadline - Current Time - Service Time

其中：

Deadline：任务的截止时间

Current Time：当前系统时间

Service Time：任务的总执行时间

示例：若有一个任务A，周期为20ms，执行时间为10ms，截止时间为30ms。当系统时间在10ms时，该任务的松弛度为：

Slack(A) = 30ms - 10ms - 10ms = 10ms

4) 已部分执行任务的松弛度计算

对于已经开始执行但尚未完成的任务，松弛度计算公式为：

Slack Time = Deadline - Current Time - Remaining Execution Time

其中：

Remaining Execution Time = Service Time - 已执行时间

示例：若任务B执行时间为25ms，已运行5ms，截止时间为50ms。当系统时间在15ms时，该任务的松弛度为：

Slack(B) = 50ms - 15ms - (25ms - 5ms) = 25ms - 20ms = 5ms

5) 调度规则

LSTF算法的核心调度规则是：始终选择当前松弛度最小的任务作为下一个执行的任务。这种动态优先级分配机制确保了系统能够根据任务的紧急程度实时调整执行顺序。

LSTF算法的调度过程可以分为以下几个步骤：

任务到达：周期性任务在每个周期的开始时间生成新实例

松弛度计算：计算所有就绪任务的松弛度

优先级排序：根据松弛度对任务进行排序，松弛度最小的任务优先级最高

任务选择：选择优先级最高的任务（即松弛度最小的任务）执行

执行监控：持续监控当前执行任务和就绪队列中的任务

任务切换：当新任务到达或当前任务的松弛度变化时，立即切换到松弛度最小的任务

任务完成：任务完成后，更新系统状态，准备下一轮调度

6) 调度机制

LSTF算法通常采用可抢占式调度，这意味着：

1.当一个任务的松弛度减为0时，它必须立即抢占CPU，以保证按时完成

2.当有更高优先级（即更低松弛度）的任务到达时，当前任务会被暂停，让出CPU

3.任务切换时，系统需要保存当前任务的执行状态，以便后续恢复

4.这种抢占机制确保了系统能够及时响应紧急任务，但也会带来一定的调度开销。

若碰到相同松弛度时的处理办法：

当多个任务具有相同的松弛度且为最小时，LSTF算法采用以下次级规则进行调度：

最近最久未调度（LRU）原则：

优先调度最近一次被调度时间最久的任务

任务到达顺序：按照任务到达的先后顺序进行调度

优先级编号：为每个任务预设优先级编号，作为最终判定依据

法核心特点（优点）

动态优先级：任务优先级随松弛度实时变化，而非固定不变

周期性任务优化：直接利用任务周期性和截止期限信息，平衡任务间的调度

可抢占式调度：允许任务被抢占，确保紧急任务优先执行

资源高效利用：通过动态调整任务执行顺序，减少CPU空闲时间

最小响应时间：优先执行剩余处理时间最短、截止时间最近的任务，有效缩短任务响应时间

预防系统过载：通过优先调度松弛度小的任务，有助于在系统过载时优先保证关键任务的截止期限

负载均衡：能够在各个任务之间实现相对均衡的负载分配，提高系统整体性能

8) 算法的局限（缺点）

计算复杂度高：需频繁计算所有就绪任务的松弛度，对系统计算能力有一定要求

调度开销大：频繁的任务切换可能导致调度开销增加，特别是在任务粒度较细的场景

参数敏感：算法效果高度依赖任务参数的准确性，包括周期、执行时间和截止期限

不适用于非周期任务：主要针对周期性任务设计，对非周期任务的处理不如EDF算法灵活

总结

综上通过合理选择调度算法并结合优化策略，嵌入式系统可在资源受限条件下实现高实时性与可靠性。实际应用中需根据任务特性（周期性、截止时间、优先级）综合评估，必要时可采用混合调度方案。

感谢大家看我絮絮叨叨，希望可以对你有所帮助。