（控制理论与控制工程专业论文）弱硬实时系统及其调度算法.pdf

中文摘要 摘要 随着计算机，网络和通信技术地发展，实时系统越来越多得被应用于工业 控制、网络通信、实时监控，多媒体等领域。这些新的实时网络应用得出现给 实时系统地发展提出了新的要求和挑战。 弱硬实时概念的提出，丰富和扩充了实时系统理论，也满足了实时网络应 用的理论需求。弱硬实时相关问题也因此成为当前实时研究的重点问题之一。 本论文的研究内容集中在弱硬实时约束规范，基于弱硬实时约束规范的调度算 法及相关实验。 弱硬实时理论能够统一描述原有各类实时系统，硬实时、软实时系统都是 类典型的弱硬实时系统。本文提出了一种新的弱硬实时规范约束。从典型弱 硬实时的角度分析了总线协议的实时特性，并具体针对弱硬实时调度算法d b p ，讨论其在优先级设置及调度中的问题，并给出修正策略。论文还讨论了弱硬 实时系统的可扩展问题，提出了任务流归类的方法。完成的相关主要 二作具体 的包括了以下几个方面： 1 简单回顾了实时系统的发展及其相关调度算法。 2 提出了( 丽，p ) 约束，研究了其与现有弱硬实时约束之间的关系：同时修正 了文献 6 1 中的一个约束强弱比较的定理：全面总结了弱硬实时系统的静 态调度算法和静态调度中的两个主要问题，以及动态弱硬实口寸调度算法及 其性能评价方法等。 3 从典型弱硬实时一硬实时的角度，分析工业网络f f 的m a c 层任务的 w c e t ，提出协议改进策略，并通过仿真验证了改进协议的有效性。比较 了集中控制式总线协议f f 和w o r l d f i p 非周期任务调度的带宽利用率。 4 研究了d b p 算法忽略状态所包含0 1 信息分布的缺点，提出了与进入失 效距离对称的概念一退出失效距离，并说明了改进优先级算法设置的合理 性，扩展了d b p 算法的优先级类别。 5 研究d b p 算法在优先级设置时仅考虑该任务流本身的历史状态，而忽略 任务流任务时间参数特性的缺点；提出了在任务优先级设置过程中考虑不 同任务流之间任务时闻参数特性的矩阵d b p 算法，并给出了矩阵元素的 计算公式。 一t 一 浙江大学博士学位论文 6 研究在有限资源下约束的弱硬实时系统可扩展问题。根据队列复用的分类 策略，提出了分别基于丢失率平衡的静态类选择算法和基于任务流平衡的 动态类选择算法。 7 设计了两种基于不同硬件平台的实验方案，验证弱硬实时系统中的各种调 度算法的性能。 题。 最后，对全文进行了概括性总结，并指出了有待进一步研究和完善的问 关键词：实时系统，调度算法，弱硬实时，动态失效，服务质量，现场总 线，d b p ，e d b p ，m a t r i x d b p ，可扩展性 一一 a b s t r 。a c t a b s t r a c t w i t ht e c h n i c a ld e v e l o p m e n to f c o m p u t e r , n e t w o r ka n dc o m m u n i c a t i o n ，r e a l t i m e s y s t e m s a r ea p p l i e dt ot h ef i e l d so f a u t o m a t i c c o n t r o l ，n e t w o r kc o m m u n i c a t i o n ，r e a l t i m e m o n i t o r , m u l t i m e d i a n e wr e q u i r e m e n t sa n dc h a l l e n g e sa r i s ef r o mt h e s ea p p l i c a t i o n s t h ec o n c e p to f w e a k l yh a r dr e a l t i m ei sp r e s e n t e d ，w h i c hn o to n l ye n r i c h e sa n d e x t e n d st h ec l a s s i c a lt h e o r yo fr e a l t i m es y s t e m ，b u ta l s om e e t sn e w r e q u i r e m e n t sa n d c h a l l e n g e s s or e l a t e di s s u e so nw e a k l yh a r d r e a l - t i m ea r eb e c o m i n gh o tr e s e a r c h p o i n t n o w a d a y s t h ec o n t e n to f t h e s i sw i l lf o c u so nc o n s t r a i n ts p e c i f i c a t i o no f w e a k l yh a r d r 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 sb a s e do nw e a k l yh a r dr e a l t i m ea n dr e l a t e de x p e r i m e n t s t h et h e o r yo f w e a k l yh a r dr e a l t i m ec a nd e s c r i b ed i f f e r e n tr e a l t i m es y s t e m ，b o t h h a r dr e a l t i m ea n ds o f tr e a l t i m es y s t e ma r et h et y p i c a lw e a k l yh a r dr e a l t i m es y s t e m s i nt h i st h e s i s ，an e w s p e c i f i c a t i o no f w e a k l yh a r dr e a l t i m ei sp r o p o s e d ；r e a l - t i m ec h a r - a c t e r i s t i co ff i e l d b u si sa n a l y z e df r o mt h ev i e w p o i n to f w e a k l yh a r dr e a l t i m e ，a n di m p r o v e da l g o r i t h m sa r ep u tf o r w a r dt oc o r r e c td r a w b a c k so fd b pi nt h ep r o c e s so fi t s p r i o r i t ya s s i g n m e n t f u r t h e r m o r e ，t h ep r o b l e mo fs c a l a b i l i t yi nw e a k l yh a r dr e a l t i m e s y s t e m i sd i s c u s s e d , a n ds c h e m e sf o rc l a s s i f y i n gs t r e a m sa r e p r o p o s e d t h em a i nd e t a i l r e s e a r c hw o r k si nt h et h e s i sc a nb ed e s c r i b e da sf 0 1 l o w s ： 1 r e v i e wi nb r i e ft h ed e v e l o p m e n to fr e a l - t i m es y s t e ma n di t s s c h e d u l i n ga l g o - r i t h m s ； 2 p r o p o s e ( 而，p ) c o n s t r a i n t ，a n ds t u d yt h er e l a t i o n s h i pw i t he x i s t i n gw e a k l yh a r d r e a l t i m ec o n s 订a i n t ；c o r r e c tt h et h e o r yo f s 拉i n g e n c yc o m p a r ei nr e f e r e n c ef 6 1 】： s u m m a r i z ef u l l yt h es t a t i c s c h e d u l i n ga l g o r i t h m sa n dt h e i rm a i nt w op r i m a r y p r o b l e m sf o rw e a k l yh a r dr e a l t i m e ，a n dd y n a m i cs c h e d u l i n ga l g o r i t h m si n c l u d i n gt h e i r m e t r i co f p e r f o r m a n c e e v a l u a t i o n ； 3 a n a l y z et h ew c e t o f m a ci nf ff r o m v i e w p o i n to f w e a k l yh a r dr e a l t i m e ，a n d p r o p o s ea ni m p r o v e ds c h e m ea n dv a l i d a t et h ee f f e c t i v e n e s sb ys i m u l a t i o n ；c o r n p a r et h eb a n d w i d t hu t i l i z a t i o no fa p e r i o d i ct a s ks c h e d u l i n gi nc e n t r a l i z e dc o n t r o l l i k ef fa n dw o r l d f i p ； i i i 浙江大学博士学位论文 4 p o i n to u t t h e d r a w b a c k o f d b p , w h i c h n e g l e c t s t h e d i s t r i b u t i o n o f o li n f o r m a t i o n i ns t a t e ，a n d p r o p o s e ad i s t a n c et oe x i tt of a i l u r es t a t e ，w h i c hi ss y m m e t r i c a ln o t i o n w i t hd i s t a n c et of a l li n t of a i l u r es t a t e ；t h er a t i o n a l i t yo f p r i o r i t ya s s i g n m e n ti s e x p l a i n e d ，a n dt h ep r i o r i t yn u m b e r i se x t e n d e d ； 5 ，i m p r o v ed b pb yam a t r i x ，w h i c ht a k e si n t oa c c o u n tt i m i n gc h a r a c t e r i s t i c so f s t r e a ml i k ep e r i o d ，d e a d l i n e ，s e r v i c et i m ee t a la n di t s r e l a t i o n s h i pw i t ho t h e r s t r e a m s s h a r i n g t h es a m e s e r v e r ；t h ei d e ar e m e d i e so r i g i n a ld b p t h a to n l yc o n s i d e r sr e c e n th i s t o r ys t a t eo fs t r e a mi t s e l f ；t h ee q u a t i o ni sg i v e nt oc o m p u t ee l e m e n t o f m a t r i x ； 6 s t u d yt h ep r o b l e m so fs c a l a b i l i t yu n d e r t h el i m i t e dr e s o u r c ei nw e a k l yh a r dr e a l - t i m es y s t e m 。s t a t i cl o s s - r a t eb a l a n c ea n d d y n a m i cs t r e a mn u m b e r b a l a n c ec l a s s s e l e c t i n ga l g o r i t h m sa r ed e s i g n e db a s e d0 1 2m u l t i p l e xq u e u e 7 d e s i g nt w od i f f e r e n te x p e r i m e n tp r o j e c tb a s e do nd i v e r s eh a r d w a r e st ov a l i d a t e t h ew e a k l yh a r dr e a l t i m eq o st h a ti sp r o v i d e db yd i f f e r e n tr e a l t i m es c h e d u l i n g a l g o r i t h m s f i n a l l y , s o m ec o n c l u d i n gr e m a r k sa l eg i v e n ，a n dt h ef u t u r er e s e a r c hw o r k sa r e p o i n t e do u t k e y w o r d s ：r e a l - t i m e s y s t e m ，s c h e d u l i n ga l g o r i t h m ，w e a k l y h a r d r e a l t i m e ，d y n a m i c f a i l u r e ，q u a l t i yo fs e r v i c e ，f i e l d b u s ，d b p , e d b p , m a t r i x - d b p , s c a l a b i l i t y i v 主要符号对照表 h r t s r t w c e t d b p w h i u 、 q o s g r b e r m e d f d w c s f f p h b 、 m h b m a c 主要符号对照表 硬实时( h a r dr e a l - t i m e ) 软实时( s o f tr e a l t i m e ) 最差执行时间( w o r s t c a s ee x e c u t i o nt i m e ) 基于距离的优先级( d i s t a n c eb a s e dp r i o r i t y ) 弱硬实时( w e a k l y h a r dr e a l t i m e ) 服务质量( q a u l i t yo f s e r v i c e ) 保证服务( g a u r a n t e e d r e s p o n s e ) 最大努力( b e s t e f f o r t ) 速率单调( r a t em o n o t o n i c ) 截止期优先( e a r l i e s td e a d l i n ef i r s t ) 动态窗口约束调度( d y n a m i c w i n d o w s c o n s t r a i n t ss c h e d u l i n g ) 基金会现场总线( f o u n d a t i o nf i e l d b u s ) 单跳行为( p e r - h o p b e h a v i o r ) 多跳行为( m u l t i h o p b e h a v i o r ) 介质访问控制层( m e d i aa c c e s sc o n t r 0 1 ) 一i x 第一章绪论 第一章绪论 1 1 弱硬实时系统研究的背景、目的及意义 随着计算机科学的发展，计算机的应用范围目益扩大。在各种应用领域 中，有一类计算机系统在现代生活和生产中起着非常重要的作用，这就是实时 计算机系统，简称实时系统。 所谓“实时”系统并非指一类快速计算的系统，而是指能及时响应外部事件 地请求，在规定的时限内，也就是通常所说得截止期( d e a d l i n e ) 内，完成对该 事件地处理并控制相关设备和任务协调一致运行的计算机系统【5 ”。传统的实 时系统按照对截止期的要求通常可以分为硬实时( h a r dr e a l - t i m e ，h r t ) 系统 和软实时( s o f tr e a l t i m e ，s r t ) 系统。在硬实时系统中，事件( 也称任务) 的 截止期错过会对外部环境造成严重后果，甚至系统崩溃。典型的硬实时系统有 飞行器控制系统、复杂核电控制系统等d s 。软实时系统中个别任务可以不满 足截止期的时间要求，但会在一定程度上造成系统性能地下降。早期的实时调 度理论主要集中在对硬实时系统地研究上，通常采用最差响应时间( w o r s t - c a s e e x e c u t i o nt i m e ，w c e t ) 和最差利用率( w o r s t c a s eu t i l i z a t i o n ，w c u ) 等方法分 析最坏情况下的系统性能，来保证每个任务的截止期时间要求，并据此设计和 选择实时系统。 近年来，随着信息技术和互联网技术得飞速发展实时系统的应用范围也 发生了巨大变化。特蹦是在嘲络通信中，实时网络传输、多媒体处理、无线传 感网等系统都需要实时技术的支持。新兴的实时应用为实时系统地发展提出了 新的要求，尤其是网络多媒体音频、视频信号等应用具有在有限时间区间内有 限数量的任务丢失并不会导致图像、语音的质量显著下降的特性。显然，传统 得简单的h r t 和s r t 的分类已经无法确切地描述这类典型的实时网络多媒体应 用d 2 ，相应的基于h r t 和s r t 的最优实时调度算法在网络实时多媒体等应用 中将不再是最优i ”。这一类实时网络应用，为实时系统和基于实时系统的调度 理论地研究提出了新的挑战，这也正是本文研究的背景。 h a m d o u i 最早用( m ，k ) 一f i r m 约束模型从有限时间区间内允许部分任务丢失 的角度来描述网络多媒体的服务质量闯题，并提出了基于距离优先级( d i s t a n c e - b a s e d p r i o r i t y , d b p ) 的方法旧，鲫。随后b e r n a t 把这类具有窗口约束的实时系统 浙江大学博士学位论文 定义为弱硬实时( w e a k l y h a r dr e a l t i m e ，w h r t ) 系统 5 9 , 6l 。所谓弱硬实时系 统是指在有限时间窗口中，任务截止期满足或错过符合一定分布要求的实时系 统。( m ，) 一f i r m 是一种典型的弱硬实时约束模型，实时应用带有类似，) 一f i r m 约束的称其具有弱硬实时约束。 弱硬实时概念地提出为实时系统的统一描述提供了理论基础。弱硬实时系 统通过参数的动态调整可以统一描述实时系统。在( m ，曲f i r m 约束模型中，当 m = 时，实际上等价于硬实时系统，即k 个任务都必须满足截止期要求：当 k 一时，等价于软实时系统。显然，在统一描述中，硬实时和软实时系统都 是一种特殊的弱硬实时系统。 弱硬实时概念地提出丰富了实时系统服务质量( q a u l i t yo f s e r v i c e ，q o s ) 的多样性( d i v e r s i t y ) 。在q o s 多样性上，此前只规定硬实时和软实时，在实 时网络中分别对应提供保证响应( g u a r a n t e e d r e s p o n s e ，g r ) 服务和最大努力 ( b e s t e f f o r t ，b e ) 服务。在提供g r 服务时，以实时系统负载的峰值为基础， 充分预留了大量的网络资源，绝对保证实时任务的截止期要求，导致系统过渡 地支持了参数裕度，同时也浪费了大量的网络资源。从实用的角度看，这种方 法的代价过高。在提供b e 服务时，可以提供可靠的服务并充分利用资源，但 是不能够保证实时任务的截止期要求。因此，硬实时和软实时性能之间缺乏良 好的过渡，即q o s 的粒度过粗，无法满足实时应用服务质量多样性的需求。针 对q o s 多样性，尽管s h i n 锌曾提出统计实时的概念【4 8 】。但是，统计实时实际 上无法保证截止期超出是否分布均匀。例如，“保证截止期错过的概率小于1 0 ” 仅仅表示在很长时间段内截止期超出的统计分布。“每l o 个任务中最多1 个截 止期错过”和“1 0 0 0 个任务中，前9 0 0 个任务截止期连续满足而后1 0 0 截止期连 续错过”均满足q o s 统计实时1 0 的要求，但是，两者提供的截止期错过的分布 和要求明显是不同的。而，凳) f i r m 约束模型可以根据实时应用q o s 的要求设 计参数m 和k ，从而明确给出有限时间区间内任务截止期错过的分布情况。在 网络负载瞬间过载时，弱硬实时调度可以保证多媒体实时应用在满足最低可接 受性能的情况下传输，从而增强网络的适应性( a d a p t a b i l i t y ) ，与g r 服务相 比，还可以提高资源利用率；而相比b e 保证，则解决了它无法在有限时间区间 内保证q o s 的缺陷，这正是本项目研究的出发点。 弱硬实时调度算法是整个弱硬实时理论的核心。在多媒体应用中，弱硬实 时服务质量需要由其调度算法保证。弱硬实时调度算法的研究，将提高具有弱 硬实时约束的多媒体应用在网络传输中的动态性能，实现在有限时间区间下 2 一 第一章绪论 衡量q o s ，提高网络资源的利用率f 4 , 2 , 2 h 。本文将主要根据( m ，) 一f i r m 约束规 范，实现弱硬实时调度算法地设计和改进。 1 2 国内外研究现状 实时系统通常由一系列互相作用的任务组成，其任务的内在特征是具有时 间要求，并且表现为截止期的形式。在实时系统中，任务的正确性不但依赖于 计算结果的正确性，还取决于产生结果的时间。而实时调度理论正是研究在实 时系统中，如何满足每个任务的功能和时间需求口1 。 实时调度理论主要研究在给定一组任务集和资源时，于何时何处执行 任务，以满足每个任务的时间约束。对于给定任务时间特征包括到达间隔 t ( i n t e r v a l - a r r i v a lt i m e ) 、计算时间e ( c o m p u t a t i o nt i m e ) 、截止期d 和任 务的调度方法，分析任务是否满足截止期要求，这一问题称为任务可调度性判 定问题1 3 2 】。 早期的实时系统研究主要集中在硬实时调度理论的研究。早在1 9 7 3 年， 对于相互独立的硬实时周期任务，l i u 和l a y a n d 首先提出了速率单调( r a t e m 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 的可调度性判定条件u 冬( 2 奇一1 ) ( 其中n 为任务集中 任务的个数) 和e d f 的可调度性判定条件u = f 墨，等 b 9 1 。 r m 算法自提出以来得到了广泛的研究和应用。目前已有大量的关于r m 算 法及其各种情况下得扩展谲度算法以及这些算法的可调度性判定的研究文献。 在经典文献1 8 9 中给出的可判定条件仅仅是充分的，l e h o c k y 对r m 算法的特 性进行了深入的分析，并推论了一个更为精确的基于利用率的可调度性判定的 充要条件，但这一算法的时间复杂性是伪多项式时间，复杂度较高 8 2 】。后来 h a n 和t y a n 提出了多项式时间的判定算法，但只是充分而不是充要的判定条件 f 6 6 】。但是上述提到的r m 算法可调度性判定条件都对调度模型作了一系列理想 的假设，忽略了一些重要的影响因素，例如截止期和周期的关系、调度的时间 开销和任务的相关性等，这就使理想的调度模型比现实情况要简单得多，从而 影响了其适用范围。当d t ，r m 不再是最优，l e u n g 等提出了截止斯单调 ( d e a d l i n em o n o t o n i c ，d m ) 算法，并证明了其在固定优先级算法中，周期和截 止期不等情况下的最优性【8 4 】。文献口舢在考虑各种调度时间开销的情况下，提 出了可调度性判定条件。理想的i l m 算法可调度性条件的一个重要的基本假设 一3 一 浙江大学博士学位论文 是任务的相互独立性，即假设任务之间都是不相关得，每个任务的请求不依赖 于其他任务请求地开始或完成。但实际上，任务之间往往存在着种种联系，由 于共享资源而引起的同步问题是其中十分重要的一种。在多个共享某一个互斥 资源的任务当中，如果有一个任务已经进入该资源的临界区，其他任务就必须 等待该任务退出临界区，即使它们的优先级比该任务的优先级高，这样实际上 就改变了原来由r m 算法确定的优先级配置，这种情况称为优先级倒置，严重 时会造成高优先级任务的无限期等待”。优先级驱动的实时调度都存在这样 的问题。可见，任务的相关性会对实时调度产生极大的影响，进而也影响了任 务的可调度性判定，因此必须在可调度性判定中考虑任务相关性。基于优先级 倒置这个问题已有几种解决方案，典型的有优先级继承协议( p r i o r i t y i n h e r e n c e p r o t o c o l ，p i p ) 1 0 9 1 和优先级上限协议( p r i o r i t y c e i l i n g p r o t o c o l ，p c p ) ( 58 1 。国内 的学者从九十年代开始陆续对r m 算法做了介绍和研究 8 1 0 , 2 2 , 2 3 , 2 5 】。中科院软 件所何军博士的论文m , 5 1 ，华中科技大学涂刚博士的论文1 对该算法都做过一 定程度的分析和改进。 在硬实时系统的研究中，动态优先级调度算法e d f 一直也是备受关注的研 究点。e d f 本质上是抢占式的，抢占的额外开销和抢占的关系降低了系统的可 调度能力，影响着系统的性能。因此，j e f f a y 在1 9 9 1 年提出了适用于周期性和 非周期性任务的非抢占的e d f 调度性判定条件。此外人们还研究了将e d f 应用 于多处理机环境的情况，文献t 4 4 , 8 1 | ) 中则提出了基于e d f 算法的硬非周期任务 调度算法。国内学者在该领域的研究也获得了诸多的结果。文献 1 3 结合截止期 和空闲时间这两个特征参数，综合设计任务的优先级表。文献o i l 中考虑了截止 期和价值结合的调度策略，提出了结合二者的两种不同的基于优先级表的实时 任务调度算法。文献担5 1 提出了一个改进的抢占式e d f 调度算法，通过将遗传 算法的优化方法离线计算得到的实时任务启动时间作为目标系统的一个调度参 数，减少抢占次数，改变抢占关系，从而提高系统的可调度能力和实时性能， 并用实验验证了改进的抢占式e d f 调度算法的有效性。国内也有学者对e d f 算 法应用于多处理器作了相关研究i ”】。 由于硬实时系统任务( 包括周期和非周期两类) 的特征明显，相应的研究 已进行得相当透彻。相比之下，由于软实时系统的应用种类繁多，不易进行系 统的分类研究，所以研究软实时的算法也相当丰富。归纳一下大概主要有以下 几种： 4 一 第一章绪论 1 ：基于服务器模型的软实时任务调度算法 在软硬实时任务混合调度时，一般都采用基于服务器模型的调度。这些方 法的目的是在保证硬实时任务的同时，提高软实时任务的响应能力。一般归为 三类：后台执行法、带宽保留法、挪用法。后台执行法是为软实时任务制定较 低的优先级并作为后台任务执行，保证了硬实时任务的执行但没有采取措施提 高软实时任务的响应能力 。带宽保留法包括优先级交换( p r i o r i t ye x c h a n g e ， p e ) ”、延缓服务器( d e f e n a b l es e r v e r , d s ) 1 ，伪周期服务器( s p o r a d i c s e r v e r , s s ) ，多路服务器( m u l 却l es e r v e r , m s ) 2 1 等。这些算法的共同 特点是在保证硬实时任务的同时，为软实时任务的执行保留了一定带宽( 或者 c p u 时间) ，大大提高了软实时任务的响应时间。挪用法的基本思想是：在保 证硬实时任务满足截止期要求的同时，尽量使用“挪出”时间服务软实时任务， 从而能提高软实时任务的响应时间。 2 ：软实时灵活调度算法 基于服务器模型的各种软实时任务调度算法大都考虑在w c e t 下的情况。 虽然采用w c e t 分析方法能够保证各种硬实时计算的正确性，但是缺乏灵活性 并容易造成资源浪费。灵活调度是软实时调度发展的一个新趋势 3 7 ，“3 】。在灵活 调度中，实时系统被看作一个控制系统，实时任务被看作各种采样信号，通过 反馈控制保持实时系统负载的稳定性和系统资源的高利用率。 基于反馈控制理论方法，s t a n k o v i c 等提出了一种f c 。e d f 的灵活调度策略 “”。在该策略中，反馈调度器通过在线监测任务丢失率或c p u 利用率，采 用一定的控制算法( 如p i d ) ，经由q o s 支持的路由器对一系列可变执行时间 软实时任务的c p u 利用率估计值进行调节，以同时获得较低的任务丢失率和较 高的c p u 利用率。文献 9 3 】对该策略进行了扩展。l i n 在文献【8 7 中，综合全局 调度和局部调度，设计了一种双回路反馈控制器。与文献【9 3 3 类似，其目标也是 维持任务丢失率在期望值附近，并获取较高的c p u 利用率。w e i 等运用混杂自 适应控制体系，有效的解决了实时系统本质非线性问题，并基于f c r t s 反馈调 度改进了系统的动态性能 1 2 7 。文献【”8 】则研究了带通信时延的实时控制系统， 针对c p u 资源变动和不可预知负载，分别为单回路和多回路控制系统设计了计 算资源的反馈调度策略。反馈控制算法都是借助系统负载的反馈值确定调度模 块是否接收当前实时请求，从而达到控制负载的目的。 在网络技术飞速发展之后，出现了很多基于网络的实时应用，称实时网络 应用。这些应用要求潜在网络性能的特殊支持，如可靠性、实时性、稳定性等 一5 一 浙江大学博士学位论文 不同水平的q o s 。 普通互联网络由于其硬件的不可靠和负载的不可控而引起的性能不稳定 性，一般根难支持硬实时应用。硬实时应用只在一些专餍的工业网络中实 现，比如现场总线。国际上在这方面的研究主要集中在葡萄牙p o r t o 理工学 院的i s e p i p p 研究组对p r o f i b u s 、p - n e t 、w o r t d f i p 等方面的研究【“2 0 l ；法 国1 n r i a _ l o r i at r i o 研究组对w o r l d f i p 的研究 1 1 0 。国内几个研究所也对 w o r l d f i p 进行了研究 2 9 a 2 6 ，并最先对基金会总线( f o u n d a t i o nf i e l d b u s ，f f ) 的周期和非周期实时任务的通信深入展开了研究 1 4 ，1 2 4 。关于专用工业网络的 实时任务的调度问题将在第三章中重点讨论。而现行一般采用b e 策略来保证 实时网络应用的服务质量。b e 服务策略在传统的实时网络应用，如电子邮件 ( e m a i l ) 、文件传输协议( f t p ) 、终端机控制协议( t e l n e t ) 和超文本传输 协议( h t t p ) 等方面运作很好。实时网络应用依赖于网络参数，如带宽、时 延、时延抖动和正常操作的丢失。对这些参数中任何一个的容忍度和敏感度随 实时应用的不同而大相径庭。如远程外科手术、在线交易系统等，要求这些参 数的可靠性和保障性传输。不断兴起的新应用，如家庭网络、智能装置、工厂 供应链网络及多媒体应用，也需要潜在网络以这些参数为依据提供不同水平 的服务质量。所谓服务质量q o s 是指“在网络中提供资源保证和服务区分的能 力”，一般包括对时延、抖动和丢失率三个参数的评价【5 。虽然现在获得大量 带宽的代价越来越小，然而，高级多媒体应用的出现和互联网在日常生活中的 普及，以及越来越多的使用可能又会使得提供的带宽远远不够，而再次返回到 最初带宽限制的情形。在带宽限制时，多种应用共享带宽的网络中出现其他应 用流量( 如t e l n e t 、h t t p 、f t p ) 的情况下，b e 服务策略虽然能保证传输的可 靠性，但必然导致网络拥塞，从而会导致实时应用的任务经历不断变化和不可 预测的时延和抖动。 实时网络应用比如多媒体任务流，通常对端到端时延比较敏感，但能够容 忍一定程度的丢失( 任务错过截止期) ，通过插值等信号重构技术来保证其通 信的质量 1 3 5 。例如，为了保证正常理解声音，v o i ：p 电话要求1 5 0 3 0 0m s 的端 到端时延，过长的时延将导致音质变差甚至不易觉察，偶尔的个别任务丢失， 并不会影响通话的声音质量【1 2 2 】。b e 服务支持任务的可靠传输，但不能保证时 延，也不支持丢失率。随着多媒体等实时应用的日益普及，原有的单一b e 服务 策略显然无法满足要求。对于不同的实时网络应用的行淹和资源要求，人们开 始研究支持多种q o s 的策略及其调度算法。 一6 第一章绪论 实时网络应用由不断重复触发的任务构成任务流，一些学者考虑任务允许 丢失的情况，提出了在保证到达的任务都满足截止期要求的情况下，以丢失率 作为其q o s 的锤量尺度称其为概率q o s 。文献邮4 5 ，5 0 ，5 1 ，5 4 ，”，旧7 1 3 3 】中都提 出了一些调度策略来满足实时应用最大丢失率的要求，从而保证概率q o s 。基 于概率q o s 的调度策略在瞬间过载的情况下允许部分任务丢失，保证任务的概 率到达，一定程度上提高了网络带宽的利用率。 然而，概率q o s 是建立在无限长的时间区间内的一种统计q o s ，菇不能满 足诸如多媒体等实时应用的需求。对多媒体等实时应用而言，其对任务的连续 丢失相当敏感，即使满足概率q o s ，但是如果任务连续丢失也可能会导致其一 小时间段上的q o s 严重下降，从而使信号无法重构或者重构的信号无法实现多 媒体应舟q o s 的目标，满足实时应用的需求1 4 7 。为此必须研究实时网络应用的 有限时间区闻上的概率q o s ，也称为弱硬实时q o s 。 从有限时间区间的角度，k o r e n 等提出的, s k i po v e r 约束( 个实时应用 有一个s k i p 因素s ，那么该应用对应的任务流中，每s 个任务允许有1 个被丢弃 ( 截止期错过) ) ，成为最早一个描述弱硬实时q o s 的弱硬实时约束规范【7 4 ； 随后，h a m d a o u i 等扩展了“s k i po v e r ”，提出了( m ，) 一f i r m 约束( 当一个实时应 用具有( m ，) f i r m 约束时，该实时应用的每连续k 个任务至少有m 个满足截止 期要求) 眦卅；最近，b e m a t 等丰富了，) 一f i r m ，提出了四种弱硬实时约束 规范：( m ，七) 一f i r m 、( m ，舟) 一f i r m 、( m ，) 一f i r m 、( m ，) 一f i r m ，并且正式定义由这些 弱硬实时约束规范描述的q o s 为弱硬实时q o s s 9 , 6 1 , 6 2 。w e s t 等提出了等价于 ( 一m ，k ) f i r m 的( z ，口) 约束：对于一个任务流，任意个任务最多z 个截止期错 过【1 3 l ，” 。m o n t e z 等提出了( p + i ，) 一f i r m 的弱硬实时自适应模型 9 6 , 9 7 1 ，该模 型结合任务窗口丢失和文献【”】中提出的非精确计算模型，但是由于非精确计算 模型不适用于实时网络应用，基于这种模型的算法没有得到更多的关注。 基于弱硬实对q o s 的调度主要分为静态调度算法和动态调度算法，分别对 应基于窗口任务丢失模式固定调度和基于窗1 2 1 任务丢失模式任意调度，并都有 了相应的一些研究成果。丢失模式固定也称固定弘一p a t t e r n ，基于固定g - p a t t e r n 的静态调度算法主要把任务分为强割( m a n d a t o r y ) 和可选( o p t i o n a l ) ，通过 硬实时调度分析的方法，满足强制任务的截止期要求。“s k i po v e r ”实际上是 ( m ，) 一f i r m 约束韵一种特殊模型，满足m = k 1 。k o r e n 等根据“s k i oo v e r ， 模型，提出了r t o ( r e dt a s ko n l y ) 算法和r m r t o ( r a t em o n o t o n i cr t o ) 算 法，通过硬实时分析的方法给出了满足任意连续个任务中一1 任务的截止 7 一 浙江大学博士学位论文 期的可调度性判定条件，并证明“s k i po v e r ”约束规范中最优的强制任务和可选 任务的设定是n p - h a r d 问题，同时还给出了一种更为柔性的b w p ( b l u ew h e n p o s s i b l e ) 算法，为可选任务提供更多的满足截止期的机会 7 4 1 。对于一般具有 ( 佻，觑) 一f i r m 约束的任务流 ，r a m a n a t h a n 给出了一个设定固定p p a t t e r n 的公式 o = l 譬 熹l ，o = 0 ，1 ，2 为任务到达序号，当值使得该公式成立时，对 应的任务就为强制任务，否则为可选任务【l o ”。显然在上面公式给定的灿一p a t t e r n 下，t = 0 时刻为紧急临界时刻。对于任务集里面的强制任务的可调度性问 题，r a m a n a t h a n 给出了紧急临界状态的判定条件。q u a n0 0 3 1 扩展了文献 1 0 5 1 中 的固定, a - p a t t e r n 公式，通过添如偏移月期，使褥强制任务分布更加均匀，从而 弱化了临界状态的紧急程度，提高了强制任务的可调度性，并证明了对于任意 适用文献 1 0 5 i 中“一p a t t e r n 的可调度性判定条件必然适用q u a n 给定的“一p a t t e r n 。 在周期、非周期任务共存的模型中，b e m a t 等提出了e d p s ( e n h a n c e dd u a l p r i o r i t ys c h e d u l i n g ) 6 0 l ，进一步扩展到一般的具有d s 置、不同任务弱硬实时 约束不同、周期和非周期任务并存、资源互斥等通用模型中，提出了b m s ( b i m o d a ls c h e d u l e r ) 策略 6 2 】。m o k 则证明了静态非重叠窗口调度是强意义上的 n p h a r d 问题，当g 都为固定单位长时，给出了静态非重叠窗口基于p 公平的 e d f 算法可调度判定的充分性条件( 9 s 】。文献 2 8 , 7 5 - 7 7 ，1 3 6 - - 1 3 9 中，a n i s 、y i n 等把 p p a t t e r n 和w f q ( w e i g h t e d f a i rq u e u i n g ) 、w f 2 q ( w o r s t c a s ef a i rw e i g h t e d f a i r q u e u i n g ) 相结合，分别提出了( m ，k ) - w f q 和( m ，k ) 一w f 2 q 算法，利用网 络演算的方法，研究了口一p a t t e m 中强制任务的时延上界，井通过网络仿真和实 验的方法验证了这些方法在提高网络利用率和保证实时应用q o s 的有效性，扩 展了w f q 算法的适用范围。 基于固定p p a t t e r n 的调度算法可以离线判断强制任务截止期是否满足，实 现简单，但缺乏柔性，而且寻找最优的固定u - p a t t e m 非常困难，同时也无法 适应瞬间过载的变化。为保证算法有效，在整个运行过程中。必须满足条件 鍪l 学sl ，但在实际网络中，瞬间过载和