（通信与信息系统专业论文）基于改进约束的弱硬实时系统及其算法研究.pdf

武汉理工大学硕士学位论文 摘要 随着计算机技术的飞速发展与普及，实时系统已经成为人们生产和生活中 不可或缺的组成部分。实时系统具有及时响应、高可靠性、专用性、少人工干 预等特征，被广泛应用于工业控制、军事、信息通讯、网络传输、军事、多媒 体处理等领域。 然而，由于新的实时网络应用的出现，尤其是丢失容忍的多媒体视频、音 频等实时应用，对实时系统及其调度理论提出了新的挑战。而弱硬实时概念的 提出，丰富和扩充了实时系统理论，也满足了实时网络应用的理论需求。弱硬 实时相关问题也因此成为当前实时研究的重点问题之一。本论文的研究内容集 中在弱硬实时约束规范，基于弱硬实时约束规范的调度算法及相关实验。 弱硬实时理论能够统一描述原有各类实时系统，硬实时、软实时系统都是 一类典型的弱硬实时系统。本文提出了一种新的弱硬实时约束，并基于此约束 设计调度算法。完成的相关主要研究工作具体如下所述： 1 ) 回顾了b c r n a t 提出的四种典型弱硬实时约束规范，并根据其性质，提出 三个推论和两个新的约束关系定理。然后分析了( m ) 一f i r m 约束对任务 丢失概率和( m ，k ) 一f i r m 约束对任务连续丢失的“松要求的缺点，提 出了一种新的约束l n , m ，k l 来弥补这些缺点。同时，还讨论了新的约束 i 以，m ，kl 随着其三个参数的不同变化，与传统典型弱硬实时约束规范之 间的严格性关系。 研究了弱硬实时的静态和动态调度算法，尤其是d b p 和e d b p 动态调度 算法，讨论了它们的优先级分配方式。然后基于新约束( 阼，m ，kl 设计了 一种双优先级动态调度算法。详细分析了在任务完成或丢失之后，双重 优先级的计算方法及其与动态失效状态的关系。 3 ) 通过v c 编写程序进行了仿真实验，从弱硬实时q o s 评价的主要标准 动态失效概率的角度，对 ：t d b p 算法评价了设计的算法对保证q o s 的有 效性。 关键词：实时系统；弱硬实时；约束规范；调度算法；服务质量 武汉理工大学硕士学位论文 a b s t r a c t w i t hf a s td e v e l o p m e n ta n dp o p u l a r i z a t i o no fc o m p u t e r st e c h n o l o g y , r e a l - t i m e s y s t e mh a sb e e ni n d i s p e n s a b l ep a r to fp e o p l e sp r o d u c t i o na n dl i f e t h er e a l t i m e s y s t e mh a sc h a r a c t e r ss u c ha sr e s p o n s ei nt i m e ，h i g l ld e p e n d a b i l i t y , d e d i c a t i o na n d l e s sa r t i f i c i a li n t e r f e r e n c e ，w h i c hi sw i d e l ya p p l i e di nt h ei n d u s t r i a lc o n t r o l ，m i l i t a r y d e f e n s e ，i n f o r m a t i o nc o m m u n i c a t i o n ，n e t w o r kd e l i v e r i n ga n dm u l t i m e d i ap r o c e s s i n g h o w e v e r , 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 ms o m en e wn e t w o r k a p p l i c a t i o n s a p p e a r a n c e , e s p e c i a l l ys u c ha sm u l t i m e d i av i d e oa n da u d i of o rl o s s t o l e r a n t t h e nt h ec o n c e p to fw 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 y e n r i c h e sa n de 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 dc 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 dr e a l - t i m ea r e b e c o m i n gh o tp o i n to fr e s e a r c hn o w a d a y s t h ec o n t e n to ft h et h e s i sw i l lf o c u so n c o n s t r a i n ts p e c i f i c a t i o no fw e a k l yh a r 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 sb a s e do n w 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 fw e a k l yh a r dr e a l - t i m ec a l lu n i f o r m l yd e s c r i b ed i f f e r e n tk i n d so f r e a l - t i m es y s t e m b o t hh 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 l w 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 ws p e c i f i c a t i o no fw e a k l yh a r d r e a l - t i m ei sp r o p o s e d ，a n dt h es c h e d u l i n ga l g o r i t h mb a s e dt h i sc o n s t r a i n ti sd e v i s e d t h em a i nd e t a i lr e s e a r c hw o r k si nt h et h e s i sc a l lb ed e s c r i b e da sf o l l o w s ： 1 ) r e v i e wf o u rc l a s s i c a lw e a k l yh a r dr e a l t i m ec o n s t r a i n ts p e c i f i c a t i o n s p r o p o s e db yb e m a t d e p e n d i n go nt h e i rc h a r a c t e r s ，p u tf o r w a r dt h r e e d e d u c t i o n sa n dt w on e wt h e o r e m sf o rr e l a t i o n s h i pb e t w e e nc o n s t r a i n t s t h e na n a l y s es h o r t a g e so fc o n s t r a i n t s 伽，足) 一声册a n d ( m ) 一f i r ma n d p r o p o s ean e wc o n s t r a i n tin ，m ，k t om a k eu pt h e i rs h o r t a g e s b e s i d e s ， d i s c u s st h es t r i c tr e l a t i o n s h i pb e t w e e nt h en e wc o n s t r a i n t ( 1 , m ，kja n d c l a s s i c a lc o n s t r a i n t sw i t hv a r i e t yo ft h r e ep a r a m e t e r s 2 ) r e s e a r c hs t a t i ca 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 so fw e a k l y h a r d r e a l - t i m e s y s t e m ，e s p e c i a l l yd b pa n de d b pd y n a m i cs c h e d u l i n g h 武汉理工大学硕士学位论文 a l g o r i t h m s ，a n dd i s c u s st h e i rm e t h o d so fp r i o r i t ya s s i g n m e n t t h e nb a s i n g o nt h en e wc o n s t r a i n t i 万，m ，k ，an e wd u a lp r i o r i t yd y n a m i cs c h e d u l i n g a l g o r i t h mw a sd e v i s e d d e t a i l e d l ya n a l y s ea l g o r i t h mo fd u a lp r i o r i t ya n d r e l a t i o n s h i pb e t w e e np r j 硎t ya n dd y n a m i ci n v a l i d a t i o ns t a t ea f t e rt a s k f i n i s h e do rm i s s e d 3 ) c o m p i l ep r o g r a mb yv ct oe x p e r i m e n t c o m p a r i n gd b ps c h e d u l i n g a l g o r i t h m s ，e v a l u a t ew e a k l yh a r d r e a l t i m eq o sf o rn e ws c h e d u l i n g a l g o r i t h mf r o ma s p e c to fm a i ns t a n d a r do fq o s d y n 锄i ci n v a l i d a t i o n r a t e k e yw o r d s ：r e a l t i m es y s t e m ：w e a k l yh a r dr e a l - t i m e ：c o n s t r a i n ts p e c i f i c a t i o n ： s c h e d u l i n ga l g o r i t h r a ：q u a l i t yo fs e r v i c e m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名篮壁日期： 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：蚀导师签名：期： 武汉理工大学硕士学位论文 第1 章绪论 实时系统起源于二十世纪中叶，最初与军事上的需求紧密相关。随着计算 机技术的飞速发展，实时系统逐渐在民用领域也得到广泛应用，例如：机械制造 业、铁路及机场调度、航空航天、核电站及化工过程监控、计算机多媒体信息 处理以及具有服务质量( q u a l i t yo f s e r v i c e ，q o s ) 需求的网络应用等。它己成为 人类社会生活中不可缺少的部分，“实时 正在成为一种无处不在的计算。 1 1 研究背景 二十世纪末，以计算机和通信技术为代表的信息科学与技术在世界经济、 科技、军事、教育等领域产生了深刻影响和变革。从二十世纪六十年代末期开 始，实时计算( r e a l t i m ec o m p u t i n g ) 一一带期限的计算( c o m p u t i n gw i t h d e a d l i n e ) 己经发展成为一个计算机科学的重要研究领域。 对于什么是实时，p o s i x1 0 0 3 1 b 标准作了这样的定义：操作系统在限定 的时间内提供所需服务水平的能力i l j 。而一个由d o n a l dg i l l i e s 提出的更为大家 接受的定义是：实时系统是指计算的正确性不仅取决于结果逻辑的正确性，更 取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统 出错。自实时概念提出以来，实时技术的研究和应用取得了长足的进步，在实 时模型、实时调度、实时容错、实时对象、形式化方法、分布式实时、嵌入式 实时等研究方向取得了较大的突破，极大地促进了计算机技术的发展。 实时系统的产生和发展动力来源于现实世界的实际需求。现实世界的许多 应用都与时间因素相关，例如要求在某个时刻之前完成某些操作等。因此，根 据应用需求而设计的计算机软件就需要满足系统中的各种时间要求。实时系统 领域相关研究的一个主要目的便是为保障计算任务的时间约束提供理论基础。 然而，随着实时应用的日趋复杂化，这方面的研究也需要相应的发展才能满足 实际需求。 所谓“实时打系统并非指一类快速计算的系统，而是指能及时响应外部事 件地请求，在规定的时限内，也就是通常所说得截止期( d e a d l i n e ) 内，完成对 该事件地处理并控制相关设备和任务协调一致运行的计算机系统1 2 】。传统的实 武汉理工大学硕士学位论文 时系统按照对截止期的要求通常可以分为硬实时( 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 ) 系统。在硬实时系统中，事件( 也称任务) 的 截止期错过会对外部环境造成严重后果，甚至系统崩溃。典型的硬实时系统有 飞行器控制系统、复杂核电控制系统等。软实时系统中个别任务可以不满足截 止期的时间要求，但会在一定程度上造成系统性能地下降。早期的实时调度理 论主要集中在对硬实时系统地研究上，通常采用最差响应时间( w o r s tc a s e e x e c u t i o nt i m e ，w c e t ) 和最差利用率( w o r s tc a s eu t i l i z a t i o n ，w c u ) 等方法分 析最坏情况下的系统性能，来保证每个任务的截止期时间要求，并据此设计和 选择实时系统。 而实时系统作为实时计算的主要载体，其相关技术得到了长足的进步和发 展，尤其是实时系统任务调度理论，已成为实时界的重要分支领域与研究热点。 实时系统通俗来讲就是迅速、立即的意思。任务的响应时间是实时系统最关键 的因素。目前，实时系统都是把任务的时间响应看作是正确性的判定标准。因 此几乎所有实时系统定义都离不开时间性( t i m e l i n e s s ) 。一般来讲，实时系统是 能及时响应外部发生的随机事件，并以足够快的速度完成对事件处理的计算机 应用系统。而对于周期性发生的事件，系统必须在每个周期内使任务的响应时 间满足某些要求。换句话说，计算机能及时响应外部事件的请求，在规定的时 间内完成对事件的处理，并能控制所有实时设备和实时任务协调运行。 与非实时系统相比，实时系统的一个主要特征就是要同时保证逻辑结果和 时间的正确性。在实时系统中计算的正确性，不仅取决于逻辑结果的正确，同 时还要保证结果在规定的时间产生，提前或者错过规定时间，在实时系统中都 会被看作不正确的结果。实时调度算法是保障实时系统两个必备特性时限 性和高可靠性的重要手段之一。实时调度是指在有限的系统资源( 如c p u 等) 下，为一系列任务决定何时以及在哪个处理器上运行，并分配任务运行所需要的 资源，以保证其时间约束( 即截止期限) 、时序约束和资源约束得到满足。 实时系统已经广泛应用于各个领域，包括飞机、太空探测器、火箭控制、 舰艇控制、雷达、制导导航、多媒体等，且在整个系统中实时系统往往担负着 关键控制系统的角色。在这些应用中，若系统的实时性得不到满足，那么就会 造成无法挽救的灾难性后果。实时系统就是在这些对时间性要求近乎苛刻的条 件下工作的，但是它们起到的作用往往是关键和可靠的。 实时系统具有以下五个特征：可预见性、及时性、交互性、高可靠性和多 2 武汉理工大学硕士学位论文 路性。也正是这些特征决定了实时系统的广泛和光明的应用前景。 近年来，随着信息技术和互联网技术得飞速发展，实时系统的应用范围也 发生了巨大变化。特别是在网络通信中，实时网络传输、多媒体处理、无线传 感网等系统都需要实时技术的支持。新兴的实时应用为实时系统地发展提出了 新的要求，尤其是网络多媒体音频、视频信号等应用具有在有限时间区间内有 限数量的任务丢失并不会导致图像、语音的质量显著下降的特性。显然，传统 的简单的h r t 和s r t 的分类已经无法确切地描述这类典型的实时网络多媒体 应用1 5 】，相应的基于h r t 和s r t 的最优实时调度算法在网络实时多媒体等应用 中将不再是最优1 6 】。这一类实时网络应用，为实时系统和基于实时系统的调度 理论地研究提出了新的挑战，这也正是本文研究的背景。 h a m d o u i 最早用( m ，k ) f u m 约束模型从有限时间区间内允许部分任务丢失 的角度来描述网络多媒体的服务质量问题，并提出了基于距离优先级 ( d i s t a n c e b a s ep r i o r i t y , d b p ) 的方法【7 一。随后b e r n a t 把这类具有窗口约束的 实时系统定义为弱硬实时( w e a k l yh a r dr e a l t i m e ，w h r t ) 系统1 9 1 0 l 。所谓弱 硬实时系统是指在有限时间窗口中，任务截止期满足或错过符合一定分布要求 的实时系统。( m ，k ) f i r m 是一种典型的弱硬实时约束模型，实时应用带有类似( m ， k ) f i r m 约束的称其具有弱硬实时约束。 弱硬实时概念地提出为实时系统的统一描述提供了理论基础。弱硬实时系 统通过参数的动态调整可以统一描述实时系统。在( m ，k ) f m n 约束模型中，当 m = k 时，实际上等价于硬实时系统，即k 个任务都必须满足截止期要求；当 k 一8 时，等价于软实时系统。显然，在统一描述中，硬实时和软实时系统都是 一种特殊的弱硬实时系统。 弱硬实时概念地提出丰富了实时系统服务质量( q u a l i t yo f s e r v i c e ，q o s ) 的 多样性。在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 的粒 度过粗，无法满足实时应用服务质量多样性的需求【1 1 l 。针对q o s 多样性，尽管 3 武汉理工大学硕士学位论文 s h i n 等曾提出统计实时的概念。但是，统计实时实际上无法保证截止期超出是 否分布均匀。例如，“保证截止期错过的概率小于1 0 仅仅表示在很长时间段 内截止期超出的统计分布。“每1 0 个任务中最多1 个截止期错过一和“1 0 0 0 个 任务中，前9 0 0 个任务截止期连续满足而后1 0 0 个截止期连续错过 均满足q o s 统计实时1 0 的要求，但是，两者提供的截止期错过的分布和要求明显是不同 的。而( m ，k ) f i n n 约束模型可以根据实时应用o o s 的要求设计参数m 和k ，从 而明确给出有限时间区间内，任务截止期错过的分布情况。在网络负载瞬间过 载时，弱硬实时调度可以保证多媒体实时应用在满足最低可接受性能的情况下 传输，从而增强网络的适应性，与g r 服务相比，还可以提高资源利用率；而 相比b e 保证，则解决了它无法在有限时间区间内保证q o s 的缺陷，这正是本 项目研究的出发点。 弱硬实时调度算法是整个弱硬实时理论的核心。在多媒体应用中，弱硬实 时服务质量需要由其调度算法保证。弱硬实时调度算法的研究，将提高具有弱 硬实时约束的多媒体应用在网络传输中的动态性能，实现在有限时间区间下衡 量q o s ，提高网络资源的利用率。本文将主要根据典型的弱硬实时约束规范， 提出一种新的约束，并实现其调度算法地设计。 1 2 国内外现状 实时系统通常由一系列互相作用的任务组成，其任务的内在特征是具有时 间要求，并且表现为截止期的形式。在实时系统中，任务的正确性不但依赖于 计算结果的正确性，还取决于产生结果的时间。而实时调度理论正是研究在实 时系统中，如何满足每个任务的功能和时间需求。 实时调度理论主要研究在给定一组任务集和资源时，于何时何处执行任务， 以满足每个任务的时间约束。对于给定任务时间特征包括到达间隔t ( i n t e r v a l a r r i v a lt t m e ) 、计算时间c ( c o m p u t a t i o nt i m e ) 、截止期d ( d e a d l i n e ) 和任务的调度方法，分析任务是否满足截止期要求，这一问题称为任务可调度 性判定问题。 早期的实时系统研究主要集中在硬实时调度理论的研究。早在1 9 7 3 年，对 于相互独立的硬实时周期任务，i j 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 ) 算法， 并证明了它们在固定优先级算法和动态优先级算法中分别是最优的，同时还给 4 武汉理工大学硕士学位论文 出基于系统利用率的r m 的可调度性判定条件u 墨( 2 1 一1 ) ( 其中n 为任务集 中任务的个数) 和e d f 的可调度性判定条件u 墨1 i l 引。 r m 算法自提出以来得到了广泛的研究和应用。目前已有大量的关于r m 算法及其各种情况下得扩展调度算法以及这些算法的可调度性判定的研究文 献。在经典文献【1 3 】中给出的可判定条件仅仅是充分的，l e h o c k y 对r m 算法的 特性进行了深入的分析，并推论了一个更为精确的基于利用率的可调度性判定 的充要条件，但这一算法的时间复杂性是伪多项式时间，复杂度较耐川。后来 h a r t 和t y a n 提出了多项式时间的判定算法，但只是充分而不是充要的判定条件 【”l 。但是上述提到的r m 算法可调度性判定条件都对调度模型作了一系列理想 的假设，忽略了一些重要的影响因素，例如截止期和周期的关系、调度的时间 开销和任务的相关性等，这就使理想的调度模型比现实情况要简单得多，从而 影响了其适用范围。当d t ，7r m 不再是最优，l e u n g 等提出了截止期单调 ( d e a d l i n em o n o t o n i c , d m ) 算法，并证明了其在固定优先级算法中，周期和截 止期不等情况下的最优性【1 6 1 。文献0 7 在考虑各种调度时间开销的情况下，提 出了可调度性判定条件。理想的r m 算法可调度性条件的一个重要的基本假设 是任务的相互独立性，即假设任务之间都是不相关得，每个任务的请求不依赖 于其他任务请求地开始或完成。但实际上，任务之间往往存在着种种联系，由 于共享资源而引起的同步问题是其中十分重要的一种。在多个共享某一个互斥 资源的任务当中，如果有一个任务已经进入该资源的临界区，其他任务就必须 等待该任务退出临界区，即使它们的优先级比该任务的优先级高，这样实际上 就改变了原来由r m 算法确定的优先级配置，这种情况称为优先级倒置，严重 时会造成高优先级任务的无限期等待【l 引。优先级驱动的实时调度都存在这样的 问题。可见，任务的相关性会对实时调度产生极大的影响，进而也影响了任务 的可调度性判定，因此必须在可调度性判定中考虑任务相关性。基于优先级倒 置这个问题已有几种解决方案，典型的有优先级继承协议( p r i o r i t yi n h e r e n c e p r o t o c o l ，p i p ) x 9 】和优先级上限协议( p r i o r i t yc e i l i n gp r o t o c o l ，p c p ) 1 2 0 。国内 的学者从九十年代开始陆续对r m 算法做了介绍和研究【2 1 彩l 。中科院软件所何 军博士的论文【矧，华中科技大学涂刚博士的论文f 2 5 1 对该算法都做过一定程度的 分析和改进。 在硬实时系统的研究中，动态优先级调度算法e d f 一直也是备受关注的研 究点。e d f 本质上是抢占式的，抢占的额外开销和抢占的关系降低了系统的可 5 武汉理工大学硕士学位论文 调度能力，影响着系统的性能。因此，j e f f a y 在1 9 9 1 年提出了适用于周期性和 非周期性任务的非抢占的e d f 调度性判定条件。国内学者在该领域的研究也获 得了诸多的结果。文献【2 6 】结合截止期和空闲时间这两个特征参数，综合设计 任务的优先级表。文献 2 7 1 中考虑了截止期和价值结合的调度策略，提出了结 合二者的两种不同的基于优先级表的实时任务调度算法。文献【2 3 】提出了一个 改进的抢占式e d f 调度算法，通过将遗传算法的优化方法离线计算得到的实时 任务启动时间作为目标系统的一个调度参数，减少抢占次数，改变抢占关系， 从而提高系统的可调度能力和实时性能，并用实验验证了改进的抢占式e d f 调 度算法的有效性。 由于硬实时系统任务( 包括周期和非周期两类) 的特征明显，相应的研究 已进行得相当透彻。相比之下，由于软实时系统的应用种类繁多，不易进行系 统的分类研究，所以研究软实时的算法也相当丰富。归纳一下大概主要有以下 几种g 1 ) 基于服务器模型的软实时任务调度算法 + 在软硬实时任务混合调度时，一般都采用基于服务器模型的调度。这些方 法的目的是在保证硬实时任务的同时，提高软实时任务的响应能力。一般归为 三类：后台执行法、带宽保留法、挪用法。后台执行法是为软实时任务制定较 低的优先级并作为后台任务执行，保证了硬实时任务的执行但没有采取措施提 高软实时任务的响应能力1 3 4 1 。带宽保留法包括优先级交换( p r i o r i t ye x c h a n g e ， p e ) 0 4 1 、延缓服务器( d e f e r r a b l es e r v e r , d s ) 3 4 1 ，伪周期服务器( s p o r a d i cs e r v e r , s s ) 3 5 】，多路服务器( m u l t i p l es e r v e r , m s ) 0 6 1 等。这些算法的共同特点是在保 证硬实时任务的同时，为软实时任务的执行保留了一定带宽( 或者c p u 时间) ， 大大提高了软实时任务的响应时间。挪用法的基本思想是：在保证硬实时任务 满足截止期要求的同时，尽量使用“挪出时间服务软实时任务，从而能提高 软实时任务的响应时间。 2 ) 软实时灵活调度算法 基于服务器模型的各种软实时任务调度算法大都考虑在w c e t 下的情况。 虽然采用w c e t 分析方法能够保证各种硬实时计算的正确性，但是缺乏灵活性 并容易造成资源浪费。灵活调度是软实时调度发展的一个新趋势【捌。在灵活调 度中，实时系统被看作一个控制系统，实时任务被看作各种采样信号，通过反 馈控制保持实时系统负载的稳定性和系统资源的高利用率。 6 武汉理工大学硕士学位论文 基于反馈控制理论方法，s t a n k o v i c 等提出了一种f c e d f 的灵活调度策略 i 掘3 9 1 。在该策略中，反馈调度器通过在线监测任务丢失率或c p u 利用率，采用 一定的控制算法( 如p i d ) ，经由o o s 支持的路由器对一系列可变执行时间软 实时任务的c p u 利用率估计值进行调节，以同时获得较低的任务丢失率和较高 的c p u 利用率。文献 4 0 1 对该策略进行了扩展。l i n 在文献f 4 1 】中，综合全局调 度和局部调度，设计了一种双回路反馈控制器。与文献 4 0 1 类似，其目标也是 维持任务丢失率在期望值附近，并获取较高的c p u 利用率。w e i 等运用混杂自 适应控制体系，有效的解决了实时系统本质非线性问题，并基于f c r t s 反馈 调度改进了系统的动态性斛4 2 1 。文献 4 3 1 贝j j 研究了带通信时延的实时控制系统， 针对c p u 资源变动和不可预知负载，分别为单回路和多回路控制系统设计了计 算资源的反馈调度策略。反馈控制算法都是借助系统负载的反馈值确定调度模 块是否接收当前实时请求，从而达到控制负载的目的。 在网络技术飞速发展之后，出现了很多基于网络的实时应用，称实时网络 应用。这些应用要求潜在网络性能的特殊支持，如可靠性、实时性、稳定性等 不同水平的q o s 。 普通互联网络由于其硬件的不可靠和负载的不可控而引起的性能不稳定 性，一般很难支持硬实时应用。而现行一般采用b e 策略来保证实时网络应用 的服务质量。b e 服务策略在传统的实时网络应用，如电子邮件( e m a i l ) 、文 件传输协议( 兀甲) 、终端机控制协议( t e l n e t ) 和超文本传输协议( m 1 p ) 等 方面运作很好。实时网络应用依赖于网络参数，如带宽、时延、时延抖动和正 常操作的丢失。对这些参数中任何一个的容忍度和敏感度随实时应用的不同而 大相径庭。如远程外科手术、在线交易系统等，要求这些参数的可靠性和保障 性传输。不断兴起的新应用，如家庭网络、智能装置、工厂供应链网络及多媒 体应用，也需要潜在网络以这些参数为依据提供不同水平的服务质量。所谓服 务质量q o s 是指“在网络中提供资源保证和服务区分的能力，一般包括对时 延、抖动和丢失率三个参数的评价【卯。虽然现在获得大量带宽的代价越来越小， 然而，高级多媒体应用的出现和互联网在日常生活中的普及，以及越来越多的 使用可能又会使得提供的带宽远远不够，而再次返回到最初带宽限制的情形。 在带宽限制时，多种应用共享带宽的网络中出现其他应用流量( 如t e l n e t ，哪 同口) 的情况下，b e 服务策略虽然能保证传输的可靠性，但必然导致网络拥塞， 从而会导致实时应用的任务经历不断变化和不可预测的时延和抖动。 7 武汉理工大学硕士学位论文 实时网络应用比如多媒体任务流，通常对端到端时延比较敏感，但能够容 忍一定程度的丢失( 任务错过截止期) ，通过插值等信号重构技术来保证其通信 的质量【4 4 1 。例如，为了保证正常理解声音，v o l p 电话要求1 5 0 3 0 0m s 的端到端 时延，过长的时延将导致音质变差甚至不易觉察，偶尔的个别任务丢失，并不 会影响通话的声音质量【4 5 l 。b e 服务支持任务的可靠传输，但不能保证时延， 也不支持丢失率。随着多媒体等实时应用的日益普及，原有的单一b e 服务策 略显然无法满足要求。对于不同的实时网络应用的行为和资源要求，人们开始 研究支持多种q o s 的策略及其调度算法。 实时网络应用由不断重复触发的任务构成任务流，一些学者考虑任务允许 丢失的情况，提出了在保证到达的任务都满足截止期要求的情况下，以丢失率 作为其q o s 的衡量尺度，称其为概率o o s 。基于概率o o s 的调度策略在瞬间过 载的情况下允许部分任务丢失，保证任务的概率到达，一定程度上提高了网络 带宽的利用率。 然而，概率q o s 是建立在无限长的时间区间内的一种统计q o s ，并不能满 足诸如多媒体等实时应用的需求。对多媒体等实时应用而言，其对任务的连续 丢失相当敏感，即使满足概率q o s ，但是如果任务连续丢失也可能会导致其一 小时间段上的q o s 严重下降，从而使信号无法重构或者重构的信号无法实现多 媒体应用q o s 的目标，满足实时应用的需求。为此必须研究实时网络应用的有 限时间区间上的概率q o s ，也称为弱硬实时q o s 。 从有限时间区间的角度，k o r e n 等提出的“s k i po v e r 约束( 一个实时应用 有一个s k i p l 天l 素s ，那么该应用对应的任务流中，每s 个任务允许有1 个被丢弃( 截 止期错过) ) ，成为最早一个描述弱硬实时q o s 的弱硬实时约束规范：随后， h a m d a o u i 等扩展了“s k i po v e r ，提出了( m ，k ) f i r m 约束( 当一个实时应用具有 ( m ，k ) f i r m 约束时，该实时应用的每连续k 个任务至少有m 个满足截止期要求) 1 7 , 8 l ；最近，b e r n a t 等丰富了( m ，k ) f i r m ，提出了四种弱硬实时约束规范： ( 臃，七) 一f i n n 、l 坍，七) 一f i r m 、彻，七) 一归铆、( m , - - i ) 一f i r m ，并且正式定义由这些 弱硬实时约束规范描述的q o s 为弱硬实时q o s l 9 , 1 0 1 。w e s t 等提出了等价于 l 彤，七l f i r m 的( x ，y ) 约束：对于一个任务流，任意y 个任务最多x 个截止期错过。 m o n t e z 等提出了( p + i k ) f i r m 的弱硬实时自适应模型，该模型结合任务窗口丢失 和文献f 3 7 1 中提出的非精确计算模型，但是由于非精确计算模型不适用于实时网 络应用，基于这种模型的算法没有得到更多的关注。 8 武汉理工大学硕士学位论文 基于弱硬实时q o s 的调度主要分为静态调度算法和动态调度算法，分别对 应基于窗口任务丢失模式固定调度和基于窗口任务丢失模式任意调度，并都有 了相应的一些研究成果。丢失模式固定也称固定p a t t e r n ，基于固定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 po 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 ) 算法，通过硬实时分析的方法给出了满足任意连续k 个任务中，k 1 任务的截止 期的可调度性判定条件，并证明“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 ) 算法，为可选任务提供更多的满足截止期的机会。对于一般具有 ( m i ，k i ) 一f i r m 约束的任务流t i ，r a m a n a t h a n 给出了一个设定固定- p a t t e r n 的公 式 ir1i 口。i i 孚i 蔓l ，口0 , 1 , 2 为任务到达序号 ( 1 1 ) 【l 畅l 他j 当a 值使得该公式1 - 1 成立时，对应的任务就为强制任务，否则为可选任 务。显然在公式1 - 1 给定的p a t t e r n 下，t - - 0 时刻为紧急临界时刻。对于任务 集里面的强制任务的可调度性问题，r a m a n a t h a n 给出了紧急临界状态的判定条 件。q u a r t 扩展了文献 4 7 q a 的固定t - p a t t e r n 公式，通过添加偏移周期，使得强 制任务分布更加均匀，从而弱化了临界状态的紧急程度，提高了强制任务的可 调度性，并证明了对于任意适用文献 1 0 5 中。p a t t e r n 的可调度性判定条件必然 适用q u a n 给定的p a t t e r n 。在周期、非周期任务共存的模型中，b e r n a t 等提出 e d p s ( e n h a n c e dd u a lp r i o r i t ys c h e d u l i n g ) ，进一步扩展到一般的具有d i - k + 1 ) 都满足约束如。满足约束九记为：i 一九。 例3 3 ：当k = 7 时，特征子序列妒= 1 1 1 0 1 0 0 满足( 4 ，7 ) 一f i r m ；( 了) 一f i r m ； ( 3 7 ) 一肋；( 2 7 ) 一f i r m 。 定义3 9 - 特征序列满足约束( 坍，七) 一f i r m ，其的任意子k 序列中至少有m 个1 。 缈i _ ( m ，k ) - f i r m 营v e s ( ) ，口( | ) 芝m 对一个具有( m ，七) 一f i r m 约束的任务流来说，任意一个长度为k 的窗口中，至 少有m 个任务满足其截止期要求，也即在任意窗il k 中至多只能有k m 个任务丢 失。 定义3 1 0 ：特征序列满足约束i 小，七) - f i r m ，其的任意子k 序列中至多有m 个0 。 卜( 而) 一f i r m v 。s ) ，r ) s 棚 武汉理工大学硕士学位论文 对一个具有i 小，七l j 5 f 删约束的任务流来说，任意一个长度为k 的窗口中，至 多允许有m 个任务丢失，同样的意思也表明至少有k m 个任务满足截止期要求。 事实上，i 小，七) 一f i r m 和( m ，七) 一乒册约束具有等价的意义。 定义3 - i i ：特征序列满足约束( m ，k ) 一f i r m ，其的任意子k 序列中至少包 含一个最短长度为m 的好序列。 i 一( m ，k ) 一声册铮v c o e s ( ) ，re s 4 ( ) 对一个具( m ，k ) 一f i r m 约束的任务流来说，任意一个长度为k 的窗口中，至少 有m 个任务连续满足截止期要求，同样的意思也表明连续k m + 1 个任务丢失肯定 导致任务流不满足约束要求，即如果0 k 辨+ 1e s b _ + 1 ( ) ，则不满足( m ，七) 一f i r m 。 显然对于相同参数的弱硬实时约束( 聊，七) 一f i r m 和( m ，七) 一f i r m ，后者具有更为严 格的约束要求。 定义3 1 2 ：特征序列c o 满足约束( 所，七) 一p r m ，其的任意子k 序列中不包含 最大长度大于m 的坏序列。 缈卜( 朋，七) 一y i r m 营v s ( ) ，o 埘“芒s “+ 1 ( 静o n + 1 诺s ”“( 妨 对一个具( m ，七) 一f i r m 约束的任务流来说，任意一个长度为k 的窗口中，连 续丢失的任务长度不能大于m ，否则该任务流不满足约束要求。显然獗，七) 一i r m 仅考虑了连续丢失，实际上与窗口的长度k 没有关系。 此外，w e s t 等提出了一个类似的弱硬实时约束( x ，y ) 。 定义3 1 3 ：任务流至多错过其任意连续任务窗i ：l y 个截止期中的x 个，记为 ( x ，y ) 。 例3 - 4 ：当y = 9 时，假设给定的。口= 0 0 1 1 1 1 0 1 0 ，则满足x = 4 的约束要求，而不 满足x = 3 的约束要求。 定义3 - 1 4 ：特征序列满足约束( x ，y ) ，其的任意子y 序列中至多有x 个o 。 i _ ( x ，y ) 尊v s y ( ) ，r ( ) s x 对一个具有( x ，y ) 约束的任务流来说，任意一个长度为y 的窗口中，至多允许 x 个任务丢失。事实上，i m ，七) 一f i r m 约束和(