GATE | GATE-CS-2017(第二组)|问题64

两次交易 1. 和T 2 具体如下:

null
T1: r1(X)w1(X)r1(Y)w1(Y)

T2 : r2(Y)w2(Y)r2(Z)w2(Z)

r在哪里 (五) 表示事务T的读取操作 关于变量V和w (五) 表示事务T的写操作 在变量V上,T1和T2可以形成的冲突可序列化计划的总数为______

注: 这个问题以数字答案的形式出现。 (A) 54 (B) 55 (C) 56 (D) 57 答复: (A) 说明: 对于可冲突序列化的时间表,它们应该没有RW、WW、WR冲突。 在冲突序列化时间表中,我们必须看到在同一数据项上发生的两个事务中的操作不应该冲突。数据项y在两个事务之间共享,因此T1中对数据项y的读写操作可能会与事务T2对数据项y的读写操作产生RW、WR、WW冲突。 另一个限制是,每个事务的操作顺序都应该保持。我们不能更改交易的操作顺序。假设在T1中,如果读(x)在写(x)之前,那么在产生冲突的可序列化调度中,它的顺序应该相同。 在T1中,我们有两个相互冲突的操作r1(y)和w1(y) 在T2中,我们有两个相互冲突的操作r2(y)和w2(y) T1在y上的读写应该在T2的读写对之前或读写对到T2之后一起执行,因为交错它们会导致不一致,因为这两个事务都在同一个对象上执行操作。

只有一种方法可以将(冲突的)可序列化计划设置为T1->T2,因为T1的最后一个操作和T2的第一个操作相互冲突。 现在看看有多少个计划可以冲突序列化到T2->T1。

T1-
      r1(x)      w1(x)         r1(y)         w1(y)   

现在从右边看T2,如果我们从右边看T2,看到第一个冲突的操作 w2(z)和r2(z)与任何操作都没有冲突,但w(y)有冲突 选择W2(y),看看它能在多少地方。

Case1:     w2(y)      r1(x)      w1(x)         r1(y)         w1(y)   
Case2:     r1(x)       w2(y)    w1(x)         r1(y)         w1(y)   
Case3:     r1(x)       w1(x)     w2(y)        r1(y)         w1(y) 

选择每个案例,看看T2的其他操作可以占据多少位置。

案例1: w2(y) r1(x)w1(x)r1(y)w1(y) w2(z)和r2(z)可以占据多少位置? (请注意,这些w2(z)和r2(z)不能在之前出现。) w2(y) ) 也就是5C1+5C2=15(两者可以占用相同的空间,也可以占用两个不同的空间) 现在看,对于这15个位置中的每一个,r2(y)可以占据多少? 显然r2(y)不能在w2(y)之前出现,因此只有一个位置。 15×1=案例1中的15个总可能时间表。

案例2: r1(x) w1(y) w1(x)r1(y)w1(y) w2(z)和r2(z)可以占据多少位置? 也就是说4C1+4C2=10(两者可以占用相同的空间,也可以占用两个不同的空间) 现在看,对于这10个位置中的每一个,r2(y)可以占据多少? 只有两个位置,因为它必须在 w1(y) . 从总计10×2个可能的时间表开始。

案例3: r1(x)w1(x) w2(y) r1(y)w1(y) w2(z)和r2(x)可以占据多少位置? 也就是3C1+3C2=6 现在看,对于这6个位置中的每一个,r2(y)可以占据多少? 只有3个位置,因为它必须在 w2(y) . 6×3=案例3中的18个总可能时间表。 可冲突序列化为T2->T1=15+20+18=53的总计划。 可冲突序列化为T1->T2=1的总计划。 冲突可序列化为T2->​​​​​​​T1或T1->T2=53+1=54。

这个解决方案是由 帕鲁尔·夏尔马。 这个问题的小测验

© 版权声明
THE END
喜欢就支持一下吧
点赞8 分享