RTOS内功修炼记（二）—— 优先级抢占式调度到底是怎么回事？
RTOS内功修炼记（二）—— 优先级抢占式调度到底是怎么回事？
内容导读：
本文从任务如何切换开始讲起，引出RTOS内核中的就绪列表、优先级表，一层一层为你揭开RTOS内核优先级抢占式调度方法的神秘面纱，只有对内核的深入了解，才能创造出更好的应用。
1.知识点回顾
1.1. 上文回顾
上篇文章讲述了任务的三大元素：任务控制块、任务栈、任务入口函数，并讲述了编写RTOS任务入口函数时三个重要的注意点。
如果你还没有阅读上一篇文章，请先阅读，这有助于对本文的理解：
- RTOS内功修炼记（一）—— 任务到底应该怎么写？
1.2. 双向循环链表
双向链表是链表的一种，区别在于每个节点除了后继指针外，还有一个前驱指针，双向链表的节点长下面这样：
如果你对双向循环列表的实现及使用还不熟悉，请一定要先阅读这篇文章：
2. 任务是如何切换的
在RTOS内核中，一个任务切换到下一个任务的原理是：
「手动触发PendSV异常，在PendSV异常服务函数中实现任务切换」。
2.1. 如何触发PendSV异常
stm32中，将中断及状态控制寄存器ICSR（Interrupt control and state register）的第28位置1，即可手动触发 PendSV 异常，如图：
tos中触发异常的底层函数为port_context_switch，实现在 arch\arm\arm-v7m\cortex-m4\armcc\port_s.S 中，如下：
GLOBAL port_context_switch
port_context_switch
LDR R0, =NVIC_INT_CTRL
LDR R1, =NVIC_PENDSVSET
STR R1, [R0]
BX LR
上面这段汇编猛一看有点难，再看看两个值具体是多少：
NVIC_INT_CTRL EQU 0xE000ED04
NVIC_PENDSVSET EQU 0x10000000
所以上面这段汇编代码，不正是完成了将寄存器 ICSR（代码中是NVIC_INT_CTRL） 的第28位置1的操作吗？
2.2. 异常服务中实现任务切换
在 stm32 中 PendSV 的异常服务函数名为 PendSV_Handler，默认在stm32l4xx_it.c中提供了一个弱定义，所以tos中的实现直接重定义此函数即可，源码在 arch\arm\arm-v7m\cortex-m4\armcc\port_s.S中，主要步骤有四个：
① 「关闭全局中断」（NMI 和 HardFault 除外），防止任务切换过程被中断：
CPSID I
② 「保存上文环境」：保存当前CPU寄存器组的值、PSP栈顶指针的值到任务栈中；
③ 「加载下文环境」：加载当前任务栈中的值到CPU寄存器组、PSP栈顶指针中；
④ 「打开全局中断」，实时响应系统所有中断：
CPSIE I
记住任务切换的这四个过程即可，深入研究每行汇编指令是什么意思，没有太大的作用和帮助。
2.3. CPU何时响应PendSV异常
我们都知道，「高优先级的中断会打断低优先级的中断」，这也是系统实时性的一个重要保障，所以就引入了一个问题：
相比起GPIO中断、定时器中断、串口中断这些外部中断，PendSV异常的优先级更高呢？还是更低呢？
想象这样一种情况：
① CPU正在开心的运行着任务1……
② 此时你按下了按键，产生了一个GPIO中断，CPU收到后马上跑去执行中断处理函数……
③ 处理过程中，此时系统产生了一个PendSV异常，CPU收到后，嘲讽了一句：“我就是从普通任务跑来处理中断的，还没处理完，现在又让我执行下一个普通任务，脑子抽风了？”，说完继续处理中断……
所以说，无论任务的优先级有多高，它都没有中断高，「系统的PendSV异常优先级必须设为最低的」，以避免在外部中断服务函数中产生任务切换。
设置PendSV异常优先级的寄存器如下，值可以为0-255：
tos中在启动调度时设定pendsv异常的优先级，源码如下：
NVIC_SYSPRI14 EQU 0xE000ED22
NVIC_PENDSV_PRI EQU 0xFF
同样，设置pendSV异常优先级为最低的汇编代码如下：
; set pendsv priority lowest
; otherwise trigger pendsv in port_irq_context_switch will cause a context switch in irq
; that would be a disaster
MOV32 R0, NVIC_SYSPRI14
MOV32 R1, NVIC_PENDSV_PRI
STRB R1, [R0]
3. 就绪列表
3.1. 就绪列表长啥样
就绪列表其实就是好多条双向链表+一张优先级表，它的类型定义在tos_sched.h，如下：
typedef struct readyqueue_st
{
k_list_t task_list_head[TOS_CFG_TASK_PRIO_MAX];
uint32_t prio_mask[K_PRIO_TBL_SIZE];
k_prio_t highest_prio;
} readyqueue_t;
①「给每个优先级都分配了一个双向链表的首节点，用于挂载该优先级的任务」。
TOS_CFG_TASK_PRIO_MAX 是最大任务优先级，在tos_config.h中配置，默认是10：
#define TOS_CFG_TASK_PRIO_MAX 10u
节点类型 k_list_t 是一个双向链表节点类型：
typedef struct k_list_node_st
{
struct k_list_node_st *next;
struct k_list_node_st *prev;
} k_list_t;
所有双向链表节点初始化完毕之后，每一个双向结点的next指针指向自己（橙色线），prev指针也指向自己，如图：
② 「用于指示系统目前所使用优先级的优先级表」。
优先级表的大小由宏定义 K_PRIO_TBL_SIZE 决定：
#define K_PRIO_TBL_SIZE ((TOS_CFG_TASK_PRIO_MAX + 31) / 32)
这儿定义的时候比较讲究，如果最大优先级不大于32，则该宏的值为1，使用一个uint32_t类型的变量即可，每个优先级的表示占一位。
初始化后的优先级表长下面这个样子：
③ 「最高优先级指示成员」。
就绪列表中的 highest_prio 成员是 k_prio_t 类型，其实就是一个uint8_t类型：
typedef uint8_t k_prio_t;
该成员表示系统中当前所存在任务的最高优先级，默认是系统定义的最大优先级。
3.2. 系统中的就绪列表
系统中有多少条就绪列表呢？
对了，答案当然是：「仅有唯一的一条就绪列表」。
在tos_global.h中声明，便于在整个内核的所有文件中使用：
/* ready queue of tasks */
extern readyqueue_t k_rdyq;
在tos_global.c中定义：
readyqueue_t k_rdyq;
「记住它的名字，它叫k_rdyq」，k就是kernel，rdyq就是ready queue的缩写，后面会经常出现。
3.3. 初始化就绪列表
知道了就绪列表长啥样，就绪列表的初始化就变得非常简单了，都是常规操作，在tos_sched.c文件中实现：
__KNL__ void readyqueue_init(void)
{
uint8_t i;
k_rdyq.highest_prio = TOS_CFG_TASK_PRIO_MAX;
for (i = 0; i < TOS_CFG_TASK_PRIO_MAX; ++i) {
tos_list_init(&k_rdyq.task_list_head[i]);
}
for (i = 0; i < K_PRIO_TBL_SIZE; ++i) {
k_rdyq.prio_mask[i] = 0;
}
}
第①步是设置最高优先级成员的初始值，为系统当前配置的最高优先级；
第②步是遍历初始化每个双向链表节点；
第③步就是初始化优先级表的所有值，为0。
4. 任务如何挂载到就绪列表
在任务创建API的最后，会调用 readyqueue_add_tail 函数将任务加入到就绪列表中，那么，任务究竟是被如何挂载上去的呢？
此函数的源码实现如下：
__KNL__ void readyqueue_add_tail(k_task_t *task)
{
k_prio_t task_prio;
k_list_t *task_list;
task_prio = task->prio;
task_list = &k_rdyq.task_list_head[task_prio];
if (tos_list_empty(task_list)) {
readyqueue_prio_mark(task_prio);
}
tos_list_add_tail(&task->pend_list, task_list);
}
① 「获取该任务的优先级在就绪列表中所对应的首节点」。
② 「在优先级表中记录此优先级」。
判断系统中该优先级是否第一次出现，如果是，则将优先级表中此优先级的标志位置1，表示系统中存在此优先级的任务，并重新赋值就绪列表中的最高优先级指示成员（注：优先级值越小，表示优先级越高）：
__STATIC_INLINE__ void readyqueue_prio_insert(k_prio_t prio)
{
k_rdyq.prio_mask[K_PRIO_NDX(prio)] |= K_PRIO_BIT(prio);
}
__STATIC_INLINE__ void readyqueue_prio_mark(k_prio_t prio)
{
readyqueue_prio_insert(prio);
if (prio < k_rdyq.highest_prio) {
k_rdyq.highest_prio = prio;
}
}
举个例子，当我们创建了一个优先级为2的任务后，则优先级表如下：
③ 「将该任务的任务控制块的pendlist节点，挂载到第一步获取到的首节点所指示的链表尾部」。
任务控制块中的pend_list成员也是一个双向链表节点：
/**
* task control block
*/
struct k_task_st {
//……
k_list_t pend_list; /**< when we are ready, our pend_list is in readyqueue; when pend, in a certain pend object's list. */
//……
};
使用双向链表将此pendlist节点添加到第①步获取到的链表尾部，添加之后如图：
5. 优先级抢占式调度
5.1. 调度规则
理解了上面的三节内容，再来看优先级抢占式调度，简直就是水到渠成。
同样，先放上优先级抢占式调度的源码，在tos_syc.c中：
__KNL__ void knl_sched(void)
{
TOS_CPU_CPSR_ALLOC();
if (unlikely(!tos_knl_is_running())) {
return;
}
if (knl_is_inirq()) {
return;
}
if (knl_is_sched_locked()) {
return;
}
TOS_CPU_INT_DISABLE();
k_next_task = readyqueue_highest_ready_task_get();
if (knl_is_self(k_next_task)) {
TOS_CPU_INT_ENABLE();
return;
}
cpu_context_switch();
TOS_CPU_INT_ENABLE();
}
在源码中可以看到，优先级抢占式调度其实就是两个步骤：
① 获取就绪列表中的最高优先级的任务控制块指针；
② 启动上下文切换；
总结一下，优先级抢占式调度的规则就是：
「每当符合调度条件时时，就切换到就绪列表中优先级最高的任务开始运行」。
5.2. 如何获取最高优先级的任务
别忘了就绪列表中有一个成员叫highest_prio，该成员指示出了系统当前存在的最高优先级，可以很方便的获取到挂载最高优先级的任务链表，函数源码如下：
__KNL__ k_task_t *readyqueue_highest_ready_task_get(void)
{
k_list_t *task_list;
task_list = &k_rdyq.task_list_head[k_rdyq.highest_prio];
return TOS_LIST_FIRST_ENTRY(task_list, k_task_t, pend_list);
}
但是需要注意，在就绪列表上挂载的是任务控制块中的pend_list节点，如图：
已知任务控制块中pend_list节点地址，如何知道它所在任务控制块的基地址呢？
其实它是通过 TOS_LIST_FIRST_ENTRY 这个宏来获取的，具体的使用方法，请阅读我在文章开头提出的第二篇文章。
6. 优先级表有什么用？
优先级表的作用是：
「在将任务从就绪列表中移出时，用来获取当前就绪列表中的最高优先级」。
优先级抢占式调度器可是六亲不认的，才不管任务当前状态是什么，反正就是永远寻找调度列表中最高优先级的任务。
所以当任务调用要主动挂起时，必须要从就绪列表中移出，源码如下：
__API__ k_err_t tos_task_suspend(k_task_t *task)
{
TOS_CPU_CPSR_ALLOC();
//一堆参数判断，省略了
TOS_CPU_INT_DISABLE();
if (task_state_is_ready(task))
{
// kill the good kid
readyqueue_remove(task);
}
task_state_set_suspended(task);
TOS_CPU_INT_ENABLE();
knl_sched();
return K_ERR_NONE;
}
其中核心的就绪列表移出函数 readyqueue_remove 源码如下：
__KNL__ void readyqueue_remove(k_task_t *task)
{
k_prio_t task_prio;
k_list_t *task_list;
task_prio = task->prio;
task_list = &k_rdyq.task_list_head[task_prio];
tos_list_del(&task->pend_list);
if (tos_list_empty(task_list)) {
readyqueue_prio_remove(task_prio);
}
if (task_prio == k_rdyq.highest_prio) {
k_rdyq.highest_prio = readyqueue_prio_highest_get();
}
}
① 获取任务当前优先级在就绪列表中的首节点；
② 将该任务控制块与该条双向链表断开（并没有删除任务）；
③ 如果断开后该链表变空，则表示就绪列表中不存在该优先级的任务，在优先级表中将该位清零；
④ 「重新获取就绪列表中的最高优先级」。
这个时候优先级表的作用就体现出来了，之前讲到，优先级表中记录了当前就绪列表中所存在任务的优先级，所以可以通过遍历查找优先级表，来获取到最高优先级，最后赋值给就绪列表中的指示成员。
源码如下：
__STATIC__ k_prio_t readyqueue_prio_highest_get(void)
{
uint32_t *tbl;
k_prio_t prio;
prio = 0;
tbl = &k_rdyq.prio_mask[0];
while (*tbl == 0) {
prio += K_PRIO_TBL_SLOT_SIZE;
++tbl;
}
prio += tos_cpu_clz(*tbl);
return prio;
}
7. 总结
讲述了这么多内容，非常有必要来总结出值得注意的点：
① 「RTOS内核中通过手动触发PendSV异常来启动一次切换，任务切换在PendSV异常服务函数中实现」。
② 「RTOS内核中PendSV异常的优先级被设为最低，避免在外部中断处理函数中产生任务切换」。
③ 「RTOS内核所谓的优先级抢占式调度规则就是永远从就绪队列中找出最高优先级的任务来运行」。
当然，有了优先级抢占式调度规则，才勉强撑起来了一个RTOS内核的肉体，什么时候进行调度，才是一个RTOS内核的灵魂，接下来的文章与大家再会。