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

2016-08-09 05:41湖南师范大学数学与计算机科学学院钱光明
电子世界 2016年13期

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



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

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

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

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

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.

作者简介:

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