《实时数据库系统之实时并发控制协议》由会员分享，可在线阅读，更多相关《实时数据库系统之实时并发控制协议（6页珍藏版）》请在金锄头文库上搜索。
1、实时数据库系统之实时并发控制协议实时数据库技术是实时系统和数据库技术相结合的产物，研究人员希望利用数据库技术 来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供时间驱动调度和资 源分配算法。然而，实时数据库并非是两者在概念、结构和方法上的简单集成。需要针对不 同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配策略、实时数据查询 语言、实时数据通信等大量问题作深入的理论研究。并发控制用于控制并发执行的事务之间的交互操作以避免数据库的一致性被破坏KOR86。在传统数据库系统中，针对这个问题上有大量的研究工作PAP86。实时数据库中的并 发控制协议不仅要求保证数据的逻辑一致
2、性，而且必须考虑满足并发事务的截止期。优先级 反转是传统的并发控制协议应用于实时数据库所表现出的主要问题Sha91。目前，许多面向 实时数据库的并发控制协议已经被提出ABB88, HAR90, HUA91, LAM95, LAMOO, LIN99,这些协议大多 数可以归结为基于锁的方法与乐观的并发控制协议。1基于锁的并发控制协议保证可串行性的一种锁机制是两阶段锁(2PL： Two-Phase Locking)协议，这个协议要 求事务分为两个阶段提出加锁与解锁请求。传统数据库系统中的研究表明,在大部分操作环 境中基于锁的协议性能优于乐观的协议AGR87。在实时数据库中事务按照截止期或者重要性 被
3、分配优先级，冲突解决机制偏向于具有较高优先级的事务。但是2PL并未考虑事务的优 先级,当应用于优先级驱动的事务调度系统时,倾向于导致优先级反转与死锁问题,因此一 些研究在2PL协议中引入了基于优先级的冲突解决机制以及优先级继承或者优先级顶机制。 基于优先级的2PL变体协议主要包括：2PL-HP、2PL-WP、2PL-CPI、2PL-CR等等。2PL-HP (2PL - High Priority)ABB88, HAR90,也称为 2PL-PA(2PL - Priority Abort),采 用偏向于高优先级事务的冲突解决方法，一旦检测到冲突就立即通过夭折低优先级的事务解 决所有的数据冲突。而2
4、PL-WP(2PL - Wait Promote)abb92, sha90,也称为 2PL-PI(Priority Inheritance)HUA92,是通过阻塞锁请求事务来解决冲突，其中包含了一种优先级继承机制。 针对2PL-HP所进行的实验结果ABB89, HUA91b表明基于优先级夭折方法的实时并发控制协议 相对于基于优先级继承方法的协议性能显著要好。Stankovic等STA9ib也发现2PL-HP在实时 数据库环境中优于2PL-WP协议，并且认为基本的优先级继承并不适合于2PL协议中的冲 突解决。Haritsa等har92认为2PL-WP减少了高优先级事务的阻塞时间，但是这种阻塞时间
5、 仍然不确定。并且，在较高的数据竞争条件下，2PL-WP可能导致系统中的大部分事务在同 样的优先级上执行LEE96。毫无疑问，重启接近完成的事务会导致CPU资源的浪费，因为重启要求被夭折事务的 所有操作必须重做。而另一方面，阻塞可能导致较高优先级的事务错失截止期。因此， 2PL-CPI(2PL - Conditional Priority Inheritance)HUA9ib,HAR92是 2PL-HP 与 2PL-WP 的组合。 在这种协议中，只有当冲突的低优先级事务接近完成时才采用优先级继承，否则这个低优先 级事务被夭折。与2PL-CR非常类似的一个协议是2PL-CR(2PL - Cond
6、itional Restart)，按 照下面的方法决定是否夭折较低优先级的事务：如果较高优先级的事务的松弛时间大于其剩 余执行时间，则较低优先级的事务继续执行，否则夭折。在实时系统中，优先级顶协议(PCP： Priority Ceiling Protocol)ShA90能够限制优先级 反转不超过单个关键段的执行时间，并且能够避免死锁。一些研究通过扩展优先级顶协议来 调度处理实时事务的并发执行，最初L. Sha等sha9 1使用读/写语义改进了 PCP协议的性能， 提出了 RW-PCP(Read/Write Priority Ceiling Protocol)协议。为了进一步减少事务阻塞时间，
7、K-W. Lam等在lamoo中引入了动态调整串行化顺序的思想增强了 RW-PCP协议来处理硬实 时事务。Tei-Wei Kuo等kuo98则采用两版本方法扩展了 RW-PCP协议，重点是利用数据项 的一致版本减少事务之间的写-读冲突。这些基于优先级顶的协议的主要优点在于能够提供 单阻塞与无死锁特性，从而支持对硬实时事务进行可调度性分析。王宏安等电子学报2005通过引入静态抢占等级的概念，基于EDF动态优先级事务调 度系统，提出了一种新的并发控制协议 MV-PL(Multi-Version two-phase locking based on Preemption Level)协议。协议中采用
8、多版本机制，使得事务的串行化顺序不再由冲突的锁 请求的顺序决定，而是能够根据事务的优先级进行动态地调整，因此能够最小化不必要的事 务阻塞，增强高优先级事务的抢占能力。2 乐观的并发控制协议基于锁的并发控制属于悲观的方法，总是假定事务冲突经常发生，而实际上锁只在最坏 情形下才是必要的。乐观并发控制基于相反的假设，事务冲突很少发生，因此允许事务无阻 碍地执行直到全部操作完成，然后在提交时进行验证，如果通过了检验就提交，否则夭折。如果系统中事务之间的数据竞争很弱，大部分事务能够通过验证并提交；而如果事务之间的竞争越激烈，越多的事务就将被夭折并重启，从而降低系统资源利用率AGR87,BHG87,ELM
9、95。OCC协议中，事务的执行分为三个阶段：读阶段(Read phase)、验证阶段(Validation phase)与写阶段(Write phase)。而为了进行事务验证，需要对每一活跃的事务片记录其读 和写数据集：RSTi与WSTJ。OCC协议的关键是如何验证事务，验证方法包括：(1) 后向验证(Backward validation)：针对最近提交的事务验证要提交的事务。这种方 法的缺点是检验冲突太迟，它实际上是检验所有已完成事务间的冲突，因此夭折与 重启的代价较大。(2) 前向验证(Forward Validation):针对活跃的事务验证要提交的事务，当冲突存在时， 有三种解决方法
10、： 1)夭折冲突的未完成的事务而让验证事务通过验证而提交， OCC-BC (Broadcast Commit)就是这种策略的代表；2)夭折冲突中优先级低的事 务； 3)让验证事务等待优先级比它高的事务，而夭折优先级比它低的事务。OCC 协议按照验证方法的不同，主要包括以下变体：OCC-BC(Broadcast Commit)OCC-BC 协议中，当一个事务提交时，它通知所有正在运行的冲突的事务，并且这些事 务将被立即重启。这里，没必要检查与已经提交事务之间的冲突，因为当前验证的事务如果 与任何提交的事务之间存在冲突，则它必定在到达验证阶段之前已经被重启。这意味着一旦 一个事务到达验证阶段，就能
11、保证提交。这个协议中采用的方法是前向验证，相对于后向验 证，会较早重启冲突的事务，因而减少了资源浪费，增加了事务满足截止期的机会 HAR90， HAR90b。OCC-SacrificeOCC-Sacrifice协议har90har92修改了 OCC-BC协议，结合了基于优先级的牺牲机制。 定义所有与当前验证事务冲突的事务组成一个冲突集，如果冲突集中存在一个或者多个较高 优先级的事务，则验证事务将被重启，即验证的事务为了保证较高优先级的事务满足截止期 而牺牲。 尽管这个协议能够优先对待较高优先级的事务， 但是也存在浪费的重启(Wasted-restart)问题。OCC-Wait 与 Wait-5
12、0OCC-Wait协议har92采用了基于优先级的事务等待机制。在这个协议中，如果一个到达 验证阶段的事务发现其冲突集中存在较高优先级的事务，则被迫去等待，从而给较高优先级 的事务先满足截止期的机会。Wait-50方法是OCC-Wait的扩展，一个验证的事务只有当其 冲突集中的事务超过50%具有较高的优先级时才等待。其实，Wait-50是BC与Wait方法的 折衷，因此能够得到更加一般性的方法Wait-xo Haritsa等har92针对不同的x进行了实验， 结果概括如下：(1) 降低x为25%会导致系统在正常负载下性能有轻微的改进，但是随着负载增加，性 能出现降级，这时因为较低的界限增加了事
13、务等待的因素；(2) 升高x为75%导致正好相反的效果。因此，利用系统负载信息动态调整x的值能够改进Wait-x协议的性能。OCC-TI 与 OCC-APROCC-TI (Timestamp Interval) lee93lee96协议采用时间戳间隔解决事务间的冲突，每个 事务在读阶段被分配一个时间戳间隔或者称为时间槽，这个时间槽用于记录事务执行过程 中暂时的串行化顺序。无论何时，由于冲突的数据操作或者其它事务的验证导致事务的串行 化顺序被改变，这个时间槽也被相应地调整以体现这些相关性。因此，与其它乐观方法不同 之处在于，OCC-TI协议并不依赖于这种设想：事务串行化顺序与事务到达验证阶段的顺
14、序 一样。Haritsa等har92认为解决冲突时考虑事务的优先级对于增强OCC协议的性能是一个重 要的决定性因素。同时，Lee等Lee93QAT97进行的研究表明，实时并发控制协议的主要决定性 因素是事务重启的数量，减少重启数量是突破这些协议性能约束的关键因素。为了减少事务重启的数量，Datta等DAT97试图在OCC-TI中使用优先级信息解决数据冲 突，其中决定重启验证事务而允许不可调和的事务继续执行的条件是：(1) 如果正在验证的事务的截止期足够远，重启后仍能满足截止期；(2) 不可调和的事务集大的足以做出这种冒险式的牺牲。结果表明，重启的验证事务与不可调和的事务集都能够更好地满足它们的
15、截止期。为了 进一步提高重启验证事务并满足其截止期的把握，Datta等DAT97试图约束重启事务所要求的 执行时间。假设重启的事务将访问先前运行时曾经访问过的同样的数据集，并且既然这个事 务已经到达其验证阶段，则内存中必定有其全部的数据集。因此，所有的IO操作能够被消 除，并且乐观的方法不要求任何锁/阻塞，消除了所有数据竞争可能导致的延误。基于此， Datta等提出了 OCC-APR (Adaptive Priority)协议，只要不可调和的事务中至少有两个较高 优先级的事务，将重启正在验证的事务。OCC-DA 与 OCC-DATIOCC-DA (Dynamic Adjustment of s
16、erialization order) LAM95基于前向验证模式，事务重启的数量通过动态调整串行化顺序而减少，这由动态时间戳分配技术所支持。冲突检测在事务的验证阶段进行，在事务的读阶段不必要进行时间戳调整。每个事务 Ti 有一个串行化顺 i序时间戳SOT(TJ，指示了这个事务相对于其它事务的串行化顺序，因而提交事务的串行化 顺序可以不同于提交顺序。OCC-DATI(Dynamic Adjustment of serialization order using Timestamp Intervals )LIN99 也是基于前向验证，事务重启的数量通过动态调整串行化顺序而减少，但是这由OCC-TI中 相似的时间槽方法所支持。但是，不像OCC-TI协议，OCC-DATI中所有的冲突检测是在事 务的验证阶段进
