（计算机系统结构专业论文）开放式实时linux的研究与设计.pdf

摘要 伴随着计算机技术的不断发展，实时系统的应用范围不断地扩大，其系统规 模和复杂程度也不断地提高。特别是随着网络与多媒体应用的日益普及，将会有 大量的实时系统与网络多媒体应用有密切关系。具体地表现在多种类型的实时应 用包括硬实时应用，软实时应用以及非实时应用共存于一个系统的情况越来越 广泛。这样实时系统的结构也将变得日益复杂，从而使实时系统的软件内部结构 的研究成为一个重要的研究内容。 另一方面这些实时系统中的实时性要求又呈现出一些新的特点，譬如流媒体 中的实时性要求，它要求在特定的时间内处理完特定数量的流媒体信息，并且要 求端系统和网络系统都必须支持q o s ，而这种q o s 的要求一方面要求可以由用 户和系统容易地进行控制。另一方面又要求在系统超负载或不稳定时，系统的 q o s 的下降是也是可控制的。因而这些软实时系统就需要有一种能很好地满足其 q o s 要求的调度模型，使其对q o s 的要求能很好地溶入到调度中去。这样就要 求该调度模型应具有相当大的灵活性，这种灵活性体现在能够定量地描述软实时 系统满足时限与不满足时限的情况，因此调度算法在该系统损失帧时能很好地控 制损失帧情况，使系统能较好地满足其q o s 的要求。 基于上述的现实背景，本文对传统开放式实时系统的调度方法进行了深入研 究提出了基于动态窗口限制调度的开放式实时系统( d w c s o r t s ：d y n a m i c w 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 o p e nr e ai t i m es y s t e m ) 。开放式实时系统中 非相关的实时应用可单独进行开发和可调度性分析，并且当系统进行动态扩展 时，无须作全局的可调度性分析。动态窗口调度( d w c s 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 ) 机制是基于窗口限制模型的调度机制，譬如( m ，k ) 窗e l 限 制。它足一种非常灵活的调度机制，因此它能很好地满足系统对调度灵活性的要 求。 在此基础上，充分利用d 眦s 特点，提出了开放式实时系统的自适应q 0 s 调 度方法，并且结合具体的操作系统平台( l i n u x ) ，讨论了集成调度框架的设计与 实现方案。 d w c s 0 r t s 把传统的二层调度框架依据实时l n u x 的特点扩充到二三层结 构，系统如不需要支持硬实时任务，可以采用二层结构，当需要支持硬实时任务 时，采用三层结构解决开放式实时系统中的多类型任务调度问题。 d w c s - o r t s 可以支持不同类型的实时应用和非实时应用的同时运行。实时应 用程序可以在不影响其它任务情况下动态加载，并可选择不同的局部调度器，再 由系统支持它们的统一调度。另外。d w c s 调度对开放式实时系统下的服务质量控 制有很好的支持，并提供了相应的解决方法。 为检验d w c s o r t s 的有效性和实际应用效果，就需要与具体的操作系统相结 合，目前l i n u x 操作系统是一个非常合适的系统。因而我们的d w c s - 0 盯s 是结合 l i n u x 操作系统提出的，并且根据此设计框架完成了主要部分的系统实现工作。 最后本文设计了实验方案，进行了相应的实验。实验数据表明，该系统能够很好 地进行硬实时、软实时和非实时任务集成调度，支持端系统的q o s 保证，并且还 具有一定的q o s 的自适应能力。 关键词：开放式实时系统、动态窗口限制调度、调度、实时操作系统、自适应q o s 、 硬实时、软实时 中图分类号：t p 3 1 6 2 v a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n dt e c h n o l o g y , t h ea p p l i c a t i o nf i e l d o fr e a l t i m es y s t e m si s c o n t i n u o u s l ye x t e n d e d a n dt h e s c a l ea n dc o m p l e x i t yo f r e a l t i m es y s t e m sa r ea l s oi n c r e a s e dc o n t i n u o u s l y s p e c i a l l y , l o t so fr e a l - t i m es y s t e m s w i l lb er e l a t e dw i t hn e t w o r ka n dm u l t i m e d i aa p p l i c a t i o n si nt h en e t w o r ka n dm u l t i - m e d i ad e v e l o p m e n t s ot h ec a s e st h a td i f i e r e n tk i n d so fh a r dr e a l t i m e ，s o f tr e a l t i m e a n dn o n - r e a l - t i m ea p p l i c a t i o n sc o e x i s ti no n es y s t e mb e c o m em o r ea n dm o r ep o p u l a r t h i ss i t u a t i o nm a k e st h er e a l - t i m es y s t e mb e c o m em o r ec o m p l e xa n dc a u s e st h ei n n e r f r a m e w o r ko f r e a l - t i m es y s t e mg a i n sm o r ea n dm o r ea t t e n t i o nf r o mr e s e a r c h e r s o nt h eo t h e rh a n d t h e r ea l es o m en e wc h a r a c t e r i s t i c si nt h e s er e a l t i m es y s t e m s f o re x a m p l e ，t h es t r e a mm e d i au s u a l l yn e e d st h er e a l - t i m es y s t e mp r o c e s ss o m e s t r e a mf r a m e sj ns o m et i m e m o r e o v e r , t h ee n ds y s t e ma n dt h en e t w o r km u s ta l lp r o - v i d eq u s i no n eh a n d 。u s e r sa n dr e a l - t i m es y s t e m sc a nc o n t r o lt h eq o ss t a t u s ，i nt h e o t h e rh a n d t h ed e g r a d eq o si sa l s ou n d e rc o n t r 0 1w h e nt h er e a l t i m es y s t e mj su n s t a b l eo ro v e r l o a d s t h u st h e s es o f tr e a l t i m en e e das c h e d u l i n gm o d e l ，w h i c hc a nm e e t t h ed e m a n do fq o sa n dq o sc a nb ei n t e g r a t e dw i t hs c h e d u l i n g s ow en e e dan e w s c h e d u l i n gm o d e lw h i c hi ss of l e x i b l et h a tw e c a l lq u a n t i f i c a t i o n a i i yc o n t r o lt h es o f t r e a l - t i m es y s t e mm e e td e a d l i n e so rn o t i no t h e rw o r d s t h es o nr e a l - t i m es y s t e mc a n g u a r a n t e et h a tt h e s ed e a d l i n e sa r em i s s e di nr i g h tm a n n e rt oh o l dt h eg o o db e h a v i o ro f r e a l - t i m e s y s t e m s t h u st h er e a l - t i m es y s t e mc a nm e e tt h ed e m a n do f q o s b a s e dt h er e a l i s t i cb a c k g r o u n d ，t h et h e s i sd e e p l yr e s e a r c h e st h es c h e d u l i n gt h e o r yo f t h et r a - d i t i o n a l o p e n r e a l t i m e s y s t e m a n d p r o p o s e s an e w o p e n r e a l t i m e s y s t e m d w c s o r t s ( d y n n m i ow 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 - o p e nr e a l - t i m es y s t e m ) i na n o p e nr e a l l i m es y s t e m ，t h eu n d e p e n d e n tr e a l - t i m ea p p l i c a t i o n sc a nb ed e s i g n e di n d e p e n d e n t l ya n d t h es c h e d u l a b i l i t yc a nb et e s t e do n l i n e m o r e o v e r , t a s k sc a nb el o a d e dd y n a m i c a l l yi na l lo p e n r e a l - t i m es y s t e m d y n a m i cw i n d o w - c o n s t r a i n e ds e h e d u l i n g ( d w c s ) i sas c h e d u l i n gs t r a t e g y b a s e do f ft h ew i n d o w - c o n s t r a i n e dm o d e l i ti sav e r yf l e x i a b l es c h e d u l i n ga l g o r i t h ma n dc a nb e m e e tt h ed e m a n do f t h ea b o v e rr e a l - t i m es y s t e m s a f t e rt h i s ，t h et h e s i sp r o p o s e sa l la d a p t i v eq o ss c h e d u l i n gs t r a t e g y , w h i c hu s e st h ec h a r a c t e r i s t i c so fd w c s t h ed e s i g na n ds c h e m eo ft h ei n t e g r a t e ds c h e d u l i n gf r a m e w o r ka r ed i s c u s s e d w i t ha na c t u a lo p e r a t i n gs y s t e m ( l i n u x ) d w c s - o r t se x t e n d st h et r a d i t i o n a lt w o - l e v e ls c h e d u l i n gs c h e m et ot w o l e v e l t h r e e - l e v e l s c h e d u l i n gs c h e m eb a s e do nt h ec h a r a c t e r i s t i c so f r e a l - t i m el i n u x w h e nt h er e a l - t i m es y s t e mh a s n o th a r dr e a l - t i m et a s k s , i tc a nu s et h et w o - l e v e ls c h e d u l i n gs c h e m e o t h e r w i s e ，t h er e a l t i m es y s - t e mn e e du s et h et h r e e - l e v e ls c h e d u l i n gs c h e m e d w c s 0 r t se n a b l e st h ec o n c u r r e n tr u n n i n gi nt h ec a s et h a td i f i e r e n tk i n d so f r e a l t i m ea n dn o n r e a l - t i m et a s k sc o e x i s t t h er e a l - t i m et a s k sc a t ib el o a d e dd y n a m i c a l l y w i t h o u ta f f e c t i n go t h e rr e a l - t i m et a s k s md i f f e r e n tk i n d so f r e a l - t i m et a s k sc a r iu s ed i f i e r e n tl m e a ls c h e d u l e r sa n dt h el o c a ls c h e d u l e r sa r cu n i f o r m l ys c h e d u l e db yt h eo p e r a t i n gs y s t e m i na d d i t i o n ，d w c sh o l d so u tt h eq o so ft h eo p e nr e a l - t i m es y s t e mv e r yw e l la n dp r o v i d e ss o l v i n g m e t h o d s f o rv e r l f y i n gt h ev a l i d i t ya n da c t u a le f f i c i e n c yo fd w c s o p t s ，i tm u s tb ei m v i p l e m e n t e di na no p e r a t i n gs y s t e m a tp r e s e n t ，l i n u xi sav e r ys u i t a b l eo p e r a t i o ns y s - t e m s od w c s - o r t si sd e s i g n e dw i t l ll m n xa n dt h em a i np a r to fd w c s - 0 r t s i s i m p l e m e n t e da c c o r d i n gt ot h ed e s i g n e df r a m e w o r ko fd w c s - o r t s i nt h ee n d ，t h e t h e s i sd e s i g ne x p e r i m e n ts c h e m e s ，a n dt h e np e r f o r mm a n ye x p e r i m e n t su s i n gt h ei m p l e m e n t e ds y s t e mi nl i n u xe n v i r o n m e n t t h er e s u l t sf r o mt h ee x p e r i m e n t ss h o wt h a t t h ee x p e c t e dp e r f o r m a n c ei sa c h i e v e d a n dh a r dr e a l t i m e , s o f tr e a l t i m ea n d n o n r e a l t i m et a s k si nt h eo p e nr e a l - t i m es y s t e mc a l lb ei n t e g r a t e da n ds c h e d u l e d m o r e o v e r , t h er e s u l t sa l s oi n d i c a t ed w c s - o r t sc a r lg u a r a n t e et h eq o so fe n ds y s - t e m sa n dh a v es o m ea d a p t i v ea b i l i t yo f q o s k e y w o r d s ：o p e nr e a l t i m es y s t e m ，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 , s c h e d u l i n g ， r e a l - t i m eo p e r a t i n gs y s t e m ，a d a p t i v eq o s ，h a r dr e a l t i m e ，s o rr e a l - t i m e c h i n e s el i b r a r yc l a s s i f i c a t i o n ：t p 3 1 6 2 指导小组成员名单： 涂时亮教授 陈章龙教授 张友德副教授 y7 6 9 6 6 s 第一章绪论 第一章绪论 1 1 论文的研究背景与意义 实时系统是一种不但要考虑其计算结果的正确性并且要考虑其结果何时产 生的系统1 1 i 。实时系统在许多领域，譬如航天，工业控制网络通信以及视频会 议系统中都可以看到，己广泛应用在军事和民用领域。然而，随着计算机技术的 不断发展以及基于l i n u x 应用的日益提高，多种类型的实时应用，包括硬实时应 用，软实时应用以及非实时应用共存于一个系统的情况也越来越广泛。同时i p v 4 也渐渐被i p v 6 所取代，网络以及多媒体应用也将日益普及，从而有大量的实时系 统接入i n t e r n e t ，并与网络多媒体应用有密切关系，因而迎来了嵌入式i n t e r n e t 兴起与发展。开放式实时系统的概念即是针对这种实际情况提出来的1 2 】。 现在实时系统的发展又呈现出许多新的特点，比较突出的是诸如象视频点 播、视频会议、数字图书馆以及远程教学等这样的软实时系统越来越普及。这些 软实时系统往往要求在特定的时间内处理完特定数量的流媒体信息，并且要求端 系统和网络系统都必须支持q o s ，因而这些软实时系统就需要有一种能很好地满 足其q o s 要求的调度模型。该调度模型应具有相当大的灵活性，这种灵活性体 现在能够定量地描述软实时系统满足时限与不满足时限的情况这就要求调度算 法在该系统损失帧时能很好地控制损失帧情况，使系统能较好地满足其q o s 的 要求。因此人们提出了一种新的调度机制一动态窗1 3 调度( d w c s ，d y n a m i c w 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 调度是一种非常灵活的调度机制。这种灵活性体现在两个方面，一 方面可以把服务对象的违例情况起到一个均匀分布的能力，这样可以提高服务对 象q o s ，并且可能通过它直接把q o s 的要求体现在调度上。另一方面这种调度 机制的调度能力可高可低，在一定的情况下可以确保调度参数的要求，起到 e d f 调度能力，在有的情况下，起到b e s t - e f f o r t 调度能力，在不知道时限的时候， 可以相当于静态优先级调度，在大多数的情况下，具有公平调度能力。 基于上述的现实背景本文对传统开放式实时系统的调度方法进行了深入研 究，提出了一种新的开放式实时系统训s 0 r t $ ( 0 w c s o p e nr e a i t i b e s y s t e m ) ；在此基础上，充分利用0 w c s 特点提出了开放式实时系统的白适应q o s 调度方法；结合具体的操作系统平台( l i n u x ) ，讨论了集成调度框架的设计与实现 方案。0 f f c s o r t s 把传统的二层调度框架依据实时l i i l l i x 的特点扩充至 j - - 三层结 构，系统如不需要支持硬实时任务，可以采用二层结构，当需要支持硬实时任务 第一章绪论 时，采用三层结构解决开放式实时系统中的多类型任务调度问题。通过把具有 某些共同特征的不同方法集成到一个统一的调度框架中，d f f c s - o r t s 可以同时支 持多种类型的实时任务以及非实时任务的并发运行。对于在系统中同时运行的非 相关的实时或非实时应用程序，可单独进行开发和验证，并可选择不同的局部调 度器，再由系统支持它们的统一调度。另外d w c s 调度对开放式实时系统下的服 务质量控制有很好的支持，并提供了相应的解决方法。相对于现有的许多方法， 该调度框架可支持的任务类型更广泛，并且有良好的可扩展性。 本文的研究主要包括四个部分：第一部分解决了各种受限制模型下的d k s 调度方法，其中为了支持硬实时的调度，又解决了弱硬实时h i 的各种受限制模型 的调度方法以及对硬实时的支持；第二部分，在对原有的c b s 服务器【5 i 研究基础上 提出了受窗口限制的c b s 务器与受弱硬实时限制的c b s j e 务器以支持开放式实 时调度框架：第三部分，结合l lf l u x 操作系统提出眦s o r t s 的调度框架；第四 部分提出了在d w c 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 l l , 寸存在的问题。研究与开发基于l i n u x 的开放式实时系统将会很大程度 地提高l i n u x 的应用能力，适应现代计算机系统以及实时系统的发展。 1 2 本文的研究内容 本文的研究内容主要是开放式实时系统中的实时调度问题，研究如何在多种 类型的实时任务并存时，更好地支持网络与多媒体的实时应用，以适应实时系统 的发展。主要需要研究的内容包括； l 、研究如何在开放式实时系统中能更好地支持象网络与多媒应用情况下的 实时调度，同时又能支持多种类型的实时任务的并存调度。 随着计算机技术的不断发展，多种类型的实时应用，包括硬实时应用， 软实时应用以及非实时应用共存于一个系统的情况越来越广泛。特别是硬 件技术的快速发展，使得不但在p c 机上，甚至许多嵌入式系统中都可以很 第一章绪论 流畅的播放各种流媒体，因此在硬实时系统中集成多媒体应用的情况也越 来越普遍。比较突出的是诸如象视频点播、视频会议、数字图书馆以及远 程教学等这样的多媒体系统越来越普及。多媒体任务是软实时任务，软实 时的任务具有自身的特点，譬如不能很好地预测最差情况下的执行时间 ( w c e t ) ，任务呈现非周期特征等，因而软实时任务不能简单采用硬实时 的调度机制。人们针对这些情况提出一些方法，比较突出的是开放式实时 调度机制。 同时这些软实时系统往往要求在特定的时间内处理完特定数量的流媒 体信息，就需要有一种能很好地满足其q o s 要求的调度模型。该调度模型 应具有相当大的灵活性，这种灵活性体现在能够定量地描述软实时系统满 足时限与不满足时限的情况。这就要求调度算法在该系统损失帧时能很好 地控制损失帧情况，使系统能较好地满足其q o s 的要求。因此，新的开放 式实时调度系统需要建立在一个新调度模型基础上以支持网络与多媒体等 任务的实际要求。 2 、研究如何能更好地在支持q o s 开放式实时操作系统。随着诸如视频点播、 视频会议、数字图书馆、虚拟现实等多媒体应用越来越普及。作为端系统 操作系统也必须支持在一种程度或从某个方面支持具体的应用( 1 0 s 需求。 0 0 s 需求包括许多方面： a ) i ) o s 实时性要求。系统必须提供c p u 带宽( 可以是其他资源，但本文主 要考虑c p u 资源) 保证应用在指定的时间期限之前完成。 b 1c p u 的需求是动态变化的。该类多媒体应用的c p u 需求，譬如其w c e t ( 最 坏情况下的执行时间) 无法事先确定，而且在其运行期间不断变化，譬 如其到达时间呈现非周期性质，因此操作系统必须支持0 0 s 的动态游商 机制。 c ) 具有一定程度的自适应性。在c p u 带宽紧张时，多媒体应用可以降低服 务质量以维持服务。待资源充足时再回复原质量。 3 、 结合具体操作系统一l i n u x 进行研究与设计。研究与开发基于l i n u x 的开 放式实时系统将会很大程度地提高l i n u x 的应用能力，适应现代计算机系 统以及实时系统的发展。但是在l i n u x 上实现开放式实时系统必须要解决 两个问题： a 1l i n u x 本身不是实时操作系统，l i n u x 操作系统首先是作为通用操作系统 设计的，其响应性能设计目的是具有较高的平均响应性能，以高的吞吐 量和公平性为目标，因此采用了耗尽式的，机会均等的进程调度策略， 而实时性是保障的最坏情况下实时响应能力，因而其实时性能是有限的。 第一章绪论 同时它又是一种类u n i x 操作系统。继承了u n i x 的许多不适合实时性 的特点，因而必须对l i n u x 进行实时化改造。 b 1 改造后的实时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 。 1 3 本文的主要贡献与创新点 本文的主要贡献与创新点包括以下五个部分： 第一部分。解决了各种受限制模型下的d w c s 调度方法，其中为了支持硬实时 的调度，又解决了弱硬实时的各种受限制模型的调度方法以及对硬实时的支持。 d w c s 调度的原先是基于( m k ) 模型的 6 1 ，但是窗口限制的模型一共有四种。 这方面的丁作别人还没有做过，本文比较好地解决了这四种模型下的调度式，有 了这个基础，就可以解决它们的组合受限情况下的调度，从而系统可以在多种受 限制模型基础下进行调度，提高了系统的调度模型的灵活性，以及更好地支持系 统的o o s ，这是符合本文提出的研究背景与目的的。同时根据多媒体的任务的特 点，提了一种帧间相关的调度模型，该调度模型能更好支持多媒体等软实时任务 的情况。 针对弱硬实时的情况也存在同样的问题，本文也作了相同的工作。 第二部分，提出了受窗口限制的c b s j i t 务器与受弱硬实时限制的c b s 服务器以 支持开放式实时调度框架。 c b s 服务器是基于e d f 调度的，当开放式实时调度如果采用d w c s 调度时， 就必须就须使c b s 服务器成为受窗口限制的c b s 服务器。 当整个系统处于超负荷的情况下，c 皓服务器的带宽分配显然就会得不到满 足，因此就需要有一种自适应的分配机制，来重新对各c b s 服务器的带宽进行重 新的分配。可是在这种情况下，尤其对于多媒体任务来讲，就有许多不合适的地 方。主要表现在原先c b s 服务器的这种重新分配是一种压缩机制，需要重新确定o 、 t 参数，问题在于c b s i j 务器的q ，t 是有限制的。如果超出该限制的话就有可能引 起全部时限违例( 会造成很大部分的违例) ，这在c b s 服务器的t 参数相同时就很 可能出现，这是由于低层采用了e d f 调度所决定的。在这种情况下，多媒体的服 务质量就会急剧下降，而采用l y j c s 调度就不会出这种情况，因为它是根据前面的 时限违例情况来确定优先级的。 第一章绪论 针对弱硬实时调度也作了本文也作了相同的工作。 第三部分，提出了在d w c s 支持下的q o s 的自适应情况的研究。 由于d w c s 的受限参数直接决定了实时任务的运行质量，并且这些受限参数能 较灵活地控制实时任务的质量情况因此可以根据d g c s 的受限参数作为q 0 s 的指 标，这样就很容易地把服务质量的要求转化为对实时系统的调度参数。因此系统 能很方便地自适应系统q o s 的变化。 第四部分由于实时l l f l u x 并不一定适合开放式实时系统的理论提出的二层 的调度框架模型，因此根据实时化l i n u x 满足硬实时任务的要求，提出一种新的 三层次的调度框架理论。 由于l i n u x 进行实时化过程，对于支持硬实时任务需要采取一种双内核的机 制，因此系统在需要支持硬实时任务时就需要三层的调度框架结构。当然如果需 支持的情况，仍可以采用二层调度框架结构。 第五部分是面向多处理器情况，提出了一种新的启发式的调度方法。随着分 布式嵌入式系统的发展，多处理器情况下的实时调度也是实时系统调度的一个发 展方向。本文根据前人的启发式的调度方法的基础上，提出了一种新的启发式的 调度方法。 1 4 论文结构 第一章绪论 介绍课题的研究背景，剖析实时系统所面临的问题研究室本课题的研究 目标和研究内容，论述本课题研究的主要贡献与创新点。 第二章实时系统的基本理论与方法 介绍实时系统领域的基本理论与方法，譬如周期任务，非周期任务等的基 本调度方法，侧重了开放式实时系统的一个研究现状以及存在的问题。 同时也介绍了l i n u x 的实时化的技术方法。 第三章多种窗口受限模型下的实时调度方法 介绍了多种受限制模型下的d w c s 调度方法以及帧间相关模型下的调度 方法。 同时了介绍了多种受的弱硬实时调度方法以及帧间相关模型下的弱硬实时 调度方法。 第四章受窗口限制的c b s 服务器 介绍了受窗口限制的c b s 服务器的定义，并且对它的性能进行分析。分别 针对弱硬实时调度情况与与d w c s 调度情况进行介绍。 第一章绪论 第五章开放式实时l i n u x 的基本架构 利用前面提出的多种受限模型的d w c s 调度方法与受窗口限制的c b s 服 务器，构成一个新的基于d w c s 调度的二层开放式实时调度框架。并对该调度 框架的性能进行了分析。 利用前面提出的多种受限模型的弱硬实时调度方法与受弱硬实时调度的 c b s 服务器，构成一个新的基于弱硬实时调度的二层开放式实时调度框架。并 对该调度框架的性能进行了分析。 结合具体的操作系统l i n u x 。提出了二仨层的调度框架结构。 第六章开放式实时l i n u x 的q o s 支持 对d w c s - o r t s ，提出了支持q o s 的系统模型。针对已提出的二三层调度 框架，加了一个新的q o s 管理模块，以有把用户的q o s 的要求及时转化为调度 参数，从而达到o o s 的要求。 第七章多处理器情况下的考虑 考虑了系统在多处理器的情况下的调度问题。首先提出一个新的多处理器 的启发式调度算法。并且提供了仿真结果。接着采用d w c s 与启发搜索算法相 结合的方法，以增强其q o s 的控制。 第八章性能评价 根据系统的实现的情况，评价了d w c s o r t s 的性能。主要评价了系统在 软实时任务下的多媒体性能的结果，同时也在三层的调度框架下做了在硬实时 任务下的系统调度性能。 第九章总结与展望 总结已完成的工作，并指出未来的发展方向。 第二章实时调度的相关研究综述 第二章实时调度的相关研究综述 传统上实时系统必须具有确定性和可预测性的行为并要求计算过程能满足 实时任务的时限要求，因此实时系统要求具有可预期的响应能力、高度可调度性 以及稳定性。随着实时系统的发展实时系统又划分为硬实时系统( h a r d r e a i t i m e ) 、严实时系统( f ir n l r e a i t i m e ) 和软实时系统( s o f tp e a l t i m e ) j 。 硬实时系统是指其时限必须要满足的系统，如不满足将会引起灾难性的后果。譬 如发电厂中的汽轮机的进汽阀门的控制，一旦电网甩负荷，必须在规定时间内关 闭阀门，否则将会引起灾难性的后果。但是对一些特定的系统，如嵌入式实时系 统中的与数据采集有关的pid 控制，视频播放等，人们可以接受一些偶然性的 不满足时限的情况发生。对于这样的模型一般把它称为软实时系统或者严实时系 统，两者的区别是软实时系统在任务时限过后任务完成仍有意义而严实时系统 则无意义。 实时系统中关键是实时调度问题，自从l i u 和l a y l a n d 在1 9 7 3 年提出了著名 的r m 调度算法【8 】至今的三十多年来，人们对实时调度算法及其在应用中做了大 量的研究，提出许多实时调度算法，取得了丰硕的成果。 本章对国内外相关研究工作做一综述。 2 1 实时调度的基本概念 2 1 1 实时调度的基本术语 一般来讲，把实时系统的具体应用称为任务( t a s k ) ，譬如机床控制系统数据 采集、电厂进汽阀门的控制或者具体到一个视频的播放。而每个任务又有一些作 、l l ( i o b ) 或实例( i n s t a n c e ) 组成，譬如视频流的播放任务需要解压一个个视频帧数 据，这样每个帧数据的解压就是这个实时任务的一个作业或实例。 每个任务都需要一些资源来完成它的要求，譬如c p u ，内存，网络带宽等， 这些资源的都会影响到实时任务的执行情况，但是本文中主要还是考虑c p u 资 源上的实时任务的调度问题。 每个作业又具有一些实时参数，这些参数一般与时间有关。释放时间( r e l e a s e t i m e ) 是指作业到达时间，也就是c p u 可以调度该作业的时间。计算时间( c o m p u t e t i m e ) 是指作业需要在c p u 的总共执行时间。实时任务要求作业必须在某一个时 刻前完成，这个时刻就称为时限( d e a d l i n e ) 。又分为绝对时限与相对时限，绝对时 第二章实时调度的相关研究综述 限根据的的系统时间，相对时限是相对作业的释放时间。实时调度的主要目标就 是用最小的代价去满足系统上所有作业的时限。 有些任务的释放特性是呈周期性的，而有些任务的释放特性是非周期性的。 如果释放时间是呈周期性的，就可以称任务为周期性任务。这时任务就具有一个 周期参数l 这个参数说明了该任务每隔r 时间就会释放一个作业，但是这个作 业不定刚好在r 整数倍上的时间n t 上释放因此又有一个相对于n t 时间的 偏移( o f f s e t ) ，也称为抖动( j i t t e r ) 。 如果释放时间是呈现非周期性的，则可以称任务为非周期任务，其作业的释 放时间是往往不可预知的，非周期任务又可以分偶发任务( s p o r a d i ct a s k ) 和非周期 任务( a p e r i o d i ct a s k ) 。一般来说偶发性任务指的是释放时间是不规则的，但是释 放的速度是有一个上界的，也就是说它有一个最小的释放时间间隔，而非周期任 务则没有这个上界。但现在有时指偶发性任务的是硬实时任务，而非周期任务是 软实时任务或稳固实时任务。 实时调度问题不但要解决在单处理器的调度，还需要解决在多处理上的调 度，在多处理器的调度问题一般说n p - 完全问题，所以一般都是采用启发式的调 度算法。 2 1 2 实时调度的基本模型 实时调度的模型，一般是由一个任务集构成。最基本的就是周期性模型。一 个周期任务集是一个由个任务r ，( 1 ，构成的集合仃，其中r ，是一个由 四元组( 乃，口，所确定的任务( 乃) 。其中； 乃：任务r ，的周期。 c f ：任务r ，的计算时间。 d 。：任务r ，的时限。 口：任务r ，释放时间的抖动。 这里面对于每一个任务来讲其中几个参数的值对于每个作业并不是固定 的，五取的是任务中各作业中释放时间间隔的最小值，而。取的是任务中各作 业的最大执行时间，也称为最坏情况的执行时间( w c e t ，w o r s tc a s e e x e c u t e t i m e ) 。 把所有任务的- 的最小公倍数称为这个任务集的超周期( h y p e r p e r i o d ) t g ! ， 用来表示。 h = l c m t i ir ，2 - 0( 2 1 ) 这个模型是一个基础模型，在不同的情况下有时可能会增加参数，以用于 实时调度优先级的确定有时有些参数是不可预知的，或者参数的变化很大，譬 第二章实时调度的相关研究综述 如流媒体，其计算时间不是不可知的，其中有较大的变化如果按照w c e t 来 调度就会过多地浪费c p u 带宽。这些扩展模型可参考文献 1 0 1 1 i 】 另外。这个任务集中的各个任务是相互独立的，也就是说一个任务运行不需 要等待另外个任务的运行结果。 2 1 3 实时调度的基本理论 实时调度的基本问题就是要找到个任务的执行顺序，使上述的任务集在 运行时，都能满足每一个作业的时限。其次还需要最小的资源消耗来完成这个调 度。 实时调度的主要任务可以分为两个部分，其一是判断某一任务集是否是可调 度的，其二是如果是可调度的，找出一个调度算法，并且最好是最优的。 前一个任务也称为调度能力分析主要是证明在给定某一调度机制的情况 下，对某一可调度系统的性质的进行分析。判断一个任务是否是可调度的很可能 是一个n p 完全问题，特别是任务存在抖动的情况【9 j 【”胂j 。 第二个任务就是要找到一个可行的调度算法，调度算法根据任务执行顺序的 确定时间又可以分为两种，一种称为是静态的调度，种称为动态的调度。所谓 静态的调度算法是指任务的调度，也就是在什么时候轮到哪一个任务执行是事先 确定的，因此静态调度也称为离线调度算法【“1 1 ”】。所谓动态的调度算法是指任 务的调度，也就是轮到哪一个任务执行是动态确定，是在运行时根据一些条件来 确定的，所以动态调度也称为在线调度算法。因而静态调度与动态的调度是从任 务的切换时间上来区分的。 动态调度里面主要是基于优先级调度，这个在后面讲到。在动态调度的情况 下，有时低优先级的任务在运行时，会有高优先级任务到达。这时系统两种选择， 一是马上停止低优先级任务，让高优先级任务得到运行，但是这个是有条件的 也应是低优先级任务在运行时必须是可抢占的，也就是说低优先级任务没有在非 抢占区运行。二是让低优先级任务先执行完，然后再选择高优先级任务执行。前 一种方式称为是抢占式调度方式，后一种方式称为是非抢占式调度方式。 参数u 表示系统在特定调度算法下，处理器的忙碌程度，即表示处理器的利 用率，定义为? = 圭孚 ( 2 2 ) ，o 由于实时系统时限的重要性，譬如硬实时系统的时限违例往往意味可能引起 重大的灾难，因此仅仅用测试来证明实时调度的正确性是不够的，这时由于系统 的测试只能证明系统有错误，而不能证明系统没有错误。因而采用实时调度理论 9 第二章实时讽度的相关研究综述 来证明实时调度算法的正确性是必要的。 2 2 实时调度策略 在实时调度领域，主要的实时调度策略可以分为三大类l l i ： 1 1 时间驱动； 2 ) 优先级驱动； 3 1 共享驱动； 这一部分就主要介绍这三种调度策略。 2 2 1 时间驱动调度 时间驱动属于静态调度，在许多传统的实时系统中都得到广泛的应用。所谓 时间驱动调度具体说是指在系统开始执行之前，选择一些特定的时刻在这些时 刻决定哪一个作业在何时执行。通常在操作系统中需要设置定时器来实现时间驱 动调度。 一般情况下，时间驱动要求硬实时任务的有