事务并发调度的可串行性及两段锁协议

妖狐艹你老母 2023-02-22 10:59 37阅读 0赞

## 一、并发调度 ##

--------------------

并发调度啥意思？

就是当很多事务同时执行的时候应该按照什么顺序执行，应该按照排队的顺序执行，这就是 **串行调度** 。

串行执行肯定是正确的，但是改变一下位置有影响吗？

这就要看改变顺序之后执行的结果是否和不改变顺序执行的结果一致了。

如果改变顺序之后执行的结果和串行调度的执行结果一致，那么就说这种调度是 **可串行化调度**。

> 可串行性是并发事务正确调度的准则。

比如：

事务 T1： 读 B A=B+1；写回 A；
    事务 T2： 读 A B=A+1；写回 B；

假设 A、B 的初始值都是 2，串行调度指的就是先执行 T1 再执行 T2，或者先执行 T2 再执行 T1，这是没有区别的，都是正确的。

1、先执行 T1：结果是 A=3，B=4；
    2、先执行 T2：结果是 B=3，A=4；

其实这里执行的顺序可以是（`R`代表读，`W`代表写），这两个都是 **串行调度** ：

1、R1(B)  W1(A)  R2(A)  W2(B)
    2、R2(A)  W2(B)  R1(B)  W1(A)

**我们只需要保证对同一数据对象的 `读写（写读）操作`和 `写写操作` 的相对位置不变即可。**

涉及对同一数据对象的读写操作称为 **冲突操作** 。

解释一下前面的意思，这里的同一数据对象假设是 A ，`W1(A) R2(A)` 就是对`同一数据对象`的读写操作，那么他们的顺序是不能调换的，不然数据的结果就会改变。这里的顺序是先 写`A` 再读 `A` ，相对位置指的是他们中间可以有其他的操作。

比如，在上一个例子中，如果执行的顺序改成下面的样子：

R1(B)  R2(A)  W1(A)  W2(B)

这就不对了，因为改变了关于数据对象 `A` 的读写顺序，应该是先写再读，因为这两个是冲突操作，所以不能随便调换位置，现在调换了无论如何也不能通过 `交换不冲突操作的位置` 变成那两个串行调度中的任何一个了。

> 总之：不管是同一个事务还是多个事务操作，只要是涉及对同一数据对象的 `读写操作` 或 `写写操作` 调换顺序的时候就要谨慎一点，不要改变了原来的结果。

除了冲突操作之外的操作称为不冲突操作，如果一个调度通过 **交换不冲突操作** 的次序得到的另一个调度是串行的，那么称这个调度为 **冲突可串行化** 的调度。

> 冲突可串行化调度只是可串行化调度的一种。有的时候就算改变了位置结果也不变。

## 二、两段锁协议 ##

--------------------

两段锁协议是为了保证事务并发调度的正确性，简称 `2PL` 协议。

*  第一阶段是获得锁：`扩展阶段`：只允许加锁；
 *  第二阶段是释放封锁：`收缩阶段`：只允许解锁；

如果并发执行的所有事务都遵循两段锁协议，那么对这些事务的任何并发调度都是可串行化的。

可能大家回想到预防死锁时使用的 **一次封锁法** 。他们的区别在于两段锁协议只是说加锁的时候在一个阶段完成，没说要用的所有数据都必须加锁，而后者则要求所有使用到的数据必须加锁而且是在刚开始的加锁时期；所以只要是使用一次封锁法的协议都遵循两段锁协议，同时也说明两段锁协议也有死锁问题。

关于死锁这里提一嘴，有两种方法解决：

*  一是预防：一次封锁法、顺序封锁法；
 *  二是解决：超时法、等待图法。

其中等待图法指的是有一个 `有向图` ，每个 `节点` 表示正在执行的事务，每个 `边` 表示事务等待的情况，如果图中存在环路则说明出现了死锁。一般是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有的锁，使其他事务继续运行下去。

另外对于封锁对象的大小不同，比如封锁一个元组，一张表或者整个数据库，分为不同的封锁粒度；这个时候就要分粒度封锁，在分粒度封锁的基础之上又发明了一种方法叫做`意向锁`。

那么这个意向锁又是个什么东西呢？

意向锁建立在一个`多粒度树`上面，多粒度树就是将整个数据库按照对象的大小建立一棵树；  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70][]  
这个时候你在一个节点上面加上一个意向锁，那么它以及他的子节点默认被加锁；

> 具有意向锁的多粒度封锁方法提高了系统的并发度，减少了加锁和解锁的开销。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200703160138979.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA==,size_16,color_FFFFFF,t_70