（计算机软件与理论专业论文）实时数据处理事务调度与控制研究.pdf

中国科学技术大学硕士论文 实时数据处理事务调度与控制研究 摘要 在现实世界中，有许多应用需要对数据“定时”存取和对“短暂有效”数据进 行存取，如军事、工业自动化及控制系统、工厂测试与质量保证设备、金融领域、 移动设备、航空航天以及互联网和证券等领域。这些实时应用的数据处理具有种种 有别于传统处理的特性，使得传统的数据库系统不再胜任，而必须借助与其本质上 有很大不同的实时数据库。 进行实时数据处理的实时事务是实时数据库系统的一个核心部分，实时事务的 正确性不仅依赖于计算的逻辑结果，还依赖于结果产生的时间，即任务的时间限制 ( 一般显式的表示为截止期) 。实时事务的这些特性使得传统事务管理器不再适合实 时事务，而是需要新的考虑和设计。 实时事务模型是整个事务处理的基础。对应用性能有着至关重要的影响，为此 本文提出了一种适合实时事务特征，具有较强开放性的柔性事务模型开放协同 层次事务模型o c h t m 。该模型中事务具有层次结构，能够满足愈来愈复杂的实时 应用，同时也能较好的支持传统实时事务，具有较好的开放性和扩展能力。模型同 时给出了o c h t m 事务的状态集、状态转换以及事务恢复策略。在该模型基础上。 本文对实时事务的调度进行了研究，提出了双截止期双优先级的优先级分派方法和 基于该优先级分派方法的定时调度策略；这些方法和策略在现有技术的基础上，深 入考虑实时事务的需求和语义，能够得到更高的效率。为了从并发控制层次上支持 事务协作，利用事务和数据语义进一步提高并发度，提出了新的语义多版本并发方 法s m v c c 。s m v c c 针对三类不同事务，利用它们对不同实时数据进行不同处理的 特点，采用了不同的并发策略；与传统的并发控制方法相比，进一步提高了事务并 发度。 最后对实时事务管理器原型设计和实现的相关问题进行了初步探索，提出了系 统结构设计，给出了部分实现的数据结构和方法。 关键词：实时数据库实时事务事务模型调度并发控制 中国科学技术大学硕士论文实时数据处理事务调度与控翩研究 a b s t r a c t t h e r ea r en e e d sf o rr e a l t i m ea c c e s sa n dt e m p o r a r yv a l i dd a t aa c c e s si na l m o s te v e r y f i e l d si nt h ew o r l ds u c h 镐m i l i t a r yf o r e e s , a a t o m a t i z a t i o na n da u t oc o n t r o li ni n d u s t r y , q u a l i t y t e s t i n g i n f a c t o r i e s ，f i n a n c ea r e a s ，m o b i l ee q u i p m e n t s ，a e r o n a u t i c sa n d a s t r o n a u t i c s ，i n t e r n e ta n ds t o c km a r k e t s t h ed e a l i n go ft e a it i m e d a t ah a sal o to f s p e c i a l i t i e sw h i c ha r ed i f i e r e n tf r o mt r a d i t i o n a lm e t h o d s a n dt h et m d i t i o n a ld a t a b a s e s 3 7 s t e mc a nn o ta f r o r di ta n ym o r e s ow et a mt ot h er e a l t i m ed a t a b a s e sw h i c hh a v e e s s e n t i a ld i f f e r e n tp r o p e r t i e s r e a l t i m et r a n s a c t i o n sd e a l i n gw i t hr e a l t i m ed a t ai so n eo ft h em a i np a r t so f r e a l t i m ed a t a b a s es y s t e m 。t h ec o r r e c t n e s so ft h er e s u l t si sn o to n l yd e p e n d e n to nt h e l o g i c a lr e s u l to fc o m p u t i n g ，b u ta l s oo nt h et i m ew h i c hi su s u a l l yd e n o t e db yd e a d l i n e w h e nt h er e s u l t sc o m eo u t a l lt h en e e d sf o rr e a l - t i m et r a n s a c t i o n sm a k et r a d i t i o n a i t r a n s a c t i o nm a n a g e ru n f i ta n y m o r e ，s ow ec a l lo nn e wm e t h o df o rm a n a g e ra r c h i t e c u t u r e d e s i g n b e c a u s er e a l - t i m et r a n s a c t i o nm o d e li si m p o r t a n tt or e a lt i m ea p p l i c a t i o n s ，w eb r i n g f o r w a r dan e wo n ec a l l e do p e nc o o p e r a t i v eh i e r a r c h yt r a n s a c t i o nm o d e l ( o c h t m ) t h i sm o d e li so p e na n df l e x i b l ea c c o r d i n gt or e a l - t i m et r a n s a c t i o nc h a r a c t e r i s t i c s a n di t h a sh i e r a r c h i c a ls t r u c t u r et om e e tt h er e a lt i m ea p p l i c a t i o n sw h i c ha r em o r ea n dm o r e c o m p l i c a t e d i ta l s oc a ns u p p o r tt r a d i t i o n a lr e a l - t i m et r a n s a c t i o n sw e l l w ea l s op r o v i d e t h et r a n s a n c t i o ns t a t e s ，t h es t a t e s c o n v e r s i o na n dr e c o v e r ym e t h o do f t h et r a n s a c t i o n si n o c h t m b a s e do no c h t m ，w ep r e s e n t e dan e wp r i o r i t ym e t h o dc a l l e dt w op r i o r i t i e s w i t ht w od e a d l i n e sa n dan e wt i m i n gs c h e d u l i n gm e t h o db a s e do nt h a t ，t h e yg e tm o r e e f f i c i e n c yb e c a u s et h e yc o n s i d e rb o t ht h eg o o d n e s so fo l dp o l i c i e sa n dt r a n s a c t i o n s s e m a n t i c s w ea l s op r o v i d ean e wc o n c u r r e n c ym e t h o dc a l l e ds e m a n t i cm u l t i 、，e r s i o n c o n c u r r e n c yc o n t r o lp r o t o c o lw h i c hd e a l t h r e ed i f i r e r e n tk i n d so ft r a n s a c t i o n sw i t h d i f f e r e n tp o l i c i e s s m v c ca l s og e t sm o r ee f f i c i e n c yt h a np r e v i o u sp r o t o c o l s i nt h ee n dw ed i s c u s st h ef i r s t - s t e pd e s i g ni m p l e m e n t a t i o no ft h er e a l - t i m e t r a n s a c t i o nm a n a g e r w ef i r s tp u tf o r w a r ds o m ea r c h i t e c t u r a ld e s i g n a n dt h e np r o v i d e s o m ed a t as t r u c t u r ea n ds y s t e mm e t h o d s k e y w o r d s ：r e a lt i m ed a t a b a s e ，r e a lt i m et r a n s a c t i o n ，t r a n s a c t i o nm o d e l ，s 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 中国科学技术大学硕士论文实时数据处理事务调度与拄利研究 致谢 三年的研究生牛活即将结束，回顾在中国科学技术大学近七年的牛活和学习， 我感触良多。在这里，我亲身感受到教授老师工作的辛勤、学识的渊博、品格的崇 高；在这里，我结识了诸多的同学朋友，从他们身上得到很多帮助和支持：在这里， 我有很多值得纪念的回忆，许多难以忘记的情景对于这一切我无法用片言支语 表达，因此只有在论文完成之际，向这七年来关心和帮助过我的老师、同学、朋友 表示衷心的感谢，谢谢您们! 首先，我要感谢我尊敬的导师岳丽华教授。岳老师不仅学识渊博、治学严谨、 公而忘私、事必躬亲，而且襟怀宽广、和蔼慈祥、诲人不倦。从岳老师身上，我们 不只学习到专业知识、研究方法，也学习到广泛的社会生活常识，学习到为人处世 的道理原则，所有这些都将影响我，给我极大的精神支持。读研期间，岳老师在各 方面给予了极大的指导和帮助，使我顺利完成了学习和研究工作。值此论文完成之 际，再次向岳老师表示最诚挚的感谢。 其次，我要感谢金培权老师和龚育昌教授，他们给予了我很大的指导和帮助。 金培权老师的才能和品格使我感受颇深，从他身上我们获益良多。龚老师渊博的学 识、敏锐的洞察力和果断的风格给我很深的印象。相信老师们树立的优秀形象，对 我今后的日子将产生深远影响。 我要特别感谢我的本科班主任于天顺老师和芦建平老师，他们一直给予我各方 面细心的关怀和帮助。 还要感谢项目组的周英华，刘彬，魏晶晶，陈安等同学。和他们的工作和生活 非常愉快，同时要感谢实验室的杨晓宇，杨洋，刘晓红，王强，任明雷，李同钧， 李航，冯朝阳，薄秋慧，韦鹏，翟小栋，陈浩然，张驭，蔡荣峰，傅宜牟，刘沾沾， 田明辉，向小岩，刘晓沐，张奇，李旭等同学，和他们在一起的日子值得回忆。 感谢p b 9 s l l 的全体同学，感谢他们给予的帮助和支持认识他们是我一生的财 富。 感谢s a 0 2 0 1 l 的全体同学，认识他们我感到十分荣幸。 感谢中国科学技术大学，这里有我许多的梦想和回忆。 最后将我最深的谢意献给父母、弟弟和亲人。是他们的亲情之爱和忘我牺牲使 我能够顺利修满学业，完成这篇论文。 中国科学技术大学硕士论文实时数据处理事务调度与控制研究 1 1 引言 第一章绪论 现实世界中，有许多应用包含了对数据的“定时”存取和对“短暂有效”数据的存取，如 军事、工业自动化及控制系统、工厂测试与质量保证设备、金融领域、移动设备、汽车电子、 医疗设备、航空航天以及互联网、通信、证券和科学研究等等。这些应用一方面需要维护大量 共享数据和控制知识另一方砸其应用活动有很强的时间性，要求在一确定的时刻或，和一定的 时间期限内，从外部环境采集数据、按彼此间的联系存取并处理采集的数据，再及时作出响应 同时，他们所处理的数据往往是“短暂”的，即只在一定的时间范围内有效，过时则不再有意 义，所以这种应用同时需要数据库技术和实时数据处理技术但传统的数据库系统旨在处理永 久性数据，其设计与开发主要强调维护数据的完整性，一致性，根本不考虑与数据及其处理相 关联的定时限制，从而不能满足这类应用的需求；而传统的实时系统不能对数据进行高效和结 构化的管理，不能适应这些对数据的完整性、一致性要求严格且数据量火的系统。在这种情况 下，实时数据库系统应运而生。 实时数据库系统r t d b s ( r e a l - t i m ed a t a b a s es y s t e m ) 是数据和事务都有定时特性或者定时 限制的数据库系统。其数据的正确性不仅依赖于逻辑结果( 内部一致性) ，而且依赖于逻辑结果 产生的时间。人们已经对r t d b s 进行了大量的研究，包括实时数据模型及其特征、实时事务模 型及其特征、事务调度以及并发控制协议等。 对实时事务的研究是这些研究中最核心的部分之一，从上个世纪八十年代开始，人们就已 经对实时事务进行了大量的研究，取得了一定的成果。这些成果包括实时事务模型及其特征、 事务的定时特性。实时事务调度及并发控制等等。 一方面，现有实时事务研究取得了很大成果提出了一些实时事务模型以及调度和并发控 制方法：另外，目前的实时事务研究局限于传统实时事务的处理，很少考虑实时数据处理事务 的深层次语义和新出现的复杂实时事务需求：再者，无论这些研究成果在支持它们的初始目标 系统时多么成功，也只是反映了在竞争、合作的环境中可能出现的相关关系的某些方面，因此 对实时数据处理事务的研究需要进一步深化。本文在现有研究的基础上，通过对实时事务语义 的挖掘，对新出现的实时需求的分析，进一步系统讨论了实时事务的相关问题。 本章下面几个小节中首先概述实时事务以及实时事务研究的现状，然后简要介绍论文所做 工作，包括实时事务模型、实时事务调度、控制方法以及原型系统设计等几个方而。 1 2 研究现状 近年来，r t d b s 已发展为现代数据库研究的主要方向之一，受到了数据库界和实时系统界 的极大关注。这主要因为数据库的应用正从传统领域向新的领域扩展，如：数据通信、电力调 中田科学技术大学硕士论文实时数据处理事务谓度与控制研究 度、交通控制、实时仿真等。实时数据库系统( r t d b s ) 所需要的一系列的概念、理论、技术、 方法和机制如：数据模型及其语言、数据库的结构与组织、事务的模型与特性、截止时间及其 软硬特性、事务的优先级分派、调度和并发控制协议与算法、数据和事务特性的语义及其与一 致性等等，目前都受到相关研究领域的关注【1 ，3 ，4 】 在实时事务研究方面已经提出了诸如嵌套事务模型、替代事务集、放松一致性等诸多概 念【1 4 ，1 0 】：事务优先级的分派则已经有最早放行最优先( e r f ) 、截止期最早最优先( e d f ) 、 可达截止期最早最优先( e f d f ) 、空余时间最短最优先( l s f ) 及价值最高最优先( h v f ) 等方 法调度方法如静态表驱动调度、优先级驱动可抢占调度、动态计划式调度、动态尽力式调度 等f 1 ，2 ，2 3 。此外，目前r t d b s 的并发控制研究也取得了大量的研究成果这些成果主要分为 两类：一类是由传统并发控制技术扩展改进而来，如2 p l h p , o c c f v 等另一类是基于事务 对象语义的并发控制方法这类方法利用实时事务的共享数据相关性、行为相关性以及时间相 关性等语义，对不同事务，对象进行专门分类和处理，数据满足放松一致性就认为其正确。如基 于锁相容关系矩阵的并发控制方法等 尽管实时数据库和实时事务的研究或产品取得了巨大成果，它仍然还处于发展阶段有关 的系统理论与技术离成熟还较远。比如，这些成果大多局限于传统实时需求，缺乏通用性普适 性。不能适应新的实时领域。因此对于实时数据库，特别是实时事务，许多方面还有待研究与 完善，如成熟的实时时限和事务行为的描述语言、通用的实时事务模型、适合复杂新型应用的 事务调度机制、并发控制机制等。 1 3 本论文的工作 论文中，我们深入讨论了实时事务的相关问题，并在现有研究基础上提出了额的实时事务 模型、优先级分派方法、事务调度策略和并发控制方法系统的对实时事务处理的各个环节进 行了研究探讨。 本文的主要贡献是：( 1 ) 系统的对实时事务处理进行了研究，针对事务处理的各个环节提 出了相应的处理机制或思路；( 2 ) 提出了一种适合实时事务处理的柔性事务模型开放协同层 次事务模型o c h t m 。并针对该模型的特点对实时事务的恢复机制进行了简要的讨论；( 3 ) 在 o c h t m 模型的基础上提出了双截止期双优先级的概念，进而对定时事务调度策略进行了讨论； ( 4 ) 提出了实时语义多版本并发控制协议s m v c c ，为事务协作提供了并发机制上的控制策略。 1 3 1 实时数据库管理系统的体系结构 图1 1 是实时数据库管理系统的体系结构图，实时事务管理器包括图中的实时事务管理模 块和恢复机制模块( 阴影部分) 。可以看出实时事务管理主要是事务的“识时”调度和“识时” 并发控制，以及相应的事务恢复机制。实时事务的管理和控制离不开其他模块的支持与配合。 2 中国科学技术大学硕士论文实时数据处理事务调度与控制研究 各种实时应用 、l 曩l l “识时”调庸糍h 黼实时事务管理潮#识时”并发控制i t 实时资源管理 i c p u 翻tb + 实时数据管理 一缓冲区管理i 数据操作 巨l 蘸 恢复机制雾辫：l 存储数据管理 上t 实时l ，o 调度 图1 1 实时数据库的体系结构 1 3 2 开放协同层次事务模型o c h t m 这一部分介绍我们提出的实时事务模型一一开放协同层次事务模型o c h t m ( o p e n c o o p e r a t i v eh i e r a r c h yt r a n s a c t i o nm o d e l ) 。 事务模型规定了事务的结构、启动、结束、与外部环境交互等方面的处理规则。随着大量 复杂实时应用的出现，传统的实时事务模型越来越变得不再胜任，为此需要提出新的高级事务 模型。o c h t m 事务模型正是在这种情况下，充分考虑实时事务处理需求，在现有研究成果的 基础上提出的。o c h t m 具有开放的高级事务结构和可扩展的规则，适应更广泛的实时应用， 可以根据需要进行剪裁，从而实现满足应用的事务处理方式。 最后，这部分还讨论了事务恢复的策略方法，从补偿恢复和日志恢复两个方面进行了阐述 提供了适合该模型恢复的策略。 1 3 3 实时事务调度 实时数据库系统可以说就是一个用来处理具有定时限制的工作负载的事务处理系统，系统 的主要目标是要满足事务的截止时间，事务处理的主要工作都围绕这个目标进行。这些工作主 要包括事务的调度即针对多个事务的c p u 的调度，以及与之紧密相关的在多个并发运行事务之 中国科学技术大学硕士论文 实时数据处理事务调度与控制研究 问的数据、i o 及内存等资源的调度。仔细的调度这些资源的使用，对r t d b s 的功能和性能有 极大的影响。 这一部分主要讨论c p u 的调度及其相关问题，包括双截止期双优先级的优先级分派和基于 这种优先级分派的定时调度方式。 l 3 4 语义多版本并发控制协议s m v c c 对于实时数据资源的调度主要通过并发控制实现。这一部分将介绍语义多版本并发控制协 议s m v c c ( s e m a n t i cm u l f i v e r s i o nc o n c u r r e n c yc o n t r 0 1 ) ，该方法将多版本并发控制协议和基于 语义方法结合，在并发控制层次上提供事务协作的机制，并在其中提出了语义相容表的概念和 对事务进行分类处理的思想。 1 3 5 原型系统设计和实现初探 在对实时事务处理的几个主要方面进行研究后，我们就可以开始设计并实现实时事务管理 器了。实时事务管理器的实现比较复杂，本文从最基本的问题开始着手，初步设计了一个原型 系统，并且在p o s t g r s q l 上作了部分实现的探索工作。这一部分将讨论相关问题。 1 4 章节安排 本论文章节安捧如下： 第一章绪论。简要介绍实时数据库和实时事务的概念、特点和当前实时事务处理技术的现 状，最后概述本文完成的工作。 第= 章实时数据库和事务处理。对实时数据库和实时事务的相关问题进行了综述性讨论 第三章开放协同层次事务模型o c i - i t m 。这一章详细介绍实时事务模型o c h t m 的结构， 状态、状态转换及恢复等相关问题。 第四章实时事务调度。本章首先讨论了现有的优先级分派方法和调度策略，介绍了影响调 度的几个因素，然后提出了新的优先级分派方法和调度策略。 第五章语义多版本并发控制协议s m v c c 。对实时事务的语义进行了深入的挖掘，以此为 基础提出了支持事务协作的语义多版本并发控制协议s m v c c ，并对其正确性和可行性进行了 证明。 第六章原型系统设计和实现初探。根据前面几章讨论的关键技术，对原型系统的实现进行 了讨论提出了相应的实时事务管理器系统设计思路，给出了初步实现的部分数据结构和方法。 第七章结束语总结本论文的研究工作，并提出下步的工作目标。 最后是参考文献和读研期间发表的论文。 中国科学技术大学硕士论文实时数据处理事务调度与控制研究 第二章实时数据库和事务处理 2 1 实时数据库 数据库与实时系统的结合导致了实时数据库系统的产生，它集成两者的概念与要求以同时 处理实时性和数据一致性；但它并非两者概念、机构、工具等的简单集成需要对一系列问题 进行研究和决策。 2 1 1 实时数据库与时间 1 ) 数据与时间相关。按照与之相关的时阔性质不同可分为两类f l ，3 】： 数据本身就是时间即从“时间域”中取值，如“日期”，称为“用户定义的时间”也就是 用户自己知道，而系统并不知道它是时间，系统将毫无区别地把它像其他数据一样处理。 数据的值随时间而变化。数据库中的数据是对其所服务的“现实世界”中对象状态的描述， 对象状态发生变化则引起数据库中相应数据值的变化，因而与数据值变化相联的时间可以是现 实对象状态的实际时间，称为“真实”或“事件”时间( 现实对象状态变化的事件发生时闻) ， 也可以是将现实对象变化的状态记录到数据库。即数据库中相应数据值变化的时间。称为”事 务时间”( 任何对数据库的操作都必须通过一个事务进行) 。实时数据的导出数据也是实时数据， 与之相联的时间自然是事务时间。 2 ) 实时事务有定时限制典型的就是其“截止时间”。 对于r t d b ，其结果产生的时间与结果本身一样重要，一般只允许事务存取“有效”的数 据，事务必须维护数据库中数据的“事件一致性”。另外，外部环境( 现实世界) 的反应时间要 求也给事务施以定时限制。所以r t d b 系统要提供维护有效性和事务及时性的设施。 2 1 2 实时数据库的特征 1 ) r t d b 的数据特征 在r t d b 中，数据随外部环境状态的变化而快速变化，其值只在一定的时间内是“流行” 的，过时就无效了，故系统除了维护数据库内部状态( 数据值) 的正确性、相容性外，还必须 同时维护内部状态与外部环境实际状态的一致性以及数据用来决荒或推导额数据时在时间上 的相互一致性【1 】。 r t d b 中的一个数据对象d 由三个分量组成( d 。d 。d c “) 它们分别为d 的当前值、采样 时间、外部有效期( 外部现实对象状态变化的时间间隔) ，有效期即自d 。算起d v 有效的时b j 长 中国科学技术大学硕士论文实时数据处理事务调度与控制研究 度。对于r t d b 中的每一d ，有内部一致性、外部一致性和相互一致性特征。 内部一致性d v 满足预先定义的数据库内部状态的完整性和一致性限制。这就是传统意义 下的数据正确性。 外部一致性设t c 为当前或检测时间，当且仅当( t c d 。) d 。则说d 足外部一致的， 即d 。和对应的外部现实对象的状态是一样的。 相互一致性用来决策或导出新数据的一组相关数据称为一个相互一致集记为r 。其中 的数据必须尽可能地在一4 个允许的公共时间期内被采取( 或导出) 。这个公共时间期就称为r 的 相互有效期记为r “，对于r 中的任两个数据d 和d ：有l d t 。一d u r 则说rt f t 的数据 是相互一致的。 外部一致性和相互一致性都是关于时间的，故统称时间一致性。既是内部一致又是时间一 致的数据才是正确的。 2 ) r t d b 的事务特征 由于实时任务往往具有内部结构和相互之间的联系传统的“原子的、平淡的数据库操作 序列”的事务概念及模型对实时事务不适合【l 】。r t d b 事务表现出了许多不同的特征，这里只 给出其标志性特征定时性其他特性后面将具体讨论。 定时可以是绝对、相对或周期时间。r t d b 的定时性方面由数据的时间一致性引起，此 时它往往取周期或定期性限制的形式，如“每5 秒取样一次”、“7 ：0 0 启动机器人”等；定 时性的另一根源是对现实世界施加于系统的反应时间的要求，这时它典型地取施加于非周期事 务的截止时间限制的形式，如“若温度达到1 0 0 0 度，则在5 秒内加冷却剂到反应堆” 定时性包含两方面的含义： 定时限制即事务的执行有显式的时限，如指定的开始时间、截止时闻等，它要求r t d b 必 须有时问处理机制。 定时正确性即事务能按指定的时间要求正确执行它要求权衡定时限制与数据一致性要 求等多方面因素提供合适的调度与并发控制算法。 2 1 3 实时数据库系统的主要技术 1 ) 实时事务模型 传统的原子事务模型已不适用，必须使用复杂事务模型。如嵌套、分裂合并、合作、通信 等事务模型 1 ，2 ，8 】。因此，实时事务的结构复杂，事务之间有多种交互行动和同步，存在结构、 数据、行为、时间上的相关性以及在执行方面的依赖性，具体讨论见第2 节。 2 )实时事务的处理 r t d b 巾的事务有多种定时限制。其中最典型的是事务截l i = 期，系统必须能让截止期更早 或更紧急的事务较早地执行，换句话说，就是能控制事务的执行顺序。所以，又需要基于截止 期和紧迫度来标明事务的优先级，然后按优先级进行事务调度。 另一方面，对于r t d b 事务，传统的可串行化并发控制过严它们“宁愿要部分正确而及 时的数据。而不愿要绝对正确但过时的数据”，故应允许“放松的可串行化”或“暂缓可串行化” 并发控制。于是需要开发新的并发控制正确性的概念、标准和实现技术f l 】。 3 ) 数据存储与缓冲区管理 1 】 传统的磁盘数据库的操作是受i o 限制的。其i o 的时间延迟及其不确定性对实时事务足 6 中国科学技术大学硕士论文实时数据处理事务调度与控制研究 难以接受的，因此，r t d b 中数据存储的一个主要问题就是如何消除这种延迟及其不确定性， 这通常通过底层的“内存数据库”支持因而内存缓冲区的管理就显得更为重要。 4 ) 恢复 在r t d b 中，恢复显得更为复杂。这是因为 1 ，3 】： 恢复过程影响处于活跃状态的事务，使某些事务超过截止期，这对硬实时事务足不能 接受的。 r t d b 中的数据不一定总是永久的，为了保证实时限制的满足，也不一定是一致和绝 对正确的，而有的是短暂的，有的是暂时不一致或非绝对正( 准) 确的。 有的事务是“不可逆”的，所以，传统的还原重启动是无意义的，可能要用“补偿”、 “替代”事务。 因此，必须开发新的恢复技术与机制，考虑到时间与资源两者的可用性，以确定最佳恢复 时机与策略，而不致太伤害事务实时性。 2 2 实时事务处理 事务是物理和抽象的应用状态下操作的集合事务的起始点和结束点均是应用的稳定状 态。传统事务的关键是维护所处理数据的一致性，保证系统的容错存储和容错处理，即保证a c i d 特性。a c i d 特性即是指原子性( a t o m i c i t y ) 、一致性( c o n s i s t e n c y ) 、隔离性( i s o l a t i o n ) 和永久 性( d u r a b i l i t y ) 。原子性是指一个事务对状态的改变是原子的，要么不发生，要么全部发生这 些改变包括数据库的改变、消息以及对转换器的操作。一致性指一个事务是对状态的一个正确 改变，作为一组操作没有违反任何与状态相关的完整性约束；这要求事务足一个正确的程序。 隔离性则针对并发执行事务而言，要求他们看起来是单个串行执行的。永久性要求一旦一个事 务成功完成( 提交) ，它对状态的改变不会受到其他失败的影响。 实时事务和传统事务在概念和技术上有着重大区别，这决定了实时事务的处理技术需要另 外研究开发。下面就实时事务的特性进行简要的讨论。 1 实时数据处理事务与传统事务 首先，传统事务强调数据的绝对完整性和一致性，要求满足严格的a c i d 特性( 即原子性、 一致性、隔离性、永久性) 。而对于实时事务，如前所述，其正确性与时间相关，因此为了满足 时问限制可以放松正确性标准。 其次，由于实时环境的特殊性，事务执行时可查看另一执行事务的操作结果，即具有可见 性。 最后，为了满足时间限制，实时数据库要有对事务执行时间进行预报的能力。 因此，在实时应用环境下事务必须考虑【l ，8 】 1 ) 传统的平坦原子事务应不适用要求“复杂事务”。 2 )事务可以合作、协调而并发执行，即要求事务间的直接交互与通信。 3 1及时性和正确性是实时事务同等重要的目标，这两者需要折衷，有时宁愿耍部分正确 而及时的数据，而不愿耍绝对正确但过时的数据。 4 )恢复的处理，参见前节的讨论。 2 实时事务的特性 前面的讨论以及现有研究都指出传统的事务概念对实时事务不合适，因为实时事务表现了 ，7 中国科学技术大学硕士论文实时敦据处理事务调度与控制研究 许多不同于传统a c i d 的特性 1 】： 1 )结构复杂性。事务内部与事务之间可能存在着复杂的相互关系和结构。 2 )功能替代性。为了满足实时性，一个任务有时可以通过不同途径来实现，一个应用就 是一个事务，一个任务则可看成是一组功能等价的子事务。成为该任务的替代集。即使某些 子事务失败了，事务仍能顺利提交极大地保证了事务不失败。 3 )结果补偿性。一个子事务提交后，可能改变现实世界的状态，如果发现这是不允许的， 那么需要进行“还原”，但是这不是传统事务意义下的“还原”，需要一种补偿性的动作来抵 消它的影响。 4 ) 语义相关性。实时事务之间存在着备种关系，包括事务结构关系、数据与通信关系、 事务时限( 时间) 关系等，这些关系带来事务问的各种相关性 5 )执行依赖性。实时事务的复杂结构关系和语义相关性引起它们之间执行的依赖性，如 执行先后和提交先后关系等。 3 实时事务的分类 事务根据某一方面的特征可以划分成不同的集合，下面是一些典型的分类【1 】。 ( 1 ) 按使用数据的方式分类，可以分为 a )只写事务收集关于现实世界的信息并写入数据库。 b )只读事务i 卖取数据库中的数据值并设置执行控制部件的参数。 c )更新事务基于现有数据值导出新的数据值可能既读叉写。 ( 2 ) 按关键性分类 a )硬实时事务( h a r dr e a l - t i m et r a n s a c t i o n s ) 超过截止期会导致恶果它对应于安 全危急佳活动。 b ) 软实时事务( s o f tr e a l - f i m e t r a n s a c t i o n s ) 超过截止期仍有一定的价值，但不断 下降，直到某一时刻( 最终有效时间) 其价值降到零。 c )固实时事务( f i r mr e a l t i m et r a n s a c t i o n s ) 一旦到达截止时问，价值立即降到零。 超过截止期的事务称为超时( t a r d y ) 事务。 ( 3 ) 按功能分类 a )数据接收事务。数据接收事务记录现实世界的信息或事件，它是短暂的、周期性 的，且是需要被立即执行的硬实时事务。 ”数据处理事务。控制事务引起现实世界中有关活动的执行通常也是短暂的硬实 时事务。 c )控制事务。数据处理事务的处理类似于传统数据库中的事务。 ( 4 ) 按到达时间分类 a 1 周期事务以一定的周期循环的到达和执行。 b )非同勰事务由外部事件或内部事件动态驱动。 c )零星事务偶尔的一次性执行。它们是非预先安排的如通常的即席查询这 类事务通常是实时数据库中的非实时事务。 2 3 小结 上面我们讨论了实时数据库和事务处理的相关问题，包括实时数据库与时间的关系、实时 中国科学技术大学硕士论文实时数据处理事务调度与控制研究 数据库的特征、实时数据库的主要技术、事务处理的概念、实时事务的特征等方面。这些内容 是今后几章讨论的基础 实时数据库的实时体现在两个方面：数据的时间特征和事务的定时限制。实时数据库不仅 仅是实时系统和数据库的简单组合，而是两者的有机统一面临着新的问题。人们已经对实时 数据库进行了大量的研究，主要集中在数据模型、事务处理、缓冲和i o 管理、恢复等方面。 但是目前的研究还处于发展阶段，有关的系统理论和技术离成熟还很远，许多方面还有待研究 与开发本论文试图从我们的研究工作中探索实时数据库的相关技术，主要包括实时事务的处 理技术包括事务模型、调度和并发控制策略等方面。 9 ， 中国科学技术大学硕士论文 实时数据处理事务调度与控制研究 第三章开放协同层次事务模型o c h t m 3 1 引言 传统的事务又被称为“扁平事务”因为应用程序的控制只有一层，由b e g r n t r a n s a c t l 0 n 和e n dn u n s a c t i o n 将所有的操作括起来没有复杂的结构。扁平事务的 限制是不能提交或中止事务的某一部分，或分几个步骤提交结果。这种事务结构不能适应高级 应用如计算机支持的协同工作c s c w 、c a d c a m 等更不适合为了满足时间限制而必须放松 数据一致性的实时事务要求。目前人们已经提出了多种高级事务模型，如带保存点的扁平事务 模型、链事务模型、多级别事务模型以及嵌套事务模型等【l ，8 ，1 0 】。 对实时事务的处理已经有比较多的研究；这些研究基于这样的情况，即跟传统的事务要求 类似，大多的实时事务执行严格遵循可串行化的标准而在实时数据库系统中，应尽量满足实 时事务定时限制( 典型地为截止期) 宁愿要部分正确而及时的数据，而不愿意要完全正确但已过 时的信息。另外，在实时数据库中，数据库中的数据是外部环境在逻辑世界的映射，逻辑世界 所监视的外部环境往往频繁地发生改变，由于把周期的采样值写入数据库本身就存在时问上的 延迟，写入数据库中的数据可能已经不是外部环境的精确描述所以严格地说。实时数据库从 本质上说就不能实现绝对一致。最后，数据库中时态对象的外部一致性本身也不能通过事务的 可串行化执行来实现，它只能通过时态对象的及时更新而得到。由于系统的不一致能够通过时 态对象的下一次采样值写入数据库而得到恢复因而实时数据库巾数据不一致的影响相对传统 数据库而言也小得多。因此，根据上述实时事务的特点和要求人们提出了不同的放松传统可 串行化的正确性标准【5 】，如准一致性、语义可串性等，以提高系统对事务的实时响应能力。 目前所提出的事务模型基本上都没有考虑到放松可串行化带来的事务结构上的影响，因此 从事务结构上来看。难以有效的满足实时事务的需求。而且，一个在某个应用领域保证了正确 性的扩展事务模型，在另一个领域却可能无法保证正确性，在某个应用领域给出的限制在另一 个领域却可能不需要。例如，s a g a s 模型在一些数据库领域就无法保证正确性 8 】而嵌套模型 不允许共享未提交数据的限制在c a d c a m 领域r r l 将极大降低系统的性能。嵌套事务模型是目 前实时数据库领域中被广泛提及的事务模型，但是对数据量大，运行时间长的实时事务来讲。 不允许共享未提交数据将极大地限制实时事务的并发度。再者实时数据库具有较强的专用性， 嵌套事务模型固定而受限的结构和处理机制不能适应广泛的不断变化的实时事务需求。 针对上述问题，本文提出一种新的扩展了传统事务a c i d 特性的事务模型开放协同层 次事务模型o c h t m ，它允许事务的执行满足数据库放松一致性而不一定要求完全一致性，比 如数据d 的任意两个状态的距离小于系统预先确定的阀值，那么d 上的计算和处理也是可以 接受的这就是放松的数据库一致性。同时o c h l m 具有柔性结构和扩展事务处理机制，能够 适应复杂和高级的应用。此外，该模型具有较强的开放性，很多高级事务模型都可以通过一定 的方式与该模型得到统1 。下面详细讨论o c h t m 的概念和相关机制。 1 0 中国科学技术大学硕士论文 实时数据处理事务调度与控制研究 3 2 相关概念 在o c h t m 模型里，一个实时事务就是一个具有时间限制的应用它由若干个任务组成 任务包含了一组功能等价的子事务成员，该组成员构成任务的替代事务集同时，子事务还可 以拥有子事务，从而形成层次结构。实时事务的结构如图3 1 所示，每一个“成员”都是一个 子事务。当实时事务执行时，从每一个替代事务集中选择一个最合适的子事务组成执行事务， 当某一个子事务失败时，从该子事务所在的替代事务集剩下的子事务中选择一个最适当的重新 执行。只要所有替代事务集中各有一个子事务执行成功那么实时事务就能提交，与没有替代 事务相比提高了事务的提交率。 定义3 1 任务定义为一定功能的子事务或操作序列的集合。 t a s k i i s h | l j m ) m 为任务i 的替代事务集中子事务的个数。且 s t ”zs t r a x s t r a x ；t i f o p l 其中s t r a x 是嵌套子事务，t 代表实时事务，o p 是基本的数据库操作( i n s e r t ，u p d a t e 。d e l e t e 等) 、事务操作( b e g i nt r a n s a c t i o n ，a b o r t ，c o m m i t ，e n dt r a n s a c t i o n 等) 或相关的计算操作。有 s t i k 营s t i l ( 1 k s m ，l 蔓i 茎m ) ，表示替代事务功能等价。 一 任务1 失效 | l i 。；l 、i ；萎i _ i | i ，i 一 睦薹；- i ；：i !i 、j 一一一一一一 ，任务2 失效 匿鋈蒸圈：3 = ：竺兰 目i ；i 蓓攀善誊i i * 7i 一一n 一 慝蔫焉焉焉曩薷曩= _ l _ ：- l 任务失效 巨三三_ i _ _ _ 型兰羔兰兰兰量j 到、j 实时事务t 包括n 个任务 替代事务集 图3 1 实时事务的逻辑结构，一个实时事务t 由n 个任务组成，每一个任务是一组等价的替 代事务集一个任务可以有一个或零个补偿事务替代事务集中的成员同样可以是一 个实时事务。从而形成层次结构 现在的问题是：有些实时事务对外部环境做出即时反应，在它提交之前就有可能启动各种 外部活动。对外部环境产生了影响，当该事务夭折时，无法通过传统事务下的“还原”( u n d o ) 来消除它所产生的影响，而必须由一个称为“补偿”事务的机制来完成“还原”任务。每一个 任务都可能有一个补偿任务，此时原执行任务( 如图3 1 巾的任务1 ) 称为主任务。当主任务的 中国科学技术大学硕士论文 实时数据处理事务调度与控制研究 替代事务集中所有的子事务都不能成功时，必须由补偿事务使该任务安全结束。补偿事务和任 务的关系见图3 1 。 一个实时事务由所有替代事务集中各选出一个子事务组成。这些子事务的一种组合就是该 实时事务的一种可执行结构，称为功能替代。功能替代的组成如图3 2 所示。所有这种结构的 集合就构成该实时事务的功能替代集。 实时 任务i 成员2 往务2 成驺3 i 任务lj 点抽i 7 任务3 成员2 任务1 i 任务芷员2 1 替代_ 事j i 任务i 废艟m l 任务2 ， f 任务2 j 垃员t l 任务2 威员2 l 任务3 i 任务2 成员l l 、f i 任务3 成员i l 任务3 威2 i 任务n 成员i i 任务n 成员2 i 任务n 任务n 成员j 替代掘 图3 2 从替代事务集构建功能替代集 定义3 2 任务集概念体现了替代事务集和实时事务的关系，定义如下： _ 月 t a s k s t a s k s if e t 4e t j - - - - ， f l ( t a s k ，h b t ，) v ( t a s k t 付a ) ，i i n ) 其中t a s k ，是任务i 的替代事务集( 见定义3 1 )