Response-time analysis for mixed criticality systems #
本文是非常重要的论文，至少在单核fp的情况下，是后续诸多论文的基础
对于模型，他基本符合在MCS综述里面提及的模型（我怀疑综述也是从这里抄过来的），模型中使用的只是一个双优先级的模型（LO和HI），当然这篇论文说他也有多优先级的情况，并且是单处理器的。
要是缺少相关模型知识就去看综述吧。
首先，本篇论文给出了几种算法
1/ PC（Partitioned Criticality） #
这个算法说的是，分割给不同的关键性以不同的时间区域，所以高低关键性没有互相影响的情况。相对的，这就是不混合的关键系统，而混合关键系统则是混合的时间区域，不在根据关键性来区分
2/ SMC #
优先级由ddl来确定而不再根据关键性水平，从而，一个任务会受到优先级更高（ddl更近或者其他优先级安排）但是临界性更低（也就是错过了ddl相对没那么有关系）的任务的影响。
SMC使用的方法是不允许其超过表示的执行时间
但AMC是允许的
在这里，通常按照之前的说法使用RTA分析方法，公式么也如出一辙
\[ R_i=C_i+\sum_{τ_j ∈ hp(i)} \lceil {\frac{R_i}{T_j}} \rceil C_j \]但是考虑到临界性，假设有两个任务，其中任务i的优先级大于j，他认为需要考虑三种情况
2.1/ Li = Lj，相等的时候，正常用优先级即可，这没啥差别
2.2/ Li < Lj，这种情况下应当使用Cj（Li），就是在i的关键级别上的j的Cj，来计算
2.3/ Li > Lj，这种情况下，再使用Cj（Li），但是注意到Li大于Lj，所以实际上他被允许执行的时间会比Lj水平上的执行时间更长，并且系统是按照高优先级去进行验证系统可用性，其实不够优化，所以相应的，策略存在两种，另一种是按照Lj去给出Cj
分别是
\[ R_i=C_i+\sum_{τ_j ∈ hp(i)} \lceil {\frac{R_i}{T_j}} \rceil C_j(L_i) \]和
\[ R_i=C_i+\sum_{τ_j ∈ hp(i)} \lceil {\frac{R_i}{T_j}} \rceil C_j(min(L_i,L_j)) \]前者，实际上需要时间监控，来保证j在Lj上运行不超时。
后者虽然不需要监控器，保证不超时，但是实际上给了更高的关键级别的运行时间，这导致了成本更昂贵
被称为SMC-NO
然后提到了Vestal使用audsley的priority assign的事情，给出了一些分析。
3/ AMC #
这个算法嘛，伟大无需多言
简单来说分为几个步骤
3.1/ 存在一个全局的关键性指示器，最开始是LO，以及一个时间监控器（当然只需要监控是否超时即可）
3.2/ 当始终是LO的情况下，按照优先级依次调度
3.3/ 当超时（超过他的LO级别声明的C）发生的时候，关键性指示器从LO变到HI
3.4/ 当始终为HI的时候，声明的关键性级别为LO的任务将不会运行，只会按照优先级运行关键性级别为HI的任务
3.5/ 在某些情况下，可以允许他退化成为优先级为LO（比如优先级为HI的任务一个都不运行了）
他用于说明这个的例子我觉得也很合适
就是他有两种人群：certification authority（CA）就是验证系统可行性的，和system designer 前者会考虑他的WCET，后者希望尽量能用
考虑在抢占的固定优先级单处理器上的系统，仅包括三个工作J1、J2和J3。所有三个工作都在0时发布。工作J1的截止日期为时间2，而另外两份工作的截止日期为时间3.5。作业J2和J3是高临界且需要认证的，而J1是低临界的，因此不是需要认证的。
系统设计师相信，每项工作的最坏情况执行时间（WCET）不超过1。因此，只要J1没有给予最低优先级，所有三项工作都会在截止日期前完成。
然而，CA要求在认证过程中使用更悲观的WCET估计，并允许工作J2和J3可能需要1.5个执行时间单位。即使J1只执行1个时间单位，作业J2和J3只有在获得最高的两个优先级时才能安排；但如果这样做，即使J2和J3只执行1个时间单位，J1也会错过截止日期。
因此，人们可能会得出结论，系统不能以系统设计者和认证机构都能接受的方式安排系统。幸运的是，有一个可以让双方都满意的执行方案。考虑优先顺序J2，然后是J1，最后是J3；以及从时间0开始的以下运行时行为：
在[0，1)执行优先级最高的工作J2。
如果J2在时刻1完成执行，那么在[1,2)上执行J1，在[2,3)上执行J3，从而确保满足所有最后期限（如果需要的话J3可以在[2，3.5)执行）。
如果J2没有按时完成1的执行，那么丢弃J1并继续执行J2，在[1.5,3)上执行J3。
其实关键就在于这里如果J2没有按照系统设计师期望的那样正确的执行的话，就会丢弃J1（实质上就是AMC这里增加关键级别，而J1在低关键级别，所以他就没法完成了（如果我们需要J2和J3都按时完成的话）。
那么这时候，如果J2按照系统设计师所期望的正常在1个单位时间内执行完了，那么就按照第一种可能，否则丢弃J1，按照高优先级进行，以满足CA的需求。
SMC和AMC的差别 #
前者如果有一个LO的任务超时了，他会被禁止执行， 后者如果一个超时了，所有LO的都被禁止执行
前者如果高关键性的任务超时了，他还能继续跑，然后低关键级别任务就只是错过ddl 后者会停下来（我的理解是在LO关键级别停下来，但是还是能继续跑，而不错过DDL）
AMC的响应时间分析 #
LO模式的可调度性分析 #
跟那个基本上一模一样，反正在LO模式下所有task都能跑 \[ R_i^{LO}=C_i+\sum_{τ_j ∈ hp(i)} \lceil {\frac{R_i^{LO}}{T_j}} \rceil C_j(LO) \]
HI模式的可调度性分析 #
\[ R_i^{HI}=C_i+\sum_{τ_j ∈ hpH(i)} \lceil {\frac{R_i^{HI}}{T_j}} \rceil C_j(HI) \] 实际上只考虑LO模式下或者HI模式下都可以适用原先的可调度性框架
切换的可调度性分析 #
主要分析集中在这里
总而言之，他提供了两种响应时间分析的情况，一种被称为AMC-rtb，另一种被称为 AMC-max
关于同样都是，AMC算法，response time analyse的方法不同，如何影响最后的效果，这个怎么理解，我认为这是由于在这种实时的系统中往往依赖于早期的静态分析，从而决定这些任务是否能安排的下。
对于cpu利用率的影响，我的理解是这样的，如果我们的前期静态的算法能尽量的把多的任务放入到系统中去，那么实际的cpu利用率也会更高，但是如果我们的分析的响应时间上界离我们的实际情况差别太大，那么就会导致他实际上塞入了更少的任务。利用率更差
因此，我认为这是两种不同分析方法对于实际的系统的影响，哪怕他们使用相同的AMC调度算法（所以更贴近的响应时间分析是有意义的）
AMC-rtb分析 #
他这个最开始的想法是，在R*时刻，分别计数在他之前的高关键级别和低关键级别的任务，让高关键级别无论如何都运行在高关键级别的时间上面，而低关键级别无论如何都运行在低关键级别的时间上（显然这种情况高于他的真实上界，因为高关键级别的任务在发生这种模式切换之前是运行在C（LO）上面的，而不是C（HI））
具体的初始情况的公式如下（相关含义，刚才已经说了，不再赘述）
\[ R_i=C_i + \sum_{τ_j ∈ hpH(i)} \lceil {\frac{R_i}{T_j}} \rceil C_j(HI) + \sum_{τ_j ∈ hpL(i)} \lceil {\frac{R_i}{T_j}} \rceil C_j(LO) \]当然，很显然的，他为了更好的贴近上界，这个公式又更进一步的使用Ri LO来表示后面的半个式子
\[ R_i^*=C_i + \sum_{τ_j ∈ hpH(i)} \lceil {\frac{R_i^*}{T_j}} \rceil C_j(HI) + \sum_{τ_j ∈ hpL(i)} \lceil {\frac{R_i^{LO}}{T_j}} \rceil C_j(LO) \]AMC-max分析方法 #
这个相对来说更复杂一些，但是也更贴近上界 \[ R_i^{s} = C_i(HI)+ I_L(s) + I_H(s) \]
他这里假定有一个任务τs，在s时刻按照AMC的方式，进行了关键级别的转换(这是相比于rtb，额外考虑的情况)
\[ I_L(s)=\sum_{τ_j ∈ hpL(i)} (\lfloor {\frac{s}{T_j}} \rfloor+1) C_j(LO) \]首先对于关键级别为低的任务，都应该使用LO的C来计算，因为显然在任务切换之后，肯定都不跑了嘛
另一个关键是，他这时候需要有多少次运行
这里必须从0到s这段时间开始算（因为之后就寄了，跑不了了）
对于I_H(s)的计算
则更为复杂，考虑一个其他的任务τ_k，运行到s之后的某个时刻t（事实上，按照响应时间分析的原则，以及之后的实际公式来看，应该用R*更合适，不过都一样，没必要）
在s到t这个时间，任务τ_k可能会最多释放 \[ \lceil {\frac{t}{T_k}} \rceil \] 这么多次数
在s到t这段时间可能产生的释放的次数是 \[ \lceil {\frac{t-s-(T_k-D_k)}{T_k}} \rceil + 1 \]
这里考虑了如果D < T的情况，deadline比周期更小，那么在ddl到下次周期到来中间存在一个空隙
然后定义了一个
\[ M(k,s,t)=min {\lceil {\frac{t-s-(T_k-D_k)}{T_k}} \rceil + 1,\lceil {\frac{t}{T_k}} \rceil} \]按照他的说法是因为，这个+1会有影响，如果s很小，而Tk-Dk等于0的话，实际上他不应该超过后者，但是这种情况可能多了个1
相应的，对于I_H(s)的计算以及最终的公式如下
\[ R_i^s = C_i(HI) + I_L(s) + \sum_{τ_j ∈ hpH(i)} { M(k,s,R_i^s)C_k(HI) + ((\lceil {\frac{t}{T_k}} \rceil - M(k,s,R_i^s)))C_k(LO) } \]很显然的，他就是计算了以s为分割，从0到响应时间Ri^s这段时间，前半段按照C（LO）计算的时间，后半段是C（HI）计算的时间。
例子和实测 #
总之，实测肯定是AMC-max更加贴合响应时间的上界，然后效果相对最好。
当然除了上面提到的SMC，SMC-NO，AMC-rtb，AMC-max，还有一个CrMPO和一个最优的，CrMPO这个是说先根据优先级排序然后根据ddl排序
可以看到混合关键系统中，这几个算法都是有效的但是AMC-max确实很棒就是了。