10.3 冲突可串行化调度的定义及判断方法

重要操作简记：

• 对数据 A 的第 i 次读操作：$r_i(A)$
• 对数据 A 的第 i 次写操作：$w_i(A)$

冲突的操作：涉及同一数据元素，至少有一次写操作。

冲突等价：当调度中的两个操作在交换时不产生冲突，且交换后的执行结果不发生变化，则称交换前后的两个调度是冲突等价的。

冲突可串行化：若一个调度与一个串行调度冲突等价，则该调度是冲突可串行化的。

判断一个调度 $S$ 是否是冲突可串行化的方法：

• 将调度按操作对象分组，保留先后顺序，仅观察至少有一个写操作的分组。
• 从分组中第一个写操作开始，按操作顺序对操作的索引画弧，完成优先图构建。
• 若优先图中存在环路，则此调度不是冲突可串行化的。

例题：

1. 已知调度 $S=r_2(A) \ r_1(B) \ w_2(A) \ r_3(A) \ w_1(B) \ w_3(A) \ r_2(B) \ w_2(B)$，判断调度 $S$ 是否冲突可串行化。

   参考答案

   解：将调度按操作对象分组，得到：

   • $S_A = r_2(A) \ w_2(A) \ r_3(A) \ w_3(A)$，优先图为：

   • $S_B = r_1(B) \ w_1(B) \ r_2(B) \ w_2(B)$，优先图为：

   合并所有优先图，得到：

   观察可知，优先图中没有环路，则此调度是可冲突串行化的。

2. 已知调度 $S=w_3(A) \ w_2(C) \ r_1(A) \ w_1(B) \ r_1(C) \ w_2(A) \ r_4(A) \ w_4(D)$，判断调度 $S$ 是否冲突可串行化。

   参考答案

   解：将调度按操作对象分组，得到：

   • $S_A = w_3(A) \ r_1(A) \ w_2(A) \ r_4(A)$，优先图为：

   • $S_B = w_1(B)$，优先图为：

   • $S_C = w_2(C) \ r_1(C)$，优先图为：

   • $S_D = w_4(D)$，优先图为：

   合并所有优先图，得到：

   观察可知，优先图中有环路，则此调度不是可冲突串行化的。