数据库的并发控制
1、为什么要进行并发控制
数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时就会产生同时读取/修改同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。所以数据库管理系统必须提供并发控制机制。
在单处理机系统中，事务的并行执行实际上是这些并行事务的并行操作轮流交叉运行，称为交叉并发方式。
在多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行，称为同时并发方式。
使用并发的目的：一是改善系统的资源利用率，二是改善短事务的响应时间。
2、并发操作可能会产生哪几类数据不一致？用什么方法能避免？
并发操作带来的数据不一致性包括三类：丢失修改、不可重复读、读“脏”数据。
(1)丢失修改<lost update>：两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了(覆盖了)T1提交的结果，导致T1的修改被丢失。
--丢失修改是“写-写冲突”
(2)不可重复读<Non-Repeatable Read>：不可重复读是指事务T1读取数据后，事务执行更新操作，使T1无法再现前一次读取结果。
--不可重复读是“读-写冲突”
(3)读“脏”数据<Dirty Read>：读“脏”数据是指事务T1修改某一数据，并将其写回磁盘，事务读取同一数据后，T1由于某种原因被撤销，这时T1已修改过的数据恢复原值，读到的数据就与数据库中的数据不一致，则读到的数据就为“脏”数据，即不正确的数据。
--读“脏”数据是“读-写冲突”
避免不一致性的方法和技术就是并发控制。最常用的并发控制技术是封锁技术。也可以用其他技术，例如在分布式数据库系统中可以采用时间戳方法来进行并发控制。它的任务就是用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，避免造成数据的不一致性。
3、什么是封锁？基本的封锁类型及其含义？
封锁就是事务 T 在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务 T 就对该数据对象有了一定的控制，在事务 T 释放它的锁之前，其他的事务不能更新此数据对象。
封锁是实现并发控制的一个非常重要的技术。
封锁类型：排它锁(Exclusive Locks|X锁)和共享锁(Share Locks|S锁)
排它锁：又称写锁，若事务 T 对数据对象 A 加上 X 锁，则只允许 T 读取和修改 A，其它任何事务都不能再对 A 加任何类型的锁，直到 T 释放 A 上的 X 锁。
共享锁：又称读锁，若事务 T 对数据对象 A 加上 S 锁，则事务 T 可以读 A 但不能修改 A，其它事务只能再对 A 加 S 锁，而不能加 X 锁，直到 T 释放 A 上的 S 锁。
X锁和S锁的相容矩阵：(最左边表示T1已经获得的锁的类型，最上面表示T2的封锁请求，-表示没有加锁)
|
T2
T1
|
S
|
X
|
-
|
|
S
|
Y
|
N
|
Y
|
|
X
|
N
|
N
|
Y
|
|
-
|
Y
|
Y
|
Y
|
4、封锁协议的类型和概念
一级封锁协议：事务 T 在修改数据 R 之前必须先对其加 X 锁，直到事务结束才释放。事务结束包括正常结束(COMMIT)和非正常结束(ROLLBACK)。
----一级封锁协议中，如果是读数据不修改，是不需要加锁的，可防止丢失修改。
没有丢失修改：
|
T1
|
T2
|
|
① Xlock A
|
|
|
获得
|
|
|
② 读A=16
|
|
|
|
Xlock A
|
|
③A←A-1
|
等待
|
|
写回
|
等待
|
|
A=15
|
等待
|
|
Commit
|
等待
|
|
Unlock A
|
等待
|
|
④
|
获得Xlock A
|
|
|
读A=15
|
|
|
A←A-1
|
|
|
写回A=14
|
|
⑤
|
Commit
|
|
|
Unlock A
|
不能重复读：
|
T1
|
T2
|
|
①读A=50
|
|
|
读B=150
|
|
|
求和 =150
|
|
|
②
|
Xlock B
|
|
|
获得
|
|
|
读B=100
|
|
|
B←B*2
|
|
|
写回
|
|
|
B=200
|
|
|
Commit
|
|
|
Unlock B
|
|
③读A=50
|
|
|
读B=200
|
|
|
求和 =250
|
|
|
(验算不对)
|
|
二级封锁协议：在一级封锁协议基础上，加上事务T在读数据R之前必须先对其加上S锁，读完后即可释放S锁。
----在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。
依旧不可重复读：
|
T1
|
T2
|
|
①Slock A
|
|
|
获得
|
|
|
读A=50
|
|
|
Unlock A
|
|
|
②Slock B
|
|
|
获得
|
Xlock B
|
|
读B=100
|
等待
|
|
Unlock B
|
获得Xlock B
|
|
③求和 =150
|
读B=100
|
|
|
B←B*2
|
|
|
写回B=200
|
|
|
Commit
|
|
|
Unlock B
|
|
④Slock A
|
|
|
获得
|
|
|
读A=50
|
|
|
Unlock A
|
|
|
Slock B
|
|
|
获得
|
|
|
读B=200
|
|
|
Unlock B
|
|
|
求和=250
|
|
|
(验算不对)
|
|
三级封锁协议：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。
----三级封锁协议除了防止了丢失修改和不读“脏”数据外，还进一步防止了不可重复读。
可重复读：
|
T1
|
T2
|
|
①Slock A
|
|
|
读A=50
|
|
|
Slock B
|
|
|
读B=100
|
|
|
求和 =150
|
|
|
②
|
Xlock B
|
|
|
等待
|
|
③ 读A=50
|
等待
|
|
读B=100
|
等待
|
|
求和=150
|
等待
|
|
Commit
|
等待
|
|
Unlock A
|
等待
|
|
Unlock B
|
等待
|
|
④
|
获得Xlock B
|
|
|
读B=100
|
|
|
B←B*2
|
|
|
写回B=200
|
|
|
Commit
|
|
|
Unlock B
|
不读“脏”数据：
|
T1
|
T2
|
|
①Xlock C
|
|
|
读A=100
|
|
|
C←C*2
|
|
|
写回C=200
|
|
|
②
|
Slock C
|
|
|
等待
|
|
③ROLLBACK
|
等待
|
|
(C恢复为100)
|
等待
|
|
Unlock C
|
等待
|
|
④
|
获得Slock C
|
|
|
读C=100
|
|
|
Commit C
|
|
⑤
|
Unlock C
|
封锁协议总结：
|
|
X锁
|
S锁
|
一致性保证
|
|
|
操作结束释放
|
事务结束释放
|
操作结束释放
|
事务结束释放
|
不丢失修改
|
不读脏数据
|
可重复读
|
|
1级封锁
|
|
√
|
|
|
√
|
|
|
|
2级封锁
|
|
√
|
√
|
|
√
|
√
|
|
|
3级封锁
|
|
√
|
|
√
|
√
|
√
|
√
|
5、什么是“活锁”？什么是“死锁”？以及避免方法。
若某数据对象加了 S 锁，这时若有其它事务申请对它的 X 锁，则需等待。但此时若有其它事务申请对它的 S 锁，按相容矩阵，应可获准。如果不断有事务申请对此数据对象的 S 锁，以致它始终被 S 锁占有，而 X 锁的申请迟迟不能获准——这种现象叫活锁。
避免活锁的简单方法是采用“先来先服务”策略，即T1用S锁锁住A，T2申请X锁等待，此时T3申请S锁也不获准，因为T2尚未得到服务。
一个事务如果申请锁而未获准，则需等待其它事务释放锁。如果事务中出现循环等待时，如果不加干预，则会一直等待下去——这叫死锁。
避免死锁主要有两种方法：一次封锁法 & 顺序封锁法
一次封锁法
：要求每个事务必须一次将所有要使用的数据全部加锁。
缺点：
1.有些数据对象过早的加锁，降低了并发度。
2.如果有些事务需要访问的“热点”数据比较多，其它事务总是不断的占有其中某些数据，不能一次获得所需要数据的全部，就会一直等待下去，易发生活锁。
3.难以确定封锁对象
顺序封锁法：预先对数据对象规定一个封锁顺序,所有事务都按这个顺序实行封锁.
缺点:
1.数据库中一般是按内容访问，而不是按名访问，所以很难预先确定所有的访问对象
2.数据经常变动，次序也经常调整，维护成本很高
总得来说，以上这两种在操作系统中广泛使用的预防死锁策略都不太适合在数据库中使用，在数据库中使用比较广泛的方法是：诊断&解除。
具体来说就是允许死锁的发生，但设置规则诊断出现死锁后即进行解除。
6、列举死锁的诊断方法以及解除方法？
死锁诊断主要有以下两种方法：
超时法：如果一个事务的等待时间超过了某个时限，就认为发生死锁。
优点：简单
缺点：一是事务因其它原因(如系统负荷太重,通信受阻等)而使事务等待时间超过时限，可能被误判死锁。二是时限的设置。
等待图法：等待图是一个有向图G=(T,U)。T为结点的集合，每个结点表示正在运行的事务；U为边的集合，每条边表示事务等待的情况。当且仅当等待图中出现回路时，死锁发生。
优点：比较准确
缺点：维护成本高
死锁的解除方法(必须由DBMS干预)：
1.在循环等待的事务中，选一个事务作为“牺牲者”，给其它事务让路
2.撤销牺牲的事务，释放其获得的锁及其它资源
3.将释放的锁让给等待它的事务
4.被牺牲的事务可以有两种处理：
* 发消息给有关用户，由用户向系统再交付该事务
* 由DBMS重新启动该事务
注：被牺牲的事务应等待一段时间才能交付系统，否则可能再发生死锁。
牺牲者的选择方法：
1.选择最迟交付的事务作为牺牲者
2.选择获得锁最少的事务作为牺牲者
3.选择撤销代价最小的事务作为牺牲者
7、什么样的并发调度是正确的调度？
可串行化 (Serializable) 的调度是正确的调度。
可串行化的调度的定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行执行它们时的结果相同，称这种调度策略为可串行化的调度。
注：一般不可串行化的并发调度产生的结果都会与串行调度结果有误差。
两段锁协议(2PL)是保证并发调度可串行化的封锁协议。
两段锁协议是指所有事务必须分两个阶段对是数据项加锁和解锁。
在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁——扩展阶段
在释放一个封锁之后，事物不再申请和获得任何其它封锁——收缩阶段
若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都可是可串行化。(充分条件)(可用反证法证明)
两段锁协议和一次封锁法的异同：
一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议
两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此可能会发生死锁
证明若并发事务遵守两段锁协议，则对这些事务的并发调度是可串行化的
首先以两个并发事务 Tl 和T2为例，存在多个并发事务的情形可以类推。根据可串行化定义可知，事务不可串行化只可能发生在下列两种情况：
(l) 事务 Tl 写某个数据对象 A ，T2读或写 A ;
(2) 事务 Tl 读或写某个数据对象 A ，T2写 A 。
下面称 A 为潜在冲突对象。
设 Tl 和T2访问的潜在冲突的公共对象为{A1,A2,…,An}。不失一般性，假设这组潜在冲突对象中 X ={A1,A2,…,Ai}均符合情况(1)，Y ={Ai+1,…,An｝符合情况(2)。
Tl 需要 XlockX ①
T2 需要 Slockx 或 Xlockx ②
1) 如果操作①先执行，则 Tl 获得锁，T2等待，由于遵守两段锁协议，Tl 在成功获得 X 和 Y 中全部对象及非潜在冲突对象的锁后，才会释放锁。这时如果存在 w∈X 或 Y ，T2已获得 w 的锁，则出现死锁；否则，Tl 在对X、Y中对象全部处理完毕后，T2才能执行。这相当于按 Tl 、T2的顺序串行执行，根据可串行化定义，Tl 和T2的调度是可串行化的。
2) 操作 ② 先执行的情况与(l)对称因此，若并发事务遵守两段锁协议，在不发生死锁的情况下，对这些事务的并发调度一定是可串行化的。证毕。
8、为什么要引进意向锁？意向锁的含义是什么？
引进意向锁是为了提高封锁子系统的效率。该封锁子系统支持多种封锁粒度。
原因是：在多粒度封锁方法中一个数据对象可能以两种方式加锁——显式封锁和隐式封锁。因此系统在对某一数据对象加锁时不仅要检查该数据对象上有无(显式和隐式)封锁与之冲突，还要检查其所有上级结点和所有下级结点，看申请的封锁是否与这些结点上的(显式和隐式)封锁冲突。显然，这样的检查方法效率很低。为此引进了意向锁。
意向锁
的含义是：对任一结点加锁时，必须先对它的上层结点加意向锁。例如事务 T 要对某个元组加 X 锁，则首先要对关系和数据库加 ix 锁。换言之，对关系和数据库加 ix 锁，表示它的后裔结点——某个元组拟(意向)加 X 锁。
引进意向锁后，系统对某一数据对象加锁时不必逐个检查与下一级结点的封锁冲突了。例如，事务 T 要对关系 R 加 X 锁时，系统只要检查根结点数据库和 R 本身是否已加了不相容的锁(如发现已经加了 ix ，则与 X 冲突)，而不再需要搜索和检查 R 中的每一个元组是否加了 X 锁或 S 锁。
附录：
---------
比较详细的PPT介绍：
解题答案来源：