数据库5版讲稿第十六章---并发控制课件.ppt

《数据库5版讲稿第十六章---并发控制课件.ppt》由会员分享，可在线阅读，更多相关《数据库5版讲稿第十六章---并发控制课件.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/291数据库系统概念-并发控制基于锁的协议基于锁的协议 l锁的概念锁的概念l事务T对某个数据对象操作之前，先向系统发出请求，对其加锁。加锁成功后，事务T开始对该数据对象进行操作，在事务T释放它的锁之前，其它的事务不能更新此数据对象。加锁不成功，事务T等待。l封锁协议：事务运用X锁和S锁对数据对象加锁时的约定。2023/3/292数据库系统概念-并发控制基于锁的协议基于锁的协议 l锁的类型锁的类型lX锁锁：排它型锁(exclusive lock)，又称为写锁（为写操作而加得锁）。l若事务T对数据对象Q加上X锁，则只允许T读取和修改Q，直到T释放Q上的锁，其他任何事务都不能对Q加上加

2、上任何类型的锁，提出加锁，只能等待。l保证了其它事务在T释放A上的X锁之前，不能再读取和修改Q 2023/3/293数据库系统概念-并发控制基于锁的协议基于锁的协议 lS锁锁：共享型锁(share lock)，又称为读锁（仅为读操作而加得锁）。l若事务T对数据对象Q加上S锁，其它事务还能再对Q加上S锁，但加不上X锁。l保证了T释放Q上的S锁之前，其它事务可以读Q，不能对Q做任何修改。2023/3/294数据库系统概念-并发控制基于锁的协议基于锁的协议 时间时间T1库库A的值的值T2并发控制器并发控制器11002LOCK-X（A）3GANT-X（A，T1）4LOCK-X（A）5Read(A)等待

3、等待6A=A-30等待等待7WRITE(A)70等待等待8COMMIT70等待等待9UNLOCK-X（A）GANT-X（A，T2）10 READ(A)11A=A*212140WRITE(A)13140COMMIT14UNLOCK-X（A）2023/3/296数据库系统概念-并发控制基于锁的协议基于锁的协议 l不能保证可重复读，不能保证可重复读，T2T2第一次读第一次读100100，第二次读，第二次读7070时间时间T1AT2并发控制器并发控制器11002READ(A)3LOCK-X（A）4 GANT-X（A，T1）5Read(A)6A=A-30 7WRITE(A)70 8COMMIT70 9U

4、NLOCK-X（A）10 READ(A)2023/3/297数据库系统概念-并发控制基于锁的协议基于锁的协议 l不能保证不读不能保证不读“脏脏”数据数据时间时间T1AT2并发控制器并发控制器11002LOCK-X（A）3GANT-X（A，T1）4Read(A)5A=A-30 6WRITE(A)70 7READ(A)8ROLLBACK 100 9UNLOCK-X（A）2023/3/298数据库系统概念-并发控制基于锁的协议基于锁的协议 l 时间时间T1库库A的值的值T2并发控制器并发控制器11002LOCK-X（A）3GANT-X（A，T1）4Read(A)5A=A-30 6WRITE(A)70

5、 7LOCK-S（A）8 等待等待9ROLLBACK 10010UNLOCK-X（A）GANT-S（A，T2）11READ(A)12UNLOCK-S（A）2023/3/2910数据库系统概念-并发控制基于锁的协议基于锁的协议 l 时间时间T1库库A的值的值T2并发控制器并发控制器11002LOCK-S（A）3GANT-S（A，T2）4 READ(A)5100UNLOCK-S（A）6LOCK-X（A）7 GANT-X（A，T1）8Read(A)9A=A-30 10WRITE(A)70READ(A)11COMMIT7012UNLOCK-X（A）13LOCK-S（A）14GANT-S（A，T2）15

6、 READ(A)16UNLOCK-S（A）2023/3/2911数据库系统概念-并发控制基于锁的协议基于锁的协议 l 时间时间T1A的值的值T2并发控制器并发控制器11002LOCK-S（A）3GANT-S（A，T2）4100 READ(A)5LOCK-X（A）6等待等待 7等待等待100 READ(A)8等待等待UNLOCK-S（A）9Read(A)GANT-X（A，T1）10A=A-3011WRITE(A)7012COMMIT7013UNLOCK-X（A）2023/3/2913数据库系统概念-并发控制基于锁的协议基于锁的协议 l例：例：T1的封锁序列的封锁序列l LOCK-S（A）.LOC

7、K-S（B）.LOCK-X（C）.UNLOCK-S（B）.UNLOCK-S（A）.UNLOCK-X（C）.lT2的封锁序列是的封锁序列是lLOCK-S（A）.UNLOCK-S（A）.LOCK-S（B）.LOCK-X（C）.UNLOCK-X（C）.UNLOCK-S（B）.lT1遵守，遵守，T2不遵守。不遵守。2023/3/2915数据库系统概念-并发控制基于锁的协议基于锁的协议 l所有事务都遵守两阶段协议，并发调度是可串性化的。（充分条件，不是必要条件）。l事务不遵守两阶段协议，并发调度是能是可串性化的，也可能不是。l例：T9：H=F+1，T10：F=G+1，l T11：F=H+1l初值：H、F

8、、G 都为02023/3/2916数据库系统概念-并发控制基于锁的协议基于锁的协议 l T9、T11遵守两阶段协议的并发调度，是时间时间T9F、G、HT11并发控制器并发控制器10，0，02LOCK-S（F）3GANT-S（F，T9）4Read(F)0，0，0 5TEMP1=F 6LOCK-X（H）7 GANT-X（H，T9）8LOCK-S（H）9H=TEMP1+1 等待等待10WRITE（H）0，0，1等待等待11COMMIT 0，0，1等待等待12UNLOCK-X（H）等待等待2023/3/2918数据库系统概念-并发控制基于锁的协议基于锁的协议 l 13GANT-S（H，T11）140，

9、0，1READ(H)15TEMP2=H16LOCK-X（F）17UNLOCK-S（F）等待等待18GANT-X（F，T11）19F=TEMP2+1202，0，1WRITE（F）212，0，1COMMIT22 UNLOCK-X（F）23UNLOCK-S（H）2023/3/2919数据库系统概念-并发控制基于锁的协议基于锁的协议 lT9、T10不遵守两阶段协议的并发调度，是 时间时间T9F、G、HT10并发控制器并发控制器10，0，02LOCK-S（F）3GANT-S（F，T9）4Read(F)0，0，0 5TEMP1=F 6UNLOCK-S（F）7 LOCK-S（G）8 GANT-S（G，T10

10、）9 0，0，0READ(G)10 TEMP2=G11 UNLOCK-S（G）2023/3/2920数据库系统概念-并发控制基于锁的协议基于锁的协议 l 12 LOCK-X（F）13 GANT-X（F，T10）14 F=TEMP2+1151，0，0WRITE（F）161，0，0COMMIT17UNLOCK-X（F）18LOCK-X（H）19GANT-X（H，T9）20H=TEMP1+121WRITE（H）1，0，122COMMIT1，0，123UNLOCK-X（H）2023/3/2921数据库系统概念-并发控制基于锁的协议基于锁的协议 lT9、T11不遵守两阶段协议的并发调度，不遵守两阶段协议

11、的并发调度，不是 时间时间T9F、G、HT11并发控制器并发控制器10，0，02LOCK-S（F）3GANT-S（F，T9）4Read(F)0，0，0 5TEMP1=F 6UNLOCK-S（F）7 LOCK-S（H）8 GANT-S（H，T11）9 0，0，0READ(H)10 TEMP2=H11 UNLOCK-S（H）2023/3/2922数据库系统概念-并发控制基于锁的协议基于锁的协议 l死锁和活锁死锁和活锁 两个或两个以上的事务都在等待其中另一个两个或两个以上的事务都在等待其中另一个事务解除封锁，它才能继续执行下去，结果事务解除封锁，它才能继续执行下去，结果任何一个事务都无法继续执行，这

12、种现象称任何一个事务都无法继续执行，这种现象称为死锁为死锁(dead lock)(dead lock)。l封锁技术可能产生某个事务可能永远处于等封锁技术可能产生某个事务可能永远处于等待状态，得不到执行的机会，这种现象称为待状态，得不到执行的机会，这种现象称为活锁活锁(live lock)(live lock)。2023/3/2924数据库系统概念-并发控制基于锁的协议基于锁的协议 l解决活锁的一种简单方法是采用解决活锁的一种简单方法是采用“先来者先先来者先执行执行”的控制策略，也就是简单的排队方式。的控制策略，也就是简单的排队方式。lDBMSDBMS中有一个中有一个“死锁测试程序死锁测试程序”

13、，每隔一，每隔一段时间检查并发的事务是否发生死锁，发现段时间检查并发的事务是否发生死锁，发现死锁，只能撤消某个事务，恢复该事务到初死锁，只能撤消某个事务，恢复该事务到初始状态。始状态。l两阶段封锁协议可能发生死锁两阶段封锁协议可能发生死锁2023/3/2925数据库系统概念-并发控制基于锁的协议基于锁的协议 l例：例：T9：H=F+1，T10：F=G+1，T11：F=H+1，初值：，初值：0，0，0lT9、T11并发，并发，l串性操作 lT9T11结果：F=2，G=0 H=1 。lT11T9结果：F=1，G=0 H=2。lT9、T11遵守两阶段协议的并发调度2023/3/2926数据库系统概念

14、-并发控制基于锁的协议基于锁的协议 l 12LOCK-X（H）等待等待13等待等待 等待等待死锁死锁14等待等待 等待等待死锁死锁15等待等待撤消撤消T11GANT-X（H，T9）16H=TEMP1+1 17WRITE（H）18COMMIT 19UNLOCK-S（F）20UNLOCK-X（H）2023/3/2928数据库系统概念-并发控制基于锁的协议基于锁的协议l例例 设设T1，T2，T3是如下的三个事务：是如下的三个事务：l T1：A=A+2l T2：A=A*2l T3：A=A*2 (AA*A)l 设设A的初始值为的初始值为0；l(1)若这三个事务允许并行执行，则有多少若这三个事务允许并行执

15、行，则有多少可能的正确结果，请一一列举出来；可能的正确结果，请一一列举出来；2023/3/2929数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l时间戳定义：事务启动时间。时间戳定义：事务启动时间。l事务事务TiTi的时间戳记为的时间戳记为 TSTS（TiTi）l若若TSTS（T1T1）TSTS（T2T2），则称），则称T1T1是年轻是年轻的事务，或称的事务，或称“后到的事务后到的事务”，T2T2是年是年长的事务，或称长的事务，或称“先来的事务先来的事务”。l时间戳用计数器实现，初值为时间戳用计数器实现，初值为0 0，第一个，第一个到来的事务为到来的事务为1 1，依次加，依次加1

16、1。2023/3/2931数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l数据项数据项QQ的时间戳的时间戳lW-TSW-TS（QQ）：所有执行了写）：所有执行了写QQ操作的事务中操作的事务中最年轻事务的时间戳（值最大）。最年轻事务的时间戳（值最大）。lR-TSR-TS（QQ）：所有执行了读）：所有执行了读QQ操作的事务中操作的事务中最年轻事务的时间戳（值最大）。最年轻事务的时间戳（值最大）。lW-TSW-TS（QQ），），R-TSR-TS（QQ）是两个同步值。）是两个同步值。2023/3/2932数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l时间戳协议的意义时间戳协议

17、的意义l1尽管对多个事务并发调度，交叉执行，但总的尽管对多个事务并发调度，交叉执行，但总的调度结果与事务先后到来的顺序所确立的串性调调度结果与事务先后到来的顺序所确立的串性调度等价。度等价。l如，如，T1，T2，Tk，是先后启动序列，尽管中，是先后启动序列，尽管中间调度先后交叉，但协议调度的结果等价串性调间调度先后交叉，但协议调度的结果等价串性调度：度：T1T2 Tk 2023/3/2933数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l2.交叉执行中，交叉执行中，l“先到的事务先到的事务”Ti 要读被要读被“后到的事务后到的事务”Tj改过的数据，不符合改过的数据，不符合Ti Tj

18、串行等价，串行等价，就发生冲突。就发生冲突。l“先到的事务先到的事务”Ti要修改被要修改被“后到的事务后到的事务”Tj读过或改过的数据，不符合读过或改过的数据，不符合Ti Tj串串行等价，也发生冲突行等价，也发生冲突2023/3/2934数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l3 发生冲突，撤消并重新启动该事务，发生冲突，撤消并重新启动该事务，使它成为最后到来的事务，赋予新的时间戳使它成为最后到来的事务，赋予新的时间戳（最大）。（最大）。事务启动序列发生变化，等价的串性事务启动序列发生变化，等价的串性调度顺序也随之变化。调度顺序也随之变化。l4 事务对数据的更新都是在最后事

19、务对数据的更新都是在最后COMMIT时起作用，执行到中间，撤消事务不影响结时起作用，执行到中间，撤消事务不影响结果。果。2023/3/2935数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l协议协议lTi 读数据读数据Q时时l（1）若若TS（Ti）W-TS（Q），执行读操作，），执行读操作，R-TS（Q）=MAX（R-TS（Q）,TS（Ti）l说明：说明：Ti要读被要读被“先到的事务先到的事务”改过的数据，允许。改过的数据，允许。2023/3/2936数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l Ti 写数据写数据Q时时l（1）若若TS（Ti）R-TS（Q），撤消）

20、，撤消Ti并重新启动。并重新启动。l说明：说明：Ti要改被要改被“后到的事务后到的事务”读过的数据，读过的数据，与事务启动序列等价的串性调度矛盾。与事务启动序列等价的串性调度矛盾。l（2）若若TS（Ti）W-TS（Q），撤消），撤消Ti并重新启动。并重新启动。l说明：说明：Ti要改被要改被“后到的事务后到的事务”改过的数据，改过的数据，与事务启动序列等价的串性调度矛盾。与事务启动序列等价的串性调度矛盾。2023/3/2937数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l（3）其它情况，执行写操作，其它情况，执行写操作，W-TS（Q）=TS（Ti）l说明：说明：Ti要写被要写被“先

21、到的事务先到的事务”读过或改过读过或改过的数据，允许。的数据，允许。2023/3/2938数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 lTi 读数据读数据Q时的程序时的程序l if TS（Ti）=W-TS（Q）l Then BEGINl READ（Q）l R-TS（Q）=MAX（R-TS（Q），），TS（Ti）l ENDl Else restart Ti;2023/3/2939数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l Ti 写数据写数据Q时时l if TS（Ti）=R-TS（Q）and TS（Ti）=W-TS（Q）l Then BEGINl WRITE（Q）l

22、 W-TS（Q）=TS（Ti）l END lElse restart Ti;2023/3/2940数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l 例：例：T14：T15：l READ（B）READ（B）l READ（A）B=B-50l DISPLAY（A+B）WRITE（B）l READ（A）l A=A+50l WRITE（A）l DISPLAY（A+B）2023/3/2941数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l初值：初值：TS（T14）=1，TS（T15）=2，T14T15R-TS（A）R-TS（B）W-TS（A）W-TS（B）0000READ（B）01

23、00READ（B）0200B=B-50WRITE（B）0202READ（A）1202READ（A）2202DISPLAY（A+B）2202A=A+50WRITE（A）DISPLAY（A+B）22222023/3/2942数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l thomas 写规则写规则l 分析：协议中分析：协议中Ti 写数据写数据Q时时l（2）若若TS（Ti）W-TS（Q），撤消），撤消Ti并重新启动。并重新启动。l说明：说明：Ti与与“后到的事务后到的事务”都要改数据都要改数据Q，正常是正常是Ti先改，先改，“后到的事务后到的事务”再改，再改，Q的的结果是结果是“后到的

24、事务后到的事务”改得值。现在是改得值。现在是Ti要要后改，不让它改，后改，不让它改，Q的结果如正常一样。所的结果如正常一样。所以用忽略，代替撤消。以用忽略，代替撤消。2023/3/2943数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l例例：TS（T16）=1 TS（T17）=2l忽略忽略T16的的WRITE（Q）。）。T16T17R-TS（Q）W-TS（Q）00READ（Q）10WRITE（Q）12WRITE（Q）122023/3/2944数据库系统概念-并发控制基于时间戳的协议基于时间戳的协议 l注意：注意：调度不是冲突可串性化的。调度不是冲突可串性化的。l S=R16（Q）W17（Q）W16（Q）l也不是视图可串性化的也不是视图可串性化的 lS=Wb(Q)R16（Q）W17（Q）W16（Q）Rf(Q)T16T17T16T17TfTb00002023/3/2945数据库系统概念-并发控制