冲突可串行化中的交换操作如何执行？附事务调度示例问询

咱们先把核心概念理清楚，再一步步分析你的问题：

交换操作的本质规则 #

首先看你引用的教材定义：

若调度S可通过一系列无冲突指令的交换转换为调度S'，则称S与S'冲突等价（conflict equivalent）；若调度S与某个串行调度冲突等价，则称其为冲突可串行化调度。

这里的无冲突指令交换，有两个硬性要求：

• 只能交换来自不同事务的连续操作（比如Ti的某步操作和Tj的某步操作，且在调度里是挨着的）
• 这两个操作必须是无冲突的——什么是冲突操作？就是两个操作满足：来自不同事务、访问同一个数据项、至少有一个是写操作。反过来，无冲突操作要么是访问不同数据项，要么是对同一数据项的两个读操作。

举个例子：Ti的write(Q)和Tj的read(R)可以交换；Ti的read(Q)和Tj的read(Q)也可以交换；但Ti的write(Q)和Tj的read(Q)、Ti的write(Q)和Tj的write(Q)都是冲突操作，绝对不能交换。

另外还有个底线：同一个事务内部的操作顺序绝对不能改——比如Ti原本是先write(Q)再read(Q)，你不能把它改成先read(Q)再write(Q)，这违反了事务的原子性逻辑。

原调度的问题根源 #

你给出的原调度是：

它的优先图出现环，是因为存在双向的冲突依赖：

• Ti的write(Q)先于Tj的read(Q)（冲突，所以Ti必须在Tj的这次读之前）
• Tj的write(Q)先于Ti的write(Q)（冲突，所以Tj必须在Ti的这次写之前）
  这就形成了Ti→Tj和Tj→Ti的环，所以调度不可冲突串行化。

你提出的两个调整方案是否合法？ #

第一个方案：把Tj所有操作移到Ti之后 #

这个调度本身是合法的串行调度，但问题是能不能从原调度通过合法交换得到它？
答案是不行。因为原调度中，Tj的write(Q)和Ti的write(Q)是冲突操作，而且它们在原调度里是Tj的write(Q)在前、Ti的write(Q)在后——这两个操作不能交换，因为是冲突的。你要把Tj的write(Q)移到Ti的write(Q)之后，必须交换这两个冲突操作，这违反了交换规则。

第二个方案：修改Ti内部操作顺序 #

这个方案直接违反了事务内部操作顺序的底线——Ti原本是先write(Q)再read(Q)，你把它改成了先read(Q)再write(Q)，这相当于修改了Ti本身的逻辑，完全不符合并发调度的要求，肯定是不合法的。

关键总结 #

交换操作的核心就是：只动不同事务的连续无冲突操作，绝对不能碰同一事务内部的操作顺序，也不能交换冲突操作。

内容的提问来源于stack exchange，提问作者Ahmet