引用本文
张忆文, 郭锐锋. 实时系统混合任务低功耗调度算法. 45(1): 261-266
ZHANG Yi-wen, GUO Rui-feng. Low-power scheduling algorithm for mixed task in real-time system. Journal of Jilin University Engineering and Technology Edition, 45(1): 261-266  
Permissions
Copyright©2015, 吉林大学学报编辑部
版权所有.吉林大学学报编辑部
实时系统混合任务低功耗调度算法
张忆文1,2, 郭锐锋1
1.中国科学院 沈阳计算技术研究所,沈阳 110168
2.中国科学院大学,北京 100039

作者简介:张忆文(1988-),男,博士研究生.研究方向:低功耗调度.E-mail:zywsy2010@126.com

基金:核高基国家科技重大专项-国产软硬件在数控/工业控制装置中的应用与推广(2012ZX01029001-002)
摘要

针对包括周期任务和非周期任务的混合任务集,利用动态电压调节(DVS)技术,提出一种混合任务低功耗调度算法。该算法包括两个阶段,第一阶段计算出离线状态的静态速度;第二阶段通过回收空闲时间调节任务的运行速度。仿真实验表明:本文算法比现有的混合任务低功耗调度算法节约27.35%的能耗。

关键词: 计算机系统结构; 混合任务; 动态电压调节; 功耗管理; 实时调度
中图分类号:TP316.2 文献标志码:A 文章编号:1671-5497(2015)01-0261-06
Low-power scheduling algorithm for mixed task in real-time system
ZHANG Yi-wen1,2, GUO Rui-feng1
1.Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168,China
2.University of Chinese Academy of Sciences, Beijing 100039,China
Abstract

Dynamic Voltage Scaling (DVS) is an effective low-power technology. In this paper, a low-power scheduling algorithm is proposed for mixed task in real-time system. In this algorithm the mixed task set with both periodic tasks and aperiodic tasks is considered using the DVS technology. The algorithm is composed of two phases: in the first phase the static speed is computed off-line; in the second phase the running speed of the task is adjusted based on the slack time. Simulation results show that the proposed algorithm can reduce the average energy consumption by 27.35% over the existing mix task DVS algorithms.

Keyword: computer system architecture; mix task; dynamic voltage scaling; power management; real-time schedule
引言

动态电压调节(DVS)技术是一种有效的低功耗和能耗优化技术。近年来, 研究者将实时调度算法和DVS技术结合起来, 取得了丰富的研究成果[1, 2, 3, 4, 5, 6, 7]。文献[1]提出了针对周期任务的DVS算法, 该算法通过回收提早完成任务的空闲时间, 调节处理器运行速度降低能耗, 但该算法忽略了处理器的静态功耗。文献[2]拓展了文献[1]的方法, 既考虑处理器的动态功耗, 又考虑处理器的静态功耗。文献[3]考虑了处理器通用的功耗模型, 利用延迟调度的方法和DVS技术, 提出一种针对周期任务的低功耗调度算法。文献[4]提出了针对非周期任务的低功耗调度算法。该算法不需要事先知道任务的信息。最后, 文献[5]提出了面向嵌入式实时应用的算法, 该算法结合了DVS技术和DPM技术。

针对混合任务的低功耗调度, 也取得了丰富的研究成果。文献[8]提出了混合任务的在线低功耗调度算法, 该算法不需要事先知道任务的任何属性, 但该算法的节能效果差。文献[9]对其进行拓展, 使得该方法能够适用于处理器提供离散频率的情形。更进一步, 文献[10]对文献[8]中算法进行细致认真的研究, 提出了四种改进方法, 分别是引入辅助队列、分析空闲时间、任务划分和反馈方法。文献[11]分别利用可延迟服务器、偶发服务器调度混合任务, 提出了在线混合任务低功耗调度算法。该算法分为两个阶段, 第一阶段计算最佳的静态速度, 第二阶段分析空闲时间, 调节任务的运行速度。文献[12]提出了总带宽服务器混合任务低功耗调度算法, 并且首次提出以能耗与非周期任务平均响应时间的乘积作为性能指标衡量混合任务低功耗调度算法。上述的算法仅考虑处理器的动态功耗, 而忽略了处理器的静态功耗。

本文考虑处理器的通用功耗模型, 即既考虑处理器的动态功耗, 又考虑处理器的静态功耗, 并且使用关键速度[13]降低系统能耗。在能耗和响应时间的权衡中, 和以往的算法不同, 为了不使非周期任务的平均响应时间过大, 非周期任务一直保持离线状态计算的速度运行。提出的混合任务低功耗调度算法, 利用总带宽服务器调度混合任务。最后进行了仿真实验证明了本文算法的有效性。

1 系统模型和总带宽服务器
1.1 任务模型

实时系统混合任务包括时间触发的周期任务和事件触发的非周期任务。周期任务以定长的时间触发, 它有截止期限的限制, 错过截止期限会带来灾难性的后果; 而非周期任务是事件触发到达的时间不确定。

周期任务定义为 , 周期任务集 是周期任务的集合, 每个周期任务用二元组 表示, 是任务 的周期, 是任务 在最高处理器速度下最坏情况下的执行时间。假设任务 的相对截止期限等于周期且真实执行时间为 。周期任务的利用率 周期任务的总利用率Utot= ui。

非周期任务定义为 用二元组 表示, 和 分别是任务 的释放时间和执行时间。

使用EDF(Earliest deadline first)算法调度任务集, 根据文献[14], 假设周期任务最坏情况下的执行时间是事先给出的, 而非周期任务的执行时间要等到任务到达时才能确定。同时假设周期任务是相互独立的, 并且都在时刻 就绪。

1.2 功耗模型

DVS处理器的功耗可以分为两个部分:与速度相关的功耗 和与速度无关的功耗 [15]。与速度相关的功耗 主要来自动态功耗和短路功耗, 而与速度无关的功耗 主要来自漏电流功耗。动态功耗 由下式表示:

式中: 是电路的翻转频度; 为电路的负载电容; 为电路的工作电压; 为时钟频率。

短路功耗 可由下式计算:

式中: 为短路电流。

漏电流功耗 的计算公式如下:

式中: 表示子阈值电流; 表示反向偏置节点电流; 表示体偏置电压。

总功耗 由下式给出:

处理器存在3个状态:工作状态(active)、空闲状态(idle)、休眠状态(sleep)。当处理器处于空闲状态时, 功耗主要来自与速度无关的漏电流功耗, 关闭处理器可以减少功耗。处理器处于工作状态时, 降低处理器的速度可以降低处理器的动态功耗, 但处理器速度的降低会延长任务的执行时间, 系统的静态功耗会增加。为了更有效地降低系统层次的能耗, 文献[15]提出了关键速度, 也就是系统能耗最低的运行速度。关键速度 可以由式(5)给出:

假设处理器提供连续的频率和电压, 对处理器的速度进行归一化, 归一化的处理器速度范围为 且不考虑速度切换的一切开销。当任务的运行速度不等于关键速度时, 这时系统的能耗会增加, 为了保证系统的实时性, 假设任务运行的最低速度应该大于等于 尽管目前的商用处理器提供的速度是离散的, 但文献[9]提供的算法能够有效地解决处理器提供离散电压和频率的情形, 因此这个假设是合理的。同时假设任务的执行时间和运行速度成线性关系, 即任务 在速度 下的执行时间为

1.3 总带宽服务器

文献[14]提出的总带宽服务器是一个简单易实现且能够使非周期任务响应时间缩短的调度算法。根据总带宽服务器的规则, 非周期任务与周期任务根据EDF算法一起调度。非周期任务的截止期限 可以由下式计算:

假设 可以看出 是服务器带宽 和非周期任务 的截止期限 的方程。同时可以看出 越大, 越小, 任务的优先级越高, 因此非周期任务的响应时间就越短。文献[14]证明了总带宽服务器在周期任务不错过截止期限的情况下, 算法可调度的充要条件为

2 混合任务低功耗调度算法
2.1 计算离线状态的速度

对于周期任务, 运行速度越低, 其能耗也越低。低的运行速度, 会延长任务的执行时间, 这样会增加非周期任务的响应时间, 因此需要在低能耗和低响应时间之间进行权衡。为了充分利用静态的空闲时间, 同时也不至于过高地增加非周期任务的响应时间, 离线状态的速度设置为 其中 为服务器带宽。下面的定理证明离线状态的速度可以确保任务集的可调度性, 并降低系统的能耗。

定理1 当 设置离线状态的速度为 使用EDF算法调度任务集依然是可行的。

证明 当 时, 系统的利用率为 所以任务集是可调度的。当 时, 系统的利用率为 所以任务集依然是可调度的。

2.2 回收任务的空闲时间

由于任务实际的执行时间往往低于估计的最坏情况下的执行时间, 可以通过回收空闲时间, 调节处理器的运行速度, 降低系统能耗。在介绍算法前先引入几个概念。

队列:指在速度 下就绪的队列, 用来回收周期任务提早完成的剩余时间。 队列的元素根据EDF调度策略进行排序。假设 和 分别为 的剩余执行时间和最坏情况下执行时间。当任务就绪时设置 随着任务的执行, 和 都减少, 减少的量等于任务执行的时间。当任务完成时设置 在当前的调度点 任务 可利用的执行时间由两部分组成:①高优先级任务提早完成剩余的空闲时间( ); ②任务 的剩余执行时间 为在时刻 之前已经完成的高优先级的任务集。 可以通过式(7)计算:

2.3 混合任务低功耗调度算法

该算法有两个目标:一个是低能耗, 另外一个是低响应时间, 但这两个目标有冲突, 需要在两者之间进行权衡。为了不使非周期任务的响应时间过大, 非周期任务一直保持离线状态计算的速度 运行, 而对于周期任务可以通过利用空闲时间来调节处理器速度, 以达到降低能耗的目的。

由于非周期任务以速度 运行, 其截止期限也会发生变化, 式(8)重新计算非周期任务的截止期限。

给出MTLPSA算法步骤如下:

(1)输入:当前调度的周期任务 非周期任务 当前调度时刻 上一次调度时刻 上一次调度的周期任务 其运行速度 关键速度

(2)输出: 的运行速度 和 的运行速度

(3)计算离线状态的速度 任务 的速度为

(4)任务 或者 就绪(计算出 的截止期限), 根据EDF调度策略将任务插入到 队列, 并设置

(5)当有新的事件发生(任务到达或完成), 队列队头任务的 假如 将该任务从 队列移除。队列的下一个元素重复这个过程, 直到队列为空。

(6)假如任务 完成,

(7)假如任务 被抢占,

(8)计算任务的空闲时间 。

(9)计算任务 的运行速度

(10)假如

任务 使用空闲时间的原则是先使用高优先级任务的空闲时间, 然后再使用自己的时间。对 队列元素进行更新可以在 时间内完成(见算法MTLPSA步骤(5))。当任务完成执行时, 设置任务的最坏情况下的执行时间为0(MTLPSA算法步骤(6))。任务被抢占, 更新任务最坏情况下的执行时间(MTLPSA算法步骤(7))。计算任务的空闲时间 可以在 时间内完成。因此算法的时间复杂度为

2.4 算法实例

考虑有两个周期任务 和非周期任务 的混合任务集, 任务的参数为 通过计算可知 假设总带宽服务器的带宽 关键速度 在区间[0, 12]用MTLPSA算法调度混合任务集。MTLPSA算法调度混合任务集是可行的, 因为 计算出的离线状态的运行速度 即非周期任务的运行速度。通过式(8)计算出非周期任务的截止期限 任务的调度结果如图1所示。

图1 MTLPSA算法调度任务Fig.1 Tasks set scheduled by MTLPSA algorithm

从图1可看出, 任务 在时刻0.5完成执行, 留下0.5个单位的空闲时间; 任务 以速度 运行, 在时刻2.86完成执行。非周期任务 在时刻3到达并开始执行, 在时刻5完成执行。在时刻4到达的任务 由于优先级比 低, 所以只能等待执行, 在时刻5.5完成执行。

3 仿真实验

为了评价MTLPSA算法, 提出两个性能指标:能耗(Energy), 能耗与非周期任务的平均响应时间的乘积(Energy * Average response time)。实验使用的硬件平台为Pentium(R) Dual-core CPU 2.20 GHz、2 GB的RAM的个人计算机。利用C语言实现一个模拟混合任务集调度的仿真器, 该仿真器基于EDF调度策略, 使用Intel XScale PXA270 微处理器。该处理器提供的速度为{0.15, 0.4, 0.6, 0.8, 1.0}。本文假设处理器提供的速度为[0.15, 1.0]。根据文献[16]该处理器的功耗模型可以近似为 处理器空闲的功耗为0.08 W。在仿真器中实现三个算法:①NODVS, 即不使用DVS技术, 所有的任务都以最大的处理器速度运行, 将其作为基准算法; ②DFSA, 该算法在文献[17]中提出, 使用总带宽服务器调度混合任务, 在满足周期任务截止期限、降低任务响应时间的情况下, 尽可能降低系统能耗, 但该算法假设任务以最坏情况下的时间运行, 没有利用任务提早完成的空闲时间; ③MTLPSA算法。选取100个混合任务集, 最终的结果是100个混合任务集的平均值。每个混合任务集包含5个周期任务, 周期任务 的周期 服从[10, 1000]的均匀分布, 周期任务 的最坏情况下的执行时间 服从[1, ]的均匀分布, 周期任务 的真实时间服从 的均匀分布。非周期任务 的参数要等到任务到达时才知道, 它的到达时间间隔服从均值为 的泊松分布, 服务时间间隔服从均值为 的泊松分布, 因此非周期任务的负载 为了简单起见, 假设 为常数。同时假设周期任务总的利用率 考虑服务器带宽 和非周期任务的负载 对Energy、Energy* average response time的影响。

3.1 服务器带宽UB的影响

这一部分设置非周期任务的负载 考虑服务器带宽 对Energy, Energy * Average response time的影响。

图2为服务器带宽对能耗的影响, 并且以NODVS算法的Energy为基准进行归一化。随着服务器带宽的增大, DFSA算法的能耗也随之增大, 这是因为带宽越大, DFSA算法的运行速度也就越大; MTLPSA算法的能耗也随之增大, 这是因为非周期任务的运行速度增大, 且周期任务离线的运行速度也增大。MTLPSA算法的能耗始终低于DFSA算法的能耗, MTLPSA算法和DFSA算法相比可以节约大约26.76%的能耗。

图2 UB与能耗的关系曲线Fig.2 Relationship between UB and Energy

图3 UB与能耗* 平均响应时间的关系曲线Fig.3 Relationship between UB and Energy * Average response time

图3以NODVS算法的Energy* Average response time作为基准进行归一化。MTLPSA算法的Energy* Average response time始终低于DFSA算法的Energy * Average response time。经过计算MTLPSA算法的Energy * Average response time比DFSA算法的Energy * Average response time大约小11.57%。

3.2 非周期任务负载ρ 的影响

设置总带宽服务器的带宽 考虑非周期任务负载 对Energy、Energy* Average response time的影响。

图4为非周期任务负载对能耗的影响, 并且以NODVS算法的Energy为基准进行归一化。从图4可以看出MTLPSA算法的Energy始终低于DFSA算法的Energy。非周期任务负载对DFSA算法的能耗影响不大, 这主要是因为服务器带宽设定为固定值, DFSA算法的周期任务的运行速度始终保持不变。经过计算可知MTLPSA算法比DFSA算法平均节约27.35%的Energy。

图4 ρ 与能耗的关系曲线Fig.4 Relationship between ρ and Energy

图5 ρ 与能耗* 平均响应时间的关系曲线Fig.5 Relationship between ρ and Energy * Average response time

图5为非周期任务的负载对Energy * Average response time的影响, 并且以NODVS算法的Energy * Average response time作为基准进行归一化。MTLPSA算法和DFSA算法的Energy * Average response time高度依赖于非周期任务的负载, 且上下波动很大。MTLPSA算法的Energy * Average response time始终低于DFSA算法Energy * Average response time。经过计算MTLPSA算法的Energy * Average response time比DFSA算法小大约18.31%, 即MTLPSA算法更具有优势。

4 结束语

针对混合任务系统, 提出了混合任务低功耗调度算法MTLPSA。该算法采用通用的功耗模型, 即包含动态功耗和静态功耗。为了更好地评价算法的性能, 提出了能耗与非周期任务的平均响应时间作为性能指标, 仿真实验表明, MTLPSA算法比DFSA算法节约大约27.35%的能耗, 本文算法比现有的混合任务的低功耗算法更具有优势。

The authors have declared that no competing interests exist.

参考文献
[1] Aydin H, Melhem R, Moss D. Dynamic and aggressive scheduling techniques for power-aware real-time systems[C]∥Proceedings of the 22th Real-Time Systems Symposium, London, 2001: 192-211. [本文引用:1]
[2] Aydin H, Devadas V, Zhu D. System-level energy management for periodic real time tasks[C]∥Proceedings of the 27th IEEE international Real-Time Systems Symposium, Riode Janeiro, 2006: 313-322. [本文引用:1]
[3] Jejurikar R, Pereira C, Gupta R. Dynamic slack reclamation with procrastination scheduling in real-time embedded systems[C]∥Proceedings of the 42th Design Automation Conference, San Diego, 2005: 111-116. [本文引用:1]
[4] Zhong X, Xu C. Energy-aware modeling and scheduling for dynamic voltage scaling with statistical real-time guarantee[J]. IEEE Transactions on Computers, 2007, 56(3): 358-372. [本文引用:1] [JCR: 1.379]
[5] Devadas V, Aydin H. On the interplay of voltage/frequency scaling and device power management for frame based real-time embedded applications[J]. IEEE Transactions on Computers, 2012, 61(1): 31-44. [本文引用:1] [JCR: 1.379]
[6] Zhu D, Aydin H. Reliability-aware energy manage-ment for periodic real-time tasks[J]. IEEE Transactions on Computers, 2009, 58(10): 1382-1396. [本文引用:1] [JCR: 1.379]
[7] Wang W, Ranka S, Mishra P. Energy-aware dynamic slack allocation for real time multitasking systems[J]. Sustainable Computing: Informatics and Systems, 2012, 2: 128-137. [本文引用:1]
[8] Lee C H, Shin K G. On-line dynamic voltage scaling for hard real time systems using the EDF algorithm[C]∥Proceedings of the 25th IEEE International Real Time Systems Symposium (RTSS 04), Lisbon, 2004: 319-327. [本文引用:1]
[9] Gong M, Seong Y, Lee C. On-line dynamic voltage scaling on processor with discrete frequency and voltage levels[C]∥Proceedings of International Conference on Convergence Information Technology, Gyeongju, 2007: 1824-1831. [本文引用:1]
[10] 张冬松, 金士尧, 吴彤. 硬实时混合任务在线节能调度技术分析[J]. 计算机应用, 2008(1): 236-239.
Zhang Dong-song, Jin Shi-yao, Wu Tong. Online energy-efficient scheduling technique analysis for hard real-time mixed tasks[J]. Computer Applications, 2008(1): 236-239. [本文引用:1]
[11] Shin D, Kim J. Dynamic voltage scaling of mixed task sets in priority-driven systems[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2006, 25(3): 438-453. [本文引用:1] [JCR: 1.093]
[12] Aydin H, Yang Q. Energy-responsiveness tradeoffs for real-time systems with mixed workload[C]∥Real-Time and Embedded Technology and Applications Symposium, Toronto, 2004: 74-83. [本文引用:1]
[13] Jejurikar R, Pereira C, Gupta R. Leakage aware dynamic voltage scaling for real time embedded systems[C]∥Proceedings of the 41th Design Automation Conference, San Diego, 2004: 275-280. [本文引用:1]
[14] Spuri M, Buttazzo G. Scheduling aperiodic tasks in dynamic priority systems[J]. Real-Time Systems, 1996, 10(2): 179-210. [本文引用:1] [JCR: 0.55]
[15] Niu L, Li W. Energy-efficient fixed-priority scheduling for real-time systems based on threshold work-demand analysis[C]∥Proceedings of the 9th International Hardware/Software Codesign and System Synthesis, 2011. [本文引用:1]
[16] Chen J J, Kuo T W. Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems[C]∥ICCAD, 2007: 289-294. [本文引用:1]
[17] Nasro M, Asad-Raza K, Ishtiaq A, et al. Minimizing response time implication in DVS scheduling for low power embedded systems[C]∥Innovations in Information Technology, 2008: 347-351. [本文引用:1] [CJCR: 0.2618]