（计算机软件与理论专业论文）基于替代补偿的嵌入式实时事务模型及其处理技术.pdf

华中科技大学博士学位论文 摘要 随着嵌入式系统的日益普及，作为数据处理核心环节的嵌入式实时数据库系统 应能嵌入到设备或大型软件中，并且能直接与环境接口和交互，除了具备一般实时 数据库系统的特点外，它还应具备以下特点：可伸缩性、可裁减性、高可靠性、体 积小、较高的可预见能力和应变能力、开放的设备驱动程序、广泛的硬件支持、开 放的用户接口等，传统的实时数据库系统和嵌入式数据库系统不能满足这些要求， 为此，需要从事务模型、并发控制、调度等方面进行研究，提供新的适合嵌入式实 时数据库系统的机制和策略。 ， 首先，文章提出了一个基于功能替代性的实时事务模型f a t m 口砝定义实时事务 为若干任务( 事务步) 的集合，每个任务又由若干功能等价的子事务组成，在每个 任务中取个子事务就组成该事务的一个替代，这样，替代就成为摹务调度和并发 控制的基本单位。只要有一个替代成功执行，则该事务可提交，但是一个替代夭折 并不代表该事务夭折，只有当事务所有的替代都失败( 或必定会超过截止期) ，该事 务才天折。功能替代性使事务的执行具有多条路径，提高了事务的适应能力和应变 能力，从而提高了事务的成功率。为了提高嵌入式实时数据库系统在非人工干预下 的可靠性，我们对默r m 进行扩展，使之支持补偿性，提出了支持替代脖b 偿的实时 事务模型，即：事务由主任务和补偿任务组成，当主任务不能成功执行时由其补偿 任务使之安全结束，防止夭折的硬实时事务对系统造成灾难。 同一事务的替代虽然在功能上是等价的，但在性能上存在差异，因此，调度不 同的替代投入运行，其效果是不同的，此特点导致事务的调度具有= 重性：调度分 为内部调度和外部调度。内部调度根据替代之间的性能差异，对该事务的所有可调 度替代进行调度，当其结果为空时该实时事务不可调度，外部调度类似于传统的实 时事务调度，其处理对象就是内部调度的结果，当事务执行失败时，不能立即夭折， 必须重新转入内部调度，停止此调度活动的原因有：事务的截止期到：由特殊操作 强迫停止；该事务的所有替代都失败；有一个替代成功执行。 在并发控制方面，与二重调度相匹配的是二重并发控制策略，即：替代级控制和 事务级控制，在替代级控制中，两个具有代表性的策略是c b h 和c c a ，c b h 允许 一个事务的多个替代并发抗行，他们是彼此相容的，主要针对子硬实对事务；c c a 在一个时刻只允许事务中的一个可调度性较强的替代执行。它们的目的都是提高实 时事务的成功率，文章给出了实现方法。y 所有这些调度和并发控制策略的实现依赖于正确的事务预分析，针对新的事务特 1 华中科技大学博士学位论文 点，文章明确指出事务动态估算执行时间和静态估算执行时间的区别，动态估算执 行时间才是对实时调度更为有意义的，并结合灰色系统理论建立了估算事务动态执 行时帕j 的模型；同时，文章在研究替代生成、替代资源需求的基础上，分析替代的 可调度性，为实时调度和实时并发控制的实施提供依据。 由于超载将导致过重的资源竞争并提高系统的控制复杂度、降低事务成功率，保 证系统效率和可靠性的另一个关键环节是有效的接纳控制机制，文章就此进行了深 入的研究。提出了一套接纳协议和相应的策略。在抢占处理上，传统的方法是高优 先级事务抢占低优先级事务，它可能抢占了一大批优先级低的事务，当这些低优先 级事务的总价值更大时，系统总体收益降低，因此，我们的接纳控制机制综合考虑 事务的优先级和和系统的总价值。 v 7， 关键词：数据库系统实时数据库系统嵌入式数据库系统事务处理 i i 华中科技大学博士学位论文 a b s t r a c t w i t l lt h ei n c r e a s i n gd e p l o y m e n to fc o m p u t e r sa se m b e d d e ds y s t e m s 、t h ee m b e d d e d r e a l - t i m ed a t a b a s es y s t e m sn o to n l ys h o u l db ei n t e g r a t e di n t oa d v i c e sa n d l a r g es o f t w a r e a sc o r eo fd e a l i n gw i t hd a t ab u ta l s oi n t e r f a c ew i t he n v i r o n m e n td i r e c t l y b e s i d e st h e g e n e r a lf e a t u r e so f r e a l - t i m ed a t a b a s es y s t e m s ，i ts h o u l dh a st h e s ec h a r a c t e r i s t i c sa sf o l l o w ： r e t r a c t i l i t y , s e w b i l i t y ，r e l i a b i l i t y , l i t t l ef o o t p r i n t ，p r e d i c t a b i l i t ya n dm e e t i n gt h ee m e r g e n c y , o p e n i n ga d v i c ed r i v e r s ，e x t e n s i v eh a r d w a r es u p p o r t , a n do p e n i n gu s e r - i n t e r f a c e ，e t c a s t h et r a d i t i o n a lr e a l - t i m ed a t a b a s es y s t e m sa n de m b e d d e dd a t a b a s es y s t e m sc a nn o tm e e t t h e s er e q u i r e m e n t s ，i ti sn e c e s s a r yt op r o v i d eh e wm e c l u m i s m sa n ds t r a t e g i e ss u i t a b l ef o r e m b e d d e dr e a l - t i m ed a t a b a s e s y s t e m st h r o u g hr e s e a r c h i n g o nt r a n s a c t i o n m o d e l ， c o n c u r r e n c yc o n t r o l ，s c h e d u l ea n d s oo n f o rs o l v i n gt h eq u e s t i o n sa sa b o v e ，t h i sp a p e rp r o p o s e sa nr e a l - t i m et r a n s a c t i o n m o d e lf a t mb a s e do nf u n c t i o na l t e r n a t i v ec h a r a c t e r i z e 黝删d e f i n e sa nr e a l t i m e t r a n s a c t i o na sas e to fs o m et a s k ( v i z t r a n s a c t i o ns t e p ) ，e a c ht a s kc o n s i s t so ff u n c t i o n e q u i v a l e n c es u b - t r a n s a c t i o n s t a k eo n es u b - t r a n s a c t i o nf r o me a c ht a s kt oc o n s t i t u t eo n e a l t e r n a t i v eo ft h er e a l - t i m et r a n s a c t i o n , t h u sa l t e r r m t i v eb e c o m e st h eu n i to fc o n c u r r e n c y c o n t r o la n ds c h e d u l e a nr e a l - t i m et r a n s a c t i o nc a nc o m m i to n l yi t so n ea l t e m a t i v e c o m p l e t es u c c e s s f u l b u ti ta b o r tw h i l ea l li t sa l t e r n a t i v e sl o s t n 地f u n c t i o nc h a r a c t e r i s t i c m a k e st r a n s a c t i o ne x e c u t i o nh a sm a n yr o u t e ss oa st oi m p r o v es u i t a b i l i t yo fr e a l - t i m e t r a n s a c t i o n s ，t h e r e b ya d v a n c i n gs u c c e s s f u l - r a t i o o fr e a l t i m et r a n s a c t i o n s i no r d e rt o i m p r o v er e l i a b i l i t yo fe m b e d d e dd a t a b a s es y s t e m sr u n n i n gw i t h o u th u m a ni n t e r r u p t ，w e e x t e n df a t mt os u p p o rc o m p e n s a t i o n i tm o d 旺1 st h a tr e a l - t i m et r a n s a c t i o nc o m p o s e so f m a i nt a s ka n d c o m p e n s a t i o nt a s k n cm m s a c t i o nc 觚f i n i s hs a f e l y t h r o u g h i t s c o m p e n s a t i o n t a s ka v o i d i n gd e f e a t e dh a r dr e a l - t i m et r a n s a c t i o n sc 钔m s y s t e mc a l a m i t y t h e s ea l t e r n a t i v e sb e l o n g i n gt oo n er e a l t i m et r a n s a c t i o nh a sd i f f e r e n tp e r f o r m a n c e a l t h o u g h t h e i rf u n c t i o ni ss a m e ，t h ee f f e c to fo n ea l t e r n a t i v ew i l ld i f f e rf r o mo t h e r a l t e r n a t i v e s ，t h u s t r a n s a c t i o ns c h e d u l eh a st w os t e p s ：i m e r i o rs c h e d u l e ra n de x t e r i o r s c h e d u l e r t h ei n t e r i o rs c h e d u l e rd e a l sw i t ha l ls c h e d u l a b l ea l t e r n a t i v e sa c c o r d i n gt ot h c i r d i f f e r e n c e p e r f o r m a n c e o n er e a l t i m e t r a n s a c t i o ni su n - s c h e d u l a b l ew h e ni t s i n t e r i o r s c h e d u l er e s u l ti n t oa ne m p t ys e t n l ee x t e r i o rs c h e d u l ei s s i m i l a r l yt o c o n v e n t i o n a l r e a l t i m es c h e d u l e ，i t so b j e c ti st h er e s u l ts e to fi n t e r i o rs c h e d u l e r w h e no n et r a n s a c t i o n l i l 华中科技大学博士学位论文 l o s ii tw i l li o i nt oi n t e r i o rs c h e d u l e t h er e a s o nw h yt h es c h e d u l es t o pa r es h o w e da s f o l l o w ：t h et r a n s a c t i o nl o s ei t sd e a d l i n e ，s o m es p e c i a lo p e r a t i o n sf o r c ei tt os t o p ，a l lo fi t s a l t e r n a t i v e sa r el o s t ，o n ea l t e r n a t i v ec o m p l e t es u c c e s s f u l t h e c o n c u r r e n c yc o n t r o la l s oh a s t w os t e p ss u i t e dt os c h e d u l e i ti sa l t e r n a t i v ed e g r e e c o n t r o la n dt r a n s a c t i o n d e g r e e c o n t r 0 1 t w or e p r e s e n t a t i o n a l s t r m e g i e s i na l t e r n a t i v e d e g r e ea r ec b h a n dc c a c b ha l l o w ss o m ec o n s i s t e n ta l t e r n a t i y e se x e c u t ec o n c u r r e n t l y w h i c hs u i tt oh a r dr e a l t i m et r a n s a c t i o n s ；b u tc c aa l l o w so n l yo n ea l t e r n a t i v er u na ta t i m e t h e i rp u r p o s ei s e n h a n c i n gt r a n s a c t i o n s u c c e s s r a t i o t h i sp a p e rg i v e sr e l e v a n t r e a l i z a t i o nm e t h o d s t or e a l i z a t i o nt h e s e s t r a t e g i e s f o rs c h e d u l ea n dc o n c u r r e n c yc o n t r o l d e p e n do n t r a n s a c t i o n p r e - a n a l y s i s c o r r e c t l y i n a l l u s i o n t on e wc h a r a c t e r i s t i c so fr e a l t i m e t r a n s a c t i o n sw e p o i n t o u tt h a tt r a n s a c t i o ns t a t i cw o r s te s t i m a t ee x e c u t et i m ed i f f e rf r o mi t s d y n a m i ce s t i m a t ee x e c u t et i m e t h el a t t e ri sm o r e c o n t e n tf o rr e a l - t i m es c h e d u l e w eb u i l d t h em o d e le s t i m a t i n gd y n a m i ce s t i m a t ee x e c u t et i m ew i t l lg r e ys y s t e mt h e o r y w ea l s o a n a l y z ea l t e r n a t i v e s s c h e d u l a b i l i t yi no r d e r t op r o v i d ei n f o r m a t i o nf o rr e a l - t i m es c h e d u l e a n d c o n c u r r e n c y c o n t r 0 1 t h eo t h e rk e yt og u a r a n t e es y s t e me f f i c i e n c ya n dr e l i a b i l i t yi se f f e c t i v ea d m i t t i n g c o n t r o lm e c h a n i s mb e c a u s eo v e r l o a dw i l lr e s u l tt oo v e r w e i g h tr e s o r l c ec o m p e t i t i o na n d e n h a n c e c o m p l e x i t y f o rs y s t e mc o n t r 0 1 w es t u d ya b o u tt h e s eq u e s t i o n sa n d p r o p o s e a d m i t p r o t o c o l sa n dr e l e v a n ts t r a t e g i e s t h ec o n v e n t i o n a lp r e e m p ts t r a t e g i e sm a k eh i g l lp r i o r i t y t r a n s a c t i o n p r e e m p t l o w e rp r i o r i t yt r a n s a c t i o n s ，s ot h eh i 曲p r i o r i t yt r a n s a c t i o n m a y p r e e m p t sal o to f l o w e r p r i o r i t yt r a n s a c t i o n s ，t h eq u e s t i o ni st h a tt o t a ls y s t e mb e n e f i tm a y b er e d u c e dw h e nt h et o t a lv a l u eo ft h e s el o w e rp r i o r i t yt r a n s a c t i o n si sb i g g e r t h u so b r a d m i tc o n t r o lm e c h a n i s m c o l l i g a t ep r i o r i t ya n d v a l u eo f t r a n s a c t i o n k e y w o r d ：d a t a b a s es y s t e m r e a l - t i m ed a t a b a s es y s t e m e m b e d d e dd a t a b a s es y s t e mt r a n s a c t i o np r o c e s s 华中科技大学博士学位论文 月u盖 嵌入式数据库系统随着便携式计算设备的发展而发展壮大，时至今日，它不仅可 以嵌入到便携式计算设备中，而且可以作为一个部件安装于大型设备和大型软件中， 与应用环境紧密结合，应用于航天、航海、军事武器、工业控制、机器人等各行业以 及汽车、家用电器等生活设旋中，具有广泛的应用前景。在实际应用中，常常要求嵌 入式数据库系统对外部环境作出实时反应，这就使研制嵌入式实时数据库系统成为当 务之急。 常用于嵌入式软件系统的d b s 分为三类：第一类如c e n t u r as o f t w a r e 公司的 v e l o c i s ，e m p r e s s 公司的e m p r e s sr d b m s ，o r a c l e 公司的o r a c l e8 i 等，它们是支 持c s 的关系型d b s ，虽然因为提供人们熟悉的s o l 得以流行，但要花费额外的时间 用于在客户机和服务器之间的通讯，并且在嵌入式系统中安装、运行和维护独立的服 务器处理过程时分外复杂。第二类如o b j e c t i v i t y 公司的o b j e c t i v i t y d b ， p e r s i s t e n c e 公司的p o w e r t i e r 等，它们是运行于u n i x 操作系统之上的面向对象的 d b s ，其主要缺点是只能使用在u n i x 操作系统、基于l i n u x 的系统以及u n i x 的某些 变种如f r e e b s d 上，难以与其它复杂的嵌入式操作系统接口，很少有操作系统能支 持它，并且必须花费c s 通讯；第三类如c e n t u r as o f t w a r e 公司的r d m ，d b 1 i n u x ， f a i r c o m 公司的c t r e ep l u s ，以及s l e e p y c a ts o f t w a r e 公司的b e r k e l e y d b ，它们 直接连接于嵌入式系统的地址空间，提供简单的语言级a p i 操纵数据而不是s q l ，由 于数据操纵不需与独立的服务器通讯，系统的运行速度较快，另外，由于运行于嵌入 式系统上的部件较少，系统的可靠性较高，不足是要求开发者精通非标准的程序设计 接口。由此可见，目前的嵌入式数据库系统不具备实时性。但在实际应用中，常常要 求系统对外部环境作出实时反应，而目前的实时数据库系统又难以保证高的成功率， 因此不能适应嵌入式环境，鉴于国内外还没有发现此类产品，我们的研究具有开创意 义。 由于生存环境的改变，用户对嵌入式实时数据库系统的需求也与传统的实时数据 库系统不同，嵌入式实时数据库系统从事务模型、并发控制机制、调度策略到恢复等 各方面都具有新的特点，需要我们重新探讨和研究，通过本课题的研制将会丰富数据 库理论，并对数据库技术的发展产生较大的影响。 华中科技大学博士学位论文 1绪论 1 i 嵌入式实时数据库应用 嵌入式数据库系统的兴起可以归功于便携式计算设备的开发兴起。由于这些设 备可以被大量生产并且具有通讯能力，用户开始用它们存储设备本身产生的大量增 加的数据和从中心企业下载的资料，以便脱线工作，因此，需要这些设备具备成熟 的数据管理能力，这些功能常常如此复杂以至平坦的文件系统不足以处理和操纵这 些数据，这就促使了对嵌入式数据库的需求。除此之外，嵌入式数据库系统还可以 嵌入到大型软件系统或设备中，存储和处理来自于所在设备和其它地方的数据，可 以访问监视器、进行诊断以及进行其它工作。例如：“汽车制造商用嵌入式数据库获 取关于汽车磨损、毁坏、行程里数和性能等的数据”，“化学植物公司的处理控制系 统可以用嵌入式数据库记录通过探测器收集到的日志，这些数据可以下载到大型中 心数据库以便改善处理过程”。这样的设备还包括具备上i n t e m e t 网功能的智能手机 ( 个人数字助理) 、售卖机等；智能装置和嵌入式系统也开始用嵌入式数据库，智能 装置包括一些路游器和h u b ；嵌入式数据库系统还可以安装在各种( 移动的和 移动 的) 设备中，可应用于航天、航海、军事武器、工业控制、机器人等各行业以及汽 车、家用电器等生活设施中，具有广泛的应用前景。由于嵌入式数据库系统常常需 要对环境作出实时反应，应准确地称之为嵌入式实时数据库系统。 1 2 嵌入式数据库的研究现状 嵌入式数据库市场有时不直接面向用户而是面向设备制造商，设备制造商将它 嵌入到设备和应用中，将嵌入式数据库产品分类成表1 1 所示的关系型c s 产品和 表l 2 所示的面向对象c s 产品，以及表1 3 所示的嵌入式程序库。它们各有优劣， 因为不同的原因而流行。表1 3 中只有g d b m 不支持事务和一定程度的并发存取。 如表1 1 所示的一些厂商提供c s 关系型系统。象m i c r o s o f t 公司、o r a c l e 公 司、s y b a s e 公司以及i n f o r m i x 公司研制出售高级终端企业数据库系统和企业数据库 引擎。对于嵌入式系统开发者，c s 关系型产品十分流行，因为程序员们已经熟悉了 垡中科技大学博士学位论文 s q l 和关系数据库设计。缺点是客户机和服务器之间的通讯要花费额外的代价，并且 在嵌入式系统中安装、运行和维护一个独立的服务器处理器增加了复杂度。 表1 1 关系型c s 产品 7 厂商产品特点 据管理的s q l 和编程接口。 e m p r e s se m p r e s sr d b m s 运行于主要的嵌入式o s ，支持数据管理的 s q l 和编程接口。 m i c r o s o f lm s d e o r a c l e8 i p e r a s i v e p e r a s i v e s q l2 0 0 0 p o l y h e d r ap l o y h e d r a s o l i de m b e d d e d s y b a s es q la n y w h e r e t i r u e s t e nt i m e s t e n 与m i c r o s o rs q ls e v e rd be n g i n e 兼容，支 持的并发度有限，相应的数据量较小只能 运行于m i c r o s o f t 操作系统。 运行于l i n u x ，一个c s 系统支持公司的标 准接口。 适应于嵌入式o s ，也能运行于桌面和服务 器o s 上。支持简单的数据操作接口。可以 根据嵌入式需求裁减。 支持s q l 的c sd be n g i n e ，运行于桌面、 服务器和嵌入式o s 。 在多种服务器和嵌入式o s 上提供数据库管 理服务，通过s q l 提供数据存取，具有 o d b c 和j d b c 接口。 一个可以根据应用裁减的s q l 引擎。特别 强调与运行- t l l l t 务器上的s y b a s e 企业数据 库同步 通过s q l 、o d b c 、j d b c 提供标准的关系 数据存取，设计使用于大内存系统，主要运 行予桌面和服务器系统。 2 华中科技大学博士学位论文 一= = = = = = = = = = = = ：= = = = = ；= = = = = = = = = ；= = = = ：= ：= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ：= = = ；= = = ；= = = = = = = = = = = 一 表1 2 面向对象的c s 产品 厂商 产品特点 o b j e c t i v i t yo b j e c t i v i t y d b p o e ts o f t w a r ep o e to b j e c t 对c + + 、j a v a 稳定的对象存储。支持桌面和服 务器o s ，但不提供嵌入式0 s 支持处理模型比其它 厂商的产品复杂。开发者可以配置复制和其它服 务。 与许多厂商生产的流行数据库接口的客户库。支 持企业j a v ab e a n 和c + + 。客户软件运行于桌面 和服务器0 s 上，服务器平台由数据库服务引擎 的厂商决定 客户库允许c + + 和j a v a 应用于各种后台数据库服 务器，包括p o e t s 面向对象数据和o r a c l e 和其 它厂商的关系型数据库，提供稳定的对象存储， 不支持嵌入式0 s 支持。 表1 2 所示的产品很少有人考虑，因为开发者为u n i x 设计了流行的面向对象数 据库并且使它们建立在关于内存管理系统和通讯处理的有关假设上。难以与嵌入式 o s 接口。然而，可以证明它们可用于l i n u x b a s e d 系统，比如f r e e b s d 可以用于嵌 入式设备。面向对象数据库系统之所以流行是因为它们集成了c + + 和j a v a 程序语言， 并且对应用程序员隐藏了数据库设计的复杂性。主要缺点是c s 通讯负担和很少的 开发者支持嵌入式0 s 。 表1 3 所示的厂商为嵌入式应用设计嵌入式程序库。他们的系统直接链接到应 用的地址空间，提供简单的语言级a p i 而不是操纵数据的s o l 。嵌入式程序库的主要 优点是： 快速执行。因为数据库操作不需要与隔离的服务器通讯。 华中科技大学博士学位论文 提高了可靠性，因为极少的部件运行在嵌入式系统上。 嵌入式库的明显缺点是：要求开发者精通非标准化的编程接口。 表i 3 嵌入的程序库 厂商产品特点 c e n t u r as o f t w a r er d m d b 1i n u x f r e es o f t w a r ef o n n d a t i o ng d b m c i s a m s l e e p y c a ts o f t w a r eb e r k e l e yd b 作为源代码发布，r d m 编译到与应用相连接的 一个库中。运行于嵌入式0 s 上，公司提供r d m 的l i n u x 接口d b 1 i n x 。 作为源代码发布，直接编译到应用的地址空间。 支持q n x 和l y n x o s ，但用户可以将源代码赢接 接口( p o r t ) 到其它嵌入式0 s 。 提供简单的编程接口到数据记录，不支持并行 的读写和事务，遵从l i b r a r yg e n e r a l p u b l i c l i c e n s e ，以源代码的形式发布，没有f r e e s o f t w a r ef o u n d a t i o n 对嵌入式o s 接口的明确 支持。不管怎样，很多接口可用。用户可以自由 地将该软件接口到新的o s 。 可嵌入的数据管理库提供嵌入式系统要求的服 务该库只运行于桌面和服务器o s 。 为数据库提供简单的编程接口，可以根据嵌入 式系统的要求配置需要的和不需要的部件。以源 代码的形式发布。运行于桌面和服务器以及某些 嵌入式o s 上。 4 华中科技大学博士学位论文 1 3 实时数据库系统研究现状 现有的嵌入式数据库系统在模型和并发控制机制上并无新意川，它们沿用了普通 数据库系统的一些控制机制，或加以部分改造【2 l ，一方面，目前的嵌入式数据库系统 不具备实时性，但在实际应用中，常常要求系统对外部环境作出实时反应；另方 面，目前的实时数据库系统( r t d b s ) 又由于难以保证高的成功率而不能适应嵌入式环 境，因为嵌入式实时数据库系统的基本目标之一就是具有高的成功率从而具备高的 可靠性，因此，严格地说，目前还没有真正意义上的嵌入式实时数据库系统。 实时数据库乃指事务和数据都可具有显式的定时限制系统的正确执行既要满 足逻辑约束又要满足时间约束，同时满足这两种一致性要求的实时数据库事务的处 理与传统的数据库相比具有更大的困难。事务处理中的众多不可预测因数的存在， 以及时间约束与逻辑约束的并存导致实时摹务的调度策略和并发控制技术成为研究 热点m 。 1 3 1 实时事务模型 在”3 中k i m 建立了一个r t d b s 模型，它包含硬实时事务和软实时事务，维护数 据的时态和逻辑一致性o “”1 ，支持多担保级别，在这个模型下，设计出一个集成的 事务处理方案，提供r t d b s 的预测能力和一致性，这样，系统中的每个应用被确保 取得它们各自的性能目标( 确保级) ，并且维持一致性需求。模拟实验表明：高确保 级需要更多的系统资源，代价高于非确保事务。在“1 “1 中，b r a o u d a k i s 使事务与一个 价值函数关联，该价值函数表示时间约束以及事务的重要性，这个模型可以说明非 实时事务、软实时事务、固实时事务和硬实时事务，此模型的特点是用一致的方法 处理不问类型的事务，事务价值以及价值函数的观点被应用于两个实时系统“7 ”3 以及 r t d b s “? ”3 中，在“。”1 中，任务的价值在接纳该任务时被估算出来，根据任务的价值 决定是否拒绝或移走一个已经被确保的任务，被系统接纳的任务有条件地确保完成 其执行，只要没有更高价值的冲突任务到达。z h o u ，r u n d e n s t e i n e r ，和s h i n 将面 向对象的观点结合到实时数据库系统中，提出了r 伽p p 一个实时的对象模型”“， 在”9 ”1 中用面向对象的框架探讨了时态和逻辑一致性和正确性。 华中科技大学博士学位论文 132 实时并发控制策略 我们不能沿用传统数据库系统的并发控制协议，因为它们强调所有事务具有平 等的地位和相同的调度机会o “。对于r t d b s 而言，为了使尽可能多的事务满足它们 的截止期，应该将事务的时间信息加入到调度中来，事务越紧急应越早地投入运行。 当一个事务正在运行时，如果新到了一个更为紧急的事务，该执行事务应该让出处 理机及对所有资源的控制权，使新到的紧急事务先执行。 具体来说，r t d b s 中事务的并发执行具有以下特点： ( 1 ) 并发执行的事务具有时间约束和依赖性； 实时数据库系统中的事务具有显示的时间约束，除此以外，当它们并发执行时， 事务之间可能存在与时间有关的依赖关系，比如：事务t l 必须在事务t 2 开始执行 之前( 或提交前后) 开始提交；一个事务在运行过程中可能触发其它的子事务， 被触发事务与此触发事务并发执行，当触发事务完成时，可能不能立即提交，需要 等到被它触发的事务也完成以便一起提交；等等，在传统数据库系统中，并发执行 的事务间也存在关联，但主要是由于事务间通讯产生的，与我们所指的关联显然具 有根本区别。 ( 2 ) 必须满足硬实时事务的截止期要求，尽可能多地满足软实时事务的截止期 要求； 在实时数据库系统中，按截止期的特性将实时事务分作硬实时事务和软实时事 务。系统必须保证硬实时事务的截止期，否则，该事务在截止期后可能对系统产生 危害，同时，虽然软实时事务超过截止期后不会对系统产生危害，但该事务的价值 也会急剧下降，由此，并发控制在保证数据一致性的前提下，为了满足事务的截止 期要求，应区别对待不同特性的实时事务。 ( 3 ) 一个正在运行的事务可以被更为紧急的事务抢占系统资源和c p o 控制权； 如上所述，当一个紧急事务到达时，为了处理该紧急事务，系统使正在执行( 还 未完成) 的事务夭折，执行该紧急事务。 ( 4 ) 由于必须保证事务的原子性，被抢占的事务可能夭折重启； 实时数据库系统的事务与传统数据库系统中的事务相比，具有更为复杂的结构 华中科技大学博士学位论文 和更强的描述能力，它已不再是平淡的操作序列。典型的事务模型具有分裂结构、 嵌套结构等。似乎不必维持事务的原予性，其实不然，从事务的整体角度上来说， 由于事务可以嵌套( 或分裂) 甚至触发多个子事务，其原子性被破坏了，但对于组 成该复杂事务的基本事务( 子事务) 来说，依然应保持原子性，因此，当一个基本 事务被抢占后，必须重启。 ( 5 ) 事务处理的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间； ( 6 ) 系统宁愿要及时的部分正确的结果，也不要过时的精确的结果； 在资源受限的实时数据库系统中，并发事务竞争系统资源，当系统超载时，必 然存在某些事务不能在其截止期内完成，对于某些实时应用环境，在截止期之后的 精确结果是无效的，那么，在截止期内，即使得不到精确结果，如果能得到近似结 果也比根本没有结果要好得多“。 ( 7 ) 传统的数据一致性标准有所放松； 传统的数据库一致性标准是可串行化，并发控制的目的是保证数据的逻辑一致 性，要求事务是平坦的，具有a c i d 特性对于实时数据库系统而言，要求满足数据 的时态一致性和逻辑一致性啪1 ，为了使尽可能多的事务满足截止期，需要放松正确 性标准以满足或兼顾时间致性要求，早期的努力集中于放松截止期的语义( 主要 是软实时事务和固实时事务扭町，不能应用于硬实时事务) 或事务的a c i d 特性( 特 别在可串行性方面) 汹。“”1 ，在。2 1 中k u o 和m o k 提出了建立在基于语义的正确性标准 ”之上的基于类似的并发控制策。一般作法是在传统的乐观或悲观并发控制基础上， 加以改造以适应实时并发控制需要。典型的并发控制正确性标准有： e 一可串行化并发控制 一可串行化( e p s i l o n s e r i a l i z a b i l i t y ) 是事务处理中的一种正确性标准， 它是一种更一般的误差受限的串行化。它允许不一致性数据被读取，并控制不一致 性的程度，使误差量限制在一个指定范围，而使数据最终能达到一个一致性状态。 e 可串行化需要数据库的数据空间是一可度量空间，使用e 一可串行化放松逻辑 一致性要求以期满足时间致性要求m ”。 一可串行性并发控制 a - - 可串行性是基于“相似性”概念的正规可串行性的扩展。相似性概念是指在 盟中科技大学博士学位论文 时 日j 和精确性上有微略差别的数据可以彼此替换地作为事务的读数据。“相似”内在 地依赖于应用的概念，不同的事务对同样的数据对象可以有不同的相似性要求，两 个值有多大的“微细差别”才能算相似，应依特定的应用而定。“相似”是一种二元 关系，它是自反的、对称的，但不一定是可传递的m 1 。 基于语义的并发控制 可串行化不是维护逻辑一致性的唯一方法，还可以依据事务在数据库中的操作 语义将事务分类，使用兼容集而非可串行化作为正确性标准。在r h o d ei s l a n d 大学 开发的r t s o r a c ( r e a l t i m es e m a n t i co b j e c t sa n dc o n s t r a i n t sm o d e l ) 系统中使 用了基于语义的并发控制技术。”1 。 ( 8 ) 评价并发控制协议性能的标准不是反应时间和系统吞吐率，而是系统的成 功率m “。 两段锁协议是经典的传统数据库系统的并发控制协议，对于实时数据库系统， 两段锁需要使用基于优先级的冲突解决机制来保证高优先级事务不被低优先级事务 阻塞。在高优先级机制中，所有解决数据冲突的方法倾向于高优先级事务。当一个 事务以冲突方式申请被另一事务持有的锁时，优先级较低的持有者重启，优先级较 高的申请者被授予锁；如果申请者的优先级低，它等待优先级较高的锁持有者释放 锁。另外，只有当新的读锁申请者的优先级高于所有等待写锁操作时，它才可以加 入一组读锁持有者。该协议被称为2 p l - h p 。 2 p l - w p ( 等待升级) ”制使用优先级继承机制来解决冲突。使用这一策略，当优 先级倒置发生时，持有锁的低优先级事务将以在等待锁的事务中的最高优先级执行， 直到它释放锁。由于优先级的升级，它能够比没有优先级升级时执行得快，这样释 放锁就很快。结果是：高优先级事务的阻塞时间可能降低。 然而，使用2 p l w p ，事务阻塞的时间仍然不确定，因为数据冲突很高时，优先 级继承实际上导致系统中大部分或所有的事务以同一优先级执行。这种情形下， r t d b s 的行为显著她降低到传统的数据库。在”侧中实时并发控制算法的实验性能评 价验证在高的数据冲突的情形下，2 p l w p 的性能降得很快。h u a g ”研究指明综合高 优先级和等待提升机制解决冲突具有较优的性能。它通常使用高优先级策略操作， 华中科技大学博士学位论文 只有锁持有事务接近结束时强迫锁申请事务等待，并且由于等待而出现优先级倒置 时使用优先级继承。 优先级顶是解决优先级倒置的另一种方法。集成r t d b s 中的优先级顶和封锁机 制产生了2 p l - p c ”。这种机制对于硬实时环境很有前途，因为它阻止死锁形成并且 严格限制了优先级倒置产生的事务阻塞时间。然而，这种机制需要被每一事务存取 的数据对象的优先级知识。这种情形在许多数据库应用中不适用，因为在很多情形 下，事务执行是数据依赖的，从并发度的角度来说，这一机制很保守。 在“”中，提出了一种实时锁协议，该协议使用上锁和动态调整串行化顺序来解 决优先级冲突。串行化顺序调接的基本思想是推迟事务之间最后的串行化顺序，有 利于高优先级事务动态调整临时性的串行化顺序，这种机制能防止因事务的优先级 顺序和串行化顺序不匹配而导致的阻塞和天折。在r t l 中，为了实现串行化顺序的 动态调整，事