RTOS原理与实现03：内核核心实现

type

status

password

date

slug

summary

资源冲突

延时队列与任务优先级

1. 临界区保护

1.1 问题引入

1.2 临界区保护原理

1.2.1 临界区概念

临界区本质上是一段代码，这段代码会对多个任务的共享资源进行访问。当有任务进入临界区时，其他任务必须等待直到该任务离开临界区，以确保对共享资源的访问不会冲突

💡

任务A访问共享资源的时候，其他任务不能访问共享资源

1.2.2 关中断保护临界区

对共享资源的访问存在于任务与任务之间 & 任务与中断ISR之间，因此只需要防止任务在访问共享资源时切换到其他任务或防止中断发生即可实现对临界区的保护。

💡

说明1：关闭中断后，中断无法响应，其中PendSV中断无法响应又会导致任务无法切换，所以进入临界区的任务在运行过程中不会被打断，效果如下图

1.2.3 嵌套关中断问题

💡

考虑到嵌套关中断的场景，如果只是简单的关闭 - 打开中断会导致临界区保护失败，因为内部的开中断操作会导致外部临界区失去保护。例如在函数调用的时候

💡

解决方案则是在进入临界区时先保存当前的中断使能配置，然后在退出临界区时恢复先前保存的中断使能配置

1.3 设计实现

1.3.1 tTaskEnterCritical函数

1.3.2 tTaskExitCritical函数

💡

说明1：对于任务 & 中断ISR之间的互斥，只能使用关中断的方式实现（当然，可以只关闭指定中断），但是长时间关中断会影响系统的实时性

说明2：如果是任务 & 任务之间互斥，而且任务对共享资源的访问时间可能较长时，仅关闭任务切换即可（这就是下节的调度锁）

2. 调度锁保护

2.1 设计目标

对于任务间共享资源的互斥，长时间关闭中断会影响系统实时性，因此可以只关闭调度功能确保任务在进入临界区后不被切换。

💡

task1Entry 、task2Entry函数中都引用了 tTaskDelay函数，而tTaskDelay用到了中断服务。所以在这种情况下，开关中断就变得不合时宜。只能使用调度锁保护

💡

补充：在Linux中关闭调度被称为关抢占（disable preempt）

2.2 调度锁保护原理

上锁时：禁止任务切换，无论何种情况（e.g. 即使时间片用完，仍运行原任务）

解锁时：允许任务切换

2.3 设计实现

2.3.1 调度锁计数器

💡

说明：调度锁本质上是一个计数器（而且是一个全局计数器），用于记录上锁次数，这主要是用于实现调度锁上锁的嵌套操作

2.3.2 tTaskSchedDisable函数

💡

说明1：由于调度锁计数器本身是全局变量，所以需要通过关中断的方式进行保护，可见关中断在实现互斥机制中的基础地位

说明2：由于此处设置调度锁计数器为uint8_t类型，所以对计数范围需要进行控制

2.3.3 tTaskSchedEnable函数

💡

说明：当调度锁计数器减到0时，说明已经允许任务切换，所以调用tTaskSched进行一次任务切换

2.3.4 禁止任务调度

💡

说明：调度锁禁止任务切换的功能实现就是依靠tTaskSched函数中判断调度锁计数器是否有计数，如果有计数则不进行任务切换

2.3.5 禁止调度的影响

说明：vTaskDelay接口中会设置当前任务的delay tick数，然后调用tTaskSched函数进行一次任务切换。但是由于调度锁已经上锁，所以此时不会切换到其他任务，此次设置的delay tick需要下次调度时才会执行

总的说来，在调度锁上锁期间，所有可能导致任务切换的操作均不会实际导致任务切换

3. 位图数据结构

3.1 位图定义

3.1.1 位图概述

位图是一组连续的标志位，每一位用于标识某种状态的有无

3.1.2 操作接口

初始化：将所有的位清零

设置指定位：将指定的位置1

清除指定位：将指定的位清零

查找：第0位开始，寻找第1个被置位的位置

方法一：移位测试，遍历每一位

方法二：分组查表

💡

说明：分组查表所借助的quickFindTable就是预先计算出0 ~ 255（每8 bit为一组）这256个数第1个被置位的位置，这是一种以空间换时间的处理方法

注意：对于数字零，此处将对应的值设置为0xFF，经过上机验证，设置为8更为合理，本质上是返回一个合理的无效位置

3.2 位图实现

3.2.1 位图结构定义

3.2.2 位图初始化

3.2.3 设置指定位

3.2.4 清除指定位

3.2.5 寻找第1个置位的位置

💡

说明：如果位图每个分组均为0，则返回位图支持的最大位置数量（此处为32），这是一个合理的无效位置

4. 多任务优先级

4.1 问题引入

任务数量无限，而资源有限。当多个任务在等待同一资源 / 事件时（e.g. 多个任务等待CPU资源），如果资源 / 事件不能在任务间共享，应该由哪个任务来使用。

💡

RTOS的解决方案是引入优先级的概念，即根据实际应用特点，为任务指定优先级。优先级更高的任务具备对CPU、事件和资源的优先使用权和处理权

4.2 优先级原理

RTOS通过任务就绪表根据任务优先级维护当前所有可运行的任务，调度函数可从中选择优先级最高的任务运行。为了加快查找速度，此处引入就绪位图。就绪位图的位数就是任务优先级个数，而就绪位图的每一位对应了一个优先级，如果就绪位图的某一位被置一，则说明对应的优先级有任务可供运行

注意：在此处的设计中，每个优先级下只有一个任务。后续会将就绪表的表项由任务指针改为任务链表，进而实现每个优先级下有多个任务

4.3 设计实现

4.3.1 添加优先级字段

在任务结构中添加优先级字段

4.3.2 添加优先级位图与任务就绪表

调度初始化中初始化就绪位图

在增设优先级之后，在任务初始化函数中需要设置相关内容

此处同时设置任务就绪表和任务就绪位图，后续就是通过任务就绪位图来查找优先级最高的任务，具体实现函数如下

💡

注意：此处没有针对就绪位图为空的处理，因为系统中最少有一个空闲任务

4.3.3 修改调度函数

4.3.4 修改延时函数

4.3.5 修改SysTick Handler

💡

说明：该函数目前仍有瑕疵，目前是遍历任务数组的所有元素，但是实际上该数组中并非每个元素都对应有效的任务，后续会通过引入任务延时队列解决该问题

补充：到此处的实现方案其实是有问题的，因为并不是所有优先级都有有效的任务。所以对无效任务的遍历，以及将所有delayTick字段为0的位置均设置位图，是错误的做法

5. 双向链表数据结构

5.1 链表结构定义

5.1.1 通常结点定义

通常链表的结点定义是根据不同的结点类型定义不同的指针域类型，结果会导致虽然对链表处理的原理与流程相同，但是因为结点类型不同需要使用不同的链表操作代码

5.1.2 通用结点定义

通用结点类型中只包含通用类型的指针域，在使用中将通用结点类型嵌入具体的父结构中即可，这样就可以用相同的代码操作父结构不同的链表，提高了链表代码的通用性

说明：通用结点的实现方式也使得链表中可以链接父结构不同的结点，当然，这种操作并不常见

5.1.3 通用结点的转换问题

已知父结构，访问通用结点。使用结构体成员运算符即可

已知通用结点，访问父结构：将通用结点地址减去通用地址在父结构中的偏移量，即可计算出父结构地址（与Linux内核链表实现一致）

5.2 链表操作实现

5.2.1 结点初始化

结点的初始化就是将结点前驱 & 后继指针均指向自己

5.2.2 链表初始化

链表的初始化就是初始化链表头结点并将链表中结点个数置位0

5.2.3 移除链表中所有结点

遍历链表，将所有结点移除，然后将链表结构与结点结构置为初始化状态

注意：此处只是将结点从链表中逐个移除，并未涉及内存释放操作

5.2.4 在指定结点之后插入结点

5.2.5 将指定结点插入链表表头

在链表表头插入结点，是在指定结点之后插入结点的特例，此处指定的结点就是头结点

5.2.6 将指定结点插入链表表尾

在链表表头插入结点，是在指定结点之后插入结点的特例，但是这里需要先处理前驱结点的指针域，因为此时若先修改了头结点相关指针域，前驱结点可能会丢失，而头结点的位置是不会丢失的

注：实际实现中的思路是在头结点之前插入指定结点

5.2.7 移除指定结点

移除结点需要调整2个指针域：1、前驱结点的next指针；2、后继结点的prev指针

5.2.8 移除头部结点

移除头部结点是移除指定结点的特例，此处list->head.node->next就是指定要移除的结点

注意：此处也只是移除结点，并未涉及内存释放操作

6. 任务延时队列

6.1 问题引入

在原先的SysTick_Handler中会遍历整个就绪表来判断是否有任务需要延时，并对延时计数值进行维护。但是存在如下2个问题：

就绪表中的某个单元是否有效由就绪位图决定，所以在遍历的过程中也会访问无需延时的任务以及就绪表中的无效单元，因此比较耗时（对无效单元的操作是一种错误！尤其是在delayTicks字段为0时设置对应位图的操作，可能会"无中生有"出一个无效的任务）

如果系统中支持多个任务使用相同优先级，遍历的代价将进一步增大

6.2 延时队列设计

💡

专门创建一个延时队列

原理：将所有需要延时的任务单独放置在一个队列中，每次发生系统时钟节拍时，只需扫描该队列，而无需遍历整个就绪列表。延时队列的组织方式有如下2种：

6.2.1 独立保存延时时间

💡

原理：延时队列中的每个任务单独保存自己的完整延时时间，在SysTick_Handler中扫描任务延时队列，并修改延时时间，如果有延时完成的任务则将其移出任务延时队列重新加入就绪表

优点：插入延时队列操作简单（e.g. 直接将需要延时的任务插入延时队列队首或队尾即可）

缺点：SysTick_Handler中需要扫描整个任务延时队列，如果延时的任务较多，扫描延时队列耗时较大

6.2.2 递增保存延时时间（任务实现中没有使用这种方式）

💡

原理：任务中的延时计数值递增保存，任务延时时间 = 之前所有任务延时计数值 + 本任务延时计数值

缺点：插入延时队列操作复杂，需要遍历延时队列，计算当前任务延时计数值及插入位置，伪代码如下，

说明：在判断p->delay_tick与insert_task->delay_tick的关系时，使用 "<="是非常关键的，他可以确保当待插入任务的总延时值与p指向的当前任务总延时值相同时，待插入任务的delay_tick字段可以被正确设置为0，并插入正确位置

优点：无需遍历整个延时队列，只需处理到延时计数值非零即可，伪代码如下，

说明：由于将任务插入延时队列时对延时计数值进行了处理，此处只要递减表头任务的延时计数值，如果表头任务延时完成，则唤醒当前所有延时计数值为0的任务

这里的处理方法是和插入延时队列的算法匹配的，如果有总延时值相同的任务，后续任务在插入时，delay_tick字段会被设置为0

注意：当前版本使用独立保存延时时间的实现方式

6.3 设计实现

6.3.1 添加延时队列

延时队列使用上节介绍的双向循环链表实现，在定义延时等待队列的同时提供初始化函数

为了配合延时队列的使用，任务结构体也要添加相应的字段并在初始化任务时进行设置

6.3.2 插入延时队列

插入延时队列涉及2个函数，分别对应2个步骤，

将任务移除就绪表

将任务加入等待队列

6.3.3 移除延时队列

移除延时队列也涉及对应的2个函数，分别对应2个步骤，

将任务移除等待队列

将任务加入就绪表

6.3.4 修改延时函数

6.3.5 修改SysTick_Handler

7. 同优先级时间片运行

7.1 设计目标

构建一个允许多任务具备相同优先级，且同优先级任务之间按时间片占用CPU运行的系统。

💡

RTOS的任务调度规则就是运行当前就绪表中优先级最高的任务，如果优先级相同再按时间片运行。在上图示例中，在优先级为0的task1释放CPU的情况下，task2 & task3根据设置的时间片轮流占用CPU

7.2 同优先级时间片运行原理

7.2.1 同优先级单任务设计（不允许相同优先级的情况）

就绪表的每个单元为一个任务类型指针（struct tTask *）指向一个任务，所以每个优先级只允许一个任务

7.2.2 同优先级多任务设计

就绪表中每个单元为一个链表（tList），用于组织同优先级的任务。

说明1：在实现同优先级任务时间片轮转时，每当调度到一个优先级就运行该优先级链表中的表头任务（e.g. 任务00），当时间片耗尽时，将该任务从链表表头移至表尾。这样当再次调度到该优先级时便可运行下一个任务（e.g. 任务01）

说明2：对于只有一个任务的优先级也按照上述算法执行，只是每次运行的都是同一个任务而已

7.3 设计实现

7.3.1 修改就绪表

将就绪表的成员修改为链表

为配合就绪表的修改，还需要修改如下内容，

增加对就绪表的初始化：我们增设tTaskSchedInit函数，用于初始化任务调度相关组件

任务结构新增链表结点与时间片字段

任务结构新增字段后，需要在任务初始化函数中初始化相关字段

7.3.2 修改tTaskHighestReady函数

由于现在支持同优先级多任务，所以在实现中是获取最高优先级列表的表头任务

7.3.3 修改任务就绪与移除函数

💡

说明：在将任务从就绪表移除时，只有当该优先级已经没有任务时，才将对应的优先级位图置为0

7.3.4 修改SysTick_Handler

💡

说明1：同优先级多任务的时间片耗尽后，仍然是在就绪列表中

说明2：操作系统计时的不精确性

在目前实现的SysTick_Handler中会将当前任务的时间片计数值减1，但是实际上当前任务并不一定真的运行了一个SysTick的时间

比如当前任务是在一个SysTick中途才被切换到执行的，此时这个SysTick的运行时间就计算该该任务上

7.3.5 任务设置

说明1：在Task1调用tTaskDelay释放CPU时，RTOS会调度优先级为1的任务运行，此时Task1释放的CPU时间就会以时间片的形式轮流被Task 2和Task 3占用

说明2：Task 2和Task 3使用忙等接口delay是为了体现实验效果，即时间片耗尽后被调度，而不是主动释放CPU