数据库系统概论PPT教程第八章 并发控制技术

1、第八章第八章 并发控制技术并发控制技术 并发控制并发控制 4为什么要并发执行事务？为什么要并发执行事务？ 4为什么要进行并发控制？为什么要进行并发控制？ 4如何进行并发控制？如何进行并发控制？ 4如何解决并发控制可能带来的问题？如何解决并发控制可能带来的问题？ 4如何保证并发控制的灵活性和效率？如何保证并发控制的灵活性和效率？ 为什么要并发执行事务（一）为什么要并发执行事务（一） 4串行执行方式串行执行方式 t2 t1 time read b (10) read a (16) b = b- 1 (9) a = a-1 (15) write b write a 为什么要并发执行事务（二）为什么要

2、并发执行事务（二） 4并发执行方式并发执行方式 t2 t1 time read b (10) read a (16) b = b- 1 (9) a = a-1 (15) write b write a 为什么要并发执行事务（三）为什么要并发执行事务（三） 4并发执行的优点并发执行的优点 一个事务由不同的步骤组成，所涉及的系统一个事务由不同的步骤组成，所涉及的系统 资源也不同。这些步骤可以并发执行，以提资源也不同。这些步骤可以并发执行，以提 高系统的高系统的吞吐量吞吐量，改善系统的资源的改善系统的资源的利用率利用率。 系统中存在着周期不等的各种事务，串行会系统中存在着周期不等的各种事务，串行会

3、导致难以预测的时延。采用并发会减少导致难以预测的时延。采用并发会减少平均平均 响应时间响应时间，特别是改善短事务的响应时间。特别是改善短事务的响应时间。 并发执行的问题：丢失修改并发执行的问题：丢失修改 4两个事务两个事务t1和和t2读入同一数据并修改，读入同一数据并修改， t2提交的结果破坏了提交的结果破坏了t1提交的结果，导提交的结果，导 致致t1的修改被丢失。的修改被丢失。 t2 t1 time read c (200) read c (200) c=c-100 (100) c = c-100 (100) write c write c 并发执行的问题：不可重复读并发执行的问题：不可重复

4、读 4事务事务t1读取某一数据后，事务读取某一数据后，事务t2对其做对其做 了修改，当事务了修改，当事务t1再次读取该数据时，再次读取该数据时， 得到与前一次不同的值。得到与前一次不同的值。 t2 t1 time read d (1) read d (1) read d (0) write d d=d-1 (0) 并发执行的问题：并发执行的问题： 不可重复读之幻影行不可重复读之幻影行 4事务事务t1按照一定条件从数据库中读取了某些数按照一定条件从数据库中读取了某些数 据记录后，事务据记录后，事务t2删除了其中部分记录，当删除了其中部分记录，当 t1再次按照相同条件读取数据时，发现某些记再次按照

5、相同条件读取数据时，发现某些记 录神秘的消失了。录神秘的消失了。 t1 t2 time select count (*) from sc where cno = c1 返回返回2行行 select count (*) from sc where cno=c1 返回返回1行行 并发执行的问题：并发执行的问题： 不可重复读之幻影行不可重复读之幻影行 4事务事务t1按照一定条件从数据库中读取了某些数按照一定条件从数据库中读取了某些数 据记录后，事务据记录后，事务t2插入了一些记录，当插入了一些记录，当t1再再 次按照相同条件读取数据时，发现多了一些记次按照相同条件读取数据时，发现多了一些记 录。录。

6、 t1 t2 time select count (*) from sc where cno = c1 返回返回2行行 select count (*) from sc where cno = c1 返回返回3行行 并发执行的问题：读并发执行的问题：读“脏脏”数数 据据 4读读“脏脏”数据数据(dirty read) 是指事务是指事务t1修改某一数修改某一数 据，并将其写回磁盘，事务据，并将其写回磁盘，事务t2读取同一数据后，读取同一数据后，t1 由于某种原因被撤销，这时由于某种原因被撤销，这时t1已修改过的数据恢复已修改过的数据恢复 为原值，为原值，t2读到的数据就与数据库中的不一致，则读到

7、的数据就与数据库中的不一致，则 t2读到的数据就为读到的数据就为“脏脏”数据。数据。 t2 t1 time c=0 read c (10000) read c (0) c=c+10000 (10000) c=10000 write c c=0 rollback 可能执行 错误的操作 并发控制的必要性并发控制的必要性 4需要进行并发控制的原因：需要进行并发控制的原因： 如果不进行并发控制，当多个事务并发执行如果不进行并发控制，当多个事务并发执行 的时候，有可能会相互影响，从而读取或者的时候，有可能会相互影响，从而读取或者 存储不正确的数据，破坏数据库的一致性。存储不正确的数据，破坏数据库的一致性

8、。 并发控制（一）并发控制（一） 4并发执行事务情况分析：并发执行事务情况分析： t1:读或写数据项读或写数据项a, t2:读或写数据项读或写数据项b t1:读数据项读数据项a, t2:读数据项读数据项a t1:写数据项写数据项a, t2:写数据项写数据项a t1:读数据项读数据项a, t2:写数据项写数据项a t1:写数据项写数据项a, t2:读数据项读数据项a 4总结，造成并发执行事务问题的原因是：总结，造成并发执行事务问题的原因是： 多个事务同时存取同一个数据集合，多个事务同时存取同一个数据集合， 并且其中至少有一个事务对该数据集合进行了更新并且其中至少有一个事务对该数据集合进行了更新

9、操作操作 没有问题没有问题 没有问题没有问题 丢失修改丢失修改 不可重复读不可重复读 读读“脏脏”数数 据据 并发控制（二）并发控制（二） 4解决问题的思路解决问题的思路 避免不同事务同时对同一数据进行可能导致避免不同事务同时对同一数据进行可能导致 数据不一致的操作。数据不一致的操作。 4采用的技术采用的技术封锁（封锁（locking） 封锁就是事务封锁就是事务t在对某个数据对象如表、记在对某个数据对象如表、记 录等操作之前，先向系统发出请求，对其加录等操作之前，先向系统发出请求，对其加 锁，从而对该数据对象有了一定的控制，在锁，从而对该数据对象有了一定的控制，在 事务事务t释放它的锁之前，其

10、他事务不能更新释放它的锁之前，其他事务不能更新 此数据对象。此数据对象。 并发控制（三）并发控制（三） 4封锁的类型封锁的类型 排它锁（x锁，锁，exclusive lock）：事务）：事务t对对 数据对象数据对象a加上加上x锁，则只允许锁，则只允许t读取和修读取和修 改改a，其它事务对，其它事务对a的任何封锁请求都不能的任何封锁请求都不能 成功（因而不能读取和修改成功（因而不能读取和修改r），直至），直至t释释 放放a上的上的x锁。锁。 共享锁（s锁，锁，share lock）：事务）：事务t对数据对数据 对象对象a加上加上s锁，则事务锁，则事务t可以读取但不能可以读取但不能 修改修改a，其

11、它事务只能对，其它事务只能对a加加s锁（因而可锁（因而可 以读取以读取a），而不能对），而不能对a的加的加x锁（因而不锁（因而不 能修改能修改a），直到），直到t释放释放a上的上的s锁。锁。 并发控制（四）并发控制（四） 相容矩阵相容矩阵 不相容请求不相容请求 相容请求相容请求 并发控制（五）并发控制（五） 4一级封锁协议一级封锁协议 事务事务t在修改数据在修改数据r之前必须对其加之前必须对其加x锁，直锁，直 到事务结束才释放。事务结束包括正常结束到事务结束才释放。事务结束包括正常结束 (commit)和非正常结束和非正常结束(rollback)。 一级封锁协议可以防止丢失修改，并保证事一级封

12、锁协议可以防止丢失修改，并保证事 务务t是可恢复的。在一级封锁协议中，如果是可恢复的。在一级封锁协议中，如果 仅仅是读数据而不对其进行修改，是不需要仅仅是读数据而不对其进行修改，是不需要 对其加锁的，因此它不能保证可重复读和不对其加锁的，因此它不能保证可重复读和不 读读“脏脏”数据。数据。 并发控制（六）并发控制（六） t1t2 xlock c成功成功 读读c=200 xlock c c=c-100 写回写回c=100 commit unlock c 等待等待 等待等待 等待等待 等待等待 xlock c成功成功 读读c=100 c=c-100 写回写回c=0 commit unlock c

13、可以避免丢失修改可以避免丢失修改 并发控制（七）并发控制（七） t1t2 读读d=1 xlock d成功成功 读读d1 d=d-1 写回写回d0 commit unlock d 读读d0 commit 不能避免不可重复读不能避免不可重复读 并发控制（八）并发控制（八） t1t2 xlock c成功成功 读读c=0 c=c+10000 写回写回c 读读c=10000 rollback c恢复为恢复为0 unlock c 不能避免读脏数据不能避免读脏数据 并发控制（九）并发控制（九） 4二级锁协议二级锁协议 二级锁协议是：一级锁协议加上事务二级锁协议是：一级锁协议加上事务t在读在读 取数据取数据r

14、之前必须先对其加之前必须先对其加s锁，读完后即锁，读完后即 可释放可释放s锁。锁。 二级锁除了防止丢失修改，还可以进一步防二级锁除了防止丢失修改，还可以进一步防 止读止读“脏脏”数据。但由于读完后即可释放数据。但由于读完后即可释放s 锁，所以不能保证可重复读。锁，所以不能保证可重复读。 并发控制（十）并发控制（十） t1t2 xlock c成功成功 读读c=0 c=c10000 写回写回c10000 slock c rollback c恢复为恢复为0 unlock c 等待等待 等待等待 等待等待 slock c成功成功 读读c=0 commit unlock c 不读脏数据不读脏数据 并发控

15、制（十一）并发控制（十一） t1t2 slock d成功成功 读读d=1 unlock d xlock d成功成功 读读d1 d = d-1 写回写回d0 commit unlock d slock d成功成功 读读d = 0 commit unlock d 不能避免不可重复读不能避免不可重复读 并发控制（十二）并发控制（十二） 4三级锁协议三级锁协议 三级锁协议是：一级锁协议加上事务三级锁协议是：一级锁协议加上事务t在读在读 取取r之前必须对其加之前必须对其加s锁，直到事务结束才锁，直到事务结束才 释放。三级封锁协议除了防止丢失修改和读释放。三级封锁协议除了防止丢失修改和读 “脏脏”数据以外

16、，还进一步防止了不可重复数据以外，还进一步防止了不可重复 读。读。 并发控制（十三）并发控制（十三） t1t2 slock d获得获得 读读d=1 xlock d 读读d=1 commit unlock d 等待等待 等待等待 等待等待 获得获得xlock d 读读d1 d=d-1 写回写回d=0 commit unlock d 可重复读可重复读 并发控制（十四）并发控制（十四） x锁锁s锁锁一致性保证一致性保证 操作操作 结束结束 释放释放 事务事务 结束结束 释放释放 操作操作 结束结束 释放释放 事务事务 结束结束 释放释放 不丢不丢 失修失修 改改 不读不读 “脏脏” 数据数据 可重可

17、重 复读复读 一级封锁一级封锁 协议协议 二级封锁二级封锁 协议协议 三级封锁三级封锁 协议协议 并发控制（十五）并发控制（十五） 4问题：问题： 是否使用的锁协议级别越高越好呢？是否使用的锁协议级别越高越好呢？ 4sql-92标准中的隔离级别标准中的隔离级别 read uncommitted（一级锁协议）（一级锁协议） read committed（二级锁协议）（二级锁协议） repeatable read（三级锁协议）（三级锁协议） serializable 4sql server中设置隔离级别的方法中设置隔离级别的方法 set transaction isolation level 死锁

18、与活锁（一死锁与活锁（一） t1t2t3t4 slock r xlock r 等待等待slock r unlock r等待等待操作操作slock r 等待等待操作操作操作操作 等待等待 等待等待unlock r操作操作 等待等待操作操作 活锁活锁 死锁与活锁（二）死锁与活锁（二） 4死锁死锁(deadlock) 定义定义 在数据库运行期间，如果存在一个事务集合在数据库运行期间，如果存在一个事务集合 =t0，t1，tn，使得，使得t0等待等待t1持有的持有的 数据项锁，数据项锁， ， tn-1等待等待tn持有的数据项锁，持有的数据项锁， tn等待等待t0持有的数据项锁，则称系统处于死持有的数据项

19、锁，则称系统处于死 锁状态，锁状态， 称为死锁事务集合。称为死锁事务集合。 死锁与活锁（三）死锁与活锁（三） t1t2 lock r1成功成功 对对r1进行操作进行操作 lock r2成功成功 对对r2进行操作进行操作 lock r2 等待等待 lock r1 等待等待 死锁死锁 死锁与活锁（四）死锁与活锁（四） 4解决死锁的方法解决死锁的方法 预防死锁预防死锁 死锁检测和恢复死锁检测和恢复 死锁与活锁（五）死锁与活锁（五） 4预防死锁预防死锁 一次封锁法一次封锁法 一次封锁法要求每个事务必须一次将其所有要使用的数据一次封锁法要求每个事务必须一次将其所有要使用的数据 全部加锁，否则就不能执行。

20、全部加锁，否则就不能执行。 一次加锁法可以有效地防止死锁的发生，但由于需要扩大一次加锁法可以有效地防止死锁的发生，但由于需要扩大 加锁的范围，因此降低了系统的并发度。加锁的范围，因此降低了系统的并发度。 顺序封锁法顺序封锁法 顺序封锁法是预先对数据对象规定一个封锁顺序，所有的顺序封锁法是预先对数据对象规定一个封锁顺序，所有的 事务都要按照这个顺序实行封锁。事务都要按照这个顺序实行封锁。 顺序封锁法可以有效地防止死锁，但其实施由于数据库中顺序封锁法可以有效地防止死锁，但其实施由于数据库中 数据的不断变化和事务封锁要求的动态提出而难度很大。数据的不断变化和事务封锁要求的动态提出而难度很大。 死锁与

21、活锁（六）一次封锁法死锁与活锁（六）一次封锁法 t1t2 lock r1，r2成功成功 对对r1，r2进行操作进行操作 lock r1,r2 commit unlock r1, r2 等待等待 等待等待 等待等待 lock r1,r2 对对r1,r2进行操作进行操作 commit unlock r1, r2 死锁与活锁（七）顺序封锁法死锁与活锁（七）顺序封锁法 t1t2 lock r1成功成功 对对r1进行操作进行操作 lock r1 lock r2成功成功 对对r2进行操作进行操作 commit unlock r1,r2 等待等待 等待等待 等待等待 等待等待 等待等待 lock r1成功成

22、功 对对r1进行操作进行操作 lock r2成功成功 对对r2进行操作进行操作 commit unlock r1，r2 死锁与活锁（六）死锁与活锁（六） 4死锁检测死锁检测 超时法超时法 如果一个事务的等待时间超过了规定的期限，就如果一个事务的等待时间超过了规定的期限，就 认为发生了死锁。认为发生了死锁。 等待图法等待图法 事务等待图是一个有向回路事务等待图是一个有向回路g=(t, u)。t为结点为结点 的集合，每个结点表示正在运行的事务；的集合，每个结点表示正在运行的事务；u为边为边 的集合，每条边表示事务等待的情况。若的集合，每条边表示事务等待的情况。若t1等等 待待t2，则，则t1，t2

23、之间画一条有向边，从之间画一条有向边，从t1指向指向 t2。事务等待图动态地反映了所有事务的等待。事务等待图动态地反映了所有事务的等待 情况。并发控制子系统周期性的检测事务等待图，情况。并发控制子系统周期性的检测事务等待图， 如果发现图中存在回路，则表示系统出现死锁。如果发现图中存在回路，则表示系统出现死锁。 死锁与活锁（七）死锁与活锁（七） t2 t1t3 事务号事务号占有资源号占有资源号请求资源号请求资源号 t1r1r2 t2r2r3 t3r3r1 死锁与活锁（八）死锁与活锁（八） 4死锁恢复死锁恢复 dbms的并发控制子系统一旦检测到系统中的并发控制子系统一旦检测到系统中 存在死锁，就要

24、设法解除。通常采用的方法存在死锁，就要设法解除。通常采用的方法 是选择一个处理死锁代价最小的事务，将其是选择一个处理死锁代价最小的事务，将其 撤销，释放此事务持有的所有锁，使其他事撤销，释放此事务持有的所有锁，使其他事 务得以继续运行下去。对于所撤销的事务所务得以继续运行下去。对于所撤销的事务所 作的操作必须加以恢复。作的操作必须加以恢复。 事务的调度与可串行性事务的调度与可串行性 串行调度串行调度 在串行调度中，属于同一事务的指令紧挨在一起。在串行调度中，属于同一事务的指令紧挨在一起。 对于有对于有n个事务的事务组，可以有个事务的事务组，可以有n！个有效调！个有效调 度。度。 并行调度并行调

25、度 在并行调度中，来自不同事务的指令可以交叉执在并行调度中，来自不同事务的指令可以交叉执 行。行。 可串行性调度（一）可串行性调度（一） 4问题：计算机系统对并发事务中并发操作问题：计算机系统对并发事务中并发操作 的调度是随机的，而不同的调度可能产生的调度是随机的，而不同的调度可能产生 不同的结果，那么哪个结果是正确的呢？不同的结果，那么哪个结果是正确的呢？ 4定义：多个事务的并发执行是正确的，当定义：多个事务的并发执行是正确的，当 且仅当其结果与按某一次序串行的执行它且仅当其结果与按某一次序串行的执行它 们时的结果相同，我们称这种调度策略为们时的结果相同，我们称这种调度策略为 可串行化调度。

26、一个给定的并发调度，当可串行化调度。一个给定的并发调度，当 且仅当它是可串行化的，才认为是正确调且仅当它是可串行化的，才认为是正确调 度。度。 可串行性调度（二可串行性调度（二） t1t2 slock b成功成功 y=b= 2 unlock b xlock a a=y+1 写回写回a(=3) unlock a slock a x=a=3 unlock a xlock b b=x+1 写回写回b(=4) unlock b t1t2 slock a x=a=2 unlock a xlock b b=x+1 写回写回b(=3) unlock b slock b成功成功 y=b=3 unlock b

27、xlock a a=y+1 写回写回a(=4) unlock a 可串行性调度（三可串行性调度（三） t1t2 slock b y=b=2 slock a x=a=2 unlock b unlock a xlock a a=y+1 写回写回a(=3) xlock b b=x+1 写回写回b(=3) unlock a unlock b t1t2 slock b成功成功 y=b=2 unlock b xlock a slock a a=y+1 写回写回a(=3) unlock a 等待等待 等待等待 等待等待 x=a=3 unlock a xlock b b=x+1 写回写回b(=4) unloc

28、k b 可串行性调度（四）可串行性调度（四） 4两段锁协议两段锁协议(two-phase locking) 在对任何数据进行读、写操作之前，事务在对任何数据进行读、写操作之前，事务 首先要获得对该数据的封锁。首先要获得对该数据的封锁。 在释放一个封锁之后，事务不再获得任何在释放一个封锁之后，事务不再获得任何 其它封锁。其它封锁。 可串行性调度（五）可串行性调度（五） 所谓两阶段锁协议的含义是指所有事务必须所谓两阶段锁协议的含义是指所有事务必须 分两个阶段对数据项加锁和解锁。第一阶段分两个阶段对数据项加锁和解锁。第一阶段 是获得封锁也称扩展阶段。在这一阶段，事是获得封锁也称扩展阶段。在这一阶段，

29、事 务可以申请获得任何数据项上的任何类型的务可以申请获得任何数据项上的任何类型的 封锁，但不能释放任何锁。第二阶段是释放封锁，但不能释放任何锁。第二阶段是释放 阶段，也称收缩阶段。在这阶段，事务可以阶段，也称收缩阶段。在这阶段，事务可以 释放任何数据项上的任何类型的封锁，但是释放任何数据项上的任何类型的封锁，但是 不能够再申请任何锁。不能够再申请任何锁。 定理：若所有事务均遵从两段锁协议，则这定理：若所有事务均遵从两段锁协议，则这 些事务的所有并行调度都是可串行化的。些事务的所有并行调度都是可串行化的。 可串行性调度（六）可串行性调度（六） t1t2 slock b成功成功 读读b= 2 y=

30、b xlock a slock a 等待等待 a=y+1 写回写回a=3 unlock b unlock a 等待等待 等待等待 等待等待 等待等待 t1t2 slock a成功成功 读读a=3 y=a xlock b成功成功 b=y+1 写回写回b=4 unlock b unlock a 可串行性调度（七）可串行性调度（七） t1t2 slock b成功成功 读读b= 2 y=b ulock b xlock a slock a 等待等待 a=y+1 写回写回a=3 unlock a 等待等待 等待等待 等待等待 等待等待 t1t2 slock a成功成功 读读a=3 y=a unlock a

31、 xlock b成功成功 b=y+1 写回写回b=4 unlock b 可串行性调度（八）可串行性调度（八） 4两阶段锁协议与死锁两阶段锁协议与死锁 t1t2 slock b成功成功 读读b=2 slock a成功成功 读读a=2 xlock a 等待等待 等待等待 xlock b 等待等待 多粒度封锁（一）多粒度封锁（一） 4封锁粒度封锁粒度 封锁对象的大小称为封锁粒度封锁对象的大小称为封锁粒度 封锁对象：包括逻辑单元，如封锁对象：包括逻辑单元，如:属性值、属性值集合、属性值、属性值集合、 元组、关系、某索引项、整个索引、整个数据库；和元组、关系、某索引项、整个索引、整个数据库；和 物理单元

32、如：物理页、块。物理单元如：物理页、块。 封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度大，则并发度低，封锁机构简单，开销小。 封锁粒度小，则并发度高，封锁机构复杂，开销高。封锁粒度小，则并发度高，封锁机构复杂，开销高。 如果在一个系统中同时支持多种封锁粒度供不同的事如果在一个系统中同时支持多种封锁粒度供不同的事 务选择是比较理想的，这种封锁方法称为多粒度封锁务选择是比较理想的，这种封锁方法称为多粒度封锁 （multiple granularity locking）。选择封锁粒度时）。选择封锁粒度时 应同时考虑封锁开销和并发度两个因素，适当选择封应同时考虑封锁开销和并发度两个因素，适当选择封 锁粒度以达到最优效果。锁粒度以达到最优效果。 多粒度封锁（二）多粒度封锁（二） 4多粒度树多粒度树 多粒度树的根结点是整个数据库，表示最大多粒度树的根结点是整个数据库，表示最大 的粒度。叶结点表示最小的粒度。的粒度。叶结点表示最小的粒度。 数据库 关系rn关系r1 元组元组元组元组 多粒度封锁（三）多粒度封锁（三） 4多粒度封锁协议多粒度封锁协议 多粒度封锁协议允许多粒度树中的每个结点多粒度封锁协议允许多粒度树中的每个结点 被独立地加锁。对一个结点加锁意味着这个被独立地加锁。对一个结