调度器的具体实现

调度器将是整个系统中最核心的功能。调度器操作的实例对象为任务，向上拓展为进程间同步模块。可以说调度器封装设计的优秀与否将成为影响整个系统性能关键。
整个时间轴由无数个任务片构成，两个重要/次要任务之间的缝隙被调度任务填充。因此必须尽可能减小调度任务的长度。

本系统的核心需求依然是将重要任务之外的时间合理高效利用，并不强调实时性，因此不适用 Round-Robin(RR) 方法。

被调度任务的排序算法

关于任务的排序方法，对于 cortex-M 系列同时运行任务最多也就十余个。此时，对于时间复杂度 O(n) 与 O(log(n)) 无明显差距。因此，不使用 AVL 及红黑树类的排序方法，仅使用其退化的最简单模型 —— 有序链表。

定义：按某种方式排序的任务链表称为任务链。

就绪任务链：按照执行顺序排序的待执行任务。
- 包含重要任务链(静态调度表)与次要任务链(优先度表)。
延时任务链：按照恢复时间顺序排序的被阻塞任务。
挂起任务链：按照时间顺序排序的被挂起任务链。（其实就是无序的🤐。。。凑个定义好处理，嘿嘿嘿嘿）

调度的排序特点

考虑所有发生当前任务改变的时刻：

重要任务发生切换
重要任务因延时被阻塞
重要任务因等待事件/资源被阻塞
次要任务发生切换
次要任务（嵌套于重要任务延时中）需要返回重要任务
次要任务执行过程中，外部中断使资源使用情况发生改变
优先级出现反转，需要系统介入调整

基于此，我们有如下推论：

任务链永远是有序的。
- 第一个任务被添加时，任务链上仅有一个任务，此时是有序的。
- 假设第 n 个任务被添加时，任务链是有序的。
- 当第 n+1 个任务被添加时，无论是重要任务还是次要任务都可以在有序任务链上找到自己的位置。
任务链的更改是非均匀离散的(事件驱动的 FSM )。
- 任意时刻，任务链的状态是确定的。
- 当某事件发生后(如发生超时、注册事件的发生及资源的释放等)，任务链的状态将发生改变，且改变后的状态也是确定的。

另外，结合系统的调度特性，我们可以进一步得到：(不考虑调度优化)

任务链的更改时刻一定包含在主动释放和中断内。
- 显然易得，事件驱动么，一定发生了事件。
当发生主动切换时，任务链的状态不发生插入性改变。
- 主动切换发生时，当前任务被阻塞，且当前任务优先级一定大于等于待执行任务链首任务的。因此将发生置换反应。
当发生插入性改变时，一定发生了异步中断。
- 对于所有异步中断来说，其可抽象为一系列随机事件(注意，ARM 定义中没有异常挂起是一种异常状态)。概率论告诉我们任意时刻发生异常的概率密度应该满足 t 分布，或简单视为正态分布。（好像某种马尔可夫链？不知道反正只是定性分析）
- 当某一时刻发生中断时，产生的插入任务优先级可被视为条件分布，此时需要进行有序插入(需要查找)。

再进一步有：

当在执行重要任务时，不会发生插入性改变。

重要任务内算法一定是连续的，等待传感器数据时将使用如下方法：

大部分中断被禁用，需要使用无中断 DMA API 获取数据。

第一次执行任务，将完全阻塞任务并记录阻塞时间。

后续执行任务，将根据阻塞时间进行异步返回。
(很像贝叶斯估计啊，估计均值用于返回时间，估计方差用于计算时间裕度。但好像没什么必要哈，时间花销略高)

逐次记录，理论上将收敛于常数 t 。

当发生插入性改变时，一定是在次要任务段内。

定义：次要任务中断禁区及重要任务执行时间段被称为静态调度段，次要任务段（不包含中断禁区）被称为动态调度段。

调度优化设计

基于上述分析我们可以进行算法设计。

调度时间内不进行任务排序，只切换。

通过尽可能压缩 PendSV 异常的时间，来降低调度造成的性能损耗。为此我们使用双缓冲方式，每次取优先级最高的两个任务加载至交换缓冲区。

调度的抽象

因本操作系统不存在 RR 调度方式，所有除异常外所有任务发生上下文切换时一定存在任务状态改变：

当前任务主动切换，即高优先级任务被阻塞。(当前任务大于等于就绪任务)
当前任务被动切换，即高优先级任务就绪。(当前任务小于就绪任务)

此时，我们可以进行抽象优化，将所有任务的阻塞抽象为 delay 型阻塞：

对于真实的 delay 需求阻塞可以视为定长延时阻塞。
对于因信号量/事件等进程同步需求的阻塞可以视为非定长延时阻塞。

在有非定长延时阻塞需求的任务视角上看，其同步需求是"异步"的，可能由线程任务触发也可能由异常任务触发。总之，不需要由系统调度来关心，一定存在明确的触发信号。如同薛定谔的猫一般，在某个瞬间由非定长延时转化为定长延时。

注意：优先级反转的特殊情况，此时需要由系统介入进行优先级继承处理。

至此我们可以确定，调度器需要维护三类四个任务链：就绪任务链、延时任务链(定长与非定长)及挂起任务链。所以，我们只需要关心定长延时调度的设计即可。

定长延时任务链代码中称为 delayQueue，非定长延时任务链代码中称为 waitQueue 。
数据结构中需要提供一个反向查找的接口，用于在同时保存 delayQueue 和 waitQueue 中的位置。这样在“存在超时的等待事件”中，才能做到 O(1) 的删除，否则将退化成 O(n) 。

定长延时调度的设计

当一个任务，被操作系统调度回到运行状态时，称为任务的返回。任务的返回存在两种情况，异步返回与同步返回。

异步返回：指由异常触发的即时返回。
同步返回：指由操作系统时间更新实现的非即时定长返回。

也就说，一个任务一旦不再占用处理器，其定长延时时间是其最小延时时间。这也是为什么我不称该操作系统的 RTOS 的主要原因，我只保证重要任务的即时性。

所以我们需要两种方式的延时函数，根据任务属性自动选择或是要求用户使用两种 API ，等到写代码时再说吧。

不同任务的返回方式

对老四样讨论其返回方式：

重要任务：重要任务的延时需要异步返回；(详见上文，不再赘述)
次要任务：不重要，要求同步返回；
内核任务：内核任务只应该存在“任务调度”这个任务需要异步返回，其他任务只要求周期性处理即可；
异常任务: 激活的异常处理不可能被用户主动阻塞(如有巧合，纯属脑瘫)；但是异常任务本身会作为非定长延时转化为定长任务的转化手段。

吐槽：黑格尔的诗是吧？必然性存在于偶然性之中，没有脱离开偶然性的纯粹必然性。必然性不是孤立存在的，它通过大量的偶然性表现出来，并为自己开辟道路。笑死🥳

总结：重要任务、内核任务需要异步返回；次要任务需要同步返回。异常任务作为非定长延时转化为定长任务进而使次要任务同步返回的手段，即视为时钟的更新。

任务链视角下的返回

同步返回时一定发生了主动的定长延时任务链更新，且仅在定长延时任务链(简称延时队列)更新时发生同步返回。

延时任务是依赖于时间，且同步延时返回只依赖于操作系统的时钟。
操作系统的时钟更新是离散的，因此在操作系统的时间更新后进行任务队列的更新才有意义。
因此同步返回时，一定是系统更新延时队列，并且超时任务具有最高优先级。

即定长延时任务链更新是同步返回的必要非充分条件。(鉴定为学数学学的🤓。)

而操作系统的时钟的更新，一定是返回了内核任务。
现在，我们的问题转化为对于时间轴上的异步返回与主动释放时刻的任务选择策略。为了效率尽量高，我们应该尽可能减少中断发生和内核任务的执行次数。

同步返回：同步返回的任务是次要任务，因此我们只进行最低限度的同步返回调度，即延时队列更新。
异步返回：
1. 有多少具体的时刻有机会回到内核任务？
  - 静态调度段的进入
  - 静态调度段内的异步返回（直接排除）
  - 静态调度段的结束(主动释放)
  - 动态调度段的异常
  - 动态调度的主动释放
2. 在一个周期内选择哪几次异步返回进行队列更新？
  1. 内核只选择进入静态调度前进行主动的周期性任务更新，理由：减少内核任务对静态调度任务的影响。
  2. 当就绪任务链为空时，会触发延时队列的更新。
  3. 异常被视为时钟的更新，即立刻将等待该非定长延时的任务插入就绪任务链（允许发生上下文切换）。
TODO：若无就绪任务，将进入低功耗待机。（在指令集中看到了 WFE/WFI 指令，还需要研究一下。）

总结：

规则1: PendSV 只做任务切换，不做队列重排/时间推进。
规则2: 任何 IRQ/IPC 唤醒只进行任务链插入和上下文切换。
规则3: 所有复杂任务均延后至静态调度段的内核任务。

调度器的初始化

装载任务
1.1 装载空闲任务
1.2 装载就绪队列队首任务，若为空，则加载空闲任务

上帝视角下调度的实现

系统初始化，注册任务
任务激活(由挂起状态切换为就绪状态)，此时完成了初始状态有序的条件
调度器使能，系统开始调度(周期的开始)
进入静态调度段
- 执行内核任务，GC、延时队列更新等
- 要求预留时间必须大于内核任务所需时间
- 剩余时间使用 5 相同手法处理
执行重要任务
- 当重要任务被阻塞时，选择优先级最高的次要任务执行
- 阻塞时，使用 SysTick 定时提前返回。（注意：有点代码洁癖，不想因为首次单独加个 if 所以硬性要求给定初值）
若存在多个重要任务，中间的间隔将使用上述相同方法处理
重要任务完成，SysTick 用于下次静态调度段的异常返回
处理次要任务
- 按就序列表依次执行，或进入阻塞
- 异常会使次要任务链发生改变
SysTick 触发的异常返回，重新进入静态调度段(返回 4 )

短暂结语

内核层级调度只包含主动释放（yield） 与 延时（delay）。其他更复杂进程间同步（信号量/事件/消息等）的接口属于操作系统的组件，只能说实现内核时尽量考虑进来，等到后期慢慢开发吧。现在是受够了，纯纯纸上谈兵，实践是检验真理的唯一标准，先实现着看看吧。

这里记录一些想法(STMDB R12!,{R0-R15}🥱)：

调度模型扩展
其实这套系统可以同时覆盖硬实时（静态表）与软实时（优先级/动态就绪队列），甚至“临界实时”的折中场景。当前还是最小可行性系统先“一刀切”实现为优先级调度，后续考虑增加 EDF，或对优先级做分层调度策略。
事件广播（多订阅者）的中介化
假定某个事件被多个简短任务订阅，这种情况下会使订阅表内存上升、查找/唤醒逻辑复杂。我将这种任务称之为鸡肋任务。
我们可以将这些任务与系统隔离，通过中介进行广播转发。具体来说，这些任务以特定数据结构导出（通过链接器注册在指定section），使用链接器我们可以捕获被导出的基址和大小，换言之，这些任务在Flash区形成了一个数组。这时，可以使用一个任务来进行所有事件的转发广播。
基于 section 导出的反射入口
上述这种导出技术的优势是：减少“必须显式声明并注册指针”的胶水代码，在 CLI 的编写中有着极大的应用前景。如果我需要让一个函数被 CLI 成功解析进而要求内核响应任务的话，必须获得函数指针，换而言之，在 C 调用规约时必须进行声明，这是很麻烦的。再或者，我想在运行时使用 CLI 修改变量的值的话，那每个变量都要跑过来进行指针的注册，麻烦的要死。但是使用反射的方式，CLI 侧只需遍历导出表并解引用即可完成命令解析、函数调用或变量读写。
事件能否抽象为信号量？
事件似乎可以被视为一种特殊的信号量？我们可以将事件视为一个资源，当没发生时所有的订阅该事件的任务都在等待资源。当事件发生时，即资源被释放（通过信号量完成），此时等待该资源的最高优先级任务获取资源。又因为是单核处理器，依次获取资源与同时获取资源实践上是等效的。在所有任务执行完后，系统将该信号回收。因此，可以将事件抽象为信号量？
while(*dest++=*src++); 优雅，太优雅了
进程间通信
可等待对象 -> 邮箱/消息队列/管道
原语
有一些必要的原语需要要实现一下的，增加访问速度特化，尽量不使用中断屏蔽方式，读写查三部曲（LDREX/计算/STREX）实现。