FreeRTOS任务之调度器中的三种调度算法

​本文主要讲解FreeRTOS调度器中的三种调度算法：基于时间片的抢占式调度、不带时间片的抢占式调度和协同调度。

前导文章：FreeRTOS全解析-3.任务（task）

参考资料：《Mastering the FreeRTOS™ Real Time Kernel》3.12 Scheduling Algorithms

1.任务状态和事件的概述

实际正在运行(使用处理时间)的任务处于运行态。在单个核心处理器上，在任何时候都只能有一个任务处于运行态。

没有实际运行，但既不处于阻塞态也不处于挂起态的任务就是处于就绪态。

处于就绪态的任务可被调度器选择，然后进入运行态。调度程序会始终选择最高优先级的就绪态任务进入运行态。

任务可以在阻塞态下等待事件，并在事件发生时自动移回就绪态。

时间事件发生在特定的时间，例如当阻塞时间过期时，通常用于实现周期性或超时行为。当任务或中断服务例程使用任务通知、队列、事件组或多种类型的信号量之一发送信息时，就会发生同步事件。它们通常用于需要同步的情况，例如数据同步。

2.配置调度算法

调度算法决定了调度器将哪个就绪态任务转换到运行态。

可以使用configUSE_PREEMPTION和configUSE_TIME_SLICING配置常量来更改算法。这两个常量都在FreeRTOSConfig.h中定义。

还有个配置常数configUSE_TICKLESS_IDLE也会影响调度算法，因为使用它会导致tick中断在很长一段时间内被完全关闭。configUSE_TICKLESS_IDLE是一个高级选项，专门用于必须最小化功耗的应用程序。configUSE_TICKLESS_IDLE在之后解说。

对于相同优先级的任务，FreeRTOS调度器依次选中相同优先级的任务进入运行态。这种轮流策略被称为‘Round Robin Scheduling’

‘Round Robin Scheduling’算法并不能保证同等优先级的任务之间运行相同的时间，只能保证同等优先级的“就绪”任务会依次进入“运行”态。

2.1基于时间片的抢占式调度

如果按照如下配置：

configUSE_PREEMPTION 1configUSE_TIME_SLICING 1

FreeRTOS调度器使用一种称为“基于时间片的固定优先级抢占式调度”的调度算法，这是大多数小型RTOS应用程序使用的调度算法。

固定优先级

被描述为“固定优先级”的调度算法不会改变分配给被调度任务的优先级，但也不会阻止任务本身改变自己的优先级或其他任务的优先级。

抢占式调度

在优先级高于运行态任务的任务进入就绪态时，调度器立即让这个高优先级的任务“抢占”运行态任务。被抢占意味着任务移出运行态并进入就绪态，并不是因为任务自己主动让出或者阻塞。

时间片

时间片用于在具有相同优先级的任务之间共享处理时间，即使任务没有显式地让步或进入阻塞状态。使用“时间片”的调度算法将在每个时间片结束时选择一个新任务进入运行状态，如果有其他与运行任务具有相同优先级的就绪状态任务。一个时间片等于两个RTOS tick中断之间的时间。

上图演示了使用“基于时间片的固定优先级抢占式调度”算法抢占调度任务的调度过程。

task1是最高优先级的事件驱动任务，task2是中等优先级的周期性任务，task3是最低优先级的事件驱动任务，Idle task是空闲任务。

task1周期性运行，阻塞时，空闲任务就会运行，task3的事件到达就会抢占空闲任务，task3运行期间，如果task2的周期到了，因为task2优先级高就会抢占task3，task2运行完了再接着运行task2，task2运行期间，由于task1优先级高，一旦task1等待的事件到了就会抢占task2。

有相同优先级任务的情况：

task1是优先级最高的事件驱动任务，task2是和Idle task优先级相同的持续处理型任务。

task2和空闲任务就会轮流运行，而task1则可以抢占task2和空闲任务。

假如空闲任务里其实没做什么事情，我们想让和空闲任务相同优先级的Task2有更多的运行时间就可以配置configIDLE_SHOULD_YIELD

如果configIDLE_SHOULD_YIELD设置为0，那么空闲任务将在整个时间片中保持运行状态，除非它被更高优先级的任务抢占。

如果configIDLE_SHOULD_YIELD设置为1，如果有其他空闲优先级任务处于就绪状态，那么空闲任务将主动让出运行时间。

2.2不带时间片的抢占式调度

配置如下时，调度算法就会变成不带时间片的抢占式调度

configUSE_PREEMPTION 1configUSE_TIME_SLICING 0

和前面的唯一区别就是相同优先级的任务之间不会随时间自动切换。

如果不使用时间片，那么调度程序只会在发生这两种情况时，进行任务切换:

1.优先级更高的任务进入“就绪”态。

2.运行态任务变为阻塞态或被挂起。

很显然，不使用时间片时，任务切换的情况会变少，所以关闭时间切片可以减少调度器的处理开销。但是关闭时间切片也可能导致具有相同优先级的任务获得的处理时间相差很大。因此，一定要慎重使用。

task1为最高优先级的事件驱动任务，task2和Idle task有相同的优先级。但是由于关闭了时间片，任务切换只会在空闲任务阻塞或者挂起或者task1抢占后发生，所以空闲任务和task2虽然优先级相同，但是明显空闲任务占有的时间长很多。

2.3协同调度

configUSE_PREEMPTION 0configUSE_TIME_SLICING 随便

当使用协同调度时，只有当运行态任务进入阻塞态，或者运行态任务通过调用taskYIELD()主动让出，才会发生任务切换。

任务永远不会被抢占，不能使用时间片，时间片配置的值随便，无所谓。

task1、2、3优先级依次变低，刚开始task3运行，虽然task1和2优先级高，并且没有阻塞，但是也无法抢占，task3调用taskYIELD()，主动让出，因为task1优先级比task2高，task1就运行了，task1运行够了进入阻塞态，由于task2比task3优先级高，task2就运行了。

2.4优缺点

多任务访问问题

在多任务程序中，应用程序编写人员必须注意一个资源不能被多个任务同时访问，因为同时访问可能会破坏资源。例如，考虑以下场景，其中正在访问的资源是UART(串口)。两个任务是向UART写入字符串;任务1写“abcdefghijklmnop”，任务2写“123456789”:

1.Task 1处于运行态，开始写它的字符串。它将“abcdefg”写入UART，然后离开运行态。

2. Task 2进入运行态，并在离开运行态之前向UART写入“123456789”。

3.任务1重新进入运行态，并将其字符串的剩余字符写入UART。

在该场景中，实际写入UART的内容是“abcdefg123456789hijklmnop”。Task 1写入的字符串没有按照预期的连续顺序写入UART，而是被损坏了，因为Task 2写入UART的字符串出现在UART中。

通常，使用协同调度比使用抢占调度更容易避免同时访问引起的问题

当使用抢占式调度时，运行状态任务可以在任何时候被抢占，包括当它与另一个任务共享的资源处于不一致状态时。正如刚才UART示例所演示的，让资源处于不一致的状态可能导致数据损坏。

当使用协同调度时，应用程序编写人员控制何时可以切换到另一个任务（干完想干的再阻塞，或者让出）。因此，应用程序编写人员可以确保在资源处于不一致状态时不会发生切换到另一个任务的情况。在上面的UART示例中，应用程序编写人员可以确保Task 1在将其整个字符串写入UART之前不会离开运行态，这样做可以消除字符串被另一个任务的激活破坏的可能性。

很明显，协同调度比抢占调度响应要慢。

当使用协同调度时，最高优先级任务进入就绪态时并不一定会立即执行，必须等到运行态任务进入阻塞态或调用taskYIELD()才会被执行。

使用抢占调度时，当一个比运行态任务优先级更高的任务进入就绪态时，这个任务会立即执行。这一点对于必须在一定时间内响应高优先级任务的实时系统是非常重要的。至于多任务访问问题(其实也就是操作系统中的多线程问题)，有其他手段去解决。