一种基于混合任务集的高能效调度算法

夏 军

（重庆邮电大学 移动通信工程研究中心，重庆400065）

随着便携式与移动实时设备市场的快速发展，减少系统能耗并扩展电池的使用时间成为嵌入式便携/移动设备设计能否商用化的重要衡量准则。动态电压调整DVS（Dynamic Voltage Scaling）技术被广泛应用于低功耗设计领域，它通过降低系统的电压或者频率的方式来平衡系统性能与功耗。在低功耗设计中，DVS利用电压与动态功耗的平方比关系，通过改变电压与频率使得系统在满足性能的同时又能使系统能耗明显减少。

DVS调度算法早期主要集中于时间间隔调度器的研究，这些算法主要是通过系统的全局性状态来设置相应的电压（频率），并不考虑实际运行的用户程序状态流程。近年来的研究主要集中于基于线程电压（频率）调度器的研究[1]。这些调度算法基于周期性任务集的模型中需要考虑单个线程或者任务的参数，比如时限、运行时间、启动时刻。

除了通用实时系统，还有一些学者关注于一些特殊应用场景的能耗。比如MPEG解码器[2]、多媒体游戏[3]。另外，DVS算法的研究也发展到分布式、多处理器的实时系统上[4]。单处理器上，以周期性任务、非周期性任务、偶发任务并发运行的实时系统为模型的DVS调度算法的研究比较少。参考文献[5]提出不同算法适用于EDF的调度方案，把偶发任务放在完全带宽服务器TBS（Total Bandwidth Server）下运行。

在实际的嵌入式便携/移动设备中，绝大多数是周期性任务与非周期性任务同时并发处理，以完成用户需要的功能。从操作系统任务抽象的角度上来说，是一个周期性任务和非周期性任务的混合并发模型。本文主要着眼于设计一个基于线程的任务间电压（频率）调度器的DVS算法，称为基于混合任务集的减慢因子DVS调度算法。这里的“混合任务集”主要指周期性任务和非周期性任务的混合的任务集，并且满足如下需求：(1)能够保证软实时任务的实行性，同时有效地降低能耗；(2)能够适用于周期性任务和非周期性任务混合并发的情况；(3)吸收基于线程的调度器和基于时间间隔的调度器二者的优势，解决软实时系统的动态电源管理问题。

1 系统模型

1.1 任务模型

下面给出了本文论述的DVS算法所基于的模型：(1)假设应用由固定数目的任务组成；(2)任务分为周期性任务和非周期性任务，周期性任务有已知的周期；(3)各个任务彼此完全独立；(4)所有系统开销、上下文切换等被忽略（即假设开销为0）；(5)所有任务的时限小于或等于它们的周期(即每个任务必须在它下一次启动前完成)；(6)所有任务有最高频率下测得固定的最坏情况执行时间；(7)由于系统定时器的粒度，周期性任务具有启动抖动；(8)所有任务在可变频率和电压的单处理器上调度。

1.2 服务器模型

系统中存在着非周期性任务与周期性任务，周期性任务可以用传统的RM算法对其调度，而非周期性任务的调度需要引入服务器进行解决。

偶发服务器SS(Sporadic Sever)在某个确定的优先级上控制一个或者多个非周期性任务的调度。它有两个重要的属性容量Es和补充周期Ts。当系统中没有非周期性任务请求服务时，偶发服务器会一直保持其容量；当非周期性任务请求服务时，该任务将会运行于服务器同一优先级上，并且消耗部分或者全部的服务器容量。当所有容量被消耗掉，而任务仍然没有运行完成时，该任务将会切换到后台优先级运行。本文SS模型采用的是优先级追踪补充。

2 基于混合任务集的减慢因子DVS调度算法

2.1 静态减慢因子

在实时系统中，可调度性是保证系统可靠的重要参数。对任务集进行可调度性分析是减慢因子算法的必要部分。当任何新的周期性任务或者服务器进入系统并且在调度器中登记后，将会执行 “静态减慢因子计算”过程，进行整个系统的可调度性分析，并且为每一个任务计算出最小的工作频率，保证所有任务在其工作频率下运行，仍旧是可调度的，不会影响整个系统的实时性需求，其中 0＜as≤1。

“静态减慢因子计算”过程会通过“调整最差执行时间”过程计算一个减慢因子，使得给定任务集中存在一个或者多个任务的最差响应时间刚好等于它们的时限（此时该任务集刚好可调度）。这样的任务称为临界任务。“静态减慢因子计算”过程首先调用“调整最差执行时间”过程计算初始任务集的同一减慢因子F，接着让优先级低于临界任务的任务集继续调用“调整最差执行时间”过程计算出新的减慢因子。这是因为如果继续让作用于优先级高于临界任务的减慢因子F变小，必然会导致至少有一个临界任务超过时限，破坏系统的实时性。而让作用于优先级低于临界任务的减慢因子F变小将不会影响整个任务集的可调度性。这个过程将会反复执行，直到初始任务集中的最低优先级任务变成临界任务。总之，这个迭代过程为每一个任务计算出运行的频率和最大频率之间的比值（减慢因子），同时保证整个任务集是可以调度的。需要说明的是，对于服务器将不会应用静态减慢因子，因为如果增加了服务器的运行时间，必然会造成受服务器调度的非周期性任务平均响应时间的增加。

2.2 动态减慢因子

联机动态减慢因子的计算通过“动态减慢因子计算”过程来实现。其原理是，每一周期性任务在运行时态其执行时间不会总处于最差执行时间的情况，这样必然会产生动态空闲间隔。计算动态减慢因子需要在实时操作系统中对每个周期性任务的最近一段时间的实际运行时间进行统计，然后根据统计的结果对下一次这个任务再次运行的时间做出预测。通过这个预测值计算出动态减慢因子。动态减慢因子(0＜ad≤1)计算的核心是预测任务运行时间的预测模型。在实际的算法实现中采用算术平均预测模型，但为了提升预测模型的精度，同时保证算法的低开销，对预测模型作了简单的改进。当任务在没有完成本周期执行的内容前被强占时，本文算法利用条件预测来估计该任务的剩余运行时间。

2.3 基于CPU利用率预测的减慢因子

由于动态减慢因子算法使用的预测模型存在预测精度较低的问题，势必造成系统中仍旧存在很多动态空闲间隔。特别是在整个任务集本来的总体利用率就比较低的情况下，浪费在空闲调度循环的能耗仍旧十分严重。然而，2.1和2.2小节论述的算法属于基于线程的电压(频率)调度器，其缺陷是不能从系统整体上把握空闲间隔。这样需要利用系统级的DVS技术来弥补这样的问题[6]。

在本文描述的减慢因子DVS算法中，引入控制理论的经典控制器和比例积分微分控制器，对未来固定时间间隔内的处理器利用率做出估计，计算出一个全局减慢因子ag。

通过简化和改变比例积分微分控制器，得到下面的离散计算公式：

其中y是预测的处理器利用率，x是实际观测到的处理器利用率。

式（1）描述了一个函数，变量是 m个过去处理器利用率的值。它用来预测下一个固定时间间隔内的处理器利用率。

把处理器的利用率作为PID的输入。在固定时间间隔内，处理器利用率的计算公式如下：

2.4 基于自适应反馈的性能－能耗权衡策略

静态减慢因子、动态减慢因子与PID控制器联合控制频率和电压在减少能耗时，由于PID控制粒度过粗，可能会导致周期性任务出现频繁超过时限的问题。为此引入基于自适应反馈的性能-能耗权衡策略。该策略非常简单，利用一个自适应乘法因子来限制周期性任务的减慢因子来减慢幅度。通过滑动窗口机制监测周期性任务超过时限的次数。当超过时限的次数超过某个门限时，自适应乘法因子增加，使得减慢因子减少频率的幅度更加保守，减少了周期性任务超过时限的几率；当超过时限的次数低于某个门限时，这个自适应乘法因子aAF将不会对减慢因子起任何作用。

3 仿真与验证

为了评估本文所提出算法的性能，需要对商用的RTOS-Nucleus进行改造并嵌入感知功耗(Power-aware)的调度器。通过能耗、平均响应时间、能耗×平均响应时间3个参数进行性能评价。整个实验环境建立在Synopsis公司的商用建模工具CCSS中。为了保证算法的普适性，实验采用随机生成的6组任务集，每一组中包含5个周期性任务，任务的周期随机地在[10，500]ms中分布。6组任务集其利用率分别为 0.1、0.2、0.3、0.4、0.5、0.6。同时，配置3种不同的SS利用率分别为 0.25、0.35、0.45。非周期性任务的达到时间随机产生并符合指数分布（平均到底时间为其容量）。每一个周期性任务的执行时间随机符合高斯分布（从0到其周期）。对于功耗指标，本文基于商用SoC处理器OMAP3530实测得到CPU的功耗、频率和电压数值，通过对其进行归一化处理来表征算法的实际性能。

3.1 不同周期性任务集下的实验

本文对基于周期性任务集的加州大学提出的减慢因子DVS[7]做了改进，加入CPU利用率预测器和自适应反馈性能－能耗权衡策略以适用于软实时系统。因此，在仿真分析时，只是与原有的减慢因子DVS算法[7]和本文改进以后的算法（即基于混合任务集的减慢因子DVS调度算法）进行比较。

两种算法经过60 s的仿真运行可以看到，参考文献[7]的算法没有超过时限，本文提出的周期性任务超过时限的情况见表1。

表1 本文提出的算法周期性任务在实验中的超过时限率

图1所示为对于不同周期性任务利用率能耗比较，从图1可以看到，改进后的算法能耗变得更小，尽管超过时限率不是0，但仍旧是可以接受的水平。为了对两种算法的性能进行比较，引入能耗乘以平均响应时间作为衡量指标。图2所示为对于不同周期性任务利用率的平均响应时间×能耗比较。图2表明，不管是在哪一种周期性任务利用率的情况下，改进后的基于混合任务集的减慢因子DVS算法都非常有优势。当然这样的改进是牺牲系统的实时性能来达到的 （反映为周期性任务超过时限率的提升），但是，在软实时系统看来，实时性能的降低仍旧可以接受。因此，通过牺牲实时性换来能耗的降低是值得的。

图1 对于不同周期性任务利用率能耗比较

图2 对于不同周期性任务利用率的平均响应时间×能耗比较

3.2 仿真总结

通过仿真实验分析基于混合任务集的减慢因子DVS算法在软实时系统下的性能，研究不同的周期性任务利用率对算法的影响。经过仿真实验，从与原有的减慢因子DVS算法和改进后的算法在60 s仿真过程中的CPU利用率比较可以看出，后者进一步减少了系统中存在的空闲间隔，表现为能耗下降了14.2%～25.9%。能耗的下降是以提高周期性任务超过时限率为代价的，在软实时系统下这样的牺牲可以接受。

本文提出的基于混合任务集的减慢因子DVS算法有如下的特点：(1)针对的模型是周期性任务和非周期性任务混合并发的情况，使得算法更贴近实际应用。(2)在软实时系统中，该算法能够在保持很好的实时性能的同时，有效地减少能耗，提高了能量的有效利用率。(3)该算法在仿真实现中，对一个成熟的操作系统内核——Nucleus进行了有效改进，使之完全对用户透明。因此，该算法更易于移植到不同的硬件平台进行实际的应用。

[1]Xian Changjiu，Lu Y H，Li Zhiyuan.Dynamic voltage scaling for multitasking real-time systems with uncertain execution time[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2008，27(8)：1467-1478.

[2]DOU C，LEE Y L.Frame dropping algorithms for dynamic voltage scaling in battery-aware low-power video decoding[J].International Journal of Engineering Research and Applications(IJERA)，2012，5(2)：1643-1653.

[3]KUMAR A S，RAJALINGAM D A，KOKILA B.Frame based prediction for games in mobile devices using dynamic voltage scaling[J].International Journal of Advanced Research in Computer and Communication Engineering，2012，8(1)：478-482.

[4]LEE W Y.Energy-efficient scheduling of periodic real-time tasks on lightly loaded multi-core processors[J].IEEE Transactions on Parallel and Distributed Systems，2011，22(3)：530-537

[5]MOHAN A L，PILLAI A S.Dynamic voltage scaling for power consumption reduction in real-time mixed task model[C].International Conference on Soft Computing，Artificial Intelligence(SAI-2012)，2012：47-56.

[6]吴俊君，邓军，詹冰.基于电池剩余电量的动态电压调节算法的改进[J].电子技术应用，2008，34(2)：30-33.

[7]RAGHUNATHAN V，PEREIRA C L，SRIVASTAVA M B，et al.Energy aware wireless systems with adaptive powerfidelity tradeoffs[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems，2005，13(2)：211-225.