判断冲突可串行化

秒速五厘米 2022-05-30 12:41 151阅读 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 条评论，151人围观）

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

相关阅读

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

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

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

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

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

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

相关对象的串行化（Serialization）

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

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

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

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

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

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

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

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

相关 Java串行化深度复制与性能调优

关于java的浅度复制与深度复制的概念大家可以在许多博文中找到我们直接上代码，看一下浅度复制的一个例子：这里有三个类College,Teacher,Student C

客官°小女子只卖身不卖艺/ 2022年08月04日 12:38/ 0 赞/ 128 阅读

相关 java串行化技术

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

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

相关判断冲突可串行化

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

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

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

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

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

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

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

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