【从零开始学习计算机科学】数据库系统（七）并发控制技术

并发控制技术

数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时就会产生同时读取和／或修改同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。所以数据库管理系统必须提供并发控制机制。

封锁

封锁是实现并发控制的一个有效措施。

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

引入锁机制是为了保证数据的一致性(事务的隔离性)和提高系统的并发处理能力，或者说，为保了证应用的有效性。

给数据加锁的方式有许多种，目前我们考虑以下两种：

排他锁：简称X锁（又称写锁），若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何锁。直到T释放A上的锁。

共享锁：简称S锁（又称读锁），若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁为止。

S锁的目的是增强并发能力，因为可能95%以上的应用是读数据，更新应用的频率非常小。但是，没有S锁，系统的发处理能力会大大降低，仅比串行调度略好。

封锁协议

仅有封锁未必能保证调度的可串行化，因此我们需要一组加锁规则来保证调度的可串行化，因此，就引入了封锁协议。

具体来讲，封锁协议约定了对数据对象何时申请X锁或S锁，持续时间、何时释放等一系列规则。
对封锁方式规定不同的规则，就形成了各种不同的封锁协议。

封锁会带来的问题

活锁（饥饿）：如果事务$T_1$封锁了数据R，事务$T_2$又请求封锁数据R，于是$T_2$等待；$T_3$也请求封锁数据R，当$T_1$释放了R上的锁之后，系统首先批准了$T_3$的请求，$T_2$任然等待；然后$T_4$又请求封锁R，当$T_3$释放R上的锁之后，系统又批准了$T_4$的请求$\cdots$ $T_2$有可能永远等待，这就是活锁的情况。避免活锁的简单方法是：采用先来先服务策略。

死锁：如果事务$T_1$封锁了数据$R_1$，$T_2$封锁了数据$R_2$，然后$T_1$又请求封锁$R_2$，因$T_2$封锁了$R_2$，于是$T_1$等待$T_2$释放$R_2$上的锁；接着$T_2$又请求封锁$R_1$，因$T_1$封锁了$R_1$，于是$T_2$等待$T_1$释放$R_1$上的锁。这样就出现了$T_1$在等待$T_2$,而$T_2$又在等待$T_1$的局面，$T_1$、$T_2$两个事务永远不能结束，形成死锁。

解决死锁有两种思路，分别是死锁的预防和死锁的恢复。

死锁预防：预先防止死锁发生，保证系统永不进入死锁状态。

死锁检测与恢复：允许系统进入死锁状态，但要周期性地检测系统有无死锁。如果有，则把系统从死锁中恢复过来。

两种策略都会引起事务回滚。如果系统进入死锁状态的概率相对较高，则通常采用死锁预防策略；否则使用死锁检测与恢复更有效。

预防死锁的两种方法

一种方法是通过对加锁请求进行排序或者要求同时获得所有的锁来保证不会发生循环等待。这种方法又有以下两种子方法

一次封锁法：一次性将所有要使用的数据全部加锁，否则就不能继续执行。这种方法存在的问题主要有在事务开始前通常很难预知哪些数据项需要封锁。数据项使用率可能很低，因为许多数据项可能封锁很长时间却用不到。

顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按照这个顺序实施封锁。这种方法存在的问题有：数据库在动态地不断变化，要维护这样的资源的封锁顺序非常困难，成本很高。事务的封锁请求可以随着事务的执行而动态地决定，很难实现确定每一个事务要封锁哪些对象，因此很难按规定的顺序去施加封锁。

另一种方法比较接近死锁恢复，每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。

预防死锁的第二种方法，也是最有效的方法就是采用抢占与事务回滚技术。

在这种方法里，赋予每个事务一个唯一的时间戳，系统利用时间戳来决定事务应当等待还是回滚。但并发控制仍使用封锁机制。

若一个事务回滚，则该事务重启时保持原有的时间戳。

利用时间戳的两种不同的死锁预防机制如下：
等待-死亡(wait-die)机制：基于非抢占技术；
受伤-等待(wound-wait)机制 ：基于抢占技术。

等待-死亡机制

这种机制基于非抢占技术。当事务$T_i$申请的数据项当前被$T_j$持有，仅当TS($T_i$) < TS($T_j$)时，允许$T_i$等待。否则， T i T_i