一种基于动态电压调节技术的可靠性低功耗调度方法

摘要

本发明涉及一种基于动态电压调节技术的可靠性低功耗调度方法。本发明在任务集调度之前，计算资源限制的周期任务集的最小运行速度ST；任务Ti在调度时，计算出任务Ti的执行截止期限EDi，利用修改的最早截止期限调度策略调度任务；选出要缩放速度的任务；计算任务Ti的静态空闲时间SST，回收任务提早完成产生的空闲时间以及预留给恢复任务没有使用的时间(DST)；当任务可利用的空闲时间大于其最坏情况下的执行时间时，调节任务Ti的运行速度；否则任务Ti以最大的处理器速度运行。本发明不仅能够回收任务的静态空闲时间和任务提早完成产生的空闲时间，而且能够利用预留给恢复任务没有使用的时间，比现有算法节约2.21％～30.52％的能耗且系统可靠性得到大大的提升。

说明书

技术领域

本发明涉及实时系统领域资源限制周期任务的实时调度，具体的说是一种基于动态电压调节技术的可靠性低功耗调度方法。

背景技术

对于关键安全的实时系统而言，实时性和可靠性是其基本特征。它要求系统能够在规定的时间内完成任务的执行，而且在系统出现错误时，还能够确保任务的正确执行。目前用于确保系统可靠性的方法通常是采用容错的手段，也就是系统发生错误时，能够及时的捕捉到错误，而且还能够预留出足够的时间，确保发生的错误的任务能够重新执行。

目前常用主副版本技术和基于检查点的回卷恢复技术来实现容错。所谓的主副版本技术是指任务在执行过程中有两个版本，一个为主版本，一个为副版本；任务先执行主版本，任务顺利执行时，撤销其副版本；当任务执行失败时，执行副版本；这样能够确保任务顺利的执行。所谓的检查点回卷恢复技术是指在任务调度之前插入一定数量的检查点，通过错误检测技术，检测到错误后，任务从最近的检查点恢复执行。

目前常用动态电压调节(DVS)技术来降低系统能耗。DVS技术是在保证系统性能的前提下，利用空闲时间调节处理器的运行速度以达到降低能耗的目的。现有的可靠性低功耗调度算法，利用检查点机制确保系统可靠性，也就是当任务在执行过程中发生错后时，重新执行出错的任务。但这些可靠性低功耗调度算法只针对相互独立的周期任务模型，没有考虑周期任务之间的资源共享问题且忽略了速度对系统可靠性造成的影响。

发明内容

针对现有可靠性低功耗调度算法的不足之处，本发明要解决的技术问题是提供一种基于动态电压调节技术的可靠性低功耗调度方法，既考虑了处理器的动态功耗，也考虑了处理器的静态功耗；既能够回收任务的静态空闲时间，又能够回收任务提早完成产生的空闲时间以及预留给恢复任务没有使用的时间；且利用DVS技术降低系统能耗。

本发明为实现上述目的所采用的技术方案是：一种基于动态电压调节技术的可靠性低功耗调度方法，包括以下步骤：

计算资源限制的周期任务集的最小运行速度S_T；

任务T_i在调度时，计算出任务T_i的执行截止期限ED_i，利用修改的最早截止期限调度策略调度任务；

在周期任务集中选出要缩放速度的任务；

计算任务T_i的静态空闲时间SST，回收任务提早完成产生的空闲时间与预留给恢复任务没有使用的时间之和DST；

当任务可利用的空闲时间大于其最坏情况下的执行时间时，调节任务T_i的运行速度；否则任务T_i以最大的处理器速度运行。

所述资源限制的周期任务集的最小运行速度为：

S_T＝LS_RT+S_NRT

其中，LS_RT为所有有资源需求的任务的最小运行速度中的最大值，S_NRT为没有资源需求任务的最小运行速度。

所述任务T_i的执行截止期限的计算方法为：

其中，t_ri为任务T_i的释放时刻，p_i为任务T_i的周期，t_si为任务T_i的开始执行时刻，P_i为所有共享资源R_i的任务的最小周期。

所述选出要缩放速度的任务的方法如下：

以周期任务集中周期最小的任务作为要缩放速度的任务；当周期最小的任务数大于1时，随机选择其中一个任务作为要缩放速度的任务。

所述任务T_i的静态空闲时间SST为：

SST＝(1-S_T)*(ED_i-t_b)

其中，S_T为资源限制的周期任务集的最小运行速度，ED_i为任务T_i的执行截止期限，t_b为任务T_i的释放时刻。

所述回收任务提早完成产生的空闲时间与预留给恢复任务没有使用的时间之和DST为：

其中，rem_i为任务T_i的剩余执行时间，w_i为任务T_i的最坏情况下的剩余执行时间，e_i为任务T_i最坏情况下的执行时间，x_i表示任务能否执行成功，当任务顺利完成时，x_i＝1；否则x_i＝0；n代表周期任务集中任务的数量。

所述调节任务T_i的运行速度，具体为：

设置任务T_i的运行速度为：

其中，SST为任务T_i的静态空闲时间，DST为回收任务提早完成产生的空闲时间与预留给恢复任务没有使用的时间之和，rem_i为任务T_i的剩余执行时间，w_i为任务T_i的最坏情况下的剩余执行时间，e_i为任务T_i最坏情况下的执行时间。

本发明具有以下优点及有益效果：

1.采用本发明方法，既能够回收任务的静态空闲时间，又能够回收任务提早完成产生的空闲时间以及预留给恢复任务没有使用的时间；从而比现有的可靠性低功耗调度方法节约2.21％～30.52％的能耗。

2.采用本发明的方法，系统的出错率为现有方法的2.11E-5倍，系统出错率大大降低，系统可靠性得到大大的提升。

3.系统能耗的降低，可以降低产品的生产成本，有助于提高企业的竞争力。

附图说明

图1为本发明方法处理步骤流程图；

图2为归一化能耗与系统利用率的仿真实验结果图；

图3为出错概率与系统利用率的仿真实验结果图。

具体实施方式

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

参见附图1，是一种基于动态电压调节技术的可靠性低功耗调度方法，包括如下步骤：

在任务集调度之前，计算资源限制的周期任务集的最小运行速度S_T；任务T_i在调度时，计算出任务T_i的执行截止期限ED_i，利用修改的最早截止期限调度策略调度任务；选出要缩放速度的任务；计算任务T_i的静态空闲时间SST，回收任务提早完成产生的空闲时间以及预留给恢复任务没有使用的时间之和DST；当任务可利用的空闲时间大于其最坏情况下的执行时间时，调节任务T_i的运行速度；否则任务T_i以最大的处理器速度运行。

对本发明进一步说明：

在任务集调度之前，计算资源限制的周期任务集的最小运行速度S_T；其处理步骤如下：

资源限制的周期任务集T被划分为两个子集：有资源需求的任务集合用RT和没有资源需求的任务集合NRT。在集合NRT中任务没有资源的需求，其最小的运行速度S_NRT由下式给出：

其中u_i表示任务T_i的利用率；

有资源需求的任务T_i的最小运行速度为S_RT(i)由下式计算：

其中表示共享资源的任务的最小周期，p_i表示任务T_i的周期，L是实数；e_i表示任务T_i的最坏情况下的执行时间，e_j任务T_j的最坏情况下的执行时间；p_j表示任务T_j的周期；

所有有资源需求的任务的最小运行速度LS_RT，其值可以由下式计算：

其中，r_i代表任务T_i的资源需求，n代表任务集任务的个数；

因此，资源限制的周期任务集T的最小运行速度S_T可以由下式给出：

S_T＝LS_RT+S_NRT

其中，LS_RT为所有有资源需求的任务的最小运行速度，S_NRT为没有资源需求任务的最小运行速度。

任务T_i在调度时，计算出任务T_i的执行截止期限ED_i，利用修改的最早截止期限调度策略调度任务；其处理步骤如下：

使用修改的最早截止期限调度策略时，每个任务T_i具有两个截止期限：初始截止期限(ID_i)和执行截止期限(ED_i)；ID_i是根据EDF调度策略分配的截止期限；而ED_i是任务被调度执行时分配的截止期限；任务始终根据EDF调度策略进行调度，也就是说截止期限越近，它的优先级就越高，优先级高的任务优先调度；任务刚释放时，执行截止期限等于其初始截止期限，EDF策略始终根据执行截止期限进行调度；对于没有资源需求的任务而言，其执行截止期限始终等于其初始截止期限；而对于有资源需求的任务而言，其初始截止期限和执行截止期限的计算方法如下：

对于周期任务T_i它的释放时刻用t_ri表示，开始执行时刻用t_si表示。则其初始截止期限ID_i＝t_ri+p_i，其执行截止期限其中P_i为所有共享资源R_i的周期任务的最小周期，其值为

选出要缩放速度的任务；其处理步骤如下：

将任务集中周期最短的任务选为缩放任务，当任务的周期相同时，下标小的任务作为缩放任务。

计算任务T_i的静态空闲时间SST，回收任务提早完成产生的空闲时间以及预留给恢复任务没有使用的时间(DST)；其处理步骤如下：

对于周期任务T_i的每一个调度周期，其静态空闲时间SST可以通过下式计算：

SST＝(1-S_T)*(ED_i-t_b)

式中ED_i是缩放周期任务T_i的执行截止期限，t_b是周期任务T_i的释放时刻；任务提早完成产生的空闲时间以及预留给恢复任务没有使用的时间(DST)由下式计算：

其中，rem_i为任务T_i的剩余执行时间，w_i为任务T_i的最坏情况下的剩余执行时间，e_i为任务T_i最坏情况下的执行时间，x_i表示任务能否执行成功，当任务顺利完成时，x_i＝1；否则x_i＝0；n代表周期任务集中任务的数量。

当任务T_i可利用的空闲时间大于其最坏情况下的执行时间时，也就是SST+DST>e_i；这时构建任务T_i的恢复任务，其恢复任务的执行时间为e_i；剩余的空闲时间SST+DST-e_i用来调节处理器的运行速度；此时任务T_i的运行速度设置为其中，SST为任务T_i的静态空闲时间，DST为任务提前完成的产生的空闲时间以及预留给恢复任务没有使用的时间，rem_i为任务T_i的剩余执行时间，w_i为任务T_i的最坏情况下的剩余执行时间，e_i为任务T_i最坏情况下的执行时间；

当任务T_i可利用的空闲时间小于或等于其最坏情况下的执行时间时，也就是SST+DST≤e_i；任务T_i以最大的处理器速度运行。

图2设置任务的WCET与BCET的比值为5，系统利用率为0.1到0.8，考察系统利用率对系统能耗的影响。在图2中比较了五种方法，第一，EDF/DDM，该方法所有的任务都以最大处理器速度执行；第二，SLPSR，该方法基于EDF/DDM，且所有的任务都以资源限制的周期任务集的最小运行速度S_T执行，但其忽略了速度对系统可靠性的影响。第三，LPF；该方法考虑了速度对系统可靠性的影响，且最长周期任务被选为缩放任务；但其假设任务以其最坏情况下的执行时间执行；第四，SPF，该方法考虑了速度对系统可靠性的影响，且最短周期任务被选为缩放任务；但其假设任务以其最坏情况下的执行时间执行；第五，本发明的方法，该方法不仅考虑了速度对系统可靠性的影响，能够回收任务提早完成所产生的空闲时间，以及预留给恢复任务没有使用的时间；在改善系统可靠性的同时进一步降低系统能耗。从图2可以看出，所有方法的归一化能耗随着系统利用率的增加而增加。这是因为系统利用率越大，任务的执行时间将延长，所以其能耗自然而然就增加。SLPSR的归一化能耗都低于其他方法，这是因为它将所有的静态空闲时间都用于降低能耗，而忽略了速度对系统可靠性的影响。而本发明方法的归一化能耗低于EDF/DDM、SPF以及LPF的能耗。这是因为该方法法能够利用动态空闲时间以及预留给恢复任务的时间来降低处理器能耗。总之，本发明方法与SPF和LPF相比分别节约2.21％～30.52％和大约18.16％的能耗。

图3设置任务的WCET与BCET的比值为5，系统利用率为0.1到0.8，考察系统利用率对出错概率的影响。图3中所比较的方法和图2的相同。从图3中可以看出，除了SLPSR之外，其他方法的出错概率都受到系统利用率的影响。当系统利用率低于关键速度(S_crit＝0.3)时，SLPSR的出错概率升高；这是因为任务的速度受到关键速度的限制，而其执行时间增加。当系统利用率大于0.3时，SLPSR的出错概率降低。这是因为系统利用率越高，可以用来降低处理器速度的静态空闲时间减少。此外注意到SPF和LPF的出错概率均低于EDF/DDM。总之，SLPSR的出错概率是EDF/DDM算法的28.04倍，而LPF的出错概率低于EDF/DDM，是它的0.89倍。此外，本发明方法的出错概率远远低于EDF/DDM，是它的2.11E-5倍。