2

有两个进程访问共享变量 x、y 和 z。每个进程访问用于保存这些变量的存储的不同副本。x、y 和 z 的值最初为 0。

过程1：

x = 1;
if (y == 0)
  z++;

和过程2：

y = 1;
if (x == 0)
  z++;

在完成这两个陈述之后，a) 顺序一致性模型和 b) 偶然一致性模型中 z 的可能值是多少？

我知道在顺序一致性中，进程按照程序指定的顺序执行。我相信在上面的示例中，z 的结果在顺序一致性模型中将为零，因为两个进程按照进程中指定的顺序同时执行。因此，没有执行任何 if 条件。但我不确定。

对于偶然的，相关的写入应该在所有进程中以相同的顺序进行。并发写入可以是不同的顺序。我无法弄清楚这个规则在我们的示例中是如何工作的。

4

1 回答 1

1

顺序一致的系统可以保证它的行为总是看起来与所涉及的某些顺序执行的读取和写入相同，与每个处理器正在执行的程序中读取和写入的相对顺序一致。它不保证不同处理器执行的两个操作会出现什么顺序。

你肯定有可能最终得到：

P1: store(x, 1)
P2: store(y, 1)
P1: load(y)     // 1
P2: load(x)     // 1

并且两个处理器都不会增加 z。但是，系统选择它也是完全合理的：

P1: store(x, 1)
P1: load(y)     // 0
P1: store(z, z+1)
P2: store(y, 1)
P2: load(x)     // 1

'z' 最终设置为 1。如果需要确定性结果，则需要添加锁定。顺序一致的系统确实可以保证 z 永远不会为 2：没有办法重新排序写入，以便两个进程都加载 0 值并增加 z 而不会违反顺序一致性。

相比之下，通常一致的系统并不能保证其行为总是与所涉及的单个顺序执行读取和写入相同。不同的处理器以不同的顺序查看其他人的写入是完全可以的，除非这些写入通常相关。你很可能最终得到：

// P1's local history
P1: store(x, 1)
P1: load(y)     // 0
P1: store(z, z+1)
P2: store(y, 1)

// P2's local history
P2: store(y, 1)
P2: load(x)     // 0
P2: store(z, z+1)
P1: store(x, 1)

z 的最终值为 2。什么因果一致性可以保证您执行的是第三个进程：

if (z == 2)
  print(x, y)

永远不会打印 0：

  • 如果 P3 加载/打印 x 和 y，则加载必须在其加载 z 之后发生
  • 如果 z 的负载值为 2，则它必须发生在 P1 和 P2 在 P3 的本地历史中的相同增量之后
  • P1 的 store(x, 1) 必须出现在它的 z 增量之前；P2/y 类似

通过传递性，包含打印语句的 P3 的任何本地历史都必须看到 x 和 y 的历史。

于 2015-07-30T04:25:20.107 回答