（计算机应用技术专业论文）基于反馈控制的实时数据库事务调度研究.pdf

江苏大学硕士研究生毕业论文 摘要 近年来，随着对实时数据库服务的需求越来越多，实时事务调度逐渐成为一 个研究的热点。先前的研究大都集中在单个或多个类型的实时事务的调度与并发 控制上，但是由于实时数据库的应用中将面临着大量的服务请求，系统可能会出 现超载，结果导致许多事务错过它们的截至期或者违反数据的时序一致性约束。 因此，实时数据库系统事务调度的目标应该是：即使在系统处于超载的情况下也 要能保证硬实时事务满足其截止期，同时最小化软实时事务的截止期错失率。 本文首先介绍了课题的研究背景，并介绍和分析了目前国内外已提出的实时 事务调度的方法。在比较分析了这些调度方法的优缺点的基础上，给出了本文研 究涉及的实时事务的概念。同时借鉴在不精确性计算中以牺牲结果的精确性来换 取执行时间的思想，把不精确性计算的方法运用到实时数据库事务调度中，提出 了基于不精确性计算的实时事务模型。 进一步，考虑到实时数据库中的数据对象的值总会和要表示的现实环境的状 态存在一定的误差，因此，引入数据误差的概念来表示这一误差；同时，考虑到 系统的负载通常是不可预知的，因此把反馈控制的思想应用到支持不精确计算的 实时事务q o s ( q u a l i t yo fs e r v i c e ) 管理中，给出了基于不精确计算的反馈控 审8 调度( f c s w i c ：f e e d b a c kc o n t r o ls c h e d u l i n gw i t hi m p r e c i s ec o m p u t i n g ) 算法和框架。在这一部分，首先定义了系统要求达到的性能指标；然后根据这些 指标讨论了基于反馈控制的体系结构，并描述了系统中各个部分的功能；最后详 细讨论了系统的建模过程，并给出了反馈控制调整过程中的实现细节和参数获取 方法和过程。 最后，作者设计丌发了一个基于反馈控制框架的实时数据库原型系统 f c w i c ，详细讨论了系统各个模块的设计以及实现过程。 本文的研究成果为进一步研究探讨实时数据库中基于反馈控制的实时事务 调度的方法提供了一个良好的基础。 关键词：实时数据库，事务调度，反馈控制，不精确计算，服务质量 江苏大学硕士研究生毕业论文 a b s t r a c t r e c e n t l y ，w i t ht h eh l c r e 勰eo ft 1 1 er e q u i r e m e n ti ns e r v i c eo fr e a l - t i m ed a t a b a s e ， s c h e d u l i n go nr e a l t i m et r 柚s a c t i o ni sb e c o m i n gah o tr e s e a r c h p r e v i o u ss t u d ym a i l l l y f o c u s e so ns c h e d u l i n ga i l dc o n c 眦r e n c yc o n t r o lo ne i t h e rs i n 舀eo rm l l l t i 一帅er e a l - t i i n e t r a i l s a c t i o n s h o w e v e r ，d u et 0t h eh i 曲i c ed e m a n d ，r e a l - 劬ed a t a b 硒e sc a i lb e o v e d o a d e d a sar e s u l t ，m a n yt 啪s a c t i o n sm a ym i s st h e i rd e a d l i n e s ，o rd a t at e m p o r a l c o n s i s t e n c yc o n s t r a i l l t sc a nb ev i o l a t e d t h e r e f o r e ，t l l eg o a lo fs c h e d u l i n g0 fr e a l t h n e d a 协a s y s t e mi st h a t 廿l e d e a d l i i i e so f h a r dr e a l t i i n et r a l l s a 甜o n sm l l s tb e g u a 舳t e e d 锄dt h en u m b e ro fd e a d l i n ev i o l a t i o n sf o rs o f tr e a l - 劬et r a n s a c t i o 璐 s h o u l db em i n i l n i z e de v e ni fo v e r l o a d i i lt h i sm e s i s ，w ef i r s t l yd i s c u s sm eb a c k 伊o u n da i l dt l l e n 、耽i i l t r o d u c c 锄d 觚a l y z et l l em a i l le x i t i n gs c h e d u l i n g 锄c h i l i q u eo fr e a l - t i n l et r a i l s a c t i o n o nt l l eb 觞i s o fc o m p a r i i 培锄da n a l y s i n gt h ea d v a i l t a g e s 锄dd i s a d v a n t a g c so ft l l e s es c h e d u l i i 培 m e t h o d s ，w ep r e s c n tt h ec o n c e p to fr e a l t i i n et r a n s a c t i o ni i lt h i st h e s i s a tt h es 锄e t i m e ，b yl e a m i i l gf 幻mt h et h o u 曲to fs a ( n f i c i n g t h er e s u l t s a c c u r a c yf o rt h e e x e c u t i o n 缸e ，w ea p p l ym em e t h o do fi n l p r e c i s ec 0 m p u t i n gt 0t h es c h e d u l i n go f r e a l - t 妇et r a 皿s a 嘶o na n dp r e s e n tt h er e a l t i n l e 订a n s a c t i o nm o d e lb 硒e do ni i l l p r o c i s e c o m p u t i n g m o r e o v e r ，c o n s i d e r i n gc e n a i l ld e v i a t i o nb e 俩e e nm ev a l u eo fd a t ao b j e c ta n dt h e s t a t eo fa c ：t i l a le n v i r o l l i i l e n ti nt l l er e a l t i i n ed a t a b a s e ，w ei n t r o d u c et h ec o n c e p to fd a t a e n o rt 0 e x p r e s st h i sd e v i a t i o n ；m e a n w h n e ，c o n s i d e r i n gm el o a d i n go fs y s t e mi s a ：1 w a y s 曲o w a b l e ，、耽a p p l y t t l e t h o u g h to ff e e d b a c kc o n t r o l t ot 1 1 eq o s m a i l a g e m e n t sw h i c hs u p p o ni i i l p r e c i s ec o m p u t i n g 锄dp u tf o 刑枷t h em e t h o da i l d m ef r 锄e w o r ko ff c s w i cb 硒e do ni m p r e c kc o m p 砸n g i i lt h i sp a r t ，w ef i 础y d e f i n et h ep e ! ：d r m 孤c em e t r i c s r e q u i r e db yt i l es y s t e m a i l d t l l e nd i s c u s st l l e a r c h i t e c t u r e sb 舔e do nf e e d b a c kc o n t r 0 1t h e o r ya c c o r d i n gt ot h e s ei i l d i c e s 锄da l s o p r e s e n tt h ef u n c t i o n so fe v e r yp a n s ；f i n a l l y ，w ed i s c i l s st l l em o d e l i n gp r 0 c e d u r c so f t l l es y s t e mi i ld e t a i la i l dp r e s e n tt h em e t h o d sa i l dp r o c e s s0 fm e i i i l p l e m e n t a t i o nd e t a i l s 孤dt l l ep a r 锄e t e rp r o c u r e m e n ti i lt h ep r 0 c e s so ff e e d b a c kc o n t r o la d j u s 仃n e n t s 江苏大学硕士研究生毕业论文 f i n a l l y ，t h ea u t l l o rd e s i 印a i l dd e v e l 叩af c w i cb 勰e do n f e e d b a c kc o n t r o l f 汹e w o r ka n dd i s c u s st h ed e s i 粤u i l e n ta j l dt h ei m p i e m e n t a t i o np r o c e d u r co ft h e s y s t e m se v e r ym o d u l e t l l l er e s e a r c ha c t l i e v e m e n t s0 ft i l i st h e s i s w i l lp r o v i d eas o u n db a s i sf o rt l l e f u n h e rs t u d i e so ft h er c a l t i n l es c h e d u l i n gm e t h o d sb a s e do nf e e d b a c kc o n t r o li i lt h e i e a l t j m ed a 协a s 岔 k e yw o l m s ：r e a l t h ed a ta _ b a s e ，t r a j l s a c t i o n s c h e d u l i n g ，f e e d b a c kc o n t r 0 1 ， h n p r c c i s ec o m p u t i n g ，q u a l i 哆o fs e i c e 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：职渺 r 期：弘劈年月p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于保密口， 不保密团。 学位论文储签名：觏删 签字r 期：蛾年6 月p 日 导师躲辔多 签字日期办绰6 月口同 江苏大学硕士研究生毕业论文 1 1 研究背景 第一章绪论 在现实中有许多应用包含了对数据的“定时 存取和对“短暂有效数据的 存取，例如电话交换、数据网络管理、空中交通管制、工厂生产过程控制和证券 交易等等。这些应用一方面需要维护大量共享数据和控制数据，另一方面其应用 活动有很强的时间性，要求在一个确定的时刻或和在一定的时间期限内，从外 部环境采集数据、按彼此间的联系存取并处理采集到的数据，再及时做出响应。 同时，它们所处理的数据往往是短暂的，即只在一定的时间范围内有效，过时则 无意义。因此，数据不能再采取单独管理的方式，它已经成为至关重要的资源， 需要高效的管理机制。为此，实时数据库系统( r 1 i ) b s ：r e a l 恤ed 雏l b a s e s v s t e m s ) 围绕这个概念进行设计，把数据作为资源来管理。r t d b s 就是其事务 和数据都具有定时特性或显示的定时限制的数据库系统，包括截止期、时态有效 性、周期等【l 】。近年来，m b s 受到了数据库和实时系统两个研究领域里的工 作者的极大关注。数据库研究工作者的动机在于利用数据库技术的特点和优点来 解决实时系统中的数据管理问题；实时系统研究者则关注于给r 1 1 ) b s 提供时间 驱动调度和资源分配算法。但是i b s 并不是数据库技术和实时系统技术的简 单集成，它必须在实时应用的基础上考虑事务截止期的满足和在数据资源冲突时 的并发控制问题，并且应该具备一定的实现结果的正确性与实时性的折中的能 力。 传统数据库中事务调度与处理方法的目标是最大化事务的吞吐量和降低事 务的平均响应时间。但是，由于数据的时态属性以及应用环境带来的时间需求， 实时数据库系统需要处理具有时间约束的事务，这些时间性需求通常表现为事务 的周期或者截止期。因此，保证较低的事务截止期错失率以及在数据库中的数据 和不断改变的外部世界之间提供一个时序一致性约束是很有必要的。进一步说， 实时数据库系统中的事务调度与处理目标不同于传统的数据库系统，最大程度的 满足事务的截止期是其最终目标。但为了解决这个问题，必须考虑下面几个方面 的问题： 一方面，必须注意到实时数据库系统与实时系统的调度算法有不同的调度单 元。实时数据库的调度单元是事务，而实时系统的调度单元通常是任务，它很少 考虑到任务调度过程中出现的数据资源的访问冲突问题。而事务的调度主要关注 的是数据资源的需求，并且它的存取有一定的动态性。事务具有隔离性，它要求 江苏大学硕士研究生毕业论文 任何夭折的事务不对其他事务的执行造成影响，也就是要求并发执行的事务必须 相互隔离。 另一方面，也必须注意到实时数据库系统中不同截止期类型的事务对系统有 不同的要求。硬实时事务错失截止期可能导致数据库系统性能的大幅下降甚至导 致灾难性的后果，而少量的软实时事务错失截止期是可以容忍的。先前的研究大 都集中在单个类型的实时事务的调度与并发控制，但是多个类型的事务负载的实 时数据库应用需求也是非常的普遍。由于硬实时事务与软实时事务错失截止期的 后果不同，因此在解决数据冲突时应该对引起冲突的事务进行区别对待，采用不 同的冲突解决策略。它的目标就是满足硬实时事务的同时最大化软实时事务的执 行。 此外，由于对实时信息服务的需求越来越大，许多实时应用在数据需求方面 变得非常的复杂。像敏捷制造这样的应用，其数据跨越从底层的控制数据( 特别 是来自传感器的数据) 到高层的管理和商业数据。由于大量的服务请求和紧迫的 时间数据新鲜度( 外部一致性) 约束，实时数据库可能出现超载的情况，结果 关键事务错失截止期。这通常采用准入控制的方法来放弃某些非关键事务的执 行，但这往往造成了由于放弃太多非关键事务的执行，而使得系统的性能较低。 当前许多实时调度算法是基于开环结构的。也就是说一旦调度器被创建，它就不 能根据外部环境的变化而改变，因此在系统超载的情况下性能较差。为了实现在 不可预测环境下的实时事务调度，一些自适应的调度算法被提出。其中，控制理 论也被应用到调度算法的设计中，例如一些研究提出了基于控制理论中的反馈控 制c p u 调度算法来满足不同的系统q o s 管理【2 】。但这些研究考虑的多是实时系 统的任务调度，而在事务调度方面仍然考虑的较少，并且对于调度系统模型的建 立、控制变量与操作变量的选取、控制函数的构造以及如何在实时数据库中应用 反馈控制调度等问题都需要进一步的深入研究。 总之，实时事务的调度是一个复杂的问题，同时为了提高系统的性能它又是 必须被重点处理的问题。因此有必要解决在不可预测的负载和数据访问模式下， 实时数据库也能保证事务的截止期错失不被违背，或者满足一定的性能要求的问 题。为了达到这个要求，r 1 d b s 必须具有个良好的系统结构。 1 2 国内外研究现状 实时数据库系统( r t d b s ) 是一个用来处理具有定时限制的工作负载的事务 处理系统，其主要目标是要满足事务的截止期，事务处理的主要工作都围绕这个 目标进行【3 1 。这些工作主要包括事务的调度即针对多个事务的c p u 的调度，以及 2 江苏大学硕士研究生毕业论文 与之紧密相关的在多个并发运行事务之间的数据、i o 及内存等资源的调度。合 理地调度这些资源，对r t d b s 的功能和性能有极大的影响。 实时事务的调度算法主要分为两类：静态调度和动态调度。在静态调度方面， m 1 ( 1 e i l l 【4 】和c l 1 i u 【5 1 提出的单调速率( r m ) 算法和它的扩展代表着一个主要的 实时调度机制。而在动态调度方面，由于任务集和时间约束不可预知，因此动态 调度算法进一步地被分成两类：工作在资源有限的环境或者资源充分的环境的调 度算法。对于资源充分的系统的调度算法，j a s t a n k o v i c 【6 j 给出的最早截止期优 先( e d f ) 算法是一个最优的动态调度算法，这也成为了实时调度机制的另一个 代表；对于资源受限的系统的调度算法，w z h a o 【7 j 给出了一个弹性( s p 血g ) 调 度算法，它主要通过准入控制的机制来动态地限制进入系统的任务数；另外 j a s t a n k o v i c 【6 j 对这个机制也进行了发展。准入控制机制的加入成了实时调度机 制的第三个主要的方法。 近来，由于实时数据库越来越多地应用到开放与不可预测的环境中，特别是 实时事务的执行时间与数据需求通常是不确定的，因此反馈控制越来越多地被应 用到实时数据库的q o s ( q u a l 御o fs e i c e ) 管理和实时调度中。以c h 【8 】的工 作为起点，使用反馈控制进行实时调度的研究迅速展开【9 】【1 0 】【1 1 】，特别是c h 在 2 0 0 2 年的文献【1 2 】中提出的反馈控制实时调度的框架、模型和算法被大量的文献 广泛的引用。毫无疑问，已有的研究表明了反馈控制理论应用到数据库系统中的 可行性并能获得预期的性能收益，但是还有许多问题有待深入、细致地研究，包 括如何在反馈控制事务调度框架中统一协调各种事务的执行和数据时间一致性 ( 新鲜度) 的保证。本文的后续章节将对这个问题进行讨论。 1 3 论文研究的内容及其主要工作 本文在广泛阅读国内外现有的实时数据库事务调度的文献后，比较和借鉴现 有成功的实时系统任务调度方法，对混合事务的调度和系统的q o s 保证的方法 进行了完善和改进，同时给出了自己的算法，并开发了测试相应的算法性能的验 证系统。论文的主要研究内容和工作包括以下几方面： ( 1 ) 提出了基于不精确性计算的实时事务模型。 由于实时数据库中的每个实时事务都要求在特定的时间约束内完成，并且数 据库中的数据也要满足一定的时序一致性，因此为了合理的协调这两者，不精确 性计算的方法被应用到本文所研究的实时事务模型中。 ( 2 ) 给出了基于反馈控制的实时事务调度体系结构。 江苏大学硕士研究生毕业论文 由于系统的负载难以预知和估计，因此系统可能出现超载的情况。本文结合 这两种情况，提出了基于反馈控制的实时事务调度框架，当系统负载降低的情况 下把更多的精力放在保证数据的新鲜度和一致性上；当系统超载时，通过调整最 大数据误差来满足给定的q o s 要求。 ( 3 ) 研究和实现了基于反馈控制技术的实时事务调度的原型系统。 实时数据库系统中的算法与协议研究是一个非常复杂的问题，而仿真测试是 相关研究与性能评估中的重要一环。因此本文设计实现了一个基于反馈控制的实 时数据库原型系统f c w i c 。这个系统允许使用者根据需要设计不同的测试场景， 来评估、分析这些新的算法或者协议。 1 4 论文的结构 论文共分六章，主要内容概括如下： 第一章介绍课题的研究背景，概述了实时数据库所涉及的研究领域及其潜在 的应用领域和研究现状。同时分析和提出本文的主要研究工作。 第二章首先概述了实时数据库系统的事务特征和分类以及实时数据库中数 据的特性；接着综述实时数据库中事务调度的研究与发展现状，分析了这些研究 所提及的主要算法，并对这些算法的优缺点进行比较，为进一步研究打下基础。 第三章讨论了实时数据库的系统模型与本文涉及的事务类型，提出了一种基 于不精确性计算的实时事务模型并给出了实时系统通用的性能指标。 第四章引入数据误差的概念，并结合反馈控制的思想，提出了在超载环境下 支持不精确计算的基于反馈控制的实时事务调度的算法和体系结构，并给出了整 个系统建模和参数调整的详细过程和方法。 第五章介绍了本文研究中所设计实现的一个基于反馈控制的实时事务调度 的原型系统的方法和过程。 第六章对全文进行总结，并指出需要进一步开展的工作。 4 江苏大学硕士研究生毕业论文 第二章实时数据库事务调度技术的研究与发展 2 1 概述 实时数据库事务组合了实时任务和传统数据库事务两者的特征，但是并非它 们在概念、机制、技术上的简单集合，而有一系列的问题需要研究与解决，如扩 展事务模型及其结构特征、事务处理的硬软限制、事务间的关系、事务正确性和 数据一致性及其与数据语义和事务特征的联系、事务调度的协议和算法。这些问 题彼此且还与其它方面的问题紧密相关。因此，实时数据库事务处理比传统的实 时任务和数据库事务都更复杂、更困难。它们必须同时实现数据一致性( 包括外 部、相互和动态一致性) l l 列和定时限制两者【1 4 1 。 2 1 1 实时事务特征 实时数据库事务组合了实时任务和传统的数据库事务两者的特性，但并非它 们在概念、机制、技术上的简单集合，它有属于自己的特性： ( 1 ) 结构复杂性：事务内部合事务之间可能存在着层次嵌套结构。 ( 2 ) 功能替代性：一个实时事务常常由若干个任务组成，而一个任务有时 可以通过不同途径来实现。这表示即使某些子事务失败了，事务仍可能顺利提交。 这还体现了实时事务的健壮性，即有的事务( 任务) 不能失败。 因此，实时事务的处理应该支持： ( 1 ) 复杂的实时事务模型，包括事务的嵌套与可选的执行路径等； ( 2 ) 事务的先后次序约束以及事务之间的协调与同步，要求事务之间直接 交互； ( 3 ) 时问正确性甚至比结果正确性更加重要，有时宁愿要求及时但部分正 确的结果； ( 4 ) “识时 的调度与并发控制协议，有时甚至放松对于传统数据库最重 要的可串行化； ( 5 ) 数据的时间相关性：许多数据是时态数据，具有绝对一致性与相对一 致性需求。 5 江苏大学硕士研究生毕业论文 2 1 2 实时事务的分类 基于实时数据库系统中事务的本质，可以从三个角度描述与分类事务：事务 处理数据的方式、事务的到达模式与事务的关键性。 根据事务处理数据的方式，可以分为以下三种类型： 1 只写事务： 只写事务负责记录外部环境的状态或者发生的事件到数据库中。为了保持数 据库的外部一致和跟踪记录，它应该是短的、周期的，且应该是被立即执行的硬 实时事务。为了保证其定时限制的满足，它可能会引起对数据库一致性的破坏。 2 更新事务： 更新事务类似于传统数据库事务，它用来恢复已违反了一致性的数据库的状 态。这种事务可看作维护正常运行的监控器。 3 只读事务： 只读事务负责从数据库读出数据给事务的发起者，从而引起有关活动的执 行。象只写事务一样，这种事务是很短的，尽管所引起的相关活动可能要执行很 长时间。它通常也是硬实时事务。 根据事务的到达模式，可以分为以下三种类型： 1 周期事务： 周期事务以一定的周期循环的到达与执行，例如物理环境的数据采样事务就 是周期事务。 2 非周期事务： 非周期事务的到达时间没有固定的周期，一般由外部事件( 如物理环境的变 化) 或者内部事件( 如定时事件或数据库状态的变化) 动态驱动。 3 零星事务： 零星事务只是偶尔一次的到达与执行，其发生的频率很低。但是两个连续零 星事务之间具有一个最小间隔时间。 根据事务关键性( 事务截止期的性质，即事务超过截止期对系统带来的影响) 分类，而事务的关键性可以很好的用价值函数来体现，于是可以把事务分为下面 三种类型【1 5 】【1 6 】： 1 硬实时事务： 硬实时事务，又称硬截止期事务，指事务的截止期错失可能导致灾难性后 果。如果截止期错失，价值函数将取得一个很大的负值，这些事务是典型的安全 关键性活动。因此，这些事务的执行要求可预测性，这主要是通过可调度性分析 江苏大学硕士研究生毕业论文 来实现。只有预先了解事务的数据需求与执行特性，包括最坏情况执行时间、截 止期、周期或者最小到达间隔时间等，否则不可能保证事务满足其截止期。 2 软实时事务： 软实时事务，又称软截止期事务，在超过截止期后也会有一定的价值，但其 价值随着时间不断下降，直到一定的时间点价值将降低为0 。一般说来，软实时 事务的到达模式、执行时间与数据存取模式都是预先未知的。特别是，这类事务 在截止期之后可以继续执行一段时间，但是事务的价值会逐渐减少。 3 固实时事务： 固实时事务是软实时事务的一种特例，如果事务的零价值点与截止期重合， 则称为固实时事务或者固截止期事务。这类事务具有固定的截止期，即事务一旦 到达截止期，则被立即夭折。由于固实时事务的到达模式、执行时间与数据存取 模式都是不可预知的，因此这类事务的调度处理具有一定的不确定性，但是少量 的事务错失截止期也是允许的。对于软实时事务与固实时事务本文不做明确的区 分，如果一个软实时事务具有固定的截止期，则是固实时事务。 图2 1 事务截止期类型 图2 1 描述了硬、软、固三种截止期类型事务的价值体现。图中x 轴表示时 间，y 轴表示事务的价值。v i ( t ) 表示事务的完成对系统产生的贡献( 价值) ，d h 、 d 。和d r 分别表示硬事务、软事务和固事务的截止期。 江苏大学硕士研究生毕业论文 2 1 3 实时数据库的数据 实时数据库中的数据有两种类型：实时数据和非实时数据。非实时数据与 时间无关，其值不会过时。实时数据是从过程控制系统中实时采集的数据、向过 程控制系统实时发送的控制数据以及对实时数据进行各种实时计算直接产生的 中间数据。实时数据具有时间性，随着时间的推移数据便会失效。 1 、实时数据的定义： 用一个三元组d ( v a l u e ，t i m e ，a v i ) 来标识一个实时数据对象，其中分量d 砌。、 d 血和d 撕分别表示实时数据的当前状态( 或值) 、观测时标( 即实时数据采样 时间或生成时间) 和绝对有效期( 即自d 血眦时刻起d 具有外部或绝对有效性的时 间长度，设当前时间为t ，当( d d 缸) d 州时，d 。有效) 。 2 、实时数据d 具有如下特征： 内部一致性：当且仅当d 满足所有对其预先定义的数据库内部的完整性限 制和一致性要求； 数据库中数据的变更都是以事务的形式进行的，因而事务操作的完整性检 验和可串行化能够提供内部一致性的保证。 外部一致性：当且仅当( t d 血。) d 撕( t 为当前时间或检测时间) ，即实 时事务使用的数据库中的值d ，在其有效时间范围d 枷内； 相互一致性：设r 是一个相互一致集，d r 。当且仅当 v d r ( | d 州一d i f r 州) ，r 是用来作决策或导出新数据的一组相关数据的相 互一致集。每个r 均有一个与之相联的相互有效期( m u t u a lv m i d i 哆i n t e r v a l ) ， 记为r m ，i 。 3 、实时数据库的数据处理 实时数据库中的数据要反映外部世界的真实情况，但在实时数据库与外部世 界交互时，并不一定能得到准确的数据。实时系统会出现一些干扰，影响数据的 正确性。采样后的数据可能要进行一些输入处理才能写入实时数据库，如尖峰信 号的抑制和数字滤波等。 江苏大学硕士研究生毕业论文 2 2 实时数据库事务调度技术的发展 实时数据库事务调度是为了使相互之间存在竞争的事务能够访问数据库中 的共享资源。实时事务调度算法的目标是要满足事务的截止时间，事务处理的主 要工作就是围绕这个目标进行的。这些工作主要包括事务的调度即针对多个事务 的c p u 的调度，以及与之紧密相关的在多个并发运行事务之间的数据、i o 及内 存等资源的调度。 事务调度策略决定如何为事务分配优先级，而调度的最重要目标是保证尽可 能多的事务能够满足截止期。大部分实时任务调度算法并不能直接用于调度实时 事务，原因在于这些算法通常要求任务到达时间、截止期与最坏情况执行时间与 关键性等参数是己知的。而实时事务调度中广泛存在的不可预测因素，主要包括 数据存取的动态性、磁盘i o 、事务夭折与回滚等，导致事务的最坏情况执行时 间很难估计。因此，很多实时数据库采用主内存数据库模型，以消除i o 操作所 带来的影响。另一方面，实时数据库通常应用于开放环境，系统的负载变化通常 是不可预知的且可能在较大范围内变化，这给实时事务调度带来更多的困难。 a b b o t t 等【r 7 】最先基于一个驻留内存的实时数据库模型，综合研究了先到先 服务( f c f s ：f i r s tc o m ef i r s ts e e ) 、最早截止期优先( e d f ： e a r l i e s td e a d l i i l e f i r s t ) 与松弛时间最小优先( l s f ：k 勰ts l a c kf i 璐t ) 三种优先级分配方法以及 串行执行( s e r i a le x e c i l t i o n ) 、高优先级两阶段锁( 2 p l 厂h p ) 与条件重启两阶段 锁2 p l c r 三种并发控制协议，仿真实验结果表明：就调度算法而言，e d f 算法 表现出最好的性能，而l s f 算法要优于f c f s 算法；2 p l 广c r 表现出最好的性能， 但是其性能很大程度地受到事务估计执行时间精度的影响。进一步地，a b b o t t 等的实验表明：( 1 ) 如果采用l s f 算法调度事务时，使用等待优先级两阶段锁 2 p l 厂w p 与2 p l 厂c r 协议更可取的，而使用2 p l ，协议对于数据冲突程度很敏 感，表现较差。( 2 ) 如果采用e d f 算法调度事务，2 p i ，、p 与2 p 【，c r 协议表 现出相似的性能，而2 p l 广h p 协议同样表现较差。此外，a b b o t t 掣1 8 j 也在磁盘驻 留的实时数据库模型之上对上面的算法与协议进行了测试，结果表明l s f 优先 级分配算法表现出最好的性能，而2 p l 册协议与l s f 或者e d f 配合使用都优 于2 p l 耶协议，并且采用优先级驱动的i o 调度相对于f i f o 方式具有很大的 性能改进。无论如何，当系统负载采用阶跃方式递增时，e d f 算法是性能最好 的调度算法，而2 p l 广h p 协议表现最佳。最后，a b b o t t 等指出c p u 调度算法是 实时事务调度处理中最重要的策略，而在并发控制中使用优先级信息解决数据冲 突有利于改进系统的性能。 9 江苏大学硕士研究生毕业论文 h u a n g 等【1 9 】基于一个实时数据库测试床r t - c a r a t ，针对实时事务调度算 法与冲突解决策略进行了实验研究，结果表明：实时事务调度算法必须综合考虑 事务的截止期与关键性，并且在冲突解决策略中考虑这些信息能否改进系统性 能；事务截止期与关键性的分布情况也在很大程度上影响系统的性能。因此，在 随后的研究中，许多算法都把事务的关键性或者重要性看作调度算法中必须考虑 的重要因素。 下面，从基于价值的事务调度、基于准入控制的事务调度、基于动态超载环 境的事务调度和基于反馈控制的实时调度等几个方面对实时事务调度处理的研 究现状进行简要的回顾。 2 2 1 基于价值的事务调度 在许多现实的应用中，不同的事务具有不同的价值或者不同的关键程度。价 值或者价值函数的概念已经用于一般的实时系统中，如基于价值的任务调度、综 合价值与截止期的任务调度算法等。在实时数据库领域，先前的一些研究也已经 考虑调度具有不同价值的事务，而系统的主要性能指标通常也转换为最大化系统 的实现价值。h u a i l g 等1 1 9 j 使用一个实时数据库测试床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 l 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 等【2 0 】给出了不同的基于价值的优先级分配算法：价值最高优先( 小佰： h i 曲e s tv a l u ef i r s t ) ( 优先级p t = 1 m ) 、v a l u e i i 皿a t e dd e a d l i n e ( v d )( 优先 级p t = d t t ) 、v a l u e i n n a t e dr e l a t i v ed e a d l i n e ( )( 优先级p t = ( d t a t ) t ) 以及桶算法( b a ：b u c k e t 伽g o r i t h m ) ，其中v d 算法中事务的优先级 按照( 截止期关键性) 进行分配，m 算法等同于c d f 算法，而b a 算法基 于构造b e s te f 幻n ( b e ) 算法的相似经验： ( 1 ) e d f 算法的最优性，即如果一个事务集中的所有事务能够以一定的执 行顺序在它们各自的截止期之前完成，则按照e d f 算法进行调度能够按照所有 事务的截止期； ( 2 ) 如果系统资源只能满足一部分事务的截止期，选择最高价值的事务优 先执行能够最大化系统的实现价值。b a 算法中事务的优先级表示为向量( b ，d ， i ) ，其中b 表示事务所属的桶，d 表示事务的截止期，而i 是一个全局唯一的 随机数。这种方法意味着系统中的事务基于其价值被均匀地分配到一个桶集中， l o 江苏大学硕士研究生毕业论文 桶i 中的事务的优先级比桶i 一1 中的事务的优先级低但比i + 1 中的事务的优先 级高。因此通过设置桶数的多少支持在调度中进行截止期与价值之间的折衷。实 验结果表明，e d f 算法在负载较轻时表现最佳，h 、师与v d 算法在较高负载下 性能较好，而算法表现出最好的综合性能。不过，通过对b a 算法的性能 测试表明，没有一个固定的截止期价值的折衷能够适用于所有负载情况，根 据负载情况合理选择参数能够产生最好的性能。此外，研究也表明了在采用综合 截止期与价值的调度算法进行固定截止期事务调度时o c c w a i t 协议的性能也优 于2 p l 广肿协议，这个结果与先前的研究结果一致。 2 2 2 基于准入的事务调度 实时事务调度面临的一个主要挑战是事务执行所需要的资源是事先未知的。 例如，事务读写的数据对象可能依赖于用户的输入或者传感器输入，因此为事 务预留资源以保证事务的最坏情况执行时间w c e t ( w b r s tc 撇e x e c 埘o nt i m e ) 是非常困难的。这种资源获取的不确定性同样导致集成实时调度与其它数据库协 议，特别是并发控制协议的困难性。 考虑当前在实时事务调度与实时并发控制方面众多的研究成果，其中包括许 多时间认知的并发控制协议被提出，目的在于最大化满足截止期的事务数量。这 些算法或者协议的优势只有当系统出现过载时才被具体地体现，它们的性能在系 统欠载的情况下通常与非常简单的算法( 如e d f 与2 p l 厂肿) 相当。既然当一个 实时数据库系统过载时，大量的事务错失了截止期，如果通过准入控制与过载管 理策略拒绝一些事务进入系统，就能够避免有限的资源浪费在执行不可能及时完 成的事务上。并且，在许多应用如过程控制系统中，及时地拒绝一个事务可能比 最终错失截止期更安全，因为这允许系统能够及时采用合适的动作。正是基于这 种思想，一些研究针对准入控制技 术进行了较深入的研究。 2 2 2 1 硬截止期事务的准入控制 b e s t a v r o s 等口1 1 给出一个实时数 据库模型( 图2 2 ) ，并在此基础 上研究了硬截止期事务的准入控制 与过载管理问题。准入控制与过载 管理的目的是最小化事务被接受但 是随后错失截止期的可能性。当然， 图2 2b e s t a v r o s 实时数据库模型 江苏大学硕士研究生毕业论文 这种情况不可能都被消除，尤其是在事务执行需求未知的情况下。对于固定截止 期或者软截止期的事务来说，偶尔的截止期错失是可以容忍的。但是，对硬截止 期事务来说，可能产生严重的后果。因此，如果系统必须支持硬实时事务，事务 的执行需求必须预先知道，或者定义一些补救活动，以保证系统不会出现灾难性 的后果。对于固截止期事务，补救活动在有些情况下也是需要的，这保证事务能 够安全地终止。 b e s t a v r o s 等考虑了下面的事务模型，每个事务由两个部分组成：基本子事 务与补偿子事务。基本子事务的执行需求( 包括最坏情况执行时间与读写数据 集) 是事先未知的，而补偿子事务的执行需求是己知的。每当一个事务到达，实 时数据库或者接纳这个事务，或者拒绝它。一旦这个事务被接纳，它必须被保证 在截止期之f j 完成，或者成功地提交( 基本子事务完成) ，或者安全地终止( 补 偿子事务被完成) 。每个事务有一个截止期与一个价值，价值通常代表了这个事 务的关键程度或者重要程度。这时，实时数据库的一个重要目标是最大化系统的 实现价值。 准入控制器a c m 用于决定是否接纳新到达的事务。这里，准入控制器由两个 部分组成：并发准入控制器( c a c m ：c o n c u r r e n c ya c m ) 与负载准入控制器( w a c m ： w o r k l o a da c m ) 。为了保证补偿事务的完成，系统采用两层优先级模式进行调度。 系统总是为补偿子事务分配一个更高的优先级，并且一个补偿子事务不能够被一 个基本子事务或者另一个补偿子事务抢占。w a c m 基于估计系统负载确定是否接 纳一个事务，特别是，如果用于补偿子事务的处理器带宽比较高，则应该谨慎地 拒绝新到达的事务。为了确保补偿子事务无阻碍地执行，c a c m 保证被接纳事务 的补偿子事务不与系统中已经接纳事务的补偿子事务存在冲突。 事务调度器管理着两个事务队列：基本事务队列( p t q ：p r i i i l a r yt r a n s a c t i o n q u e u e ) 与补偿事务队列( c t q ：c o m p e n s a t i n gt r a n s a c t i o nq u e u e ) 。每个被接 纳的事务分成基本子事务与补偿子事务分别进入两个队列。但是，补偿子事务并 不马上执行，它必须等待准入控制器的指示。p t q 中的事务按照e d f 算法进行调 度，而c t q 被组织为一系列的槽，每个补偿事务占据一个槽，具有一个事务i d 与开始、结束执行时间。所有的槽按照补偿子事务的开始执行时间排序，c p u 继 续处理基本子事务，直到一个补偿子事务必须被执行，即到了这个补偿子事务的 开始执行时间。这时，将要执行的补偿子事务对应的基本子事务将被夭折。必 须注意的是，在这种模式下，即使采用乐观的方法，补偿事务也不会被重启，因 为补偿事务不会交迭执行，冲突时只需重启基本子事务。 为了最大化系统的实现价值，a c m 必须接纳足够多的事务，但是也不能太多。 b e s t a v r o s 等川提出了一些不同的方法用于w a c m 并通过模拟实验比较了它们的 江苏大学硕士研究生毕业论文 性能。这些方法包括f i r s t f i t ( f f ) ，l a t e s t f i t ( l f ) ，l a t e s t m a r g i n a l 一f i t ( l m f ) ，l a t e s t a d a p t a b l e f i t ( l a f ) 以及v a l u e a d a p t a b l e f i t ( v a f ) ， 其中前面四种方法都是通过判断补偿事务的可调度性或者给定补偿子事务处理 器阈值下处理器带宽的可得到性决定接纳或者拒绝事务。v a f 方法中准入控制分 为两个部分：( 1 ) 评估接纳一个事务进入系统的预期价值，这是通过对比接纳 这个事务潜在的价值与损失达到的