判断冲突可串行化

秒速五厘米 2022-05-30 12:41 170阅读 0赞

在数据库中，事务在并发调度过程中，会产生多种结果，什么样的调度是正确的？只有串行调度才是正确的结果。并发过程的结果只有与串行调度结果一样的才是正确的。这种并发调度被称为可串行化调度。

可串行化是并发事务正确调度的基本准则。对于一个并发调度，当且仅当它是可串行化的时候，才被认为是正确调度。

本文主要讲解判断可串行化调度的充要条件。

1.冲突操作指的是不同事务对于同一数据的读写操作与写写操作。

2.有些冲突操作是可以交换次序的，有些冲突操作不能交换次序。

3.不能交换位置的次序为：    （1）.不同事务的冲突操作。

（2）.同一事务的两个操作。

4.一个调度Sc在保证冲突操作（即3中的两种情况）次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc'，如果Sc'是串行的，则称调度Sc为冲突可串行化的调度。（如果觉得第四句话拗口不熟悉继续往下看就明白了）

例1：有两个事物T1与T2，初值A=10，B=20。

T1：读B；A=B+1 ;

T2：读A；B=A+1；

先执行T1，后执行T2，结果为A=21，B=22。

先执行T2，后执行T1，结果为A=12，B=11。

以上两种结果均是正确。除这两种结果外的结果，都是错误的调度结果。

### 冲突可串行化例：    ###

例2.先导解释：r1（A），其中r代read表读操作，1代表事务1，A代表A类数据。w2（B），w代表write写操作，2代表事务2，B代表数据B。

例2:有一调度，Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B),

选出其可以交换的次序，即不是第二种情况就可以交换次序：

r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)     这四个颜色块分别标记为A，B，C，D。（注意各块内部也是可以分开的）

经过上文的分析，从块与块之间的角度来看，我们可以得出A与B是冲突操作，C与D是冲突操作，符合第三条的第一种情况，所以这两个不能交换次序。

再从块内角度分析，A内部r1(A)w1(A)是冲突操作，符合第三条的第二种情况，所以这两个不能交换次序。同理可得BCD块内情况均是如此。

下面我们打破块的束缚，从整体来看，绿色块跟青色块可以交换次序，因为这两个操作不冲突，不符合第三条的任意一种情况。

r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

交换这两个块，可以得到如下结果：

r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)

再看新的绿色快=块与青色块，如果交换它俩也不会发生冲突：

r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

交换之：

r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)

最后这个结果就变为：

r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)

把原来的次序：r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

换成了

r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)

这就相当于执行了串行操作T1，T2。于是，这就是冲突可串行化。

串行化就是把同一个事务要做的读写操作按先后顺序排到一块。并发事务可以调整成串行化的话，就称为可串行化调度。

### 冲突不可串行化例： ###

有三个事务T1 = W1（Y）W1( X ) , T2 = W2(Y)W2( X ) , T3 = W3( X )。

调度L1=W1（Y）W1( X )W2(Y)W2( X )W3( X )是一个串行调度。

调度L2=W1（Y）W2(Y) W2( X )W1( X )W3( X )不满足冲突可串行化，但是调度L2是可串行化的。因为L2的调度结果与L1结果相同。为啥相同？自己随便代入值算算就知道了。

为什么说调度L2不可冲突串行化？如果把W1(X) 放到W2(Y) W2( X )前，变为W1（Y）W1( X )W2(Y)W2( X )W3( X )，就违反了第三条第一种情况，所以不能改变次序。但是可串行化的条件是只要满足其中一种串行调度次序就可以。

在本题中串行顺序有6种，分别是123,132,213,231,312,321.

上文的判断方法很稳妥，求出来的肯定是对的，但如果用优先图来做的话，时间效率会很高，而且容易识别出错误来。

## 大杀器：优先图    ##

用圆圈跟逻辑线来表示，圆圈表示事务，逻辑箭头线表示从事务1转向事务2.

例：有三个事务T1 = W1（Y）W1( X ) , T2 = W2(Y)W2( X ) , T3 = W3( X )。调度L2=W1（Y）W2(Y) W2( X )W1( X )W3( X )的优先图画法如下图所示：

![Image 1][]

有环就不能冲突可串行化，没有环的就可以。

画优先图注意事项：

1.所有资源都要画上，在逻辑线上标注资源名称，在圆圈内标注事务标号。、

2.如果要画从Ti到Tj的线，需要满足以下三种情况的其中一种：

（1）Tj在read（W）前，Ti要write（W）

（2）Tj在write（W）前,Ti要read（W）

（3）Tj在write（W）前,Ti要write（W）

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关 Hadoop基础-Apache Avro串行化的与反串行化

标题Hadoop基础-Apache Avro串行化的与反串行化 https://www.cnblogs.com/yinzhengjie/p/9127535.htm

约定不等于承诺〃/ 2023年03月01日 10:23/ 0 赞/ 13 阅读

相关会议室申请时间冲突判断

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

逃离我推掉我的手/ 2023年02月12日 06:25/ 0 赞/ 80 阅读

相关 php对象的串行化函数,PHP对象模型深度探索（11）：对象串行化

串行化可以把变量包括对象，转化成连续bytes数据，你可以将串行化后的变量存在一个文件里或在网络上传输，然后再反串行化还原为原来的数据。你在反串行化类的对象之前定义的类，PHP

桃扇骨/ 2023年01月17日 15:54/ 0 赞/ 127 阅读

相关对象的串行化（Serialization）

对象的串行化（Serialization）一、串行化的概念和目的 1.什么是串行化

小鱼儿/ 2022年08月24日 11:54/ 0 赞/ 179 阅读

相关可编程串行通信接口芯片8251A

8251A的基本功能 8251A是一种可编程的通用同步/异步接收发送器，通常作为串行通信接口使用，被广泛应用Intel80X86为CPU的微型计算机中。其基本功能为：

末蓝、/ 2022年08月18日 11:32/ 0 赞/ 531 阅读

相关理解VC的类的“串行化”概念

串行化是微软提供的用于对对象进行文件I/O的一种机制，该机制在框架(Frame)/文档(Document)/视图(View) 模式中得到了很好的应用。很多人对什么是串行化、怎么

深藏阁楼爱情的钟/ 2022年08月14日 02:44/ 0 赞/ 120 阅读

相关 java串行化技术

java串行化技术的实质就是把一个对象的状态写进一个Byte流里面，然后再通过Byte流反解出来该数据 [Java][]串行化技术可以使你将一个对象的状态写入一个Byte流里

分手后的思念是犯贱/ 2022年06月09日 05:10/ 0 赞/ 190 阅读

相关判断冲突可串行化

在数据库中，事务在并发调度过程中，会产生多种结果，什么样的调度是正确的？只有串行调度才是正确的结果。并发过程的结果只有与串行调度结果一样的才是正确的。这种并发调度被称为

秒速五厘米/ 2022年05月30日 12:41/ 0 赞/ 171 阅读

相关 PHP面向对象_对象串行化

在开发时有时候需要把一个对象在网络上传输，为了方便传输，可以把整个对象转化为二进制串，等到达另一端时，在还原成原来的对象。这一个过程简称串行化（序列化）案例：把一辆启程通

川长思鸟来/ 2022年05月14日 00:56/ 0 赞/ 181 阅读

相关 MFC-文件串行化（序列化）

二进制操作文件 CArchive类 1. 写文件（1）创建文件对象 CFile （2）以写方式打开文件 file.Open(\_T("…/test.txt")

约定不等于承诺〃/ 2022年05月09日 05:12/ 0 赞/ 175 阅读