实时系统中两类高能效调度问题

湖南师范大学数学与计算机科学学院 钱光明



实时系统中两类高能效调度问题

湖南师范大学数学与计算机科学学院 钱光明

【摘要】实时和嵌入式系统中，节能和省电备受关注。这一问题牵涉许多方面，其中系统的调度方案至关重要。文章将高能效调度作了典型分类：单次作业集合的高能效调度和周期任务集合的高能效调度，总结和归纳了多年来国际学者的代表性研究，探讨了今后的研究趋势。

【关键词】单次作业集合；高能效调度；最优调度方案；竞争比

1　引言

从环保、节能和经济角度来说，省电是一个长久的话题。Google服务器维护工程师早就声称，如果电费继续增加，其所占比例将大大超过硬件开销［1］。这些年，随着便携式通信、远程测量、无线节点等技术的大量应用，低功耗越来越被更多的普通人所关注。

一个嵌入式系统，为了实现其省电和低功耗，经常考虑的是在满足应用需求的前提下，其工作频率和工作电压要尽量低，空闲时尽量处于低功耗状态（如待机状态、断电状态等），也就是要做到高能效（Energy-Efficient）［2］。但是，如何在不同的系统和不同的场合做好这两个“尽量”，吸引了大量学者进行研究，至今仍存在不少的开问题。

实时应用中，主要的应用需求就是任务需要在一定时间内完成。既要低功耗，又要满足时间指标。容易想象，系统的调度方案和算法，对实现高能效至关重要。在众多的研究文献中，我们梳理出两大类问题：①单次作业集合的高能效调度；②周期任务集合的高能效调度。

2　单次作业集合的高能效调度

2.1未考虑睡眠

这里单次作业集合是指：系统中可能有一个或多个任务（或称作业），但每个任务只执行一次。设系统中的作业集合为（J1，J2，…，Jn）。，其释放时间为ri，截止期为di，执行量为wi，作业模型可表示为（ri，wi，di）。因为高能效调度一般要考虑改变处理器的频率，所以Ji的实际执行量为wi/f，这里f代表处理器的当前工作频率。有的文献中干脆将执行量表示为处理器周期数［3］。

图1　单次作业集合示例：作业J1、J2和J3按EDF策略调度

图1所示为单次作业集合的一个示例，调度策略为EDF（Earliest Deadline First）［4］。图中三个作业分别为，涂黑的部分表示相应作业正在得以执行，例如在t=5到t=9期间，J1占据处理器运行。假定每个作业在其截止期后就不再有执行要求，这就是单次作业的含义。

实际上，图1中的调度情况只是针对处理器的一个特定工作频率f。当f升高时，每个作业的运行时间将缩短，当f降低时，运行时间将被拉长。

为了低功耗，实现高能效调度，一个自然的想法就是：在满足各作业截止期的前提下，尽量降低工作频率f，因为大量的文献都指出CMOS器件的耗能E是随着f的升高而快速增加。所以，在计算系统的功率P时，有的研究模型取［5］；有的按进行研究［6］；或干脆写出，系数β，γ＞0［7］。

在不同的工作时间段，合理分配不同的最低工作频率，就可能既满足时间指标又能耗最低。YDS（以作者姓氏首字母命名）算法便符合此要求，它是一个适应于图1所示场合的最优调度方案［2］［5］［6］。这是一个离线（offline）调度方案，只有多项式时间复杂度。但是，在线（online）调度就没这么幸运，因为任务的参数（如执行时间wi）有时是难以预知的。设计出一个在线调度方案，往往需要评估它与最优调度方案有多大的差别。例如，如果采用最优调度方案时系统的能量消耗为Eopt，在线调度方案消耗的能量为，那么，k值可达多少？这就是所谓的竞争比（competitive ratio）［2］。抽象地，与竞争比相关的问题远远不只是在考虑计算机的调度方案时碰到，物联网、交通领域、经济调控等诸多领域都与之关联，文献［8］被众多不同专业的研究人员所引用。

2.2考虑睡眠

为了节能，当处理器空闲时，可将其设置在睡眠状态（sleep state），或干脆到停机状态（Power-Down）。例如，图1中，在t=9 到t=12期间，三个作业都已运行完毕，处理器空闲，自然想到此间停机最好。但是，无论从唤醒（wake-up）到睡眠，还是从睡眠到唤醒，变化过程都是需要消耗能量的，设其为Etran。如果睡眠时间不够长，其节省的能量可能还不够补偿Etran。

设睡眠时长L刚好补偿Etran，并且系统工作在某一固定频率，那么，是否将处理器空闲状态转变为睡眠状态，主要看睡眠时间是否长于L。如一个简单直接的算法ALG-D就是：空闲时先不睡眠，只有当空闲时间超过L时才转入睡眠状态，此算法的竞争比可达2［2］。还有一些算法可小于2。

如果频率可变，又要考虑睡眠状态，可归为SS-PD（Speed Scaling with Power-Down）问题［9］。SS-PD问题的离线最优调度算法已被证明是NP难度［7］，尽管存在近似算法的研究［6］。

如果频率固定，而作业的安排使得处理器出现零零散散的空闲时间，那么，能不能将这些空闲时间尽量集中，使单次睡眠的长度增加，有利于实现合算的睡眠呢？答案是肯定的。关于该问题的最优调度方案，文献［9］指出如果它是多项式时间复杂度，会有较宽广的应用。在适当的建模假设下，文献［10］证明该最优调度方案的时间复杂度是O（n5）。

需要注意的是：实际系统中工作频率并不是越低越好，因为可能存在一部分与频率无关的能量损耗。文献［6］提出了一个临界频率fcrit（critical speed）的概念。系统工作频率等于fcrit时，能量损耗最低。关联fcrit时，调度方案将更加复杂化。在t=4到t=6期间，系统工作频率从f=1降到f=0.5来运行。

图2　周期任务集运行时降频示例

3　周期任务集合的高能效调度

许多实时系统中任务是周期性的。对于一个周期任务来说，每一周期可看作一个单次作业；对系统中的所有周期任务，可以找出它们周期的最小公倍数周期TLCM，然后在TLCM内应用单次作业集合的分析方法。但无论如何这都使问题更负责。

图2所示的方法称为ccEDF（cycle-conserving EDF），直截了当，但其节能性能并非最好［11］。文献［11］中提出了一个look-ahead EDF，从将来的某一截止期往当前时刻反推，其节能性能强于ccEDF，算法实现虽然不像ccEDF简单，也不很复杂，是一个值得推荐的online算法，该文被同行引用早已超过千次。文献［12］在保存ccEDF简洁性的同时，提出了一个EccEDF算法，该算法能精确计算未使用的带宽，以改善节能。

实际系统中，往往工作频率并非连续可变的，只能取一些离散值。因此，当算法选定的频率fopt不存在时，只好选择其附近的一个可用频率，这样一来，节能又要打折扣。文献［3］提出了一个PWM （pulse-width modulation）方案，在最靠近fopt的左边和右边各取一个可用频率fl-opt和fr-opt，fl-opt＜fopt＜fr-opt，通过调节系统在fl-opt和fr-opt下的工作时间，达到最小化能量消耗的目的。

4　结束语

除了以上典型代表外，学者们还有不少其它研究模型。比如，离线非最优调度方案［6］。又如单次作业集合的运行时调度方案［2］［5］。不过，系统运行前，如果所有任务的所有参数都是已知的、不变的，自然就想到要考察最低能耗的最优调度方案，上面提到既变频又考虑睡眠时这一问题为NP难度，因此，今后应该会出现一些性能较好的非最优调度方案。而系统运行中，方案应该尽量简单而快速，所以，在现有基础上，有理由期盼找到更简单的、能耗更低的、或是适应于某些特定场合的运行时调度方案。

参考文献

［1］Barroso L A.The price of performance［J］.Queue，2005，3（7）：48-53. ［2］Albers S.Energy-efficient algorithms［J］.Communications of the ACM，2010，53（5）：86-96.

［3］Bini E，Buttazzo G，Lipari G.Minimizing CPU energy in realtime systems with discrete speed management［J］.ACM Transactions on Embedded Computing Systems（TECS），2009，8（4）：31.1-31.23.

［4］Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment［J］.Journal of the ACM（JACM），1973，20（1）：46-61.

［5］Yao F，Demers A，Shenker S.A scheduling model for reduced CPU energy［C］.//Foundations of Computer Science，1995.Proceedings.，36th Annual Symposium on.IEEE，1995：374-382.

［6］Irani S，Shukla S，Gupta R.Algorithms for power savings［J］.ACM Transactions on Algorithms（TALG），2007，3（4）：41.1-41.23.

［7］Albers S，Antoniadis A.Race to idle：new algorithms for speed scaling with a sleep state［J］.ACM Transactions on Algorithms（TALG），2014，10（2）：9.1-9.31.

［8］Borodin A，El-Yaniv R.Online computation and competitive analysis［M］.cambridge university press，2005.

［9］Irani S，Pruhs K R.Algorithmic problems in power management［J］. ACM Sigact News，2005，36（2）：63-76.

［10］Baptiste P，Chrobak M，Dürr C.Polynomial-time algorithms for minimum energy scheduling［J］.ACM Transactions on Algorithms（TALG），2012，8（3）：26.1-26.29.

［11］Pillai P，Shin K G.Real-time dynamic voltage scaling for lowpower embedded operating systems［C］.//ACM SIGOPS Operating Systems Review.ACM，2001，35（5）：89-102.

［12］Min-Seok L E E，Cheol-Hoon L E E.Enhanced Cycle-Conserving Dynamic Voltage Scaling for Low-Power Real-Time Operating Systems［J］. IEICE TRANSACTIONS on Information and Systems，2014，97（3）：480-487.

作者简介：

钱光明，男，教授，主要研究方向为嵌入式和实时系统。