RTOS开发学习记录(3)：任务调度

前言

上一篇文章记录了任务切换的实现。任务切换解决的是“如何从一个任务切到另一个任务”的问题，而任务调度解决的是“应该切到哪一个任务”的问题。

这篇文章记录一下 Yuan RTOS 中任务调度的实现。

完整代码请访问我的Github仓库，网址为：yuan-rtos。

值得注意是本文的示例代码在你阅读时可能已经进行过修改了，具体实现以仓库中代码为主。

调度器要解决什么问题

RTOS 中往往同时存在多个任务，但单核处理器同一时刻只能执行一个任务。因此调度器至少要解决下面几个问题：

• 哪些任务当前可以运行
• 多个任务都可以运行时，应该选择谁
• 当前任务不再适合继续运行时，如何切换到下一个任务
• 同优先级任务之间是否需要轮流执行

在 Yuan RTOS 中，任务有多个状态，例如 INIT、READY、RUNNING、BLOCKED、SUSPENDED、TERMINATED 等。调度器真正关心的是处于就绪队列中的任务，也就是可以被 CPU 执行的任务。

优先级调度

Yuan RTOS 采用基于优先级的调度方式，任务优先级范围如下：

/* 优先级范围 [0, YR_TASK_MAX_PRIORITY) */
#define YR_TASK_MAX_PRIORITY (32)

这里采用类似中断优先级的习惯：数值越小，优先级越高。因此优先级 0 最高，优先级 31 最低。

最直接的做法是每次调度时遍历所有任务，找到优先级最高的就绪任务。不过这种方式会随着任务数量增加而变慢。对于 RTOS 来说，调度路径一般希望尽可能短，因此 Yuan RTOS 使用了“优先级位图 + 每优先级链表”的方式。

核心变量如下：

yr_task_t* yr_current_task;
yr_uint32_t yr_thread_ready_priority_group;
yr_list_head_t yr_task_priority_table[YR_TASK_MAX_PRIORITY];

其中：

• yr_current_task：当前正在运行的任务
• yr_thread_ready_priority_group：就绪优先级位图
• yr_task_priority_table：每个优先级对应一个双向循环链表

也就是说，每一个优先级都有一个自己的就绪队列。如果某个优先级下存在就绪任务，那么位图中对应的 bit 就会被置 1。

就绪队列与位图

任务进入就绪态时，会被插入到对应优先级的链表中：

yr_err_t yr_sched_insert_task( yr_task_t* task)
{
    yr_list_insert_before( &yr_task_priority_table[task->current_priority],
                           &task->list_node);

    yr_thread_ready_priority_group |= task->priority_mask;

    return YR_OK;
}

其中 task->priority_mask 永远等于：

1 << task->current_priority

任务移出就绪队列时，则需要把链表节点删除。如果这个优先级的链表已经空了，还需要清除位图中对应的 bit：

yr_err_t yr_sched_remove_task( yr_task_t* task)
{
    yr_list_delete_self( &task->list_node);

    if( yr_list_isempty(&yr_task_priority_table[task->current_priority]) ) {
        yr_thread_ready_priority_group &= ~(task->priority_mask);
    }

    return YR_OK;
}

这样调度器就不需要遍历所有任务，只需要在位图中找到最低位的 1，就能知道当前最高优先级的就绪队列在哪里。

找到最高优先级任务

调度器启动或切换时，会通过 yr_find_first_set() 找到位图中最低位的 1：

highest_ready_priority = yr_find_first_set(yr_thread_ready_priority_group);
highest_ready_priority -= 1;

这里需要减 1，是因为 __builtin_ffs() 返回的是从 1 开始的 bit 序号，如果输入为 0b1，返回值是 1，而优先级数组下标应该是 0。

为什么这里可以认为是 O(1)

前面一直说通过位图可以快速找到最高优先级任务，但这里需要再说清楚一点：O(1) 的关键并不是“用了位图”这四个字，而是能够在常数时间内找到位图中最低位的 1。

如果只是把就绪状态存在一个 yr_uint32_t 里，然后自己从 bit0 开始写一个循环挨个检查，那么最多要检查 32 次。由于当前优先级数量固定为 32，这在大 O 记号里也可以视为常数，但从实现思路上看，它仍然是“按优先级逐个扫描”。

Yuan RTOS 当前的 Cortex-M3 + GCC 移植层中，yr_find_first_set() 是这样实现的：

/* 利用编译器内建指令查找最低位的 1 */
int yr_find_first_set(int value)
{
    return __builtin_ffs(value);
}

__builtin_ffs() 是 GCC 提供的内建函数，用于查找一个整数中最低位的置位位置。这样调度器就不需要在 C 代码中手动循环检查每一个优先级，而是把这个操作交给编译器和目标平台去优化。

因此当前调度器选择下一个任务的关键路径大致是：

1. 通过 yr_find_first_set() 从就绪位图中找到最高就绪优先级
2. 用这个优先级作为下标访问 yr_task_priority_table
3. 从对应链表头部取出第一个任务

这几个步骤都不依赖系统中任务数量，因此可以认为调度器查找下一个任务的过程是 O(1) 的。

不过这里也要注意，yr_find_first_set() 属于移植层接口。换到其它编译器或其它 ISA 时，不一定还叫 __builtin_ffs()，可能需要改成对应平台的指令或编译器内建函数。比如有些架构可以通过 CLZ、CTZ、FFS 一类指令完成类似操作；如果目标平台没有这些能力，才需要退化成软件循环查找。

得到最高就绪优先级后，调度器取该链表的第一个任务作为下一个任务：

next_task = YR_LIST_ENTRY(
    yr_task_priority_table[highest_ready_priority].next,
    yr_task_t,
    list_node
);

由于位图查询是常数时间的，链表取头节点也是常数时间的，因此这个调度路径比较简单，也比较适合资源较小的 MCU。

启动第一个任务

调度器启动时，系统中还没有真正运行的任务。yr_sched_start() 会先找到最高优先级的就绪任务，然后把它设置为当前任务：

yr_current_task = next_task;
next_task->status = YR_TASK_STATUS_RUNNING;
next_task->remaining_ticks = next_task->init_ticks;

yr_task_first_switch_to( (yr_uint32_t)&next_task->sp);

最后通过前一篇文章介绍的 yr_task_first_switch_to() 进入第一个任务。

这里有一个细节：内核初始化时会创建一个 idle 任务，并将其优先级设置为最低。这样只要系统中没有其它就绪任务，调度器也总能找到一个任务运行，不会出现“无任务可调度”的情况。

普通任务切换

普通任务切换由 yr_sched_switch() 完成，其核心过程如下：

prev_task = yr_current_task;
next_task = YR_LIST_ENTRY(
    yr_task_priority_table[highest_ready_priority].next,
    yr_task_t,
    list_node
);

if( prev_task == next_task ) {
    return;
}

yr_current_task = next_task;

if( prev_task && prev_task->status == YR_TASK_STATUS_RUNNING )
    prev_task->status = YR_TASK_STATUS_READY;

next_task->status = YR_TASK_STATUS_RUNNING;
yr_task_switch( (yr_uint32_t)&prev_task->sp,
                (yr_uint32_t)&next_task->sp);

调度器只负责选择任务和更新任务状态，真正保存、恢复寄存器的工作仍然交给移植层中的 yr_task_switch()。这样通用调度逻辑和架构相关代码就分开了。

同优先级时间片轮转

仅有优先级调度会带来一个问题：如果同优先级下有多个任务，那么链表前面的任务可能一直运行。为了解决这个问题，Yuan RTOS 支持同优先级任务的时间片轮转。

每个任务中有两个和时间片相关的字段：

yr_uint32_t init_ticks;
yr_uint32_t remaining_ticks;

每次系统 tick 到来时，会递减当前任务的 remaining_ticks：

--current_task->remaining_ticks;
if( current_task->remaining_ticks == 0 ) {
    current_task->remaining_ticks = current_task->init_ticks;
    yr_sched_yield();
}

当时间片耗尽时，当前任务会主动让出 CPU。yr_sched_yield() 会把当前任务从同优先级链表的当前位置删除，再插入到链表末尾：

yr_list_delete_self( &prev_task->list_node );
yr_list_insert_before( priority_list, &prev_task->list_node);

这样同优先级的其它任务就有机会运行。

不过需要注意的是，时间片轮转只发生在同优先级任务之间。如果有更高优先级任务就绪，那么调度器仍然会优先选择更高优先级任务。

任务阻塞与重新调度

任务不一定一直处于就绪态。例如任务调用延时、等待信号量、等待队列消息时，都会进入阻塞状态。

以延时为例，yr_task_sleep_ticks() 会把当前任务从就绪队列移除，设置为阻塞状态，并启动一个与任务绑定的定时器：

yr_sched_remove_task( current_task);
current_task->status = YR_TASK_STATUS_BLOCKED;

yr_timer_set_ticks( &current_task->timer, ticks);
yr_timer_start( &current_task->timer);

yr_sched_switch();

任务被移出就绪队列后，就不会被调度器选中。随后调用 yr_sched_switch()，CPU 会切换到其它就绪任务。

当定时器超时或 IPC 条件满足时，任务会重新进入就绪队列。如果新就绪任务优先级高于当前任务，则会触发一次任务切换。

总结

Yuan RTOS 的任务调度实现可以概括为：

• 使用 32 个优先级，数值越小优先级越高
• 每个优先级维护一个双向循环链表
• 使用位图记录哪些优先级存在就绪任务
• 通过 yr_find_first_set() 快速找到最高优先级就绪队列
• 同优先级任务通过时间片轮转依次运行
• 阻塞、挂起、删除等操作本质上都是改变任务是否参与就绪队列

这样做的好处是实现比较直观，同时调度路径较短，适合轻量化 RTOS。缺点是优先级数量固定为 32，并且调度策略也比较简单，不过对于当前这个项目来说已经足够使用了。

---