考虑有 n个周期任务的实时任务集 T={ T₁, T₂,…, T_n},一个任务的参数为 T_i=( P_i, C_i, D_i, k_i), P_i是任务 T_i的周期,且相对于截止期限等于其周期, C_i是任务在最大处理器速度和任务没有出错情况下的执行时间, D_i是任务的截止期限, k_i代表能够容忍错误的数量。 T_ij是任务 T_i的第 j次调用。任务是相互独立且在时刻0同时就绪;因此任务 T_ij的就绪时间 r_ij=( j-1) *P_i,它的截止期限 d_ij=j*P_i。

不失一般性,假设任务的周期满足 P₁≤ P₂≤…≤ P_n, U_tot是在最大速度下,任务总的利用率, U_tot = ,用EDF策略调度周期任务的充要条件是 U_tot≤1,本文假设 U_tot = ≤1。

使用文献[9,10]的功耗模型。系统的功耗为:

式中: P_s代表静态功耗,当关闭整个系统时 P_s =0。静态功耗包括(但不限于)基本电路的功耗、维持时钟运行以及主存和I/O设备在睡眠状态的功耗。 P_ind和 P_dep分别代表正在运行的任务 T_i与频率无关的功耗和与频率相关的功耗。与频率无关的组件的功耗是不受CPU频率或者电压变化影响的。任务 T_i使用的主存和I/O设备等功耗都包含在 P_ind里面。 P_dep包括CPU的动态功耗和系统中与频率和电压相关的功耗。 C_ef为有效的负载电容。 m为动态指数(2≤ m≤3)。 S_i为任务 T_i的当前速度。 h代表系统的状态,当系统处于动态模式时, h=1;当系统处于睡眠或者关闭模式时 h=0。由于关闭和打开设备的开销比较大,因此对于实时系统而言,任务在执行过程中将某些组件设置为低功耗的状态,而不是关闭它。

降低CPU的速度可以降低处理器的动态功耗,但处理器速度的降低会延长任务的执行时间,这时系统的静态功耗会增加。文献[9]定义了关键速度 S_crit,关键速度是系统能耗最低的速度。关键速度可以由式(2)求出:

当任务的速度不等于关键速度时,系统的能耗会增加,为了保证系统的实时性,假设任务运行的最低速度应该大于等于 S_crit。

CPU提供离散的频率和电压,即[ f₁, f₂,…, f_max]和[ v₁, v₂,…, v_max],能够提供的速度也是离散的,对频率进行归一化处理, S_min = , S_max = =1,因此其相应的速度为 个离散点。忽略速度转换的一切开销。尽管文献[11]指出由于存储器读写和IO设备的影响,处理器的执行时间与处理器的速度之间不成线性关系,然而这两者之间的具体关系已经超出本文的研究范围。为简单起见,本文假设它们成线性关系,即在速度 S下, T_i的执行时间为 C_i· 。

任务执行期间发生错误的原因很多,例如硬件错误、软件错误、宇宙射线的影响等。本文考虑瞬时错误,因为研究表明发生瞬时错误的概率比永久错误的概率大。假设一个任务在执行期间最多发生 k次错误;当错误发生时使用检查点机制对错误进行恢复,检测错误的开销记录在建立检查点的开销里面,任务在回卷和恢复的过程中不会再发生错误。从图1可以看出,任务有4个等间距的检查点,把任务分成4个部分。当发生错误时,任务回卷到上一个检查点,继续执行。恢复任务的主要作用就是预留时间在任务发生错误时,任务有足够的时间重新执行。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 检查点和回卷恢复Fig.1 Checkpoint and rollback recovery

考虑单个任务,任务的优化的检查点就是确保任务在最坏情况下的执行时间最低,这样就有更多的空闲时间用于节能。任务最坏情况下的执行时间是指任务在执行过程中发生了 k个错误。任务 T_i的最坏情况的执行时间可以表示为:

式中: m_i为检查点的数量; C_io为任务 T_i建立检查点的开销。

本文的目标就是找到恰当的 m_i,在保证任务时限和可靠性的前提下,使得任务 T_i的空闲时间最大(任务最坏情况下的执行时间最小),利用DVS技术节约更多的能耗。

对方程(3)求导,令求导后的方程值为0,求出 m的非负解,可得使空闲时间最大的 m值为:

定义 为任务的优化的检查点数量,函数 F( WCET( m)) =m。

任务 T_i的空闲时间 Slack=D_i-WCET( )。if Slack≥0存在能够容忍 k个错误的等距离检查点,所以在任务 T_i中插入 个检查点。else Slack <0,不存在容忍 k个错误的等距离检查点。

前面已经确定了任务的优化的检查点,这一部分主要是确定使总能耗最低的任务的运行速度。假设系统的所有任务都以相同的速度 S运行。在不发生错误的情况下,任务 T_i插入 检查点的执行时间为 C_i+ C_io,在速度 S下,任务 T_i的执行时间为 ,此时任务 T_i的有效利用率为 。

在发生 k个错误后,为了正确执行任务,在每个时间间隔 P₁预留 k 个单位的空闲时间。接下来的引理证明任务在发生 k个错误后能够在截止期限前顺利完成。令 F_j=C_j/ ,表示任务 T_j恢复执行的时间。

引理1 对于任务集 T={ T₁, T₂,…, T_n},假如 U_tot≤1 - ,利用EDF策略调度的任务将在其周期结束之前 kmax_{1≤ j≤ n}{ F_j}个时间单位完成。

证明 考虑一个修改的任务集,其任务 T_i被任务 取代, 和 T_i有相同的周期,其执行时间为 C_i+kmax_{1≤ j≤ n}{ F_j}。因为 P₁≤ P_i,新的任务集的利用率 U_tot + ≤1,因此在EDF调度的任务集中所有的任务都在其周期结束之前完成。假如 的执行时间为 C_i+kmax_{1≤ j≤ n}{ F_j}而不是 C_i,它将在其周期结束之前 kmax_{1≤ j≤ n}{ F_j}个时间单位完成。对于任何的1≤ i≤ n,上述结论都成立,所以引理得证。

系统在无错情况下的运行速度为 S,当出现错误时,恢复任务以最高处理器速度运行,因此插入检查点后系统的利用率为:

为了充分利用系统的空闲时间,设置系统的利用率为1,求出速度:

假如由式(6)求出的速度 S小于关键速度 S_crit,这时 S=S_crit。

由于处理器提供的频率和电压是离散的,为了确保任务不错过截止期限,本文提出两种速度选择策略,第一种策略(H_SPEED)每个任务选择的速度都大于或等于速度 S。第二种策略(A_SPEED)^{[ 12]}是任务以相邻的速度运行,任务的执行时间划分为两部分。通过速度 S确定第一部分的速度和第二部分的速度,并且利用速度 S下的执行时间计算出第一部分的执行时间。待第一部分执行完成,根据剩余执行时间完成第二部分。

H_SPEED

{ select speed from ;

Return the first speed greater than or equal S;}

定义速度 S_L、 S_H且满足 S_crit≤ S_L<S≤ S_H。在速度 S_L、 S_H下相应的频率和电压分别为 和 。定义 C'_{i, I}是在理想速度 S下任务 T_i的执行时间, R_i是任务 T_i的剩余执行时间,开始时 R_i=C'_{i, I}; C'_i.L和 C'_i.H是任务 T_i在速度 S_L和 S_H下的执行时间。它们满足关系式:

为了保持任务的运行时间,于是有关系式:

由式(7)(8)可以计算出:

A_SPEED

{ //任务 T_i在无错和最高处理器速度的执行时间为 C_i+ C_o

对于任务 T_i,1≤ i≤ n;

根据 S选择 S_L和 S_H;

选择速度 S_L执行任务;

//计算任务在 S_L下的执行时间

t_trig =t+( D_i-t)( S_H-S) /( S_H-S_L)

SetTimer( t_trig);//给任务的执行设一个计时器

SetTimer( t)

Set Timer to be triggered at t;

On Trigger()

R_i=R_i-S_L( t-l)// l代表先前时刻 t

If( R_i>0)

Then 速度 S_H执行。}

为了保证系统的可靠性、实时性,同时尽可能降低系统的功耗,提出了基于检查点机制的容错节能调度算法(CPFTES)。该算法使用EDF调度策略,在任务调度前,插入检查点到任务中,当错误发生时,任务回卷到最近的检查点,重新执行任务。利用DVS技术调节任务的运行速度,降低系统的能耗。

CPFTES Algorithm

1.For each T_i in T, do {

1.1 Calculate for each T_i;

1.2 Calculate Slack;

1.3 if Slack0;

Return exist equidistant checkpoint;

1.4 Calculate F_i;}

2 Calculate speed S;

3 Select speed policy

(H_SPEED OR A_SPEED).

1.1~1.3计算每个任务优化的检查点的数量,同时判断是否存在优化的检查点。1.4计算每个任务的恢复时间间隔。第2步计算任务的运行速度。第3歩选择速度策略,确定任务最终的运行速度。CPFTES算法的计算时间主要消耗在确定优化的检查点上,因此时间复杂度为 O( n)。

从图2可以看出,在错误数量一定时,检查点开销增加,优化的检查点的数量降低。检查点的开销越大任务的执行时间就越长,这时可以降低检查点的数量。因为添加过多的检查点,任务就有可能错过截止期限。错误的数量增加,优化的检查点数量随之增加。增加检查点,减少了检查点之间的间距,有利于错误的恢复。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 检查点开销对优化的检查点数量的影响Fig.2 Overheads of checkpoint vs number of optimal checkpoint

仿真实验比较了CPFTES算法的3种策略,第一种策略(CPFTES_NODVS)没有采用DVS技术,任务始终以最大的处理器速度运行;第二种策(CPFTES_H_SPEED)任务的运行速度大于或等于连续频率计算出来的速度 S;第三种策略(CPFTES_A_SPEED)任务以相邻的速度运行。图3和图4分别是CPFTES算法在PXA250处理器和TM5800处理器上的仿真结果。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 PXA250处理器运行结果Fig.3 Running results of PXA250 processor

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 TM580处理器运行结果Fig.4 Running results of TM580 processor

从图3和图4都可以看出,CPFTES_A_SPEED的能耗始终低于CPFTES_H_SPEED的能耗。随着任务集利用率的增加,CPFTES_A_SPEED和CPFTES_H_SPEED的能耗随之增加。图3中任务集所消耗的能耗比图4任务集消耗的能耗大,这主要是因为TM5800处理器比PXA处理器提供的速度多;任务集在TM5800运行时,实际的运行速度更接近计算出来的理想速度 S。在任务集的利用率小于0.3时,CPFTES_A_SPEED和CPFTES_H_SPEED的能耗几乎相同,这是因为任务集的利用率低时,所计算出的理想速度 S小于关键速度 S_crit,两种策略的运行速度都设定为关键速度 S_crit。从图3可以看出,CPFTES_A_SPEED比CPFTES_H_SPEED节约0~19.41%的能耗,CPFTES_A_SPEED比CPFTES_NODVS平均节约66.18%的能耗。从图4可以看出CPFTES_A_SPEED比CPFTES_H_SPEED节约0~28.15%的能耗,CPFTES_A_SPEED比CPFTES_NODVS平均节约74.95%的能耗。仿真实验表明CPFTES_A_SPEED始终比CPFTES_H_SPEED节能;任务集在TM5800上运行的能耗低于在PXA250上运行的能耗。