5.05 Locking Protocol 加锁协议
1 5.05 Locking Protocol 加锁协议
● 实际运行时，不可能事先 规定一个事务集，提供一个 调度交系统执行。而且DBMS 对事务的调度受制于0$对事 务的调度。 ●较实际的办法是要求DBMS按一定的协议控制 事务执行。从而控制并发事务的操作按可串 行化方式执行。而不必关心具体的调度。 DBMS控制并发事务的操作按可串行化方式执 行，最通用的方法是加锁。 为保证调度执行的可串行化，加锁须遵守一 定的协议，叫加锁协议
2 ⚫ 实际运行时，不可能事先 规定一个事务集，提供一个 调度交系统执行。而且DBMS 对事务的调度受制于OS对事 务的调度。 ⚫ 较实际的办法是要求DBMS 按一定的协议控制 事务执行。从而控制并发事务的操作按可串 行化方式执行。而不必关心具体的调度。 ⚫ DBMS控制并发事务的操作按可串行化方式执 行，最通用的方法是加锁。 ⚫ 为保证调度执行的可串行化，加锁须遵守一 定的协议，叫加锁协议
一.exclusive lock X锁，排他锁。 此协议中，只有一种锁， 即x锁。既用于写操作， 也用于读操作。 一个事务对某数据对象加锁后，其他事务不得对 该数据对象加锁，故称排他锁。 Compatibility matrix相容矩阵。 NL X 请求加锁X Y N ● 列NL一无锁，X一已加锁；行一申请加X锁
3 一.exclusive lock X锁，排他锁。 ⚫ 此协议中，只有一种锁， 即x锁。既用于写操作， 也用于读操作。 ⚫ 一个事务对某数据对象加锁后，其他事务不得对 该数据对象加锁，故称排他锁。 Compatibility matrix相容矩阵。 NL X 请求加锁X Y N ⚫ 列NL—无锁，X—已加锁；行—申请加X锁
Cascading rol lback 连锁卷回 T1,T2两个事务加锁和释放情况： T1 T2 lock(D)方 W1D方 lock(D); unlock(D); 等待 lock (D); R2(D): (rollback unlock (D) 加锁，释放过程
4 Cascading rollback 连锁卷回 ⚫ T1，T2两个事务加锁和释放情况： ⚫ 加锁，释放过程。 T1 T2 . . . lock(D); W1(D); unlock(D); . . . . . . （rollback） . . . . . . lock(D); 等待 lock（D）； R2（D）； unlock（D）； . .
T1因故卷回，T2也被迫卷回。 即使T2已提交也要卷回，因为T2使用了脏数据。 读过T2写入的数据的事务也被迫卷回，还可发 展，造成连锁卷回。 连锁卷回的产生原因：过早地释放锁。 把锁保持到事务结束，则T1结束前其他事务不 能读取加锁数据，而不会产生连锁卷回。原因： 卷回只能在事务结束前发生
5 ⚫ T1因故卷回，T2也被迫卷回。 ⚫ 即使T2已提交也要卷回，因为T2使用了脏数据。 读过T2写入的数据的事务也被迫卷回，还可发 展，造成连锁卷回。 ⚫ 连锁卷回的产生原因：过早地释放锁。 ⚫ 把锁保持到事务结束，则T1结束前其他事务不 能读取加锁数据，而不会产生连锁卷回。原因： 卷回只能在事务结束前发生
读操作的锁是也要保持到E0T(end of transaction)读操作完成即释放锁，不 会引起连锁卷回，但可引起读值不可复现。 Ti T2 lock(D)月 R1(D) unlock(D); lock(D)为 W2(D), unlock (D); lock(D)为 R1(D)方 unlock(D方
6 读操作的锁是也要保持到EOT（end of transaction）读操作完成即释放锁，不 会引起连锁卷回，但可引起读值不可复现。 T1 T2 . . . lock(D); R1(D); unlock(D); . . . . . . . . . lock(D); R1(D); unlock(D); . . . . . . . . . . . . lock(D); W2(D); unlock（D）； . . . . . . . .
二.two-phase locking protocol 2PL协议，两段封锁协议 o Two-phase transaction and two-phase locking protocol 。在一个事务中，如果加锁动作都在释放锁动作之前 称此事务为两段事务。上述加锁的限制称两段封锁协议。 两段事务可截然为两段：拥有的锁增长阶段(growing phase),拥有的锁缩减段段(shr inking phase) ● 两段事务中，一旦开始释放第一个锁之后，再不准对 任何数据对象加锁
7 二.two-phase locking protocol 2PL协议，两段封锁协议 ⚫ Two-phase transaction and two-phase locking protocol ⚫ 在一个事务中，如果加锁动作都在释放锁动作之前 称此事务为两段事务。上述加锁的限制称两段封锁协议。 ⚫ 两段事务可截然为两段：拥有的锁增长阶段（growing phase），拥有的锁缩减段段（shrinking phase）。 ⚫ 两段事务中，一旦开始释放第一个锁之后，再不准对 任何数据对象加锁
●例： T1: lock(A)lock(C)lock(B) unlock(C)unlock(A)unlock(B) growing phase shrinking phase 时间 Wel l formed transaction, 合式事务： 一个事务如果遵守先加锁，后操作的原则，则此事务 叫合式事务
8 ⚫ 例： T1： lock(A)lock(C)lock(B) unlock(C)unlock(A)unlock(B) growing phase shrinking phase 时间 Well formed transaction, 合式事务： 一个事务如果遵守先加锁，后操作的原则，则此事务 叫合式事务
● 定理：如果所有事务均为合式、两段事 务，则它们的任何调度都是可串行化的。 证明：用反证法。设满足定理条件的事 务集有一个调度是不可串行化的，则其 前趋图中必有回路，设为： Ti1->Ti2->...->Tip->Ti1 Ti1->Ti2表示两事务中至少有一个数据对 象必须由Ti1必先加锁进行操作，释放后， Ti2才能加锁操作，依次Tip>Ti1也有此 种等待，所以Ti1不能是两段事务。与命 题违，满足定理条件的事务集是可串行 化。证毕
9 ⚫ 定理：如果所有事务均为合式、两段事 务，则它们的任何调度都是可串行化的。 ⚫ 证明：用反证法。设满足定理条件的事 务集有一个调度是不可串行化的，则其 前趋图中必有回路，设为： Ti1->Ti2->. . .->Tip->Ti1 Ti1->Ti2表示两事务中至少有一个数据对 象必须由Ti1必先加锁进行操作，释放后， Ti2才能加锁操作，依次Tip->Ti1也有此 种等待，所以Ti1不能是两段事务。与命 题违，满足定理条件的事务集是可串行 化。证毕
● 2PL协议是调度可串行化的充分条件，但2PL协 议不是调度可串行化的必要条件。 。反例： ● S=R2(x)W3(x)R1(y)W2(y); S=R1 (y)R2 (x)W2 (y)W3 (x) S与S等价，且是串行调度，所以S是可串行化 调度，但T1必须先释放Y上的锁后T2才能对y 加锁并操作，所以S不是两段事务。 虽然2PL协议不是可串行化的必要条件，由于 2PL协议简单，一般DBMS都用它来实现调度 可串行化 10
10 ⚫ 2PL协议是调度可串行化的充分条件，但2PL协 议不是调度可串行化的必要条件。 ⚫ 反例： ⚫ S=R2（x）W3（x）R1（y）W2（y）； ⚫ S'=R1（y）R2（x）W2（y）W3（x）； ⚫ S'与S等价，且是串行调度，所以S是可串行化 调度，但T1必须先释放Y上的锁后T2才能对y 加锁并操作，所以S不是两段事务。 ⚫ 虽然2PL协议不是可串行化的必要条件，由于 2PL协议简单，一般DBMS都用它来实现调度 可串行化