Decode360's Blog

业精于勤而荒于嬉 QQ:150355677 MSN:decode360@hotmail.com

  BlogJava :: 首页 :: 新随笔 :: 联系 ::  :: 管理 ::
  397 随笔 :: 33 文章 :: 29 评论 :: 0 Trackbacks
事务并发调度问题
 
    昨天看模拟题,有一道关于数据库并发的题目,不是很明白,所以今天特地到网上查了一下,在这里做一个记录:
 
    题目是数据库系统工程师考试06年5月下午卷的第5题,具体的题目是这样的:
******************************************************************************
【说明】
  现有一个事务集{T1,T2,T3,T4},其中这四个事务在运行过程中需要读写X、Y和Z。设Ti对X的读操作记作TiR(X),Ti对X的写操作记作TiW(X)。
  事务对XYZ的访问情况如下:
  T1:T1R(x)
  T2:T2R(Y),T2W(X)
  T3:T3W(Y),T3W(X),T3W(Z)
  T4:T4R(Z),T4W(X)
 
【问题1】试述事务并发高(调)度的正确性准则及其内容(4分)
【问题2】请判断如下高(调)度是否正确。(4分)
T3W(Y),T1R(X),T2R(Y),T3W(X),T2W(X),T3W(Z),T4R(Z),T4W(X)
按这种调度产生的事务依赖关系图如下:
    trans
【问题3】给出与【问题2】中调度等价的一串行调度序列。(3分)
 
(注:严重质疑题目里的“高度”应该是错别字,改成“调度”才可以理解)
******************************************************************************
 

    首先关于【问题1】,我的理解是这样的:事务的并发调度的正确性,取决于这个并发调度是不是可以等价得转换为串行调度。只有当一个并行调度可以与某一次的串行调度转化时,这个并发调度才是正确的。
 
    然后对于【问题2】,可能对题目本身比较难以理解。其实对于并行调度的正确性判断不需要考虑读写一致性和锁定/解锁的问题,虽然事务T1/T2/T3/T4中的每一个子项都是原子性的,在启动前锁定,完成后解锁,但是如果不是按照整个事务的串行化执行,其最后的结果是会发生错误的。所以我们只能从事务对于X/Y/Z的依赖性的角度来进行分析,例如:
 
    数据项X:T1R(X),T3W(X),T2W(X),T4W(X)
    相对于X的事物依赖图为:T1--->T3,T1--->T2,T1--->T4,T3--->T2,T3--->T4,T2--->T4
 
    数据项Y:T3W(Y),T2R(Y)
    相对于Y的事物依赖图为:T3--->T2
 
    数据项Z:T3W(Z),T4R(Z)
    相对于Z的事物依赖图为T3--->T4
 
    综合X,Y,Z的事物依赖图得到题目已知的事物调度依赖图。
    在事物调度依赖图中,沿箭头方向不产生回路(要包含所有事务)的一条路径就是与该并发调度等价的串行调度,假设在事务依赖图中有回路产生,则该并发调度是不可串行化的。而本题按照T1--->T3--->T2--->T4的顺序是满足条件的,所以题中的并行调度顺序是正确的。
 
 
    如果是不可串行化的调度,则可能是发生了死锁。例如...,T2R(Y),T3W(X),...T2W(X),T3W(Y),...
    如果出现这种情况,则改换成串行模式时,对于Y,T3在等待T2结束后对Y解锁,而对于X,T2在等待T3结束后对X解锁,这样就造成了互相等待的死锁情况而无法进行下去。
 
    需要特别注意的是:在事物依赖有向图中,选取的路径是不可以包括回路(多方死锁),或者双向路径的。
 
    对于【问题三】,只要搞明白上面的原理,就很简单了,答案就是 T1--->T3--->T2--->T4
 

 
posted on 2009-04-18 21:14 decode360 阅读(299) 评论(0)  编辑  收藏 所属分类: 12.Certified

只有注册用户登录后才能发表评论。


网站导航: