可串行化调度和前趋图在线视频

同学们好

我是来自云南大学软件学院的包崇明

下面为大家介绍

可串行化调度和前趋图

前面我们学习了串行化调度

或者称之为串行化经历

要求一个事务的所有操作完成之前

其他事务的操作不能执行

不同事务的操作不会交错执行

由于串行化调度执行效率太低

我们还是希望事务的操作能够交错执行

从而引出可串行化调度的定义

一个经历中不同事务的操作是交错执行的

但这个调度执行的结果

和某一个串行调度执行的结果一样

这样的经历我们称为可串行化调度

注意这两种经历名称上的区别

串行化和可串行化

这两个概念容易混淆

注意它们的区别

一个可串行化调度执行结果

等同于某一个串行化调度执行结果

意味着

调度器只要按照经历给出的操作顺序执行

就可能得到正确的结果

那怎样判断一个经历

是否是一个可串行化经历呢

这是我们本节学习的内容

首先我们来看一下

如果不同事务操作交错执行

但是它们没有访问相同的数据项这种情形

由于没有访问相同数据项

不同事务操作不会相互影响

所以它们的执行顺序不重要

我们可以交换它们的执行顺序

将属于同一个事务的所有操作放到一起

这样就可以形成一个串行调度

所以这种情形下

这个经历是可串行经历

如果不同事务的操作访问了同一数据项

情况会发生变化吗

我们假设

由两个事务的不同操作访问同一数据项A

会发生什么样的情况呢

总共由四种情形

第一种是事务T1读取A

经过一些和数据项A无关的操作后

事务T2也读取A

这种情形下两个事务读取A的操作

可以交换顺序

第二种是事务T1读取A

经过一些和数据项A无关的操作后

事务T2给A写入新值

这种情形下两个事务对A的操作

不能交换顺序

因为交换后T1可能读到不同的A值

第三种是事务T1写A

经过一些和数据项A无关的操作后

事务T2读取A的值

在这种情形下

两个事务对A的操作也不能交换顺序

因为交换后T2可能读到不同的A值

第四种是事务T1写A

经过一些和数据项A无关的操作后

事务T2也写A

这种情形下

两个事务对A的操作也不能交换顺序

因为交换后T1可能写入不同的A值

T2也可能写入不同的A值。

经过上面分析

我们得到如果不同事务访问同一数据项

不同事务操作的顺序可能就不能交换

从而不能通过

交换不同事务操作顺序的方法

来得到串行调度

由此我们引出冲突操作的定义

我们把不同事务中

不能交换操作顺序的两个操作

称为冲突操作

从前面讨论的第2第3第4种

不能交换顺序的操作特点来看

它们具有下面特点

一

两个不同事务发出操作

二

访问的是同一个数据项

三

两个操作中至少有一个是写操作

总结一下

冲突操作的三种类型

第一种

事务Ti读取数据项A之后

事务Tj写数据项A

第二种

事务Ti写数据项A之后

事务Tj读数据项A

第三种

事务Ti写数据项A之后

事务Tj写数据项A

冲突操作的本质

是这两个操作的执行顺序不能交换

交换了执行顺序

会导致事务得到不同的执行结果

有了冲突操作的定义

可给出经历等价定义

对于两个包含相同操作的经历

如果所有的冲突操作对

在两个经历中都具有相同的执行顺序

这两个经历称为等价经历

现在我们可以给出可串行化经历定义

如果一个经历等价于一个串行经历

这个经历就是可串行化的

下面我们用三个例子来说明

如何根据可串行化经历的定义

来判断一个经历是否是可串行化的

第一个例子

是我们熟悉的转账和信用评估经历

我们把它称为经历H1

首先我们假设

经历H1等价于某一个串行经历S（h1）

根据经历等价的定义

H1和S（h1）的所有冲突操作对

执行顺序应该一致

我们来找H1的冲突操作

操作2事务T2写数据项A

和操作3事务T1读取数据项A是冲突操作

那么在

和它等价的串行经历S（h1）中

T2写数据项A

也应该在T1读取数据项A之前执行

由于串行经历S（h1）中

一个事务的所有操作执行完毕后

才能执行其他事务的操作

T2写A在T1读A之前执行

意味着在串行经历S（h1）中

事务T2在T1之前执行

接下来我们发现

H1中操作4和操作6也是一对冲突操作

经过同样的分析

我们可以得到

在等价的串行经历S（h1）中

事务T1必须在事务T2之前执行

现在我们得到了

串行经历S（h1）应该满足两个要求

事务T1必须在事务T2之前执行

同时事务T2也必须在事务T1之前执行

对于一个串行经历来说

任何时刻只允许一个事务先执行

这两个要求不能同时得到满足

意味着

我们假设

经历H1等价于一个串行经历S（h1）

是不可能的

从而证明了经历H1不是可串行化经历

这就是前面例子中信用评估错误的原因

下面我看第二个例子

经历H2

在这个经历中

首先事务T1读取A

接着事务T2读取A

事务T1写入A

事务T2写入A

最后是事务T1和T2相继提交

我们假设

这个经历等价于某个串行经历S（h2）

下面我们来找H2的的冲突操作

操作1和操作4冲突

意味着在串行经历S（h2）中

要求事务T1在T2之前执行

操作2和操作3冲突

在S（h2）中

要求事务T2在T1之前执行

同样

满足这两个要求的S（h2）是不存在的

证明H2是不可串行化的

这个不可串行化的经历

导致的不一致问题是一个

典型的丢失更新问题

也称为“脏写”

因为事务T1写入A的值

被后面事务T2写入的值覆盖了

事务T1对A的更新丢失了

所以称之为丢失更新

下面我们看第三个经历H3

在这个经历中

事务T1写A

接着事务T2也写A

事务T2写B

接着事务T1也写B

最后是事务T1和T2相继提交

同样我们假设

这个经历等价于某个串行经历S（h3）

H3中操作1和操作2冲突

操作3和操作4冲突

这两个冲突操作要求T1在T2之前执行

和T2在T1之前执行

在串行经历S（h3）中同时满足

可得到经历H3是不可串行化的

这个经历导致的不一致问题

我们称为盲写

事务T2覆盖了事务T1对A的更新

事务T1也覆盖了事务T2对B的更新

通过上面三个例子

我们学习了判断一个经历是否可串行的方法

总结一下

我们首先假设

这个经历等价于某个串行化经历

然后找出经历中所有的冲突操作

从每一个冲突操作

我们可得到在等价串行经历中

两个事务的一个执行顺序

如果能够找出一对矛盾的执行顺序

那这个经历是不可串行化的

否则我们说这个经历是可串行化的

下面我们用更直观的有向图的形式

来判断一个经历是否是可串行化的

这种有向图称为前趋图

它可以表示

隐含在经历冲突操作中的事务的执行顺序

对每个经历H

我们可构造一个前趋图

图的顶点代表经历中一个已提交的事务

用事务名称表示

图中由节点Ti指向节点Tj的一条有向边

代表经历中存在一个冲突操作对

Ti的一个操作和Tj的一个操作冲突了

且Ti的操作在Tj的操作前面执行

经历H中任何一个冲突操作

都对应着前趋图中的一条有向边

通过前趋图

我们很容易判断一个经历是否是可串行的

这就是可串行化定律

一个经历是可串行的

当且仅当

对应的前趋图中不存在环

现在来画出前面三个经历

H1H2和H3的前趋图

可发现这三个经历对应着同一个前趋图

这个前趋图中只有两个顶点

但两条有向边在这张图上形成一个环

根据可串行化定律可知

这三个经历是不可串行化的

好了

同学们

今天的课就到这

我们下节课见