（计算机应用技术专业论文）支持qos的弱硬实时linux系统研究.pdf

啥尔滨理_ 大学t 学硕：卜学位论文 支持q o s 的弱硬实时l i n u x 系统研究 摘要 随着计算机技术的发展，特别是网络多媒体技术的发展，多种实时应用 以及非实时应用共存于一个实时系统中的情况也会越来越普遍。实时系统需 要对服务质量( q u a l i t yo fs e r v i c e ，q o s ) 支持的情况也将会经常遇到。 在实时操作系统领域，l i n u x 系统越来越流行，由于其代码开源，将会 有许多实时系统采用l i n u x 作为操作系统。因此，建立一个基于l i n u x 的开放 式实时系统是一件急需要解决的工作。研究与开发基于l i n u x 的开放式实时 系统将会很大程度地提高l i n u x 的应用能力，适应现代计算机系统以及实时 系统的发展。 基于上述分析，本文从弱硬实时( w e a k l yh a r dr e a l t i m e ) 系统的概念出 发，详细介绍了弱硬实时系统模型，重点研究了基于窗口约束的两个调度算 法d b p 和e d b p ，并针对上述算法中存在忽略任务流历史状态的0 1 信息分 布的问题，提出两个新的概念进入失效完全距离和退出失效完全距离，给出 了距离计算公式，设计并实现了t d b p ( t o t a ld i s t a n c eb a s e dp r i o r i t y ) 算法。 t d b p 算法进一步扩展了d b p 和e d b p 算法的优先级设置，很好地解决了上 述问题。 在弱硬实时调度算法的基础上，本文又对开放式实时l i n u x 系统调度框 架做了进一步的研究。在研究过程中发现其集成的调度算法存在调度公平性 的不足，并且在系统过载时不能满足实时网络应用的q o s 要求，而t d b p 集 成至l j l i n u x 系统能很好地解决上述问题，所以本文设计了w h r t - l i n u x 系统模 型，从而使l i n u x 系统更具灵活性，更适合实时网络的多媒体应用。 最后，本文在系统地学习了o p n e t 仿真软件的结构、原理、仿真方法 的基础上，在o p n e t 仿真平台上实现了e d b p 和t d b p 调度算法，并对算法 的动态失效概率和任务时延两个参数进行了性能测试。仿真结果表明， t d b p 算法在动态失效率、时延和调度的公平性等方面都优于e d b p 。 关键词弱硬实时；开放式实时系统；伽，七) - 约束；服务质量；网络仿真 哈尔演理t 人学r 学硕i j 学位论义 r e s e a r c ho nw e a k l yh a r dr e a l - - t i m el i n u xs y s t e m s u p p o r t i n gq o s a b s t r a c t w i t ht h e d e v e l o p m e n t o f c o m p u t e rt e c h n o l o g y , i np a r t i c u l a r t h e d e v e l o p m e n t o fn e t w o r km u l t i m e d i at e c h n o l o g y , i tw i l lb em o r ea n dm o r e p o p u l a rt h a ta p p l i c a t i o n so fr e a l t i m ea n du n r e a l t i m ea p p l i c a t i o nc o e x i s ti no n e r e a l - t i m es y s t e m r e a l - t i m es y s t e m st os u p p o r tq o s ( q u a l i t yo fs e r v i c e ) w i l lb e o f t e ne n c o u n t e r e d i nr e a l t i m eo p e r a t i n gs y s t e m ，l i n u xw i l lb e c o m em o r ea n dm o r ep o p u l a r b e c a u s eo fi t so p e ns o u r c ec o d ea n dt h e r ew i l lb em a n yr e a l t i m es y s t e m st o a d o p tl i n u xa so p e r a t i n gs y s t e m t h e r e f o r e ，i ti su r g e n tw o r kt oe s t a b l i s hao p e n r e a l - t i m es y s t e mb a s e do nl i n u x t h er e s e a r c ha n dd e v e l o p m e n to fo p e nr e a l t i m el i n u xs y s t e mw i l lg r e a t l yi m p r o v et h ea p p l i e da b i l i t yo fl i n u x ，w h i c ha d a p t t ot h ed e v e l o p m e n to fm o d e r nc o m p u t e rs y s t e m sa n dr e a l t i m es y s t e m o nt h eb a s i so ft h ed e f i n i t i o no fw h r t ( w e a k l yh a r dr e a l t i m e ) ，t h i s d i s s e r t a t i o ns u m m a r i z e st h ec o n s t r a i n tq u a l i f i c a t i o n so ft h ee x i s t i n gw h r ta n d s c h e d u l i n ga l g o r i t h m s ，p l a c e se m p h a s i so nt h ed i s c u s s i o no fd b pa l g o r i t h ma n d e - d b p a l g o r i t h m t w oc o n c e p t sa r ep r o p o s e da c c o r d i n gt ot h ed e f i c i e n c i e so ft h e t w oa l g o r i t h m s ，n a m e l yt o t a ld i s t a n c eo fe n t e r i n gi n v a l i d a t i o na n dt o t a ld i s t a n c e o fa b o r t i n gi n v a l i d a t i o n ，a n dt h ed i s t a n c ec a l c u l a t i o ne q u a t i o ni s p r e s e n t e d t d b p ( t o t a ld i s t a n c eb a s e dp r i o r i t y ) e x t e n d st h ep r i o r i t ys e t t i n gm e t h o d so f d b pa n de - d b pf u r t h e rm o r ew h i c hs o l v et h e p r o b l e m o ft h e0 1s t a t e d i s t r i b u t i n gi n f o r m a t i o ni g n o r e di nb o t ha l g o r i t h m s i nt h eb a s i so fw e a k l yh a r ds c h e d u l i n ga l g o r i t h m ，t h i sp a p e rm a k eaf u r t h e r r e s e a r c hc o m b i n e dw i t ho p e nr e a l t i m el i n u xs y s t e m i nt h ep r o c e s so fr e s e a r c h ， i ti sf o u n dt h a tt h es c h e d u l i n ga l g o r i t h mo ft h eo p e nr e a l - t i m el i n u xs y s t e mh a s t h ed e f i c i e n c yo ns c h e d u l i n gf a i r n e s s ，w h i c hc a nn o tm e e tt h eq o sr e q u i r e m e n t s o fr e a l - t i m en e t w o r kw h e nt h es y s t e mi so v e r l o a d e d h o w e v e r ，t d b pc a ns o l v e t h ep r o b l e ma b o v ew e l l s o ，t h i sd i s s e r t a t i o np r e s e n t e dt h ew h r t - l i n u xs y s t e m m o d e l w h i c hm a k e sl i n u xs y s t e mm o r ef l e x i b l e a n ds u i t a b l ef o rr e a l 。t i m e n e t w o r km u l t i m e d i aa p p l i c a t i o n s f i n a l l y ，b a s e do nt h es t u d yo ft h ep r i n c i p l ea n ds t r u c t u r eo fo p n e t , t h e e - d b pa n dt d b pa l g o r i t h m sa r er e a l i z e do no p n e t 10 。0 k jl1m o d e l e rp l a t f o r m t h es i m u l a t i o nr e s u l t ss h o wt h a tt d b pi sb e t t e ro nd y n a m i cf a i l u r er a t e ，t i m e - d e l a ya n df a i r n e s so fs c h e d u l i n gc o m p a r e dw i t he - d b e k e y w o r d sw e a k l yh a r dr e a l t i m e ，o p e nr e a l - t i m es y s t e m ，( 聊，尼) _ f i r m ，q u a l i t y o fs e r v i c e ，n e t w o r ks i m u l a t i o n i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文支持q o s 的弱硬实时l i n u x 系统研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期问独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己发 表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名： 评字 日期：a 渺 年多肜d 日 哈尔滨理工大学硕士学位论文使用授权书 支持q o s 的弱硬实时l i n u x 系统研究系本人在哈尔滨理工大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工 大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨 理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文 和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、 缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密留。 ( 请在以上相应方框内打) 作者签名： 导师签名： 日期：j _ o o q 年3 月a d 日 同期：o d 口7 年了月a o 日 哈尔滨理t 火学t 学颂卜# 位论义 1 1 研究背景及意义 第1 章绪论 实时系统是一种不但要考虑其计算结果的j 下确性而且要考虑其结果何时 产生的系统。实时系统在许多领域，譬如航天，工业控制，网络通信以及视 频会议系统中都可以看到，已广泛应用在军事和民用领域。然而，随着计算 机技术的不断发展以及基于l i n u x 应用的日益提高，多种类型的实时应用， 包括硬实时应用，软实时应用以及非实时应用共存于一个系统的情况也越来 越广泛。同时i p v 4 也渐渐被i p v 6 所取代，网络以及多媒体应用也将r 益普 及，从而有大量的实时系统接入i n t e r n e t ，并与网络多媒体应用形成了密切 关系，因而迎来了嵌入式i n t e r n e t 兴起与发展。开放式实时系统的概念即是 针对这种实际情况提出来的。 现在实时系统的发展又呈现出许多新的特点，比较突出的是诸如像视频 点播、视频会议、数字图书馆以及远程教学等这样的软实时系统越来越普 及。这些软实时系统往往要求在特定的时间内处理完特定数量的流媒体信 息，并且要求端系统和网络系统都必须支持q o s ，因而这些软实时系统就需 要有一种能很好地满足其q o s 要求的调度模型。该调度模型应具有相当大的 灵活性，这种灵活性体现在能够定量地描述软实时系统满足时限与不满足时 限的情况，这就要求凋度算法在该系统损失帧时能很好地控制损失帧情况， 使系统能较好地满足其q o s 的要求。因此人们提出了弱硬实时的概念，弱硬 实时概念的提出，丰富和扩充了实时系统理论，满足了实时网络应用的理论 需求，丰富了实时系统服务质量的多样性，也为实时系统的统一描述提供了 理论基础。弱硬实时系统通过参数的动态调整可以统一描述实时系统。在网 络负载瞬问过载时，弱硬实时调度可以保证多媒体实时应用在满足最低可接 受性能的情况下传输，从而增强网络的适应性，提高资源利用率，能在有限 时间区问内保证q o s 。 在实时操作系统领域，l i n u x 将会越来越流行，将会有许多实时系统采 l i n u x 作为操作系统。因此，建立一个基于l i n u x 的多种实时应用和非实时应 用的q o s 支持的开放式实时系统是一件急需要解决的工作。研究与开发基于 l i n u x 的丌放式实时系统将会很大程度地提高l i n u x 的应用能力，适应现代计 哈尔演理t 人学t 学硕l j 学位论文 算机系统以及实时系统的发展。 本课题是自拟题目。 1 2 国内外研究现状 1 2 1 弱硬实时系统的研究现状 近年来，随着信息技术和互联网技术的飞速发展，实时系统的应用范围 也发生了巨大变化。特别是在网络通信中，实时网络传输、多媒体处理、无 线传感器网络等系统都需要实时技术的支持。新兴的实时应用为实时系统的 发展提出了新的要求，尤其是网络多媒体音频、视频信号等应用具有在有限 时间区间内有限数量的任务丢失并不会导致图像、语音的质量显著下降的特 性。显然，传统得简单的h r t 和s r t 的分类已经无法确切地描述这类典型的 实时网络多媒体应用，相应的基于h r t 和s r t 的最优实时调度算法在网络 实时多媒体等应用中将不再是最优。这一类实时网络应用，为实时系统和基 于实时系统的调度理论地研究提出了新的挑战，这也正是本文研究的背景。 弱硬实时概念地提出为实时系统的统一描述提供了理论基础。弱硬实时 系统通过参数的动态调整可以统一描述实时系统。在( m ，七) f i r m 约束模型 中，当m = k 时，实际上等价于硬实时系统，即七个任务都必须满足截止期 要求；当k o d 时，等价于软实时系统。显然，在统一描述中，硬实时和软 实时系统都是一种特殊的弱硬实时系统。 弱硬实时概念地提出丰富了实时系统服务质量的多样性。在o o s 多样性 上，此前只规定硬实时和软实时，在实时网络中分别对应提供保证响应 ( g u a r a n t e dr e s p o n s e ，g r ) 服务和最大努力( b e s te f f o r t ，b e ) 服务。在提供 g r 服务时，以实时系统负载的峰值为基础，充分预留了大量的网络资源， 绝对保证实时任务的截止期要求，导致系统过渡地支持了参数裕度，同时也 浪费了大量的网络资源。从实用的角度看，这种方法的代价过高。在提供 b ej 艮务时，可以提供可靠的服务并充分利用资源，但是不能够保证实时任 务的截止期要求。因此，硬实时和软实时性能之间缺乏良好的过渡，即q o s 的粒度过粗，无法满足实时应用服务质量多样性的需求。针对q o s 多样性， 尽管s h i n 等曾提出统计实时的概念| 2 1 。但是，统计实时实际上无法保证截止 期超出是否分布均匀。例如，保汪截止期错过的概率小于1 0 仅仅表示在 很长时间段内截止期超出的统计分布。“每1 0 个任务中最多1 个截止期错 哈尔滨理t 人学t 学硕l 学位论义 过”和“1 0 0 0 个任务中，f i 9 0 0 个任务截止期连续满足而后1 0 0 截止期连 续错过”均满足q o s 统计实时1 0 的要求，但是，两者提供的截止期错过的 分布和要求明显是不同的。而( 肌，七) f i r m 约束模型可以根据实时应用q o s 的 要求设计参数m 和k ，从而明确给出有限时间区间内任务截止期错过的分布 情况。在网络负载瞬间过载时，弱硬实时调度可以保证多媒体实时应用在满 足最低可接受性能的情况下传输，从而增强网络的适应性，与g rj 艮务相 比，还可以提高资源利用率；而相l k b e 保证，则解决了它无法在有限时间 区间内保证q o s 的缺陷。 h a m d o u i 最早用伽，七) f i r m 约束模型从有限时间区间内允许部分任务丢 失的角度来描述网络多媒体的服务质量问题，并提出了基于距离优先级 ( d i s t a n c eb a s e dp r i o r i t y ，d b p ) 的方法1 3 1 。随后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 ) 系统。所谓弱硬 实时系统是指在有限时间窗口中，任务截止期被满足或者错过符合一定分布 要求的实时系统。伽，k ) f i r m 是一种典型的弱硬实时约束模型，实时应用带 有类似( m ，七) f i r m 约束的称其具有弱硬实时约束。 基于弱硬实时q o s 的调度主要分为静态调度算法和动态调度算法，分别 对应基于窗口任务丢失模式固定调度和基于窗口任务丢失模式任意调度，并 都有了相应的一些研究成果。丢失模式固定也称固定“p a t t e r n ，基于固定p p a t t e r n 的静态调度算法主要把任务分为强$ 1 j ( 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 p o 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 c r 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 np o s s i b l e ) 算法，为可选任务提供更多的满足截止期的机会 1 。对于一般具有i ，缸) f i r m 约束的任务流t ，r a m a n a t h a n 给出了一个设定 固定“p a t t e r n 的公式( 1 1 ) ，其中口为任务到达序号，当口值使得该公式成立 时，对应的任务就为强制任务，否则为可选任务嵋。显然在上面公式给定的 i x - p a t t e r n 下，t = 0 时刻为紧急临界时刻。对于任务集罩面的强制任务的可 调度性问题，r a m a n a t h a n 给出了紧急临界状态的判定条件。q u a 在文献m 1 中 扩展了固定u p a t t e r n 公式，通过添加偏移周期，使得强制任务分布更加均 匀，从而弱化了临界状态的紧急程度，提高了强制任务的可调度性，并证明 哈尔演理t 大学t 学硕 ：学位论义 了对于任意适用“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 ) 1 ，进一步扩展到一般的具有 口s 口、不同任务弱硬实时约束不同、周期和非周期任务并存、资源互斥 等通用模型中，提出了b m s ( b i m o d a ls c h e d u l e r ) 策略佃1 。m o k 贝l j 证明了静态 非重叠窗口调度是强意义上的n p h a r d 问题，当c 都为固定单位长时，给出 了静态非重叠窗口基于p 公平的e d f 算法可调度判定的充分性条件。文献 随1 0 川中，, m i l s ， y i n 等把i x p a t t e r n 和w f q ( w e i g h t e d f a i r q u e u i n g ) 、 w f 2 q ( w o r s t c a s e f a i rw e i g h t e d f a i rq u e u i n g ) 相结合，分别提出了( 肌，七) w f q 和沏，七) w f 2 q 算法，利用网络演算的方法，研究了i x - p a t t e r n 中强制任 务的时延上界，并通过网络仿真和实验的方法验证了这些方法在提高网络利 用率和保证实时应用q o s 的有效性，扩展了w f q 算法的适用范围。 叫刚鲁j m 1 ， 针对单跳行为( p e r h o pb e h a v i o r ，p h b ) ，依据任务接近伽，七) f i r m 约束 失效状态的距离，h a m d a o u i 等提出了d b p 调度算法；r a m a n a t h a n 用概率方 法分析了d b p 的性能并证明了其比单优先级在动态性能保证方面的优越性： 文献2 1 中提出了与进入失效距离对称的概念退出失效距离，并基于此概念 扩展了d b p 优先级设置方法，改进了d b p 性能；由于d b p 算法在优先级设置 过程中只考虑该任务流本身情况而忽视其他任务流，实质上是局部优先级没 定方法，s o n g 等从可调度性和系统失效时间的观点出发，给出了周期任务 可调度的两个必要条件，并且通过考虑不同任务流任务之间时间参数特性的 相互影响关系提出了m a t r i x d b p 算法n 引；针对非周期任务流( p o i s s o n 过程) ， 从系统动态失效的概率观点，文献1 中提出了等价矩阵( e q u i v a l e n tm a t r i x ， e m a t r i x ) d b p 算法。w e s t 等基于“，y ) 约束做了系列的研究，提出动态窗口 约束调度( d y n a m i cw i n d o w c o n s t r a i n e ds c h e d u l i n g ，d w c s ) 算法，虚拟截止 期调度( v i r t u a ld e a d l i n es c h e d u l e r ，v d s ) 。针对两种基于弱硬实时约束模型 的经典算法d w c s 和d b p ，陈积明博士从动态失效概率方面进行了性能比 较。k r i s h n a m u r t h y 贝, 4 在网络协处理器上成功应用了d w c s ，明显改进了多媒 体服务器的动态性能。随后，吴彤等人又提出了给出任意窗口约束调度 ( a n yw i n d o wc o n s t r a i n ts c h e d u l e ，a w c s ) 算法及其简化算法k 窗口约束调度 ( k - w i n d o wc o n s t r a i n ts c h e d u l e ，k w c s ) ，降低了系统在重度过载时的q o s 4 哈尔滨理r 人学t 学颂f j 学位论义 退化速度5 1 。 对于多跳行为( m u l t i h o pb e h a v i o r ，m h b ) ，l i n d s a y 提出了d b p m ( m o d i f i e dd b p ) ，该算法主要提出了中间节点截止期的分配方法( 按照h o p 数平均截止期) ，并在中问节点采用了d b p 算法；利用任务流在局部节点可 以不满足，七) f i r m 约束，而只需满足链路端对端，七) f i r m 的特点， s t r i e g e l 进一步改进了d b p m 算法，提出了e d b p ( e n h a n c e dd b p m ) i 肩j 度算法 【1 6 】 o 弱硬实时概念及相关算法提出以来，分别在多媒体系统、能量有效约束 系统、控制系统、工业网络系统c a n ( c o n t r o l l e ra r e an e t w o r k ) 等系统中进行 了应用研究。 1 2 2 国内外实时l i n u x 发展现状 实时调度是保障实时系统重要特性的重要手段之一，国内外在这方面的 研究也由来已久。实时调度理论研究主要包括硬实时，软、硬混合实时，弱 硬实时三个方向。 在硬实时方面典型的有静念优先级r m 算法和动态优先级算法e d f 算 法。r m ( r a t em o n o t o n i c ) 是一种典型的静态优先级调度算法，它根据任务的 执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高 的优先级。e d f ( e e a l i e s td e a d l i n ef i r s t ) 是使用最多的一种动态优先级调度算 法，该算法给就绪队列中的各个任务根据它们的截止期限( d e a d l i n e ) 来分配 优先级，具有最近的截止期限的任务具有最高的优先级。 在针对各种类型实时任务的混合调度方面，已经有一些研究成果。以下 是几种典型方法： 1 后台处理( b a c k g r o u n dp r o c e s s i n g ) 法 这种方法首先满足前台周期 任务的运行需要，在处理器空闲时以先来先服务f c f s ( f i r s tc o m ef i r s ts e r v e ) 次序调度执行后台非周期任务。该方法保证了硬周期任务的执行，但它没有 采取有效措施来减少软非周期任务的响应时间。 2 基于服务器( s e r v e rb a s e d ) 方法基于服务器的算法，又称为带宽预 留( b a n d w i d t hp r e s e r v i n g ) 算法，其主要思想是，在保证满足周期任务截止期 的前提下，引入一个或者几个额外的周期任务使用定制的处理器带宽作为服 务器来处理非周期任务。根据周期任务调度算法的不同，带宽预留算法又可 以归结为固定优先级服务器算法与动态优先级服务器算法，典型的是由 呛尔滨理t 人学t 学硕f j 学位论文 l e h o c z k y 等提出的可延期服务器d s ( d e f e r r a b l es e r v e r ) 算法引和限定截止期 的可延期服务器d d s ( d e a d l i n ed e f e r r a b l es e r v e r ) 算法等引。这些算法的共同 点是为软实时非周期任务的执行保留了一定的c p u 时间( 带宽) ，软实时非周 期任务在使用完带宽后需要等待下次带宽被充满后才能再次投入运行。带宽 保留法能大大提高软实时非周期任务的响应时间，但它们在保留带宽的同时 限制了任务对c p u 的使用。 3 基于时间空闲( s l a c kb a s e d ) 方法这类算法的主要思想是通过离线或 者在线分析从周期任务调度的空隙获得尽可能多的处理时间来处理非周期任 务。基于空闲时间的方法主要包括空闲时间偷取( s l a c ks t e a l i n g ) 法、时间片 移位( s l o ts h i f t i n g ) 方法与双重优先级( d u a lp r i o r i t y ) 法托引。该方法在保证 硬实时周期任务不错过最后期限的同时，尽量使用周期任务集挪出的时间。 若挪用不当会造成周期任务集不可调度。周期任务集在使用不同调度算法 时，可挪用时间是不同的，通常分为基于固定优先级的算法妇3 和基于动态优 先级的算法心屯2 引。 基于动态优先级的算法能够获得很好的响应时间，但使用动态优先级调 度时，周期任务的最大挪用时间的理论计算复杂度为q 研为周期任务的个 数) 。这使得进行直接计算将很费时间，所以现有算法多是近似算法。如 b u t t a z z o 的t b ( 0 算法幢引，r i p o l l 的e e s s 算法幢 。 s p u r i 等人的e d l 算法幢8 2 引基于c h e t t o 在文献1 中理论提出。e d l 算法对 周期任务执行过程中的空闲时间进行分析，可以精确求得周期任务集的最大 可挪用时间。但由于其只能从任务集的角度计算可挪用时间，忽略了单个任 务的特性，所以计算量过大，其计算复杂度为q ( 为周期任务集在一个超 周期中的到来次数之和) 。 在国内，基于混合调度的算法研究主要有华中科技大学计算机科学与技 术学院涂刚等人通过定义“调度”和“逆调度”，提出一种精确求解周期任 务集在使用e d f 算法调度时最大可挪用时间的方法，在此基础上，提出了用 于缩短非周期任务响应时间的调度算法一i s a ( i d l es t e a l i n ga l g o r i t h m ) 。中 国科技技术大学计算机科学与技术系龚育昌等人提出的一种按严格比例派发 服务的混合实时调度算法r p d s 。坨1 ( r i g o r o u s l yp r o p o r t i o n a ld i s p a t c h i n g s e r v e r ) 。 复旦大学的朱响赋博士对传统开放式实时系统的凋度方法进行了深入研 究，提出了一种新的开放式实时系统d w c s o r t s ( d w c s o p e nr e a l t i m e s y s t e m ) ；在此基础上，充分利用d w c s 特点，提出了丌放式实时系统的自 哈尔滨理t 人学t 学硕l j 学f 蕾论文 适应q o s 调度方法，结合具体的操作系统平台( l i n u x ) ，讨论了集成调度框架 的设计与实现方案。d w c s o r t s 把传统的二层调度框架依据实时l i n u x 的 特点扩充到- - 三层结构，系统如不需要支持硬实时任务，可以采用二层结 构，当需要支持硬实时任务时，采用三层结构，解决开放式实时系统中的多 类型任务调度问题。通过把具有某些共同特征的不同方法集成到一个统一的 调度框架中，d w c s o r t s 可以同时支持多种类型的实时任务以及非实时任 务的并发运行。对于在系统中同时运行的非相关的实时或非实时应用程序， 可单独进行开发和验证，并可选择不同的局部调度器，再由系统支持它们的 统一调度。另外，d w c s 调度对开放式实时系统下的服务质量控制有很好的 支持，并提供了相应的解决方法。相对于现有的许多方法，该调度框架可支 持的任务类型更广泛，并且有良好的可扩展性。 1 3 本文的研究内容 本论文的研究目的是设计一个能够支持q o s 的弱硬实时l i n u x 系统，使 其能更好地适应实时网络应用领域。基于此出发点，本论文的主要研究内容 如下 1 研究弱硬实时系统模型及其调度算法，找出现有算法不足提出改进 方案，为下一步调度模型的搭建提供算法基础。 2 研究网络q o s ，给出仿真实验的性能指标。 3 研究d w c s o r t sl i n u x 系统模型，并加入改进后的弱硬实时算法。 4 学习使用o p n e t 网络仿真软件，对改进后的弱硬实时调度算法进行 实时性能测试。 哈尔滨理t 人学t 学硕i ：学化论文 第2 章网络q o s 概述及测量参数 以开放性、分布性和综合性为主要特征的下一代网络( n g n ) 技术正在深 刻地改变着传统电信网的观念和体系结构。n g n 采用分层、开放的体系结 构，其主要技术优势是各层间采用开放的协议或a p i 接口，从而有利于打破 传统电信网络封闭的格局，实现多种异构网络间的融合。更为准确地说 n g n 体系通过将业务与呼叫控制分离，呼叫控制与承载分离来实现相对独 立的业务体系，使得上层业务与底层的异构网络无关，从而为实现业务提供 了更为广阔的空间。然而，虽然n g n 是网络技术和网络融合发展的趋势， 但n g n 本身还有待成熟和完善，特别是在服务质量方面。下一代网络是以 软交换技术为核心的分组网络，而能否有效保证分组网络承载多类型业务时 的服务质量，则是通信网络向下一代网络演进的关键陋引。 网络q o s 即i p 网络的服务质量，它是指i p 分组或流通过网络时的性能， 这种性能可通过一系列可度量的参数来描述。它的目标是提供端到端的服务 质量保证。 2 1 网络服务质量的概念 服务质量是一组服务要求，网络必须满足这些要求才能确保数据传输的 适当服务级别。这些服务要求以q o s 功能的行业标准为基础。q o s 使得实时 程序能最有效地利用网络带宽。由于q o s 能为某个保证级别提供充足的网络 资源，所以它为共享网络提供了与专用网络类似的服务级别。q o s 保证是指 某个服务级别，该服务级别可以使程序按照指定的速率并在指定的时间帧内 传输数据。 当前，众多国际标准化组织和研究机构都对如何实现分组网络承载业务 的q o s 保证投入了极大的热情，并已经定义、规范和应用了多种类型的q o s 控制机制，如基于服务优先级的接入控制、拥塞反馈、流量的汁量和测量、 q o s 选路和流量工程、q o s 策略及策略配置、排队和调度、资源预留( 如 r s v p ) 、服务等级管理以及服务费率表征和流量标识等。同时，作为当前通 信领域的研究热点，各项新的q o s 保证机制的提出及对已有技术的改进也层 出不穷。熟悉并在网络建设中适当地应用这些技术，对于提高分组网络的 q o s 保证能力是十分有益的。 8 哈尔滨理工人学t 学硕i j 学位论文 然而，由于网络基础设施的庞杂性，实现端到端的q o s 并非易事。影响 网络q o s 的因素有很多，网络q o s 控制涉及到构成网络的每一个节点和元 素，从网络链路与协议到路由器、交换机、服务器的硬件以及软件体系结 构。计算机互联网络发展至今，已成为一个庞大的非线性复杂巨系统，而且 系统的规模和用户数量巨大且仍在不断增长，异质异构的网络不断融合发 展，致使网络协议体系庞杂。垂直方向上呈现出多样化的层次结构，而水平 方向上又以地域和功能为标准进一步形成分布且多级的架构，在业务性质上 表现为多种业务的集成与综合，业务量突发性日渐明显，且不同业务要求不 同的q o s 保证。网络节点间，节点与数据分组间由于协议而产生的非线性作 用以及用户之间的合作与竞争，使网络行为呈现出相当的复杂性并且难以预 测。因此，要真正实现针对各类网络用户提供端到端的q o s 保证，仍有很长 的路要走。 2 2l 1 e t f 的q o s 体系结构 目前互联网工程任务组( t h ei n t e r n e te n g i n e e r i n gt a s kf o r c e ，简称i e t f ) 把q o s 体系划分为两大类综合服务体系( i n t s e r v ) 和区分服务体系 ( d i f f s e r v ) 。 2 2 1i n t s e r v 集成业务体系结构 1 基本概念i n t s e r v 模型的基本思想是资源预留。在传送数据之前，根 据业务的服务质量需求进行网络资源预留，从而为该数据流提供端到端的服 务质量保证。i n t s e r v 的目的是为尽力而为的i n t e r n e t 增加一些端到端的服 务，以适合新出现的实时媒体流和交互式应用。 在i n t s e r v 模型中最基本的概念是“流”( f l o w ) ，是指具有相同的源l p 地 址、目的i p 地址、端口号的一串彼此相关的数据包。实时应用被看成一个个 流( f l o w ) 。 2 服务模型i n t s e r v 定义了4 个功能部件，r s v p ( r e s o u r c er e s e r v a t i o n p r o t o c 0 1 ) 、接纳控制( a d m i s s i o nc o n t r 0 1 ) 、分类器( c l a s s i f i e r ) 、队列调度器 ( s c h e d u l e r ) ，网络中的每个路由器都需要实现这4 个部件，如图2 1 所示。 综合服务的优点： ( 1 ) 能够提供有保证的端到端的q o s 。 ( 2 ) r s v p 在源和目的地之间可以使用现有的路由协议决定流的通路。 哈尔演理t 人学t 学硕f j 学位论文 r s v p 使用i p 包承载，使用“软状态”的概念，通过周期性的重传p a t h 和 r e s v 信息并分析，对网络拓扑的变化做出反应。即对原有路由协议没有影 响。 ( 3 ) 支持从一个源到一个目的地( u n i c a s t ) 或一个源到多个目的地 ( m u l t i c a s t ) 的q o s 服务。 图2 - 1i n t s e r v j 艮务模型 f i g 2 1i n t s e r vs e r v i c em o d e l 综合服务的缺点： ( 1 ) 对现有路由器的改造十分复杂。由于需要进行端到端的资源预留， 必须要求从发送到接收之间所有路由器都支持r s v p 和许可控制协议，同时 每个路由器还要花费大量的资源来维护和更新数据库( 如链路状态数据库) 。 ( 2 ) 综合业务模型下的预留状态信息是与业务流的个数成正比的，这使 得路由器的负担会随着网络的扩大、业务流的增多而加重，网络的扩展性不 好。 ( 3 ) 该模型不适合于短生存期的流。在i n t s e r v 中，r s v p 进行的资源预 留是单向的，因此必须对其规定两个方向的资源预留，从而增加网络开销。 在短生存期的流占大多数的网络中，采用i n t s e r v 就得不偿失了。 总之，综合服务能够在i p 网上提供端到端的o o s 保证。但是，综合服务 要求端到端的信令，对路由器的要求很高，当网络中的数据流数量很大时， 路由器的存储和处理能力会遇到很大的压力，在实际运营的网络中几乎无法 实现。因此，综合服务可扩展性很差，难以在i n t e r n e t 核心网络实施，目前 业界普遍认为综合服务有可能会应用在网络的边缘上旧圳。 哈尔滨理t 大学t 学硕f 。学位论文 2 2 2d i f f s e r v 区分业务体系结构 1 基本概念i e t f 在1 9 9 7 年酝酿并于1 9 9 8 年提出了i n t e r n e t 区分服务 ( d i f f s e r v ) 模式。d i f f s e r v 的初衷就是避免高复杂性，提供一种具有良好扩展 性的q o s 解决方案，其核心思想是“边缘分类，内部转发”。 在区分服务中，引入了d i f f s e r v 域( d o m a i n ) 的概念，它是指一系列协同 满足区分服务策略管理的、连续的i n t e r n e t 网络的一部分。一个区分服务域 可以包括不同的主机与路由器、管理区域、自治域，不同的信任域与不同的 网络技术( 比如信元或帧) 等等。区分服务域也叫d s ( d i f f e r e n t i a t e ds e r v i c e ) 域。 i p 包头部的区分服务标记域( d sf i e l d ) 是d s 区域边界节点和内部节点传 输流聚集信息的媒介，是内部核心路由器转发报文的依据，是连接报文与转 发服务( p h b ，p e r - h o p b e h a v i o r ) 的桥梁。d s 标记域定义为i p v 4 头部的 t o s ( t y p eo fs e