（计算机科学与技术专业论文）容错实时嵌入式系统低功耗调度技术研究.pdf

国防科学技术大学研究生院学位论文 摘要 随着嵌入系统应用的不断扩展，实时嵌入式系统的功耗和可靠性已经成为学 术界和产业界关注的重点。低功耗能耗技术和容错技术在实时嵌入式系统中具有 重要意义，长期以来它们都是被作为两个相互独立的领域进行研究。目前许多应 用在国防、空间和消费产品等领域的嵌入式实时系统往往既有功耗限制又有容错 需求，而最新的一些研究成果又表明，功耗限制和容错需求往往存在相互矛盾。 因此，在实时嵌入系统中将容错技术与低功耗技术融合具有重要的现实意义和应 用价值。近年来，国外的一些学者已经开始将二者结合起来进行考虑和研究，并 且受到学术界越来越多的重视。 实时嵌入式系统容错与低功耗的融合可以在不同层次上实现，本文根据实时 嵌入式系统资源往往受限，系统层的容错技术和低功耗技术具有开销小、灵活性 强和效率高等特点，选择从任务调度来研究容错实时嵌入式系统的节能问题，本 文的工作与成果主要有以下几点： 1 目前容错与节能相结合的任务调度主要基于检查点和d v s 展开。许多研究 只考虑了检查点的时间开销，本文从检查点实现过程、动态功耗组成及d v s 原理 等方面研究认为在某些情况下检查点的功耗开销必须要考虑。建立了检查点的功 耗模型，并基于该模型改进了基于检查点的d v s 容错节能算法。分析和讨论了检 查点功耗开销对最优检查点个数和节能效率的影响。 2 针对目前d v s 容错算法中离线算法实现简单、开销小，但对空闲时间的利 用过于保守，在线算法空闲时间利用率高，但在线计算开销大、计算复杂等不足， 本文提出了一种准静态的容错节能调度算法，它能以较低的在线时间开销达到近 似在线算法的性能。此外，与目前大多数算法不同，我们考虑了d v s 本身对暂时 性故障率的影响，并且任务可以具有不同的可靠度，使得算法更接近现实应用。 3 嵌入式系统的能量供给往往是十分有限的，如何在能量受限的环境下，最 大化能量的利用率或使系统性能最优是目前实时系统低功耗研究领域的热点之 一。本文研究了能量约束时，基于非精确计算模型i c m 的实时容错调度问题，提 出一种使系统性能优化的调度算法。该算法在离线阶段根据能量密度的优先级来 选择要执行的任务的可选部分，达到静态性能最优；运行阶段通过动态资源回收， 利用节余的能量进一步提高系统性能。 主题词：实时系统，嵌入式系统，容错，低功耗，任务调度 第i 页 国防科学技术大学研究生院学位论文 a bs t r a c t w i t l l 雠i n c r e a s i n ga p p l i c a t i o n so fe m b e d d e ds y s t e m s p o w e rc o n s u m p t i o na n d r e l i a b i l i t yo fr e a l - t i m ee m b e d d e ds y s t e m sh a v eb e e na t t r a c t i n gm u c ha t t e n t i o ni n a c a d e m ea n de n g i n e e r i n gc i r c l e s l o w e rp o w e r & e n e r g ya n df a u l tt o l e r a n c ea r eo f s i g n i f i c a n c ei nt h ed e s i g no fr e a l t i m ee m b e d d e ds y s t e m s ，a n di nt h ep a s t ，t h e ya r e v i e w e da st w oi n d e p e n d e n tr e s e a r c hd o m a i n sa l lg o n g h o w e v e r , f o rm a n yr e a l t i m e e m b e d d e ds y s t e m si ns u c ha p p l i c a t i o n sa sd e f e n s e ，s p a c ea n dc o n s u m p t i o n ，b o t ht h e p o w e rc o n s u m p t i o nr e s t r i c ta n df a u l tt o l e r a n c ea l er e q u i r e d m o r e o v e r ，s o m er e c e n t r e s e a r c h e sr e v e a lt h a tt h e r e a r es o m ec o n f l i c t sb e t w e e nt h e o p t i m i z a t i o no np o w e r c o n s u m p t i o na n dt h en e e do ff a u l tt o l e r a n c e 1 1 m s ，t h eu n i t yo ff a u l tt o l e r a n c ea n d1 0 w p o w e r 、) l ，i l lb eo fr e a ls i g n i f i c a n c ea n da p p l i c a t i o nv a l u e r e c e n t l y s o m eo v e r s e a s s c h o l a r sb e g i nt h eu n i t e dr e s e a r c ho ft h et w o p r o b l e m s 。w h i c hi n c u r si n c r e a s i n g a t t e n t i o ni na c a d e m e t h eu n i t yo ff a u l tt o l e r a n c ea n dl o wp o w e rc a ni m p l e m e n to nd i f f e r e n tl e v e l s s i n c em a n ye m b e d d e dr e a l - t i m es y s t e m sa r es u b j e c tt o s y s t e mr e s o u r c e ，t h ef a u l t t o l e r a n c et e c h n o l o g ya n dl o wp o w e rt e c h n o l o g yi ns y s t e ml e v e ln e e dl o w e rc o s t ，h a v e h i g hf l e x i b i l i t ya n dh i g he f f i c i e n c y a c c o r d i n gt ot h e s ec h a r a c t e r i s t i c s ，i nt h i sp a p e rt h e t a s k s c h e d u l i n gi si n v e s t i g a t e di no r d e rt ol o 惯p o w e ri nf a u l tt o l e r a n tr e a l - t i m e e m b e d d e ds y s t e m s n l em a i nw o r ka n dc o n t r i b u t i o na r ea sf o i l o w s ： f i r s t l y ，t h ep r e s e n tr e s e a r c ho nt r a d e o f rb e t w e e nl o w e rp o w e rd e s i g na n df a u l t t o l e r a n c ef o c u so nc h e c k p o i n t i n ga n dd y n a m i cv o l t a g es c a l i n g ( d v s ) m u c hl i t e r a t u r e o n l yd e a l e dw i t ht i m ec o s to fc h e c k p o i n t i n g a f a rr e s e a r c ho nt h ep r i n c i p l eo f c h e c k p o i n t i n g , t h em a k e u po fd y n a m i cp o w e ra n dt h ep r i n c i p l eo fd v s ，ac o n c l u s i o ni s g o tt h a ts o m e t i m e st h ep o w e rc o n s u m p t i o no fc h e c k p o i n t i n gm u s tb ec o n s i d e r e d a p o w e rc o n s u m p t i o nm o d e lo fc h e c k p o i n t i n gi ss e t u p , b a s e do nw h i c has c h e m ef o r e n e r g ys a v i n ga n df a u l tt o l e r a n c eb a s e dd v sa n dc h e c k p o i n t i n gi si m p r o v e d ，n l e n t h e e f f e c to fp o w e rc o n s u m p t i o no nt h eo p t i m a ln u m b e ro f c h e c k p o i n ta n d 雠e 伍c i e n c yo f e n e r g ys a v i n ga r ed i s s c u s s e d s e c o n d l y ，i np r e s e n ts c h e d u l i n gs c h e m eo fc o m b i n a t i n gd v sw i t hf a u l tt o l e r a n c e ， o f f - l i n e s c h e d u l i n gi se a s yt oi m p l e m e n ta n dn e e d sf e w e ro v e r h e a d b u ti st o o p e s s i m i s t i ci nt e r m so fu t i l i t y ，w h i l eo n - l i n es c h e d u l i n gh i g h l ye f f e c t i v e l yu s es y s t e m s l a c kb u ti t sc o m p u t a t i o nc o s ta n dc o m p l e x i t ya r eh i g h aq u a s i c s t a t i c s c h e d u l i n g s c h e m ed i f f e r e n tf r o mm o s to fo t h e r si s p e r f o r m a n c eo fn e a ro n - l i n es c h e m ew i t h p r o p o s e di nt h i sp a p e r ，w h i c ho b t a i nt h e f e w e rt i m ec o s t m o r e o v e r , i nt h es c h e m e p r o p o s e dh e r e ，t h ee f f e c to fd v si t s e l fo ns o f te r r o rr a t ei sc o n s i d e r a t e da n dt a s k si nt h e n e ws c h e m ec a nh a v ed i f f e r e n t r e l i a b i l i t yr e q u i r e m e n t s ，w h i c ha p p r o a c ht h er e a l a p p l i c a t i o n s 第i i 页 国防科学技术大学研究生院学位论文 f i n a l l y , t h ee n e r g ys u p p l yi su s u a l l yc o n s t r a i n e di ne m b e d d e ds y s t e m s t oi m p r o v e e n e r g ye f f i c i e n c yo ro p t i m i z es y s t e mp e r f o r m a n c ei sah o ts u b j e c ti np r e s e n tr e s e a r c h d o m a i no fl a wp o w e ri nr e a l - t i m es y s t e m s i nt h i sp a p e r , r e a l - t i m ef a u l tt o l e r a n t s c h e d u l i n gb a s e do ni c mw h e ne n e r g yi sc o n s t r a i n e di si n v e s t i g a t e d ，a n dan e w s c h e d u l i n gm e t h o di sp r o p o s e dt ob e t t e rt h es y s t e mp e r f o r m a n c e t h en e wm e t h o d s e l e c t st h eo p t i o n a lp a r to ft h et a s ki nl i g h to fp r i o r i t yo fe n e r g yd e n s i t yo f f l i n e ，w h i c h c a no p t i m i z es y s t e mp e r f o r m a n c e b yt h ed y n a m i cr e c l a i m i n ga l g o r i t h m ，t h es y s t e m p e r f o r m a n c ei sf t u r t h e ri m p r o v e da tr u n - t i m ew i t hs u r p l u se n e r g y k e yw o r d s ：r e a lt i m es y s t e m s ，e m b e d d e ds y s t e m s ，f a u l tt o l e r a n c e ，l o w e rp o w e r , t a s ks c h e d u l i n g 第i i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 各抽象层的低功耗技术划分。1 3 表3 1 k - 2 5 时，检查点个数与能耗对比2 6 表3 2k = 5 时，检查点个数与能耗对比2 7 表3 3k = 1 0 时，检查点个数与能耗对比一2 8 表3 4p = o 0 0 5 时，n 与k 和仃的关系。2 9 表3 5p = 0 0 3 时，刀与k 和盯的关系3 0 表4 1 任务集t 的属性3 4 表4 2k u 与乃( a ，) 和r i 的关系( ，= 2 5 ) 。3 6 第页 国防科学技术大学研究生院学位论文 图目录 图1 1 嵌入式系统路线图2 0 0 2 1 2 4 1 j 4 图1 2s e m b d m r 结构图【2 7 1 5 图1 3r p r 结构图【2 8 】6 图1 4 论文结构8 图2 2 检查点原理图1 1 图2 2 不同层次功耗优化技术效率比较1 4 图2 2 均匀检查点d v s 算法【8 】l 7 图2 3 非均匀检查点d v s 算法【3 】1 8 图4 1 算法结构概略图。3 4 图4 2 任务集t 的依赖关系示意图3 4 图4 3 当骂篝簪= 5 ，各算法的能耗比较4 0 图4 4 当u 耐= 6 0 ，各算法的能耗比较4 0 图5 1e r 。- - 1 0 和u = 1 2 0 时，厂与e 坤，的关系5 4 图5 2e r ，= 0 4 和u = 1 2 0 时，c l r 与e h 如| 的关系5 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料：与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：盘i 蒸垒塑塾查叁重! 兰鱼垡生兰! 鱼垄鱼查堑差 学位论文作者签名：亟堑銎日期：p 年，月善l 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：芝丛垒竺望垒叁丝生丝丝差兰! 璺垒型堑羞 学位论文作者签名： 作者指导教师签名： 傀内窆 啤 日期：，f 年，月吨日 日期：川年月砂日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 研究背景 1 1 1 实时嵌入式系统 实时嵌入式系统( r e a l t i m ee m b e d d e ds y s t e m s ) ，是指同时具有嵌入式系统和实时系统 特征的计算机系统。 嵌入式系统( e m b e d d e ds y s t e m s ) ，全称嵌入式计算机系统，是指以应用为中心、以计 算机技术为基础、软硬件可裁剪、适应应用环境对功能、实时性、可靠性、成本、体积、 功耗等严格约束的专用计算机系统。嵌入式系统的基本特性是以应用为中心，系统的功能、 性能、组成和表现形式都按照应用需求确定，具有运行环境千差万别、硬件平台丰富多样、 软硬件高度融合、系统资源有限、运行稳定可靠等特点【3 0 】。 实时系统( r e a l t i n es y s t e m s ) ，全称实时计算机系统，是指必须在其运行环境规定的时 间范围内响应环境激励的计算机系统。实时系统的正确性不仅依赖于系统计算的逻辑结 果，还依赖于产生输出结果的时间。实时系统的基本特性是响应时间的确定性或可预测性。 嵌入式系统一般都有较强的实时要求，而实时系统也一般都置身于应用环境之中，常 见的嵌入式系统或实时系统常常同时具有实时系统和嵌入式系统的特征，因此实践中嵌入 式系统或实时系统往往均是指实时嵌入式系统。本文以下若无特殊说明，嵌入式系统或实 时系统就是指实时嵌入式系统。 嵌入式系统一般由嵌入式微处理器( 主要由1 6 位及1 6 位以上的微处理器、微控制器 和数字信号处理器组成) 等硬件及专用软件( 包括实时操作系统和实时应用程序) 组成。 它通常以片上系统( s y s t e mo nc h i p ，简称为s o t 3 ) 、板上系统( s y s t e mo nb o a r d ，简称为 s o b ) 、嵌入式p c 等形式嵌入到各式各样的设备或大系统中作为设备或大系统的处理和控 制核j t ) , t 3 0 j 。 嵌入式系统已普遍应用于国防、航空航天、数字家庭、工业自动化、汽车电子、医学 科技、消费电子、无线通讯、电力系统等国民经济的主要行业。随着嵌入式技术的发展， 嵌入式系统将更广泛地应用于人类生活的方方面面。 1 1 2 嵌入式系统的功耗能耗问题 近年来，集成度和时钟频率的大幅提高导致集成电路的功耗越来越大，系统的功耗 能耗问题日益严重。例如a l p h a 2 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 | 3 1 。全球桌面处理器的总功耗在1 9 9 2 年为 第1 页 国防科学技术大学研究生院学位论文 1 6 0 m w ，在2 0 0 1 年已经达到了9 0 0 0 m w 2 | 。功耗大不仅引发难以解决的散热问题，而且 限制了处理器主频的进一步提高。对于电池供电的嵌入式设备，功耗问题尤为突出。嵌入 式设备的发展和广泛应用，相对于发展缓慢的电池技术，是驱动低功耗技米研究的主要动 因。 更具体地说，低功耗能耗设计技术发展的因素主要来源于以下几个方面【4 】： 1 电池供电设备的需求。 电池的供电时间是衡量系统好用性的重要参数，但电池受重量和体积的限制，储能能 力有限。低能耗设计有助于减轻设备所携带电池的容量和重量，这对于空间、重量和能量 受限的嵌入式应用是非常重要和有意义的。 2 系统可靠性。 功耗增加所引起的芯片温度升高将会增加故障发生的可能性，降低整个系统的可靠 性。对于嵌入式系统，高功耗带来的高发热量往往超出目前系统的散热能力，高温会导致 系统运行不稳定，可靠性下降。 3 系统封装和冷却的成本问题。 功耗增加会显著提高系统的发热量，这一方面需要发展相应的封装、冷却技术，另一 方面产品还必须为增加封装、冷却的设备而提高成本。 多数实时系统都有着严格的功耗能耗约束。最为普遍的情形是，嵌入式系统对于功耗 一般有着严格要求，而绝大部分嵌入式系统都是实时系统。如何在满足系统实时性要求的 前提下尽可能地降低其能耗已成为目前实时系统设计所面临的新挑战。嵌入式系统功耗研 究具有深远的战略意义，1 9 9 7 年美国全国咨询中心( n a t i o n a lr e f e r r a lc e n t e r ，简称n v c ) 研究表明功耗需求是“下下一代陆军 ( a r m ya f t e r n e x t ，简称a a n ) 的主要障碍，1 9 9 9 年美国d a r p a 开始了“p a c c ( p o w e r - a w a r ec o m p u t i n ga n dc o m m u n i c a t i o n s ) 计划第 一期项目，2 0 0 1 年紧接着又启动了“p a c c ”计划第二期研究项目【3 0 】。该计划支持从芯片 设计、编译技术、操作系统、网络通信、实时系统、分布式系统到应用工程各层次各方面 的功耗管理研究。可见嵌入式系统功耗研究对提升国家核心竞争力、掌握高科技前沿技术 具有不可忽视的战略意义。 1 1 3 嵌入式系统的可靠性 近年来，嵌入式系统的可靠性，尤其是暂时性故障的容错问题引起了人们的极大关注， 可靠性已经像低功耗一样成为业界关注的热点。i t r s ( i n t e r n a t i o n a lt e c h n o l o g yr o a d m a po n s e m i c o n d u c t o r s ) 预测可靠性需求将成为未来几年里一个重要的设计参数1 3 】。随着集成电路 工艺的进步，嵌入式系统的暂时性故障率s e r ( s o f t ：e r r o rr a t e ) 将急剧增加，其原因包括 以下几方面因素：晶体管工作电压的减小降低了集成电路噪声容限，使芯片更易受暂时 性故障影响；处理器主频的提高使其故障率增加：集成度的提高使芯片中晶体管数量 第2 页 国防科学技术大学研究生院学位论文 呈指数性增长，使整个芯片的故障率增加。据s h i v a k u m a r 等人预测，从1 9 9 2 2 0 1 1 年芯片 暂时性故障率将增加9 个数量级，也就是说那时由于空间粒子辐射等因素造成的芯片暂时 性故障率可以与现在不加任何防护措施的存储器相比【5 1 。传统上一般认为只有在空间应用 中才会考虑单粒子翻转s e u ( s i n g l e e v e n tu p s e t ) ，但是随着工艺的不断向前推进，s e u 也逐渐成为地面应用需要考虑的因素之一1 6 j 。 大多数嵌入式系统都是用于实时应用，除了工艺等因素导致故障率上升影响系统可靠 性外，实时系统的工作环境和本身的实时性需求也要求实时系统必须具备较强的容错能 力。许多实时系统的工作环境非常恶劣，各种干扰使实时系统发生暂时性故障的概率很高； 在恶劣环境下工作的实时系统发生永久性故障的频率也高于一般系统，航天实时控制系统 就是一个典型的例子。另外，虽然目前的软硬件设计技术得到了长足发展，但是仍然不能 够保证生产出的计算机系统中不存在任何缺陷。在很多关键性的控制领域中，如果系统运 行结果不能符合预期需求，将可能导致严重的后果，甚至会危及人员伤亡。对一些非关键 实时应用而言，虽然丢失时限不会引起像硬实时应用那么严重的后果，但可能会导致系统 性能或服务质量( q o s ) 的严重下降，在有些时候这也是不可以接受的。因此，实时系统 的容错是十分重要的问题，对实时容错系统的研究已经成为当前实时系统研究领域中的重 要课题与研究方向。 1 1 4 嵌入式系统容错与低功耗的融合 从上面两小节的概述可知，功耗能耗限制和可靠性需求是实时嵌入式系统的重要挑战 和设计约束。低功彬能耗技术和容错技术在实时嵌入式系统中有着重要的意义，长期以来 它们都是被作为两个相互独立的领域进行研究，最近才有一些国外的学者将二者结合起来 进行考虑和研究【1 2 j 【1 4 1 ，而且受到学术界越来越多的重视【9 】【1 0 】【1 1 1 8 2 0 1 ，但目前国内还很少见 到这方面的研究工作和论文。 在实时嵌入式系统，容错技术与低功耗技术相融合的主要背景和产生的原因可以归结 为以下两点： 1 许多嵌入式系统往往同时具有功耗能耗限制和容错需求。 。 在 v l s i 工艺进入深亚微米技术时代，随着故障率急剧上升和功耗的增加，容错和低 功耗问题显得尤为突出。图1 1 是p r o g r e s s s t w ( 一个命名为“嵌入式系统和软件研究计 划 的国际研究项目) 的报告“e m b e d d e ds y s t e m sr o a d m a p ：i n t e r a c t i o n 的一部分阱】。该 图明确地说明，功耗问题和可信性是嵌入式系统的主要挑战。嵌入式系统的资源受限的特 点和应用需求决定了许多嵌入式系统往往同时具有功耗限制和容错要求，不但应用于安全 关键领域的嵌入式系统如卫星系统、导航控制系统等必须同时具备功耗约束和高可靠性， 而且随着工艺的进步，一些非关键领域的嵌入式应用如消费电子和无线传感网等也同时提 第3 页 国防科学技术大学研究生院学位论文 出了容错和低功耗要求【2 5 1 。因此，在嵌入式系统中，将容错技术与低功耗技术相融合具有 广泛的应用前景。 i2 0 0 2 卜一2 0 0 5 | _ 一2 0 0 8 卜一2 0 1 1 i 、_ - - - - _ _ _ _ 、_ _ _ _ 、_ _ _ - - _ 图1 1 嵌入式系统路线图2 0 0 2 【2 4 】 2 容错需求与低功耗要求往往存在冲突。 实时嵌入式系统的最优目标是希望能同时具备容错、能耗低和时限响应强等优点。然 而由于容错、能耗和时限响应性存在内在的矛盾，这一最优目标在现实中往往难以达到。 首先，目前的许多低功耗技术常常采用d v s ( d y n a m i cv o l t a g es c a l i n g ，动态电压调节) 来实现，而d v s 本身又会导致处理器速度下降，这将威胁到时限响应性；其次，基于时 间冗余的容错技术将引入额外的时间开销，从而增加任务的执行时间，这又影响到任务的 及时完成：第三，能耗和容错也存在均衡考虑的问题。如果为了节能降低处理器的速度， 将导致可用的冗余时间减少，从而影响容错能力。此外，国外一些学者的最新研究成果显 示，供电电压的降低将引起暂时性故障率上升。有研究报告指出，当电压下降1 v ，s e u 率要增加1 到2 个数量级【2 6 】。 1 2 研究现状 低功耗技术可以在系统设计的不同抽象层上实现，如电路层、体系结构层、编译层、 系统层和网络层等。同样容错技术也可以在硬件层、体系结构层、软件层等实现。因此， 容错与低功耗的融合也可以在不同层次上展开。下面分别从硬件层和软件层( 系统层) 介 绍目前容错与低功耗融合的研究现状，重点介绍一些典型的技术和应用。 1 2 1 硬件层容错与低功耗的融合 1 低功耗f p g a 容错技术 随着应用需求的提高和f p g a 技术的发展及其成本的降低，目前许多嵌入式系统或者 第4 页 国防科学技术大学研究生院学位论文 采用了f p g a 部件，或者直接基于f p g a 构建。基于s r a m 的f p g a 由于具有开发成本 低、上市时间短和可再编程能力强等特点在空间应用等关键领域应用迅速增长。工艺尺寸 不断缩小既使f p g a 的速度越来越快，同时也使其可靠性降低。应用于空间领域的f p g a 特别易受暂时性故障的影响，目前许多f p g a 都采用t m r ( 三模冗余) 来提高可靠性，由 于需要3 倍的逻辑和额外的选举控制电路，t m r 的面积和能耗至少是原电路的3 倍。鉴 于空间应用的重要性和特殊性，许多学者开始研究低功耗f p g a 容错技术。 文献【2 7 】提出了一种基于s e m b ( s y n c h r o n o u se m b e d d e dm e m o r yb 1 0 c k ) 实现的有限 状态机f s m ( f i n i t es t a t em a c h i n e ) ，每个f s m 都由两个s e m b 来实现，称为s e m b d m r 结构，如图1 2 所示。通过增加一个校验位和周期性的字重写，能够避免暂时性故障，增 强可靠性，而且能使能耗比传统的t m r 低很多。 图1 2s e m b - d m r 结构图【2 7 】 文献【2 8 】提出了r p r ( r e d u c e dp r e c i s i o nr e d u n d a n c y ) 结构。其主要思想是：复杂度 与可靠度往往是矛盾的，精度越高实现越复杂，可靠性越低。在很多应用中，精确值虽然 更好但有时并不必要，精度稍低的值比精度高但可能出错的值更重要。r p r 的结构类似于 金字塔，分为底层、中间层和顶层，如图1 3 所示，底层是计算单元，能达到应用要求的 最高精度，称为精确模块；中间层由二个或二个以上的单元组成，可完成与精确模块相同 的基本功能，只是精度要低些；项层模块是选举单元，决定底层与中间层模块输出的计算 结果中哪个最可能是正确的且应该作为整个r p r 的输出。在普通环境，r p r 可提供与t m r 等同的性能；在高辐射环境，r p r 的可靠性或精度虽然可能要比t m r 低，但由于占用的 资源更少，r p r 的总体效率要比t m r 高。r p r 节省资源的能力主要取决于冗余模块需达 到的计算精度。 第5 页 国防科学技术大学研究生院学位论文 图1 3r p r 结构图1 2 3 】 o u t p u t 2 低功耗c a c h e 容错技术 c a c h e 对计算机系统的性能有重要的影响，许多学者对c a c h e 中的功耗与容错交互问 题进行了深入研列5 1 。z h a n g 等人提出一种通过保护复制数据实现低功耗的机制【4 3 】；s o m a n i 等人对使用频率高的c a c h e 行进行保护降低功耗 4 4 1 ；l i 等人在电路级和微结构级研究可信 性与低功耗的交互与均衡问题，并提出一种自适应的、利用不同复杂度编码实现对c a c h e 中干净数据( c l e a n ) 和脏数据( d a v y ) 保护的机制【4 5 】。 1 2 2 软件层容错与低功耗的融合 在软件层实现容错与低功耗融合是目前研究的重点之一，研究主要集中在容错与节能 相结合的任务调度，又可以分为低功耗的容错技术【8 】【1 0 】【1 1 】【1 2 】和容错约束下的节能调度技术 【2 0 】【2 1 】【2 2 】( 2 3 1 两个主要方向。低功耗容错技术的主要思想是，采用系统层功耗管理技术如d p m ( d y n a m i cp o w e rm a n a g e m e n t ，动态功耗管理) 和d v s 来降低一些传统的容错技术如检查 点和任务重复( 即多模冗余) 等的系统能耗。容错约束下的节能调度与一般的节能调度最 大不同之处是，它基于d v s 技术本身会引起暂时性故障率上升，即对可靠性有负面影响 这一前提来进行节能调度，采用预留恢复任务或检查点的技术来补偿由于d v s 技术本身 对系统可靠性的负面影响。本文将在第二章中详细分析目前实时系统容错与节能相结合调 度技术的研究现状。 1 3 1 现有工作的不足 1 3 研究内容 从上一小节可以看出，实时系统容错与节能的融合可以在不同层次上实现。由于实时 系统往往资源受限，基于硬件冗余容错的开销比较大，因此，实时系统中常采用基于时间 第6 页 国防科学技术大学研究生院学位论文 冗余的方法( 重试或重执行) 进行容错。低功耗技术可以在不同的抽象层次上实现，并且 抽象层次越高，节能效率越高。目前，实时系统主要采用系统层的d p m 和d v s 来降低功 耗。操作系统支持的任务调度机制能有效地将基于时间冗余的容错和d v s 节能技术有机 结合起来，从任务调度角度来研究容错与低功耗的融合是目前该领域的重点。基于此，本 文从任务调度来研究容错实时嵌入式系统的功耗问题。 根据对目前研究现状的总结可以发现，在容错与节能相结合的任务调度技术的研究中 主要存在以下不足： 1 大多数基于检查点的d v s 容错节能技术研究没有考虑d v s 技术对暂时性故障率的 影响【8 】【1 0 1 1 1 】【1 8 1 。此外，许多研究只考虑了检查点的时间开销，而忽视了检查点的功耗开销 【8 】 o 2 目前的容错节能算法大多是静态算法，没有充分利用系统的空闲时间，而其他一些 动态算法往往计算复杂，在线计算时间开销比较大。 3 具有能量约束的实时任务调度是目前实时系统低功耗研究的热点之一。如何在有限 的能量预算下设计一些调度策略来提高系统性能( 如可靠性) 是一个迫切需要解决的问题， 但目前关于这方面的研究还比较少。 ? ： 4 任务模型比较单一，对周期任务研究得多，对非周期任务研究得少；对硬实时任务 研究得多，对软实时任务研究得较少；对实时任务研究得多，对非实时任务研究得少。 5 对算法的验证，采用仿真和模拟得较多，而通过真实实验得相对较少；对调度算法 和调度策略研究得较多，对操作系统的支持机制及如何在工程实践去应用研究得相对较 少。 1 3 2 研究内容 从上一小节可知，目前容错与节能相结合的任务调度技术研究已经取得了一定的进 展，但是也存在一些还没有很好解决或是还没有研究的问题。由于时间限制、课题的工作 量以及可参考的资源相对较少，本课题不大可能针对上述总结的所有目前研究存在的问题 与不足进行研究，而只是选取了其中的一些问题进行研究。总体而言，本课题主要围绕实 时系统容错与节能相结合的任务调度技术，作了以下几个方面的研究工作： 1 总结和分析了目前实时系统主流的容错技术和节能调度技术，比较全面和深入地剖 析了出现容错与节能相融合这一趋势的背景、原因和发展过程，重点总结了容错与节能相 结合任务调度技术的研究现状。 一 2 目前容错与节能相结合的调度技术大多围绕检查点和d v s 技术展开。许多相关研 究只考虑了检查点的时间开销，而没有考虑检查点的功耗开销。本文从检查点实现过程、 动态功耗组成及d v s 原理等方面研究认为在某些情况下检查点的功耗开销必须要加以考 虑。建立了检查点的功耗模型，并分析和讨论了在该模型下，检查点功耗开销对最优检查 第7 页 国防科学技术大学研究生院学位论文 点个数和节能效率的影响，还分析了检查点的功耗开销与时间开销及任务的处理器利用率 之间的关系。 3 针对目前实时嵌入式系统d v s 容错算法中离线算法实现简单、开销小，但对空闲 时间的利用过于保守，而在线算法空闲时间利用率高，但在线计算开销大、计算复杂等不 足，本文提出了一种准静态的容错节能调度算法，它能以较低的在线时间开销达到近似在 线算法的性能。同时本文还考虑了d v s 本身对故障率的影响，任务可以具有不同的可靠 度。此外，目前许多随机的d v s 算法的功耗模型过于理想，忽略了电压切换的时间开销 和能耗开销，本文的d v s 算法采用了更符合实际的d v s 模型。 4 嵌入式系统在能量约束时，最大化能量的利用率或优化系统性能是非常重要的。本 文研究了基于i c m 容错模型的有能量约束时的任务调度问题，提出了一种综合考虑任务的 关键程度和能耗需求来对任务进行选择和调度的算法，在保证指定等级容错能力的条件 下，通过静态最优能量分配和动态资源回收来优化系统能量的利用率和提高系统性能。 1 4 论文结构 本文的主体内容共分为六章，论文结构如图1 4 所示。 第一章，绪论，主要介绍课题的研究背景、研究现状和研究内容。 第二章，相关技术分析，主要介绍实时系统的容错技术和低功耗技术，重点分析实时 系统容错与低功耗结合的任务调度技术的研究现状。 第三章，检查点功耗开销的研究与分析。 第四章，研究实时系统中容错约束下准静态节能调度算法。 第五章，研究基于i c m 容错模型的有能量约束的实时任务调度算法。 第六章，小结与未来工作展望。 第意 1 第章 l i 第三章 il 第四章第? i i 章 、 第六章 图1 4 论文结构 第8 页 国防科学技术大学研究生院学位论文 第二章实时系统的容错技术与低功耗技术分析 2 1 引言 本章分析实时系统主流的容错技术与低功耗技术，作为后续章节的基础。首先，介绍 实时系统的容错技术，重点分析目前实时系统广泛应用的检查点技术。其次，介绍实时系 统的低功耗技术，重点分析基于d v s 的节能调度技术。最后，分析实时系统中容错与低 功耗相结合调度产生的背景和原因，全面和深入地总结容错与低功耗相结合任务调度技术 的研究现状。 2 2 1 容错技术概述 2 2 实时系统的容错技术 提高计算机系统可靠性的主要技术手段包括：避免错误、消除错误、容错和规避错误。 在实时系统运行过程中，容错是最重要的可靠性保障手段。 1 故障模型 故障模型是容错技术研究的基础，确立合理的故障模型才能对故障进行正确的检测和 诊断。根据故障的持续时间和产生故障的原因，可以将故障分为以下几种类型【2 9 】： ( a ) 永久性故障：指永久持续下去直到修复为止的故障。对硬件而言，永久性故障意 味着不可逆的物理变异，如连接线断开；对软件而言，这种故障往往是由于程序设计中固 有的又必须执行的缺陷代码引起的。 间歇性故障：指故障是短暂的又是断续的，它既有其短暂性，又有其不定期重复 性。比如一个虚焊点可能引起电路输出处于临界状态而时好时坏；而对软件而言，程序由 于某一个输入进入一个有错误的分支也能产生这样的故障。 ( c ) 暂时性故障：又称为瞬态故障，指故障出现是暂时的，并且可能是非重复性的。 环境变化、电源干扰、元器件性能波动、软件输入变化以及电磁干扰等因素都可能引起暂 时性故障。这种故障可能只出现一次，也可能很长时间出现一次。 统计数据表明，间歇性故障和暂时性故障占整个故障的很大比例。m m 的一项报告指 出，这两种故障占所有现场失效故障的9 0 ，因此在进行容错技术研究和容错计算机系统 设计时，应着重解决间歇性故障和暂时性故障的容错处理问题。 2 冗余技术 资源冗余是实现容错的重要手段，目前所有的容错技术几乎都是利用冗余技术来实现 的。冗余技术主要有以下几种不同类型： 第9 页 国防科学技术大学研究生院学位论文 ( a ) 硬件冗余：利用硬件进行故障容错处理，主要有以下两种方式： ( 1 ) 静态冗余：又称故障屏蔽技术，就是将发生故障的元件或部件屏蔽。由于这种方 法采用多个模块同时工作，自动屏蔽故障元件，因此不需要在容忍故障前检测故障，实时 性较好。经典的n 模冗余( n m r ) 容错模型就是静态冗余结构的代表。 ( 2 ) 动态冗余：又称系统重组技术，与静态冗余不同，动态冗余系统由若干模块组成， 但只有一个模块工作，发生故障时首先要求及时检测到故障发生，并能够正确定位故障， 之后利用备用模块取代当前故障模块，完成容错切换过程。 ( b ) 软件冗余：利用软件方法实现故障处理，是硬件冗余思想在软件容错技术上的体