基于概率性分析的混合关键级系统节能调度算法

冒 航,张凤登,陆 禹,朱嘉炜

(上海理工大学 光电信息与计算机工程学院,上海 200093)

随着计算机技术的发展,实时系统得到了广泛应用,嵌入式实时系统的复杂度也不断提升。将不同重要性的任务或功能整合到一个平台上工作成为一个趋势,这样虽可以进一步节约成本和减少能耗,但导致了混合关键级系统(Mixed Criticality System,MCS)的出现[1]。混合关键级系统主要应用于安全关键领域,例如汽车电子、航空航天等领域。汽车的刹车不能实时控制制动、飞机不能有效控制转向和航速等问题将会产生灾难性的后果,这些任务称为安全关键级任务[2]。当资源配置不足或安全关键任务需要更多资源时,可以暂时合理放弃某些非安全关键任务,以确保安全关键任务的实时性和正确性,这也是混合关键级系统进行资源调度的显著特征。

目前,对混合关键级系统的研究已经从功能方面逐步深入到非功能方面,例如制约该类系统进一步发展的能耗问题[3]。由于混合关键级系统的实时性要求使得系统建模和分析偏向于较坏的情况,所以容易存在资源配置过度问题。因此,对混合关键级系统的节能问题进行研究具有重要的现实意义。

本文对混合关键级系统中存在的固定优先级任务节能问题进行研究,提出了基于概率性分析的混合关键级系统节能调度算法。该算法创新性地将概率性分析方法引入了系统的响应时间分析,通过将DVFS技术和混合关键级系统调度算法相结合挖掘空闲时间,从而在保证系统实时性的前提下降低系统的能耗。

1 模型介绍及理论基础

1.1 任务模型

1)Ti表示任务的周期;

4)pETi是任务的概率分布函数,表示任务在某个时间段内完成的概率值;

5)Li表示任务的关键级别。Li∈{L,H},其中L表示低关键级任务,H表示高关键级任务。

1.2 概率模型

对于具有概率执行时间的任务,需要概率模型来进行可调度性分析。文献[4～5]对实时系统的概率性分析进行了描述分析,本文的概率模型以此为基础进行了总结分析。概率模型是对任务的执行时间进行概率性分析,所以该模型是基于时间的离散概率模型。

本文中任务τi的概率分布函数为pETi,该函数是一个3×n的矩阵,并且与fi概率质量函数[6](Pro-bability Mass Function,PMF)[6]和Fi累积分布函数(Cumulative Distribution Function,CDF)[7]有关。pETi具体定义如下

(1)

其中,n是任务执行时间可能性的个数,为提高概率模型的可读性,通常假设c1

1.3 能耗模型

本文考虑在单处理器上运行混合关键级任务。只要系统的CPU(Central Processing Unit)支持DVFS技术,则CPU的频率可以在任务运行时进行调整。本文采用的功率模型为[8]

(2)

本文采用DVFS以减少动态功耗从而达到降低总功耗的目的,该策略主要是探索更多的空闲时间来达到预期能耗的最小化。

假设1处理器的频率范围为[fmin,fmax],系统以频率fb为基本频率运行,并且fmin≤fb≤fmax,该值是系统正常运行时的频率值,也就是未使用DVFS策略时的频率。

假设2当处理器在频率为fmax运行时,此时其处理器的速度值SH=1。因此,处理器按比例在频率为f运行时,其处理器的相对速度值为f/fmax。

2 算法设计

2.1 算法描述

本文算法的目的是在混合关键级系统的实时约束下,满足系统安全性的同时使得系统任务的能耗最小化。本文提出了基于概率性分析的混合关键级系统节能调度算法来解决周期性非抢占固定优先级任务的高功耗问题。该算法使用基于松弛时间的DVFS分析方法,充分挖掘任务的实际完成时间与截止时间之间的差值来降低处理器频率。

(3)

本文提出概率性分析的节能调度算法有助于获得平均最小能耗的调度表,同时满足系统任务的实时性要求。概率信息仅用于对平均能耗的计算以及能耗最小化,对系统的可调度性没有影响。伪代码如下所示。

算法1 基于概率性分析的混合关键级系统节能调度算法输入:MCS周期任务集Γ={τ1,τ2,…,τn};输出:任务调度表。1Begin:2input Γ=τ1,τ2…,τn /*输入任务集*/3for τi from 1 to n4 for pL→H from(pL→H)min to (pL→H)max5 CLi=F-1i(pL→H) /*计算任务执行时间*/6 if Ri≤Di then7 SL←Smin /*选择最小处理器速度*/8 end if9 Calcu(Eε ) /*计算单个任务平均能耗*/10 end for11 ∑ni=1Calcu(Eε ) /*计算任务集平均能耗*/12end for13end

该算法的可调度性通过确定任务的WCET来保证,分析流程可以分为以下几步:

(4)

2)内部优化:该部分主要是计算最小的SL。为确保系统可调度性,本文进行了基于最大响应时间的分析,从而得出在满足可调度性的条件下处理器速度的最小值。根据处理器的速度值SL可得到作业的输出时间表,该时间调度表作为能耗估算的输入在外部优化中使用。

3)能耗比较:在以上流程完成后,通过将系统平均能耗进行比较可得出平均能耗最小值以及最佳的SL和pL→H。

2.2 可调度性分析

本文使用最大响应时间分析方法。该方法先计算任务的最大响应时间Ri,如果任务的最大响应时间小于其截止期Di,则该任务可以被调度。如果任务集中的任务都可以被调度,则该系统可调度并且安全,其算法分析流程如图1所示。

图1 可调度性分析流程Figure 1. Flow of schedulability analysis

从任务到达时刻直至任务执行完成的时刻,这段时间间隔称为响应时间。文献[13～14]提出了较先进的非抢占固定优先级调度的响应时间分析方法。非抢占固定优先级的最坏响应时间Ri具体计算如下所示

(5)

其中,Bi是由较低优先级任务引起的最大阻塞时间;Ci是任务τi执行所产生的时间;Nj是优先级高于任务τi的干扰作业数;Cj是任务τj执行所产生的时间;Bi的计算式如下所示

(6)

其中,对于混合关键级系统来说,lp(i)是优先级低于任务τi的一组任务集;hep(i)代表优先级高于任务τi的一组任务集;Nj是较高优先级任务的干扰作业数量,计算式如下所示。

(7)

情况1任务τi在低关键级模式下的最坏响应时间分析

(8)

(9)

Ri=Bi+Ci+Ii

(10)

情况2对于高关键级任务τi在高关键级模式下运行完成,其最坏响应时间如下所示。

(11)

(12)

(13)

(14)

(15)

情况3由任务τi发布的作业在经历模式转换后其最坏响应时间计算如下所示

(16)

在模式的切换之前,任务τi以速度SL执行,发生模式切换后任务以速度SH执行,则该任务执行时间Ci的计算式所示。

(17)

任务τi只在低关键级模式下受到任务τj的干扰,干扰时间Ii的计算方法如下

(18)

所以在经历转换时间的情况下的任务的最大响应时间的计算如式(19)所示。

(19)

2.3 能耗计算

基于上述的高关键级作业概率数,可推导出作业执行时间的概率质量函数。其具体计算式为

(20)

(21)

3 实验及结果分析

3.1 实验平台搭建

混合关键级系统调度仿真软件(MCSIMU)主要由任务输入模块、节能调度算法调度模块以及输出模块3部分组成,在该仿真软件中需要对一些优化算法以插件的形式插入系统内核,该算法需要在内核当中重新进行编译,在标准任务集正确调度的基础上进行系统开销测试实验,对存在的异常问题进行算法插件的修正,以保证插入算法的正确性,其算法验证过程如图2所示。

图2 调度算法验证过程Figure 2. Scheduling algorithm verification process

本文的节能调度算法作为软件运行插件实现,即在内核当中加入一个新的调度器,主要根据需求实现具体的调度算法,维护相关数据结构。采用任务控制块(Task Control Block,TCB)[15]来实现对任务调度参数以及任务运行状况的保存,其任务调度过程如图3所示。

图3 任务产生及调度过程Figure 3. Task generation and scheduling process

本实验借鉴了文献[16～18]的实验操作步骤与方法。首先在随机任务集上进行可调度分析系统,对于任务集的生成采用UUnifast算法,有利于分析任务利用率与任务集中任务数量之间的关系。其仿真实验参数设定如下:

1)系统利用率U=[0.4,1.0];

2)任务间释放的时间间隔Td= [6,60];

3)任务高关键级模式下的WCET与低关键级模式下的WCET之比Z=[1∶4]和Z=[1∶8];

4)高关键级任务的概率值CP=[0.1,0.9],默认为0.5。

3.2 结果及分析

在低关键级模式下不同处理器速度可调度性对比如图4所示。

图4 低关键级模式下不同处理器速度可调度性对比(a)WCET之比为1∶4时的可调度性对比 (b)WCET之比为1∶8时的可调度性对比Figure 4. Comparison of different processor speed schedulability in low critical mode(a)Schedulability comparison when the ratio of WCET is 1∶4 (b)Schedulability comparison when the ratio of WCET is 1∶8

图4(a)和图4(b)只有在高关键级模式下最坏执行时间(WCET)与在低关键级模式下最坏执行时间比值Z的取值范围不同,其他参数均相同。图4反应了任务集可调度性随着系统利用率增加的趋势。任务可调度性随着系统利用率的增加而降低。在系统利用率接近1时,此时大多数的任务集变得不可调度。在系统利用率较低时,大多数任务集可调度。在本文仿真实验中,由于一开始就固定了低关键级模式下处理器的速度值SLO,故实验结果对可调度性造成了一定的负面影响。由图4(a)和图4(b)对比可知,低关键级模式下的最坏执行时间较少,可使得任务相对较早进入高关键级模式,相对而言其可调度性也有一定提高。

本文实验对7组任务集进行能耗的最小化分析。该实验的系统平均利用率为0.4,固定优先级的分配算法为RM(Rate Monotonic)算法。如图5所示,热力图的形式展示了任务集中pL→H从0.05～0.50的节能情况,实验结果进行了可视化分析使得节能效果简单直观。在实际系统中,利用本文提出的方法,根据系统所处的工作模式,在满足任务实时性的前提下,动态地调节处理器的工作频率或者供电电压,当电压或者频率降低时,处理器耗降低以立方级减少,从而使系统的功耗也显著降低。

图5 不同模式转换概率值下任务集的节能效果Figure 5. Energy-saving effect of task set under different mode conversion probability values

在图5中,节能效果以颜色深浅来显示,小方块的灰度值越大或颜色越深代表其节能效果越好。通过颜色对比分析和能耗计算可为任务集求得最小的能耗值以及相应的设置参数。任务集1～7节能效果的最优参数设置如表1所示。

表1 实验任务集以及相应最优实验参数Table 1. Set of experimental tasks and corresponding optimal experimental parameters

与上述实验相类似,通过改变系统的利用率进行2 000个任务集的模拟仿真实验。通过该算法得到的最优能耗值与随机选择而得到的能耗值进行比较,结果显示本文算法的平均能耗降低大约10%。与未进行节能调度的能耗值即该任务集中频率一直为最大值相比,平均能耗约降低45%。

4 结束语

本文提出了一种基于概率性分析的混合关键级系统节能调度算法,创新性地将概率性分析方法引入最坏响应时间分析,考虑了系统任务实时性和能耗最小化之间的平衡,由概率性分析方法获得处理器能耗最小化的速度或者频率值,最终获得相对最小化的平均能耗。本文对其进行理论证明,并通过对比实验验证了该算法的有效性。 实验结果表明,与未使用节能调度算法相比,其节能效果高达45%。但是本文研究针对系统节能调度算法主要是动态功耗的降低从而达到系统能耗降低的目的。随着处理器尺寸的越来越小,静态功耗问题也不容忽视,在未来研究中可以进一步将静态功耗的影响也考虑在内,使得系统能耗进一步降低。