时钟与阻塞

硬件时钟

我们使用的硬件为内核计数器。

SysTick：

The RCC feeds the external clock of the Cortex System Timer (SysTick) with the AHB clock (HCLK) divided by 8. The SysTick can work either with this clock or with the Cortex clock (HCLK), configurable in the SysTick control and status register. [STM32F4xx Reference manual(RM0090Rev20)]

When enabled, the timer counts down from the value in SYST_CVR. When the counter reaches zero, it reloads the value in SYST_RVR on the next clock edge. It then decrements on subsequent clocks. This reloading when the counter reaches zero is called wrapping. [ARM DDI 0403E.e]

SysTick exception is permanently enabled. Software can suppress hardware generation of the SysTick event, but ICSR.PENDSTSET and ICSR.PENDSTCLR are always available to software. [ARM DDI 0403E.e]

易知对于 168M STM32F407 的 SysTick 时钟频率为 21M , 此时其分辨率为 47.619ns，可执行语句约为 10 。

DWT

+ When implemented and enabled, CYCCNT increments on each cycle of the processor clock. When the counter overflows it wraps to zero, transparently.
+ The DWT unit suspends CYCCNT counting when the processor is in Debug state.

易知对于 168M STM32F407 的 DWT_CYCCNT 时钟频率为 168M , 此时其分辨率为 5.952ns，可执行语句约为 1.25 。

使用策略

对于 PendSV 中断，包含 25 条汇编语句(早期版本，仅包含上下文切换)。考虑到其包含向量操作与连续内存读写操作，执行时间保留 100% 裕度。则平均等待时间约为 261.890ns( $119.04*2+47.619*0.5$ ) ，假定每秒进行 3000 次重要任务上下文切换，则因上文切换产生的性能损耗约为 0.0786% 。

为了完成之前提到过的高时间精度的调度，通过对 PendSV 进行阻塞的方式完成时间对齐。阻塞循环过程为三条指令(约为 14.284ns)，阻塞后需要完成两条指令(约为 9.523 ns)。也就是说在不考虑量化精度的情况下，时间对齐的精度为 5.952ns，平均误差约为 7.142ns 。

看门狗

看门狗作为返回内核的手段。当长时间无法返回系统进程时，触发看门狗并返回。

空闲任务的二重性

空闲任务在普通情况下，作为补位和填充处理器时间而存在。
在某些情况下，空闲任务通过 SVC 使自身升格为内核任务。内核任务在 SVC 中处理。

静态调度表

静态调度的时间

首先是调度的时间单位，对于 STM32F4 系列，比较极限的任务频率为 50kHz (即 20 μs) ，故使用 μs 作为调度的时间单位。

静态调度的数据模型

一般来说，对于内核级别的数据结构，越简单越好。很自然的想法是使用一个静态数组来完成调度表。
但是考虑这样一种简单情况：一个任务的周期为 100μs ，另一个任务的周期为 1000μs。那么在排列线性表的时候，就会产生巨大的空间浪费。具体来说，当两个任务的周期互质，或相差较大倍数时，很可能使得线性表的空间复杂度急剧上升。因此，使用最大公约数的思想，建立一种新的数据模型：最大公约树。

不是谐音梗，真的。

最大公约树

如图所示，一棵最大公约树遵循如下生成规则：

任意子节点都是父节点的倍数。
同一父节点的越大的子节点越靠右侧。
若一个子节点具有多个公约数，那么选择最大的公约数作为父节点。

定理：满足上述条件的任意树，最多只存在一个虚拟节点，且该节点为根节点。
证明：

虚拟节点：称为满足生成条件，而生成出的不存在节点为虚拟节点。如任意互质数集的最大公约树，其最大公约数为一，且为根节点。
由上述例子易知，当数集存在一个互质子集且向该子集添加数集内的任意其他元素后依然是互质的，对于这种数集的最大公约树，必定会生成出一个虚拟节点。
设除根结点外，存在其他虚拟节点。由生成规则 1 得，该节点一定可以由其父结点倍数表示，故除根节点外不可能存在其他虚拟节点。
综上，定理得证。于是我们有，对于不存在虚拟节点的任意数集构成的最大公约树，其空间为数集大小 * 结点大小 + (数集大小 - 1) * 指针大小；当存在虚拟节点时，额外加上结点大小 + 指针大小。

最大公约树的建立

创建这个数据结构有点麻烦，因为每个结点的度是不确定的。先来整理一下问题和已知条件：
问题：找到一种方法，进行递归建树。
已知：

整个空间的大小已知。
全部结点的周期已知。
由 1 知，我们不需要进行多次内存申请；由 2 知，我们可以获得一个有序数列。
再来看一下棘手的地方：每个结点的度是未知的，因为需要保证每个节点都保存所有孩子，所以对于单个结点的空间是未知的。
广度搜索？这应该是比较直觉的方法，但是我觉得有点复杂，时间复杂度应该 O(n^2) ，不喜欢。
深度搜索？好像可以，但是我觉得可以优化。
已知一个有序数列，其最大值必定是叶节点。那么我们可以按照如下步骤进行递归建树。（从大到小的数列）
找到最大值(端点)，初始化该节点。（度必定为 0 ）
搜索第一个公因子，因为数列有序，那么第一个公因子必定是最大的公因子。
(深度搜索)反向搜索其他的叶节点，并重复步骤 1 。
理论上来说这种方法应该具有最佳的时间复杂度，但最终并没有选择这个方法，因为怕爆栈。最后选择将广度搜索融合进去，简化了迭代深度。

已知降序数列 a, b, c, d, e, f, g ，若 $k \in N, a = k*e$ 且不存在更小的的 k 值使上式成立。能否当视角受限于子数列 {a~e} 时，依可满足生成规则 3 。
不妨设 b 为 e 的倍数。1. 若数列中只有 b 是 e 的倍数，那么 b 一定是 e 的子结点。2. 若数列 {a~g} 中存在多个结点为 b 的因数，以 e 为分界线，当存在其他因数大于 e 时，一定被包含在子数列 {a~e} 中，故可以递归建树；当不存在其他因数结点大于 e 时，则 e 是最大因数结点，可以建树。