资源受限周期任务双速度调度算法

张忆文，吴文江，郭锐锋

1(中国科学院 沈阳计算技术研究所，沈阳 110168) 2(华侨大学 计算机科学与技术学院，福建 厦门 361021)

1 引 言

实时系统已经广泛应用于工业控制、航空航天、通信等行业.实时系统按照任务释放实例的特点，可以将任务划分为周期任务、偶发任务和混合任务等.随着技术的发展，实时系统的能耗越来越高，已经成为系统发展的瓶颈.动态电压调节技术[1]根据系统的实时负载，通过动态调节处理器速度，降低处理器能耗，是解决系统能耗问题的重要技术.

文献[1-6]将实时调度理论与动态电压调节技术结合起来，降低系统能耗.但这些工作都假设任务之间是相互独立，没有考虑任务之间的共享资源问题.事实上，在实时系统中，任务之间由于共享资源而存在相互依赖关系.文献[7,8]研究了任务的资源共享问题，但这些研究主要针对偶发任务模型.针对周期任务模型的资源共享问题的研究相对较少.文献[9,10]通过利用动态优先级策略调度周期任务，且所有任务在执行过程中都以单一的速度执行.这些研究工作不能适用于采用固定优先级调度策略的系统，且节能效果差.

针对现有基于动态优先级策略资源受限周期任务能耗优化算法不能适用于固定优先级系统，且节能效果差等不足，提出RCPTDSSA.该算法基于RM/DPP算法，使用双速度策略调度任务，利用动态电压调节技术降低能耗.任务开始以低速度执行，当有阻塞发生时切换到高速度执行，且被阻塞的任务也以高速度执行.

2 系统模型

2.1 任务模型

2.2 处理器模型和能耗模型

P=Ps+h(Pind+CefSm)

(1)

3 双优先级单调速率调度算法

文献[7,8]提出了RM/DPP算法，该算法基于RM策略，利用抢占阈值的思想，通过设置任务的优先级，确保资源互斥访问.在RM/DPP算法中，每个周期任务Ti有两个优先级：初始优先级(IPi)和执行优先级(EPi).初始优先级根据RM策略进行分配，任务的周期越小，其优先级就越高，反之，其优先级越低.执行优先级是在任务开始执行时分配.

先通过一个实例解释RM/DPP算法.考虑有3个周期任务的任务集，其具体信息如下：

T1(1，1，4)，T2(1，0，5)，T3(3，1，20)

该任务集的系统利用Utot=0.6，周期任务T1与周期任务T3共享资源R1，周期任务T2没有资源需求.假设所有的周期任务都在时刻0释放其任务实例.在区间[0，20]利用RM/DPP算法调度该周期任务集.周期任务T1、T2以及T3的初始优先级分别为3，2，1.使用共享资源R1的所有周期任务的最大初始优先级π1=3.在时刻0，周期任务T1、T2以及T3同时释放实例，周期任务T1的初始优先级最高，其最先执行，且在时刻1完成执行.在时刻2，周期任务T2完成执行.在时刻2，周期任务T3开始执行，由于其共享资源R1，所以其执行优先级被修改为3.尽管在时刻4，周期任务T1释放实例，但其初始优先级不大于周期任务T3的执行优先级，所以不能抢占其执行，也就是说周期任务T1被周期任务T3阻塞.其他任务以相似的方法调度.RM/DPP算法调度周期任务集的最终结果如图1所示.

图1 RM/DPP算法调度周期任务集Fig.1 RM/DPP algorithm schedules the periodic task set

从图1可以看出，RM/DPP算法调度任务始终以最大的处理器速度执行，造成很多空闲间隔如[7，8]、[9，10]、[11，12]、[13，15]以及[17，20]，浪费了系统资源.接下来提出节能效果更好的RCPTDSSA算法.

4 RCPTDSSA算法

4.1 准备工作

4.2 计算SL和SH

定理1[12].RM算法调度具有n个相互独立周期任务的周期任务集是可行，其必须满足以下条件：

Utot≤LLB(n)

(2)

根据定理1，SL可以通过下式计算；

(3)

定理2[13]. 基于RM调度策略的算法调度具有n个资源受限周期任务的周期任务集是可行，其必须满足以下条件：

(4)

根据定理2，SH可以通过下式计算；

(5)

4.3 RCPTDSSA算法描述

所提出的RCPTDSSA算法基于RM/DPP算法，周期任务在执行时没有阻塞发生，其以低速度SL执行，发生阻塞时其以高速度SH执行，直到完成执行，且被阻塞的周期任务也以高速度SH执行.

算法1.RCPTDSSA算法

1) 计算低速度SL和高速度SH；

2) 当SL

3) 当SL>SH，SH=SL；// 确保高速度不低于低速度

4) 当SH>1.0，SH=1.0； //确保高速度不超过处理器提供的最大速度.

5) 当周期任务Ti释放一个实例，根据RM策略将其插入到就绪队列；

6) 周期任务Ti开始以低速度SL执行，且修改其执行优先级；

7) 当周期任务Ti阻塞周期任务Tk的执行时，周期任务Ti以高速度SH执行，直到其完成执行；此时，周期任务Tk也以高速度SH执行，直到其完成执行.

RCPTDSSA算法的时间复杂度主要由计算低速度SL和高速度SH以及RM/DPP算法调度任务两部分组成.计算低速度SL和高速度SH的时间复杂度分别为O(n)和O(n2)；而RM/DPP算法调度任务的时间复杂度为O(nlogn).因此，RCPTDSSA算法的时间复杂度为O(n2).

4.4 RCPTDSSA算法实例

在证明RCPTDSSA算法可行性之前，先介绍几个引理.

图2 RCPTDSSA算法调度周期任务集Fig.2 RCPTDSSA algorithm schedules the periodic task set

(6)

证明：参见文献[13].

∃t∈U={mpi|i=1，…，k；m=1，…，⎣pk/pi」}，则下式成立：

(7)

证明：参见文献[13].

定理3.周期任务集T按照其周期进行非降序排序，共享m个连续可重用资源的资源集合R={R1，R2，…，Rm}，其假设周期任务的相对截止期限等于其周期；RCPTDSSA算法以低速度SL和高速度SH调度该周期任务集是可行的充分条件为：∀k，1≤k≤n，∃ta，tb∈U={mpi|i=1，…，k；m=1，…，⎣pk/pi」，公式(8)和公式(9)成立.

(8)

(9)

证明：反证法.假设存在一个任务错过其截止期限.当t″不存在时，其值设置为t″=0.因此，在区间[t″，t′]不存在空闲时间.区间[t″，t′]的任务可以分为两种情形.第一种情形，任务实例释放时刻不早于t″且初始优先级比任务Ti高的集合，用β表示.第二种情形，处理器在时刻t″之前处于空闲状态或者存在一个初始优先级任务比任务Ti的初始优先级低的任务，且在其在时刻t″已经占有共享资源，该任务用Tk表示.

第一种情形：在区间[t″，t′]没有阻塞发生.

第一种情形只有集合β中的任务在区间[t″，t′]以低速度SL执行.在区间[t″，t′]的处理器需求Dt″，t′由下式给出：

(10)

由于存在任务在时刻t′错过其截止期限.因此，下式成立.

(11)

令t=t′-t″，经过变换可知：

(12)

这与公式(6)矛盾.

第二种情形：在区间[t″，t′]发生阻塞.

第二种情形假设任务Tj是时刻t″之前已经开始执行，且假设任务Tk在区间[t″，t′]被任务Tj阻塞.显然，任务Tk是集合β中初始优先级最高的任务.任务Tk的截止期限以及其被任务Tj阻塞的时刻分别用td和th表示.任务Tj开始以低速度SL执行.在时刻th，任务Tj以高速度SH执行直到其完成执行.当任务Tj完成执行，任务Tk以高速度完成执行.因此，在区间[t″，t′]的处理器需求可以分为三部分：

由于存在任务在时刻t′错过其截止期限，因此下式成立：

(13)

根据引理1，且经过不等式变换，可以得出：

(14)

进而推出：

(15)

令t=td-th，则下式成立：

(16)

这与公式(7)矛盾.因此，定理得证.

推论1.周期任务集T按照其周期进行非降序排序，共享m个连续可重用资源的资源集合R={R1，R2,…，Rm}，其假设周期任务的相对截止期限等于其周期；RCPTDSSA算法以低速度SL和高速度SH调度该周期任务集是可行的充分条件为：SL和SH分别满足公式(3)和公式(5).

证明：直接由引理1、引理2以及定理3得出.

5 仿真实验

为了评价算法的性能，利用C语言实现一个基于RM策略的周期任务调度仿真器.该仿真器采用文献[9]的功耗模型.P=0.08+1.52S3，处理器处于空闲状态的功耗为0.085，关键速度Scrit=0.3.在仿真器中实现RM/DPP算法和RCPTDSSA算法.以数控系统的任务集为研究对象[2]，该任务集由8个周期任务组成.每个周期任务Ti的周期在区间[2.4，9.6]中随机选择，其相应的最坏情况下的执行时间在0.035到其周期之间随机选择.随机选择4个任务作为有资源需求的任务，其余任务没有资源需求.实验的仿真时间设置为100000个时间单位，重复实验100次，取平均值作为最后的实验结果.

考察系统利用率对算法能耗的影响，系统利用率的范围设置为0.15到0.65，步长设置为0.05.以RM/DPP算法在系统利用为0.65的能耗为基准进行归一化.实验的结果如图3所示.

图3 系统利用率对算法能耗的影响Fig.3 System utilization effects on the algorithm energy consumption

从图3可以看出，RCPTDSSA算法和RM/DPP算法的能耗依赖于系统利用率.当系统利用率上升时，RCPTDSSA算法和RM/DPP算法的能耗上升.这是因为随着系统利用率上升，任务的执行时间变长，而RM/DPP算法始终以最大的处理器速度执行，其能耗增加.而对于RCPTDSSA算法，系统率增加，不仅任务的执行时间增加，而且任务执行的低速度和高速度也增加，因此，其能耗也增加.此外，当系统利用率低于0.3时，RCPTDSSA算法能够节约更多能耗，这是因为RCPTDSSA算法此时能够以关键速度执行，所以其节约的能耗更多.当系统利用率大于0.3，RCPTDSSA算法能够节约的能耗降低，这是因为系统利用率增加，RCPTDSSA算法的执行速度增加，所消耗的能耗也增加，节约的能耗变少.从图中还可以看出，无论系统利用率如何变化，RCPTDSSA算法的归一化能耗都低于RM/DPP算法的归一化能耗.通过计算可知，RCPTDSSA算法比RM/DPP算法节约大约55.31%的能耗.

6 结 论

针对现有基于动态优先级策略资源受限周期任务能耗优化算法不能适用于固定优先级系统，且节能效果差等不足，提出RCPTDSSA算法.该算法基于RM/DPP算法，使用双速度策略调度任务.任务开始以低速度执行，当有阻塞发生时切换到高速度执行，且被阻塞的任务也以高速度执行.利用理论分析的手段验证RCPTDSSA算法的可行性，仿真实验表明RCPTDSSA算法比RM/DPP算法节约大约55.31%的能耗.由于RCPTDSSA算法假设任务以最坏情况下执行时间执行以及任务的执行时间与处理器速度成线性关系，且忽略处理器速度转化开销等不足，接下来将研究能够回收动态空闲时间，且考虑处理器速度切换开销以及任务执行时间与处理器速度成非线性关系的资源受限周期任务能耗优化算法.