（计算机软件与理论专业论文）分布式实时事务预分析处理与预测.pdf

华中科技大学博士学位论文 = = ；= = # = = ；= = 一= 在分布式主动实时数据库系统中，由于全局事务的予事务可能执行在其它不问的 结点，事务可能动态地触发新的事务，子事务，这使得分布式主动实时事务处理的可预 测性支持更加复杂化与困难。为了支持分布式主动实时事务的预分析处理及预测，系 统中每个结点由共享内存双处理器构成，其中一个处理器是事务及数据处理器，另一 个处理器是分橱恢复处理器，它专门负责事务和数据存取的动态分析。基于树的分布 式主动实时事务的语义缨搀模型靼事务“关节点”的概念，能够有机地把事务的静态 孩分辑、动态预分析及动态预测结合起来，并有效地支持分布式主动实时事务的动态 舔测。关节点可能悬事务理廖的分支点、分东式予事务的创建点、主动规则的触发点， 也是事务静态不确定性在动态执行串戆确谈点，是逃萼亍事务动态分橱与处理调整及动 态可诱发性谈测翡执行蕊。y 基于事务榻关黼的优先缀动态璇整策赂，基予事务翊关性分据豹冲突敏感的攀务 子事务初始优壳级分配策珞和系统动态受蓠模型够充分反应系绞中事务熬动态行为 和相互影响，由此建立的事务接缩控制策路帮基于瑟分析豹悲鼹串谤动态释放豹分毒 式实时静态两段锁协议可以改善系统的健能。 内存数据库能提高实时事务处瑗的可预颖俊。在实对肉存数据霹中，滚复娃理， 特别是内存数据库踅装是影响实时事务处理往能的关键黼素之一。灰关联阉包韵概念 发展了灰色关联分析的理论，而基于此的实时事务动态数据存取分轿能够两时表达安 时攀务由于语义和非语义成分所表现的数据存取关联，从而可醣合理地进行蟹筏数据 的划分，这些是优先级分组重装算法的理论基础，该算法与传统重装算法相t e 有更好 实时性能。 ? ? 关键词：主动实时数据库分布式实时数据库内存数据库可预测性 ， o 霉务调度并发控制事务预分析事务预测 v j l 华中科技大学博士学位论文 罱慧= 踹篁墨端= 篇誊= 黜# 筝篇= 筠兰= 黼= 罱端= 粼= = 拦= 群兰岂黼= ；= = = 盏=：兰 a b s t r a c t “ ar e a l - t i m ed a t a b a s es y s t e mi sd e f i n e da sad a t a b a s es y s t e mw h e r et r a n s a c t i o n sa n dd a t a a 托a s s o c i a t e dw i t he x p l i c i tt i m i n gc o n s t r a i n t s a n di tm u s tm a i n t a i nt h el o g i c a lc o n s i s t e n c y r e q u i r e m e n t so ft h ed a t a b a s ea n ds i m u l t a n e o u s l ys a t i s f yv a r i o u st i m i n gr e q u i r e m e n t so f r e a l - t i m et r a n s a c t i o n s ，e s p e c i a l l yt h e i rd e a d l i n e s s oar e a l - t i m ed a t a b a s es y s t e ms h o u l db e a b l et o p r e d i c t t h eb e h a v i o ro f h a r dr e a l - t i m et r a n s a c t i o n ss t a t i c a l l ya n d p r e d i c t t h eb e h a v i o ro f s o f tr e a l - t i m et r a n s a c t i o n s d y n a m i c a l l y , c o n s e q u e n t l y , t h es y s t e m s h o u l dh a v es o m e p r e d i c t a b i l i t yo np r o c e s s i n g o f r e a l - t i m et r a n s a c t i o n s h o w e v e r , i nad a t a b a s es y s t e m ，t h e r ea r ean u m b e ro f s o u r c e so f u n p r e d i c t a b i l i t y , s u c ha s t h ed e p e n d e n c eo ft h ei r a n s a c t i o n se x e c u t i o ns e q u e n c eo nd a t av a l u e s ，d a t aa n dr e s o u r c e c o n f l i c t s ，t h ed e p e n d e n c e sa m o n gt r a n s a c t i o n s ，t h ed y n a m i c t r i g g e r i n g o fn e w a c t i o n s t r a n s a c t i o n s ，d y n a m i cp a g i n ga n dy o ，t r a n s a c t i o na b o r t sa n dt h er e s u l t i n gr o l l b a c k s a n dr e s t a r t s ，a n dt h ec o m m u n i c a t i o n d e l a y sa n d s i t ef a i l u r e si nd i s t r i b u t e dd a t a b a s es y s t e m s a n ds oo n d u et ot h e s ef a c t o r s ，t h ew o r s t - c a s ee x e c u t i o nt i m eo f t h e t r a n s a c t i o n ，i t sa c c e s s i n g d a t ao b j e c t s ，t r i g g e r i n gr u l e r sa n de x e c u t i o ns i t e sa r eu n c e r t a i n ，a n dt h e nm a k ei td i f f i c u l tt o g u a r a n t e et h et i m i n gr e q u i r e m e n t so f t h e _ l r a n s a c t i o ns t a t i c a l l yo rd y n a m i c a l b ：t h e r e f o r e , t h e r e q u i r e m e n t so f p e r f o r m a n c e a n d p r e d i c t a b i l i t yo f r e a l - t i m ed a t a b a s e w o u l dn o tb es a t i s f i e d i no r d e rt os u p p o r tt h ep r e d i c t a b i l i t yo f r e a l - t i m et r a n s a c t i o n p r o c e s s i n g ，s o m es t r a t e g i e s r e s o l v i n g t h ea b o v e p r o b l e m s h a v eb e e n p r o p o s e d i nl i t e r a t u r e s + t h e s es t r a t e g i e sa r eb a s e do n s o m es t r i c tr e s t r i c t i o n so rs o m eu n r e a l i s t i ch y p o t h e s e sa n dc a n n o tu l t i m a t e l yr e s o l v et h e p r o b l e m an e ws t r a t e g y b a s e do nt r a n s a c t i o np r e a n a l y s i si si n t r o d u c e da n di t i n t e g r a t e s t r a n s a c t i o np r e a n a l y s i s , d y n a m i cp r e d i c t i o nw i t ht r a n s a c t i o np r o c e s s i n g ，a n dp r o p o s e sa n d e x p l o r e s a t h r e e - p h a s es c h e m a f o ri t 。t h ef i r s tp h a s ei st h es t a t i cp r e a n a l y s i si nt h ea p p l i c a t i o n d e v e l o p m e n ta n d t h es e c o n di s i n i t i a l l yd y n a m i cp r e a n a l y s i s a tt h ea d m i s s i o no ft h e t r a n s a c t i o n , t h e “r di se x t e m p o r ea n a l y s i sa n dd y n a m i cp r e d i c t i o ni nt h ee x e c u t i o no ft h e t r a n s a c t i o n 。t h et r a n s a c t i o np r e a n a l y s i si n c l u d e s 钉a n s a c t i o nd a t aa c c e s sa n a l y s i s ，d a t a , b e h a v i o r , s t r u c t u r e a n ds e m a n t i c d e p e n d e n c ea n a l y s i sa m o n gt r a n s a c t i o n s ，t h e w c e t t h i sw o r kw a ss u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h m au n d e rg r a n tn o , 6 0 0 7 3 0 4 5 。 n i 华中科技大学博士学位论文 = ；= _ t = = _ = ；= = = _ ；# = ；目= _ = = 2 = = = 一 e s t i m a t i o na n dt h es t a t i cs c h e d u l a b i l i t y a n a l y s i so f t r a u s a c t i o n s s o m er e a l - t i m e d a t a b a s e s y s t e m w i t ht r a n s a c t i o n s h a v i n g d e t e r m i n i s t i cr e s o u r c e r e q u i r e m e n t sm a yr e q u i r en ! i n h l l i z et h eo v e r h e a do f t r a n s a c t i o n p r o c e s s i n gs y s t e m ，e s p e c i a l l 冀 m e m o r ys i z e f o rs u c hs y s t e m sc o n f l i c t b e es c h e d u l ep o l i c ya n d 台a n s a c t i o ns c h e d u t a b i l 盼 a n a l y s i sm o d e la r ep r o p o s e du s i n gp r e e m p t i o nt h r e s h o l d a st h es c h e d u l ep o l i c yi sa b l et o c o n t r o l sw a n s a c t i o n sp r e e m p t i o na n dt h e nc a nr e d u c et h es y s t e mo v e r h e a d i ns c h e d u l a b i l i t y a n a l y s i s ，t h ea s s i g n m e n to f s c h e d u l ep a r a m e t e r si sv e r y i m p o r t a n t w i t hi n t e g e rp r o g r a m m i n g a no p t i m a la s s i g n m e n tm o d e lo f p r i o r i t i e sa n dp r e e m p t i o nt h r e s h o l d si sp r e s e n t e da n dt h i s c o m p u t i n g m o d e lt a k e st r a n s a c t i o ns c h e d u l a b i l i t y ，w a n s a c t i o nl o g i c a lc o n s i s t e n c y r e q u i r e m e n t a n dm e m o r yu t i l i z a t i o no f t r a n s a c t i o n si n t oa c c o u n t h e n c ei ti sm o r ef l e x i b l ea n d n l a k e f o rt h ew h o l e o p t i m i z a t i o no f t r a n s a c t i o ns c h e d u l i n g i nd i s t r i b u t e da c t i v er e a - t i m ed a t a b a s es y s t e m s , s u b t r a n s a e t i o u so fag l o b a lt r a n s a c t i o n m a y e x e c u ti nd i f f e r e n ts i t e sa n dg a n s a c t i o u sc a nt r i g g e rn e wt r a n s a c t i o n so rs u b 拄a n s a c t i o n s ， t h e z ea d d ￥m p r e d i c t a b i l i t 3 , o fd i z t r i b u t e da c t i v er e a l - t i m ei r a n s a c t i o np r o c e s s i n g ，b ys t u d y i n g t h es c h e m a , s y s t e ma r c h i t e c t u r ea n ds t r a t e g i e so fp r e a n a l y s i s ，p r o c e s s i n ga n dd y n a m i c p r e d i c t i o n o fd i s t r i b u t e da c t i v er e a l - t i m et r a l l s a c t i o n , as e m a n t i c sa n ds t r u c t u r em o d e lo f d i s t r i b u t e da c t i v er e a l - t i m et r a n s a c t i o nb a s e do nt r e ei sd e s i g n e d w 弛an e w n o t i o mi e ，j o i n t ， t h es t a t i cp r e a n a l y s i s ，d y n a m i cp r e a n a l y s i sa n dd y n a m i cp r e d i c t i o no ft r a n s a c t i o n sc a l lb e i n t e g r a t e dc l o s e l y m o r e o v e r , ad y n a m i cp r e d i c t i o nm o d e lo fd i s t r i b u t e da c t i v er e a l - t i m e v a n s a c t i o ni sd e v i s e d ，t h ej o i n tm a yb et h eb r a n c hp o i mi 1 1t r a n s a c t i o np r o g r a m ，o rt h e c r e a t i o np o i n to f s u b t r a n s a c t i o n so f g l o b a lw a u s a c t i o na n dt h et r i g g e r i n gp o i n to f a i a c t i v er u l e r , a n da l s ot h ev a l i d a t i n gp o 越o ft h eu n c e r t a i no fs t a t i ca n a l y s i si ne x e c u t i o n ，a b o v ea l l ，i ti s p o i n t a tt h a tt h ed y n a m i ca n a l y s i so f t r a n s a c t i o n ，a d j u s t m e n to f t r a n s a c t i o np r o c e s s i n ga n dt h e a a m i cs c h e d u l a b i l i t yp r e d i c t i o no f t r a n s a c t i o n sc a r r yo u t o nt h eo t h e rh a n d ，i nb a s i so f d e p e n d e n c ea n a l y s i sa m o n gt r a n s a c t i o n s ，s t r a t e g i e sa b o u t d y n a m i cp r i o r i t ya d j u s t m e n ta n di n i t i a lp r i o r i t ya s s i g n m e n to f i r a n s a c t i o no rs u b t r a n s a c t i o n w i t hc o n f l i c t - s e n s i t i v ep r o p e r t ya r ep r o p o s e d b e s i d e s ，ad y n a m i cm o d e la b o u ts y s t e ml o a di s i n l x o d u c e da n db yu s i n go ft h i sm o d e lan e wa d m i s s i o nc o n t r o ls t r a t e g yo ft r a n s a c t i o ni s p r e s e n t e d an e w d i s t r i b u t e dr e a l - t i m es t a t i ct w o - p h a s el o c k i n gp r o t o c o la l s ob ei n t r o d u c e d , a n di tc a nr e l e a s er e d u n d a n tl o c kd y n a m i c a l l yb ym a k eu s eo ft r a n s a c t i o ns t a t i cp r e a n a l y s i s a n dd y n a m i c p r e a n a l y s i s m a i nm e m o r yd a t a b a s ec a l l i m p r o v e t h e p r e d i c t a b i l i t y o fr e a l - t i m et r a n s a c t i o n 华中科技大学博士学位论文 = = = = = = = = = = = ；= = = = = = = = = = = = = = = ； = = ；= ；= = = 一 p r o c e s s i n g i nr e a l t i m em a i nm e m o r y d a m b a s es y s t e m s r e l o a d i n g o f d a t ai sv e r yf r e q u e n ta n d h a sg r e a ti n f l u e n c eo n s y s t e mp e r f o r m a n c e t h ee x i s t i n gr e l o a dm e t h o d sd o n tc o l l s i d e rt h e d a t aa c c e s sa s s o c i a t i o n s an e w n o t i o n , i e ，g r e yr e l a t i o n a lc l o s u r ei si n l r o d u c e df i r s t ，b a s e d o ni tt h ed a t aa c c e s sa s s o c i a t i o nk n o w l e d g ei sm i n e df r o md a t a b a s er e f e r e n c eh i s t o r yw i t h g r e yr e l a t i o n a la n a l y s i s ，a n dt h e nan o v e lp r i o r i t i z e dg r o u pr e l o a da l g o r i t h m ( p g r a ) i s p r o p o s e d ，w h i c hm a k e s f u l lu s eo fd a t aa e z 宅s sa s s o c i a t i o n k n o w l e d g ee x c e p tt h et e m p o r a l i t y o fd a t a , t h ea c c e s sf r e q u e n c i e so fd a t aa n dt r a n s a c t i o ne x e c u t i o np r i o r i t i e s s i m u l a t i o nr e s u l t s s h o wt h a tp g r a p r o v i d e sp e r f o r m a n c ei m p r o v e m e n t o v e rt h ec o n v e n t i o n a lr e l o a da p p r o a c h k e y w o r d s ：d i s t r i b u t e dr e a l - t u n ed a t a b a s ea c t i v er e a l - t i m ed a m b a s e m a i nm e m o r yd a t a b a s e p r e d i c t a b i l i t y t r a n s a c t i o ns c h e d u l i n g c o n c u r r e n c yc o n t r o l t r a n s a c t i o n p r e a n l y s i s t r a n s a c t i o np r e d i c t i o n v 华中科技大学博士学位论文 1 1 实时计算与可预测性 1 绪论 在实时计算系统中，计算的正确性不仅依赖于计算结果的逻辑正确性，而且 也依赖于计算结果产生的时间【。如果错过计算的截止期，系统即使获得逻辑正 确的计算结果，可能仍是毫无价值的，有时甚至导致灾难性的后果。实时计算作 为关键技术广泛地应用于许多重要领域，例如过程控制、核电站生产管理、高速 磁悬浮列车系统、航空航天、无线通讯、空中交通管制、多媒体应用、实时仿真、 虚拟现实、医疗监控、武器装备及军事指挥控制系统等。国际著名的实时计算专 家j s t a n k o v i e 在1 9 9 6 年曾断言：几乎所有的未来计算机系统将是实时计算系统 t 2 。 实时计算融合了计算机科学中系统结构、网络、多媒体、操作系统、调度理 论、程序语言、数据库、形式化方法、软件工程、容错、安全、人工智能等许多 理论和技术，实时计算理论与技术的研究历经大约四十年，已取得了丰硕的成果， 并成功地应用到许多传统的实时系统中，新型实时应用如开放的实时系统、分布 实时计算、实时多媒体计算等提出了许多新的研究课题：支持系统的进化和发展、 性能保证的科学、可靠性与形式化验证、支持实时计算的软件工程等。 除了定时性之外，实时计算区别于传统非实时计算的另一重要标志是系统的 可预测性需求。实时系统的可预测性是指系统具有判定其是否能实现所规定的功 能特性与定时要求的特性。实时系统从简单的单一设备控制系统到高度集成的、 复杂的分布式实时系统，其复杂度具有极大的差异，具体表现在任务截止期的松 紧度不同；截止期有不同的严格性，可能是硬实时、软和固实时；关键性不同， 对于关键的硬实时任务，错过其截止期会导致灾难性的后果，因此必须事先保证 这类任务的资源需求，以预报的方式确保满足其截止期，而对于其它实时任务， 则在系统运行时使其满足截止期的任务的数量比极大；系统的大小及任务间相互 协作依赖的程度的不同；系统所作用的外部环境的特性差别很大等等。它们都影 响着系统的可预测性。 实时系统的可预测性因不同的应用环境特征和不同的任务特性而不同。对小 华中科技大学博士学位论文 1 1 实时计算与可预测性 1 绪论 在实时计算系统中，计算的正确性不仅依赖于计算结果的逻辑正确性，而且 也依赖于计算结果产生的时间【。如果错过计算的截止期，系统即使获得逻辑正 确的计算结果，可能仍是毫无价值的，有时甚至导致灾难性的后果。实时计算作 为关键技术广泛地应用于许多重要领域，例如过程控制、核电站生产管理、高速 磁悬浮列车系统、航空航天、无线通讯、空中交通管制、多媒体应用、实时仿真、 虚拟现实、医疗监控、武器装备及军事指挥控制系统等。国际著名的实时计算专 家j s t a n k o v i e 在1 9 9 6 年曾断言：几乎所有的未来计算机系统将是实时计算系统 t 2 。 实时计算融合了计算机科学中系统结构、网络、多媒体、操作系统、调度理 论、程序语言、数据库、形式化方法、软件工程、容错、安全、人工智能等许多 理论和技术，实时计算理论与技术的研究历经大约四十年，已取得了丰硕的成果， 并成功地应用到许多传统的实时系统中，新型实时应用如开放的实时系统、分布 实时计算、实时多媒体计算等提出了许多新的研究课题：支持系统的进化和发展、 性能保证的科学、可靠性与形式化验证、支持实时计算的软件工程等。 除了定时性之外，实时计算区别于传统非实时计算的另一重要标志是系统的 可预测性需求。实时系统的可预测性是指系统具有判定其是否能实现所规定的功 能特性与定时要求的特性。实时系统从简单的单一设备控制系统到高度集成的、 复杂的分布式实时系统，其复杂度具有极大的差异，具体表现在任务截止期的松 紧度不同；截止期有不同的严格性，可能是硬实时、软和固实时；关键性不同， 对于关键的硬实时任务，错过其截止期会导致灾难性的后果，因此必须事先保证 这类任务的资源需求，以预报的方式确保满足其截止期，而对于其它实时任务， 则在系统运行时使其满足截止期的任务的数量比极大；系统的大小及任务间相互 协作依赖的程度的不同；系统所作用的外部环境的特性差别很大等等。它们都影 响着系统的可预测性。 实时系统的可预测性因不同的应用环境特征和不同的任务特性而不同。对小 华中科技大学博士学位论文 高端端嵩黼篁群描鲁攀踹黜昌誊黼粼絮鲁黼拦黜黼篇蹴端高榴崔黜篇毒黼粘粼篇= = 端邕：出 的静态环境的实时系统，w 预溺馁意睬管瓷系统设计时能够确定地保证满足所裔 强务的定时约菜，冀前提是必须事先获得所有任务的精确特征与倍患，如任务的 个数、经务的执行时间芹讨资源潜求；对具有高度不确定性鼠规模较大的实时环境， 动态、复杂实辩系统可预溯住脊两层语义：在系统层，要求确保满砖所有关键实 对经务豹截止期( 1 0 0 保诞) ，硬实时周期镁务常属此类，当然，这类任务的资 源箨戎与定慰约束必须事先明确，褥对所肖非关键实时任务，系统臌从熬体上按 统计戏概率保诞满足它们的截止期灏性能懿求。在镁努层，每个关键实时任务必 须确保潍最其定避双铡，焚冀悬截止期；恧对任意其它a 关键实时任务( 例如动 态翻达翡嚣髑鲻任务) ，篡搜能依赣予系统遂簿数当煎状态，但系缆应能动态地确 定它稍豹娄嚣炊懑，靼系绞能够农线她镄定装个任务是否熊满足其截止期。 系统实璇蜀溪铡缎，提供裁盘耀保谜豹藏提是憝够搴先绘宠实蛙任务的到达 时阉裙技行辩阗等痿惠，毽获褥任务执黪簿润憋耩确毯是不哥缝鹣，般可以遵 ：；筵分糖、诗冀、傍奏及测试等等蔽继算实对程务抟簸豁攘费对鲻。男终，经务之 耀豹数据程荧、露梵援关、辩瓣稳关及肄突资源熬等特等懿会影酾任务豹实际螭 皮辩蠲，为了控秘这鍪戮索辩妊务实际拽行鼯瓣豹影稳，系统疲采取鸯效麴接蕊， 懿譬 怒程务执行辩阕交纯懿举礁定鬻素转纯舞拳确定静、装至确定弱毅素，铡翔 采麓优先缀礞锛议i 3 ”( p r i o r i t y - c e i l i n gp r o t o c 0 1 ) 控制饶先级赣馕辩澜。v i r g i n i a 大学稀发靛s p r i n gs y s t e m 怒容应舔说懿语富、程謦语裔、软件瘩劝釜成工其、实 辩任务分祈与支持工其、具有确定往的实辩操作系统泠核的一个高度集成鹃蜜对 疲用汗教支持环境，髓有效地分析庶用的执行行为，怒括任务的黼塞、并发、同 步与诃调度健，获取任务的最环执行时间、赞源需求与使埔禳式、任务间酶执行 颓序约束与通信、潜在的阻塞点等知识，运行时的调度器莉用这楚知识构造可行 驰执好计划，从褥裁够支持复杂实时应阁系统的可预测性嘲。 1 2 实时数据霹系统的特镊 程一些实肄应用孛，霸要数握痒功能铃理大量麸黎数据，而传统数据库系统 瘗予没鸯专f 1 搬划处理“对闽维”定对性，因丽不能满足实时殿用的需要，于 楚实蹿数据痒傍为实村舌 弊熬一个重要分支成运蕊生筹已受到广泛两深入的研 究。实对鼗獭露系统是指事务鞠数据郡县鸯定游特性戏显浅定对照割( 典型地为 2 华中科技大学博士学位论文 高端端嵩黼篁群描鲁攀踹黜昌誊黼粼絮鲁黼拦黜黼篇蹴端高榴崔黜篇毒黼粘粼篇= = 端邕：出 的静态环境的实时系统，w 预溺馁意睬管瓷系统设计时能够确定地保证满足所裔 强务的定时约菜，冀前提是必须事先获得所有任务的精确特征与倍患，如任务的 个数、经务的执行时间芹讨资源潜求；对具有高度不确定性鼠规模较大的实时环境， 动态、复杂实辩系统可预溯住脊两层语义：在系统层，要求确保满砖所有关键实 对经务豹截止期( 1 0 0 保诞) ，硬实时周期镁务常属此类，当然，这类任务的资 源箨戎与定慰约束必须事先明确，褥对所肖非关键实时任务，系统臌从熬体上按 统计戏概率保诞满足它们的截止期灏性能懿求。在镁努层，每个关键实时任务必 须确保潍最其定避双铡，焚冀悬截止期；恧对任意其它a 关键实时任务( 例如动 态翻达翡嚣髑鲻任务) ，篡搜能依赣予系统遂簿数当煎状态，但系缆应能动态地确 定它稍豹娄嚣炊懑，靼系绞能够农线她镄定装个任务是否熊满足其截止期。 系统实璇蜀溪铡缎，提供裁盘耀保谜豹藏提是憝够搴先绘宠实蛙任务的到达 时阉裙技行辩阗等痿惠，毽获褥任务执黪簿润憋耩确毯是不哥缝鹣，般可以遵 ：；筵分糖、诗冀、傍奏及测试等等蔽继算实对程务抟簸豁攘费对鲻。男终，经务之 耀豹数据程荧、露梵援关、辩瓣稳关及肄突资源熬等特等懿会影酾任务豹实际螭 皮辩蠲，为了控秘这鍪戮索辩妊务实际拽行鼯瓣豹影稳，系统疲采取鸯效麴接蕊， 懿譬 怒程务执行辩阕交纯懿举礁定鬻素转纯舞拳确定静、装至确定弱毅素，铡翔 采麓优先缀礞锛议i 3 ”( p r i o r i t y - c e i l i n gp r o t o c 0 1 ) 控制饶先级赣馕辩澜。v i r g i n i a 大学稀发靛s p r i n gs y s t e m 怒容应舔说懿语富、程謦语裔、软件瘩劝釜成工其、实 辩任务分祈与支持工其、具有确定往的实辩操作系统泠核的一个高度集成鹃蜜对 疲用汗教支持环境，髓有效地分析庶用的执行行为，怒括任务的黼塞、并发、同 步与诃调度健，获取任务的最环执行时间、赞源需求与使埔禳式、任务间酶执行 颓序约束与通信、潜在的阻塞点等知识，运行时的调度器莉用这楚知识构造可行 驰执好计划，从褥裁够支持复杂实时应阁系统的可预测性嘲。 1 2 实时数据霹系统的特镊 程一些实肄应用孛，霸要数握痒功能铃理大量麸黎数据，而传统数据库系统 瘗予没鸯专f 1 搬划处理“对闽维”定对性，因丽不能满足实时殿用的需要，于 楚实蹿数据痒傍为实村舌 弊熬一个重要分支成运蕊生筹已受到广泛两深入的研 究。实对鼗獭露系统是指事务鞠数据郡县鸯定游特性戏显浅定对照割( 典型地为 2 华中科技大学博士学位论文 截止期) 的数据库系统。其事务处理不仅要维护数据库的一致性约束，即逻辑正 确性，而且也要满足事务的定时限制。实时数据库系统并不是实时系统与数据库 系统的简单叠加，而需要将两者的理论与技术有机、完善地集成，建立新的数据 管理方法和事务处理机制，支持事务处理的可预测性。传统数据库管理永久性的 数据，数据不具有时间特性，事务也无定时限制，且满足可串行化的正确性标准 与a c i d 特性，系统所追求的性能目标是较高的吞吐量和平均响应时间的最小化。 特别地，在传统数据库系统中事务的响应时间一般是不可预测的。与之相比，实 时数据库系统的数据、事务、应用环境有着较大的区别：数据具有时间相关性， 并非所有的数据都是永久的，许多是短暂的，甚至不一定要求所有结果都记录到 永久数据库中，数据的存储、组织、与存取都是“识时”的：支持“时间正确” 的事务调度与“识时”的并发控制协议，放松与扩展可串行化的正确性标准： 及时性是与正确性同等甚至更重要的性能标准，有时宁愿要求及时而部分正确的 信息，而不愿得到完全正确但是过时的信息：传统的平坦原子事务模型已不再 适用，事务可以具有内部结构，事务之间具有结构、数据、行为和时间上的相关 依赖性，它们可能相互合作、直接交互作用与通信。下面，对实时数据库系统的 数据、事务、应用特征进行详细分析和描述。 1 2 1 实时数据特征 一个实时数据库系统一般由三个子系统组成：被控系统、执行控制系统、数 据系统。其中被控系统是指同计算机交互作用的外部环境，称之为物理世界：执 行控制系统监视被控系统的状态，协调和控制它的活动，称为逻辑世界；数据系 统有效地存储、操纵与管理实时信息，称为内部世界，执行控制系统和数据系统 统称控制系统。内部世界状态及时地反应物理世界状态，执行控制系统藉此感知 物理世界状态，并与被控系统交互作用。 因此，在实时数据库系统中，数据除了满足传统数据库所要求的完整性、一 致性约束之外，其特征主要体现在它的时态特征上，即实时数据可能在某一时间 内是有效的，而过期则是无效的。例如，反应飞行器位置的数据因飞行器位置的 快速变化而只是短暂有效的，把与之相关联的时间称为绝对有效期；另外，当多 个实时数据共同参与计算时，还应考虑数据间的“相互时间一致性”，即只有这些 数据满足相互有效期，计算才是有效的。下面给出形式化的描述。 3 华中科技大学博士学位论文 拦兰罱篙= 糕= 篇盘= 篇= 罱= = 拦皇群# = 糙= 群= 奄粘= 然兰昌黼= 篁= # = = = - 一个r t d b 的数据对象被定义为个三元组庆 。其中分鬣巩、巩、 玩v 分别为d 的当前状态或值；观测时标( o b s e r v a t i o nt i m e s t a m p ) ；外部( 绝对) 有效期( e x t e r n a lv a l i d i t yi n t e r v a l ) 陬7 1 。 内部一致性 数据d 是内郝( 或逻辑) 一致的，当且仅港4 满足所有对其预先定义的数 据岸内部的完整性限制和一致性要求。 外部一致性 数据d 是终部( 或绝对) 一致豹，当且仅当( 一如) 旗文岛为当翦或检测时 阗1 。 相互一致性 撼共溺参与计算鹣一组楣关数据称必一令摆互( 提对) 一致集，每一这撵豹 数据集霞都有一奄之襁联豹摇互有效期( m u t u a lv a l i d i t yi m e r v a l ) ，记必盂。，。若 d 霆，d 燕裙匿( 或辐对) 一致的，港虽仅当：v d e r | 如一蠢豁 露。w ) 。 辩闻一致往( t e m p o r a c o n s i s t e n c y ) 对d 毯霞，d 是时闯一致的，警置仅当d 既是外部一致的又是相蠢一致的。 数据庠状态正确悛 当且仅当个数据同时飚内部一致和时间一致的，它才有难确状态。而数据 库有正确状态则意味着其中每一数据都裔正确状态。 事务的并发控制与事务操作的完整性检查掇供数据库的内部一致住保证，对 于传统数据库，般基予可串行化的正确性标准并采用两段锁并发控制协议也就 足够了，但在实时数据库系统中，还必须提供“识时”的攀务处理机制来保证数 据的时间一致性。同时保证数据的内部一致性和时间一致饿对于事务处理具有潜 我的困难，它们往往是一对难以调和的矛盾，因此，有时为了实时性需要在一定 范围内牺牲内部一致性以求时间一致性。 1 2 2 实时事务的特征与分类 安露数撂浑事务熬擞本特短是宠露性，定黠可以是绝慰、相对或舆期蛙间。 实时事务定辩性的报源蔓要有器今方露爨毽素：由数豢熬对阅致牲嚣求艨熬加 予实时事务的定辩链，它一般取定期或周鬻性限制熊形式；由物爨世器撬鸯瑟予控 4 华中科技大学博士学位论文 = = = = = = = = = = = = = = = = ；= = = = = = ；= = = = = = = = = = = = 一= = 一 制系统的反应时间要求所引起的实时事务的定时性，它典型地取施加于非定期事 务的截止时间限制形式。 除了定时性之外，实时事务的特征还表现在使用数据的方式、关键性、功能 及到达率等方面，据此可以将实时事务进行以下几种分类。 按使用数据的方式分类 只写事务收集关于现实世界的信息并写入数据库。 只读事务读取数据库中的数据值并设置执行控制部件的参数。 更新事务基于现有数据值导出新的数据值，故它可能既读又写。 按关键性( 截止期的严格度) 分类 硬实时事务超截止期会导致恶果( 价值函数取大的负值) 。 软实时事务超截止期仍有一定的价值，但不断下降，直到某时刻其价 值降到零，此后保持为零( 不会为负) 。 固实时事务旦到达截止时间，其价值立即降为零，此后固定为零( 也 不会为负) 。显然，固实时事务是软实时事务的特例。 按到达时间分类 周期事务以一定的周期循环地到达和被执行。 非周期事务一一由外部事件( 如现实世界状态变化) 或内部事件( 如特定的 时钟行为、数据库状态的变化) 动态驱动。 零星事务偶尔地一次性执行。 实时事务处理必须针对各类事务的不同特征提供相应的调度与并发控制策 略，从而实现各自的性能目标。在一个实时数据库系统中同时支持硬实时事务和 软实时事务使事务处理极为复杂与困难，因此，混合类型的实时事务处理仍然是 需要进一步研究的课题之一。 1 2 3 实时数据库应用 实时数据库应用，如过程控制、电话交换、自动取款机、高能物理实验、集 装箱码头自动控制与管理、电力或数据网管理、空中交通管制、雷达跟踪、军事 指挥控制系统、c i m s 、金融证券交易等与传统商务和事务型应用都不一样，它们 具有下列共同的基本特点( 或要求) ： 5 华中科技大学博士学位论文 = ；= = = 自= # = = = = _ = = = ；= = = _ = = = 一： ( 1 ) 定时蚀：数据与事务都具有定时限制，系统必须确僳满足“硬实时”事 务的定时限制，“软实时”事务超截止时间