（计算机科学与技术专业论文）实时系统的节能调度技术研究.pdf

国防科学技术大学研究生院学位论文 摘要 近年来，能耗问题的研究在实时系统设计中越来越重要。节能调度技术能够结合实时 调度理论和动态电压调节d v s 技术有效地实现实时系统的节能设计。本文深入研究了硬 实时系统的节能调度技术。 首先，本文分别讨论了实际d v s 处理器具有的离散电压频率调节模式、转变时间和 能量开销等物理限制对理想情况最优离线节能调度算法的影响，进而综合考虑d v s 处理 器具有的多维限制，提出了空闲时间选择法，理论证明优于忙周期选择法，并给出了统一 的离线节能调度优化方法。 其次，本文深入分析了目前优秀的硬实时系统在线节能调度o l d v s 算法，指出存在 不足的原因。为提高节能效果，提出多种改进思路，同时设计并实现了用于验证节能调度 算法的模拟器，并在此基础上提出了节能调度技术仿真实验设计结构。 再次，针对o l d v s 算法不适应任务执行的动态变化的不足，提出一种基于辅助队列 的硬实时混合任务节能调度算法( 0 l d v s a q ) 。该算法能够更有效地利用动态松弛时间进 一步降低能耗。不仅证明了该算法的可调度性，仿真结果还表明，o l d v s a q 算法相比 o l d v s 算法平均提高约1 0 的节能效果。同时随着非周期负载因子的增大，节能效果会 更好。 最后，针对o l d v s 算法当周期任务的计算量占较大比值时节能效果很差这一不足， 提出一种基于简单反馈的硬实时混合任务节能调度算法( o l d v s s f ) 。该算法通过减少执行 周期任务的能耗进一步降低系统能耗。不仅证明了该算法的可调度性，仿真结果还显示 o l d v s s f 算法始终优于o l d v s 算法，当周期任务的计算量占较大比值时，最大可提高 1 0 以上、平均提高约5 的节能效果。 主题词：实时系统，节能调度，离线算法，混合实时任务，动态电压调节，转变开销 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t r e c e m l y ，r e s e a r c ho ne n e 唱yc o n s 啪p t i o np r o b l e mb e c o m e sm o r ea i l dm o r ei m p o r t 锄ti n t h ed e s i 趴o fr e a l t i m es y s t e m s e n e r g y e 街c i e n ts c h e d u l i n gt e c l l i l i q u e sc a nr e d u c ep r o c e s s o r e n e 唱yc o n s 啪p t i o ne 丘e c t i v e l yb yc o m b i n i n gr e a l t i m es c h e d u l i n gt h e o r yw i t hd y n 锄i cv o l t a g e s c a l i n g ( d v s ) ，a n dc a nb ea p p l i e di n t ot h er e a l - t i m ee n e r g y - e 衔c i e n td e s i g l l t h et h e s i sm a k e sa t h o r o u 班s t u d yo ne n e r g y - e 衢c i e n ts c h e d u l i n gt e c l l i l i q u e sf o rh a r dr e a l - t i m es y s t e m s f i r s t l y ，t h i sp 印e rr e s p e c t i v e l yd i s c u s s e st h ee f f e c t so fp r a c t i c a ld v sp r o c e s s o rl i m i t a t i o n s o nt h ei d e a l l yo p t i m a lo m i n ee n e r g y e m c i e n ts c h e d u l i n gm e t h o d ，s u c ha st h ee f f e c to ft m n s i t i o n t i m e ，e n e r g yt r a s i t i o no v e r h e a da n dt h a to ft h ev o l t a g e l e v e la n df r e q u e n c y - l e v e ld i s c r e t i z a t i o n f o rt h em u l t i d i m e n s i o n a ll i m i t a t i o n sm e n t i o n e da b o v e ，t h i sp a p e rp r o p o s e san e wm e t h o dc a l l e d s e l e c t i n gi d l et i m e ，w h i c hh a st 啪e do u tb e t t e ri nt h e o 叫t h a nt h eo n ec a l l e ds e l e c t i i 坞b u s y i n t e r v a l ，a n da l s od e s c r i b e sab e 仳ru i 】i f i e dt e c l u l i q u et oo p t i m i z eo f n i n ee n e r g y e m c i e n t s c h e d u l i n g s e c o n d l y ，“sp 印e rd e e p l ya n a l y s e s a ne x c e l l e n to n l i n ee n e 唱y e 所c i e n ts c h e d u l i n g a l g o r i t h mc a l l e do l d v s ，a n ds h o w st h ec a u s e sw r h i c hr e s u l ti nt h ea l g o r i t h m ss h o r r t c o m i n g h o r d e rt oi m p r o v ee n e r g ys a v i n g so f “sa l g o r i t h m ，t h i sp 印e ra l s op r e s e n t sv 撕o u sn e wm e 锄s a i l dd e s i g n s t oe v a l u a t et h ep e r f o m a n c eo ft h ee n e r g y - e m c i e n ta l g o r i t h m ，as i m u l a t o ri s i m p l e m e n t e d m o r e o v e r ，t h i sp 印e ra l s op r o p o s e st h ed e s i g ns t m c t u r eo fs i m u l a t i o ne x p e r i m e n t o ne n e r g y e m c i e n ts c h e d u l i n gt e c l l l l i q u e s t h i r d l y ，a c c o r d i n gt ot h es h o r t c o m i n go fo l d v sa l g o r i t h ms u c ha sn oa d a p t i v ea b i l i t i e st o d y n a l n i cc h a n g e so ft a s ke x e c u t i o n ，t h i sp 印e rp r o p o s e sa ne n e r g y e f f i c i e n ts c h e d u l i n ga l g o r i t h m o fh a r dr e a l t i m em i x e dt a s k sb a s e do na s s i s t a n tq u e u e ( 0 l d v s a q ) t h i sa l g o r i t 胁c a nu s e d y n 撇i cs l a c kt i m em o r ee f f e c t i v e l yt or e d u c ee n e r g yc o n s u m p t i o nl a r g e l y t h ef e a s i b i l i t yo f t h e a l g o r i t h mi sp r o v e d ，a n dt h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t l l i i la l w a y s i m p r o v e se n e r g ys a v i n ga b o u t10 o na v e r a g em o r et h a no l d v sa l g o r i t h n l m e a i l w l l i l e ，m e p e r f 0 r n l a n c eg 印b e c o m e sm u c hl a r g e ra l st h ea p e r i o d i c f a c t o ri n c r e a l s e s l a s t l y ，a c c o r d i n gt ot h ef a c tt h a to l d v sa l g o r i t h ma c m e v e sl e s se n e r g ys a v i n g m e nt h e r a t i oo fm ec o m p u t a t i o nr e q u i r e m e mo fp e r i o d i ct a s k st ot o t a lc o m p u t a t i o nr e q u i r e m e n ti sl l i g h e r ， “sp a p e rp m p o s e sa t le n e r g y e f j f i c i e n ts c h e d u l i n ga l g o r i t h mf o rh a r dr e a l t i m em i x e dt a s k s b a s e do ns i m p l ef e e d b a c k ( o l d v s s f ) t m sa l g o r i t h mc a nr e d u c ee n e r g yc o n s u m p t i o nm o r e e f f e c t i v e l yw h e ns c h e d u l i n gp e r i o d i ct a s k sa i l dc o n s e q u e n t l ya c l l i e v e m o r ee n e r g ys a v i n g m o r e o v e r ，t h ef - e a s i b i l i t yo fn e wa l g o r i t l u ni sa l s op r o v e d ，a n dt h es i i t l u l a t i o nr e s u l t ss h o wt h a t t h en e wo n ea l w a y so u t p e “1 0 r m so l d v sa l g o r i t l l l l l ，a n dc a ni m p r o v ee n e r g ys a v i n ga b o u tlo a tm o s ta n da b o u t5 o na v e r a g ew h e nt h er a t i oo ft h ec o m p u t a t i o nr e q u i r e m e n to fp e r i o d i c t a s k st ot o t a lc o m p u t a t i o nr e q u i r e m e n ti st l i 曲e r k e yw o r d s ： r e a l - t i m es y s t e m s ，e n e r g y e f r i c i e n ts c h e d u 1 n g ，o f f i i n ea i g o r j t h m ， m i x e dr e a l - t i m et a s k s ， d y n a m i cv o i t a g es c a i i n g ，t r a n s i t i o no v e r h e a d 第i i 页 国防科学技术大学研究生院学位论文 表目录 表1 1 实时调度技术基本分类6 表3 1 任务集合举例2 8 表4 1 辅助队列维护过程举例3 4 表5 1 任务集合举例4 9 第页 国防科学技术人学研究生院学位论文 图目录 图1 。1i n t e l 芯片的功耗密度2 图1 2w c e t 与c p us p e e d 近似关系图9 图2 1 最优离线节能调度算法伪代码1 8 图2 2 最优电压频率分配算法伪代码1 9 图2 3 最优电压分配方法的两段式调节步骤图2 0 图2 4 最优调度举例示意图2 1 图2 5 考虑时间开销的可行性调度示意图2 l 图2 6 空闲时间选择法中的两段式速度调节步骤图2 2 图2 7 统一的离线节能调度优化算法伪代码2 4 图3 1e d f 算法调度举例一2 8 图3 2o l d v s 算法调度举例2 9 图3 3节能调度结构图3 1 图3 4 节能调度技术仿真实验设计结构图31 图4 1 o l d v s a q 算法伪代码3 5 图4 2 调度举例示意图3 7 图4 3o l d v s a q 算法调度举例3 8 图4 45 个和1 5 个任务的能耗百分比3 9 图4 5非周期负载因子分别为0 5 和0 7 时的能耗百分比4 0 图5 1 任务划分示意图4 3 图5 2o l d v s s f 算法伪代码4 6 图5 3 执行第一个子任务时发生抢占示意图4 7 图5 4 执行第二个子任务时发生抢占示意图4 8 图5 5 调度举例示意图4 9 图5 6o l d v s s f 算法调度举例4 9 图5 75 个和1 5 个任务的能耗百分比5 0 图5 8 非周期负载因子分别为o 5 和0 7 时的能耗百分比5 l 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示谢意。 学位论文作者签名：丞篓兰途日期：2 护口7 年2 月8 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 学位论文作者签名：丞叁趁 日期：2 d 口7 年胆月倡日 作者指导教师签名：坌兰扛 日期：2 。d 7 年7 2 月2 斗日 国防科学技术大学研究生院学位论文 第一章绪论 随着c m o s 集成电路的设计工艺逐渐接近尺寸规模的极限，能耗问题已经变得越来越 重要。近年来，由于实时系统领域中能耗受限应用的日益增多，如何在满足时限约束的前 提下降低实时系统能耗，已成为一个有别于传统实时和低能耗设计的新兴课题【1 1 。实时系 统的节能调度技术正是顺应这一潮流而发展起来的。因此，研究节能调度技术，对于提高 实时系统的节能设计水平具有重要的现实意义。 1 1 1 实时系统的能耗问题 1 1背景 实时系统( r e a l t i m es y s t e m ) 通常是指这样一个系统：任何一个对于外界的刺激都能由 计算机给出及时响应的系统拉j 。其中，如果计算机不能及时给出它的输出，会发生一些很 糟糕的事情，这些称为硬实时系统。另一类称为软实时系统，即使超过了某些时限也不会 有什么灾难发生，但是性能会下降到可接受水平以下。以前实时系统的概念和技术主要应 用于内嵌的设备单元的程序控制，这些程序相对而言比较小而且简单，属于静态控制和集 中控制的。随着技术不断发展和更新，实时系统领域必须要适应日益增多的分布的、动态 的、高层应用的等各种更加普遍的实时控制要求。实时应用已经在国防、航空航天、核反 应堆控制、电信、过程控制、精细加工、医药、智能家电和传感器网络等各种领域发挥越 来越重要的作用。“实时计算”正在成为一种人类社会生活中不可缺少的技术。 c m o s 技术是现代计算机系统的基础。随着c m o s 的尺寸规模不断推进计算机性能的 提高，系统能耗问题同益严重。例如a l p h a2 1 2 6 4 处理器的功耗在6 0 0 m h z 的工作频率下 达到7 2 w ，p e n t i u m 4 处理器的最大功耗己经超过1 0 0 w 。摩尔定律也影响着系统能耗，在功 耗密度每1 8 2 4 个月翻一番的情况下，新一代的i n t e l 微处理器的功耗密度已接近核反应堆 的功耗密度，如图1 1 所示1 3 j 。近年来，随着实时领域朝着无线移动和便携式计算方向飞 速发展，不仅各种数码相机、掌上电脑( p d a ) 、移动电话、无线传感器和便携式医疗设备 大量出现，而且应用需求也越来越复杂化、智能化。例如许多移动电话不仅能够打电话， 还能够听音乐、拍照片、摄像等；新一代的无线传感器已能够处理多媒体流等复杂信号； 用户甚至可以通过扩展软硬件来扩展系统的功能，如掌上电脑提供硬件扩展槽来扩展它的 功能。这些设备往往都是依靠电池供电，电池的供电时间是衡量系统的重要参数，但电池 受重量、体积和尺寸的限制，储能能力有限，比如在军事、航空等特殊领域不可能允许频 繁更换电池，希望尽力延长电池寿命。而处理器功能越多能耗越大，又减少了电池寿命。 与半导体技术的发展相比，电池技术发展慢得多。今后随着系统日益的微小型化以及应用 需求对系统性能的要求不断提高，对于电池供电的实时嵌入式设备，能耗问题尤为突出。 能耗问题不仅引发难以解决的散热问题，而且限制了处理器主频的进一步提高，反过 第1 页 国防科学技术大学研究生院学何论文 来会影响系统的性能。此外，能耗的急剧增加还会提高硬件的封装和制冷成本，导致系统 可靠性的下降。因此，应用的需求尤其是降低系统能耗的需求大大促进了实时系统节能设 计的发展。 n g 迫 笔 1 5 “lp o 7 “o 5 p0 3 5 h0 2 5 o1 8 “o 1 3 po ipo 0 7 “ t c c h n 0 1 0 9 yg e n e r a t i o n f s s u r f 缸e 图1 1i n t e l 芯片的功耗密度 更具体地说，发展实时系统节能设计技术具有以下几个好处： ( 1 ) 节约能源 能源问题越来越受到人们的重视，节约能源已成为共识。发展节能设计技术，由此带 来的能源节余将有助于改善系统设备的工作环境。 ( 2 ) 降低成本、保证可靠性 降低系统能耗后，就不需为增加封装、冷却设备而提高成本。同时较低的能耗将会产 生较低的芯片温度，低发热量会减少系统故障发生率，从而保证了实时系统的可靠性。 ( 3 ) 减小体积、减轻重量、延长电池寿命 节能设计技术往往可以提高电池寿命，有助于减轻设备所携带电池的容量，使得设备 体积和重量大大减小。这对于空间、重量和能量受限的应用环境非常重要。 1 1 1 2 节能设计技术 为实现系统的节能设计，需要了解数字电路功耗的产生原因。目前大部分数字系统均 采用c m o s 集成电路。因此，本节首先分析c m o s 集成电路的功耗，然后分别从硬件和软 件两个方面介绍节能设计技术【4 】。 1 1 2 1c m o s 集成电路的功耗分析 c m o s 集成电路的功耗主要由静态功耗和动态功耗两部分构成。静态功耗是指漏电流 功耗，是电路状态稳定时的功耗，与电路的逻辑状态有关。动态功耗是指动态充放电功耗 和短路功耗，与电路的翻转频率有关。 ( 1 ) 静态漏电功耗 静态漏电是在二极管在反向加电时，晶体管内出现的漏电现象。在m o s 管中，主要指 第2 页 国防科学技术大学研究生院学位论文 的是从衬底的注入效应和亚门限效应。这些与工艺有关，而目前的c m o s 电路中，由漏电 流而产生的静态功耗与动态充放电功耗相比要小得多。漏电流功耗模型可以表示为 = k 屹。其中，是供应电压，k 是漏电流。 ( 2 ) 动态充放电功耗 动态充放电功耗是信号变化时电路电容充放电引起的功耗，其功耗模型为： 尼= 口c 吃厂。其中，a 为电路翻转频率，c 是负载电容，厂为时钟频率。 ( 3 ) 短路功耗 n m o s 和p m o s 之间短路瞬态电流产生的短路功耗是动态功耗的另一个来源。短路功 耗可以表示为名= 乞屹。其中l 是短路电流。一般来说，内部短路电流功耗不会超过动 态充放电功耗的1 0 。因此通常忽略短路功耗，动态功耗主要是指动态充放电功耗。 动态充放电功耗在c m o s 电路中起决定作用，大约占全部功耗的7 0 到9 0 。因此， 目前绝大多数低功耗能耗设计技术都以动态充放电功耗为考察和优化对象，忽略短路功耗 和漏电流功耗的影响。但是随着芯片面积的缩小，静态功耗所占的比重也在扩大，未来工 作也将逐渐重视静态漏电功耗的优化。 能耗是指一段时间内的总能量消耗。能耗的计算由时间和功耗这两个因素来决定，计 算公式为e = i 。尸( ，) 刃。 砌 1 1 2 2 硬件节能设计 硬件节能设计技术主要关注硬件模块的节能。硬件部分的节能设计技术主要包括电路 级、门级、寄存器传输级、结构和算法级等各个层次1 4 j 。 电路级节能设计，也可称为物理级。在这个层次上，常见的方法有：选择合理的逻辑 形式、降低负载电容、降低工作电压和降低时钟频率等。例如，动态逻辑电路不仅可减少 因为竞争冒险而产生的毛刺，并且能够降低节点的寄生电容。 当电路采用逻辑门来描述时，节能设计所能操作的最小单元就是具体的门电路，此时 并不需要关心逻辑门的具体版图实现，这些设计策略又称为门级节能设计方法。常用手段 有单元库映射、改变单元尺寸、插入缓冲器、调节相位、管脚置换、因式化简等。 寄存器传输级( i 汀l ) 是目前电路设计最常采用的层次，它的抽象层次已经提高到了 时序和组合模块，因此i 盯l 级的节能设计主要针对这些模块采取功耗优化措施。在r t l 级 一般都使用了硬件描述语言v h d l ，所以r t l 级的节能设计技术通常可对应到具体的硬件 描述语句，并且可采用综合手段来实施这些低功耗策略。主要的手段有门控时钟、存储单 元分区访问、操作数分离、预计算和操作树变形等。 结构和算法级低功耗设计是在确定电路实现方案时就需要考虑电路的功耗，它的功耗 优化效率相比门级和寄存器传输级要高的多。它主要是从电路的体系结构和编码等方面入 手，对具体电路实现没有特殊要求，这些节能措施对综合工具和布局布线工具完全是透明 的。常用的一些手段有采用并行结构和流水线，优化总线编码，使用异步电路等。 近年来又出现了一些新兴的硬件节能设计技术，包括微体系结构优化、功能部件动态 第3 页 国防科学技术大学研究生院学位论文 关闭( t 唧i n go f f 岫u s e ds y s t e mu n i t s ，t o s u ) 、动态电压调节( d y n a m i cv o l t a g es c a l i n g ， d v s ) 等技术。传统的处理器微体系结构级设计一般只以提高性能为目的。最近的研究则表 明，微体系结构级设计对于处理器功耗有着重要的影响，微体系结构级节能设计技术的基 本思路是对微体系结构级的各种功能部件进行合理的调节和配置，通过消除冗余操作来实 现性能和功耗的共同优化，或者在性能和功耗之间寻求合理的权衡。另外，动态电压调节 和功能部件动态关闭也是两种重要的节能技术。d v s 技术通过动态调节c m o s 工艺处理器 的供电电压和频率来降低处理器动态功耗，而t o s u 技术通过时钟门控和泄漏电流控制等 手段来动态关闭系统中的空转部件以减少冗余功耗和漏电流功耗。 1 1 2 3 软件节能设计 能耗的本质来源即c m o s 电路的开关电容活动最终是由软件运行情况所决定，节能设 计中存在相当大部分的节能空间是硬件级或者微体系结构级所无法涉足的，只有通过软件 节能设计技术才能得到解决【4 】。 软件节能设计包括编译器的节能设计、操作系统中调度算法的节能设计等等。编译器 的节能设计就是在输入输出的行为保持不变的前提下，对软件的运算结构进行改变，也就 是改变指令的排列组合顺序，并从中选择最低功耗的结构。编译器对代码的优化原来主要 用于体积和性能的优化，这里主要用于在保持性能的前提下，对功耗进行优化。编译器主 要通过两种方法实现优化，一种是减少程序的执行时间，一种是减少电路的活动性。 近年来，一些新型硬件节能技术的提出为软件能耗优化技术提供了新的优化途径。其 中许多重要的研究成果都围绕着d v s 技术展开，它已经成为一种关键的硬件节能技术。由 于今天大多数微处理器都采用c m o s 技术，最大运行频率受限于电压，所以降低供应电压 同时会导致频率的降低。而且采用c m o s 电路的处理器能量消耗与供应电压的二次方成正 比( eo c 矿2 ) ，使得通过软件方法动念降低供应电压和运行频率以减少能量消耗成为可能。 1 1 3 实时系统的特点 实时系统与一般的计算机系统相比，它主要有如下不同特点【5 】： ( 1 ) 时间约束性 时间约束性是指各个任务不仅应满足相互之间的拓扑约束和时序约束，还要遵从各自 的时限约束。任务具有时间约束是实时系统的一个重要特征。实时计算要求在有限的时间 之内完成任务的分配、调度和执行。实时计算的j 下确性不仅取决于逻辑正确性，而且取决 于时序正确性。 ( 2 ) 可预测性 可预测性是指系统能对实时任务的执行时间进行判断，确定是否能够满足任务的时限 要求。由于实时系统对时间约束要求的严格性，使得可预测性成为实时系统的一项重要性 能要求。 ( 3 ) 可靠性 大多数实时系统要求有较高的可靠性。在一些重要的实时应用中，任何不可靠因素和 第4 页 国防科学技术大学研究生院学位论文 计算机的一个微小故障，或某些特定实时任务超过时限，都可能引起难以预测的严重后果。 可靠性已成为衡量实时系统性能的不可缺少的重要指标。 早期的实时系统功能简单，包括单板机、单片机，以及简单的嵌入式实时系统等，其 调度过程相对简单。随着实时系统应用范围的不断扩大，系统复杂性不断提高，实时系统 具有以下新的特点： ( 1 ) 多种任务类型 在实时系统中，不但包括周期任务、偶发任务、非周期任务，还包括非实时任务。实 时任务要求要满足其时限，而非实时任务要求要使其响应时间尽可能的小。多种类型任务 的混合，使得系统的可调度性分析更加困难。 ( 2 ) 约束的复杂性 任务的约束包括：时间约束、资源约束、执行顺序约束、性能约束和能量约束等。时 间约束是任何实时系统都固有的约束。资源约束是指多个实时任务共享有限的资源时，必 须按照一定的资源访问控制协议进行同步，以避免死锁和高优先级任务被低优先级任务堵 塞的时间( 即优先级倒置时间) 不可预测。执行顺序约束是指各个任务的启动和执行必须 满足一定的时i 白j 和顺序约束。例如：在分布式端到端实时系统中，同一任务的各个子任务 之间存在前驱后继约束关系，需要执行同步协议来管理子任务的启动和控制子任务的执 行，使它们满足时间约束和系统可调度性要求。性能约束是指必须满足如可靠性、可用性、 可预测性、q o s 等性能指标。能量约束是指必须满足在固定的能量预算内，最大化整个系 统的性能目标。 为了精确管理“时间”资源，以达到实时性和可预测性要求，并能够满足实时系统的 新的要求，需用实时调度理论对任务进行调度和可调度性分析。任务调度技术包括调度策 略和可调度性分析方法，两者是紧密结合的。任务调度技术研究的范围包括任务使用系统 资源( 包括处理机、内存、i 0 、网络等资源) 的策略和机制，以及提供判断系统性能是否 可预测的方法和手段。例如：什么时候调度任务运行、在哪运行( 当系统为多处理机系统 或分布式系统时) 、运行多长时间等等；以及判断分析用一定参数描述的实时任务能否被 系统正确调度。可见，任务调度技术是实时系统中的关键技术之一，也是实时系统中最重 要、最活跃的研究领域之一。 1 1 4 实时调度 给定一组实时任务和系统资源，确定每个任务何时何地执行的整个过程就是调度。在 非实时系统中，调度的主要目的是减小系统平均响应时间，提高系统资源利用率，或优化 某一项指标；而在实时系统中，计算的正确性不仅取决于计算的逻辑结果，也取决于结果 产生的时间，实时调度的目的则是要尽可能地保证每个任务满足它们的时间约束，及时对 外部请求做出响应。 根据不同的分类依据，实时调度技术可以有多种分类【4 ，5 j 。基本分类方法如表1 1 所示。 第5 页 国防科学技术大学研究生院学位论文 表1 1 实时调度技术基本分类 分类依据分类 实时任务是否可被抢占抢 式调度和非抢- i 式凋度 实时任务是否分配优先级静态表驱动策略和优先级驱动策略 调度顺序产生的时机利方式离线调度和在线凋度 调度方法所针对的运ij 平台单处理器凋度和多处理器调度 ( 1 ) 抢占式调度和非抢占式调度 抢占式调度通常是优先级驱动的调度。每个任务都有优先级，任何时候具有最高优先 级且己启动的任务先执行。一个正在执行的任务放弃处理器的条件为：自愿放弃处理器( 等 待资源或执行完毕) ；有高优先级任务启动，该高优先级任务将抢占其执行。除了共享资 源的临界段之外，高优先级任务一旦准备就绪，可在任何时候抢占低优先级任务的执行。 抢占式调度的优点是实时性好、反应快，调度算法相对简单，可优先保证高优先级任务的 时间约束，其缺点是上下文切换多。而非抢占式调度是指不允许任务在执行期间被中断任 务一旦占用处理器就必须执行完毕或自愿放弃。其优点是上下文切换少；缺点是在一般情 况下，处理器有效资源利用率低，可调度性不好。 ( 2 ) 静态表驱动策略和优先级驱动策略 静态表驱动策略是一种离线调度策略，指在系统运行前根据各任务的时问约束以及关 联关系采用某种搜索策略生成一张运行时刻表。这张运行时刻表与列车的运行时刻表类 似，指明了各任务的起始运行时刻以及运行时间。运行时刻表一旦生成就不再发生变化了。 在系统运行时调度器只需根据这张时刻表启动相应的任务即可。由于所有调度策略在离线 情况下制定，因此调度器的功能被弱化，只具有分派器的功能。 优先级驱动策略指按照任务优先级的高低确定任务的执行顺序。优先级驱动是实时调 度中应用最广泛的调度策略，而单处理器实时调度主要采用优先级驱动的可抢占式调度算 法。按照优先级分配策略的不同，又分为静态优先级调度和动念优先级调度两类。 静态优先级调度是指：任务的优先级分配好之后，在任务的运行过程中，优先级不会 发生改变。静态优先级调度又称为固定优先级调度。它的特点是任务优先级在运行期间保 持不变。l i u 和l a y l a j l d 【6 j 提出了一种适用于可抢占的周期任务调度的静态优先级调度算法一 速率单调( r a t em o n o t o n i c ，r m ) 调度算法，并对其可调度性判定问题进行了研究。i 洲算法 的主要思想是：任务优先级按照周期大小固定分配，周期越短优先级越高，处理器根据优 先级高低进行任务调度。使用该算法时，含刀个周期任务的任务集可调度的充分条件是任 务集处理器利用率螨足以下条件u 刀( 2 枷一1 ) 。当甩趋近o 。时，刀( 2 1 加一1 ) 趋近l i l 2 = 0 6 9 3 ； 当i l _ 2 时，可调度利用率为o 8 3 。 由于r m 算法己被证明是单处理器下的最优静态优先级调度算法【6 j ，所以它受到研究 者和应用开发者的重视。该算法的特点有：算法简单，开销小，灵活性好：系统瞬间过载 时，可以完全预测哪些任务会丢失时限；处理器利用率较低，尤其是当任务集模型的数目 趋近无穷大时，不超过7 0 左右。 第6 页 国防科学技术大学研究生院学位论文 动态优先级调度是指：任务的优先级可以随着时间或系统状态的变化而发生变化。这 类算法在运行期间，任务的优先级依据某种原则可能随时间动态改变。最早时限优先 ( e a r l i e s td e a d l i n ef i r s t ，e d f ) 算法是动态优先级策略中的经典算法【6 1 。在e d f 算法中，系统 中最早时限的任务优先级最高。就绪队列中的任务总是按时限排序，时限越早的越靠近队 首。e d f 算法可调度的充分必要条件是处理器利用率小于等于l ，因此该算法在处理器利 用率方面有较大优势。 e d f 算法是单处理器下的最优动态优先级调度算法【6 】，在实际工程应用中已被广泛应 用。它的特点有：处理器利用率高，最大可达1 0 0 ；瞬间过载时，系统行为不可预测，也 就是不能预测哪些任务会丢失时限；可能发生多米诺骨牌现象，即一个任务超过时限可能 会引起一连串任务接连超时。 ( 3 ) 离线调度和在线调度 离线调度是在任务集运行之前就产生一个静态的调度表，在运行时总是按照调度表来 决定从就绪任务队列中选择哪个任务来运行。这类调度算法假设系统中实时任务的特性 ( 如：最坏执行时间，时限、执行次序等) 是全部己知的，它的可调度性分析是脱机进行的。 这类调度算法适合于问题需求确定，并且运行中不会发生较大变化的情形，如简单的工业 过程控制。离线调度算法的优点是运行开销小，可预测性强。但是它的灵活性较差，不适 合动态变化的或不可预测环境下的调度。在线调度算法是在运行期间才决定选择哪个就绪 任务来运行，它所依据的是目前己处于就绪态的各任务的相关属性，以此来决定当前的调 度序列。这类算法比较灵活，能够对变化的环境做出反应，适合于任务不断生成，并且在 任务生成之前其特性并不清楚的动态实时系统。但是，在线调度算法的运行开销一般比离 线调度算法大。 ( 4 ) 单处理器调度和多处理器调度 单处理器调度主要考虑在何时把系统唯一的处理器合理分配给相应的任务。而多处理 器调度不仅要考虑任务在单个处理器上的运行情况，还要考虑把任务分配到哪一个处理器 上运行。单处理器调度算法是实现多处理器调度的基础，部分单处理器调度算法的设计思 路可进一步扩展到多处理器调度中。 1 2 实时系统的节能调度技术 实时系统通常是按照系统最大资源需求来设计，而这种保守设计策略为专门面向实时 系统的节能设计技术提供了广阔的空间，可以在系统运行中根据实际任务执行情况采用合 理的节能技术。又因为实时系统中改变处理器的运行频率会改变实时任务的执行时间，很 有可能会违背实时性约束，所以直接利用硬件自适应的能耗管理策略是无法满足实时性要 求，而应该采用软件节能方法，利用d v s 等新技术对实时系统进行灵活的能耗敏感的资 源管理和任务调度，在满足时限约束( d e a d l i n e c o n s t r a i n e d ) 条件下合理降低系统能耗。 d v s 技术用于降低能耗的原理在于：e = 尸f其中：e 是能耗，尸是平均功耗，f 第7 页 国防科学技术人学研究生院学位论文 是执行时间。当使用动念电压调节d v s 技术动态降低处理器运行的供应电压和频率时， 通常能够立方级地减少功耗尸，而实时任务的执行时间，一般近似为线性的增加，最后能 耗e 就会近似得到平方级的减少。因此，本文把利用d v s 技术来优化实时系统能耗的方 法统称为实时系统的节能调度技术。为描述方便，以下调节电压或频率均是指电压和频率 的同步调节，节能调度技术是指基于d v s 技术的节能调度技术。 由于处理器能耗已经成为实时系统能量消耗的主要来源，多数情况下超过5 0 【7 1 ，所 以降低处理器能耗已经成为实时系统节能设计技术的关注焦点。目前，节能调度技术能够 有效地结合原有的实时调度理论和新兴硬件节能机制所提供的动态电压调节d v s 技术， 从编译和操作系统等角度来有效地实现实时系统的节能设计。 1 2 1 动态电压调节( d y n a m i c v b i t a g es c a i i n g ，d v s ) 技术简介 采用d v s 技术的处理器供电电压和时钟频率厂( 又称为处理器速度) 之间存在如 下关系【8 1 ： 厂：r ! 垡二堡竺 。 其中，r 和口( 1 口 2 ) 为工艺相关常数，”为门限电压。因此，对于给定的处理器频 率，存在一个使得处理器能够正常工作的最低供电电压。由于降低电压可极大地降低处理 器功耗，故d v s 处理器在能够达到所需要的频率的前提下，将尽量使供电电压最小化。 d v s 处理器只支持有限数目的离散电压频率档，一般可构建一个频率与电压的对照表， 然后把该对照表以硬编码方式写到芯片中。 为实现动态改变，d v s 处理器需要一个额外的反馈环路和电压转换器。电压频率 转变时存在一定的转变开销，包括转变时间和转变能耗。在进行电压频率转变时，处理 器通常会停止运行。转变时间主要来自于电压转换器的电压转换时间和处理器的频率转变 时白j 。电压转换器的电压转换时间的计算公式为【8 1 ： 2 c ， 昌= i k 一砭l l r i z l i m a x 频率转变时间通常较少，可在几个微秒内完成，但处理器和片外部件如存储器等进行 同步的时问可能会达到几十毫秒。因此，在时间调节开销方面，可能是几十微秒、几百微 秒或者达到毫秒级【4 1 。 转变能耗来自于处理器能耗和电压转换器能耗。由于d v s 处理器通常在转变期间采 用门控技术，此时只有极少的处理器静态功耗，故处理器能耗可忽略不计。电压转换器的 能量消耗是转变能耗的主要来源，计算公式为【8 】： & = ( 1 一) c ，l k 2 一呼i 在上述两个计算公式中，c ，是电压转换器的负载电容，k 是电压转换器的最大输出 第8 页 国防科学技术大学研究生院学位论文 电流，k 和是转换前电压和转换后电压，是电压转换器的切换效率系数。 如今随着d v s 技术的能耗优化潜力越来越被人们所重视，各种支持d v s 技术的商用 处理器也较为普遍，例如i n t e l 公司的x s c a l e 处理器和p e n t i 眦m 处理器，m d 公司的 a m d - k 6 11 1 和m o b i l ea t h l o nx p ，t r a i l s m e t a 公司的c m s o e 处理器等，c o m p a q 公司的掌 上电脑i p a q 也支持d v s 技术。 1 2 - 2 节能调度与传统实时调度的区别 传统实时调度算法是基于早期非d v s 处理器而提出的，其中执行时间概念可以看成 是相对处理器唯一最高频率而言的。例如，如果一个实时任务的最坏执行时间为6 秒，就 是指以处理器最高频率运行该任务的最大可能值为6 秒。而在基于d v s 处理器中，实时 任务在不同的处理器频率下会表现出不同的最坏执行时间，故首先需要分析出在保证时限 条件下处理器频率的改变对任务最坏执行时间的影响。由于实时任务本身的差异性和复杂 性，想要精确地描述出两者间的关系是很难的。事实上，大多数研究均采用近似的方法， 即假定任务最坏情况下执行时间( w c e t ) 的减少与处理器速度( c p us p e e d ) 的增加成正比 一，lu 4 。如图1 2 所示。 w c e t o c p us p e e d 图1 2w c e t 与c p us p e e d 近似关系图 利用d v s 技术改变实时任务运行时处理器的电压和频率，实质上就是对处理器电压