（计算机应用技术专业论文）分布式混合实时数据库事务研究.pdf

南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 摘要 随着计算机网络技术，数据库技术的飞速发展，实时数据库系统( r t d b s ) 的应用领 域也越来越广，如科研、工业、军事、通讯和金融等领域。新的领域应用对r t d b s 的性 能提出了更高的要求。在现实世界中存在大量包含硬实时与非实时、固实时与非实时、 软实时与非实时的混合实时事务，称硬实时、固实时、软实时为真实时，把这类混合实 时事务细分为真实时与非实时两部分，区别对待分开处理就能使事务在满足原有的数据 完整性约束基础上让系统更好地满足实时性时问约束，从而提高系统效率。 本文首先分析研究传统的实时数据库系统及实时事务调度与并发控制协议。具体讨 论了实时数据库系统模型、实时事务特性与分类、基于价值的事务调度、基于准入的事 务调度、动态过载管理；基于锁的并发控制、乐观并发控制、多版本并发控制等并发控 制协议。 接着定义一种含有真实时事务( 硬实时、固实时、软实时) 和非实时两部分的混合实 时事务。给出了混合实时数据库系统模型。讨论分析了混合实时事务价值模型，在传统 实时事务的调度与并发控制协议基础上研究分析了混合实时事务的调度与并发控制。 更进一步，研究分布式混合实时事务的事务模型、分布式混合实时数据库系统架构、 分布式混合实时事务价值模型、分布式混合实时事务的准入控制机制、分布式混合实时 事务的提交协议与并发控制协议。其中重点研究讨论了分布式混合实时事务的准入控制 机制，综合考虑分布式混合实时事务的执行需求和价值，达到保留系统资源，有效控制 负载的目的，从而减少被系统接纳执行后又不能满足截止期的事务，提高了分布式混合 实时数据库系统事务处理的成功率和可靠性，使系统收益晟大化。针对分布式混合实时 事务的特点分析研究了2 p l h v 、o p t h v s a c r i f i c e 等并发控制协议。 最后设计了一个分布式混合实时事务仿真测试平台e t p d h r t t p 。详细讨论了 e t p d h r t t p 的体系结构与e t p d h r t t p 的类图和序列图。 本文的研究成果为进一步研究探讨分布式混合实时数据库系统及分布式混合实时 事务的调度与并发控制，以及对流数据库、移动数据库、微小型数据库等相关数据库技 术研究提供了良好的基础。 关键词：分布式混合实时数据库系统，混合实时事务，混合实时事务调度，混合实时 并发控制 南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r ka n dd a t a b a s et e c h n o l o g y , r e a l t i m e d a t a b a s e sm a n a g es y s t e m ( r t d b m s ) a p p l i c a t i o na r ew i d e l yu s e di nv a r i o u sa p p l i c a t i o n f i e l d s s u c ha ss c i e n c er e s e a r c h 、i n d u s t r y 、m i l i t a r ya f f a i r s 、c o m m u n i c a t i o na n df i n a n c e 。t h e 1 1 i g hp e r f o r m a n c eo f r t d b m si sb r o u g h tf o r w a r di nn e wa p p l i c a t i o nf i e l d s i nt h er e a lw o r l d t h e r ea r el o t so fh y b r i dr e a l t i m et r a n s a c t i o n s ，w h i c ha r ec o m p o u n d so fh a r dr e a l t i m e t r a n s a c t i o na n dn o n - r e a l - t i m et r a n s a c t i o n f i x e dr e a l t i m et r a n s a c t i o na n dn o n r e a l t i m e t r a n s a c t i o n ，s o f tr e a l t i m et r a n s a c t i o na n dn o n - r e a l - t i m et r a n s a c t i o n ，t h ep a p e rs u g g e s t st h a t t h eh y b r i dr e a l t i m et r a n s a c t i o n sb ed i v i d e di n t o g e n u i n er e a l t i m e ：m a r dr e a l - t i m eo rf i x e d r e a l t i m eo rs o f tr e a l - t i m e ) a n dn o n - r e a l t i m ep a r t sw h i c ha r ed i f f e r e n t l yd i s p o s e d ，i tm a k e s t h es y s t e mm e e td a t ai n t e g r i t yc o n s t r a i n t sa n dt i m i n gc o n s t r a i n s ，s o i m p r o v e ss y s t e m e f f i c i e n c y 。 i n t h i sp a p e r , f i r s t l y , t 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 ma n dr e a l - t i m et r a n s a c t i o n s c h e d u l i n ga n dr e a l t i m ec o n c u r r e n c yc o n t r o lp r o t o c o la r es t u d i e d i td i s c u s s e sr e a l t i m e d a t a b a s es y s t e mm o d e l ，r e a l - t i m et r a n s a c t i o np r o p e r t ya n dc l a s s ，t r a n s a c t i o ns c h e d u l i n gb a s e d o nv a l u e ，t r a n s a c t i o n s c h e d u l i n gb a s e d o n a c c e s s i n g ，d y n a m i c o v e r l o a d m a n a g i n g ； c o n c u r r e n c ec o n t r o lb a s e dl o c k ，o p t i m i s t i cc o n c u r r e n c ec o n t r o l ，m u l t i v e r s i o nc o n c u r r e n c e c o n t r o 】e t c 。 n e x t ，at r a n s a c t i o ni n c l u d i n gg e n u i n er e a l - t i m e ( h a r dr e a l t i m e ，f i x e dr e a l - t i m e ，s o f t r e a l - t i m e ) a n dn o n r e a l t i m ei sp r o p o s e d ，h y b r i dr e a l - t i m ed a t a b a s es y s t e mm o d e li sg i v e n 。 i td i s c u s s e sa n da n a l y z e sd e t a i l e d l yt r a n s a c t i o nv a l u em o d e lo fh y b r i dr e a l t i m et r a n s a c t i o n ， s t u d i e sh y b r i dr e a l - t i m et r a n s a c t i o ns c h e d u l i n ga n dc o n c u r r e n c ec o n t r o lb a s e do nt r a d i t i o n a l r e a l - t i m et r a n s a c t i o ns c h e d u l i n ga n dc o n c u r r e n c ec o n t r o l 。 f u r t h e r m o r e ，i ts t u d i e sd i s t r i b u t e dh y b r i dr e a l - t i m et r a n s a c t i o nm o d e l d i s t r i b u t e dh y b r i d r e a l t i m ed a t a b a s es y s t e mf r a m e w o r k ，d i s t r i b u t e dh y b r i dr e a l t i m et r a n s a c t i o nv a l u em o d e l ， a d m i s s i o nc o n t r o lm e c h a n i s mf o rd i s t r i b u t e dh y b r i dr e a l - t i m et r a n s a c t i o n ，t r a n s a c t i o ns u b m i t p r o t o c o la n dc o n c u r r e n c ec o n t r 0 1p r o t o c o lf o rd i s t r i b u t e dh y r b r i dr e a l t i m et r a n s a c t i o n i t e m p h a s i z e so nr e s e a r c h i n ga d m i s s i o nc o n t r o lm e c h a n i s mf o rd i s t r i b u t e dh y b r i dr e a l - t i m e t r a n s a c t i o n 。 i tc o n s i d e r sb o t l lt h ee x e c u t i n gr e q u i r e m e n ta n dt h ev a l u eo fd i s t r i b u t e dh y b r i d r e a l t i m et r a n s a c t i o n ，i no r d e rt om a x i m i z es y s t e mp r o f i t ，i tr e s e r v e ss y r s t e mr e s o u r c e sa n d c o n t r o l se f f e c t i v e l ys y s t e ml o a d ，b yr e d u c i n gt h en u m b e ro ft r a n s a c t i o n sb e i n ga c c e p t e df o r e x e c u t i o nb n tn o ta b l et oc o m et oi t sd e a d l i n e 2 p l h vo p t - h v - s a c r i f i c ec o n c u r r e n c e c o n t r 0 1a l e a n a l y z e do nd i s t r i b u t e dh y b r i dr e a l t i m et r a n s a c t i o np r o p e r t y 。 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 f i n a l l y , a e m u l a t i o n a lt e s t p l a t f o r m f o rd i s t r i b u t e dh y b r i dr 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 gi sd e s i g n e d 。i ts t u d i e sd e t a i l e d l ye t p - d h r t t sa r c h i t e c t u r e t h em a i nr e s u l t sa c h i e v e di nt h i sp a p e rp r o v i d e st h ef o u n d a t i o nf o rf u r t h e rr e s e a r c ho n d i s t r i b u t e d h y b r i dr e a l t i m e d a t a b a s e s y s t e m ，d i s t r i b u t e dh y b r i d r e a l t i m et r a n s a c t i o n s c h e d u l i n ga n dc o n c u r r e n c ec o n t r o l ，s t r e a m i n gd a t a b a s e ，m o b i l ed a t a b a s e ，s m a l l f o o t p r i n t d b m se t c w d r e nb yc a oc h o n g h u a ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rb a is i x u e k e y w o r d ：d i s t r i b u t e dh y b r i d r e a l t i m ed a t a b l es y s t e m ，i q y b r i dr e a l - t i m e t r a n s a c t i o n ，h y b r i d r e a l - t i m et r a n s a c t i o ns c h e d u l i n g ，h y b r i dr e a l t i m e c o n c u r r e n c y c o n t r o l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得壹墨叁鲎或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示谢意。 学位论文作者签名：苇龟乍 签字日期：炒f 年月7 蝈 学位论文版权使用授权书 本学位论文作者完全了解南昌史学有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权南昌土学可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：前钐争 1 导师签名：白( 一鹰 签字日期：妒年阳h - b 签字日期：7 1 - , ( 年f 月蝈 学位论文作者毕业后去向 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 1 1 背景知识 第一章绪论 现实中的许多应用包含具有时间约束的数据存取，或者对时态数据的存取。例如， 生产过程监控、电话交换系统、网络管理、导航系统、证券交易、以及命令与控制系 统等。随着计算机技术及应用的发展，这些实时应用要求大量的数据能够被及时地处 理与管理，并且不同应用的数据之间存在相互依赖关系。因此，数据不能再采取单独 管理的方式，它已经成为至关重要的资源，需要高效的管理机制。数据密集的实时应 用能够借助数据库管理系统的原理和技术得到改善，数据库系统将数据封装成为一种 资源，并提供了更为结构化的数据管理方式。分布式混合实时数据库系统( d h r t d b s ： d i s t r i b u t eh y b i r dr e a l t i m ed a t a b a s es y s t e m s ) 也是围绕着这个概念进行设计，即把数 据作为资源来管理，但是其中数据与事务不仅具有分布性，且都带有了典型的时间性 需求，包括截止期、时态有效性、周期等【1 2 。当前，分布式混合实时数据库得到了 实时系统和分布式数据库系统两个领域的研究者的关注，并取得了很大的进展，数据 库领域研究者的动机是利用数据库技术来解决实时系统中的数据管理问题，而实时系 统的研究者则注重于时间驱动的事务调度与资源分配算法。但是简单地集成分布式数 据库系统与实时系统的概念、机制与工具是不可行的，必须在实时应用需求的基础上 综合考虑子事务分布执行、实时调度与并发控制中涉及的截止期保证与数据访问冲突 问题。为了提高整个系统的运行效率，除了要提高事务执行的并发度，还要尽量减少 因为错过执行期限而被迫放弃的事务的数目 3 1 1 4 】。 传统数据库中事务调度与处理方法的目标是最大化事务吞吐量或者降低平均响 应时间。强调维护系统的完整性、一致性，适当处理稳定的需要长期保存的数据，在 传统的应用领域( 主要是商务和管理系统) 中取得了巨大的成功1 5 j 。然而随着数据库的 应用向新的领域扩展，如电话交换，电力调度、雷达跟踪、航空管制等，传统的事务 处理技术就显得无力。 分布式混合实时数据库系统目前有着很广的应用领域，除了传统的移动通讯、无 线通讯、远程教育、分布交易、办公管理、电子商务等应用领域外【6 】【7 】【8 】，还包括了工 业控制，核反映控制、飞机导航、军事系统、股票交易监控系统等等新的应用9 】【i o l f ”1 【1 2 l 。 南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 1 2 研究现状 分布式混合实时数据库系统是由实时数据库系统( r t d b s ) 、分布式数据库系统 ( d d b s ) 、混合实时数据库系统( h r t d b s ) 【1 3 】一步步发展过来的。 实时数据库( r t d b ) 的研究起源于2 0 世纪8 0 年代中期。在1 9 8 8 年发表的a c m s i g m o dr e c o r d 实时数据库专刊，揭示了r t d b s 研究领域的诞生，1 9 8 8 年9 月 r o b e r t k ，a b b o t t 和h e c t o rg a r c m m o l i n a 在1 4 届v l d b 会议上的一篇论 文s c h e d u l i n gr e a l t i m et r a n s a c t i o n s ：ap e r f o r m a n c ee v a l u a t i o n 是实时数据库这一领域 中重要论文，这篇论文提出了数据库系统中的事务可以具有实时限制，并提出了与之 相关的一系列的c p u 及i o 调度算法、并发控制协议等等。特别是1 9 9 6 年三月召开的第 一届国际实时数据库系统的专题讨论会以后，很多学者都对其进行了大量的研究，并 发表了许多有价值的文章，r a m a r i t h a m 提出了实时数据库中的数据实时特性，指出事 务执行必须满足严格的时间约束，对实时数据库的发展起到了奠基的作用，之后l a m 评估了r t d b 的特性，又提出了各种实时事务的正确性准则。随着r t d b s 研究的不断 深入和日益完善，d b x 公司推出了z i pr t d b m s ，该系统虽然能很好地满足硬实时事 务和某些r t d b 的特征，但是它具有一个明显的缺点，不支持动态实时调度和数据的 时序一致。 近年来，常规数据库得到长足发展与应用，而实时数据库的研究相对发展较慢， 主要是实时问题有较强的专用性。传统自动化系统对运行信息的处理多以本地报表、 历史数据保存为目标，对系统管理的高层支持若依托常规数据库，那么面对实时问题 便受到很大限制。 国外对r t d b 的研究非常关注，在此方面的研究开展较早，尤其是美国、英国、 德国、瑞典等国起步较早，现已有许多成功的实验系统，有的甚至已商品化，典型的 有h i p a c 、z i pr t d b m s 等系统。涉及航天、军事、能源、过程生产等1 1 4 】 1 5 【1 6 1 。 国内的研究起步稍晚，基本上是在8 0 年代末、9 0 年代初才开始，但发展很快。目 前已有成功的实验系统，但尚未形成正式产品，其主要原因是国内缺乏合适的实时操 作系统，这已成为r t d b 发展的重要障碍。目前，自动化领域内应用的可组态系统内 有一些实时数据库的内容，但集成于特定的系统中，对不同系统的连接较难实现。特 别是把不同业务试图合在一个软件系统中，从发展角度看是不恰当的。 分布式混合实时数据库系统是混合实时数据库系统与分布式数据库系统相结合 ， 南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 的产物，事务调度与并发控制方法基本上都是在传统的方法中改进以适合分布式混合 实时事务处理的需要，目前它还主要处于理论研究状态 1 7 1 1 8 】【1 9 】 删。 1 3 研究内容与组织结构 对比传统的数据库系统的事务处理，分布式混合实时数据库系统的主要研究重点 是混合实时事务的分布性和混合实时事务的实时性。由此本文主要研究以下内容： ( 1 ) 实时事务的调度与并发控制： ( 2 ) 混合实时事务的价值模型、调度、并发控制； ( 3 ) 分布式混合实时事务模型、事务价值模型、分布式混合实时事务的准入控制 策略、事务的调度与并发控制协议。 ( 4 ) 仿真测试平台实现。 本文的组织结构如下： 第一章绪论：简述了分布式混合实时数据库的背景知识、研究现状，介绍了本 文研究的主要内容、组织结构与创新点。 第二章实时事务的调度与并发控制：首先介绍了实时数据库系统模型、实时事 务模型、接着阐述了实时事务的调度与实时事务并发控制方法。讨论了几种经典的事 务提交协议与并发控制方法。 第三章混合实时事务的调度与并发控制：首先提出混合实时事务的定义：含真 实时( 硬实时、固实时、软实时) 子事务与非实时子事务的事务：接着介绍了混合实时 数据库系统模型，混合实时事务价值模型、最后讨论了混合实时事务的调度方法与并 发控制策略。 第四章分布式混合实时事务的调度与并发控制：这是本文的重点之一。首先给 出了分布式混合实时事务模型，定义了分布式混合实时事务、子事务，以及怎样的事 务才算成功提交；接着讨论了系统架构、给出了分布式混合实时数据库的体系结构图； 然后讨论了分布式混合实时事务的价值模型，分布式混合实时事务的准入控制机制： 最后讨论了分布式混合实时事务的调度方法与并发控制策略。 第五章d h r t t p 仿真测试平台( e t p d h r t t p ) ：第一节讨论了分布式混合实时 数据库的设计思想：第二节简述了e t p d h r t t p 的总体架构：由系统设置模块、发生 器、事务调度模块、数据管理模块等模块组成。第三节讨论了e t p d h r t t p 的类图。 3 南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 第四节讨论了e t p - d h r t t p 的泛序列图。 第六章总结与展望：对本论文的研究进行总结，讨论了它的可取与不足之处， 指出进一步研究的方向。 本文的创新性工作主要体现在以下几个方面： 1 ) 提出了一种混合实时事务的定义：包含了硬实时与非实时、固实时与非实时、 软实时与非实时的事务称为混合实时事务，把硬实时、软实时、固实时统称 为真实时。 2 ) 提出了混合实时事务的价值机制； 3 ) 研究讨论分布式混合实时数据库模型，分布式混合实时事务准入控制策略 ( a c m d h r t t ) ： 4 ) 分布式混合实时数据库系统架构； 5 ) 设计了分布式混合实时事务的仿真测试平台：e t p d h r t t p 。 1 4 小结 本章首先介绍了混合实时数据库的研究背景及研究现状。然后简述了本文的研究 重点与组织结构，最后说明了本文的创新点。 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 第二章实时事务的调度与并发控制 本章首先给出一个简单的实时数据库系统模型，及实时事务模型，并描述一个实 时事务在实时数据库系统中的执行过程，为后面进行的实时事务调度与并发控制研究 提供基本框架。然后讨论实时事务的调度与并发控制策略，最后对实时事务的调度与 并发控制策略做个小结。 2 1 实时数据库系统模型 由于内存价格的逐步下降，性能却不断提高，越来越多的实时数据库系统采用主 内存数据库模型，从而减少7 i 0 操作所导致的事务执行的不确定性，增加了事务执行 的可预测性。在主内存数据库模型中，c p u 是实时调度所考虑的主要系统资源。另一 方面，尽管事务具有传统实时系统中任务相似的属性，包括截止期、周期性、关键性、 优先级等，但数据库本身是受限存取的资源。因此，实时事务的调度处理必须关注事 务对数据的存取，截止期是对数据存取的时间约束。这与单纯的c p u 调度不同，但是 可以假设c p u 调度存在于实时事务调度的底层。 每个实时事务的执行都是在实时数据库系统中经过不同部件的处理直到结束，或 者成功提交，或者安全终止。图2 1 给出了一个简单的实时数据库系统模型，下面简要 描述一下事务在这个实时数据库系统中的处理过程： 21 实时数据库系统模型 任何新的事务必须经过准入控制机制进入系统，准入控制用于监视并调整系统内 并发的事务数量，避免系统出现过载。 每个新事务或者重启事务都会被分配一个优先级，事务按照优先级次序等待占用 南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 c p u 以开始执行。 在一个事务对一个数据对象执行读写操作前，必须通过并发控制部件以便实现请 求的数据一致性；如果一个事务的请求被拒绝，则这个事务将被放入阻塞队列；当请 求的数据对象可用时，阻塞的事务则被激活。如果采用乐观的并发控制协议，可能需 要夭折并重启冲突中的某些事务，以便解决冲突。 如果一个事务在截止期内完成了所有操作，则提交结果并释放所有占用的数据对 象；如果事务没能在截止期之内完成，则如果此事务是软实时或非实时事务就继续执 行否则终止。 准入控制机制通常利用事务的最坏情况执行时间作为准入标准，但是在事务的执 行与数据需求并不确定的情况下，最坏情况执行时间很难预测。并且事务的天折可以 分为两类：终止天折包括由截止期错失导致的事务天折或者由系统异常导致的事务夭 折；非终止的天折是由于死锁或者数据冲突导致的，如果该事务的截止期仍然未过， 则事务可以被重启。 实时事务的优先级分配可以使用实时系统中同样的方法，但是必须注意到实时数 据库中的优先级驱动的事务调度应该包含具有时间性的并发控制机制，事务的优先级 使得调度器能够着手执行较关键的事务，并发控制机制能够基于冲突事务的相对优先 级来解决冲突。 2 2 实时事务模型 实时数据库系统模型与传统数据库系统相类似，实时数据库系统的操作也是以事 务的形式出现。事务就是包含在b e g i n c o m m i t a b o r t 之间的操作序列。系统以事 务为单位分配c p u 、数据等资源，进行优先级的分配、调度处理等。 实时数据库系统中的事务与传统事务有很大的不同，其事务可以有定时限制( 典 型地为截止期) ，系统追求的目标不是系统的吞吐量，而是单个事务定时限制的满足， 以使满足定时限制的事务比率最大：传统事务的原子性、一致性、隔离性及永久性在 实时环境下变得太严格或不可能；要求采用”识时”机制来处理事务的调度或并发控 制，而不是传统的先来先服务方式。 2 2 1 实时事务特性 实时数据库系统中的事务与传统事务具有根本性的区别，实时事务的特性主要表 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 现在【2 l 】： a 事务的正确性不仅在于逻辑结果的正确性，而且要求时间上的正确性，即事 务必须在给定的截止期之内完成； b 可预测性：特别是硬实时事务，要求能够预测这些事务是否会满足截止期； c 可恢复性：发生故障时使数据库成为某种被认为是正确的状态，而不一定是 事务回滚。 因此，实时事务的处理应该支持： a 复杂的实时事务模型，包括事务的嵌套与可选的执行路径等； b 。事务的先后次序约束以及事务之间的协调与同步，要求事务之间直接交互； c 时间正确性甚至比结果正确性更加重要，有时宁愿要求及时但部分正确的结 果； d “识时”的调度与并发控制协议，有时甚至放松对于传统数据库最重要的可串 行化； e 数据的时间相关性：许多数据是时态数据，具有绝对一致性与相对一致性要求。 2 2 2 实时事务的分类 基于实时数据库系统中事务本质，可以从三个角度描述与分类事务：( 1 ) 事务时 间性的特点或者满足事务截止期的关键性或者说错失截止期的后果分类：( 2 ) 事务处 理数据的方式即按功能分类；( 3 ) 事务的到达模式。 一、 实时数据库一个非常重要的性质是事务有多种定时限制，其中最典型的是 事务截止期( d e a d l i n e ) 。按事务截止期分类，实时事务一般可以分为三类： 硬实时事务：指事务的截止期错失可能导致灾难性后果，这类事务在其执行过期 后，将给系统传递一个很大的负值，如图2 1 2 所示，当事务错过截止期后价值为负值。 这些事务是典型的安全关键的活动。它对应于安全危急性活动，例如威胁人的生命， 在系统发现事务具有很大的负值时，必须采取预定的紧急措施。因此，这些事务的执 行要求可预测性，系统中一般具有固定数目的硬实时事务，并且要求这些事务的最坏 情况执行时问与读写数据集是预先知道的，一般来说这些事务或者是定期事务或者是 偶发事务，具有固定的周期或者最小间隔到达时间，从而能够在一定的调试算法与并 发控制协议下进行事务的可调度性分析。只有预先了解事务的数据需求与执行特性， 包括最坏情况执行时间、截止期、周期或者最小间隔到达时间等，否则不可能保证事 一7 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 务满足其截止期。 图2 2 软实时事务：这类事务超过截止期仍有一定的价值，且随着时间价值不断下降， 直到某一时刻( 称为最终有效时间) 降到零，此后保持为零。一般来说，软实时事务 的到达模式、执行时间与数据存取模式都是预先未知的。特别是，这类事务在截止期 之后可以继续执行一段时间，但是事务的价值会逐渐减少。如图2 3 所示的价值函数 ( t ) ，事务在截止期d i 之前v i ( t ) 是一个常数值v i ，但是事务的价值在截止期之后逐渐下 降，直到零价值点z i 。衰减率d e c a y - r a t e = t a n ( q ) ，能够用来定义事务价值下降与截止 期之间的关系。 d -函 图2 3 固实时事务：事务一旦到达截止期，其价值立即降为零，此后固定为零。所以固 实时事务是软实时事务的一种特例。此类事务的零价值点与截止期重合。女n t n 2 4 所示 的价值函数( t ) ，事务在截止期d i 之前v i ( t ) 是一个常数值v i ，但是事务的价值在截止 期之后降为零，此后固为零。固实时事务的到达模式、执行时间与数据存取模式都是 预先未知的，因此这类事务的调度处理具有一定的不确定性，但是，少量的事务错失 截止期也是允许的。 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 d 。乙 图2 4 二、 从事务处理数据的方式，实时数据库中事务涉及传统数据库研究中的全部 三种事务类型：只写事务( 即获取环境的状态并写入数据库中) ；更新事务( 即导出新的 数据并存到数据库中) ；只读事务( 即从数据库中读出数据并发送给发起者) 。 三、 按照事务的到达模式，事务可以分为周期事务、非周期事务与零星事务。 周期事务以一定的周期循环地到达与执行，例如对物理环境的数据采样事务是周期事 务。非周期事务通常由外部事件( 如物理环境的状态变化) 或者内部事件( 如定时事 件或者数据库状态的变化) 动态驱动。零星事务只是偶尔一次地执行，但是两个连续 实例之间具有一个最小间隔时间。 2 3 实时事务调度 事务调度策略主要是解决如何为事务分配优先级，而调度的最重要目标是保证尽 可能多的事务能够满足截止期。即最大限度的减少错失率( m i s s r a t e ，简称m r ) - 与重 执率( r e s t a r tr a t e ，简称为r r ) ，这也是衡量r t d b s 性能的最常用的二个尺度。下 面分别定义m r 和r r 如下： 定义1 ： 错失率( m r ) = 重执率( r r ) = n m i s s e d n c o m m i t t e d + n m l s s e d n m s l b d n c o m m i t t e d + n m i s s e d ( n 。i 。d 表示错过执行期限的事务数目) ( n c 。i t t e d 表示成功提交的事务数目) ( n 。o 。i t t e d 表示被重新执行的事务数目) 大部分实时任务调度算法并不能直接用于调度实时事务，原因在于：这些算法通 常要求任务到达时间、截止期与最坏情况执行时间与关键性等参数是已知的。而实时 事务调度中广泛存在的不可预测因素，主要包括数据存取的动态性、磁盘i o 、事务 夭折与回滚等，导致事务的最坏情况执行时间很难估计。因此，很多实时数据库采用 9 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 主内存数据库模型，以消除l ，o 操作所带来的影响。另一方面，实时数据库通常应用 于开放环境，系统的负载变化是不可预知的且可能在较大范围内变化，给实时事务调 度带来更多的困难。 a b b o t t 等川最先基于一个内在驻留的实时数据库模型，综合研究了f c f s ( f i r s t c o m ef i r s ts e r v e r ) 、e d f ( e a d i e s td e a d l i n ef i r s t ) 与l s f ( l e a s ts l a c kf i r s t ) 三种并发 控制协议，仿真实验结果表明：就调度算法而言，e d f 算法表现出最好的性能，而 l s f 算法要优于f c f s 算法：2 p l c r 表现出最好的性能，但是其性能很大程度地受 到事务估计执行时间精度的影响。进步地，a b b o t t 等【2 2 1 的实验表明： ( 1 ) 如果采用l s f 算法调度事务时，使用2 p l _ w p 与2 p l c r 协议更可取的。而 使用2 p l - h p 协议对于数据冲突程度很敏感，表现较差。 ( 2 ) 如果采用e d f 算法调度事务，2 p l - w p 与2 p l c r 协议表现出相似的性能， 而2 p l - h p 协议同样表现较差。此外，a b b o t t 等也在磁盘驻留的实时数据库 模型之上对上面的算法与协议进行了测试，结果表明l s f 优先级分配算法表 现出最好的性能，而2 p l w p 协议与l s f 或者e d f 配合使用都优于2 p l h p 协议，并且采用优先级驱动的i o 调度相对于f i f o 方式具有很大的性能改进。 无论如何，当系统负载采用步进方式递增时，e d f 算法是性能最好的调度算 法，而2 p l h p 协议表现最佳。最后，a b b o t t 等指出c p u 调度算法是实时事 务调度处理中最重要的策略，而在并发控制中使用优先级信息解决数据冲突有 利于改进系统的性能。 h u a n g 等【2 3 l 基于一个实时数据库测试床r t - c a r a t ，实时事务调度算法与冲突解 决策略进行了实验研究，结果表明：实时事务调度算法必须综合考虑事务的截止 期与关键性，并且在冲突解决策略中考虑这些信息能够改进系统性能；事务截止 期与事务关键性的分布情况也在很大程度上影响系统的性能。因此，在随后的研 究中，许多算法都把事务的关键性或者重要性看作调度算法中必须考虑的重要因 素。下面，我们从基于价值的事务调度、基于准入控制的事务调度、动态过载管 理等几个方面对实时事务调度处理的研究现状进行简要的回顾。 2 3 1 基于价值的事务调度 在许多现实的应用中，不同的事务具有不同的价值或者不同的关键程度。价值或 者价值函数的概念已经用于一般的实时系统【2 4 1 【2 5 1 中，如基于价值的任务调度、综合价 ： 1 阻 南昌大学信息工程学院硕士学位论文 分布式混合实时数据库事务研究 值与截止期的任务调度算法等。在实时数据库领域，先前的一些研究也已经考虑调度 具有不同价值的事务，而系统的主要性能指标通常也转换为最大化系统的实现价值。 h u a n g 等使用一个实时数据库测试床r t - c a r a t 评估了m c f ( m o s tc r i t i c a lf i r s t ) 、 e d f 与c d f ( c r i t i c a i n e s s d e a d l i n ef i r s t ) 三种调度算法的性能，其中c d f 算法中事务 的优先级按照( 相对截止期关键性) 进行分配，结果表明综合考虑事务的截止期与 关键性在很大程度上改进了系统的综合性能。 h a r i t s a 等蚓给出了不同的基于价值的优先级分配算法：h i g h e s tv a l u ef i r s t ( h v f ) 、v a l u e i n f l a t e dd e a d l i n e ( v d ) 、v a l u e i n f l a t e dr e l a t i v ed e a d l i n e ( v r d ) 以及桶算法( b a ：b u c k e ta l g o r i t h m ) ，其中v d 算法中事务的优先级按照( 截止期 关键性) 进行分配，v r d 算法等同于c d f 算法，而b a 算法基于构造b e s te f f o r t ( b e ) 算法的相似经验：( 1 ) e d f 算法的最优性，即如果一个事务集中的所有事务能够以 一定的执行顺序在它们各自的截止期之前完成，则按照e d f 算法进行调度能够执行所 有事务的截止期；( 2 ) 如果系统资源只能满足一部分事务的截止期，选择最高价值的 事务优先执行能够最大化系统的实现价值。b a 算法中事务的优先级表示为向量 ( b ，d ，i ) ，其中b 表示事务所属的桶，d 表示事务的截止期，而i 是一个全局唯一的 随机数，通过设置桶数的多少支持在调度中进行截止期与价值之间的折衷。实验结果 表明，e d f 算法在负载较轻时表现最佳，h v f 与v d 算法在较高负载下性能较好，而v r d 算法表现出最好的综合性能。不过，通过对b a 算法的性能测试表明，没有一个固定 的截止期一价值的折衷能够适用于所有负载情况，根据负载情况合理选择参数能够产 生最好的性能。此外，研究也表明了在采用综合截止期与价值的调度算法进行固定截 止期事务调度时o c c w a i t 协议的性能也优于2 p l h p 协议，这个结果与先前的研究结 果一致。 t s e n g 等【2 9 1 提出了另一种基于价值的调度算法h r f ( h i g h e s tr e w a r df i r s t ) ，其 中事务的优先级按照( 价值剩余执行时间) 进行分配，因此这种优先级是时变的。 h a r i t s a 与t s e n g 等对于基于价值的调度算法的研究可以汇总如下：在磁盘驻留的实时 数据库( r t d i b ：r c a l t i m ed i s kr e s i d e n td a t a b a s e s ) 系统上，如果事务的价值是一 致分布的并且采用最大化系统的实现价值作为性能指标，正常负载下按照算法优劣排 序为e d f h r f h v f v r d ，在系统过载时性能排序为h r f h v f v r d e d f 。 南昌大学信息工程学院硕士学位论文分布式混合实时数据库事务研究 主内存数据库( m m d b ：m a i nm e m o r yd a t a b a s e s ) 与磁盘驻留数据库( d r d b ：d i s k r e s i d e n td a t a b a s e s ) 相比，主要区别在于前者的事务存取数据时没有磁盘i o 操作， 因此主内存数据库更加适合实时应用，使得事务的执行时间更加可预测3 叭。t s e n g 等 【3 13 研究了不同基于价值的实时事务调度算法在实时主内存数据库( r t m m d b ) 与部 分驻留内存的实时数据库中的性能，目标在于评估并比较这些算法在主