例4 T1 、T2 的另一个可串行化调度S4 ： S4 = { R2 (x); x := x – 20; W2 (x); R1 (x); x := x +10; W1 (x); R2 (y); y := y * 2; W2 (y); C2 R1 (y); y := y –15; W1 (y); C1 } 例5 T1 、T2 的一个不可串行化调度S5 ： S5 = { R1 (x); x := x +10; W1 (x); R2 (x); x := x – 20; W2 (x); R2 (y); y := y * 2; W2 (y); C2 R1 (y); y := y –15; W1 (y); C1 }
Lock-S(a1)
Lock-S(a2) Lock-S(a2) Lock-S(a3) Lock-S(a4) unLock-S(a1) unLock-S(a2) Lock-S(an) upgrade(a1)
（7）多粒度锁及意向锁：
多粒度加锁的特点:
•显式加锁：树上每个结点都可以单独加锁。
•隐式加锁：对当前结点加锁会导致隐式地对全部后代 结点加上同类型的锁。 •检查锁冲突时，必须检查祖先、后代结点！ 对锁类型进行扩充：意向锁： 一个事务对一个数据对象显式加锁之前，必须对它的 全部祖先结点加意向锁。
某一并行调度S经过非冲突指令转换成串行调度，且其 该串行调度的执行结果一致，则S是冲突可串行化的。
T1
Read(A) Write(A)
T2
T1 Read(A) Write(A)
T2
Read(A)
Read(A)
Read(B)
Read(B)
Write(A)
Write(A)
Write(B)
Write(B)
Read(B) Write(B)
Read(B) Write(B)
T1 Read(A)
T2
Write(A)
非冲突可串行的调度
Write(A)
* 关于冲突可串行性调度的讨论 1. 构造冲突可串行性调度 允许不同事务上的非冲突操作交换执行次序。 2.冲突可串行调度必定是一致性调度。 3.冲突可串行性不是可串行性的必要条件。即，可串 行性不一定是冲突可串行性。存在其它可串行调度策 略！（如，视图可串行性调度）。
B
IS
IX Da
S T3 Db Dc
S r1 r2
X r3 rb1 rb2 rc1 rc2
T1
T2
多粒度锁协议在由如下事务类型混合 而成的应用中有用： •只存取几个数据项的短事务 •由整个文件或一组文件形成报表 的长事务
（8）封锁机制的实现是由锁管理器执行，锁管理器通 过维护锁表控制加锁机制。
3 死锁的处理
T1
Read(A) A=A-50 Write(A)
T2
Read(B) B=B+50 Write(B)
Read(B) B=B-10 Write(B)
非冲突可串行的调度, 但其与串行调度的执 行结果相同
Read(A) A=A+10 Write(A)
串行调度： T1 Write(A) Write(B) T2 T3
•基于超时的机制：事先给出事务的等待的时间，超时即 回滚。
死锁的检验：等待图
T1 T2 T1 T2
T3
T4Biblioteka T3T4无死锁等待图
有死锁等待图
系统周期对等待图进行环搜索，以检测有无死锁。周期
的长短受死锁发生的频率以及受影响事务的数目两个因
素有关。
从死锁中恢复：选择事务回滚 选择代价最小的事务。 回滚事务 防止饿死，将回滚次数考虑在代价中
∴ 如果一个结点上有意向锁，则它的后代结点必有被 显式加锁。
意向锁分类： •IS锁(Intent Share Lock): 若对某结点加IS ，那么 将对后代结点显式地加S 锁。 •IX锁(Intent Exclusive Lock): 若对某结点加IX锁， 那么将对后代结点显式地加X锁。 •SIX锁(Share Intent Exclusive Lock): 若对某结点加 SIX锁，则对该结点不仅显式地S锁，而且还对它加了IX 锁。即，SIX = S + IX
基于锁的协议开销较大，并发的提升有限度。
§3 基于时间戳的调度协议
时间戳：数据库系统赋予事务的唯一 的时间标记，以标 记该事务开始执行。 系统时钟值或逻辑计数值 时间戳的基本原理：事务的时间戳决定串行化顺序，如 果TS（Ti）<TS（Tj）,则系统必须保证产生的调度等价 于Ti，Tj串行调度。 TS(T)---时间戳 TS（Ti)<TS(Tj)---事务i比j开始的早 W(Q)—在数据项Q上成功执行写操作的所有事务的最大 时间戳 R(Q)—在Q上执行读的所有事务的最大时间戳
读数据D 时间 事务B
t1
t2 读数据D
修改数据D
t3 t4 修改数据D?
②读入“脏”数据 事务A 读数据D 修改数据D
时间
t1 t2
事务B
t3
事务回退 t4
读数据D?
③不可重复的读 事务A 时间 t1 读数据D 修改数据D t2 事务B
读数据D
t3
t4
读数据D?
（2）调度：若T = { T1 , T2 , „„,Tn }是一组并发 执行的事务，则T中各事务的重要操作按时间排序的一 个序列，记S = {Σ T,,∠T}，是T 的一个调度。
（3）冲突可串行化：Ti={I1,I2„In},Tj={J1,J2,„,Jm}
则考虑两条指令Ii,Jk的以下情况： Ii=read(Q),Jk=read(Q) 次序无关紧要
Ii=read(Q),Jk=write(Q)
Ii=write(Q),Jk=read(Q)
次序重要
次序重要 Ii,Jk是冲突的
Ii=write(Q),Jk=write(Q) 次序重要
Read(A)
Lock-S(B) Read(B) Write(A) unlock(A) commit
要求：事务持有的排 它锁必须在事务提交 后方可释放。
Lock-X(A) Read(A) write(A) unlock(A) commit Lock-S(A) Read(A)
强两阶段锁协议：要求事务提交之前不得释放任何锁。 大部分数据库系统采用严格两阶段锁协议或强两阶段 锁协议。
（4）加锁产生的问题： ①不正确加锁产生错误结果:B=200,A=100
T1 Lock-X(B) Read(B) B=B-50 Write(B) Unlock(B) T2 管理器 grant-X(B,T1)
Lock-S(A) Read(A) unlock(A) Lock-S(B) Read(B) Unlock(B) Display(A+B)
死锁:两个或两个以上事务处于等待状态，每个事务都 在等待其中另一个事务释放资源，导致所有事务都 无法执行。这种现象称为死锁。
处理死锁方法:
（1）引入死锁预防协议，使系统不进入死锁状态: 通过对加锁请求进行排序，一事务开始前要锁定所有 的数据项。
（2）允许系统进入死锁状态，引入死锁检测和死 锁恢复机制进行恢复。
B=B-50 Write(B)
Lock-X(A)
Read(A)
A=A+50
两个事务相互 等待数据，进 入死锁状态！
Write(A)
Unlock(B)
Unlock(B)
unlock(A)
③产生饿死现象：
T1
Lock-S(A) Lock-X(A) Write(A) Lock-S(A)
T2
T3
等待。。。
Write(A)
Write(B)
Write(B)
T1
T2
T3
Write(A)
Write(A) Write(B) Write(B) 非冲突可串行的调度, 但其与串行调度的执 行结果相同！ Write(B)
冲突可串行性的判断：优先图 优先图由节点和有向弧两种元素构成，节点表示事务， 有向弧表达事务的先后次序。 事务的先后次序由冲突动作的先后次序决定。
a. 串行调度：若对于一个调度S 中的任意两个事务Ti 和Tj, i≠j, Σ i<Σ j,或Σ j<Σ i. b. 一致性调度: 如果执行一个调度S ，使数据库从一个一致性状 态转入另一个一致性状态，则称S 是一个一致性调 度。 注： 数据库状态的“一致性”与业务规则有关。
例：
这两个调度 均为串行调度
T1 Lock-X(B) Read(B) B=B-50 Write(B) Lock-X(A) Read(A) A=A+50 Write(A)
T2
T1
Lock-S(A) Read(A) Lock-S(B) Read(B)
T2
Unlock(B)
unlock(A)
Display(A+B) unlock(A) Unlock(B)
T1
T2
T3
T4
T1
T1
T1
T2
T3
T2
T3
T3 T4 T4
T2
T4
可串行化调度
T1
T2
不可串行化调度
§2 基于锁的协议
（1）锁的基本模式： •共享锁（Shared---S锁）：允许执行读操作 •排它锁（Exclusive---X锁）：允许执行读/写操作 （2）锁的调度策略： •解除一个数据对象的排它锁之前，其它事务不能对它 加任何锁。 •一个数据对象允许加几个共享锁，但不能在共享锁之 上，加排它锁。 S X （3）锁的相容矩阵： S T F X F F
但这两种协议并行程度较低，有时为提高并行能力， 采用锁转换机制，在写的时候将S锁转换成X锁，写完 后再降为S锁。