嵌入式系统调度算法介绍

嵌入式系统的任务调度算法，核心目的是在资源受限的硬件上，高效、有序地分配CPU时间给多个任务。

先来先服务（FCFS）调度算法

先来先服务（FCFS）调度算法，也称为先进先出（FIFO）算法，是操作系统中最简单、最基础的任务调度策略。其核心思想是“先到先得”，即按照任务到达就绪队列的先后顺序进行调度。

核心规则与运行机制

FCFS的核心在于其非抢占式（Non-preemptive） 的特性。这意味着：
1、排队执行：所有就绪任务在一个队列中按到达时间排序，CPU总是分配给队列最前端的任务。
2、一跑到底：一旦一个任务获得CPU控制权，它就会一直运行，直到任务完成或因等待某事件（如I/O操作）而被阻塞。
3、重新排队：如果一个正在运行的任务因等待而被阻塞，它会被移出CPU。当它被唤醒后，会重新被放到就绪队列的末尾，再次排队等待。

优缺点分析

FCFS的特点是一把双刃剑。

在嵌入式系统中的应用与局限性

应用场景：

1、极简系统：在一些资源极度受限、任务单一且执行时间可预测的超轻量级系统中，FCFS因其极低的实现开销而被采用。
2、特定功能模块：作为其他复杂调度策略的补充，例如处理同优先级任务时，可按FCFS顺序执行。
3、非实时任务：用于调度对时间不敏感的批处理或后台任务。

主要局限：

1、与实时性需求冲突：嵌入式系统常需硬实时响应，而FCFS无法保证关键任务的截止时间，这是其最大缺陷。
2、不适用于复杂RTOS：主流RTOS（如FreeRTOS）的核心是优先级抢占调度，这与FCFS的“先来后到”原则冲突。

“最短作业优先”（Shortest Job First，SJF） 算法

核心思想：短者优先

SJF算法的核心思想非常直观：在所有处于就绪状态的任务中，选择预计执行时间（即“作业”或“任务”的长度）最短的那个任务，优先分配CPU资源。
它的设计初衷是为了改进FCFS（先来先服务）算法的缺点。在FCFS中，一个执行时间很长的任务会阻塞后面所有任务，导致平均等待时间变长（“护航效应”）。SJF通过优先处理“短任务”，可以有效减少系统的平均周转时间和平均等待时间。

两种实现方式

非抢占式 (Non-Preemptive SJF)

规则：一旦一个任务开始运行，即使之后有一个执行时间更短的新任务到达，它也会继续运行直到完成或主动阻塞，才会让出CPU。
特点：实现相对简单，但灵活性稍差。

抢占式 (Preemptive SJF)

规则：当一个新任务到达就绪队列时，系统会比较它的总执行时间和当前正在运行任务的剩余执行时间。如果新任务的总时间更短，那么当前任务会被立即抢占，CPU转而去执行新任务。
专门名称：这种抢占式版本通常被称为 “最短剩余时间优先”（Shortest Remaining Time First，SRTF） 算法。
特点：更加灵活，能进一步优化系统的响应时间，但实现更复杂，上下文切换也更频繁。

优缺点分析

SJF/SRTF算法在追求高效率的同时，也存在一些明显的缺陷。

在嵌入式系统中的应用与局限

应用场景

1、软实时或非实时系统：在一些对时间要求不那么苛刻的系统中，可用于提高效率。
2、批量任务处理：用于处理一组已知执行时间的后台或批处理任务。

主要局限

1、与硬实时需求冲突：最关键的是，SJF无法为高优先级的关键任务提供确定的响应时间保障。一个紧急但执行时间较长的任务，可能会因为不断到来的短任务而被无限期推迟，这在硬实时系统中是不可接受的。
2、执行时间难以预估：在许多嵌入式控制任务中，任务的执行时间受外部条件影响，很难精确预估。

时间片轮转（Round-Robin，RR）调度算法

时间片轮转（Round-Robin，RR）调度算法是一种专为多任务系统设计的公平调度策略。它的核心思想是，让所有处于就绪状态的任务，轮流且平等地获得一小段固定的CPU执行时间。

在嵌入式领域，它和优先级抢占调度是两种最主流的策略。对于同优先级的任务，RR算法能有效防止单一任务长期霸占CPU。

核心概念：时间片

RR算法的核心是时间片（Time Slice 或 Time Quantum）。它指的是一个任务在被强制切换前，允许连续运行的最长时间。

工作流程：当一个任务获得CPU后，调度器会启动一个定时器，开始计时。
超时切换：时间片耗尽时，无论任务是否执行完毕，调度器都会强制中断当前任务。
上下文保存：保存当前任务的运行状态（即“上下文”），以便下次恢复。
重新排队：将该任务移至就绪队列的队尾，等待下一轮调度。

工作流程

1、任务入队：所有就绪任务按照先来先服务（FCFS） 的原则排列在一个循环队列中。
2、调度执行：调度器从队列头部取出一个任务，让其运行一个时间片。
3、检查完成：时间片结束后，检查任务是否已完成：
4、若未完成：将任务放回队列尾部。
5、若已完成或主动阻塞（如等待I/O）：任务立即让出CPU，不再参与本轮排队。
6、循环往复：调度器继续从队列头部取出下一个任务执行，形成一个“Task A → Task B → Task C → Task A …”的循环。

优缺点分析

优点

1、公平性高：所有就绪任务都能公平地获得CPU时间，不会出现“饥饿”现象。

2、响应时间可预测：每个任务等待下次执行的最长时间是确定的。若有 n 个任务，时间片为 q，则最长等待时间为 (n-1)q。

3、实现相对简单：其核心逻辑清晰，资源开销较低。

缺点

1、缺乏实时性保障：无法保证紧急任务被及时响应。紧急任务必须和普通任务一样排队，这在硬实时系统中是不可接受的。
2、上下文切换开销：频繁的任务切换会消耗CPU时间，产生额外开销。
3、时间片大小难抉择，时间片的大小对系统性能影响巨大：
时间片过大：算法会退化为先来先服务（FCFS），失去轮转意义。
时间片过小：任务切换过于频繁，系统开销剧增，降低CPU有效使用率。

应用场景与典型实现

应用场景

1、公平性优先的系统：如多用户操作的人机交互界面（HMI）。
2、无严格实时要求的场景：如温控系统、数据采集等周期性任务。
3、同优先级任务：当多个任务重要性相同时，使用RR保证它们公平共享CPU。

典型实现

1、在FreeRTOS中，RR通常与抢占式调度结合使用。
2、通过配置 configUSE_PREEMPTION 和 configUSE_TIME_SLICING 这两个宏，可以启用“抢占式调度 + 同优先级时间片轮转”的模式。这是绝大多数STM32项目采用的经典配置。
3、在这种模式下，高优先级任务可以随时抢占低优先级任务，而同优先级的任务则通过时间片轮转来共享CPU。

优先级调度算法

优先级调度算法是现代嵌入式实时操作系统（RTOS）的核心。其基本思想是：为每个任务分配一个优先级，调度器会确保CPU始终优先执行当前处于就绪状态的、优先级最高的任务。

核心机制：两种实现方式

抢占式优先级调度 (Preemptive Priority Scheduling)

这是最常见也是最重要的模式。其规则是，一旦一个更高优先级的任务进入就绪状态，调度器会立即暂停当前正在运行的（较低优先级的）任务，保存其上下文，并立刻将CPU控制权交给高优先级任务。这种模式能确保关键任务得到最及时的响应，是硬实时系统的首选。

非抢占式优先级调度 (Non-preemptive Priority Scheduling)

在这种模式下，即便有更高优先级的任务就绪，也无法中断当前正在运行的任务。当前任务必须主动放弃CPU（如等待I/O或主动调用延时函数）后，调度器才会重新选择最高优先级的任务执行。这种模式减少了任务切换开销，但实时性较差，适用于软实时系统。

优先级分类：静态与动态

任务的优先级可以是固定的，也可以是变化的。

静态优先级 (Static Priority)：任务在创建时被赋予一个固定的优先级，并在整个运行期间保持不变。速率单调调度（RMS） 算法是静态优先级调度的经典代表，它为周期越短（执行频率越高）的任务分配更高的优先级。静态优先级算法实现简单，开销小。
动态优先级 (Dynamic Priority)：任务的优先级可以根据系统状态（如任务的等待时间、截止时间等）在运行时动态调整。最早截止时间优先（EDF） 算法是典型代表，它动态地为截止时间更早的任务分配更高优先级。动态优先级能实现更高的CPU利用率（理论上限可达100%），但调度开销也更大。

关键挑战与解决方案：优先级反转

问题描述：当一个高优先级任务和低优先级任务共享某个资源（如互斥锁）时，低优先级任务可能先获得了该资源。此时，高优先级任务因等待资源而被阻塞，而一个中等优先级的任务（不共享该资源）却可以运行，从而抢占了CPU，导致高优先级任务被间接地、无限期地推迟。

典型解决方案：
1、优先级继承 (Priority Inheritance)：当高优先级任务因等待低优先级任务持有的资源而被阻塞时，系统会临时将低优先级任务的优先级提升到与高优先级任务相同。这样，低优先级任务就能快速执行并释放资源，从而解除阻塞。这是目前最主流的解决方案，被FreeRTOS等主流RTOS采用。
2、优先级天花板 (Priority Ceiling)：系统为每个资源预设一个“天花板优先级”（等于可能使用该资源的所有任务中的最高优先级）。任何任务想要获取资源，其当前优先级必须高于该资源的天花板优先级，否则会被阻塞。这种协议能更彻底地避免反转，但实现更复杂。

优先级反转的经典案例：火星探路者号的“死机”危机

1997年，NASA的火星探路者号在着陆后不久，频繁出现系统重启，导致与地球的通信中断。事后分析发现，罪魁祸首正是优先级翻转。
1、问题根源：一个低优先级的“气象数据采集”任务长期占用了一个共享资源（一个互斥锁）。
2、翻转发生：一个中等优先级的“通信任务”抢占了CPU，导致低优先级任务无法释放资源。
3、最终后果：一个高优先级的“总线管理任务”因等待该资源而被无限期阻塞。系统的“看门狗”定时器检测到高优先级任务长时间未执行，判定系统故障，于是触发了系统复位（重启）。
这个案例清晰地展示了优先级翻转如何从软件逻辑问题演变为物理上的系统“死机”或重启。

技术原理：为什么会死机？

要理解其致死机制，我们需要看一个典型场景：

1、初始状态：低优先级任务（L）获得了共享资源R的锁。
2、高优先级就绪：高优先级任务（H）就绪，它需要资源R，但被L占用，因此H被阻塞，等待L释放R。
3、翻转发生：此时，一个与资源R无关的中等优先级任务（M） 就绪。由于M的优先级高于L但低于H（而H被阻塞无法运行），系统调度器会让M抢占CPU执行。
4、陷入僵局：任务M持续运行，导致低优先级任务L无法获得CPU，也就无法释放资源R。因此，高优先级任务H只能无限期地等待。

死机的原因就出现在这一步：如果中优先级任务M一直运行（例如，陷入了一个死循环），那么低优先级任务L就永远无法执行，高优先级任务H也就永远无法获得资源。整个系统最核心的高优先级任务被“饿死”，系统响应完全停滞，对外表现为死机。

总结来说：优先级反转不一定会带来死机，但是给死机创造了条件。

优先级分组算法

组内同优先级，组间不同优先级。

调度器首先选择优先级最高的非空组。在该组内部，任务之间则采用时间片轮转（Round-Robin） 或先来先服务（FCFS） 的方式进行调度。

实际应用：以FreeRTOS为例

FreeRTOS是广泛使用的开源RTOS，其调度策略完美体现了优先级调度的核心思想。

默认策略：抢占式优先级调度 + 同优先级任务的时间片轮转。
工作机制：
不同优先级之间：完全遵循抢占式原则。高优先级任务就绪，立即抢占低优先级任务。
相同优先级之间：采用时间片轮转（Round-Robin） 策略。多个同优先级的任务会平分CPU时间，轮流执行。

优先级配置：开发者通过FreeRTOSConfig.h文件中的configMAX_PRIORITIES宏定义优先级数量，数值越大，优先级越高。