一种非抢占固定优先级混合关键任务能耗优化调度方法与流程

本发明涉及混合关键系统技术领域，更具体地说，涉及一种非抢占固定优先级混合关键任务能耗优化调度方法。

背景技术：

混合关键系统是指不同的软件组件和不同的关键层次的应用集合在同一个平台上。混合关键系统的工业标准，例如飞机的软件标准就包含5个关键层次a、b、c、d、e，其中，关键层次a代表最高的关键等级，如果a关键层次的任务没有及时完成执行，会导致致命性灾难的发生；关键层次e代表最低的关键层次，其任务不能按时完成执行，不会威胁到飞机的飞行安全，但会降低用户的体验。无人机就是属于混合关键系统的典型应用，由于重量、体积与空间的限制，能耗是设计无人机的必须考虑的目标。

针对混合关键系统的能耗研究的现有技术，主要采用抢占性的调度策略。由于抢占性调度策略，会导致上下文切换频繁发生，无形中增加了系统的抢占开销；此外，抢占性调度方法不够灵活，无法预测任务的调度过程，时间复杂度高等。因此，提出系统开销小，时间复杂度低，非抢占性能耗优化方法。

技术实现要素：

本发明的目的在于克服现有技术的不足，提供一种非抢占固定优先级混合关键任务能耗优化调度方法，系统开销小，时间复杂度低，非抢占性能耗。

本发明的技术方案如下：

一种非抢占固定优先级混合关键任务能耗优化调度方法，步骤如下：

1)建立非抢占固定优先级混合关键任务调度模型；

2)设置系统处于低模式下调度可行的充分条件、系统处于高模式下调度可行的充分条件、设置系统处于转换模式调度可行的充分条件；

3)基于步骤2)设置的调度可行的充分条件，计算能耗优化的速度sop。

作为优选，步骤1)具体如下：

混合关键任务调度模型由n个混合关键周期任务组成的集合γ＝{τ1,τ2,…,τn}，每个混合关键周期任务τi由四元组{ti,di,ξi,ci}组成，1≤i≤n；其中，

ti表示混合关键周期任务τi的周期；

di表示混合关键周期任务τi的相对截止期限，且其等于ti；

ξi表示混合关键周期任务τi的关键层次，且ξi＝{lo,hi}，当混合关键周期任务τi的关键层次为lo时，其为低关键层次任务，当混合关键周期任务τi的关键层次为hi时，其为高关键层次任务；

ci表示混合关键周期任务τi的不同模式下的最坏情况下执行时间；对应的，ci(lo)和ci(hi)分别表示混合关键周期任务τi在低模式和高模式下的执行时间；

所述的低模式是指作为高关键层次任务的混合关键周期任务τi完成执行时，其执行时间不超过ci(lo)；所述的高模式是指作为高关键层次任务的混合关键周期任务τi完成执行时，其执行时间不超过ci(lo)但不超过ci(hi)；所述的转换模式是指混合关键周期任务τi的执行时间超过ci(lo)但其没有完成执行；如果混合关键周期任务τi为低关键层次任务，则ci(hi)＝ci(lo)；如果混合关键周期任务τi为高关键层次任务，则ci(hi)≥ci(lo)。

作为优选，混合关键周期任务组成的集合γ由非抢占固定优先级调度策略调度；其中，非抢占固定优先级策略是指混合关键周期任务一旦开始执行，不会被优先级比其高的混合关键周期任务抢占，高优先级的混合关键周期任务只有等当前混合关键周期任务完成执行后，才可以执行；固定优先级是指混合关键周期任务在调度之前分配优先级，优先级一旦分配，其在执行过程中保持不变。

作为优选，采用单调速率策略分配任务的优先级，当混合关键周期任务τi的周期越小，其优先级越高；当混合关键周期任务τi的周期越大，其优先级越高；当混合关键周期任务τi的周期相同时，到达时间越早的优先越高，到达时间越晚的其优先级越低；当混合关键周期任务τi的周期和达到时间都相同时，下标i小的混合关键周期任务τi，其优先级越高，下标i大的混合关键周期任务τi，其优先级越低。

作为优选，步骤2)中，设置系统处于低模式下调度可行的充分条件，包括：

混合关键周期任务τi在低模式下的响应时间具体如下：

其中，是混合关键周期任务τi在低模式下被优先级比其低的混合关键周期任务阻塞的时间，ci(lo)和cj(lo)分别是混合关键周期任务τi和τj在低模式下最坏情况下的执行时间，slo是低模式下的执行速度，是在响应时间内混合关键周期任务τj在低模式下的释放的作业数量，hep(i)是优先级比混合关键周期任务τi高的任务集合；

系统处于低模式下调度可行的充分条件，具体如下：

其中，di是混合关键周期任务τi的相对截止期限；

设置系统处于高模式下调度可行的充分条件，包括：

混合关键周期任务τi在高模式下的响应时间具体如下：

其中，是混合关键周期任务τi在高模式下被优先级比其低的混合关键周期任务阻塞的时间，ci(hi)和cj(hi)分别是混合关键周期任务τi和τj在高模式下最坏情况下的执行时间，shi是高模式下的执行速度，是在响应时间内混合关键周期任务τj在高模式下的释放的作业数量；

系统处于高模式下调度可行的充分条件，具体如下：

设置系统处于转换模式调度可行的充分条件，包括：

混合关键周期任务τi在转换模式下的响应时间具体如下：

其中，是混合关键周期任务τi开启转换模式的响应时间，是除了混合关键周期任务τi以外的其他作为高关键层次任务的混合关键周期任务τi开启转换模式的响应时间；

系统处于转换模式下调度可行的充分条件，具体如下：

作为优选，混合关键周期任务τi在低模式下被优先级比其低的混合关键周期任务阻塞的时间具体如下：

其中，lp(i)是优先级比混合关键周期任务τi低的任务集合；

在响应时间内混合关键周期任务τj在低模式下的释放的作业数量具体如下：

作为优选，混合关键周期任务τi在高模式下被优先级比其低的混合关键周期任务阻塞的时间具体如下：

其中，和分别是转换模式开始时和进入高模式后作为高关键层次任务的混合关键周期任务τi被阻塞的时间，具体如下：

其中，ck(lo)和ck(hi)分别表示作为高关键层次任务的混合关键周期任务τi在低模式和高模式下的最坏情况下执行时间；lph(i)是优先级比混合关键周期任务τi低的作为高关键层次任务的混合关键周期任务τi的集合；

在响应时间内混合关键周期任务τj在高模式下的释放的作业数量具体如下：

作为优选，混合关键周期任务τi开启转换模式的响应时间具体如下：

除了混合关键周期任务τi以外的其他作为高关键层次任务的混合关键周期任务τi开启转换模式的响应时间具体如下：

其中，ii是混合关键周期任务τi执行过程中被干涉的时间上限，具体如下：

作为优选，步骤3)具体如下：

设置shi＝1，当系统处于低模式时，所有混合关键周期任务τi以能耗优化的速度sop执行；当系统处于高模式时，低关键层次任务被丢弃，作为高关键层次任务的混合关键周期任务τi以速度shi＝1执行。

作为优选，能耗优化的速度sop，具体如下：

设置分别计算低模式、高模式、转换模式下的执行速度slo，将其最大的取值作为能耗优化的速度sop的值。

本发明的有益效果如下：

本发明所述的非抢占固定优先级混合关键任务能耗优化调度方法，与现有技术的混合关键系统周期任务调度方法相比，能够节约大约33.08％能耗；能够确保周期任务在其截止期限内完成执行；混合关键系统能耗的降低，可以降低产品的生产成本，延长设备的使用时间，减少电池的更换周期。

附图说明

图1是本发明的流程图示意图。

具体实施方式

以下结合附图及实施例对本发明进行进一步的详细说明。

本发明提供一种非抢占固定优先级混合关键任务能耗优化调度方法，如图1所示，步骤如下：

1)建立非抢占固定优先级混合关键任务调度模型；

2)设置系统处于低模式下调度可行的充分条件、系统处于高模式下调度可行的充分条件、设置系统处于转换模式调度可行的充分条件；

3)基于步骤2)设置的调度可行的充分条件，计算能耗优化的速度sop。

步骤1)具体如下：

混合关键任务调度模型由n个混合关键周期任务组成的集合γ＝{τ1,τ2,…,τn}，每个混合关键周期任务τi由四元组{ti,di,ξi,ci}组成，1≤i≤n；其中，ti表示混合关键周期任务τi的周期；di表示混合关键周期任务τi的相对截止期限，且其等于ti；ξi表示混合关键周期任务τi的关键层次，且ξi＝{lo,hi}，当混合关键周期任务τi的关键层次为lo时，其为低关键层次任务，当混合关键周期任务τi的关键层次为hi时，其为高关键层次任务；ci表示混合关键周期任务τi的不同模式下的最坏情况下执行时间；对应的，ci(lo)和ci(hi)分别表示混合关键周期任务τi在低模式和高模式下的执行时间。

所述的低模式是指作为高关键层次任务的混合关键周期任务τi完成执行时，其执行时间不超过ci(lo)；所述的高模式是指作为高关键层次任务的混合关键周期任务τi完成执行时，其执行时间不超过ci(lo)但不超过ci(hi)；所述的转换模式是指混合关键周期任务τi的执行时间超过ci(lo)但其没有完成执行；如果混合关键周期任务τi为低关键层次任务，则ci(hi)＝ci(lo)；如果混合关键周期任务τi为高关键层次任务，则ci(hi)≥ci(lo)。

混合关键周期任务组成的集合γ由非抢占固定优先级调度策略调度；其中，非抢占固定优先级策略是指混合关键周期任务一旦开始执行，不会被优先级比其高的混合关键周期任务抢占，高优先级的混合关键周期任务只有等当前混合关键周期任务完成执行后，才可以执行；固定优先级是指混合关键周期任务在调度之前分配优先级，优先级一旦分配，其在执行过程中保持不变。

本发明采用单调速率策略分配任务的优先级，当混合关键周期任务τi的周期越小，其优先级越高；当混合关键周期任务τi的周期越大，其优先级越高；当混合关键周期任务τi的周期相同时，到达时间越早的优先越高，到达时间越晚的其优先级越低；当混合关键周期任务τi的周期和达到时间都相同时，下标i小的混合关键周期任务τi，其优先级越高，下标i大的混合关键周期任务τi，其优先级越低。

步骤2)具体如下：

2.1)设置系统处于低模式下调度可行的充分条件，包括：

混合关键周期任务τi在低模式下的响应时间具体如下：

其中，是混合关键周期任务τi在低模式下被优先级比其低的混合关键周期任务阻塞的时间，ci(lo)和cj(lo)分别是混合关键周期任务τi和τj在低模式下最坏情况下的执行时间，slo是低模式下的执行速度，是在响应时间内混合关键周期任务τj在低模式下的释放的作业数量，hep(i)是优先级比混合关键周期任务τi高的任务集合。

混合关键周期任务τi在低模式下被优先级比其低的混合关键周期任务阻塞的时间具体如下：

其中，lp(i)是优先级比混合关键周期任务τi低的任务集合；

在响应时间内混合关键周期任务τj在低模式下的释放的作业数量具体如下：

系统处于低模式下调度可行的充分条件，具体如下：

其中，di是混合关键周期任务τi的相对截止期限。

2.2)设置系统处于高模式下调度可行的充分条件，包括：

混合关键周期任务τi在高模式下的响应时间具体如下：

其中，是混合关键周期任务τi在高模式下被优先级比其低的混合关键周期任务阻塞的时间，ci(hi)和cj(hi)分别是混合关键周期任务τi和τj在高模式下最坏情况下的执行时间，shi是高模式下的执行速度，是在响应时间内混合关键周期任务τj在高模式下的释放的作业数量；hep(i)是优先级比混合关键周期任务τi高的任务集合。

混合关键周期任务τi在高模式下被优先级比其低的混合关键周期任务阻塞的时间具体如下：

其中，和分别是转换模式开始时和进入高模式后作为高关键层次任务的混合关键周期任务τi被阻塞的时间，具体如下：

其中，ck(lo)和ck(hi)分别表示作为高关键层次任务的混合关键周期任务τi在低模式和高模式下的最坏情况下执行时间；lph(i)是优先级比混合关键周期任务τi低的作为高关键层次任务的混合关键周期任务τi的集合。

在响应时间内混合关键周期任务τj在高模式下的释放的作业数量具体如下：

系统处于高模式下调度可行的充分条件，具体如下：

其中，di是混合关键周期任务τi的相对截止期限。

2.3)设置系统处于转换模式调度可行的充分条件，包括：

混合关键周期任务τi在转换模式下的响应时间具体如下：

其中，是混合关键周期任务τi开启转换模式的响应时间，是除了混合关键周期任务τi以外的其他作为高关键层次任务的混合关键周期任务τi开启转换模式的响应时间。

混合关键周期任务τi开启转换模式的响应时间具体如下：

除了混合关键周期任务τi以外的其他作为高关键层次任务的混合关键周期任务τi开启转换模式的响应时间具体如下：

其中，ci(lo)和cj(lo)分别是混合关键周期任务τi和τj在低模式下最坏情况下的执行时间，slo是低模式下的执行速度，是在响应时间内混合关键周期任务τj在低模式下的释放的作业数量，ci(hi)是混合关键周期任务τi在高模式下最坏情况下的执行时间，shi是高模式下的执行速度，lp(i)是优先级比混合关键周期任务τi低的任务集合，hep(i)是优先级比混合关键周期任务τi高的任务集合；ii是混合关键周期任务τi执行过程中被干涉的时间上限，具体如下：

系统处于转换模式下调度可行的充分条件，具体如下：

其中，di是混合关键周期任务τi的相对截止期限。

步骤3)具体如下：

为了确保作为高关键层次任务的混合关键周期任务τi尽早的完成执行，设置shi＝1，进而，能耗优化的速度sop可基于步骤2)获得，具体如下：

设置分别计算低模式、高模式、转换模式下的执行速度slo，将其最大的取值作为能耗优化的速度sop的值。

当系统处于低模式时，所有混合关键周期任务τi以能耗优化的速度sop执行；当系统处于高模式时，低关键层次任务被丢弃，作为高关键层次任务的混合关键周期任务τi以速度shi＝1执行。

本实施例中，混合周期任务集γ＝{τ1,τ2,τ3,τ4}包含4个周期任务。

混合关键周期任务τ1的周期t1等于20，其相对截止期限为20，关键层次ξ1为hi，即其为高关键层次任务，其低关键层次模式最坏情况下执行时间c1(lo)为2；其高关键层次模式最坏情况下执行时间c1(hi)为4。

混合关键周期任务τ2的周期t2等于40，其相对截止期限为40，关键层次ξ2为lo，即其为低关键层次任务，其低关键层次模式最坏情况下执行时间c2(lo)为4；其高关键层次模式最坏情况下执行时间c2(hi)为4。

混合关键周期任务τ3的周期t3等于10，其相对截止期限为10，关键层次ξ3为hi，即其为高关键层次任务，其低关键层次模式最坏情况下执行时间c3(lo)为1；其高关键层次模式最坏情况下执行时间c3(hi)为2。

混合关键周期任务τ4的周期t4等于15，其相对截止期限为15，关键层次ξ4为lo，即其为低关键层次任务，其低关键层次模式最坏情况下执行时间c4(lo)为3；其高关键层次模式最坏情况下执行时间c4(hi)为3。

通过计算可知，能耗优化速度sop＝0.6，在区间[0,50]内调度该任务集，将本发明与没有采用动态电压频率调节方法相比较节约大约33.08％的能耗。

上述实施例仅是用来说明本发明，而并非用作对本发明的限定。只要是依据本发明的技术实质，对上述实施例进行变化、变型等都将落在本发明的权利要求的范围内。

技术特征：

1.一种非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，步骤如下：

1)建立非抢占固定优先级混合关键任务调度模型；

2)设置系统处于低模式下调度可行的充分条件、系统处于高模式下调度可行的充分条件、设置系统处于转换模式调度可行的充分条件；

3)基于步骤2)设置的调度可行的充分条件，计算能耗优化的速度sop。

2.根据权利要求1所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，步骤1)具体如下：

混合关键任务调度模型由n个混合关键周期任务组成的集合γ＝{τ1,τ2,…,τn}，每个混合关键周期任务τi由四元组{ti,di,ξi,ci}组成，1≤i≤n；其中，

ti表示混合关键周期任务τi的周期；

di表示混合关键周期任务τi的相对截止期限，且其等于ti；

ξi表示混合关键周期任务τi的关键层次，且ξi＝{lo,hi}，当混合关键周期任务τi的关键层次为lo时，其为低关键层次任务，当混合关键周期任务τi的关键层次为hi时，其为高关键层次任务；

ci表示混合关键周期任务τi的不同模式下的最坏情况下执行时间；对应的，ci(lo)和ci(hi)分别表示混合关键周期任务τi在低模式和高模式下的执行时间；

所述的低模式是指作为高关键层次任务的混合关键周期任务τi完成执行时，其执行时间不超过ci(lo)；所述的高模式是指作为高关键层次任务的混合关键周期任务τi完成执行时，其执行时间不超过ci(lo)但不超过ci(hi)；所述的转换模式是指混合关键周期任务τi的执行时间超过ci(lo)但其没有完成执行；如果混合关键周期任务τi为低关键层次任务，则ci(hi)＝ci(lo)；如果混合关键周期任务τi为高关键层次任务，则ci(hi)≥ci(lo)。

3.根据权利要求2所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，混合关键周期任务组成的集合γ由非抢占固定优先级调度策略调度；其中，非抢占固定优先级策略是指混合关键周期任务一旦开始执行，不会被优先级比其高的混合关键周期任务抢占，高优先级的混合关键周期任务只有等当前混合关键周期任务完成执行后，才可以执行；固定优先级是指混合关键周期任务在调度之前分配优先级，优先级一旦分配，其在执行过程中保持不变。

4.根据权利要求3所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，采用单调速率策略分配任务的优先级，当混合关键周期任务τi的周期越小，其优先级越高；当混合关键周期任务τi的周期越大，其优先级越高；当混合关键周期任务τi的周期相同时，到达时间越早的优先越高，到达时间越晚的其优先级越低；当混合关键周期任务τi的周期和达到时间都相同时，下标i小的混合关键周期任务τi，其优先级越高，下标i大的混合关键周期任务τi，其优先级越低。

5.根据权利要求1至4任一项所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，步骤2)中，设置系统处于低模式下调度可行的充分条件，包括：

混合关键周期任务τi在低模式下的响应时间具体如下：

其中，是混合关键周期任务τi在低模式下被优先级比其低的混合关键周期任务阻塞的时间，ci(lo)和cj(lo)分别是混合关键周期任务τi和τj在低模式下最坏情况下的执行时间，slo是低模式下的执行速度，是在响应时间内混合关键周期任务τj在低模式下的释放的作业数量，hep(i)是优先级比混合关键周期任务τi高的任务集合；

系统处于低模式下调度可行的充分条件，具体如下：

其中，di是混合关键周期任务τi的相对截止期限；

设置系统处于高模式下调度可行的充分条件，包括：

混合关键周期任务τi在高模式下的响应时间具体如下：

其中，是混合关键周期任务τi在高模式下被优先级比其低的混合关键周期任务阻塞的时间，ci(hi)和cj(hi)分别是混合关键周期任务τi和τj在高模式下最坏情况下的执行时间，shi是高模式下的执行速度，是在响应时间内混合关键周期任务τj在高模式下的释放的作业数量；

系统处于高模式下调度可行的充分条件，具体如下：

设置系统处于转换模式调度可行的充分条件，包括：

混合关键周期任务τi在转换模式下的响应时间具体如下：

其中，是混合关键周期任务τi开启转换模式的响应时间，是除了混合关键周期任务τi以外的其他作为高关键层次任务的混合关键周期任务τi开启转换模式的响应时间；

系统处于转换模式下调度可行的充分条件，具体如下：

6.根据权利要求5所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，混合关键周期任务τi在低模式下被优先级比其低的混合关键周期任务阻塞的时间具体如下：

其中，ck(lo)分别是混合关键周期任务τk在低模式下最坏情况下的执行时间，lp(i)是优先级比混合关键周期任务τi低的任务集合；

在响应时间内混合关键周期任务τj在低模式下的释放的作业数量具体如下：

7.根据权利要求6所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，混合关键周期任务τi在高模式下被优先级比其低的混合关键周期任务阻塞的时间具体如下：

其中，和分别是转换模式开始时和进入高模式后作为高关键层次任务的混合关键周期任务τi被阻塞的时间，具体如下：

其中，ck(lo)和ck(hi)分别表示作为高关键层次任务的混合关键周期任务τi任务在低模式和高模式下的最坏情况下执行时间；lph(i)是优先级比混合关键周期任务τi低的作为高关键层次任务的混合关键周期任务τi的集合；

在响应时间内混合关键周期任务τj在高模式下的释放的作业数量具体如下：

8.根据权利要求7所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，混合关键周期任务τi开启转换模式的响应时间具体如下：

除了混合关键周期任务τi以外的其他作为高关键层次任务的混合关键周期任务τi开启转换模式的响应时间具体如下：

其中，ii是混合关键周期任务τi执行过程中被干涉的时间上限，具体如下：

9.根据权利要求6至8任一项所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，步骤3)具体如下：

设置shi＝1，当系统处于低模式时，所有混合关键周期任务τi以能耗优化的速度sop执行；当系统处于高模式时，低关键层次任务被丢弃，作为高关键层次任务的混合关键周期任务τi以速度shi＝1执行。

10.根据权利要求9所述的非抢占固定优先级混合关键任务能耗优化调度方法，其特征在于，能耗优化的速度sop，具体如下：

设置分别计算低模式、高模式、转换模式下的执行速度slo，将其最大的取值作为能耗优化的速度sop的值。

技术总结
本发明涉及一种非抢占固定优先级混合关键任务能耗优化调度方法，包括以下步骤:建立非抢占固定优先级混合关键任务调度模型；给出系统处于低模式下调度可行的充分条件；给出系统处于高模式下调度可行的充分条件；给出系统处于转换模式调度可行的充分条件；由调度可行的充分条件，计算能耗优化的速度Sop。本发明与现有技术的混合关键系统周期任务调度方法相比，能够节约大约33.08％能耗；能够确保周期任务在其截止期限内完成执行；混合关键系统能耗的降低，可以降低产品的生产成本，延长设备的使用时间，减少电池的更换周期。

技术研发人员：张忆文;陈雁;潘玉彪
受保护的技术使用者：华侨大学
技术研发日：2020.11.30
技术公布日：2021.03.12