（计算机软件与理论专业论文）动态调整串行化顺序算法的改进.pdf

哈尔滨工程大学硕士学位论文 皇暑暑皇宣宣昌暑昌宣一i ；i i 葺i 暑罱葺；暑昌；眚薯昌暑暑暑暑昌暑；i 置| 目i 鼻宣葺e 宣宣宣皇昌| 昌；| 摘要 随着实时数据库研究的逐步兴起，现实生活中对它的应用也越来越广泛， 诸如电子商务、空中交通管制、程控电话交换、电力调度等应用都需要它的 支持。然而。在实时数据库中还存在着许多仍未解决的问题，使得实时数据 库如此难以实现酶关键在于截止期和一致性这一对矛盾。实时数据库中最重 要的特性就是实时性，而它的实时性能取决于很多因素，但对于一个给定的 系统配置，决定实时性能的最基本因素是对数据存储进行调度的并发控制算 法。近年来很多研究人员致力于设计适合实时数据库系统的并发控制算法 然而，现有的实时事务并发控制算法依然存在浪费的执行和不必要的重启等 问题。 本文着重研究了实时事务乐观并发控制算法的优化问题，在对动态调整 串行化瞩亭的0 c c 髓算法进行充分分析之后，给出了一个o c c - c p t i 算法， 该算法能解决一定程度上的不必要重启的问题另外，以抛弃冲突事务策略 为研究原型，根据其在不同的系统负载情况下表现出不同的性能，给出了一 个条件虚抛弃策略，并将该策略与o c c 删算法结合起来给出了 o c c - c f f i - c v d 算法，该算法可以有效地解决一些浪费的执行问题 最后通过仿真实验对改进后的算法进行了各方面的验证，从三种算法的 错失率曲线图可以看出o c c - c p t i 算法和0 c c 茁l y l l c 、r d 算法的错失率的确 少于o c c - t i 算法，达到了优化的目的。 关键词：实时数据库；并发控制；时间戳；串行化顺序 哈尔滨工程大学硕士学位论文 a b s tr a c t r e a l - t i m ed m a b a s es y s t e m ( 1 l ：t d b s ) i su s e dm o r ea n dm o r ew i d e l yi nd a f f y l i f ew i t hi t sd e v e l o p m e n t sa n dr e s e a r c h e s s u c ha se - b u s i n e s s ，a i rt r a m cc o n t r o l s y s t e m , t e l e p h o n e 羽概1 1 a n de l e c t r i c i t ym m s p o 吨b u tt h c l e a r cs t i l l $ o m c p r o b l e m sm l s o l v e di nr t d b s n cp r o b l e mt h a tm a k e sr t d b sh a r dt ob e 髓8 l 切e di st h e i n c o n s i s t e n c y b c t w o t m d e a d l i n ea n dc o n s i s t e n c y t h em o s t i m p o r t a n tc h a r a c t c r i s f i ci nr t d b si sr e a l - t l m ew h i c hd l = p 锄d so nm a n yf a c t o r s f o rag i v e ns y s t e mc o n f i g u r a t i o n b a s i cf a c t o r st h a td e m i n ep 盱f 0 珊瑚o f r e a l - t i m ea r cc o n c u r r e n c yc o n 血o la l g o r i t h m sf o rs c h e d u l i n go f = o r i n sd a l 乱 r e c e n t l y , m a n yr e s e a r c h e r sf o c u so i ld e s i g n m gt h ec 0 临加玎e n c yc o n t r o la l g o r i t h m s w h i c ha 阳s u i t a b l et or t d b s h o w e v e r , t h ec u r r e n ta l g o r i t h m ss t i l lh a v et h e p r o b l e m ss u c h a sw a s t e de x e c u t i o na n du n n e c e s s a r yr e s t a r t a f t e r 锄a i y 五n gd y m m ca d j u = m e l 吐o fs c r i a l i 丝t i o no r d e r 羽g 叫谢吼，t h e a l g o r i t h mo fo c c c 阿，w h i c h 锄s o l v ep r o b l e m so fu n n e c e s s a r y 删a n s 墙 g i v 乱a f t e rs t l y i n gd i s c a r dc o n f l i c tt r l i 删j o np o l i c y 叠c o n d i t i o nv 主m l a l d i s c a r dp o l i c yi sg i v = la n do c c f n c v d a l g o r i t h mi sg i v e nb yc o m b m i n g t h ep o l i c yw i t ho c c - c p t i t ka l g o r i t h m 渤s o l v ee f f e c t i v e l yp r o b l e m so f w a s u = de x e c u t i o 也 f i n a l l y , t h e s i m u l a t i o n s a 砖i m p l e m e n t e dt o e x a m i n et h eo c c - ( ：p h a l g o r i t h ma n do c c - c p t i e n da l g o r i t h n lc o m p a r i n gt h e 越i s sr a t i oc u r v eo f t h e t h r e ea l g o r i t h m s i ti sc l e a rt h a to c c c p t ia l g o r i t h ma n do c c - c p n c v d a l g o r i t h ma r e b e t t e rt h a nt h eo c c - t i t h ea i mi ss c h i e v e 正 k e f c o r d s ：r e a l t i m ed a t a b a s e s e r i a l i z a t i o no r d e r 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：叩引月7 日 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 计算机科学技术是众多自然科学中发展最快的领域之一。而数据库技术 则是计算机科学技术中发展最快、应用最广泛的技术之一在现代的信息系 统中，数据库充当了后台的提供者的角色，是数据库所有功能模块的核心。 实时数据库系统( r e a l t u n ed a t a b a s es y s t e m ，r t d b s ) 是数据库与实时系统 相结合的数据库，是其数据和事务都具有显式时间约束的数据库在实时数 据库系统中，系统的正确性不仅依赖于逻辑结果的正确性，而且还依赖于产 生逻辑结果所需要的时间的正确性实时数据库与传统数据库的区别主要表 现在；实时数据库不仅要维护大量的共享数据以及控制数据。还需要保证事 务的时间性、数据的实时性它在化工、电力、航空、通信以及程控股票交 易等系统中起着重要的作用。 时闻是实时系统中一个很重要的系统资源，它在系统的实时任务上表现 出很多不同的特征例如；启动时间，运行时阀和截止时间等，实时系统要 尽可能保证在任务的截止时间之前完成任务。快速性是一个基本要求，各实 时任务都要能尽量快速地得到响应而可预测性n 恻是实时系统中的一个很重 要的特征，即系统能够对实时任务的执行时间进行预判，从而决定是否能满 足时限方面的要求在研究和设计实时系统时。它的这些特征使得系统在实 现上变得相当困难，所以实时数据库系统的发展非常的缓慢n - 目前，市场上 还没有完全成熟的通用商用r m s 出现，只有适用于各个行业个别应用方 面的l 渤s ，比如国家电力公司自动化研究所开发的n s i s 石油化工生产实 时数据库产品和中国大庆金桥信息技术公司开发的c c 栅b 系统等等 实时数据库系统并非是数据库系统和实时系统的概念、机构、工具等的 简单集成，而需要对一系列问题进行研究与决策：数据和数据库的结构与组 织；事务的截止时间的软硬性；事务的优先权分派、调度和并发控制的协议 哈尔滨工程大学硕士学位论文 和算法；i o 调度和恢复；数据和事务特性的语义及这种语义与一致性、正 确性的关系等等m 、 一 r t d b s 中的实时事务并发地运行和存取数据，事务彼此之间存在着相互 的干扰和破坏并发控制技术正是用来控制并发事务间的这种相互干扰以保 证数据库的一致性。由于实时数据库系统具有时间限制的特殊性，因此 r t d b s 的并发控制协议、方法与机制都需另行开发。在目前的并发控制协议 中，可串行化是最流行的标准。但在r t d b s 中，有时需要牺牲可串行化。 这样傲的依据是在有些应用中，数据的生命期常常很短，由并发事务引入的 任何不一致性不会在数据库中扩散得很厉害，因此可以使用补偿事务进行一 致性维护。但是，对于有些应用来说，可串行化仍然是维护数据库一致性的 较好选择 本文主要研究了基于时间戳( t i m e s t a m p ，t s ) 的动态调整串行化顺序 算法和抛弃冲突事务策略，首先对o c c - t i 算法进行了比较深入的探讨，分析 了o c c - t i 算法的缺点，采用了一种新的最终时间戳的选择方法，减少了重新 启动的事务的数量，一定程度上保证了高优先权事务的执行，并给出了 o c c - c p t i 算法另外又给出了条件虚抛弃策略的方法，将抛弃策略与重启策 略更好的结合，也就是将条件虚抛弃策略与o c g c p l l 算法相结合给出了更完 善的o c c - c p t i c v d 算法该算法在整个系统负载下都将表现出相当好的性 能，一方面减少了不必要的重启，另一方面又减少了浪费的执行文章最后 通过实验证明了新给出的两个算法在错失率指标上的优越性 1 2 国内外研究现状 。 实时数据库的概念是从2 0 世纪7 0 年代中期开始出现的。1 9 7 5 年，美国 的h o n e yw e l l 公司首先推出d e s ，从此d c s 技术和产品的发展推动了工业 自动控制领域全面发展到集散控制系统阶段，在此基础上结合了数据库和管 理信息系统的概念，引发了实时数据管理和实时数据库概念的出现。 国际上从2 0 世纪8 0 年代后期开始较系统的发表了有关实时数据库的论 文。9 0 年代中期。爱尔兰的r h o d e 大学以及美国麻省理工学院开始重点研究 实时s q l 语言，开创了实时数据库研究的新领域。进入2 l 世纪后，芬兰的 2 哈尔滨工程大学硕士学位论文 赫尔辛基大学计算机科学院的j a nl i n d s t r o m 在文献【4 】和文献【5 】中提出了一 些关于实时数据库中的乐观并发控制算法。包括动态调整串行化顺序算法的 一些想法及改进 国内从2 0 世纪9 0 年代初，随着国内工业界对d c s 的大量引进和应用， 国内科技教育界率先开始研究实时数据库理论。其中比较知名的有华中理工 大学刘云生教授，他曾发表过很多篇关于研究实时事务的并发控制和调度的 论文，并指导研制了取名为a r ：i 孓1 型实时数据库系统的雏形w 。进入2 l 世 纪后，中国科学院软件研究所的一些研究学者王强等人也提出了很多实时数 据库的并发控制算法方面的改进与优化思想，同时还自主开发研制出一个完 整的实时数据库测试平台r t d b t p ，用来测试实时数据库的性能。 1 3 实时数据库概述 实时数据库是其数据和事务都具有时间属性或显式的时间约束的数据 库。在实时数据库中，事务处理的正确性不仅依赖于逻辑结果的正确性，而 且依赖于产生逻辑结果的时间的正确性 实时数据库中的数据对象是用一个有效的时间问隔来标识的，主要用来 表示该数据对象可以在这段时问间隔内非常真实地反映当前环境因此，任 何与该数据对象有关的事务处理必须在有效时间间隔内完成。这也就表示实 时数据库事务处理的时间其有可预测性”t 1 3 1 时间特性 实时数据库在实时系统中主要是进行数据的组织以及管理在与外界环 境进行交互时，外界环境产生输入信号。实时数据库需要在限定的肘问间隔 内接受这种输入信号用以表示实时数据库接受外界环境的数据输入；当外界 环境产生控制信号，则要求实时数据库接受这个控制信号并在限定的时间内 产生进一步的控制输出因此在设计实时数据库系统时必须要考虑以下时间 特性： 。 ( 1 ) 实时数据库中的很多数据只是暂时的，一旦时间发生了推移，这些 3 哈尔滨工程大学硕士学位论文 数据将不能再反映外界环境的状态，成为了无效数据 ( 2 ) 实时数据库系统必须及时地完成活动并产生正确的结果。当规定时 间来到时，实时数据库系统中要有一些相关联的活动来进行处理因此，完 成活动并不简单的要快，而且要求要及时 ( 3 ) 传统的数据库只要求逻辑一致性，而实对数据库在要求有逻辑一致 性的同时还要求有时态一致性等等实时数据库中有四种一致性约束：数据 逻辑一致性、事务逻辑一致性、数据时态一致性和事务时态一致性。 ( 4 ) 实时数据库系统包含了传统数据库和实时系统两者的特性，如图 1 1 所示一方面，它必须保证数据一致性。数据一致性通常用串行性观点来 实现：另一方面，它必须满足时间限制，重要的不是事务在截止期前多长时 间完成，而是事务是否能在其截止期内完成。 1 3 2 性能指标 图1 i 实时系统与数据库系统的交互 错失率( m i s sr a t i o ，m r ) 是实时数据库系统中最重要的性能指标之一 在实时数据库系统中，系统的性能指标不是吞吐量和平均响应时间，而是错 失率由此可见。系统错失率是本文用来衡量实时事务并发控制算法性能的 最为主要的评测参数。 对于实时数据库系统中存在的三种不同类型的实时事务( 硬实时事务， 软实时事务和固实时事务) 来说，对错失率的要求也大为不同硬实时事务 要求保证事务的截止期，因此系统要求硬实时事务的错失率必须为o ；而对 于固实时事务与软实时事务来说，可以允许少量的事务错失截止期，因此可 4 哈尔滨工程大学硕士学位论文 以要求部分事务的错失率小于一定的比例这也就是意味着，不同的事务要 求不同的服务质量( q u a l i t yo fs e r v i c e ，q o s ) ，因此不同的错失率需求是混 合实时事务的q o s 规范之一例如，可以定义o o s - m a = f 珏h - - - - 0 ) m r s 1 0 ，这就要求系统必须保证所有硬截止期事务满足截止期，而软实 时事务的错失率必须小于等于1 0 。, 4 “ 1 4 实时数据库前沿课题与展望 随着实时数据库系统研究的逐步兴起，许多学者和研究人员都开始学习 和研究实时数据库系统相关方面的理论和技术，并取得了丰硕的成果。但是， 如何实现研制实时数据库系统的初衷，即如何在维护数据库一致性的基础上 确保实时事务处理在截止期之前完成，仍是一个不可回避的课题。文献1 1 0 中给出了实时数据库系统的研究领域所呈现出的几个特点： ( 1 ) 事务调度算法研究的发展 在实时数据库的起步阶段，研究最多的是单独处理某一种实时事务( 硬 实时事务或软实时事务) 的事务调度算法，随着实时数据库的不断应用扩展， 处理事务的复杂程度也逐渐加大，这时主要需要处理两种实时事务，甚至还 要同时处理非实时事务。如何制定新的、有效的和适应复杂事务的实时数据 库事务调度算法将成为未来的研究方向 ( 2 ) 并发控制协议研究的发展 现阶段，研究人员已经提出了很多的并发控制协议，这些协议分别适用 于各自不同的环境现在需要做的工作就是对各种并发控制协议在典型应用 环境中的表现做出评价虽然与悲观并发控制相比，乐观并发控制的实时性 要好一些，但还应该研究减少前者导致的事务处理重启次数的方法，以节约 系统资源并进一步提高实时性能。 ( 3 ) 内存实时数据库的发展 。，。 目前的实时数据库主要是建立在磁盘数据库的基础上的磁盘数据库的 使用有它的优点，同时在具体实现上存在了很多问题在常驻磁盘数据库系 统中，磁头的定位时间、缓冲区管理和页面错误等都会导致在平均执行时间 和最坏情况下执行时阋的估算出现很大误差。如果将实时数据库建立在主内 s 哈尔滨工程大学硕士学位论文 存数据库的基础上，那么在事务处理过程中就可以避免以上这些不确定因素， 从而可以更好地满足实时事务处理的要求“时 1 5 课题的来源及主要工作 1 5 1 课题的来源及背景 传统数据库中事务调度与处理方法的目标是最大化事务吞吐量或者降低 平均响应时阋。但是，由于数据的时态属性以及应用环境带来的时间性需求， 实时数据库系统需要处理具有时间约束的事务，这些时闻性需求通常表现为 周期或者截止期必须注意的一个关键点是实时并不是简单地意味着快，而 是要求系统的行为具有可预涮住可以说，实时意味着需要明确地处理时间 约柬，即使用时间认知的协议来处理与事务相关联的截止期与周期。进一步 地说，实时数据库系统中的事务调度与处理目标也就不同于传统的数据库系 统，而是最大程度地满足事务的截止期。 为满足实时性能的实时调度算法在实时操作系统中已得到开发，操作系 统实时调度与数据库的调度有不同的前提与目的，致使有不同的意义，操作 系统实时调度并不考虑数据资源一致性，而传统数据库中事务调度与管理， 又没有考虑各个事务不同的时间约束，故有必要结合二者的思想，提出新的 实时事务并发控制协议要考虑事务实时约束，就必须引入实时语义信息， 目前实时系统中最重要的实时语义信息即为优先权，时间约束被反映成优先 权，尽管优先权概念已被作为实时操作系统中调度策略的基准，但在数据库 传统应用领域长期以来根本没有受到注意，要研制实时并发控制必须引入优 先权的概念，然而传统实时操作系统中抢占恢复的优先权调度方式并不 适合于实时数据库系统( 若采用抢占恢复方式，在实时数据库中可能会 导致性能下降，这是由于抢占意味着被抢占事务必须中止撤消且执行时又重 启，浪费大量执行时婀，另外消去数据库中不一致性也比较费时间) 为此必 须研制满足实时事务需要的并发控制机制，在可串行化模型中增加实时语义 信息，既保证事务执行的可串行化，以维护数据库的一致性，又要满足事务 6 哈尔滨工程大学硕士学位论文 的优先权约束，以确保实时性 1 5 2 论文主要工作 本文在实时乐观并发控制算法的基础上，一方面对已提出的基于时问戳 技术的动态调整串行化顺序算法o c c - t i 进行深入的探讨，研究其读、写及 验证阶段的特点，分析其存在的一些不必要的重启以及缺乏对优先权信息的 描述方面的不足，给出了新的基于时间戳的动态调整串行化顺序的算法 o c d c p l r i 。该算法延用了乐观实时并发控制算法中事务执行的三阶段思 想和时间戳技术，从最终时间戳选择机制和优先权机制上对o c c t i 算法进 行改进。改进的主要目的是尽量满足实时事务的截止期以更进一步的减少不 必要重启数目从而降低系统的错失率另一方面对乐观并发控制中的抛弃冲 突事务策略进行了深入的分析。提出了改进后的策略一条件虚抛弃策略， 并在之前提出的o c c c 肌算法的基础上结合该策略得出了o c c c 阴册 算法，该算法在一定程度上解决了不必要的重启和浪费的执行两方面的问题 最后通过仿真实验验证了o c c - c p t i 算法和o c c 栅c 、，d 算法错失率均小 于o c c 棚算法，故而在一定程度上提高了系统的性能 1 5 3 论文的组织 本文按照下面几个部分组织。 第l 章介绍了实时数据库的基本概念，简单阐述了实时数据库的时问特 性及实时数据库的性能指标等等，分析了国内外相关课题的研究现状对实 时数据库的前沿课题作了一下展望，并阐明课题的来源和主要研究工作。 第2 章详细说明了并发控制理论的概念，并对可串行化理论和可恢复性 理论进行了简单的描述同时扩展到具体的实时事务的并发控制，介绍了实 时事务的相关属性及性质，实时事务并发控制的特点及串行化规则，最后阐 述了并发控制算法中存在的待解决的问题。 第3 章描述了乐观并发控制算法中出现的两个关键问题的解决方案 动态调整串行化顺序和抛弃冲突事务策略动态调整串行化顺序算法中介绍 哈尔滨工程大学硕士学位论文 了比较有代表性的基于时间戳技术的o c c - t i 算法，并对其各阶段进行了详 细深入的讨论。然后详尽地描述了抛弃冲突事务策略，对比其缺点和优点 最后分析了两种策略的适应条件 第4 章综合以上各部分内容，确定了o c c - t i 算法的改进及优化的具体 方向。提出了o c c - i 算法的缺点，并根据其缺点，给出了新算法的具体描 述。同时改进了抛弃冲突事务策略，提出了条件虚抛弃策略，并将该策略与 之前所提出的新算法结合，得出了更完善的算法 第5 章通过仿真实验验证了o c c - c p t i 算法和o c c - c p t i - c v d 算法性能 的提高，达到了预期目的 哈尔滨工程大学硕士学位论文 i i 暑鲁阜| i 暑暑暑i 皇暑暑；暑置暑宣昌；i 暑i ；宣暑；昌暑暑；宣i 暑；i 茸皇昌暑譬；j 薯暑暑昌；罱i 第2 章实时并发控制理论 ； 数据库事务之间的相互影响可能导致数据库状态的不一致要做到既使 各个事务能保持状态的正确性，而且也没有任何故障发生，那么不同事务中 各个步骤的执行顺序必须以某种方式进行规范。保证并发执行的事务能保持 一致性的整个过程称为并发控制并发执行的事务要保持数据库状态的正确 性，需要满足可串行性的要求。 2 1 并发控制理论 并发控制是任何多用户数据库管理系统必不可少的部分，其作用是正确 协调同一时间里多个事务对数据库的并发操作，以保证数据库的一致性和完 整性并发控制是通过调度来确保事务的并发执行的效果等同于没有并发执 行时的执行效果，也就是使事务的并发执行调度等价于事务的某个串行调度， 从而确保数据库的一致性调度的可串行性保证了数据库在事务执行之前和 事务执行之后都是一致的数据访问冲突是不可避免的，而且由于死锁的存 在，有些事务可能被夭折，如何保证事务在天折之后能够恢复到事务执行之 前的状态对系统的正确性是很重要的。可恢复性将傈证事务在夭折时。能够 将系统恢复到事务执行之前的状态；当系统出现意外故障而崩溃时，可恢复 性保证系统能够恢复到以前的某个正确状态 2 1 1 可串行化理论 并发控制的可串行化理论主要包括两方面：冲突可串行化m ，与视图可串 行化m ， 1 冲突可串行化 若五与5 是在相同的数据项d 上的两个不同事务的操作，五与再中至少 有一个是w m 指令时，则五与磊是冲突的 哈尔滨工程大学硕士学位论文 如果调度日可以经过一系列非冲突指令交换转换成日，则称日与日是 冲突等价的由冲突等价的概念引出了冲突可串行亿的概念：若一个调度胃 与一个串行调度冲突等价，称调度是冲突可串行化的 2 视图可串行化 。 视图等价也是基于事务的r e a d 和w r i t e 操作的，是一种比较宽松的等价 形式。考虑两个调度日与日，两个调度所涉及的事务集是一样的，如果满足 以下三个条件，则调度胃与曰称为视图等价。 ( 1 ) 对于每个数据项d ，若事务乃在调度日中读取了d 的初始值，那 么在调度日，中乃也必须读取d 的初始值； ( 2 ) 对于每个数据项d ，若事务乃在调度日中执行r e a d ( d ) 并且读取 的值是由事务乃执行w r i t e ( d ) 产生的，则在调度日中，t j 的r e a d ( d ) 操 作读取的值d 也必须是由乃的同一个w r i t e ( d ) 产生的； ( 3 ) 对于每个数据项d ，若在调度日中有事务执行了最后的w r i t e ( d ) 操作，则在调度日中该事务也必须执行最后的w r i t e ( d ) 操作 条件( i ) 与( 2 ) 保证了在两个调度中的每个事务都读取相同的值，从 而进行相同的计算。条件( 3 ) 与条件( 1 ) 、( 2 ) 一起保证两个调度得到相 同的最终系统状态。 视图等价的概念引出了视图可串行化的概念：如果某个调度视图等价于 一个串行调度，则这个调度是视图可串行化的。 3 两种可串行化的关系 每个冲突可串行化调度都是视图可串行化的，但并不是所有的视图可串 行化调度都是冲突可串行化的m 2 1 2 可恢复性理论 数据库的可恢复性理论1 是并发控制理论中同样比较重要的一部分它 体现在具体的事务并发控制处理中是这样的：如果一个事务瓦夭折了，则必 须撤消该事务的影响以确保事务的原子性，让数据库系统恢复到事务乃开始 执行之前的状态。在允许事务并发执行的系统中，还必须确保依赖于乃的任 何事务也天折，从而保证事务调度是可恢复的。为了维护数据库的可恢复性， i o 哈尔滨工程大学硕士学位论文 对于每个事务乃，如果事务乃被天折，则该事务乃对数据库系统的所有影响 都将被撤销，而且不会破坏其它已提交事务对数据库系统的所有影响。一个 事务调度日是可恢复调度，如果对于任意两个事务乃和乃，乃读取了由乃 写的数据，那么乃先于乃提交，即c f - c j ( 其中e r e 髓是事务乃的提交操作) 如果乃读取了由乃写的数据，乃提交了而乃没有提交，一旦乃由于某种原因 被夭折，则数据库需要恢复到事务乃执行之前的状态，同时也必须乃回滚， 然而乃已经提交无法进行回滚操作，这样的事务调度是不可恢复的 2 2 并发控制协议 近年来，研究人员们提出了很多种不同的并发控制协议。并发控制协议 的主要目的是为了解决事务处理过程中出现的数据访问冲突。事务访问数据 库主要包括两种操作：读操作和写操作。所谓读操作指的是事务读取数据库 中的某个值，但不进行更改；所谓写操作指的是事务永久地更改数据库中的 某个值。如果在同一时间，两个不同的事务访问同一个数据对象，且其中的 一个事务包含对该数据对象的写操作，就会发生冲突目前，并发控制协议 主要包括两大类策略： ( 1 ) 等待 停止其中一个事务引起冲突的操作使其停留在等待状态，直到另一个事 务的操作完成为止 ( 2 ) 回滚 撤销引起冲突的操作，或者将事务对数据库所有已完成的操作全部撤消， 事务重启。回到开始时的状态。回滚策略被认为是乐观的，它假设事务发生 冲突的可能性很小使得回滚很少发生。 1 基于等待策略的并发控制协议 。 在基于等待策略的并发控制协议中，数据库为事务提供数据锁，如果一 个事务申请加锁时，数据对象已经被另一个事务锁住。则该事务只能等待 为了减少读取数据所需时闭，使用7 两种数据锁： ( 1 ) 读锁：被加锁的数据对象只能读不能写，也不能加写锁，直到解锁 为止； l i 哈尔滨工程大学硕士学位论文 ( 2 ) 写锁：数据对象只能被加锁的事务读写，其它事务不能访问，直到 解锁为止 在基于等待策略的并发控制协议中，两阶段封锁协议( t w op h a s e i d c k i n g ，2 p l ) m ，占有重要地位。在这里就不予详述了 2 基于回滚策略的并发控制协议 在基于回滚策略的并发控制协议中，数据库并不提供数据锁此类协议 又被称为乐观的并发控制( o p t i l n i s t i c c o n c t u r e n e y c o n t r o l ，o c c ) 相应的， 基于等待策略的并发控制协议被称为悲观的并发控制( p e s s i m i s t i c c o n 舢c y c o n u o l ，p c c ) w o c c 的事务处理过程分为四个阶段： ( 1 ) 读：事务读取数据对象的值并将其写入局部变量中，需要注意的是 局部变量只能表示数据对象的历史状态； ( 2 ) 计算：事务利用读阶段获得的副本数据进行计算，并将计算结果存 入相应的局部变量中； ， ( 3 ) 验证：检查事务处理是否违反了可串行化要求，若违反了，则对事 务迸行回滚操作；否则就进入提交阶段； ( 4 ) 提交：将所有因事务处理而变更的数据从局部变量中复制到数据库 中。 这四个阶段经常会被合为三个阶段，其中的读和计算阶段合称为读阶段 其中验证阶段是最重要的。它的处理过程直接关系到并发事务是夭折，是重 启，还是提交。o c c 认为事务之间不会发生冲突。但如果真的检测到数据访 问冲突，o c c 需要检测并解决冲突，以便维护数据的一致性和完整性，值得 注意的是，在o c c 中冲突检测就是在验证阶段进行的” 2 2 1 乐观并发控制 乐观并发控制算法是一种乐观协议，其中的乐观指的是系统认为事务之 问不会发生数据访问冲突因此该算法允许事务无阻碍地执行直到全部操作 完成，然后在提交之前进行验证，如果通过了验证就提交，否则就重启或者 夭折。该算法中事务的冲突检测和冲突解决并没有在发生数据访问冲突那一 刻立即执行，而是延迟到了事务提交之前每个事务都有一个私有缓存，私 1 2 哈尔滨工程大学硕士学位论文 i 有缓存的作用主要是使事务可以独立的对数据进行访问，不受任何干扰事 务的读写操作都是针对私有缓存中的数据，因此，数据库中的数据此时并没 有任何改变当事务未被检测到有数据访问冲突而顺利通过验证时，才将事 务所做的修改从私有缓存中提交给数据库。 乐观并发控制算法的精髓主要体现在三阶段思想，具体的三个阶段分别 是： ( 1 ) 读阶段：事务将要访问的数据复制到它的私有缓存中，并在私有缓 存中对数据进行相应的读写操作； ( 2 ) 验证阶段：主要包括进行冲突检测和冲突解决两部分。如果检测出 数据访问冲突，则重启或者夭折验证事务，否则验证事务通过验证并进入写 阶段； ( 3 ) 写阶段：事务将所做的修改从私有缓存提交到数据库中 值得注意的是，在验证阶段检测数据访问冲突的方法有两种：后向验证 和前向验证。两种方法都是以验证事务为研究对象，在后向验证中，检测验 证事务跟已提交事务之闻的数据访问冲突；而在前向验证中，检测验证事务 跟活动事务之间的数据访问冲突传统的乐观并发控制算法采用的是后向验 证方法“” 2 2 2 动态调整串行化顺序 事务重启是乐观并发控制算法中存在的最大问题之一事务一旦重启， 就是意味着事务之前执行的所有操作都将无效，需要重新执行，这样会浪费 系统资源。可见，提高乐观并发控制算法性能的一个最重要的机制就是减少 重启事务的次数。减少重启事务的方法就是动态地重新定义串行化顺序为 了保证算法调度的可串行性。如果验证事务必须串行化在活动事务之前，那 么必须满足两个条件： ( 1 ) 无覆盖：验证事务不会覆盖活动事务的写； ( 2 ) 无读依赖：验证事务的写不会影响到活动事务的读阶段u ， 较早的一些乐观并发控制算法认为事务的串行化顺序在执行过程中保持 不变。比如：o c c b c 算法町。它要求事务最终的串行化顺序必须与事务进行 1 3 哈尔滨工程大学硕士学位论文 验证操作的顺序一致，否则认为事务调度是不可串行化的这种观点使得一 些不会破坏数据库一致往的调度也被认为是不可串行化的，从而导致了不必 要的重启为了解决这个问题，研究人员提出了动态调整串行化顺序 ( i ) y n a m i e a d j u s u n e n t o f s e r i a l i z a t i o n o r d e r ，d a s o ) 方法该方法能够在动 态执行过程中不断地调整活动事务的串行化顺序，以寻求无需重启事务的串 行化顺序，只有在找不到串行化顺序时才重启冲突事务来保证数据库的致 性 用乃一乃表示乃串行化在乃之后。假设事务瓦正在进行验证操作，事务死 为任意一个活动事务，动态调整串行化顺序方法中串行化顺序调整规则如下： ( 1 ) 事务b 和事务l 之问的读一写冲突可以通过将它们之间的串行化顺 序调整为兀一死来解决。这样，事务瓦的读操作不会受到事务死的写操作影响。 这种类型的串行化调整称为前向调整。 ( 2 ) 事务兀和事务瓦之间的写读冲突可以通过将它们之问的串行化顺 序调整为死一瓦来解决这意味着，事务死的读阶段被放置到事务兀的写阶段 之前。这种类型的串行化调整称为后向调整。 ( 3 ) 事务巧和事务死之间的写一写冲突可以通过将它们之间的串行化顺 序调整为瓦一死来解决这样，事务兀写的数据就不会覆盖事务死写的数据 此类型的串行化调整也称为前向调整m 2 3 实时事务并发控制 2 3 1 实时事务的性质 事务是实时数据库系统并发执行的基本单位m 它是一个操作序列，是 查询和修改数据库的进程为了保证数据的完整性，通常要求事务具有五个 性质： 一 ( 1 ) 原子性：即事务要么全部执行，要么全部不执行： ( 2 ) 一致性：数据库在事务执行之前是一致的，在事务执行之后依然是 一致的； 1 4 哈尔滨工程大学硕士学位论文 ( 3 ) 隔离性：并发执行的事务感觉不到系统中有其它事务在执行，一个 尚未完成的事务在提交前不能向其它事务提供其结果； ( 4 ) 串行性：若干个事务并发执行，其执行结果与它们以某个串行顺序 执行的效果相同； ( 5 ) 持久性：即一旦一个事务执行后，即使以后出现故障，系统也必须 保证其结果不丢失 传统的数据库系统由于其事务的原子性、一致性和隔离性等性质，强调 的是逻辑结果的绝对正确性，根本没有涉及到时间的相关属性但在实时数 据库中，时间是最重要的属性之一w 也正是因为如此，在实时数据库系统 中的事务与传统数据库中的事务有着根本性的区别，实时事务的特性主要表 现在： ( 1 ) 正确性：传统事务只是注重逻辑结果的正确性，而实时事务注重的 正确性不仅在于逻辑结果的正确性，而且要求时问正确性； ( 2 ) 可预测性：时间属性要求实时事务具备预测执行时间的能力，这样 才可以确保事务能够满足截止期，保证系统正常运行； c 3 ) 可恢复性：当事务由于错失截止期或数据访问冲突而被夭折或重启 时，需要将该事务在被夭折或重启之前的所有操作全部取消，使得数据库恢 复到未执行该事务的状态； ( 4 ) 重要性：重要性不同的事务将会给系统带来不同的价值，为了实现 系统的高价值，应该让重要性高的事务优先执行 2 3 2 实时事务的属性及类别 首先来看一下实时事务的一些主要属性： ( 1 ) 绝对截止期：要求事务在绝对截止期到来之前提交； ( 2 ) 到达时间：系统接收到该事务请求的时间； ( 3 ) 相对截止期；事务的绝对截止期与事务的到达时间的差； ( 4 ) 执行时间：并非事务的实际执行时间，而是估计的事务执行时间； ( 5 ) 剩余执行时间：事务执行过程中，估计韵剩下需要执行的时间； ( 6 ) 松弛时间：事务的相对截止期与事务的执行时间之差； i s 哈尔滨工程大学硕士学位论文 ( 7 ) 价值：即事务的关键性，该事务相对其他事务的重要程度； ( 8 ) 完成时间：事务提交完成的时间 实时事务的这些属性对于解决数据访问冲突起着关键的作用当事务发 生数据访问冲突时，系统将执行相应的操作以保证其能够正确运行比如说： 系统会依据事务的截止期、事务的执行时间和事务的价值等事务的属性信息 来选择事务进行夭折或者重启的处理因此，在实时事务的并发控制算法中， 这八个属性信息对于系统的错失率来讲是至关重要的w 接下来主要看一下实时事务的类别划分，这里主要介绍两种分类方式 从事务使用数据的方式考虑，实时数据库中的事务与传统数据库一样， 包括三种事务类型： ( 1 ) 只写事务，采集外界环境的数据并将其写入实时数据库中； ( 2 ) 更新事务，将当前读写操作产生的新数据提交到实时数据库中： ( 3 ) 只读事务，从实时数据库中读出数据m ， 按照实时事务时间限制( 截止期) 的性质，即事务错失截止期后所带来 的后果将事务分为三类：硬截止期事务、软截止期事务与固截止期事务不 同的事务满足截止期会带给系统不同的价值： ( 1 ) 硬截止期事务( 硬实时事务) ：事务在错失截止期之后会导致恶果 ( 价值函数将是一个很大而且不断增加的负值) ，它对应于最关键的活动： ( 2 ) 软截止期事务( 软实时事务) ：事务在错失截止期之后仍会有一定 的价值，且价值不断下降，直到某个时刻( 称为最终有效时问) 降为零，此 后保持为零不变； ( 3 ) 固截止期事务( 固实时事务) ：事务在错失截止期之后其价值函数 为零，这类事务在错失截止期之后将被抛弃 这三类实时事务对应的实时系统分别称为硬实时系统、软实时系统和固 实时系统m ， 2 3 3 实时事务并发执行的特点 实时效据库中事务并发执行的主要特点： ( 1 ) 并发执行的事务具有时间约束和依赖性。实时数据库系统中的事务 1 6 哈尔滨工程大学硕士学位论文 具有显式的时间约束，而其中实时数据的一致性包括逻辑结果的一致性和时 何的一致性此外，当它们并发执行时，事务之间可能存在与时间有关的依 赖关系。 ( 2 ) 紧迫程度不同的事务处理要求不同，所有的硬实时事务要求能够在 截止期之前完成，同时要尽量减少错过截止期的圃实时事务和软实时事务数 量。在实时数据库系统中，实时事务分作硬实时事务，固实时事务和软实时 事务。为了避免给系统造成灾难性的破坏，应尽量减小硬实时事务超过截止 期的机率。而对于圃实时事务和软实时事务来说，超过截止期并不会造成像 硬实时事务一样灾难性的破坏，但是会浪费系统资源，降低系统性能。 ( 3 ) 事务的调度是基于可抢占机制的。紧迫程度高的事务可以抢占系统 资源，阻止运行中的事务继续进行。若因为事务的抢占导致了数据的一致性 遭到破坏，则应保证紧迫程度高的事务继续运行，而被抢占的事务则可以按 照一定的冲突解决策略重启或者夭折 ( 4 ) 系统性能的目标不是提高反应速度和系统吞吐率，而是满足截止期 事务的比率。实时数据库系统中的每个事务都有时问约束，最直接的体现就 是事务的截止期属性错失了截止期的实时事务就会失效，因此，系统更倾 向于保证更多的事务在截止期内完成“1 2 3 4 实时事务的串行化规则 在动态调整串行化顺序算法中，事务的串行化顺序关系是极为重要的， 而决定事务串行化顺序的因素就是事务的串行化规则。事务的串行化可以基 于开始时间、完成时间或者元组存取顺序等等下面是经常用来定义串行化 顺序的方法： ( 1 ) 事务开始时阗：每个事务在执行之前分配一个时阅戳，如果基于这 个时间戳顺序的事务不能通过验证，则被夭折。， 。+ ( 2 ) 事务完成时间：每个事务在执行完后分配一个时间戳，如果基于这 个时问戳顺序的事务不能通过验证。则被夭折或重启。研究表明事务的串行 化顺序基于开始时间比基于完成时间可能导致更多的事务夭折或重启。乐观 并发控制一般采用这种方法。 1 7 哈尔滨工程大学硕士学位论文 ( 3 ) 元组存取顺序：两阶段锁采用这种方法来定义事务的串行化，不过 在所有的锁在提交时被释放的倩况下。基于元组存取顺序与基于事务的完成 时间的串行化顺序是等价的 本文所采用的事务的串行化定义正是依赖于事务的完成时间来实现的。 2 4 实时并发控制算法存在的问题 在实时数据库系统中，事务处理和并发控制都必须以事务的优先权为依 据。传统的事务处理和并发控制方法运用在实时环境中会导致一些问题。 2 4 1 基于锁的并发控制算法存在的问题 基于锁的并发控制算法存在两个主要问题：浪费的重启和浪费的等待。 浪费的重启：如果一个低优先权事务因为与一个高优先权事务发生数据 访问冲突而被重启了。而之后这个高优先权事务却因为错失截止期而被抛弃 了那么先前低优先权事务的重启就是浪费的，是浪费的重启 浪费的等待：如果一个低优先权事务因为与一个高优先权事务发生数据 访问冲突而处于等待系统资源状态，而之后高优先权事务却因为错失截止期 而被抛弃了。那么先前低优先权事务的等待就是浪费的，是浪费的等待n ” 2 4 2 乐观并发控制算法存在的问题 乐观并发控制算法同样存在的两个关键问题：浪费的执行和不必要的重 启 一 浪费的执行：首先，如果一个事务错失了截止期，那么该事务在错失截 止期之前的所有执行都是浪费的。其次，如果一个事务由于发生了数据访问 冲突而被重启，那么它在被重启之前的所有执行都是浪费的。最后，就是实 时数据库系统中存在的浪费的重启问题，它也属于一种浪费的执行 不必要的重启：一个事务在验证阶段由于发生数据访问冲突而被重启， 假如让该事务继续执行下去依然能够保证事务调度的可串行性，那么该事务 l 暑 哈尔滨工程大学硕士学位论文 的重启就是不必耍的“” 2 5 本章小结 本章主要对实时并发控制进行了比较详细的介绍，描述了并发控制的基 本原理以及后续将会用到的乐观并发控制及动态调整串行化顺序的并发控箭 协议的基本知识并深入地探讨了实时事务并发执行中的各种特性，最后列 举了并发控制中存在的问题。新算法理论上的正确性及仿真实验则正是依赖