第7章节并发控制v1.2.pptVIP

数据库系统与应用第7章 并发控制 ;事务的并发执行 并发执行可能引起的问题 可串行化 基于锁的并发控制协议 *活锁与死锁 *多粒度封锁 ;7.1 事务的并发执行;调度(schedule);7.2 并发执行可能引起的问题 ;不可重复读(unrepeatable read) ;丢失更新(lost update) ;7.3 可串行化;串行调度 ;可串行化调度 ;【例】：左表中事务的另外一种调度方式;【例】：左表中事务的另外一种调度方式;如果将事务的并发执行完全交给操作系统，则任何一种调度方式都有可能出现。 有的调度能保持数据库的一致，有的调度却会产生错误的结果。 DBMS必须对事务的运行加以控制，确保交叉调度完毕后的结果与某一串行调度的结果相同，数据库不会出现不一致的状态。 ;简记符号 WRITE简写为W， READ简写为R， WT(X)：事务T写数据库元素X， RT(X)：事务T读数据库元素X， S表示一个调度。 调度(事务序列)表示： S = R1(A) R2(A) W1(A) W2(A) R2(B) R1(B) W2(B) W1(B) ;读相同数据：不冲突 若事务Ti 和Tj都是读取数据A，则Ri(A)，Rj(A)指令不发生冲突。 读写相同数据：冲突 若事务Ti 和Tj一个是读数据，一个是写数据，则事务的执行顺序是重要的。Ri(A)和Wj(A)指令是冲突的。 写相同数据：冲突 若事务Ti 和Tj都是写数据A，则Wi（A）和Wj（A）指令也是冲突的。 读写不同数据：不冲突;调度中两个事务发生冲突，必须： 对同一数据对象进行操作 两个操作指令中有一个是写操作W ;冲突等价： 若调度S中属于不同事务的两条操作指令是不冲突的，则可以交换两条指令的执行顺序，得到一个新的调度S′。称调度S与调度S′冲突等价的（conflict equivalent）。 冲突可串行化： 若一个调度冲突等价于一个串行调度，则该调度是冲突可串行化的。 ;调度S： S= R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B) R1(B)与W2(A)指令不冲突，可以交换执行顺序； R1(B)与R2(A)指令不冲突，可以交换执行顺序； W1(B)与W2(A)指令不冲突，可以交换执行顺序； W1(B)与R2(A)指令不冲突，可以交换执行顺序。 调度S′(交换执行顺序)： S’ = R1(A) W1(A) R1(B) W1(B) R2(A) W2(A) R2(B) W2(B);冲突可串行是可串行性的充分条件 ;7.3 可串行化;调度S和调度S’是视图等价的，因为两个调度中： 事务T1读取的都是数据库的初始值 事务T2读取的数据都是事务T1修改后的值 数据库中药品A、B的最终状态都是由事务T2写入的。 ;视图可串行化 如果某个调度视图等价于一个串行调度，则称这个调度是视图可串行化的 如果调度是冲突可串行化的，则该调度一定是视图可串行化的。但反过来未必成立。 ;设调度S1为事务T1、T2、T3的一个可能调度： S1 = R1(A) W3(A) R2(B) W1(B) 经过非冲突指令顺序的调整，得到调度S2： S2 = R2(B) R1(A) W1(B) W3(A) 调度S1和调度S2是冲突等价的。 又因为调度S2为一串行调度，因此调度S1是冲突可串行化的。 对于调度S1和S2，事务T1读取的A、事务T2读取的B都是数据库的初始值；数据库最终的A、B值都是由事务T3和T1写入的。 因此，调度S1和S2是视图可串行化的。 ;判定一个调度是否是冲突可串行化的，可以使用前驱图（precedence graph） 前驱图中若存在环，则表示调度S是不可串行化的。反之，若前驱图中不存在环，表示调度S是冲突可串行化的，可用拓扑排序得到调度S 的一个等价的串行调度。 ;【例】 S = R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B) 冲突指令W1(A)在R2(A)前，W1(B)在R2(B)前，因此存在从T1到T2的有向边。 ;【例】 S = R1(A) R2(A) W1(A) W2(A) R2(B) R1(B) W2(B) W1(B) W1(A)在W2(A)之前，R1(B)在W2(B)之前，因此存在T1到T2的有向边； R2(A)在W1(A)之前，W2(B)在W1(B)之前，因此存在T2到T1的有向边。 ;可恢复性 ;事务在并行执行过程中发生故障，还可能引起多个事务的级联回滚 。;7.4 基于锁的并发控制协议 ;锁的类型及相容性; 当事务需要操作数据项时，它向锁管理器发出锁的申请： 若申请的是一个共享锁，且申请队列为空，当前数据项上也没有排它锁，则锁管理器授予锁，并修改数