（计算机软件与理论专业论文）一种反馈控制机制在edf算法上的应用.pdf

太原理工大学硕士研究生学位论文 一种反馈控制机制在e d f 算法上的应用 摘要 实时调度算法是嵌入式实时系统设计和实现的关键问题之一，也是保 障实时系统两个必备特性( 时限性和可靠性) 的重要方法，是实时系统中重要 而活跃的研究领域。 在众多的实时调度算法中，速率单调( r a t em o n o t o n i c ，r m ) 和最早截止 期限优先( e a r l i e s td e a d l i n ef i r s t ，e d f ) 分别是静态调度和动态调度领域中经 典的调度算法。r m 算法属于静态调度算法，在系统运行前决定任务的调度， 实现简单，在满足前提条件的情况下可以保证实时任务集的成功调度。e d f 算法属于动态调度算法，在系统运行时决定任务的调度，c p u 利用率可以 达到1 0 0 ( 理想情况下) 。虽然r m 和e d f 算法以其各自所具备的优良性 能在嵌入式实时系统中得到了广泛应用，但是我们也不能忽视它们本身存 在的实时性问题。 虽然一些改进后的算法能支持更复杂的任务集特性，但这些算法都是 开环的调度算法。开环就意味着一旦调度器被创建，它们就不能基于持续 的反馈进行调整了。尽管开环调度算法在负载精确建模的静态或动态系统 中执行良好，但是该类算法在不可预测的动态系统环境下性能却较差。 本文是在考虑“系统过载 的情况下，通过在e d f 调度算法中引入反 馈控制机制来提高e d f 调度算法的实时性及稳定性。 首先介绍实时调度算法的应用背景：实时系统、嵌入式系统、实时操 作系统和嵌入式实时操作系统。 接着对现有的实时调度模型、实时调度基本理论、调度策略和实时调 度算法进行了分析和研究。对r m 和e d f 实时调度算法进行了详细分析， 并举例说明了它们的调度过程。 然后介绍了本文提出的反馈控制机制用到的相关理论一比例一积分微 太原理工大学硕士研究生学位论文 分( p r o p o r t i o n a l i n t e g r a l d e r i v a t i v e , ri d ) 自动控制理论和操作方法，并说明了单神 经元智能控制的基本理论。 最后，通过使用自适应单神经元p i d 算法对e d f 调度算法进行动态反 馈控制，动态调整过载时系统中的任务数量，运用每次运行获得的截止期错 失率作为下一次运行的输入参数进行实时任务调度，以此来提高实时系统 的实时性和稳定性，达到有效改善过载的目的。本文模拟了基于p i d 反馈控 制机制的最早截止期限优先调度算法，并比较了引入反馈控制机制前后的 实验情况。实验结果表明：引入自适应单神经元p i d 反馈调度算法可以快 速稳定并积极改善实时系统达到过载时的情况，可以优化系统降级时的性 能。说明了使用p i d 反馈控制对改善e d f 调度算法执行情况的可行性和有 效性。该结论对实时调度算法的研究和使用有一定的理论和实践意义。 本文的创新之处在于引入了单神经元p i d 反馈控制机制，使反馈控制 更具智能型，实现了自适应单神经元p i d 控制算法在嵌入式实时调度算法 领域的运用。 关键词：嵌入式实时系统，实时调度，e d f 调度算法，自适应单神经元p i d 反馈控制 太原理工大学硕士研究生学位论文 af e e d b a c kc o n t r o ls c h e m ea p p l ! dt oe a r l s t d e a d l ef i r s ts c h e d u l 玳ga l g o r i t h m a b s t r a c t r e a l t i m es c h e d u l i n ga l g o r i t h mi so n eo fm a j o rd e s i g ni s s u e sf o re m b e d d e d r e a l t i m es y s t e m s i ti sa l s oa l li m p o r t a n tm e t h o dt og u a r a n t e et i m ec o n s t r a i n s a n dr e l i a b i l i t yf o rr e a l t i m es y s t e m s ，a c t i v e l yb e i n gr e s e a r c h e di nt h i sf i e l d a m o n gt h es c h e d u l i n ga l g o r i t h m s ，r m ( r a t em o n o t o n i c ) a n d e d f ( e a r l i e s td e a d l i n ef i r s t ) a r et w oc l a s s i c a ls c h e d u l i n ga l g o r i t h m s r mi sag o o d a l g o r i t h mi nt h ef i e l do fs t a t i cs c h e d u l i n g r md e c i d e dt a s ks c h e d u l i n go r d e r b e f o r es y s t e mr u n n i n g ，a n di ti se a s yt oc a r r yo u t i fp r e c o n d i t i o n sa r em e t ，r m c a l ls c h e d u l er e a l t i m et a s ks e t ss u c c e s s f u l l y e d fi sag o o da l g o r i t h mi nt h e f i e l do fd y n a m i cs c h e d u l i n g e d fd e c i d e dt a s ks c h e d u l i n go r d e rd u r i n gs y s t e m r u n n i n g t h ec p uu t i l i z a t i o no fe d fs c h e d u l i n ga l g o r i t h mc a nb e1 0 0 i n p e r f e c tc o n d i t i o n a l t h o u g hh a v i n gn o t i c e dt h a tr ma n de d fd oh a v eg o o d p e r f o r m a n c ea n db r o a d l yu s e di ne m b e d d e dr e a l t i m es y s t e m s ，w ec a nn o t i g n o r et h es h o r t c o m i n g so fr e a l t i m ep e r f o r m a n c eo f t h et w oa l g o r i t h m s w h i l es o m ei m p r o v e de a r l i e s td e a d l i n ef i r s ta n dr a t em o n o t o n i c s c h e d u l i n ga l g o r i t h m sc a ns u p p o r tm o r es o p h i s t i c a t e dt a s ks e tc h a r a c t e r i s t i c s ， t h e ya r es t i l la l lo p e nl o o ps c h e d u l i n ga l g o r i t h m s o p e nl o o pm e a n st h a to n c e s c h e d u l e sa r ec r e a t e dt h e yc a nn o ta d j u s tt h e m s e l v e sb a s e do nc o n t i n u o u s f e e d b a c k w h i l eo p e n l o o ps c h e d u l i n ga l g o r i t h m sc a np e r f o r mw e l li ns t a t i co r d y n a m i cs y s t e m sw h e r et h ew o r k l o a d sa r ea c c u r a t e l ym o d e l e d ，m e ys t i l lc a n p e r f o r mp o o r l yi nu n p r e d i c t a b l ed y n a m i cs y s t e m s i nt h ec o n s i d e r a t i o no fs y s t e mo v e r l o a d ，af e e d b a c kc o n t r o ls c h e m ei s 1 1 i 太原理工大学硕士研究生学位论文 i n t r o d u c e di nt h i st h e s i st oe n h a n c et h er e a l t i m ep e r f o r m a n c ea n ds t a b i l i t yo f e d f s c h e d u l i n ga l g o r i t h m f i r s t l y , t h eb a c k g r o u n d ( r e a l t i m es y s t e m ，e m b e d d e ds y s t e m ，r e a l t i m e o p e r a t i n gs y s t e ma n de m b e d d e dr e a l t i m eo p e r a t i n gs y s t e m ) o fr e a l - - t i m e s c h e d u l i n ga l g o r i t h m sw a si n t r o d u c e d s e c o n d l y , r e a l t i m es c h e d u l i n gm o d e l s ，t h eb a s i ct h e o r yo fr e a l t i m e s c h e d u l i n g ，r e a l t i m es c h e d u l i n gs t r a t e g i e sa n dr e a l t i m es c h e d u l i n ga l g o r i t h m s w e r ed e s c r i b e d r ma n de d fw e r ed i s c u s s e di nd e t a i la n ds o m ee x a m p l e sw e r e u s e dt oe x p l a i nt h e i rs c h e d u l i n gp r o c e s s e s t h i r d l y , t h ec o r r e l a t e dt h e o r yu s e df o ro u rf e e d b a c ks c h e m ep r o p o s e di n t h i sp a p e rw a si n t r o d u c e d i ti so np i d ( p r o p o r t i o n a l - i n t e g r a l d e r i v a t i v e ) i n a u t o c o n t r o lt h e o r ya n do p e r a t i o nm e t h o d t h et h e o r yo n s i n g l en e u r a le l e m e n t s e l f - a d a p t i v ep i dm e t h o dw a sa l s oi l l u s t r a t e d f i n a l l y , i tc a nb ea c h i e v e dt h a to v e r l o a ds i t u a t i o nc a nb ei m p r o v e dt h r o u g h u s i n gs i n g l en e u r a le l e m e n ts e l f - a d a p t i v ep i da l g o r i t h mt om a k ef e e d b a c k c o n t r o lo ne d fs c h e d u l i n g i tc a nd y n a m i c a l l ya d j u s tt a s kn u m b e ri no v e d o a d s y s t e ma n du s et h er e c e i v e dd e a d l i n em i s sr a t i of o re a c hr u n n i n ga st h ei n p u t p a r a m e t e rf o rn e x tr e a l t i m es c h e d u l i n g w es i m u l a t e dae d fs c h e d u l i n gw i t ha p i df e e d b a c kc o n t r o ls c h e m e ，t h e nc o m p a r e dt h ee x p e r i m e n t sb e f o r ea n da f t e r i n t r o d u c e ds u c hf e e d b a c kc o n t r o ls c h e m e t h er e s u l t ss h o wt h a tt h ei n t r o d u c e d s i n g l en e u r a le l e m e n ts e l f - a d a p t i v ep i da l g o r i t h mc a nf a s ts t a b i l i z ea n d a c t i v e l yi m p r o v et h er e a l t i m es y s t e mo v e r l o a d e d ，a n do p t i m i z et h ep e r f o r m a n c e w h e ns y s t e md e g r a d e d i tp r o v e st h ef e a s i b i l i t ya n dv a l i d a t i o no ft h ep i d f e e d b a c kc o n t r o ls c h e m ef o re d fs c h e d u l i n g t h ec o n c l u s i o n so ft h i st h e s i sc a n b er e f e r e n c e df o rt h e o r ya n da p p l i c a t i o no fr e a l t i m es c h e d u l i n ga l g o r i t h m t h ei n n o v a t i n go ft h i st h e s i si st h a ti n t r o d u c i n gs i n g l en e u r a le l e m e n t s e l f - a d a p t i v ep i ds c h e m et om a k ef e e d b a c kc o n t r o lo nr e a l t i m es c h e d u l i n gb e i v 太原理工大学硕士研究生学位论文 m o r ei n t e l l i g e n ta n di m p l e m e n t i n gt h i sa l g o r i t h ma p p l i e di ne m b e d d e dr e a lt i m e s c h e d u l i n g k e yw o r d s ：e m b e d d e dr e a l t i m e s c h e d u l i n ga l g o r i t h m ， p i d v s y s t e m ，r e a l t i m es c h e d u l i n g ，e d f s i n g l en e u r a le l e m e n ts e l f - a d a p t i v e 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：鲻 日期：趔垂皇篁旦! 鲤 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；。学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签 名。：蝼各 日期：兰堕玺翊幽 导师签名：二童旺日期：一 太原理l ：人学硕十研究生学位论文 1 1 选题背景 第一章绪论 实时。i 生( r e a l t i m e ) 是指系统能够在限定时间内完成任务并对外部事件做出及时响应。 限定时间的范围因实时应用要求的不同而有较大的变化，可以从微秒级到分钟级。实时 与快速是有区别的，实时要求快速，但实时不等于快速，快速是无时间限制的，是从事 件发生到系统响应之间的时间越短越快越好。虽然实时也给人们快速的感觉，并且它也 要求系统在一定程度上能快速响应。但是，实时是有时间余量和时间期限的。 实时任务( r e a l t i m e t a s k ) 是指在时间期限内启动，在规定时间内完成的任务。实时系 统与非实时系统的本质区别就在于实时系统中的任务都有时间限制，实时任务必须在其 截止时问内丌始和完成。截止时间可以划分为开始截止时间和完成截止时问两种。丌始 截止时间要求任务在某个时间内必须丌始执行；完成截止则要求任务在某个时问内必须 完成。 实时系统( r e a l t i m es y s t e m s ) 是指计算的正确性不仅取决于程序的逻辑正确性，也取 决于计算结果产生的时间。如果系统的时间约束条件得不到满足，将会导致系统出错。 实时调度( r e a l t i m es c h e d u l i n g ) 是指在有限的系统资源下，为一系列任务决定何时以 及在哪个处理器上运行，并分配任务运行所需要的资源，以保证其时间和资源得到满足。 调度的实质是资源的分配，包括给任务分配相应的资源和时间从而保证任务的实时性要 求。 实时调度是整个实时系统的重要组成部分，采用调度算法的优劣是实时系统性能的 1 关键。实时调度算法( r e a l t i m es c h e d u l i n ga l g o r i t h m ) 的研究起源于l i u 和l a y l a n d ”1 在1 9 7 3 年提出的单调速率优先算法r m ( r a t e m o n o t o n i ) 币l 最早截止期优先算法e d f ( e a r l i e s t d e a d l i n ef i r s t ) 。他们对这两个算法的可调度性判定条件和调度特性进行了详细的研究， 但在讨论这两个算法时，他们提出了几个前提假设，分别为【2 】： ( 1 ) 所有的任务请求都是周期性的，具有硬时限要求，即必须在限定的时限内完成； ( 2 ) 任务的时限要求仅限于一个任务必须在该任务的下一个请求发生之自i 完成； ( 3 ) 任务之间都是独立的，每个任务的请求不5 依赖于其他任务请求的丌始或完成； 太原理l ：人学硕十研究生学位论文 ( 4 ) 每个任务的运行时l 日j 是不变的，这罩任务的运行时间是指处理器在无中断情况 下用于处理该任务的时间； ( 5 ) 调度和任务切换的时间忽略不计； ( 6 ) 任务之间是可抢占的； ( 7 ) 所有任务的分配都在单处理器上进行。 这些假设条件一方面方便了问题的讨论和模型的建立，但另一方面也限制了整个理 论系统的实用性。随着实时系统的发展，这些限定条件不断遭遇着挑战，为了改善实时 调度性能，产生了很多杰出的研究成果。 抢占的e d f 算法被评估为动态最优调度算法，因其自身的明显优点和缺陷，该算 法在研究应用方面备受青睐。e d f 算法以其理论上系统利用率可达1 0 0 的性能优点在 各种实时系统中有着广泛的应用，例如，实时操作系统，网络通信，多媒体传输，自动 化控制等。e d f 算法的缺点是当系统发生过载时，算法的调度性能会退化很快，甚至会 n 1 引发多米诺效应”。 针对过载问题，到目6 i 己进行了大量以e d f 算法为基础的调度机制的研究工作， r d l 产生了许多有效的改进算法，但这类传统的实时调度算法所遇到的一个普遍问题是， 任务的所有时问约束( 如执行时问、截止期等) 需要精确知道，并在可预测环境下j 能提 供性能保证。然而在许多实际问题中，系统的任务特征通常是模糊不确定的，比如，任 务的执行时间通常是不准确的，从而空闲时间也是不准确的；任务的关键性也是相对的， 通常不太适合用某个确切的数值来区分不同任务之问的关键程度，任务的截止期通常也 不是准确的，它可以在某个范围内随机变化；至于就绪时间、周期等也不是绝对精确知 道的。所有这些特征都可以看成是不确定的。而随着此类问题出现，近年来，实时调度 算法都在不断优化中向着层次化、智能化的方向发展，因此在许多工业控制领域都有着 广泛的应用前景。 本课题主要集中研究e d f 实时调度算法及近年来提出的一些改进算法、及以其为 基础设计的调度控制机制，在深入分析这些研究成果的基础上，将一种反馈控制机制应 用于e d f 算法，以改善实时系统的调度性能。该反馈控制机制的核心是一个单神经元 p i d 算法，使调度控制更具智能性。反馈机制的引入使得该调度比传统调度更接近于实 际，更适用于在实时系统中实现。 本课题是对计算机技术，智能控制理论及其综合运用的探索，希望为将来继续探索 2 太原理工大学硕士研究生学位论文 与研究实时调度方面提供一定的依据。 1 2 实时调度研究现状 随着信息技术，计算机技术和移动技术的发展，世界迎来了一个新的时代，那就是 以嵌入式系统为核心的“后p c 时代 。伴随着电子技术的不断发展和数字信号处理与 人机交互界面等相关技术的不断成熟和完善，嵌入式系统己经有了较好的发展。嵌入式 系统有着无比广阔的市场需求和发展前景。一般来说，嵌入式系统是硬件与软件的结合， 将特定的软件固化在一定的硬件环境上的实用系统。嵌入式软件与嵌入式硬件共同构成 了嵌入式系统。 嵌入式系统通常都具有特定的功能。当我们使用电器，使用手机时，我们都会接触 到一些不同功能的嵌入式系统。绝大多数的嵌入式系统，都具有实时性能的要求，我们 就把这样的系统称为嵌入式实时系统( e m b e d d e dr e a l t i m es y s t e m ) 。同样，一个实时系统 也有可能在资源上受到限制，从而具有嵌入式特性。 随着实时系统应用范围的不断扩大，系统复杂性不断提高，以及应用背景的不同， 对实时调度理论提出了许多新的要求： ( 1 ) 过载运行调度 实践中，有的实时系统不能保证足够的时间来处理所有的任务，无法保证所有的任 务在时间约束内完成，即出现过载运行的情况，此时如何处理和调度任务就非常重要。 在任务调度的研究领域，很多是针对系统过载的情况进行研究的。在实时调度算法中， r 气1 e d f 在正常负载的情况下是动态最优算法，但是l o c k e 的实验显示在过载的情况下 e d f 易导致多米诺效应，其执行性能会急剧降级。b u t t a z z o 等人提出了系统产生过载时 的两种处理机制：保证性和健壮性机制，并对几种基本的调度算法( 包括e d f ) 采用这两 种处理机制后的执行性能进行了比较，结论得出在非过载情况下e d f 算法的性能最优， 而在过载情况下，采用健壮性机制的最大价值密度算法h d f ( h i g h e s td e n s i t yf i r s t ) 性能 最优。该研究还指出，可依据系统处于不同负载的情况选择合适的调度算法，使调度更 具灵活性，为以后的算法过载性能研究提供了一定的指导意义。根据系统处于不同负载 r 钉 时可采用不同的调度算法的思想，s s w a m i n a t h a 等人提出了一种混合调度算法，该算 法将基于价值的调度与截止期的调度相结合，经模拟实验证明，该算法可以对系统处于 3 太原理工大学硕士研究生学位论文 过载时的性能有一定的改善。在这一方面，中国科学院在充分研究e d f 及其他基本调 度算法过载性能的基础上，提出了新的算法框架“。该算法将截止期等任务特征参 f 7 1f r lr 0 1 数集成到一张优先级表中，并以该表作为实时调度的依据。经实验证明，该算法相对 e d f 算法有较大改进，在过载时可以在一定程度上实现性能优雅降级。 针对抢占引入过载的研究方面，k a t c h e r l l 0 1m 1 等人的实验结果表明，在实时系统的 实际实现中，因抢占开销使预期的任务处理器利用率比理想情况低得多。j u k k a n 2 1 3 1 等 人分别改进了l i u 的响应时间分析方法r t a ，将带有偏移量的任务考虑进来，并逐步 降低了算法复杂度。a r v i n d ”1 则在其技术报告中提出了作业响应时间方程，以此来判定 任务抢占次数的界限，并据此修改了e d f 的可调度条件。r e i n d e r 1 5 1 、r e d e l l 1 句n 刀则分 别提出最好情况和最坏情况下的响应时间分析方法，该方法通过优化单个任务的响应时 间以减少此任务被抢占的次数，但不能确定整个任务集发生抢占的次数是否相应减少， 针对此类问题国内研究学者提出了一套对周期性任务的就绪队列进行微调度的抢占模 型n 8 1 ，通过改变抢占关系来减少抢占次数、优化实时系统性能。 ( 2 ) 多处理器调度 多处理器系统是指整个系统内包含有多个处理器单元，各处理器可以同时并发工 作。在多任务单处理器系统中，多个任务在宏观上是并发的，但在微观上是顺序执行的。 在多处理器系统中，多个任务可以分别在不同的处理器上执行，宏观上和微观上都是并 发的。按照多处理器的结构，多处理器系统可以分为紧耦合系统和松耦合系统两种。紧 耦合系统是多个处理器通过共享内存空间来交换信息的系统，而松耦合系统是多个处理 器通过通信链路来链接和交换信息的系统。 现在的计算机也逐步跨进了多核时代。随着实时应用的日趋复杂，多处理器系统因 其高性能和可靠性，逐渐成为处理复杂应用的有效方法。多处理器实时系统的调度算法 是一个重要的研究课题。 单处理器e d f 经理论证明是动态最优的，在系统不过载的情况下，可以达到1 0 0 的c p u 利用率，也正是因为这一点，e d f 调度算法被广泛应用于各种实时系统中。然 而，实际证明，单处理器e d f 算法及其他最优在线调度算法必须在足够快的处理器上 执行才能达到最优性能，若硬件条件不能提供足够快的处理速度，这一点就不能保证1 9 1 。 4 太原理工大学硕士研究生学位论文 在单处理器下得到的e d f 算法是动态最优的结论，在多处理器环境下并不成立。 因为没有最优的多处理器在线调度算法刚，而且多处理器调度比单处理器调度更容易发 生抢占口1 1 ，因此调度多处理器调度算法的研究更复杂。多处理器系统有局部调度和全局 调度两类实时调度方法，关于e d f 的局部调度算法有e i ) f f f ( e d f f i r s tf i o 算法口2 1 ， 全局调度算法有e d f 贪心算法g e d f l 2 3 1 ( g r e e d ye d f ) ( 优先级越高的任务得到的处理器 速度越快) 。 ( 3 ) 实时任务的混合调度 基于前提：系统中存在硬实时的周期任务，且它们的c p u 利用率小于1 ，同时存在 软实时的非周期任务。调度目标是在保证硬实时周期任务截止期的前提下，尽可能的提 高软实时的非周期任务的响应速度。当两种类别不同的任务放在一起进行调度时，必须 优先让硬实时周期任务得到响应，保证其满足截止期限，从而保证系统的可靠性。 般有下面几种典型的混合调度方法1 2 4 2 5 1 2 6 1 2 7 ： 基于调度服务器模型的软实时任务调度算法。此算法是为了缩短硬实时周期任务 和软实时非周期任务混合调度中软实时非周期任务的响应时间以及防止软实时非周期 任务错过其截止期限而提出的调度算法。通常有：后台执行法、资源保留法和挪用法三 种基于服务器模型的任务调度算法。 软实时任务灵活调度模型及算法。灵活调度是软实时调度发展的一个趋势。灵活 调度不需要我们事先确定任务的最坏截止时间和预留系统资源数量，不需要对实时任务 的类型加以区分。在灵活调度模型中，实时系统被当作一个控制系统，任务通常被看作 各种采样信号，其目的是通过反馈控制维持实时系统负载的稳定性和系统资源的高利用 率。 弱硬实时模型及调度算法。弱硬实时能够准确而科学地对软实时任务的实时特性 进行界定和分类，使研究者可以方便地对不同的软实时任务进行定量分析。在弱硬实时 系统中，实时任务可以错过截止期限，但任务错过的截止期限必须可预知且被限制在一 定的范围内。 混合调度器的设计方式还有：以截止期划分任务子集，对组进行e d f 调度，对组 内任务的调度采用其他调度形式。该调度结构经实验证明也是有效的，较之单一的调度 器有适合系统多种需求的优势伫8 1 。 5 太原理工大学硕士研究生学位论文 虽然此后对实时调度算法的分析和研究又进行了多方面的扩展，如有资源共享的周 期任务、有非周期任务运行的情况、在分布式实时系统下的调度算法等等。不过，这些 扩展都是以r m 或e d f 为基础，r m 和e d f 调度算法在实时调度领域中占有重要地位。 对经典的r m 和e d f 算法的研究一直都是理论研帮2 9 1 1 3 0 1 的一个重点。 ( 4 ) 反馈调度 也属于软实时任务灵活调度的一种，但是。尽管实时调度有了很多重大的成果，但 许多现实世界中的问题仍不容易解决。虽然e d f ，r m 等调度算法能支持复杂的任务集 特性( 例如截止期，先前约束，共享资源，抖动等等) ，但这些算法都是开环的调度算 法。开环就意味着一旦调度器被创建，它们就不能基于持续的反馈进行调整了。尽管开 环调度算法在负载精确建模的静态或动态系统中执行良好，该类算法在不可预测的动态 系统环境下性能还是较差卜1 。 基于这些算法的缺点，因此有必要在实时调度中引入反馈控制。结合控制理论的优 点，带有反馈控制器的调度机制被越来越多的研究和应用。其中，由于基本p i d 控制的 优点，以p i d 控制作为基本反馈控制技术的研究比较多，具体理由为以下几点： ( 1 ) 根据控制理论，调度系统是一个动态系统，例如，一个系统的输入不仅依赖当 前的输入，还依赖系统以前的输入。而p i d 控制是一种在动态系统中广泛应用的控制技 术。 ( 2 ) 与其他控制技术相比，p i d 控制的重要特点是它不要求被控系统的精确分析模 型。基于近似模型的p i d 控制器能达到满意的性能。而由于当前计算机系统中极度复杂 的行为，不可能精确地为实际调度系统的动态因素建模。 ( 3 ) 根据控制理论，基本的p i d 控制能为低级别的动态系统提供稳定的控制，而自 适应的p i d 控制形式能为更高级别的动态系统提供稳定的控制。 1 3 论文的组织结构 本文总体上是通过引入智能p i d 反馈控制调度机制对实时系统中一个较通用的动 态优先级调度算法一e d f 调度算法的实时性能进行优化，将每次调度后获得的结果作为 反馈控制的输入，运用这些输入值以及动态调整的参数来辅助在线实时系统使用e d f 算法进行实时任务调度，来提高实时系统的实时性和稳定性。最后用模拟的方法比较了 引入反馈控制机制之前和之后的任务截止期错失率，从模拟实验结果看出，通过引入反 6 太原理工大学硕士研究生学位论文 馈控制机制( 在第四章进行了详细介绍) 可以对实时任务的调度性能进行优化，可以积 极改善过载，从而提高嵌入式实时系统的实时性和稳定性。 进一步，本论文共分为六章。第一章介绍本论文的选题背景，实时调度现状等内容， 主要是对论文的概况介绍。第二章详细说明实时系统以及嵌入式实时操作系统。对嵌入 式系统和实时操作系统等内容作了阐述。该章主要是对本论文应用背景的分析和研究。 第三章对本论文的主要操作对象一实时调度作了详尽的分析和研究。介绍了现有的实时 调度理论、策略和算法，通过实例对r m 和e d f 调度算法进行了分析和说明。第四章 对本论文要用到的p i d 反馈控制机制进行了分析。第五章对引入反馈控制的具体方法、 内容和过程进行了详细分析和研究。通过模拟实验说明使用该方法的可行性和有效性， 改善了e d f 算法的实时调度性能。该结论可以为实时调度算法的研究和使用提供一定 的参考。若应用于实践，可以提高嵌入式实时系统的实时性和稳定性。 7 太原理工大学硕士研究生学位论文 第二章实时系统 2 1 实时系统的特性及其分类 实时系统( r e a l t i m es y s t e m ) 是具有实时性的计算机系统，是计算机的应用与科学计 算在控制领域应用两者相结合的结果。实时系统与非实时系统之间最大的区别就是要满 足处理与时间的关系。实时系统最重要的能力要求就是必须满足在一个事先设定好的时 间限制内对外部和内部的事件进行响应和处理的能力。 2 1 1 实时系统特性 实时系统一般应具备以下几个重要的特性： ( 1 ) 实时性 实时系统结果产生的时间有着严格的要求，只有符合时间要求的结果才是正确的。 任务必须在其截止期限内完成，以保证系统所产生的结果在时间上的正确性。 ( 2 ) 可靠性 可靠性主要包含两个方面的含义：一方面指系统的正确性，即系统本身要连续稳定 运行，系统所产生的结果在返回值和运行时都是正确的；另一方面指系统的健壮性，即， 如果系统出现了错误或外部环境与预先假定的外部环境不符合，系统检查出故障后要有 一定的补救措施及故障排除功能，系统仍然可以处于可预测状态，仍可以安全地带错运 行。 ( 3 ) 并行性 一般来说，实时系统通常有多个外部输入端口。因此，这就要求系统具有一定的并 行处理能力，以便能同时响应来自不同端口的输入信号。 ( 4 ) 可预测性 实时系统的任务必须在一定的限度内开始或截止，而这个限度是根据系统需要定义 的。这意味着系统对来自外部输入的反映必须全部是可预测的，即使在最坏的条件下， 系统也要严格满足截止期限。 9 太原理工大学硕士研究生学位论文 2 1 2 实时系统分类 根据实时任务侧重点不同可将实时系统进行多种分类。如，按系统的可扩展性可分 为专用系统和开放系统；按系统的集中性可分为集中式系统和分布式系统。下面是两种 常用的分类方法： 根据任务的作业到达时刻规律的不同，可分为周期性和非周期性。对于周期任务， 其相邻两次作业到达时刻之间的间隔是一个固定的数值，即周期。非周期任务的作业到 达时刻则没有规律。随着实时理论的发展，人们又将非周期任务进行了细化，分为一般 非周期任务和零星任务d 2 1 。零星任务是非周期任务的极端情况，其出现的规律更加难以 预测。由于周期任务的到来比较规律，所以在实时系统中，周期任务的执行比较容易保 障。而一般非周期任务和零星任务则由于发生不规律，通常不容易保障。 按对截止期限的要求程度可分为硬实时( h a r dr e a l t i m e ) 和软实时( s o f tr e a l t i m e ) 。硬 实时要求可确定性强，具有明确的时间约束，对系统有很高的实时要求，对操作系统有 严格的实时限制，系统必须及时的对事件做出反应，绝对不能发生错过截止期限的情况。 如果在某个限定时刻之前不能完成任务则导致整个实时应用的失败。软实时也对时间敏 感，而且要求其基本上满足实时性要求。软实时允许系统在重负载的情况下发生错过截 止期限的情况，一般不会造成大的危害，不至于影响全局。硬实时系统和软实时系统在 选择实时调度算法上有较大区别。基于优先级调度的算法可以满足软实时系统的实时需 求，而且可以提供高速的响应和较大的系统吞吐率。而对硬实时系统来说，需要使用的 算法就应该是调度方式简单，反应速度快的调度算法。 在现实世界中，硬实时应用和软实时应用都大量存在，并可能在同一个系统中共存。 而且，随着实时应用的发展，实时概念也在不断地发展变化。传统意义上的软实时任务 概念不能够准确地描述一些新出现的软实时系统，从而进一步根据响应时间将实时系统 分为了三种类型： ( 1 ) 弱实时系统 弱实时系统是使各个任务运行的越快越好，没有严格限定某一任务必须在多长时间 内完成。弱实时系统更多地关注软件运行的结果正确与否及安全性能等其他方面，而对 任务执行时间的要求相对较宽松。一般它的响应时间可以是数十秒或更长，并可能随着 系统负载的轻重而有所变化。 ( 2 ) 一般实时系统 】0 太原理工大学硕士研究生学位论文 一般实时系统是弱实时系统和强实时系统的折衷。在错过截止期限后，其计算结果 的价值是降低而不是变为0 。它的响应时间可以在秒的数量级上。如p d a 、手机等就属 于一般实时系统。 ( 3 ) 强实时系统。 在强实时系统中，各个任务不仅要保证执行过程和结果的正确，同时还要保证在系 统能够允许的时间内完成任务。错过截止期限后，任务计算结果的价值变为o 。它的响 应时间在毫秒或者微秒的数量级上。这对于安全和军事领域的软硬件系统来说是至关重 要的。 2 2 嵌入式系统 嵌入式系统( e m b e d d e ds y s t e m ) 是指以应用为中心、以计算机技术为基础、软硬件可 剪裁、适应应用系统对功能、可靠性、成本、体积和功耗严格要求的专用计算机系统。 可以说，嵌入式系统就是应用软件和系统硬件的一体化，它集成了计算机技术、半导体 微电子技术、数据传输技术、传感器技术，体现了当代最新技术的发展。硬件部分通常 由嵌入式处理器、内存、i o 端口及一些与应用密切相关的控制和电子、机械系统组成。 软件部分通常由嵌入式操作系统和应用软件组成，高端的应用可能还会使用到图形平 厶 1 7 3o 嵌入式处理器是硬件的核心内容，有4 位、8 位、1 6 位、3 2 位、6 4 位的微处理器 可供选择。通常从功能和应用方向可将嵌入式处理器分为以下几种： ( 1 ) 嵌入式微处理器。嵌入式微处理器目前主要有a m l 8 6 8 8 ，3 8 6 e x ，s c 一4 0 0 ，p o w e r p c ，6 8 0 0 0 ，m i p s ，a r m s t r o n g a r m 系列等。 ( 2 ) 嵌入式微控制器。其典型代表是在控制系统中广泛应用的单片机，即将整个计 算机系统集成到一块芯片中。最有代表性的通用系列有8 0 5 1 ，m c s 9 6 系列以及m c 6 8 h 系列等。 ( 3 ) 嵌入式d s p 处理器( e m b e d d e dd i g i t a ls i g n a lp r o c e s s o r , e d s p ) 。此种处理器是专 门为信号处理设计的，其在系统结构和指令算法方面都进行了特殊设计。目前主要的嵌 入式d s p 处理器主要有r n 公司的t m s 3 2 0 c2 0 0 0 c 5 0 0 0 系列，i n t e l 的m c s 一2 9 6 和 s i e m e n s 的t r i c o r e 等。 嵌入式系统在硬件上受到很多限制，使得软件同普通软件有所不同，而这些硬件和 软件的不同区分了嵌入式系统的不同发展阶段。嵌入式系统的发展，大致经历了以下四 l 】 太原理工大学硕士研究生学位论文 个阶段： 第一阶段是以单芯片为核心的可编程控制器形式的嵌入式系统。这种系统大部分应 用于专业性极强的工业控制系统中，一般没有操作系统的支持。此阶段系统的主要特点 是：系统结构和功能相对单一，处理效率较低，存储容量较小，几乎没有用户接口。 第二阶段是以嵌入式c p u 为基础、以专用简单操作系统为核心的嵌入式系统。这一 阶段系统的主要特点是：c p u 种类较多，通用性较弱；系统开销小，效率高；操作系统 具有一定的兼容性和扩展性；应用软件较专业，用户界面不够友好；系统主要用来控制 系统负载以及监控应用程序运行。 第三阶段是以嵌入式操作系统为标志的嵌入式系统。这一阶段系统的主要特点是： 嵌入式操作系统能运行于各种不同类型的微处理器上，兼容性好；操作系统内核精小、 效率高，并且具有高度的模块化和扩展性；具备文件和目录管理、设备支持、多任务网 络支持、图形窗口以及用户界面等功能；具有大量的应用程序接口，开发应用程序简单， 嵌入式应用软件丰富。 第四阶段是以基于i n t e m e t 为标志的嵌入式系统，这是一个正在迅速发展的阶段。 目前大多数嵌入式系统还孤立于i n t e m e t 之外，但随着i n t e m e t 的发展以及i n t e m e t 技术 与信息家电、工业控制技术等结合日益密切，嵌入式设备与i n t e m e t