事务并发控制中的两段锁和可串行化冲突图的对比.pdf

( ) 第 27 卷 第 1 期 湖北大学学报 自然科学版 　Vol . 27 　No . 1 　 ( ) 2005 年 3 月 Journal of Hubei University Natural Science Mar . ,2005 ( ) 文章编号 :1000 - 2375 2005 01 - 0019 - 05 事务并发控制中的两段锁和 可串行化冲突图的对比 金 　蓉 ,李跃新 (湖北大学 数学与计算机科学学院 ,湖北 武汉 430062) 摘 　要 :数据库中并发操作一般分为数据级和事务级两种 , 由于资源的竞争可能引起数据级的冲突和事 务级的冲突 ,因此需要对并发执行的事务转化为某个可串行化调度 ,从而确保数据库的一致性. 目前并发控制 的方法有很多 ,从锁和非锁机制两个方面分析了两段锁和可串行化冲突图两种并发控制的规则和数据结构 及分类 ,并从事务的冲突可串行化方面和结构上分析了各自的性能和优缺点. 关键词 :锁 ;两段锁协议 ;可串行化冲突图 中图分类号 :TP311 　　文献标志码 :A 1 　引　言 数据库中的并发操作一般分为数据级和事务级两种 , 一方面在微观数据级上有数据对象的读 ( ) ( ) ( ) ( ) Read 操作和写 Write 操作 ,另一方面在宏观事务级上有事务的操作原语 :终止 Abort ,开始 Begin , ( ) ( ) 提交 Commit ,结束 End ,实质上事务中包含着对一系列数据对象的操作 , 因为一个事务系统主要由3 ( ) 个部分构成 :数据项集 、对数据项集的操作和控制事务存取数据的管理器 我们称为事务管理器 TM . 并 发控制的作用是正确协调同一时间里多个事务对数据库的并发操作 ,解决资源竞争问题以保证数据库 的一致性和完整性. 并发控制是通过调度来确保事务的并发执行的效果等同于没有并发执行时的执行效果 ,也就是使事务的 并发执行调度等价于事务的某个可串行化调度 ,从而确保数据库的一致性. 可串行化简单的说就是一个并发 操作等效于某个串行执行的效果 ,也即有相同的输出结果 ,与串行操作对数据库有同样的效果. 冲突有数据级的冲突和事务级的冲突 ,数据间的冲突体现在数据库中同时对相同的数据对象操作 , 事务间的冲突是由事务的数据相关性及在共享数据对象上的交互作用而引起的 ,通常用事务的“冲突关 系”来表示. ( ) , 当且仅当 ( ( ) , ) 定义 1 　数据对象 d 上的两个操作p 、q 是“冲突”的, 记为 CT d , p , q S S s , p q ≠ ( ( ) ) ( ) ( ( )