目录
HLC-PCP：可证明混合关键性调度的资源同步协议
作者提出了一种新的资源同步协议，HLC-PCP，它可以在AMC下保证不同关键性级别的任务之间的资源共享和优先级反转控制并证明了HLC-PCP可以保证高关键性级别的任务在最坏情况下满足其截止时间。
详情参照操作系统论文导读（七）：Response-Time Analysis for Mixed Criticality Systems——混合关键系统的响应时间分析_管二狗赶快去工作！的博客-CSDN博客
任务定义：一组任务τ={τ1...τn}，访问的资源信号量以S={S1,...,Sm}表示，每个任务由下面的八元组定义<T,D,C（向量）,P,p,L,l,σ>，前四个为基础任务定义四元组;p为活动优先级，可以根据 PCP 在运行时动态更改;L为任务关键度，l为动态关键性可能会根据 HLC 在运行时动态变化，σ为任务使用的信号量组。
另外，在系统切换关键模式的期间，由于一些LO-crit任务可能由于资源同步而持续活动一段时间，因此除了AMC中的LO-crit和HI-crit模式外，需要考虑中间模式MCP，即从任何任务超过其C(LO)值的那一刻起，直到所有 LO-crit 任务都被丢弃并且系统进入 HI-crit 模式的时间间隔。
定义AMC在锁定在 LO-crit 模式下的优先级天花板为所有需要该临界区任务优先级的最高值
定义AMC在锁定在 HI-crit 模式下的天花板优先级 ，类似的，只是去掉了LO任务
为每个临界区再定义一个动态优先级天花板，为可以锁定它的活动任务的最高优先级（举个例子，当LO模式下，那就是所有任务，当HI模式下，那就是HI级别任务）
定义一个动态系统优先级上限 dSPC ，为活动任务（注意是活动任务，不是所有任务）当前持有的所有信号量的最大动态优先级上限，说白了就是正在被占领的临界区的所有动态优先级天花板的最大值。
每个信号量都与一个恒定的关键度上限相关联，等于可能锁定它的所有任务的最高关键度，可以理解为关键度天花板。
HLC-PCP应用于AMC的作业调度规则如下：
1.有一个系统范围的关键性级别指示器θ，初始化为LO。 在任何时候，系统都可以处于三种模式之一： LO-crit 模式 ( θ=LO)；HI-crit模式 (θ=HI)； 模式改变周期 (θ=MCP )。 在系统执行期间，当任务没有持有任何信号量时，p=P，l=L（对这个任务来说）。
2.While( θ=LO )，在每个时刻，选择由具有最高优先级的任务来执行。
3.如果当前正在执行的作业在C（LO）之前没有发出完成信号，则系统进入模式更改周期，则如果某些 LO 任务在临界区内执行，且这个临界区是与HI任务共享的，则 这些任务在退出其关键部分时被丢弃； 当不再有活动的 LO-crit 任务时，系统进入 HI-crit 模式 。
4.一旦( θ=HI或MCP)，具有LO活动关键性的作业立即被丢弃（注：这里给的是l=LO，不是L）。 在每个时刻，选择由具有最高优先级的HI活动关键性任务生成的等待作业来执行（这里给的也是l=HI，不是L）。
5.任务i的活动关键性（l）取决于max（li，CC(Sk）），当任务进入临界区后活动关键性可能随关键性天花板发生变化； 释放后，恢复到锁定前的原始临界值。
6.要进入由信号量Sk保护的临界区，任务i的优先级必须高于dPC（S*）（其实当前任务中优先级，包括天花板优先级最高的，当然这个不包含Sk保护的临界区）。 此外，如果一个较低优先级的任务i持有信号量Sk并阻塞了一个试图锁定的较高优先级的任务j，则i继承j的活动优先级，即pi<-pj。（但其实根据前边的，这个时候Pj=pj，事实上就是正常的优先级继承协议）。
在这里给一点定义活动关键度l的个人理解：
其实这个作用主要体现在MCP阶段，也就是有任务的时长超过C（LO）的使用，利用这个变量去判断低关键性任务是否有的在临界区内，且这个临界区可能会有高关键性任务进入，这部分任务不会立即停止执行，而是执行完毕，直至没有这部分任务，就会进入HI模式。
定理 1：HLC-PCP 确保 HI-crit 任务所需的任何受信号量保护的关键部分将始终执行完成，而不是中止。
文章里没有给出证明，但其实比较容易理解。
由于MSP并不会剥夺正在执行，且动态关键度l=HI的LO任务执行，故而只要LO/HI任务进入到有HI任务需要的shared resource，它就一定会被执行完毕，而不是被终止。
补充：数字越大优先级越大；τ2获取S1的时间为10; τ3的嵌套临界区的最大时间总长度为 25；τ4获取S2的最长时间为10。
T0：任务4释放并开始运行。 由于没有信号量被锁定，系统优先级上限dSPC=0；dPC(S1)=3（active任务为任务2和3） ;dPC(S2)=2（active为任务3和4）.
T10：τ4锁定信号量。 系统优先级上限根据PCP提高，dSPC=dPC(S2)=2；
T15：τ2 和τ3 被释放。 由于τ2 优先级高于τ3和τ4，并且最初不需要临界区，因此抢占并开始运行。
T25：τ2锁定信号量，因为其优先级3超过当前系统优先级上限2，之后系统优先级上限根据PCP 提升至3；τ2活动关键性l2从LO 提升至HI。
T30：τ1释放并抢占。
T50：τ1运行了20 个时间单位，其WCET 估计处于LO-crit 模式，并且尚未完成，因此系统经历从LO 到MCP 的模式变化。
T60：τ1执行完毕，τ2由于活动关键性为HI，则继续执行；
T65：τ2释放信号量； 其活动关键性回落至 LO，根据 AMC 的说法，它会立即中止。 由于不再有 LO-crit 任务处于活动状态，系统进入 HI-crit 模式。 信号量S1的动态优先级上限从 3 下降到 2； 系统优先级上限也下降为2。τ3开始运行（活动优先级比τ4高）。
T75：τ3请求信号量S1。 但即使S1是空闲的，其也会被阻止，因为它的优先级不超过dSPC=2； τ4开始运行并继承τ3活动优先级2。
T80：τ4释放S2； 系统优先级上限降至0，但τ3锁定S1时立即回升至2，
T80 之后：τ3继续运行，锁定并释放其所需的信号量，因为没有其他任务与其争用信号量。
注意：在协议的规则里，选取的一直是活动优先级最高的任务，也就是说倘若一个任务活动优先级为1，进入了优先级为3的临界区，执行了一段时间，一样会被一个活动优先级为2但不需要临界资源的任务抢占，但是这个任务不能进入任何临界区，因为他当前优先级小于活动系统天花板，而后续开始时优先级为1的任务再次执行的时候则会继承优先级为2任务的优先级。
在 MCS 的背景中，阻塞可以分为传统的优先级反转阻塞（pi-阻塞），即由较低优先级任务持有较高优先级任务所需的资源引起的传统阻塞； 或关键性反转阻塞（ci-blocking），LO-crit 任务在模式更改期间持有 HI-crit 任务所需的资源而引起的新阻塞项。
关键性反转阻塞为什么单独定义在模式更改期间，个人的看法：
首先在LO模式下，所有任务都以C（LO）为执行界限，所以无论HI还是LO级别的任务都可以按时完成，这是MCS的一个特性；
而在HI模式下，AMC定义摒弃所有LO任务，事实上倘若有LO任务混进去且所有任务以C（HI）执行会导致有任务错过截止期限，在模式转换期间，还是有LO任务在执行，在这种意义上来讲，这些任务会给高关键性带来阻塞，故而计算这些是有必要的。
对于AMC任务集的可调度性分析，需要检查3种情况：
1）通过计算每个任务的WCRT来验证LO-crit模式的可调度性。 在 LO-crit 模式下，任何任务都可能经历 pi-阻塞。用PBi^(LO)来表示在 LO-crit 模式下可以经历的最大 pi-阻塞时间。
2）通过计算每个HI任务的WCRT来验证HI-crit模式的可调度性。原理与1）类似。用PBi^(HI)来表示在 LO-crit 模式下可以经历的最大 pi-阻塞时间。
3）通过计算每个 HI任务的 WCRT 来验证模式更改期间的可调度性，该任务的作业在 LO-crit 模式或模式更改期间发布，并在 HI-crit 模式或模式更改期间完成，即作业的执行间隔与模式更改周期有一些重叠。 在此期间，任何HI任务都可能会受到HI和LO中任务的 pi 阻塞； 此外，还可以从LO任务中经历 ci 阻塞。我们用PBi^(MCP) ( CBi^(MCP) ) 来表示在模式更改周期内可以经历的最大 pi 阻塞（ci 阻塞）时间。
定义Zi,k表示由信号量Sk保护的任务i的最长关键部分；δi,k表示Zi,k的持续时间。
这里，考虑以LO-crit模式发布并完成的任务
由于任务i最多可以经历一次 pi 阻塞，因此 LO-crit 模式下可以经历的最大 pi 阻塞时间由可以阻塞的最长临界段的长度给出（类似于PCP）。
和PCPbound完全相同。这里参数Zi,k和δi,k的差别就可以理解为Z是找到这个区域，δ是算净时间。
类似的，考虑以HI-crit模式发布并完成的任务
没啥说的，和上一个完全一样。
定义χ表示可能导致任务i产生 ci 阻塞的临界区集
任务i最多被每一个可以对它产生ci阻塞的任务阻塞一次。 故将所有可能导致 ci 阻塞的关键部分中最长关键部分的持续时间相加。
另外，从另一个角度看，任务i最多被每一个有信号量保护的临界区阻塞一次。找到所有可能对它产生阻塞的临界区，将最长关键部分的持续时间相加。
之后这两个取较小的那个即可。
另外，由于在 LO-crit 模式下和模式转换期间，τi可以从lpH（τi）和lpL（τi）遭受pi阻塞；在HI-crit模式，HI-crit任务只能经历来自lpH（τi）任务的pi-blocking所以有：
因此，最大总阻塞时间为公式（13）与（7）相加。
可调度任务集与任务集 CPU 利用率和关键部分长度的百分比。
详情略
