Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems #
其实应该来说，Mixed-Criticality Scheduling of Sporadic Task Systems可能是这个的原文（？）但是看上去内容和作者都没啥大变化，估计就是一篇文章改吧改吧的结果，那就只看这个顺序更靠后的文章即可（2015年 JACM）
模型在传统的MCS的基础上增强了di=pi的属性。这被本文称为混合关键性Sporadic task system
开头在上面那篇2010的文章的基础上也总结了一下10到15那段时间EDF-VD相关的研究。
模型定义 #
一个系统中有K个关键性级别。然后存在n个任务 每个任务都有一个关键性级别χ，属于K的取值中 以及三元组（ci，di，pi）
ci是一个向量，表明从关键性级别1到χ的WCET。并且，关键性级别越低，ci越少。
di是deadline
pi是任务的最小到达间隔。
这个task会按照上述的最小到达间隔生成一系列的MC Jobs，Jij 其中i表示task的id，而j表示序列号
Jij=（aij，lambda ij）
aij是到达时间，lambda在0-ci之间，是具体的job的要求执行时间
最后还有一个scenario的场景的关键性级别k（小k）。大于等于该关键性级别的任务都需要按时完成
对于利用率的定义
\[ u_i(k) = \frac{c_i(k)}{p_i} \]在k level的利用率是
\[ U_l(k) = \sum_{i∈[n]:χ_i=l}{u_i(k)}，其中l∈[1:K],k∈[1:l] \]所以第一个条件是 对于一个速度为σ的处理器来说， 必须对于任何一个k等级而言，其利用率不大于1
但是并不是说，只要系统利用率小于1，EDF就一定有一个可行的调度
他给的例子是一个level转换的过程，如果一直都是低关键性级别，或者高关键性级别，那么就没问题。但是如果存在超时并进行状态切换，就会出问题。
至于为什么AMC那套不出事情（因为按照这个设定是没法处理的）。我的理解是他在静态分析的阶段已经完成了相关的事情的分析，这是没法过静态分析的。
我觉得，对于上面的这个，可以用一个矩阵（实际上，只有个三角矩阵）来形容，矩阵内是cij，i表示task，j表示level，因为高于task的level的系统level的cij没有意义，会丢弃掉低优先级的任务，所以是一个三角矩阵，下面task1和2的任务关键性级别是1，task3和4的任务关键性级别是2，task5的是3
我举个例子（下面表里面，实际上隐含了每个任务的p是不变的，所以u和c是一一对应的。因此下面有所混淆）
| Level1 | Level2 | Level3 | |
|---|---|---|---|
| task1 | c11* | ||
| task2 | c21* | ||
| task3 | c31 | c32* | |
| task4 | c41 | c42* | |
| task5 | c51 | c52 | c53* |
按照我对上面式子的理解，U_l(k)表示的是用户等于l（χ_i=l），系统等于k的u总和。 如，l=1，k=1，那么就应该是c11和c21在求u的和 如果是l=2，k=1，那么应该是c31和c41在求u的和
相应的
\[ \sum_{l=1}^{K}{U_l(l)} \]这里头l=k都是l 也就相当于把上表的所有带星号的值对应的u求和。
我觉得对这个东西的理解很重要，否则，后面的公式推倒都抓瞎。
EDF-VD #
分为离线预处理和运行时调度两个阶段。
离线预处理阶段对可调度性进行了分析，如果可调度，则增加两个输出值，一个是k，另一个则是每个任务所具有的虚拟截止时间^di，虚拟截止时间永远不会大于真实的di。
运行时调度，如果系统小于等于k，则使用虚拟截止时间来安排作业（EDF嘛，调度顺序跟deadline相关），否则根据原始截止时间来安排作业
离线预处理阶段 #
看图
如果存在所有l情况下的U的求和都小于等于1。把虚拟截止时间设置为原始截止时间 （疑问：为什么如此？？？上面的例子里面U都小于1，但是却不可调度。而这里在U小于等于1的情况下，虚拟截止时间就是实际原始截止时间。 我仔细看了一下，上面讲的U_l(k)是说在每个任务的关键级别为l的情况下，所有的任务i在系统关键级别为k的情况下的使用率总和。 然后他这里的是对所有的U再求和。也就是说，所有关键级别的运行情况都求和，仍然小于1） 就实际意义而言，应该是，每个任务都按照他们自己宣称的关键性级别，在该级别上运行，这时候不需要丢弃低关键级别的任务，也仍然能够调度的过来。
否则判断是否满足条件(3)（之后说），如果没有满足条件的系统k，就说明不可调度。
如果存在这样的k，就把1到k的关键级别的截止时间都设为原始的截止时间，但是高于k但小于K的则按照一个缩放因子来进行缩放，具体的值为什么这么取，后面也可以继续接着说。
运行时调度 #
他定义了current_level函数 就是说，目前所有的真正的执行时间，都小于等于该level下声明的ci，并且该level是最小的。
运行时调度 首先是根据前面离线阶段的处理
在l小于等于k的时候
所有低于l的任务都被丢弃。更高的则按照虚拟截止时间运行
在l大于k的时候，关键性k+1的任务都恢复原始截止时间。
可调度性的条件 #
作者给出了，要么
\[ \sum_{l=1}^{K}{U_l(l)≤1} \]要么，存在某个k值，满足
\[ 1-\sum_{l=1}^{k}{U_l(l)>0} \]并且满足
\[ \frac {\sum_{l=k+1}^{K}{U_l(k)}} {1-\sum_{l=1}^{k}{U_l(l)}}≤ \frac {1-\sum_{l=k+1}^{K}{U_l(l)}} {\sum_{l=1}^{k}{U_l(l)}} \]就是可调度的。 相关的证明如下
如果第一个条件满足，说明所有的任务都可以在他们自己宣称的关键级别上，按照该关键级别运行。
第二条件才是真正需要证明的部分
他的证明分为两部分
第一步，证明如果存在一个x≤1（这里的x不是指具体的task所在的level，χ，额有那么点混淆，不过问题不大），满足以下的条件
\[ \sum_{l=1}^{k}{U_l(l)}+\sum_{l=k+1}^{K}{\frac{U_l(k)}{x}}≤1 \] \[ x\sum_{l=1}^{k}{U_l(l)}+\sum_{l=k+1}^{K}{U_l(l)}≤1 \]则对于某个任务来说，EDF就是正确的可调度策略 第二步则反过来证明，如果存在某个k < K，那么就有x≤1满足上面两个式子
（就是正着推和反过来推，都需要满足，从而说明充分必要嘛）