4-3. 冲突可串行化调度在线视频

那么我们介绍了可串行化调度的概念之后

那么我们就有这样的一个想法

就说如果我要能构造一个可串行化的调度

那是不是就可以达到我们的目标了，是吧

但是我们如何去构造这个可串行化的这种调度呢

比如说两个事务想去访问相同的资源的时候

那么显然是说他们只有有冲突才会产生错误，是吧

如果他们之间没有冲突的话，那显然是不会产生错误的，是吧

那么他们怎么样才会产生冲突呢，那显然是他们的操作指令

那下面呢，我们就来分析一下就说两个事务

比如说他们要去访问相同的数据项的时候，同哪些指令会产生冲突呢

那么显然其他的一些指令不会产生冲突，只有读和写才会产生冲突

我们在这个PPT上给大家列出来，哪些这个操作指令会产生冲突呢

也就说，比如说两个事务Ti和Tj

那么Ti的命令是i，比如说i1,i2,in，Tj的命令是j1,j2,jn

那就只有是什么呢，比如说如果这个i这个命令，Ti这个命令，比如说它读

然后呢，Tj的命令可能也会是读或者是写

那么他们产生冲突一定是两个，比如说先读后写，先写后读，是吧

如果两个数都去读这个数据，实际上是没有什么冲突的

因为什么，它不修改呀，它只要读谁都有可能，但是写就不行了，是吧

如果我要写就相当于更新数据了

那么如果我更新了数据的话，那么我先读数据后更新和先写先更新后读

以及两个同时更新的话，那显然谈的是有冲突的，是吧

那么如果有冲突的话，那么它们的次序是非常重要的

那么这样的话呢，那我们说，如果我们构造这个可串行化调度的时候

如果它们的冲突指令，产生冲突的这个指令

如果与它们串行时候的执行次序是一样的话

那显然基本上它的结果就应该是正确的，是吧

所以这样的话，我们就引出另外一个概念，叫做冲突可串行化

那么冲突可串行化指的是什么呢，就说我们某一个并行调度

它如果经过非冲突指令，这样的一种转化，转化成了串行调度最后

比如说我们用这个图大家来看一下

前面呢比如说左边这是两个并发执行的事务，是吧

它们的命令基本上T1读A写A，读B写B，那么T2也是读A写A，读B写B

但是它们发生的时刻不一样

那么然后呢，我们对这两个事务的指令呢

比如说对它们进行一些转化

我们看哪些是冲突的，哪些是不冲突的，是吧

那么显然T1的Read(A)和T2的Read(A)是冲突的，是吧

但是呢，T1的Read(B)和T2的Write(A)和Read(A)是不是都是不冲突的

因为它们根本是不同的数据项，这样的话，如果我要做这样的一个改变

比如说，通过这种非冲突指令转变

最后我把T1和T2转化成一种先执行T1后执行T2的一种串行调度

那么这样的话，我左端的调度就是一个冲突可串行化调度

那冲突可串行化调度显然那是一种串行化调度了

也就是我从冲突指令这个角度来看

那我们再看一个例子，那就是上面这个T1

它也读A写A，T2是写A

像这样的一个调度呢，它就是不可串行化的

因为什么，它的冲突指令，它的指令全是冲突的，是吧

它是没有办法变成一个可串行的，指令无法交换

那么从这个冲突可串行化的这个定义来看

那么我们就可以，比如说，我按照这个反的方向，是吧

如果我把一个串行调度按照非冲突指令进行交换，变成一个并行调度的话

那这个并行调度显然就是冲突可串行化调度，是不是

所以这样的话，就为我们构造并发的可串行化调度提供了思路

那么这里面呢，就是我们还要注意一点呢，就说

冲突可串行化调度，它一定是一个一致性的调度

因为什么，它是非冲突指令转化的嘛

非冲突指令肯定不决定结果的正确性

所以呢，这个呢，一定是一个正确的这样的结论

再有一个呢，就是冲突可串行化它不是可串行化的必要条件

实际上可串行化是有很多种情况呢

你比如说像这个呢，左边这个例子

T1读A写A，读B写B，T2读B写B，读A写A

那么像这个，无论我们怎么变化，都变换不成串行的

这个呢，就说我们怎样对它进行变化，都变化不成先执行T1后执行T2

也就说变化不成串行调度

像这样的一种调度呢，它就是非冲突可串行化

但是我们知道，像这样的调度，虽然是非冲突可串行化

但它实际上是正确的，它是一个正确的调度

所以我们把它叫做可串行化调度

那么只是我们给它起一个名字，叫做视图可串行化

那么后面这个例子也一样

你比如说这样一个串行调度，是吧

然后呢，我们可以把它变换成这样的一个非冲突的可串行化调度

因为它最后的结果都是一样的

那么我们怎么样去判断一个这个冲突可串行化调度

因为一个调度是不是冲突可串行化的呢，我们可以用优先图

这个优先图呢，是由节点和带有有向的弧来表示

节点呢，是代表事务，那么每个事务比如说T1，T2，T3

那么有向弧指向的就是，比如说T1指向T2

就是指T1的命令和T2的命令它们之间是有顺序的，T1要先于T2

T2指向T3，T3要先于T1，T2要先于T3

就这样，就说它们冲突指令的顺序

如果这个有向弧是无环的

那么说明这个可串行化是冲突可串行化的

就是这个调度是冲突可串行化的

如果有向弧是有环的，那就说明这个调度是非冲突可串行化的

这就是我们用来判断冲突可串行化的这样的一个方法

这样的话呢，我们第四章关于并发调度的基本概念给大家就先介绍了这么多

我们大家要主要掌握一个是并发调度

那么另外一个是可串行化一致性调度，可串行化以及冲突可串行化这几个概念

以及呢，我们如何去用优先图来检测或者判断一个调度是不是冲突可串行化的