并发控制之二.docVIP

并发控制之二 时间戳协议 1时间戳概述 对于基本加锁的并发控制方法，不同事务间的冲突操作可以按照获得锁的顺序进行排序，加锁协议将操作间的顺序扩展到事务间，因而确保可串行化。 另一种决定事务可串行化次序的方法是事先选定事务的次序，其中最常用的方法是时间戳排序机制。 1时间戳概述 对于系统中每个事务Ti，我们把一个唯一的固定的时间戳和它联系起来，此时间戳记为TS(Ti)。该时间戳是在事务Ti开始执行前由数据库系统赋予的。若事务Ti已被赋予时间戳TS(Ti)，同时有一个新事务Tj进入系统，则TS(Ti) TS(Tj)。实现这种机制可以采用下面两个简单的方法。 1时间戳概述 1、使用系统时钟值作为时间戳；即事务的时间戳等于该事务进入系统时的时钟值。 2、使用逻辑计数器，每赋予一个时间戳，计数器增加一次。即事务的时间戳等于该事务进入系统时的计数器值。 事务的时间戳决定了串行化顺序。因此，若TS(Ti) TS(Tj)，则系统必须保证所产生的调度等价于事务Ti出现在事务Tj之前的某个串行调度。 1时间戳概述 要实现这个机制，每个数据项Q需要与两个时间戳关联： W-timestamp（Q）：表示成功执行write（Q）的所有事务的最大时间戳（最年轻的）。 R-timestamp（Q）：表示成功执行read（Q）的所有事务的最大时间戳（最年轻的）。 每当有新的write（Q）或read（Q）指令执行时，这些时间戳就被更新。 2 时间戳排序协议 时间戳排序协议保证任何有冲突的read和write操作按时间戳顺序执行。该协议运作方式如下： 1、假设事务Ti发出read（Q）操作： （1）若TS(Ti)W-timestamp(Q)，则Ti需读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚。 （2）若TS(Ti)=W-timestamp(Q)，则执行read操作，R-timestamp(Q)被设为R-timestamp(Q)与TS(Ti)两者中的最大值。 2 时间戳排序协议 2、假设事务Ti发出write（Q）操作： （1）若TS(Ti)R-timestamp(Q)，则Ti所产生的值是先前所需要的值，且系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚。 （2）若TS(Ti)W-timestamp(Q)，则Ti想写入的Q值已过时，因此，write操作被拒绝，Ti回滚。 （3）其它情况是执行write操作，将W-timestamp(Q)设为 TS(Ti)。 事务Ti如果由于发出read或write操作而被并发控制机制滚回，则被赋予新的时间戳并重新启动。 2 时间戳排序协议 为说明这个协议，考虑事务T1与T2，事务T1定义如下： T1：read(A); A=A-30 write(A) 2 时间戳排序协议 事务T2的定义如下： T2: read(A); A=A*2; Write(A); 2 时间戳排序协议 在说明时间戳协议下的调度时，假设事务在第一条指令执行之前的那一刻被赋予时间戳。因此，如图所示的调度中，TS(T1)TS(T2)，同时该调度是满足时间戳协议的一个可能的调度。 2 时间戳排序协议 2 时间戳排序协议 2 时间戳排序协议 该协议保证无死锁，因为不存在等待的事务。协议可能产生不可恢复的调度，然而协议可以进行扩展，保证调度可恢复且无级联，这可以通过只在事务末尾执行写操作或使用一种受限制封锁形式来实现。 3 Thomas写规则 现在给出对时间戳排序协议的一种修改，它允许的并发程度比上节中的协议要高。让我们来看图所示调度。由于T1先于T2开始，我们可假定TS(T1)TS(T2)。 3 Thomas写规则 3 Thomas写规则 虽然事务T1回滚是时间戳排序协议所要求的，但也是不必要的。因为T2已经写入了A，T1想要写入的值将永远不会被读到。满足TS(Ti)TS(T2)的任何事务Ti试图进行Write(A)操作时均被回滚，因为TS(Ti) W-timestamp(A)。满足TS(Tj)TS(T2)的任何事务Tj必须读由T2写入的A值，而不是由T1写入的值 3 Thomas写规则 根据以上分析，可以修改时间戳排序协议而得到一个新版本协议，该协议在某些特定的情况下忽略过时的write操作。协议中有关read操作的规则保持不变，但有关write操作的规则与上节中的时间戳排序协议略有区别。 3 Thomas写规则 假设事务Ti发出write（Q）操作： （1）若TS(Ti)R-timestamp(Q)，则Ti产生的值是先前所需要的值，但系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚。 （2）若TS(Ti)W-timestamp(Q)，则Ti试图写