0. 目录
1. 综述
2. 垫话
3. 调度的本质
3.1 开门见山
3.2 资源等待
3.2.1 软件资源等待
3.2.2 硬件资源等待
3.2.3 时间资源等待
3.2.4 归纳统一
3.3 资源唤醒
4. 极简风调度框架
4.1 运行队列
4.2 放弃 CPU 的实现
4.2.1 yield
4.2.2 pend
4.2.3 sleep
4.3 唤醒语义的实现
4.3.1 yield - ?
4.3.2 pend - ?
4.3.3 sleep - ?
5. 线程状态转移的本质
5.1 请拉黑
5.2 本质是什么
5.3 wakeup 语义：从本质层面的统一
6. 一点简单的魔法
6.1 魔法的施展
6.2 时间片魔法
6.3 优先级魔法
6.4 何谓抢占
7. 总结
1. 综述
本文是 linux 内核调度器学习系列文章的第一篇。
本文着力点在于解构“调度”一词的本质，试图回答清楚“调度”这一概念相关的元问题。
从我个人角度来说，本文是对 RTOS 调度器的一个回顾和总结。
从调度器 newbie 角度的来说，本文是一篇很好的导引。
2. 垫话
不同内核（RTOS、linux，etc.）调度器实现的复杂程度不同，譬如相较于一个单核、单地址空间、单特权级、单用户的 RTOS，linux 内核引入了 SMP、负载均衡、组调度、多级调度类、进程、cgroups 等等。但仅从调度这一概念本身来说，其背后包含的元问题并无本质不同。
简单起见，本文拆解“调度”一词时，会主要基于一个单核、单地址空间、单特权级、单用户的 RTOS 内核实现。
3. 调度的本质
3.1 开门见山
调度的本质到底是啥？
- 有人说是将 CPU 资源进行合理的分配
这在我看来属于魔法（算法）范畴，并不是其本质。魔法相关的后续会另外撰文，不在本文讨论范围内。
- 有人拿出了一张 TA 珍藏的线程状态转移图
遇到这类文章请直接拉黑。
调度的本质，在我看来就是四个字：按需分配。至于分配的合不合理，那是魔法范畴的事，不在本文讨论范围内。
所谓按需分配包含两个内涵：
- 任务在等待资源的时候让其从 CPU 上下去，不要白白占着 CPU 不拉 S。
可以归纳为“资源等待”。
- 在资源 ready 的时候，尽快让任务上到 CPU 上跑起来干活，不要让 CPU 白白空转。
可以归纳为“资源唤醒”。
那么引出两个问题：
- 啥是资源？
- 如何实现按需分配（等待的时候下去，ready 的时候上来）
3.2 资源等待
从物理视角，计算机的资源无非就是软件、硬件。
还有一个维度容易被忽视：时间也是一种资源。
下面就这三类资源如何进入等待、ready 状态进行讨论。
3.2.1 软件资源等待
软件资源的等待，最典型的就是代码临界区，而对代码临界区的等待，一般是通过各种锁来实现。
锁的实现包括：互斥锁（mutex）、自旋锁（spin\_lock）、读写锁（rwlock）等，不一而足。
软件资源还包括多个线程之间的协作关系，比如消费者需要等待生产者队列有产出才可以消费；生产者需要等消费者消费后，生产队列产生空闲 buffer 才可以继续生产。
实现这种协作关系的软件资源等待，可以通过信号量（semaphore）、事件（event，RTOS 里面用的比较多）等等，不一而足。
3.2.2 硬件资源等待
硬件资源的等待，最典型的就是等待设备 rx 来数据。
这种硬件资源等待，可以通过信号量（semaphore）、事件（event，RTOS 里面用的比较多）等等，不一而足。
3.2.3 时间资源等待
时间的等待有两类：
- 第一类是线程需要主动 sleep 一段时间之后再醒来继续干活。
- 第二类是一些锁的实现提供了带最长等待时间限制的接口。
比如 TencentOS tiny 中的 tos_mutex_pend_timed，此接口支持传入一个超时时间。当超时到期之前仍未等到这个信号量，就给资源等待者（pender）返回超时。
linux 内核中也有类似的接口，如 rt_mutex_timed_lock。
3.2.4 归纳统一
- 软件/硬件资源等待
这二者并无本质不同，资源等待者（下文简称 pender）都是等待（pend）在一个软件实现的通知机构上（对硬件资源的等待，最终也还是通过软件机制来实现的），这个通知机构可以是互斥锁，也可以是信号量等等。
- 时间资源等待
等待者等的是一个定时机构，在时间未到之前 pender 会一直等。
3.3 资源唤醒
3.2.4 中我们归纳总结了，系统中对资源的等待无非两种场景：
- 第一种是 pend 在一个通知机构上，这种等待我们定义为“一类等待”。
- 第二种是 pend 在一个定时机构上，这种等待我们定义为“二类等待”。
那么对于这两类等待的 pender，怎么唤醒它们也就呼之欲出了：
- 一类等待：在资源变为可用状态时，比如互斥锁被持有者释放，此时释放者（下文简称 poster）会通过通知机构的 post 接口，唤醒等在这个机构上的 pender。一个更为具体的例子，设备 rx 中断处理函数中，调用该设备的信号量 post 接口，唤醒等待该设备来数据的任务。
- 二类等待：内核实现一个定时框架，当时间到时，唤醒等在定时机构上的 pender。一个更为具体的例子，系统可以在周期时钟（tick）中断处理函数中，定时检查 sleep 的任务是否有时间到期的，有则唤醒之。
4. 极简风调度框架
本节设计一个极简的调度框架，旨在说明调度器是如何实践 3.1 节中所述“调度的本质就是按需分配资源”的哲学原理。
4.1 运行队列
假设有这么一个傻瓜调度函数，该调度函数的任务就是挨个遍历某个链表，从链表上取到的第一个任务，摘下来运行。一直运行到此任务放弃 CPU，则选择链表上的第二个任务运行，如此往复。
如你所知，这其实就是最简单的 FIFO 调度策略。
这个管理所有任务的链表，我们不妨称之为 runqueue（运行队列）：
FUNC schedule():
/* 摘取 runqueue 上的第一个 task，并运行之
*/
task = runqueue.first_task()
/* 切换到 task 上下文中运行
*/
context_switch_to(task)4.2 放弃 CPU 的实现
在 4.1 节中设计的调度函数中，每次选择一个 task 运行，直到此 task 放弃 CPU。
那么什么情况下 task 会放弃 CPU 呢？
有三种情况：
- task 主动放弃 CPU：比如调用 yield。
- task 进入“一类等待”：比如等待互斥锁（pend）
- task 进入“二类等待”：比如主动睡眠（sleep）
那么这三种情况下对 CPU 的放弃应该如何实现呢？
4.2.1 yield
所谓的 yield，就是主动放弃 CPU。
注意，这并不意味该 task 不需要 CPU 了，它与资源等待性质不同，可以把 yield 理解为是一种“高风亮德、顾全大局”的行为。
故而，主动发起 yield 的 task，在未来的某个时刻，当调度器再次选中它时，它仍然是可以理直气壮的拿到 CPU 直接就开始运行。
一个可行的 yield 实现如下：
/* 入参 self，为当前主动发起 yield 的任务
*/
FUNC yield(self):
/* 将 self 移动到 runqueue 的末尾
*/
runqueue.move_to_tail(self)
/* 触发 schedule，让调度器选择下一个 task 来运行
* 这里注意，如果 runqueue 中就只有 self 这一个任务
* 那么 schedule 函数中下一次选中的仍然是 self 任务，self 将继续运行
*/
schedule()4.2.2 pend
pend 是因为等待某个资源而放弃 CPU，它与 yield 有着本质区别。
因 pend 放弃 CPU 的任务，即使该任务再度被调度器选中，也不具备运行的条件，因为它继续运行所需要的资源并不满足。
为了实现上面的 pend 语义，我们应该解决如下问题：
- pend 时，task 应该被从 runqueue 上摘下来。这样调度器就不会再从 runqueue 中选中此 task 让其运行。
- 当资源满足时，作为 pender 的 task 需要能被唤醒。所谓“唤醒”的语义，就是重新进入可被调度器选中进而运行的状态。这就要求我们需要有一个数据结构把 pender 们管理起来，我们不妨称这个数据结构为等待队列（waitqueue）
一个可行的 pend 实现如下：
/* 入参 self，为当前主动发起 pend 操作的任务
* 入参 resource，为 self 所需要等待的资源
*/
FUNC pend(self, resource):
/* 第一步，将 self 从 runqueue 上摘下
*/
runqueue.remove(self)
/* 第二步，将 self 加入到 resource 的 waitqueue 上
*/
resource.waitqueue.add(self)
/* 触发 schedule，让调度器选择下一个 task 来运行
* 这里注意，self 已经不在 runqueue 中，故而调度器永远也不会选择 self 来运行
*/
schedule()4.2.3 sleep
其实看透了，sleep 与 pend 的本质是相同的。
实现 sleep 语义要解决的问题，与 pend 语义要解决的问题几乎是一样的。
不同的是，在 sleep 语义下，当 task 等待时间到期时，不是将其放到一个 waitqueue，而是放到一个 sleepqueue 上：
/* 入参 self，为当前主动发起 sleep 操作的任务
*/
FUNC sleep(self):
/* 第一步，将 self 从 runqueue 上摘下
*/
runqueue.remove(self)
/* 第二步，将 self 加入到一个 sleepqueue 上
*/
sleepqueue.add(self)
/* 触发 schedule，让调度器选择下一个 task 来运行
* 这里注意，self 已经不在 runqueue 中，故而调度器永远也不会选择 self 来运行
*/
schedule()4.3 唤醒语义的实现
4.2 节中我们通过 yield、pend、sleep 语义，实现了让 task 放弃 CPU。
在合适的机会下，放弃 CPU 的 task 还会被“唤醒”从而重新得到被调度的机会。
下面讨论 yield、pend、sleep 三种主动放弃 CPU 的场景下，如何实现唤醒。
4.3.1 yield - ?
通过 yield 主动让出 CPU 的任务，应该如何被“唤醒”？
这里再强调一下，啥是“唤醒”？
一个任务被“唤醒”，意味着这个任务重新进入了“可以被调度器选中”的状态。
那一个任务啥时候“可以被调度器选中”呢？没错，就是当它在 runqueue 里面的时候（schedule 函数）。
而因 yield 放弃 CPU 的 task，其压根就从来没脱离过 runqueue，我们在 yield 语义的实现里，只是将 task 移到了 runqueue 的末尾，而非摘除。
所以发起过 yield 的 task，压根不需要被唤醒。
当 runqueue 上正在运行的任务调用到 yield、pend、sleep，进而触发 schedule 时，该任务自然可能会被选中。
4.3.2 pend - ?
pend 与 yield 不同，因 pend 而让出 CPU 的 task 压根就不在 runqueue 上了。
要唤醒这类 task，需要实现 post 语义，该语义会被资源的释放者调用，用来唤醒资源的等待者。
根据“唤醒” 的定义，post 语义应该：
- 将 pend 在资源等待队列上的 pender 重新加回到 runqueue 上。
- 当然也要将 pender 从资源等待队列上摘下。
/* 入参 resource，为要释放的资源
*/
FUNC post_all(resource):
/* 这里根据资源释放时，是唤醒所有的 pender，还是个别 pender
* 有不同的实现，post_all 实现的是唤醒所有 pender 的 post 语义
*/
FOR task IN resource.waitqueue.tasks():
/* 将 waitqueue 上的 task，从 waitqueue 上摘除
*/
resource.waitqueue.remove(task)
/* 将 task 重新加回到 runqueue 上
*/
runqueue.add(task)
/* 触发一次调度
*/
schedule()
FUNC post_one(resource):
/* post_one 实现的是唤醒单个 pender 的 post 语义
*/
task = resource.waitqueue.first_task()
resource.waitqueue.remove(task)
runqueue.add(task)
schedule()这里可能会有人疑问，为啥 post 的最后也要触发一次 schedule 呢？
因为 post 会唤醒其他 task，在多优先级的内核上，被唤醒的任务可能比当前正在运行的任务优先级更高，因此被唤醒的任务需要立即被投入运行，故而需要触发一次 schedule。
但是本文 FCFS 的傻瓜调度模型下，其实没必要。
4.3.3 sleep - ?
sleep 与 pend 本质差不多，只是发起唤醒操作的，不是某个资源的释放者，而是内核的一个定时机构，我们不妨称这个定时机构为 tick：
FUNC tick():
FOR task IN sleepqueue.tasks():
/* 这个定时机构的任务，就是固定间隔去看一下 sleepqueue 上的任务是否到期
*/
IF task.time_is_up():
/* 如果到期了，则执行类似 post 中的操作
*/
sleepqueue.remove(task)
runqueue.add(task)
schedule()5. 线程状态转移的本质
5.1 请拉黑
在 3.1 节中提到，讲调度时，“如果有人拿出一张线程状态转移图，请直接拉黑。”
为什么这么说？因为言必称“线程状态转移图”的人，压根就没搞明白线程发生状态转移的本质。
那些代码中充斥着诸如如下代码的 RTOS 内核实现，请直接拉黑：
task.status |= READY
task.status &= ~(READY | BLOCK）
if (task.status & (READ | BLOCK))
balabala不是说内核实现中不应该去记录线程状态的变化，而是说这些状态的设定，应该是隐晦的、顺其自然的，而不应该是如此 naked、nonsense、crude 的。
注意，本文主要讨论 RTOS，linux 下有进程模型等，让线程状态设计异常复杂，不在本文讨论范围内。
5.2 本质是什么
从一个 task 的视角来看，它此刻的状态的本质，就是它现在正位于哪个管理数据结构之中。
换句话说，状态只是一个形而上的概念而已，这个形而上的概念必然对应的是一个形而下的具体 case。
- 如果一个任务是 ready 的，那么它此刻正位于 runqueue 中。
- 如果一个任务是 pend 的，那么它此刻正位于某个资源（软件机构）的 waitqueue 中。
- 如果一个任务是 sleep 的，那么它此刻正位于 sleepqueue 中。
除此之外呢？还有一种可能，就是一个任务既位于某个机构的 waitqueue 中，又位于 sleepqueue 中。
造成这种局面最典型的情况就是任务调用了带超时参数的 pend 接口，比如 tos_mutex_pend_timed，那么此刻，task 既在等 post，也在等时间到期。
5.3 wakeup 语义：从本质层面的统一
在 4.3 节中，我们针对 pend、sleep 情况，实现了对应的唤醒语义。
但这两个实现还不够 meta。根据 5.2 节，我们设计如下 wakeup 语义，并将 post、sleep 唤醒语义统一到 wakeup 语义上：
FUNC wakeup(task):
/* task 在某个 waitqueue 上，则将其从 waitqueue 上摘除
*/
IF task.in_waitqueue():
task.waitqueue.remove(task)
/* task 在 sleepqueue 上，则将其从 sleepqueue 上摘除
*/
IF task.in_sleepqueue():
task.sleepqueue.remove(task)
/* 加入 runqueue
*/
runqueue.add(task)我们来审视一下上述 wakeup 逻辑是否完备：
- 如果任务是 pend 进入的等待，那么其只会位于 waitqueue 上，且唤醒者必然为 poster，从 waitqueue 上摘除并加入 runqueue，没问题。
- 如果任务是 sleep 进入的等待，那么其只会位于 sleepqueue 上，且唤醒者必然为 tick，从 sleepqueue 上摘除并加入 runqueue，没问题。
- 如果任务是 pend_timed 进入的等待，那么其既会位于 waitqueue 上，也会位于 sleepqueue 上，并且唤醒者既可能是 poster，也可能是 tick：
- 如果是 poster 调用的 wakeup 接口：证明此时 pender 已经等到了它想要等的东西（信号量或者互斥锁，whatever），无需再等在 waitqueue 上，同时 pender 也无需再继续等在 sleepqueue 上了，waitqueue、sleepqueue 上都摘下并加入 runqueue，没问题。
- 如果是 tick 调用的 wakeup 接口：证明此时 pender 的等待已经超时，也无需再等在 waitqueue 上了，更无需再等在 sleepqueue 上了，没问题。
至此，我们可以基于 wakup 语义，完成对 post 及 sleep 唤醒语义的统一：
FUNC post_one(resource):
task = resource.waitqueue.first_task()
wakeup(task)
schedule()
FUNC tick():
FOR task IN sleepqueue.tasks():
IF task.time_is_up():
wakeup(task)
schedule()6. 一点简单的魔法
如果日子就这么一直平淡地过下去似乎也没啥。
但直到有一天，一个 task 内部写了一个死循环，且内部不会主动（调用到 yield）或被动让度 CPU（调用到 pend），导致其他 task 都被饿死了。
这显然是资源出现了不合理的分配，这时候就需要一点简单的魔法了。
6.1 魔法的施展
这里的关键是如何施展魔法。
如果一个 task 死循环，而我们又不希望这个死循环 task 独占系统的 CPU 资源，那么我们就需要有打断 task 运行的能力。
如何打断 task 的执行？没错，中断。而且最好这个中断是周期性的，使得我们可以固定间隔施展魔法。
无论是 RTOS 还是 linux，一个常见的实践就是起一个周期性的硬件定时器（本文不考虑 tickless 场景），该定时器以固定的频率（HZ）触发硬件中断，就像一个系统的心跳一样。
如你所知，这个周期性的节拍中断，就是 tick。
6.2 时间片魔法
解决死循环任务霸占 CPU 的问题，可以引入时间片来解决。
核心思路是：给每个 task 赋予一个时间片，task 在一次持续运行中，最多只能运行时间片的时长，一旦时间片耗尽，强行让出 CPU。
FUNC tick():
/* current_task 为当前正在运行的任务
*/
IF --current_task.timeslice == 0:
/* 时间片耗尽
* 重新复位当前任务的 timeslice，并 yield 当前 task
*/
current_task.reload_timeslice()
yield(current_task)实际上，带时间片轮转的算法，又称为 round robin。
6.3 优先级魔法
RTOS 中一个常见的调度设计，是给每个 task 赋予一个优先级，所预期的行为是，如果系统中存在不同优先级的 ready 任务，则优先让优先级最高的任务运行。
这个稍微复杂一点，但实现起来其实很简单，只需要稍微改一下 runqueue 即可：
FUNC schedule():
/* 摘取 runqueue 上优先级最高的 task，并运行之
*/
task = runqueue.highest_priority_task()
/* 如果 runqueue 上的最高优先级的 task 不是正在运行的任务，
* 则切换到 task 上下文中运行
*/
IF task != current_task:
context_switch_to(task)相较于 FIFO 算法，带优先级的调度无非就是将 task 挑选逻辑，从 runqueue.first_task() 改成了 runqueue.highest_priority_task()。
具体工程实践中，带优先级的 runqueue，可以通过优先级 bitmap 的链表数组（本质上类似哈希表），或者红黑树之类的树形数据结构来实现。runqueue 的具体实现不在本文讨论范围。
6.4 何谓抢占
本节不讨论类似 linux 抢占这种庞杂的话题，实际上，linux 调度是否使能抢占的本质，是在内核态中断处理返回时，是否做任务的切换，如果要在这个点上做切换，就是使能了抢占，否则不是。本文不过度展开，有机会后续专门撰文。
这里想讨论的是，“抢占”一词其背后的本质。
在我看来，抢占的本质，就是当系统中出现一个，可能比当前任务更适合运行的任务（“更适合”的语义可能是基于优先级的，也可能是基于 vruntime 之类的指标）的时候，尽快让这个更适合的任务被投入运行。
那实现抢占，核心是要解决：识别什么时机可能会出现更适合的任务，并及时将上下文切换到更适合的任务中。
出现更适合任务的典型时机有：
- 调用 wakeup 语义时：wakup 会触发任务状态从非 ready 变 ready，而被唤醒的任务可能比当前正在运行的任务更适合运行。故而调用 wakeup 语义后，需要检查是否要抢占（本质就是触发调度，下同）。
- 开抢占（TencentOS tiny：tos\_knl\_sched\_lock/tos\_knl\_sched\_unlock，linux：preempt\_enable/preempt\_disable）时：在关抢占的这段时间内，可能会有中断处理函数调用了 wakup 语义，使得当前 cpu 上有其他更适合的任务被唤醒，所以重新打开抢占时需要检查是否要抢占。
- tick 中断处理函数中：tick 是周期性的中断，其肩负的一个很重要的职责就是刷新每个任务运行的时间信息。每个 tick 到来时，随着任务运行时间信息的刷新，某些任务可能会变得比当前任务更适合运行（或者说当前任务不再是最适合运行的）。在本文的调度框架中，最典型的场景就是 tick 中检查到当前任务的时间片用完了；linux 中，拿 CFS 来说，最典型的场景就是存在其他任务的 vruntime 更小。故而 tick 中在完成任务时间信息刷新后，也需要检查是否要抢占。
那什么时候做真正的上下文切换呢【检查到存在更适合的任务，只是给了内核一个“需要切换上下文”的 hint，其本质只是设置了一个 flag，而并没有触发真正的上下文切换】？
对于 v7m 架构的单特权级 RTOS 内核来说，一般是通过在 context\_switch\_to() 中悬起一个 pendSV 中断，真正的上下文切换需要在该 pendSV 处理函数中来做。
对于 linux 这种分态的内核来说，情况就更复杂了，可以做上下文切换的一般是几个固定的点位：内核态中断返回（使能内核抢占的情况下）、用户态系统调用返回、用户态异常/中断返回。
ARM mbed OS 是一个分态的 RTOS，其切换点位基本上与 linux 类似，如果嫌 linux 代码太麻烦，可以读一下 ARM mbed OS 的源码。另外，本号很久之前写的《中断中的上下文切换》，对 RTOS 中断中的上下文切换相关细节进行了讨论，感兴趣的可以取阅。
7. 总结
本文从一个极简的调度框架入手，解构了“调度”概念背后的元问题：等待、唤醒，等等。并对线程状态的本质进行了讨论，进而提出了统一的唤醒语义实现。
文章对所谓的魔法（也就是调度算法）进行了一些简单的讨论，旨在展示调度算法施展的基本手法。最后，讨论了一下“抢占”一词背后的本质。
本文所借助的模型虽然简单，但却直击了最朴素最基本的元问题。调度种种，不过尔尔。
后续文章展开对更复杂的 linux 调度器实现的解读。
作者： 戴胜冬
文章来源：窗有老梅
推荐阅读
欢迎大家点赞留言，更多Arm技术文章动态请关注极术社区嵌入式客栈专栏欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。
