一种基于区域划分的嵌入式节能调度方法

摘要

本发明公开了一种基于区域划分的嵌入式节能调度方法，包括如下步骤：采用任务实例修订方法对待调度的任务集进行修订；根据任务运行周期及任务集的利用率，为每个任务设置执行阈值；根据执行阈值进行任务调度：当任务的周期区间与垛区间的重叠区域的长度大于任务的执行阈值，则调度该任务使之在当前的垛区间中完成；否则，将该任务调度到下一个垛区间中执行；本发明提供的这种调调方法，将系统中小的空闲时间片段合并，以增加空闲时间片段的平均长度，进而获得足够长的空闲时间用于完成嵌入式处理器的休眠状态转换，从而有效降低处理器的工作负载以达到节能目的。

说明书

技术领域

本发明属于嵌入式实时系统任务调度领域，更具体地，涉及一种基于区域划分的嵌入式节能调度方法。

背景技术

嵌入式移动终端己经逐渐融入人们生活，大多数嵌入式设备通常以固定电量的锂电池等作为电源供电而非直流供电，而其应用背景也限制了嵌入式设备随时充电的可能性。低能耗已然成为决定嵌入式系统价值的重要性能指标。完成相同任务能耗更少，则可以极大延长嵌入式移动设备的单次充电使用时间，对提高用户体验和发挥嵌入式设备实际使用价值都具有极其重要的作用。

嵌入式系统中运行的应用任务需要满足执行时间限制，必须在预先给定的截止期之前完成，如何有效平衡实时性调度及节能调度之间的关系是嵌入式实时计算领域的研究重点。现有的嵌入式系统的节能管理有ERHS(Energy-saving Rate HharmonizedSchedulers)和DVFS(Dynamic Voltage and Frequency Scaling)两种典型技术。

ERHS是在速率单调调度的基础上发展起来的，任务的优先级按截止时间来分配，截止时间短的任务优先级高，截至时间长的任务优先级低；缺陷在于仅以任务的周期来决定优先级容易导致某些周期较小但非常重要的任务错过截止期而无法调度的问题。

DVFS是通过调节处理器的执行频率来降低处理器的动态能耗，处理器的执行频率随着作用在处理器上的片载电压变化而变化，而处理器的速度越慢，处理器的动态能耗越少；利用DVFS技术能够调整处理器频率进行节能，但降低处理器速率的弊端是造成实时任务执行时间的增加，从而导致静态能耗增加。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于区域划分的嵌入式节能调度方法，其目的在于降低嵌入式实时处理器的静态能耗。

为实现上述目的，按照本发明的一个方面，提供了一种基于区域划分的嵌入式节能调度方法，包括如下步骤：

(1)对待调度的任务集进行修订，以缩短任务集中所有任务的周期与任务的工作量；

(2)根据任务运行周期及任务集的利用率，对修订后的每个任务设置执行阈值；所述执行阈值的小于任务实例周期的1/3；

(3)根据所述执行阈值进行任务调度：当任务的周期区间与垛区间(Crenel-Interval，CI)的重叠区域的长度大于任务的执行阈值，则调度该任务使之在当前的垛区间中完成；否则，将该任务调度到下一个垛区间中执行；

其中，CI是通过对调度序列进行区间划分而形成的形状类似垛的划分区间，CI的两端为Crenel-Point(CP)；对于单个CI，任务被调度到CI的两端执行，从而使得CI的中间区域具有较长的空闲时间片段用于处理器状态转换。

优选地，上述基于区域划分的嵌入式节能调度方法，其步骤(3)包括如下子步骤：

(3.1)获取任务的最坏完成时刻t_j；

(3.2)比较任务的预估完成时间与最坏完成时间，当预估完成时间大于最坏完成时间，则进入步骤(3.3)；

当预估完成时间等于最坏完成时间，则进入步骤(3.4)；

当预估完成时间小于最坏完成时间，则进入步骤(3.5)；

(3.3)根据任务执行所需的时间判断任务是否可延期处理，若是，则进入步骤(3.4)；若否，则进入步骤(3.6)；

(3.4)将任务加入到延时任务集，并进入步骤(3.7)；

(3.5)判断预估剩余时间是否大于所述执行阈值，若是，则进入步骤(3.4)；若否，则进入步骤(3.6)；

(3.6)增加可执行任务总和，并进入步骤(3.7)；

(3.7)获取任务的起始时间点。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够获得以下有益效果：

(1)本发明提供的基于区域划分的嵌入式节能调度方法，通过执行阈值进行任务调度，部分任务实例被推迟执行，将系统中小的空闲时间片段合并，从而确保每个CI中最多只有一个连续的空闲时间片段；通过增加空闲时间片段的平均长度，以获得足够长的空闲时间用于完成嵌入式处理器的休眠状态转换，同时保证嵌入式系统实时任务调度满足周期性及截止期的约束，从而有效降低处理器的工作负载以达到节能目的；

(2)本发明提供的基于区域划分的嵌入式节能调度方法，对调度序列进行区间划分，并在划分后的区间中调度任务集，可以简化调度的复杂性；而另一方面，其调度序列划分的CI个数越少，整个调度过程中的空闲时间片段的长度越长；当系统中的空闲时间片段平均长度越长，系统中能够用于节能的空闲时间片段越多，其节能效果也越好；

相比较而言，现有技术的DVFS方法，虽然能够降低动态能耗，但是处理器的静态功耗却在增加；而本发明通过将更多的空闲时间片段集中，形成大的空闲时间段以用于将处理器转换为低能耗状态，而低能耗状态下的静态功耗也会降低，由此起到节能的效果；

现有技术的ERHS方法，最小周期长度越小的任务被调度的可能性越小；随着任务集的利用率的增大，ERHS的可调度验证条件越不容易满足；而本发明提供的这种调度方法则没有这些限制，所有的任务集都可以被调度，可适用更多的周期性任务集。

附图说明

图1为实施例提供的基于区域划分的嵌入式节能调度方法的流程示意图；

图2实施例中的任务分配步骤的流程示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

实施例中提供的基于区域划分的嵌入式节能调度方法的流程如图1所示意的，包括如下步骤：

(1)对待调度的任务集进行修订，以缩短任务集中所有任务的周期与任务的工作量；

(2)根据任务运行周期及任务集的利用率，对修订后的每个任务设置执行阈值；该执行阈值小于任务实例周期的1/3；

(3)根据所述执行阈值进行任务调度：当任务的周期区间与CI的重叠区域的长度大于任务的执行阈值，则调度该任务使之在当前的垛区间中完成；否则，将该任务调度到下一个垛区间中执行。

通过对任务集τ'＝{τ'₁,...τ'_n}进行修订，将其转换为τ＝{τ₁,...τ_n}；将该任务集中较长的任务转换为较短的任务(将任务的周期和任务的工作量同时缩短相应的倍数)，从而保证整个任务集的最终利用率保持不变；

转换后的任务集中，任务的周期截止时间任务的利用率

转换获得的任务集中的任务的周期都满足条件：T₁≤T_i≤2T₁(1≤i≤n)；

其中，C'_i是指任务集τ'的最坏执行时间；T'_i是任务集τ'的周期；T₁是指任务实例τ₁的周期，是周期转换的倍数，i是指任务的编号，n是指任务集的任务实例的数量；

根据执行阈值进行任务调度，计算任务τ中所有可选任务开始执行的时刻点，其流程如图2所示，具体如下

(1)计算任务的预估的最坏执行时间t_j；

(2)判断每个任务是否能在区间CI_j中执行，具体如下：

(a)如果任务τ_i的预估执行时间小于其最坏执行时间t_j；则进一步比较预估执行时间与执行阈值UT_i的大小；若预估执行时间大，则判定任务实例τ_i为拟推迟执行的实例，否则，判定实例τ_i为强制任务，应在当前垛区间CI_j中执行；记录可执行任务需要执行的总时间；

(b)如果任务τ_i的预估执行时间等于其最坏执行时间t_j；则判定该任务τ_i为可延迟执行的任务；

(c)如果任务τ_i的预估执行时间大于其最坏执行时间t_j，则进一步判断该任务是否为可延迟任务；若该任务实例不可延迟，则必须在CI_j中执行；若任务为可延迟任务，则将该实例延迟到下个垛区间CI_j+1中执行；

获取所有可选任务开始执行的时刻点δ＝t_j-SumOptional；其中，SumOptional是指在对区间CI_j屮需要执行的所有可选任务的工作量的总和。

实施例中，采用形如(C_i，D_i，T_i)的三元组来量化描述任务；其中，C_i是指任务τ_i在最大的处理器频率下的最坏执行时间，D_i和T_i分别是指任务的相对截止期和周期长度；采用τ_i,j表示任务集τ_i的第j个任务实例。

对于任务集中的可选任务实例如果满足则将调度在当前的垛区间C_j中执行，并且使得该可选任务实例在时间点t_j之前完成；否则，则将可选任务实例调度到下一个垛区间C_j+1的起始处执行；实施例中，每个垛区间的周期长度为20ms。

对于实施例中的如下周期任务的任务集：τ₁＝(1,10,10)，τ₂＝(6,16,16)(单位为ms)；为每个任务集τ_i设置一个执行闽值U*T_i；U为任务集的利用率；根据执行阈值判断可选任务实例是否延迟执行；

具体地，首先计算获取整个任务集的利用率U＝1/10+6/16＝0.47；

然后判断任务实例是否被推迟，由于任务实例τ_2,2在时刻点16释放，并且其截止期在t₁时刻点之后，因此，判定任务实例τ_2,2在CI₁中为可选实例；由于其预估的执行时间L₁(τ_2,2)＝4＜0.475*16＝7.52，将任务实例τ_2,2推迟到下一个垛区间CI₂中执行；

其中，强制任务实例是指必须在指定CI内执行的任务，可选任务实例是指可被延迟到下一个CI内执行的任务。

在垛区间CI₂中，任务实例τ_2,2为强制实例，必须在该垛区间内完成；对于垛区间CI₂而言，任务实例τ_2,3为可选任务实例，该任务的预估的执行时间L₂(τ_2,3)＝8＞0.47*16＝7.52，任务τ_2,3必须在垛区间CI₂中完成。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。