文档介绍：数据库系统概论99
内容提要
并发控制是数据库管理系统的重要组成部分，通过本章的学习，应重点掌握：
并发控制带来的新问题
封锁及封锁协议
并发调度的可串行性
两段锁协议
2
数据库系统概论
概述
在单处理机系统中交付系统，否则可能再发生死锁。
18
数据库系统概论
死锁的解除（2）
选择哪个事务作为牺牲者，由下列几种选法：
选择最迟交付的事务作为牺牲者
选择获得锁最少的事务作为牺牲者
选择撤销代价最小的事务作为牺牲者
19
数据库系统概论
死锁的预防—一次封锁法
一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁。
缺点：
有些数据对象过早的加锁，降低了并发度
如果有些事务需要访问的“热点”数据比较多，其它事务总是不断的占有其中某些数据，不能一次获得所需要数据的全部，就会一直等待下去，易发生活锁。
20
数据库系统概论
死锁的预防—顺序封锁法
顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。
缺点：
数据库中一般是按内容访问，而不是按名访问，所以很难预先确定所有的访问对象
数据经常变动，次序也经常调整
上述两种方法用于数据库系统不实际。
21
数据库系统概论
死锁的预防—事务重执（1）
事务重执：当事务申请锁而未获准时，不是一律等待，而是让一些事务撤销重执。
为区别事务开始执行的先后，每个事务开始执行时，赋予一个唯一的、随时间增长的整数，称为时间标记，记为ts。如两个事务TA和TB，若ts（TA）< ts（TB），表明TA比TB“年老”
事务重执有两种策略
等待—死亡策略
击伤—等待策略
22
数据库系统概论
死锁的预防—事务重执（2）
等待—死亡策略
设TB持有某对象数据的锁，当TA申请同一数据的锁发生冲突时，按如下规则处理：
If ts(TA)<ts(TB) then TA waits;
else {
rollback TA； / *die* /
restrat TA with the same ts(TA);
}
总是年老的事务等待年轻的事务。
23
数据库系统概论
死锁的预防—事务重执（3）
击伤—等待策略
设TB持有某对象数据的锁，当TA申请同一数据的锁发生冲突时，按如下规则处理：
If ts(TA)>ts(TB) then TA waits;
else {
rollback TB； / *wound* /
restrat TB with the same ts(TB);
}
总是年轻的事务等待年老的事务。
24
数据库系统概论
死锁的预防—事务重执（4）
上述两种策略中，当冲突发生时，总是以年轻的事务作为牺牲品。因为年轻的事务随着时间的流逝，总会变成年老的事务，不致永远成为牺牲品。
25
数据库系统概论
并发调度的可串行性（1）
定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度策略为可串行化的调度。
可串行性是并发事务正确性的准则。按这个规则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。
对于n个事务，可有n!中排列次序，即有n!种串行调度。
26
数据库系统概论
并发调度的可串行性（2）
一个调度S是否可串行化，可用前趋图来测试。前趋图是有向图，点表示所有参与调度的事务对于边，当满足下列条件之一时，加入：
Ri(x)在Wj(x)之前
Wi(x)在Rj(x)之前
Wi(x)在Wj(x)之前
若前趋图中有回路，则S显然不等价于任何串行调度，若无回路，则可用拓扑排序得到一个串行调度。
27
数据库系统概论
并发调度的可串行性（3）
设有事务集{T1,T2,T3,T4}的一个调度：
S=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x)
试检验S是否可串行化。
分别分析对x,y,z的所有操作，画出前趋图。
T2
T1 T4 T1,T3,T2,T4
T3
28
数据库系统概论
并发调度的可串行性（4）
可串行化调度和串行调度是有区别的：
前者交叉执行各事务操作，在效果上相当于事务的某一串行执行
后者完全是串行执行各事务，失去并发意义，不能充分利用系统资源
DBMS并发控制的任务就是保证事务执行的可串行化，比较有效的方法是要求DBMS按一定的封锁协议调度事务，以保证其执行可串行化。
两段锁协议