（计算机科学与技术专业论文）弱硬实时调度关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 随着计算技术的发展，实时应用种类日益增多，实时系统应用范围不断扩大， 系统复杂性不断提高，特别是随着网络技术的发展而推动的网络实时应用，例如 网络多媒体、远程教学、远程手术等，这些应用对任务的完成具有时间的约束， 但是这类时间约束既不像硬实时那样严格，又不像弱实时那样定义不明确，而是 基于一定的服务质量需求。 为了更好地应对实时系统任务类型多种多样、约束复杂、具有瞬时超载等新 特点，弱硬实时理论应运而生。弱硬实时理论作为一种规范，完善充实了实时系 统理论，统一描述了原有各类实时系统，硬实时和弱实时实际上都是弱硬实时系 统的一种特例。 弱硬实时能够满足实时系统新特点的需要。由于其可以把硬实时、弱实时统 一起来，因此更便于处理多种类型任务的综合调度；弱硬实时采用两个参数描述 任务的服务质量需求，从而更明确地定义和区分了任务的服务质量；在系统过载 时，可以通过弱硬实时调度算法提供服务质量的缓慢退化。 为此，本文进一步丰富了弱硬实时的约束规范，并对弱硬实时调度算法进行 了深入的研究，在以下几个方面做出了富有成效的工作并具有创新性： 1 ) 本文丰富了弱硬实时约束规范，提出p ，助约束，并证明了其与( 而，p ) 约束 的等价性，进而可以导出与其它弱硬实时约束的关系。( 瓦p ) 约束和，助约束的侧 重点不同，前者突出连续丢失截止期的次数，后者突出用户考虑的最小窗口。进 一步，定义了p ，助丢失率，并通过p ，d 丢失率给出满足，动约束的必要条件，为分 类选择算法提供了理论基础。 2 ) 本文提出了一类基于裁剪的调度算法，基于( 丽，p ) 约束，提出了一类用于 解决变长窗口约束违背判别的基于裁剪的弱硬实时调度( c u t d o w nb a s e d s c h e d u l i n g ，c d b s ) 算法。通过对任务的执行序列进行有效的裁剪，并引入转折点 的概念，使得对( 丽，p ) 约束满足性判别的复杂度大幅度降低，而且与序列长度无关。 文中给出了裁剪算法正确性的证明，并通过实验验证了其有效性。本文采用了一 种简洁的优先级分配策略，即基于距离m 次连续丢失截止期的距离分配任务的优 先级，并结合任务可能出现的四种状态进行调度。最后，将算法与e d f 、d w c s 、 d b p 等算法进行比较，c d b s 算法在动态失效率和最小成功率方面都提供了适当 的折中，与其它算法相比具有相当的性能。 3 ) 本文提出了种任意窗口约束调度算法，从变长窗口的丢失率保证问题出 发，研究在过载情况下提供公平而有差别的服务。设计了基于p ，d 约束的任意窗口 第i 页 国防科学技术大学研究生院博士学位论文 约束调度( a n yw i n d o wc o n s t r a i n ts c h e d u l i n g ，a w c s ) 算法，分析了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 i n g ，k w c s ) 算法。实验表明 k w c s 具有与a w c s 相近的性能，且复杂度大幅降低，因此k w c s 更适合实际系 统应用。通过分析a w c s ( k w c s ) 提供的公平性和差别性，进一步定义出成功率偏 离度，并给出调度算法时延上界的通用表示方法。最后，将算法与其它弱硬实时 调度算法进行比较，结果表明a w c s ( k w c s ) 在重度过载情况下优于其它算法，能 够使任务的q o s 缓慢地退化，提供了一种既公平又有差别的服务。 4 ) 本文对置窗口约束调度算法的实践应用进行了丰富的扩展。提出k w c s 与d b p 的混合算法，将系统过载情况分为轻度过载、临界过载和重度过载，动态 监控系统的状态，并根据不同的过载情况采取不同的调度策略，进而解决了k w c s 在轻度过载情况下性能欠佳的问题；针对k w c s 算法需要保存历史状态而不利于 扩展的问题，提出分类选择算法，根据( p ，助丢失率，对p ，勋流进行分类，从而提高 了算法的可扩展性；提出多跳k 窗口约束调度( m u l t i h o pk w c s ，m k w c s ) 算法， 解决了k w c s 在端到端系统中的应用。 5 ) 本文对弱硬实时调度算法在新应用领域的探索进行了尝试。提出多处理器 弱硬实时调度算法，解决多处理器中多类任务的综合调度，并考虑了资源的共享 独占访问方式；提出基于简单反馈的混合静态动态节能弱硬实时调度算法，针对 任务的实际执行时间通常远小于最坏情况执行时间的实际情况，对混合静态动态 节能弱硬实时调度算法加以改进，引入任务划分，通过反馈机制估计任务的实际 执行时间，以获取更低的执行速度，达到更好的节能效果。实验表明，当平均情 况执行时间低于最坏情况执行时间较多时，新算法优于原始算法，最多可节能6 0 到7 0 ，最少可节能约1 0 。算法的不足之处在于当平均情况执行时间接近最坏 情况执行时间时，新算法比原算法更耗能。 最后，对全文进行了概括性总结，并指出了有待进一步研究和完善的问题。 主题词：实时系统，弱硬实时，调度算法，动态失效。服务质量，定长窗口约束， 变长窗口约束，c d b s ，a w c s ( k w c s ) ，反馈机制 第i i 页 国防科学技术大学研究生院博士学位论文 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 i n gt e c h n o l o g y ，t h en u m b e ro ft h et y p e so f r e a l - t i m ea p p l i c a t i o n si si n c r e a s e dd a yb yd a y ，t h ea p p l i c a t i o na r e ai sw i d e ra n dw i d e r ， a n dt h es y s t e mi sm o r ea n dm o r ec o m p l i c a t e d e s p e s c i a l l y ，w i t ht h ed e v e l o p m e n to f n e t w o r kt e c h n o l o g y ，t h en e t w o r k i n gr e a l t i m e a p p l i c a t i o n s a r ep u tf o r w a r d ，e g ， n e t w o r k i n gm u l t i m e d i a ，d i s t a n c ee d u c a t i o n ，t e l e s u r g e r y ，e t c ，w h i c ha l s oh a v et h et i m e c o n s t r a i n to nt h e t a s kc o m p l e t i o n b u t ，t h et i m ec o n s t r a i n ti sn e i t h e ra sh a r da sh a r d r e a l t i m e ，n o ra sf u z z ya ss o f tr e a l t i m e i ti sb a s e do ns o m ed e f i n i t i v eq o sr e q u i r e m e n t t od e a lw i t ht h en e wc h a r a c t e r so ft h er e a l - t i m es y s t e m ，s u c ha sk i n d sa n dk i n d so f t a s k s ，c o m p l i c a t e dc o n s t r a i n t sa n dt r a n s i e n to v e r l o a d ，t h et h e o r y o fw e a k l y - h a r d r e a l t i m ei sb r o u g h tf o r w a r d t h et h e o r yi st a k e na sas p e c i f i c a t i o n ，w h i c he n r i c h e st h e r e a l t i m es y s t e mt h e o r ya n du n i f o r m sa l le x i s t e dr e a l - t i e ms y s t e m s e i t h e rh a r dr e a l t i m e o rs o f tr e a l t i m ei sas p e c i a lc a s eo fw e a k l y - h a r dr e a l t i m es y s t e m w e a k l y h a r dr e a l t i m es y s t e mc a l ls a t i s f yt h ee m e r g i n gc h a r a c t e r s s i n c ei t c a n u n i f o r mh a r dr e a l - t i m ea n ds o f tr e a l - t i m ei n t oo n ed e s c r i p t i o n ，i ti sac o n v e n i e n tt o o lf o r h a n d l i n gt h ei n t e g r a t e ds c h e d u l ew i t hv a r i o u st a s k s t h eq o sr e q u i r e m e n ti sd e s c r i b e d b y t w op a r a m e t e r si nw e a k l y h a r dr e a l - t i m e c o n s t r a i n t ，w h i c hc a nd e f i n e a n d d i f f e r e n t i a t et h et a s k s q o sm o r ec l e a r l y w h e nt h es y s t e mi si no v e r l o a dc o n d i t i o n s ， w e a k l y - h a r 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 sc a np r o v i d eg r a c e f u ld e g r a d a t i o no fq o s t h e r e f o r e ，i nt h i st h e s i s ，t h ew e a k l y h a r dr e a l - t i m et h e o r yi se n r i c h e d ，a n dt h e a l g o r i t h m sa r ed e e p l yr e s e a r c h e d t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r es u m m a r i z e d a sf o l l o w s 1 ) t h i st h e s i se n r i c h e st h ew e a k l y - h 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 t h ep ，助 c o n s t r a i n ti sp r o p o s e d ，o fw h i c ht h ee q u i v a l a n c ew i t ht h e ( 瓦p ) c o n s t r a i n ti sp r o v e d a n dt h er e l a t i o n sw i t ho t h e rc o n s t r a i n t sc a i lb ed e r i v e d t h ee m p h a s e so ft h e ( 丽，p ) c o n s t r a i n ta n dt h ep ，助o n ea r ed i f f e r e n t ，t h ef o r m e re m p h a s i z e st h en u m b e ro f c o n t i n u o u sm i s s i n gd e a d l i n e s ，a n dt h el a t t e re m p h s i z e st h em i n i m u mw i n d o ws i z e f u r t h e r m o r e ，t h e0 ，助l o s sr a t e i s d e f i n e d ，b yw h i c ht h en e c e s s a r yc o n d i t i o no f s a t i s f y i n gt h ep ，助c o n s t r a i n ti sp r e s e n t e d t h ep ，助l o s sr a t ea l s op r o v i d e s t h e t h e o r e t i c a lb a s i sf o rt h ec l a s ss e l e c t i o na l g o r i t h m 2 ) b a s e do nt h e ( 丽，p ) c o n s t r a i n t ，t h i st h e s i sp r o p o s e sak i n do fa l g o r i t h m sw h i c h i sn a m e da s c d b s ( c u t d o w nb a s e ds c h e d u l i n g ) a n d i su s e dt os o l v et h e d i s c r i m i n a t i o no fw i n d o wc o n s t r a i n tw i t hv 撕a b l es i z e s i nc d b s ，t h ee x e c u t i o ns t a t e s e q u e n c ei sc u td o w ne f f e c t i v e l ya n dt h en o t i o no ft u m p o i n ti si n t r o d u c e d ，w h i c hm a k e s t h ed i s c r i m i n a t i o no ft h e s a t i s f i a b i l i t yo f ( 丽，p ) c o n s t r a i n tm u c he a s i e ra n dt h e c o m p l e x i t yo f j u d g m e n ti sn o tr e l e v a n tt ot h el e n g t ho fs e q u e n c e t h ec o r r e c t n e s so ft h e 第i i i 页 国防科学技术大学研究生院博士学位论文 a l g o r i t h mi sp r o v e da n dt h ee f f e c t i v e n e s si sv e r i f i e di ne x p e r i m e n t s t h i st h e s i sp r o r o s e s ac o n c i s ew a yt oa s s i g nt h ep r i o r i t i e s ，w h i c hi sb a s e do nt h ed i s t a n c ef r o mmt i m e s c o n t i n u o u sm i s s e s t h et a s k sa r ea l s os c h e d u l e dw i t hc o n s i d e r a t i o no ff o u rp o s s i b l e s t a t e s f i n a l l y ，w ec o m p a r ec d b sw i t ho t h e rc l a s s i c a la l g o r i t h m s ，s u c ha se d f ，d b p ， d w c s a n dt h er e s u l t ss h o wi t sc o m p e t e n c ea n di t sc o m p r o m i s ei nd y n a m i cf a i l u r e r a t i oa n dm i n i m u ms u c c e s sr a t i o 3 ) b e g i n n i n gw i t ht h el o s sr a t eg r u a r n t e ei nv a r i a b l ew i n d o w ，t h i st h e s i sp r o p o s e s a na l g o r i t h mn a m e da sa n yw i n d o wc o n s t r a i n ts c h e d u l i n g ( a w c s ) ，w h i c hc a n p r o v i d ef a i ra n dd i s c r i m i n a t o r ys e r v i c ei no v e r l o a dc o n d i t i o n s a w c si sb a s e do nt h e p ，动c o n s t r a i n t ，i t sc o m p l e x i t yi sa n a l y z e d u n f o r t u n a t e l y ，t h ec o m p u t a t i o no fa w c s i n h e a v i l yo v e r l o a dc o n d i t i o n si st o oc o m p l i c a t e dt os c h e d u l e as i m p l ev e r s i o no fa w c s i sp u tf o r w a r d ，w h i c hi sc a l l e dk - w i n d o wc o n s t r a i n ts c h e d u l i n g ( k w c s ) e x t e n s i v e e x p e r i m e n t ss h o wt h a tk w c sc a ns u p e r s e d ea w c s ，a n dn o to n l ya c h i e v ec o m p a r a t i v e p e r f o r m a n c eb u ta l s og e tl o w e rc o m p l e x i t y i nt h i st h e s i s ，t h ep r o p e r t i e so ft w o a l g o r i t h m sa r ea d d r e s s e d ，a n dt h ed i f f e r e n c eo fs u c c e s sr a t i oi sd e f i n e d ，b yw h i c ha g e n e r a lr e p r e s e n t a t i o no fd e l a yb o u n do ft h es c h e d u l i n ga l g o r i t h m si sb r o u g h tf o r w a r d r e s u l t ss h o wt h a tb o t ha w c sa n dk w c sc a np r o v i d eb e t t e rp e r f o r m a n c et h a no t h e r w e a k l y h a r 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 si nh e a v i l yo v e r l o a dc i r c u m s t a n c e s ，t h a ti s t h eq o si sd e g r a d e dg r a c e f u l l ya n dt h es e r v i c ei sb o t hf a i ra n dd i s c r i m i n a t o r y 4 、it h i st h e s i se x t e n d sk - w i n d o wc o n s t a i n ts c h e d u l i n ga l g o r i t h mf o rp r a c t i c e t h e m i x e da l g o r i t h mo fk w c sa n dd b pi sp u tf o r w a r d t h es t a t e so fs y s t e mo v e r l o a da r e c l a s s i f i e di n t ol i g h to v e r l o a d ，c r i t i c a io v e r l o a da n dh e a v i l yo v e r l o a d t h es y s t e m o v e r l o a ds t a t ei sm o n i t o r e dd y n a m i c a l l y a c c o r d i n gt od i f f e r e n to v e r l o a ds t a t e t h e d i f f e r e n tp o l i c yi sa d o p t e d t h em i x e da l g o r i t h mo v e r c o m e st h ep o o rp e r f o r m a n c eo f k w c si nl i g h to v e r l o a dc o n d h i o n s 。k w c sn e e d st om a i n t a i nt h eh i s t o r yo fe x e c u t i o n a n ds ot h eo v e r h e a di st o oh e a v yt oe m i tw h e nt h es y s t e mb e c o m e sl a r g e ra n dl a r g e r f o rt h i sr e a s o n ，t h ec l a s ss e l e c t i o na l g o r i t h mi sb r o u g h tf o r w a r d ，w h i c hc l a s s i f i e st h e p ，助s t r e a m sa c c r o d i n gt ot h e ，动l o s sr a t e r e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft h e a l g o r i t h m s ，a n dt h ec l a s s s e l e c t i o na l g o r i t h m sc a l lb o t hd e c r e a s et h eo v e r h e a d e f f e c t i v e l ya n dg u a r a n t e et h eq o s f u r t h e r m o r e ，t h em u l t i h o pk - w i n d o wc o n s t r a i n t s c h e d u l i n g ( m k w c s ) a l g o r i t h mi sp r e s e n t e d ，w h i c hi sa p p l i e di n t ot h ee n d t o e n d s y s t e m 5 ) t h i st 1 1 e s i st r i e st ou s ew e a k l y h a r 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 si n t on e w a p p l i c a t i o na r e a s t h ew e a k l y h a r dr e a l t i m es c h e d u l i n ga l g o r i t h mf o rm u l t i p r o c e s s o ri s b r o u g h tf o r w a r d w h i c hj s u s e dt os c h e d u l ev a r i o u st a s k si nt h em u l t i p r o c e s s o r i n t e g r a t e d l y t h ea l g o r i t h m a l s oc o n s i d e r st h er e s o u r c ec o n s t r a i n t s am i x e d s t a t i c d y n a m i ce n e r g y - a w a r ew e a k l y - h a r dr e a l t i m es c h e d u l i n ga l g o r i t h mw i t hs i m p l e f e e d b a c km e c h a n i s mi sp u tf o r w a r d s i n c et h ea c t u a le x e c u t i o nt i m ei sf a rl e s st h a nt h e w o r s tc a s ee x e c u t i o nt i m ef w c e t ) ，t h em i x e ds t a t i c d y n a m i ee n e r g y a w a r e 第i v 页 国防科学技术大学研究生院博士学位论文 w e a k l y h a r dr e a l t i m es c h e d u l i n ga l g o r i t h mi sm o d i f i e d t h et a s kp a r t i t i o ni si n t r o d u c e d ， a n dt h es i m p l ef e e d b a c km e c h a n i s mi su s e dt oe s t i m a t et h ea c t u a le x e c u t i o nt i m e t h e w h o l es p e e di sd e c r e a s e da n dt h ee x e c u t i o nt i m ei sp r o l o n g e d ，a n ds ot h en e wa l g o r i t h m i sm o r ee n e r g ye f f i c i e n t t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m o u t p e r f o r m st h eo r i g i n a lo n ew h e nt h ea v e r a g ec a s ee x e c u t i o nt i m e ( a c e t ) i sm u c h l e s st h a nt h ew c e t w h i c hc a ni m p r o v ee n e r g ys a v i n g sa b o u t6 0 t o7 0 a tm o s ta n d a b o u t10 a tl e a s t u n f o r t u n a t e l y w h e nt h ea c e ti sc l o s et ot h ew c e t 。t h ep r o p o s e d a l g o r i t h mc o n s u m e sm o r ee n e r g yt h a nt h eo r i g i n a lo n e 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 r 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 l e p o i n t e do u t 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 y h a r dr e a l t i m e ，s c h e d u l i n g a l g o r i t h m ，d y n a m i cf a i l u r e ，q u a l i t yo fs e r v i c e ，w i n d o wc o n s t r a i n tw i t hf i x e d s i z e ，w i n d o wc o n s t r a i n tw i t hv a r i a b l es i z e s ，c d b s ，a w c s ( k w c s ) ，f e e d b a c k m e c h a n i s m 第v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 基于定长窗口的弱硬实时约束1 7 表3 1 同一状态下任务按照自顶向下的顺序调度3 l 表4 1 任务优先级顺序4 1 表4 2 调度算法参数配置表4 9 第v 页 国防科学技术大学研究生院博士学位论文 图 目录 图1 1 论文的组织结构1 3 图2 1滑动窗口和固定窗口的区别1 7 图3 1部分违背约束的子序列进入测试序列的情况2 9 图3 2m = 2 时的状态转换图3 0 图3 3c d b s 算法中使用的数据结构3 1 图3 4 转折点平均个数变化图3 4 图3 5 转折点最大个数变化图3 4 图3 6 转折点平均个数变化图3 5 图3 7 转折点最大个数变化图3 5 图3 8 ( m ，幼动态失效率变化图3 6 图3 9 最小成功率变化图3 6 图4 1a w c s 算法中使用的数据结构4 2 图4 2 最危险转折点最大编号变化图4 6 图4 3 动态失效率变化图4 7 图4 4 最小成功率变化图4 7 图4 5 区间最小成功率变化图一4 8 图4 6c p u 利用率在 1 4 ，1 5 】区间内的最大时延变化图4 8 图4 7c p u 利用率在 1 7 ，1 8 】区间内的最大时延变化图4 9 图4 8c p u 利用率在 2 0 ，2 1 】区间内的最大时延变化图4 9 图4 9 异构环境下动态失效率变化图5 0 图4 1 0 异构环境下最小成功率变化图5 1 图4 11 等效c p u 利用率在 0 9 8 ，1 0 5 】区间内区间最小成功率变化图5 1 图4 1 2 等效c p u 利用率在【0 9 8 ，1 0 5 区间内的最大时延变化图一5 2 图4 1 3 等效c p u 利用率在 1 1 9 ，1 2 6 区间内的区间最小成功率变化图5 2 图4 1 4 等效c p u 利用率在【1 1 9 ，1 2 6 区间内的最大时延变化图5 2 图4 1 5 等效c p u 利用率在【1 4 0 ，1 4 7 区间内的区间最小成功率变化图5 3 图4 1 6 等效c p u 利用率在 1 4 0 ，1 4 7 1 区间内的最大时延变化图5 3 图5 1( m ，幼动态失效率变化图6 0 图5 2 最小成功率变化图6 0 图5 3区间最小成功率变化图6 0 图5 4 ( m ，动动态失效率变化图6 1 图5 5 最小成功率变化图6 1 第v i i 页 国防科学技术大学研究生院博士学位论文 图5 6 平均等效负载低于1 情况下的区间最小成功率变化图6 2 图5 7 平均等效负载略大于1 情况下的区间最小成功率变化图6 2 图5 8平均等效负载远大于1 情况下的区间最小成功率变化图6 2 图5 9c s a k w c s 模型6 4 图5 1 0 等效利用率对，d 动态失效率的影响6 6 图5 1 1 等效利用率对最小成功率的影响6 7 图5 1 2 周期对( 垅，d 动态失效率的影响一6 7 图5 13 周期对最小成功率的影响6 8 图5 1 4 系统中有5 0 个流，类数为1 0 时的流数比较图6 8 图5 1 5 系统中有5 0 个流，类数为1 0 时的成功率比较图6 9 图5 1 6 等效利用率对伽，d 动态失效率的影响。6 9 图5 1 7 等效利用率对最小成功率的影响。7 0 图5 18 周期对动态失效率的影响7 0 图5 19 周期对最小成功率的影响7 0 图5 2 0 网络拓扑7 6 图5 2 l 考虑所有流时动态失效率变化图7 7 图5 2 2 考虑所有流时丢失报文率变化图7 7 图5 2 3 仅考虑主数据流时动态失效率变化图7 7 图5 2 4 仅考虑主数据流时丢失报文率变化图7 8 图6 1实例任务集的可行调度8 0 图6 2 多媒体服务器模式的冲突8 0 图6 3多处理器调度算法伪代码8 2 图6 4av g 跏，对动态失效率的影响8 4 图6 5av gu t i l 对成功率的影响8 5 图6 6t a s k 尸对动态失效率的影响8 5 图6 7 t a s kp 对成功率的影响8 6 图6 8u s ep 对动态失效率的影响8 6 图6 9u s e 尸对成功率的影响8 7 图6 1 0i n t e l 芯片的功耗密度8 8 图6 1 l 强制工作划分示意图9 2 图6 1 2 可选工作划分示意图9 2 图6 1 3m k ，。反馈框架9 3 图6 14m k ，。一s f 算法伪代码描述。9 5 图6 1 5a c e t w c e t 对性能的影响9 8 第v i i i 页 国防科学技术大学研究生院博士学位论文 图6 1 6 ( m ，助利用率对性能的影响9 9 第1 x 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同- r 作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：塾亟塞吐翅廛羞筵捷盔盟窥 学位论交作者签名：叁g 垒 日期：l 刀罗年夕月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 幺丑垒 作者指导教师签名：垒二全垄 日期：彻方年9 月，7 日 魄耐年j 7 月7 日 国防科学技术大学研究生院博士学位论文 第一章绪论 19 9 8 年，g u i l l e mb e r n a t 发表了名为( ( s p e c i f i c a t i o na n da n a l y s i so fw e a k l yh a r d r e a l t i m es y s t e m s ) ) 的博士论文【i j ，建立了弱硬实时系统理论。在硬实时和弱实时 之间利用明确的约束引入了一种新的实时范畴。弱硬实时的提出丰富了实时理论， 更加适合实际应用。弱硬实时既克服了硬实时系统的过度严格，又避免了弱实时 和准实时的不确定性，同时又可以将硬实时和弱实时统一描述。弱硬实时通过对 截止期丢失进行适当的约束规范，使其更具应用价值。因其不必满足所有截止期 而使得所需的系统资源数量较小，这就允许使用更简洁和更高性价比的系统，能 够在充分利用有限的可用资源的同时，保证较好的服务等级。本文主要研究了弱 硬实时的约束规范、相关调度算法及其调度算法的应用。 1 1 课题背景 实时系统是指那些正确性不仅依赖于计算的逻辑结果，而且依赖于产生结果 的时间的系统【2 ，3 】。实时系统在航空、航天、电子、核工业、军事等很多领域都得 到了广泛的应用。这些领域，尽管各不相同，但是具有公共的底层特征，即要求 系统在己知的预定义时间间隔内产生结果。 随着计算技术的发展，实时应用种类也日益增多。除了在关键领域中需要硬 实时应用之外，弱实时应用得到了极大的发展，特别是随着网络技术的发展而推 动的网络实时应用，例如网络多媒体、远程通讯、远程手术等，这类应用对任务 的完成同样具有时间的约束，但是既不像硬实时那样严格，又不像弱实时那样定 义不明确，而是基于一定的服务质量的。 1 1 1 实时系统概述 实时系统是以实时计算机系统为核心的一个完整的应用系统。实时计算机系 统负责完成应用提出的各种需求，与通用计算机系统不同的是，它既要满足应用 提出的功能需求，又要满足应用提出的时间需求。也就是说，实时计算机系统的 正确性不但取决于产生结果的正确性，还取决于结果的产生时间。如果结果的产 生时间不符合应用的时间需求，则该结果可能是毫无用处的，甚至还会产生灾难 性的影响。 根据丢失截止期的重要性可将实时系统分为以下三类【3 】： ( 1 ) 硬实时系统( h a r dr e a l - t i m es y s t e m ) ：在航空、航天、军事、核工业等一 些关键性领域中，应用的时间需求应完全得到满足，否则就可能会造成重 第1 页 国防科学技术大学研究生院博士学位论文 大安全事故，导致重大生命财产损失。因此，在这类系统的设计和实现过 程中，应采用各种分析、模拟以及形式化验证方法对系统进行严格的检验， 以保证在任何情况下应用的时间需求和