11.1并发控制概述

11.1.1多事务执行方式

1. 事务串行执行
2. 交叉并发执行
3. 同时并发执行

11.1.2并发控制机制的任务

• 对并发操作进行正确调度
• 保证事务的隔离性
• 保证数据库的一致性

11.1.3并发操作带来的数据不一致性

1. 丢失修改（ Lost Update）
2. 不可重复读（ Non-repeatable Read）
3. 读“脏”数据（ Dirty Read）

丢失修改(写—写)

两个事务T1和T2读入同一数据并修改，T2的提交结果破坏了T1提交的结果，导致T1的修改被丢失。

不可重复读(读—更新)

不可重复读是指事务T读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果。
包括三种情况：

1. 读—修改
2. 读—删除
3. 读—插入

读“脏”数据

事务T1修改某一数据，并将其写回磁盘事务，T2读取同一数据后，T1由于某种原因被撤销，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，T2读到的数据就为“脏”数据，即不正确的数据

操作不一致性

并发操作破坏了事务的隔离性

11.1.4并发控制的主要技术

• *（ Locking）
• 时间戳（ Timestamp）
• 乐观控制法
• 多版本并发控制（MVCC）

11.2*

11.2.1什么是*

• *就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁
• 加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。

11.2.2基本*类型

• 排它锁（ Exclusive locks，简记为X锁）
• 共享锁（ Share locks，简记为S锁）

排它锁（写锁）

若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁
保证其他事务在T释放A上的锁之前不能再读取和修改A

共享锁（读锁）

若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁
保证其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改

11.3*协议

在运用X锁和S锁对数据对象加锁时，需要约定一些规则，这些规则为*协议（ Locking Protocol）。

• 何时申请X锁或S锁
• 持锁时间
• 何时释放

11.3.1三级*协议

1. 一级*协议
2. 二级*协议
3. 三级*协议

11.3.2一级*协议

事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。

• 正常结束（ COMMIT）
• 非正常结束（ ROLLBACK）

作用

一级*协议可防止丢失修改，并保证事务T是可恢复的。
在一级*协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。

11.3.3二级*协议

一级*协议加上事务T在读取数据R之前必须先对其加s锁，读完后即可释放S锁。

作用

二级*协议可以防止丢失修改和读“脏”数据。
在二级*协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。

11.3.4三级*协议

一级*协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。

作用

三级*协议可防止丢失修改、读脏数据和不可重复读。

11.4活锁和死锁

11.4.1活锁

如果事务T1*了数据R，事务T2又请求*R，于是T2等待。T3也请求*R，当T1释放了R上的*之后系统首先批准了T3的请求，T2仍然等待。然后T4又请求*R，当T3释放了R上的*之后系统又批准了T4的请求，…，T2有可能永远等待，这就是活锁的情形

解决方法

采用先来先服务的策略

• 当多个事务请求*同一数据对象时
• 按请求*的先后次序对这些事务排队
• 该数据对象上的锁一旦释放，首先批准申请队列中第个事务获得锁

11.4.2死锁

如果事务T1*了数据R1，T2*了数据R2，然后T1又请求*R2，因T2已*了R2，于是T1等待T2释放R2上的锁。接着T2又申请*R1，因T1已*了R1，T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2，而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成死锁。

解决方法

• 死锁的预防——破坏产生死锁的条件
• 死锁的诊断与解除

死锁的预防

• 一次*法——要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行
• 顺序*法——顺序*法是预先对数据对象规定一个*顺序，所有事务都按这个顺序实行*。

在操作系统中广为采用的预防死锁的策略并不太适合数据库的特点，数据库管理系统在解决死锁的问题上更普遍采用的是诊断并解除死锁的方法

死锁的诊断与解除

• 超时法——如果一个事务的等待时间超过了规定的时限，就认为发生了死锁
• 等待图法——用事务等待图动态反映所有事务的等待情况，选择一个处理死锁代价最小的事务，将其撤消谓释放此事务持有的所有的锁，使其它事务能继续运行下去

11.5并发调度的可串行性

11.5.1可串行化调度

多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同

可串行性

是并发事务正确调度的准则
一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度

11.5.2冲突可串行化调度

冲突操作

是指不同的事务对同一数据的读写操作和写写操作，涉及同一个数据库元素，并且至少有一个是写操作
Ri（x）与Wj（x）
Wi（x）与Wj（x）

不能交换的动作

• 同一事务的两个操作
• 不同事务的冲突操作

冲突可串行化

一个调度S在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度S，如果S是串行的，称调度S是冲突可串行化的调度
若一个调度是冲突可串行化，则一定是可串行化的调度
冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度

11.6两段锁协议

指所有事务必须分两个阶段对数据项加锁和解锁

• 在对任何数据进行读、写操作之前，事务首先要获得对该数据的*
• 在释放一个*之后，事务不再申请和获得任何其他*

11.6.1“两段”锁的含义

事务分为两个阶段

• 第一阶段是获得*，也称为扩展阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
• 第二阶段是释放*，也称为收缩阶段，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁

11.6.2两段锁协议注意点

• 事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。
• 若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的
• 若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议
• 不遵守两段锁协议，对这些事务的并发调度策略可能是可串行化的，也可能不是可串行化的。
• 一次*法遵守两段锁协议，但两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁

11.7*的粒度

11.7.1*粒度的原则

• *的粒度越大，数据库所能够*的数据单元就越少，并发度就越小，系统开销也越小；
• *的粒度越小，并发度较高，但系统开销也就越大

多粒度*

在一个系统中同时支持多种*粒度供不同的事务选择

• 需要处理大量元组的用户事务：
• 以关系为*单元需要处理多个关系的大量元组的用户事务：以数据库为*单位
• 只处理少量元组的用户事务：以元组为*单位

11.7.2多粒度*

多粒度树

• 以树形结构来表示多级*粒度
• 根结点是整个数据库，表示最大的数据粒度
• 叶结点表示最小的数据粒度

多粒度*协议

允许多粒度树中的每个结点被独立地加锁
对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
在多粒度*中一个数据对象可能以两种方式*：显式*和隐式*

显式*

直接加到数据对象上的*

隐式*

是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁

系统检查*冲突

对某个数据对象加锁，系统要检查:

• 该数据对象
• 所有上级结点
• 所有下级结点

11.7.3意向锁

为了提高对某个数据对象加锁时系统的检查效率

意向锁的使用

• 如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁
• 对任一结点加基本锁，必须先对它的上层结点加意向锁数据库

常用意向锁

• 意向共享锁（ Intent share lock，简称IS锁）
• 意向排它锁（ Intent Exclusive lock，简称IX锁）
• 共享意向排它锁（ Share Intent Exclusive lock，简称SIX锁）

IS锁

如果对一个数据对象加s锁，表示它的后裔结点拟
（意向）加S锁。

IX锁

如果对一个数据对象加锁，表示它的后裔结点拟
（意向）加X锁。

SIX锁

如果对一个数据对象加S锁，表示对它加S锁，再加IX锁，即SIX=S+IX。

具有意向锁的多粒度*方法

• 申请*时应该按自上而下的次序进行
• 释放*时则应该按自下而上的次序进行

意向锁的好处

• 提高了系统的并发度
• 减少了加锁和解锁的开销
• 在实际的数据库管理系统产品中得到广泛应用